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.
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica

