Principio del buon ordinamento: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
mNessun oggetto della modifica |
→Equivalenza con il principio di induzione: Correzione di un'imprecisione |
||
Riga 14:
== Equivalenza con il principio di induzione ==
Il '''principio del buon ordinamento''' è equivalente al '''[[principio di induzione]]''', nel senso che è possibile dimostrare, assumendo gli altri [[assiomi di Peano]] e il fatto che 0 è l'unico numero naturale a non avere predecessore, che il primo è vero [[se e solo se]] è vero il secondo. Diamo una traccia della dimostrazione. Nel seguito i due enunciati saranno indicati con PDI (per l'induzione) e PBO (per il buon ordinamento).
<math>PDI \Rightarrow PBO</math>
Riga 29:
:[[Dimostrazione per assurdo|Per assurdo]]:
:Se non fosse vuoto per il PBO conterrebbe un numero minimo ''m'', che non può essere lo 0 (che appartiene ad ''A''). Quindi c'è un predecessore ''m''-1 che non può trovarsi in '''N'''-''A'' (visto che il suo minimo è ''m'') e che quindi si trova in ''A''. Ma dalle ipotesi su ''A'' sappiamo che se ''A'' contiene ''n''=''m''-1 deve contenere anche ''n''+1=''m'', il che è falso. Siamo giunti ad una contraddizione e da questa deduciamo che era falsa l'assunzione che '''N'''-''A'' fosse non vuoto.
:
:L'assunzione che ogni numero naturale diverso da zero ammetta un predecessore è necessaria per dimostrare che PBO implica PDI. Infatti è possibile trovare un controesempio di un insieme che rispetti PBO e gli tutti gli assiomi di Peano, escluso PBI
:Consideriamo per esempio la terna <math>(X,~x_0,~s) </math> dove <math>X=\{n/2~~\forall n\in\mathbb{N}\}\subset \mathbb{Q} </math>, <math>x_0=0 </math>, <math>s(x)=x+1 ~~\forall x \in X </math>.
:* (P1) <math>x_0 \in X </math>
:* (P2) <math>\forall x \in X \Rightarrow s(x)\in X </math>
:* (P3) <math>x \neq y \Rightarrow s(x) \neq s(y) </math>
:* (P4) <math>s(x) \neq x_0 ~~~\forall x \in X </math>
:* (PBO) Poiché ogni sottinsieme di <math>\mathbb{N} </math> non vuoto ammette un elemento minimo, <math>\forall ~Y \subseteq X </math> non vuoto sia <math>M=\{n \in \mathbb{N} ~\mid~n/2 \in Y \} \Rightarrow \exist ~ m \in M </math> suo elemento minimo. <math>m/2 \in Y </math>è l'elemento minimo di Y. È evidente come <math>X </math> non rispetti PBI, infatti <math>\mathbb{N} \subsetneq X </math> contiene lo 0, e <math>\forall n \in \mathbb{N} \Rightarrow n+1 \in \mathbb{N} </math>.
==Note==
| |||