[A/L] (2021/22) Induzione - Esercizio 18

[matypist]

[LuginiAndrea]

Reputo entrambe le confutazioni di @Exyss errate.
Nella prima:

1. Non solo nel caso base, ma in tutti i passi viene assunto che $n = m = k$, in quanto per come funziona il $\max$, $k = m \lor k = n$, il che unito al fatto che $n = m$ implica $n = m = k$, ma su tutti i passi. L'errore nel ragionamento sta nel fatto che non viene mai assunto nel Passo induttivo che $n = m = k$, bensì viene assunto che $n = m = k+1$.
2. Anche qui, $n,m$ non sono valori fissati. Il testo ci dice che $\max\left(n-1, m-1\right) = 0$, ma $n \land m$ non sono gli stessi valori del caso baso, non capisco quindi come si possa dire che $n = m = 0$.

Procedendo alla confutazione dell'Induzione dell'esercizio:
Il problema sta nel fatto che $n-1$ ed $m-1$ non sono necessariamente $\in \mathbf{N}$.
Infatti poniamo $k = 0$. Ne segue che $\max\left(n, m\right) = 1 \implies n = 1 \lor m = 1$, ma non che $n = m = 1$, in quanto $n = 1 \land m = 0$ è comunque un assegnamento accettabile.
Ne segue che $n-1 \in \mathbf{N} \land m - 1 \not\in \mathbf{N}$, il che rende non applicabile l'ipotesi induttiva

[Exyss]

A distanza di un anno affermo che la mia precedente dimostrazione (ormai nascosta ma ancora visibile per chi volesse un esempio di come non fare una dimostrazione ) è assolutamente sbagliata in quanto vengono fatte assunzioni completamente distaccate dalla dimostrazione stessa. Difatti, come sottolineato da @LuginiAndrea, viene assunto che $m$ ed $n$ utilizzate nel passo induttivo siano le stesse del caso base, ovviamente ciò è errato.

---

La dimostrazione di @LuginiAndrea è corretta, l'errore è nell'inapplicabilità dell'ipotesi inuttiva nel caso in cui $n = 0 \lor m = 0$ come spiegato