Principio di induzione

Sia {P(n)}nโˆˆN una famiglia di proposizioni, ovvero affermazioni, indicizzata su N. Supponiamo

  1. P(0) รจ vera. (BASE DELL'INDUZIONE)
  2. โˆ€nโˆˆN,ย โ™ฃP(n)โŸนโงซP(succ(n)) รจ vera.
    โ™ฃ:IPOTESI INDUTTIVA
    โงซ:PASSO INDUTTIVO
    Allora P(n) รจ vera โˆ€nโˆˆN.

Dimostrazione

A:={nโˆˆNย |ย P(n)ย รจย vera}ย โŠ‚N

Osserviamo:

  1. โ‡”ย 0โˆˆA
    Sia nโˆˆA. Vale: nโˆˆAโ‡”P(n) รจ vera โŸนP(succ(n)) รจ vera โ‡”succ(n)โˆˆA
    Grazie all'assioma 2.8 (di induzione), A=Nโ‡”P(n) รจ vera โˆ€nโˆˆN