Buon ordinamento dei numeri naturali

Teorema

(N,โ‰ค) รจ ben ordinato.

Dimostrazione

Supponiamo esista AโŠ‚N dove โˆ„ย minย A. Sia B:=Nย โˆ–ย A.
Dimostriamo che B=N e A=โˆ….

Procediamo per induzione di prima forma. Sia {0,1,...,n}โŠ‚Bย ย โˆ€nโˆˆN, ovvero P(n)=({0,1,...,n}โŠ‚B) รจ vera โˆ€nโˆˆN.

n=0 (BASE DELL'INDUZIONE)
Vale che {0}โŠ‚Bโ‡”0โˆˆBโ‡”0โˆ‰A.
Infatti se supponessimo per assurdo che 0โˆˆA, allora avremmo che 0=minย A.
Quindi 0โˆ‰AโŸน{0}โŠ‚B.

nโ‰ฅ1,ย nโŸนn+1 (PASSO INDUTTIVO)
Assumiamo che {0,1,...,n}โŠ‚B per qualche n. Proviamo che {0,1,...,n,n+1}โŠ‚B.
n+1โˆˆA? No, altrimenti avremmo che n+1=minย A, che รจ impossibile per ipotesi.
Allora n+1โˆˆBโŸนB=N,ย A=โˆ…
Il passo induttivo รจ stato fatto. Dunque, grazie al principio di induzione di prima forma, tutte le P(n) sono vere, ovvero B=N