Principio del buon ordinamento

Da Wikipedia, l'enciclopedia libera.

Il principio del buon ordinamento (da non confondere con il Teorema del buon ordinamento) afferma che

Ogni insieme di numeri naturali non vuoto contiene un numero che è più piccolo di tutti gli altri

il che equivale a dire che l'insieme dei numeri naturali è un insieme ben ordinato (rispetto alla relazione d'ordine usuale).

[modifica] 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 che il primo è vero se e solo se e vero il secondo. Diamo una traccia della dimostrazione. Nel seguito i due principi saranno indicati con PDI (per l'induzione) e PBO (per il buon ordinamento).

Sia A un sottoinsieme dei naturali che non ha un elemento minimo: mostriamo che è vuoto dimostrando per induzione che il suo complementare N-A coincide con tutto l'insieme N dei naturali:

• base dell'induzione: N-A contiene lo 0, altrimenti 0 sarebbe in A e avremmo che A ha un elemento minimo (sfruttiamo il fatto che 0 è il più piccolo numero naturale).
• passo induttivo: se N-A contiene il numero n allora deve contenere anche n+1, altrimenti abbiamo che A contiene n+1 ma non n, quindi consideriamo il minimo numero tra 0 e n+1 che si trovi in A (essendo l'insieme finito l'esistenza del minimo non richiede il PBO), questo sarà l'elemento minimo di A contro l'ipotesi che A non ha elemento minimo.

Deduciamo che N-A coincide con N e quindi A è vuoto.

Sia A un sottoinsieme di N che contiene lo 0 e tale che se contiene n contiene anche n+1.

Consideriamo il complementare N-A. Mostriamo che è vuoto usando il PBO.

Per assurdo:

Se non fosse vuoto per il PBO conterrebbe un numero minimo m, che non può essere lo 0 (che è in A). Quindi c'è un predecessore m-1 che non può trovarsi in N-A (visto che il 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, quindi deduciamo che era falsa l'assunzione che N-A fosse non vuoto.