Principio del buon ordinamento

Questa voce sull'argomento matematica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Teknopedia. 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).

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

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

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

${\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.

${\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.

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

• (EN) Eric W. Weisstein, Well Ordering Principle, su MathWorld, Wolfram Research.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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