4.6 Generalized induction, well ordering[27M]

Proposition 157 Generalized induction

[1XR] Let \(N∈ ℕ\), and let \(P(n)\) a be logical clause, true for \(n=N\) and such that

\[ ∀ n≥ N, P(n)⇒ P(S(n))\quad , \]

then \(P\) is true for every \(n≥ N\).

Let us now present the principle of strong induction.

Proposition 158 Strong Induction

[1XS] Assume that a (partial) order associated to \(ℕ\) satisfies 143. Let \(P(n)\) be a logical clause, true for \(n=0\) and such that

\begin{equation} ∀ n∈ ℕ , \Big( \big(∀ k≤ n, P(k)\big)⇒ P(Sn)\Big)\label{eq:passo_ induttivo_ forte} \end{equation}
159

then \(P\) is true for every \(n∈ℕ\).

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 5.

E159

[1XN]Prerequisites:143,133.Difficulty:*.

Use the induction principle 133 to demonstrate the strong induction principle 158

Warning: use the properties in Hypothesis 143, but do not assume that \(≤\) is a total order: indeed this result is needed to prove it.

Hidden solution: [UNACCESSIBLE UUID ’1XQ’]

E159

[1XP]Prerequisites:143,158.Difficulty:*.

Assume that a (partial) order \(≤\) associated to \(ℕ\) satisfies 143. Use the strong induction principle 158 to show that every non-empty \(A⊆ ℕ\) contains a minimal element, i.e.

\[ ∃ a∈ A~ ,~ ∀ b∈ A~ ,~ ¬(b{\lt}a)\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’1XZ’]

E159

[273]Prerequisites:2,2,4.Use the prerequisites to prove that \(({\mathbb {N}},\le )\) is well ordered.

E159

[1XT]Prerequisites:158.Use strong induction to show that every \(n≥ 2\) factorizes into the product of prime numbers.

Hidden solution: [UNACCESSIBLE UUID ’1XV’]

E159

[1XY] Difficulty:*. Let \(A\) be a well-ordered set 1 by the order \(≤\); let \(m=\min A\); then for propositions \(P(a)\) with \(a∈ A\) you can use a proof method, called transfinite induction, in which

  • \(P(m)\) is required to be true, and

  • the following ”inductive step” is proven:

    \[ ∀ n∈ ℕ \Big( \big(∀ k{\lt} n, P(k)\big)⇒ P(n)\Big) \]

Show that if the proposition \(P\) satisfies the previous two requirements, then \(∀ x∈ A,P(x)\).

Prove also that if \(A=ℕ\) then the ”inductive step” is equivalent to the inductive step of strong induction (defined in 158).

Other exercises regarding "induction" are: 4

  1. As defined in 103.