Seconda forma del principio di induzione

Teorema

Sia P(n)nโˆˆN una famiglia di proposizioni indicizzata su nโˆˆN. Supponiamo che

  1. P(0) sia vera (BASE DELL'INDUZIONE)
  2. โˆ€n>0,(P(k)ย รจ veraย โˆ€k<n)โŸนP(n)ย รจ vera (PASSO INDUTTIVO)

Allora P(n) รจ vera โˆ€nโˆˆN.

Dimostrazione

Sia A:={nโˆˆNย |ย P(n)ย รจ falsa}, dimostriamo che A=โˆ….
Supponiamo per assurdo che Aโ‰ โˆ…. Grazie al teorema di buon ordinamento di N, A ammette minimo m. Osserviamo che mโˆˆAโŸนย P(m) รจ falsa.
Da (1) segue che mโ‰ 0.
Inoltre, se 0<k<m,ย kโˆ‰A, in quanto abbiamo che m=minย A, ma allora dalla (2) segue che P(m) รจ vera, che รจ impossibile. Segue che A=โˆ…, ovvero P(n)ย รจ veraย โˆ€nโˆˆN.