EDB — 27M

4.6 Generalized induction, well ordering[27M]

Let us now present the principle of strong induction.

This principle is apparently stronger than the usual one; but we’ll see that it is in fact equivalent.

Even this result can be generalized by requiring that \(P(N)\) is true, and writing the inductive hypothesis in the form ”\(∀ k, N≤ k≤ n, P(k)\)”: you will get that \(P(n)\) is true for \(n≥ N\).

Note that the principle of well ordering is in some sense equivalent to the principle of induction; see [1XY]↺↻.

E2

[1XN]↺↻

E2

[1XP]↺↻

E2

[273]↺↻

E2

[1XT]↺↻

E2

[1XY]↺↻

Other exercises regarding "induction" are: [1XW]↺↻