Principio di induzione e principio del minimo
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!
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!
Risposte
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
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
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ì?
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ì?
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.
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.
Giusto! 
Grazie di tutto, ciao!!
Grazie di tutto, ciao!!
Ma aspetta, così facendo abbiam utilizzato la seconda forma del principio di induzione!
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
Facciamo un attimo il punto. Vogliamo dimostrare il principio del buon ordinamento, cioè
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)
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".
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)
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".
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo