EDB — 1XY

[1XY] Difficoltà:*. Sia $A$ un insieme bene ordinato ¹ dall’ordinamento $\le$; sia $m=minA$; allora per proposizioni $P(a)$ con $a\in A$ si può usare un metodo di dimostrazione, detto induzione transfinita, in cui

• si richiede che $P(m)$ sia vera, e

• si dimostra il “passo induttivo”

  $$\forall n\in \mathbb{N}((\forall k<n,P(k))\Rightarrow P(n))$$

Si dimostri che se la proposizione $P$ soddisfa le due precedenti, allora $\forall x\in A,P(x)$.

Si dimostri inoltre che se $A=\mathbb{N}$ allora il “passo induttivo” è equivalente al passo induttivo della induzione forte (definita in [1XS]↺↻).