4.6 Induzione generalizzata, buon ordinamento[27M]

Proposizione 157 Induzione generalizzata

[1XR] Sia \(N∈ ℕ\), sia \(P(n)\) una proposizione logica vera per \(n=N\) e tale che

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

allora \(P\) è vera per ogni \(n≥ N\).

Presentiamo adesso il principio di induzione forte.

Proposizione 158 Induzione forte

[1XS] Assumiamo che un ordinamento (parziale) associato a \(ℕ\) soddisfi 143. Sia \(P(n)\) una proposizione logica vera per \(n=0\) e tale che

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

allora \(P\) è vera per ogni \(n∈ℕ\).

Questo principio è apparentemente più forte di quello usuale; ma vedremo che è in effetti equivalente.

Anche questo risultato si può generalizzare richiedendo che \(P(N)\) sia vera, e scrivendo l’ipotesi induttiva nella forma “\(∀ k, N≤ k≤ n, P(k)\)”: si otterrà che \(P(n)\) è vera per \(n≥ N\).

Si noti che il principio di buon ordinamento è in un qualche senso equivalente al principio di induzione; si veda 5.

E159

[1XN]Prerequisiti:143,133.Difficoltà:*.

Usate il principio di induzione 133 per dimostrare il principio di induzione forte 158

Attenzione: usate le proprietà nell’Ipotesi 143, ma non assumete che \(≤\) sia un ordinamento totale: infatti useremo questo risultato per dimostrarlo.

Soluzione nascosta: [UNACCESSIBLE UUID ’1XQ’]

E159

[1XP]Prerequisiti:143,158.Difficoltà:*.

Assumiamo che un ordinamento (parziale) \(≤\) associato a \(ℕ\) soddisfi 143. Usate il principio di induzione forte 158 per mostrare che ogni \(A⊆ ℕ\) non vuoto ha un elemento minimale, cioè

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

Soluzione nascosta: [UNACCESSIBLE UUID ’1XZ’]

E159

[273]Prerequisiti:2,2,4.Usate i prerequisiti per mostrare che \(({\mathbb {N}},\le )\) è ben ordinato.

E159

[1XT]Prerequisiti:158.Usate l’induzione forte per dimostrare che ogni \(n≥ 2\) si fattorizza nel prodotto di numeri primi.

Soluzione nascosta: [UNACCESSIBLE UUID ’1XV’]

E159

[1XY] Difficoltà:*. Sia \(A\) un insieme bene ordinato 1 dall’ordinamento \(≤\); sia \(m=\min A\); allora per proposizioni \(P(a)\) con \(a∈ A\) si può usare un metodo di dimostrazione, detto induzione transfinita, in cui

  • si richiede che \(P(m)\) sia vera, e

  • si dimostra il “passo induttivo”

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

Si dimostri che se la proposizione \(P\) soddisfa le due precedenti, allora \(∀ x∈ A,P(x)\).

Si dimostri inoltre che se \(A=ℕ\) allora il “passo induttivo” è equivalente al passo induttivo della induzione forte (definita in 158).

Altri esercizi che usano l’induzione sono: 4

  1. Come definito in 103.