Principio di induzione e principio del minimo

[Giso]

Salve a tutti!
Dopo aver elencato gli assiomi di Peano, al corso di aritmetica abbiamo introdotto le due forme del principio di induzione e il principio del minimo (o del buon ordinamento). Il prof ci ha assegnato come compito a casa di dimostrare il principio del minimo a partire dalla prima forma del principio di induzione.. potreste aiutarmi? Perchè c'ho pensato ma mi sembrano così distaccati che non riesco a trovare un nesso!
Ciao e grazie!

[Gi8]

Devi dimostrare questo (correggimi se sbaglio):
Sia $A sube NN$, $A$ non vuoto. Allora $EE bara in A$ tale che $AA a in A$ si ha $bara<=a$.


Equivalentemente, puoi dimostrare che l'unico sottoinsieme $A$ di $NN$ che non ha minimo è l'insieme vuoto.
Iniziamo la dimostrazione: sia $A sube NN$ che non abbia minimo.
Consideriamo $NN\\A$ e dimostriamo per induzione che coincide con tutto $NN$:

Base: $0 in NN\\A$. Infatti...

Passo: se tutti i naturali da $0$ a $n$ stanno in $NN\\A$, anche $n+1 in NN\\ A$. Infatti...

Dunque $NN\\A= NN$, cioè $A= O/$. Fine

[Giso]

Ok forse ci sono..

Base: ...infatti se non fosse $0\in\NN\backslash\A$, allora $0\in\A$ e dunque $A$ avrebbe un minimo, contro le ipotesi.

Passo: ...infatti ciò si deduce dalle ipotesi del principio di induzione. Dunque (sempre poiché assumo per ipotesi il principio di induzione) $NN\backslash\A\=\NN$ e perciò $A\=\emptyset$.

Così?

[Gi8]

La base è ok, ma il passo è sbagliato.
Devi dire "infatti se per assurdo non fosse $ n+1 in NN\\A$,
allora $n+1 in A$ e non ci sarebbero elementi di $A$ minori di $n+1$, quindi $A$ avrebbe minimo. Assurdo".

Il principio di induzione lo usi dopo.

[Giso]

Giusto!

Grazie di tutto, ciao!!

[Giso]

Ma aspetta, così facendo abbiam utilizzato la seconda forma del principio di induzione!

[asromavale]

il mio dubbio in merito alla dimostrazione sopra è il seguente : si è usato per dimostrare il tutto l'affermazione $A_n$ "$n!inT$ " ora non dovrei dimostrare il teorema per qualsiasi affermazione $A_n$? Cosi procedendo non ho semplicemente dimostrato che se "$n!inT$ " allora è vero il principio del buon ordinamento ?
grazie in anticipo

[Gi8]

Facciamo un attimo il punto. Vogliamo dimostrare il principio del buon ordinamento, cioè

Ogni sottoinsieme non vuoto di $NN$ ha minimo

Sia $T$ sottoinsieme di $NN$ che non ha minimo.
Dimostriamo per induzione (induzione forte, cioè il principio di induzione 2) che $n !in T$ per ogni $n in NN$.
(metto in spoiler la dimostrazione, è identica a quella scritta sul libro)

Testo nascosto, fai click qui per vederlo

BASE: $0 !in T$. Questo è vero, perchè se per assurdo $0 in T$ allora $0$ sarebbe il minimo di $T$.
PASSO: fissiamo $n>=0$.
ipotesi induttiva: per ogni $k in {0,1,...,n}$ si ha $k !in T$
tesi induttiva: $n+1 !in T$.

Se per assurdo $n+1 in T$, dato che per ipotesi nessun elemento minore di $n+1$ appartiene a $T$,
si avrebbe che $n+1$ sarebbe il minimo di $T$, assurdo.

Da questo segue immediatamente che $T= emptyset$

Ciò significa che l'unico sottoinsieme di $NN$ che non ha minimo è l'insieme vuoto.
Quindi abbiamo dimostrato il "principio del buon ordinamento", sfruttando il "principio di induzione 2".