Principio del buon ordinamento

Abbozzo matematica
Questa voce sull'argomento matematica è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

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

Sia A N {\displaystyle A\subseteq \mathbb {N} } un insieme non vuoto.

Allora A {\displaystyle A} ammette minimo, cioè esiste a ¯ A {\displaystyle {\overline {a}}\in A} tale che a ¯ a {\displaystyle {\overline {a}}\leq a} , a A {\displaystyle \forall a\in A} .[1]

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

P D I P B O {\displaystyle PDI\Rightarrow PBO}

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.

P B O P D I {\displaystyle PBO\Rightarrow PDI}

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

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

Bibliografia

  • Marco Manetti, Topologia, Springer, 2008, ISBN 978-88-470-0756-7.

Collegamenti esterni

  • (EN) Eric W. Weisstein, Principio del buon ordinamento, su MathWorld, Wolfram Research. Modifica su Wikidata
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica