Ma l'induzione non fallisce?

[WiZaRd]

Salve a tutti.
Perdonatemi se vi pongo una domanda idiota, ma avendo discusso altre volte su questo forum di esempi di prove per induzione che sembrano funzionare ma poi non funzionano, torno per porre una domanda sulla seguente dimostrazione. La faccio perché l'ho trovata su una dispensa dell'università, quindi per il principio di autorità credo di essere io in errore.

Oggetto: dimostrare la seguente proposizione

$ \text{ Se } a,b,d \text{ sono tre qualunque elementi di } \mathbb{N} \text{ allora } a+b=a+d \implies b=d $

Dimostrazione

$ \text{Fissati } b, d \text{ l'implicazione da provare è vera se } a=0. \text{ Ammettiamola vera per } a \text{ e supponiamo }\\ (a+1)+b=(a+1)+d \text{ o, ciò che è lo stesso, } (a+b)+1=(a+d)+1. \text{ Ma questo, per l'iniettività della }\\ \text{ funzione successore, implica } b=d. $

E' evidente che si usa il principio di induzione, ma io mi domando: questo non è uno dei casi dove l'induzione fallisce? Voglio dire: qui l'ipotesi induttiva è una implicazione, che essa sia vera per $ a $ non ci assicura che sia vero l'antecedente di questa implicazione (i.e. (*) $ a+b=a+d $); inoltre perché assume che sia vero (**) $ (a+1)+b=(a+1)+d $? Mi son risposto: perché vuole provare che l'implicazione è vera per $ a+1 $ e se supponesse falsa la (**) l'implicazione sarebbe vera per falsità dell'antecendente, ma ammesso e non concesso che questo sia lecito, poi quando sfrutta l'iniettività del successore su $ (a+b)+1=(a+d)+1 $ non sta usando (*) senza sapere se è vera?

Non è forse forse sono in errore? Se lo sono, perché lo sono?

[Ani-sama]

Fa' attenzione che in questo caso la tesi è un'implicazione! Cioè tu vuoi dimostrare che quell'implicazione è vera! Cioè tu vuoi DIMOSTRARE l'IMPLICAZIONE, cioè vuoi dimostrare che SE SUPPONI una certa cosa ALLORA è vera una certa altra cosa, non so se mi spiego. E per farlo, cosa fai? A parte l'induzione, fissi gli elementi come nel membro sinistra (dell'implicazione) e cerchi di mostrare che è vero il membro destro (dell'implicazione).

[WiZaRd]

Penso di essere effettivamente in errore.
Si vuole provare per induzione che $ \forall a,b,d \in \mathbb{N}, a+b=a+d \implies b=d $.
Per $ a=0 $ si ha $ 0+b=b=d=0+d \implies b=d $ che è banalmente vera.
Occorre poi provare che $ (a+b=a+d \implies b=d) \implies ((a+1)+b=(a+1)+d \implies b=d) $: supposto dunque vero che (1) $ a+b=a+d\implies b=d $ si vuole provare che è vero (2) $ (a+1)+b=(a+1)+d\implies b=d $; ebbene se $ (a+1)+b\neq(a+1)+d $ allora (2) è vera perché ex falso quodlibet, sicché supponiamo $ (a+1)+b=(a+1)+d $: risulta, per associatività e commutatività, $ (a+b)+1=(a+d)+1 $, ma questa è l'uguaglianza tra i successivi di $ a+b $ ed $ a+d $, quindi per l'iniettività della funzione successore e non per l'antecendete della (1), si ha $ a+b=a+d $; quindi poiché è vera la (1) per ipotesi induttiva, si ha $ b=d $, sicché, finalmente, $ (a+1)+b=(a+1)+d \implies b=d $ è vera.

Dico bene o no?

[Ani-sama]

Mi sembra di sì, anzi sei stato sin troppo formale . Cioè, di solito uno passa sotto silenzio il fatto che, nel dimostrare un'implicazione, deve supporre anche il caso in cui l'ipotesi è falsa (e concludere perché falso implica vero è vero).

[WiZaRd]

OK. Grazie mille. E buona notte.

P.S.
Scusami ma non avevo visto il tuo primo post: stavamo scrivendo in contemporanea.

[Dani92]

$ \text{ Se } a,b,d \text{ sono tre qualunque elementi di } \mathbb{N} \text{ allora } a+b=a+d \implies b=d $

Ma serve l'induzione per dimostrarlo?

[Nonno Bassotto]

Ma serve l'induzione per dimostrarlo?

Risposta breve: sì.

Risposta lunga: se si vuole essere formali si definiscono i numeri naturali tramite una serie di assiomi, tra cui il principio di induzione. Tutte le usuali proprietà dei numeri naturali si ricavano da questi assiomi, e tutte quelle interessanti richiedono di usare anche l'induzione. Da questo punto di vista l'induzione diventa non un supertrucco per dimostrare cose altrimenti difficili, ma semplicemente una delle proprietà fondanti dei numeri naturali.

[Dani92]

Ok scusate l'ignoranza...

[Tibor Gallai]

A parte il dubbio sull'induzione, che è giustamente stato risolto, trovo tutto il resto molto diseducativo. A cominciare dalla "dispensa dell'università", che (potrei sbagliarmi, non potendola vedere per intero) mi sembra proporre la tipica lezione di fondamenti dell'aritmetica for dummies (senza offesa per i "dummies"), in cui non si fa distinzione tra teoria e meta-teoria. Tutto quello che viene detto nel thread, di conseguenza, è ammorbato dal medesimo equivoco.

Un grave errore metodologico è credere che una dispensa dell'università è fatta bene per il semplice fatto d'essere stata scritta da un professore universitario. I professori non sempre sono esperti di quel che insegnano, specie quando sono chiamati a fare corsi "introduttivi", del tipo di aritmetica elementare. Lì si pensa che un professore di matematica sia comunque adeguato allo scopo: sicuramente sa cos'è l'induzione, sicuramente sa risolvere una diofantea lineare, etc. Purtroppo, più le cose si avvicinano ai fondamenti logici (come in questo caso), più è necessario un esperto che ne parli senza creare enormi confusioni, a livello più o meno conscio. Quindi l'approssimazione grossolana secondo cui una dispensa universitaria è fatta bene andrebbe, a mio avviso, sostituita con un'approssimazione molto più precisa: una dispensa scritta in Italiano è fatta male.

Concretamente, l'equivoco di cui parlavo si basa su un'ambiguità: il "per ogni" è compreso nella formula che vogliamo dimostrare, o no? Cioè, vogliamo dimostrare la formula $ $\forall a, \forall b, \forall d, (a+b=a+d \implies b=d) $, o vogliamo, per ogni a, b, d, dimostrare la formula $ $(a+b=a+d \implies b=d) $? Ovvero: ci interessa dimostrare che è vero per ogni scelta delle variabili, o ci interessa dimostrare che nell'aritmetica si può dimostrare che, per ogni scelta delle variabili, è vero? A priori non è chiaro...

Nel primo caso, l'induzione non è affatto necessaria. Usiamo l'induzione a livello di meta-matematica, ma non all'interno della teoria. Potremmo convincerci che il fatto è vero anche senza dimostrarlo, proprio perché si tratta di una meta-dimostrazione, ed in effetti è ovvio che sia vero. E' altresì ovvio che sia dimostrabile nell'aritmetica, per ogni scelta delle variabili.

Nell'altro caso, ovvero quando il "per ogni" è incluso nella formula da dimostrare, servono effettivamente gli assiomi d'induzione. Però insisto nel dire che uno può contentarsi di dimostrare che il fatto è dimostrabilmente vero per ogni scelta delle variabili, e non di dimostrare che l'aritmetica dimostri che per ogni scelta delle variabili sia vero... Tipicamente, se il corso è di aritmetica e non di logica, ciò che interessa è proprio la prima cosa, ed è assolutamente irrilevante la seconda.

Al di là di questo, vorrei sottolineare come moltissime cose siano dimostrabili nella teoria dell'aritmetica del prim'ordine senza induzione (e con questo non voglio contraddire Nonno Bassotto, anche perché il concetto di "interessante" è opinabile, paradossi di Berry a parte). Tutte le formule vere sui naturali, nelle quali i quantificatori universali siano "limitati" (ovvero, sono della forma $ $\forall x\leq t $, dove t è un termine), sono dimostrabili nell'aritmetica del prim'ordine senza induzione. Altre cose richiedono invece l'induzione, come ad esempio il fatto che ogni numero è pari o dispari: $ $\forall x, \exists y\leq x, (x=y+y \vee x=y+y+1) $, o che $ $\sqrt 2 $ è irrazionale: $ $\forall x, \forall y, (x\cdot x \neq y\cdot y + y\cdot y) $. Tuttavia, l'aritmetica senza induzione può certamente dimostrare ad esempio che 37 è pari oppure dispari, e questo per qualsiasi scelta di 37. Il primo teorema d'incompletezza di Goedel dice semplicemente che, anche "elencando" nuovi assiomi (tipo quelli d'induzione, ma anche altri qualunque), esistono comunque formule vere per i naturali ma non dimostrabili. Come conseguenza di quel che dicevo prima, tali formule conterranno necessariamente un quantificatore universale non limitato.

[Nonno Bassotto]

Cioè, vogliamo dimostrare la formula $ $\forall a, \forall b, \forall d, (a+b=a+d \implies b=d) $, o vogliamo, per ogni a, b, d, dimostrare la formula $ $(a+b=a+d \implies b=d) $? Ovvero: ci interessa dimostrare che è vero per ogni scelta delle variabili, o ci interessa dimostrare che nell'aritmetica si può dimostrare che, per ogni scelta delle variabili, è vero? A priori non è chiaro...

Vorrei solo sottolineare che in questa frase hai invertito l'ordine dei due casi. Uno che legge potrebbe fare confusione.

By the way, il fatto che si possa lavorare senza induzione finché i quantificatori sono limitati è abbastanza intuitivo: basta scrivere esplicitamente tutti i passi induttivi fino a dove serve. Proprio per questo intendevo che questi enunciati sono meno interessanti. Quando si vuole dimostrare che una proprietà è vera per ogni numero naturale è quasi sempre necessario ricorrere a una forma di induzione.

[Nonno Bassotto]

Ok scusate l'ignoranza...

L'ignoranza è la condizione naturale che uno ha prima di venire a sapere le cose, non c'è niente da scusarsi.

[Tibor Gallai]

Vorrei solo sottolineare che in questa frase hai invertito l'ordine dei due casi. Uno che legge potrebbe fare confusione.

Esatto, specialmente perché dopo parlo di "primo caso" e "altro caso", riferendomi implicitamente alla seconda formulazione dei 2 casi.
Ero consapevole di questo, ma non mi andava di eccedere in pedanteria.
Segnalazione doverosa, comunque. Grazie.

[Tibor Gallai]

Quando si vuole dimostrare che una proprietà è vera per ogni numero naturale è quasi sempre necessario ricorrere a una forma di induzione.

Certo, se lo si vuole fare all'interno della teoria dell'aritmetica stessa. Ma in tutti i casi pratici, ovvero quando non stiamo facendo della logica fondazionale, non vogliamo studiare la potenza dimostrativa dell'aritmetica di Peano, etc, non c'importa nulla di confinarci all'interno dell'aritmetica, ma vogliamo poter dare delle meta-dimostrazioni, e quindi non usare l'induzione se non quando effettivamente semplifica le cose. Nel nostro dimostrare quotidiano abbiamo ben chiaro cosa siano i naturali, e vogliamo dedurne proprietà vere astraendo da una teoria specifica, e quindi ponendoci in una meta-teoria che mai assiomatizzeremo. Va bene così, è sempre andato bene così, e mai sarà possibile liberarsi da questa condizione: per ragionare su una teoria è necessario porsi in una super-teoria, e questo procedimento di "astrazione" non può umanamente essere fatto all'infinito.

Spero si intuisca che non sto facendo discorsi campati in aria, ma sto cercando di rispondere a Dani92, che giustamente chiedeva se è davvero necessario usare l'induzione per una cosa così banalmente vera.

[WiZaRd]

A Tibor Gallai.
Posso dire che non ho capito la distinzione che fai? Come dimostri senza il principio di induzione che in $ \mathbb{N} $ vale quella proprietà?
Comunque la dispensa in questione tratta la costruzione di $ \mathbb{N} $ con gli assiomi di Peano (che non sono espressi in linguaggio formale), quindi la costruzione degli altri insiemi numerici (con i passaggi al quoziente e le sezioni).

[Tibor Gallai]

Posso dire che non ho capito la distinzione che fai?

Certo! Stavo giusto accusando la dispensa di non fare codesta distinzione, quindi IMHO stenti a capire il discorso per colpa di chi l'ha scritta, e non per altro.

Come dimostri senza il principio di induzione che in $ \mathbb{N} $ vale quella proprietà?

Appunto: in che teoria? Una dimostrazione è sempre riferita ad una teoria, e non ha senso parlare di dimostrazione senza fissare una teoria. E' come se parlassi di "divisore" senza specificare di che numero... Se ti chiedessi "4 è un divisore?", cosa risponderesti? Mi chiederesti di quale numero... 4 è un divisore di 12 ma non di 18, etc.

Comunque la dispensa in questione tratta la costruzione di $ \mathbb{N} $ con gli assiomi di Peano (che non sono espressi in linguaggio formale), quindi la costruzione degli altri insiemi numerici (con i passaggi al quoziente e le sezioni).

Tagliamo la testa al toro? Me la linki? Così ne parlo male (o bene?) con cognizione di causa, e vediamo di amalgamarla con lo sproloquio qua sopra.