Timeline
Chat
Prospettiva

Principio del buon ordinamento

principio matematico Da Wikipedia, l'enciclopedia libera

Remove ads

In matematica, il principio del buon ordinamento (da non confondere con il teorema del buon ordinamento), talvolta chiamato principio del minimo intero, o più propriamente principio del minimo intero naturale, afferma che:

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

In altre parole, un qualsiasi sottoinsieme non vuoto dei numeri naturali ammette minimo. Il che equivale a dire che l'insieme dei numeri naturali è un insieme ben ordinato (rispetto alla relazione d'ordine usuale).

Remove ads

Il principio

Sia un insieme non vuoto.

Allora ammette minimo, cioè esiste tale che , .[1]

Remove ads

Equivalenza con il principio di induzione

Riepilogo
Prospettiva

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 è 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).

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; se così non fosse 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 tutti i numeri da 0 a n allora deve contenere anche il numero n+1; se così non fosse, A conterrebbe n+1 ma nessuno degli elementi minori di esso; n+1 sarebbe dunque l'elemento minimo di A contro l'ipotesi che tale insieme non abbia 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 e 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 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.
Remove ads

Note

Bibliografia

Collegamenti esterni

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads