[A-L] (20 Settembre 2024) Esercizio 4

[FeddyLix17]

Trovare l'errore (o gli errori) nel Caso Base o nel Passo Induttivo della seguente pseudo-dimostrazione per Induzione.

• Tesi:

  Se il massimo di due numeri naturali è un numero naturale allora i due numeri sono uguali.

  La tesi equivale alla seguente proposizione: Per ogni naturale k, per ogni n,m naturali, se max(n, m) = k allora n = m.

  Dimostriamo questa proposizione per induzione su k.

• Base: k = 0.

  Siano n,m naturali tali che max(n,m) = 0.

  Ovviamente n = m = 0.

• Passo:

  Assumiamo l'Ipotesi Induttiva: per ogni naturale k, per ogni n,m naturali, se max(n,m) = k allora n = m.

  Dimostriamo che la tesi vale anche per k + 1, ossia: per ogni n,m naturali, se max(n,m) = k + 1 allora n = m.

  Siano n,m naturali tali che max(n,m) = k + 1. Dunque max(n - 1, m - 1) = k.

  Per ipotesi induttiva segue n - 1 = m - 1. Dunque n = m.