Principio del buon ordinamento

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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

Il principio[modifica | modifica wikitesto]

Sia un insieme non vuoto.

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

Equivalenza con il principio di induzione[modifica | modifica wikitesto]

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.

Note[modifica | modifica wikitesto]

  1. ^ a b M. Manetti, p.22

Bibliografia[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica