Un po’ di proposizioni

Nonostante le differenze di fondo tra l’approccio classico e quello intuizionista sulla nozione di cosa sia una proposizione, e quando una proposizione sia vera, siamo abbastanza fortunati che nella usuale pratica matematica i due approcci spesso si incontrino e che si possa sviluppare in entrambi i casi una matematica ricca ed interessante anche se non sempre coincidente, come abbiamo visto con gli esempio forniti all’inizio di questo capitolo.

Quel che vogliamo fare in questo paragrafo `e introdurre un insieme di affermazioni che sia abbastanza espressivo da permetterci di raccontare fatti matematicamente rilevanti e al tempo stesso tali che siano riconosciute come proposizioni sia da un classico che da un intuizionista, pur rimanendo ciascuno dei due all’interno della propria posizione epistemologica.

Proposizioni atomiche

Cominciamo quindi con le pi`u elementari tra le proposizioni possibili, quelle cio`e la cui analisi non possa essere condotta spezzandole in proposizioni pi`u elementari (il loro nome di proposizioni atomiche viene da qui). Abbiamo in realt`a appena incontrato una proposizione atomica, i.e. 3 + 2 = 5, e non dovrebbe essere quindi difficile capire di cosa si tratta. Ci`o di cui stiamo parlando sono quelle relazioni elementari che corrispondono direttamente ad una relazione matematica. L’esempio che abbiamo visto sopra corrisponde al fatto che la terna h3, 2, 5i appartiene alla funzione somma (si veda l’appendice A per i richiami sul linguaggio insiemistico). Altri esempi di proposizioni atomiche possono essere la proposizione che esprime la relazione identica, cio`e la diagonale di un insieme o la proposizione che esprime la relazione d’ordine tra i numeri naturali.

Naturalmente dal punto di vista classico `e immediato verificare che si tratta di proposizioni, visto che si tratta di affermazioni dotate di un valore di verit`a, ed `e pure facile capire quando la proposizione `e vera, visto che basta vedere se la relazione descritta corrisponde ad uno stato di realt`a (naturalmente bisogna pensare che la relazione in esame si estenda completamente di fronte a noi nella sua interezza, che potrebbe anche essere infinita, in modo che noi si possa vedere se l’n-pla richiesta appartiene oppure no alla relazione, quindi l’approccio classico richiede uno spazio infinito anche se la risposta alle nostre domande pu`o avvenire in un tempo nullo giacch`e basta guardare il grafico della relazione interessata per saper rispondere).

D’altra parte quelle considerate sono proposizioni anche da un punto di vista intuizionista perch`e sappiamo cosa conta come ticket della loro verit`a: basta fare il calcolo che ci porta a vedere se la relazione richiesta `e verificata. Naturalmente questo metodo funziona solo per le relazioni per le quali esista la possibilit`a di fare un calcolo per decidere sulla loro verit`a (e quindi richiede di sviluppare una qualche teoria delle relazioni calcolabili) e inoltre ci vuole del tempo per fare i calcoli. Tuttavia non si ha pi`u la necessit`a dello spazio infinito in cui tenere il grafico delle relazioni.

In un certo senso nel passaggio tra l’approccio classico e quello intuizionista si ha uno scambio tra uno spazio infinito e un tempo illimitato; ci troveremo nuovamente di fronte a questa dicotomia quando analizzeremo il rapporto tra semantica e sintassi (vedi capitolo 5).

C’`e un caso speciale di proposizioni atomiche che tornano molto utili nel parlare di matematica.

Si tratta della proposizione sempre falsa ⊥ e della proposizione sempre vera >. Dal punto di vista classico `e chiaro che esse non presentano problemi, ma anche dal punto di vista intuizionista possiamo riconoscere queste due affermazioni come proposizioni: la prima come la proposizione per la quale non c’`e nulla che possa convincermi della sua verit`a mentre la seconda `e la proposizione per la quale qualsiasi cosa pu`o convincermi della sua verit`a (per semplificarci la vita potremo dire che c’`e una ticket canonico ∗ per la proposizione >).

I connettivi

Introduciamo ora delle particelle linguistiche che servono per connettere, i.e. mettere assieme, delle proposizioni al fine di ottenerne di pi`u complesse.

La congiunzione

Il primo modo che pu`o venire in mente per combinare due proposizione `e forse fare la loro congiun-zione: se A e B sono le proposizioni che stiamo analizzando allora indicheremo la loro congiunzione

con A ∧ B. Chiariamo subito che si tratta della proposizione che `e vera esattamente quando sono vere sia la proposizione A che la proposizione B, ma possiamo essere sicuri che si tratta di una proposizione?

Come spesso succede, dal punto di vista classico non ci sono problemi visto che dobbiamo solo chiederci se ammette valore di verit`a e la risposta `e affermativa visto che abbiamo gi`a detto che A∧B `e vera esattamente quando lo sono sia A che B ed essendo A e B proposizioni esse ammettono sicuramente valore di verit`a.

Dal punto di vista intuizionista la situazione `e simile ma ci richiede di essere un poco pi`u dettagliati visto che dobbiamo anche dire cosa conta come ticket per A ∧ B. Ora il ticket per A ∧ B deve garantirci la verit`a di A ∧ B quando sono vere sia A che B, cio`e quando abbiamo un ticket sia per A che per B, e quindi il modo migliore per costruire il ticket desiderato consiste semplicemente nel mettere assieme il ticket per A con il ticket per B. Possiamo dire la cosa in termini leggermente diversi dicendo che se confondiamo una proposizione con l’insieme dei sui ticket allora A ∧ B `e il prodotto cartesiano tra A e B; quindi se a `e un ticket per A e b `e un ticket per B indicheremo con ha, bi il ticket per A ∧ B.

Esercizio 2.2.3 Si scriva il ticket per la proposizione (3 + 2 = 5) ∧ (2 × 2 = 4).

La disgiunzione

La seconda maniera di comporre due proposizioni che vogliamo considerare `e la disgiunzione: se A e B sono due proposizioni allora intendiamo analizzare la proposizione A ∨ B.

Che si tratti di una proposizione sia per il classico che per l’intuizionista pu`o essere verificato facilmente. Infatti per quanto riguarda il classico A ∨ B ha sicuramente un valore di verit`a in quanto `e vera se e solo se `e vera A o `e vera B. Inoltre per quanto riguarda l’intuizionista abbiamo un ticket per A ∨ B quando abbiamo un ticket per A oppure quando abbiamo un ticket per B ma, per evitare di perdere dell’informazione che potrebbe tornarci utile in futuro quando cercheremo di scoprire quali sono le conseguenze di A ∨ B, ci serve anche mantenere l’informazione di quale dei due; quindi A ∨ B corrisponde all’unione disgiunta di A con B e quindi i suoi ticket saranno indicati con i(a) se si tratta di un ticket che viene dal ticket a di A oppure con j(b) se si tratta di un ticket che viene dal ticket b di B.

Una proposizione solamente classica: la negazione

Una proposizione che nasce in modo naturale in ambito classico `e la negazione. Se A `e una propo-sizione indicheremo la sua negazione con ¬A. Si tratta della propopropo-sizione che `e vera esattamente quando la proposizione A `e falsa e quindi, per il classico, `e chiaramente dotata di un valore di verit`a.

Dal punto di vista intuizionista non si tratta invece di una proposizione perch´e non sappiamo cosa potrebbe essere un ticket che ci permetta di garantirne la verit`a visto che per l’intuizionista non esistono ticket che certificano la falsit`a di una proposizione.

Una proposizione solamente intuizionista: l’implicazione

D’altra parte esiste anche una proposizione che `e significativa solamente dal punto di vista intui-zionista mentre non ha molto senso per un classico. Si tratta dell’implicazione tra due proposizioni A e B che indicheremo con A → B. Quel che vogliamo per poter affermare che A → B `e vera `e che quando A `e vera sia vera pure B e quindi vogliamo essere sicuri che se abbiamo un ticket per A possiamo avere anche un ticket per B. A questo punto `e chiaro che un ticket per A → B altro non `e che una funzione che trasforma ticket per A in ticket per B e quindi A → B indica l’insieme delle funzioni da A verso B (per denotare tali funzioni possiamo utilizzare la notazione introdotta nell’appendice B).

Esercizio 2.2.4 Data una proposizione A, trovare un ticket per A → A.

Esercizio 2.2.5 Date le proposizioni A e B, trovare un ticket per la proposizione A → (B → A)

2.2. L’APPROCCIO CLASSICO E QUELLO INTUIZIONISTA 11

Esercizio 2.2.6 Date le proposizioni A, B e C, trovare un ticket per la proposizione (A → B) → ((B → C) → (A → C))

Esercizio 2.2.7 Date le proposizioni A e B, trovare un ticket per la proposizione (A ∧ (A → B)) → B

Esercizio 2.2.8 Date le proposizioni A, B and C dimostrare che c’`e un ticket per la proposizione (C ∧ A) → B se e solo se c’`e un ticket per la proposizione C → (A → B).

Esercizio 2.2.9 Date le proposizioni A e B, trovare un ticket per la proposizione (A ∧ B) → (A ∨ B)

Facciamo parlare assieme un classico e un intuizionista

L’implicazione `e quindi per sua natura una operazione dinamica, di trasformazione, e questo spiega perch`e non esiste una operazione classica completamente equivalente: l’approccio classico predilige lo studio della situazioni che non si evolvono nel tempo. Tuttavia, vista l’importanza dell’implicazione in matematica non esiste in pratica teorema che non abbia la forma di una implicadell’implicazione -deve esistere una controparte classica dell’implicazione.

Quel che ci serve `e quindi di inventare una maniera per un classico e un intuizionista di comu-nicare anche se essi usano due lingue non completamente compatibili visto che una manca della negazione e l’altra dell’implicazione. Anche in questo caso, come succede in generale quando si traduce una lingua in un’altra la traduzione non sar`a perfetta e quindi potr`a dare luogo a qualche incomprensione (ma si vedano gli esercizi 4.2.15 e 4.2.30). Tuttavia l’intuizionista guadagner`a una negazione, e quindi almeno in maniera approssimativa potr`a parlare della falsit`a di una proposi-zione, e il classico avr`a a disposizione un’implicazione, e sar`a quindi in grado di dare un senso agli enunciati dei teoremi.

Come al solito, quando in una lingua un termine manca si pu`o tentare di approssimarne il signi-ficato, al meglio possibile, utilizzando qualche giro di parole. Cominciamo quindi con l’esprimere intuizionisticamente la negazione. Il problema in questo caso `e quello di capire quando la proposi-zione A `e falsa, un concetto che manca nel bagaglio linguistico e concettuale dell’intuizionista. La sua migliore approssimazione `e quella di dire che una proposizione `e falsa quando assumere che sia vera conduce alla falsit`a, e quindi possiamo porre

¬A ≡_iA → ⊥

Esercizio 2.2.10 Trovare un ticket per la proposizione (A ∧ ¬A) → ⊥

Per quanto riguarda invece la definizione di una proposizione classica che approssimi l’implica-zione A → B dobbiamo tenere conto della seguente consideral’implica-zione: quel che si vuole `e che A → B sia vera se tutte le volte che A `e vera allora contemporaneamente anche B `e vera e quindi l’unico caso in cui A → B `e sicuramente falsa accade quando A `e vera ma B `e falsa. Questo ci porta a proporre la seguente definizione

A → B ≡c¬(A ∧ ¬B)

Come con ogni forma di traduzione da una lingua ad un altra non dobbiamo aspettarci che tutto fili liscio⁷. Infatti il rischio `e di trovarsi di fronte a risultati inaspettati se ci si dimentica che la traduzione `e solo una approssimazione di quel che si intendeva dire.

Ad esempio il classico potr`a restare sorpreso che l’intuizionista non sia in grado di esibire alcun ticket per la proposizione A ∨ ¬A se dimentica che non esiste per l’intuizionista un concetto di falso e quindi che l’intuizionista per poter produrre un ticket per tale proposizione dovrebbe essere in grado di produrre un ticket per A o una funzione che permetta di trasformare ogni ticket per A in un ticket per ⊥ e non c’`e alcun motivo perch`e questo dovrebbe essere possibile per una qualsiasi proposizione A.

7Tradurre `e sempre un po’ tradire ...

Ma forse ancora pi`u sorpreso potrebbe essere l’intuizionista se dimentica che quando il classico usa l’implicazione non intende dire come si trasforma una prova, ma solamente esprimere una giudizio su uno stato di realt`a. Ad esempio sembra sicuramente strano che un classico possa affermare che queste proposizioni sono vere

((A₁∧ A2) → B) → ((A₁→ B) ∨ (A2→ B)) (A₁→ (A1∧ A2)) ∨ (A₂→ (A1∧ A2))

se pensiamo all’implicazione come ad un modo di trasformare prove visto che la prima esprimerebbe il miracolo che se la proposizione B `e conseguenza di due proposizione allora in realt`a essa sarebbe conseguenza di una solamente tra esse, mentre la seconda, conseguenza della prima, esprime il fatto che la verit`a di una congiunzione di due proposizioni sarebbe conseguenza di una sola tra esse!

Esercizio 2.2.11 Dimostrare che dal punto di vista di un classico A → B `e vero se e solo se

¬A ∨ B.

Esercizio 2.2.12 Dimostrare che l’implicazione classica soddisfa le condizioni dimostrate sul-l’implicazione intuizionista negli esercizi 2.2.7 e 2.2.8, naturalmente sostituendo la condizione sull’esistenza di un ticket per una proposizione con la condizione che tale proposizione sia vera.

Esercizio 2.2.13 Dimostrare che dal punto di vista classico la negazione e la disgiunzione sono sufficienti per definire tutti i connettivi finora considerati, i.e. >, ⊥, ∧ e →.

Esercizio 2.2.14 Dimostrare che dal punto di vista classico la proposizione A ∨ ¬A `e sempre vera.

Se ne pu`o costruire un ticket intuizionista?

Esercizio 2.2.15 Dimostrare che dal punto di vista classico la proposizione ¬¬A → A `e sempre vera. Se ne pu`o costruire un ticket intuizionista?

Esercizio 2.2.16 Dimostrare che qualsiasi proposizione intuizionista che abbia un ticket `e classi-camente vera. Cosa si pu`o dire del viceversa?

2.2.2 Un linguaggio formale per scrivere di matematica . . .

. . . e anche di molto altro per quel che conta, ma per il momento quel che ci interessa `e vedere che c’`e la possibilit`a di esprimere in un linguaggio completamente formale, e quindi facile da controllare, le proposizioni che abbiamo introdotto nel paragrafo precedente e, ancora pi`u importante, quelle che introdurremo nei due paragrafi successivi.

Quel che ci serve `e semplicemente utilizzare nel caso dei connettivi logici che abbiamo finora introdotto la teoria generale per la scrittura di espressioni che si pu`o trovare nell’appendice B.

Secondo tale teoria un linguaggio utile per lavorare con oggetti matematici si pu`o costruire a partire da pochi costrutti (variabili, costanti, applicazione ed astrazione) a patto che variabili e costanti abbiano una ariet`a e l’applicazione possa avvenire solamente tra una funzione di ariet`a α → β ed un argomento di ariet`a α per dare un risultato di ariet`a β.

Nella teoria delle espressioni possiamo a grandi linee distinguere tra espressioni di ariet`a 0, che non si applicano, e espressioni di ariet`a α → β che si possono applicare. `E naturale pensare che, cos`ı come le funzioni di ariet`a zero sono gli elementi dell’insieme su cui una funzione `e definita, anche nel nostro caso le proposizioni debbano corrispondere alle espressioni di ariet`a 0 di un linguaggio adatto ad esprimere un linguaggio logico, che contenga cio´e i connettivi come costanti.

Per costruire le proposizioni che abbiamo usato finora possiamo quindi utilizzare le seguenti costanti con ariet`a

⊥ : 0 > : 0

∧ : 0 → (0 → 0) ∨ : 0 → (0 → 0)

¬ : 0 → 0 →: 0 → (0 → 0) e le seguenti abbreviazioni (i.e. zucchero sintattico):

A ∧ B ≡ ∧(A)(B) A ∨ B ≡ ∨(A)(B)

¬A ≡ ¬(A) A → B ≡ → (A)(B)

2.2. L’APPROCCIO CLASSICO E QUELLO INTUIZIONISTA 13

Naturalmente anche le proposizioni atomiche si possono scrivere come particolari espressioni con ariet`a a patto di introdurre le necessarie costanti con una opportuna ariet`a. Ad esempio se vogliamo scrivere la proposizione atomica che afferma che la somma di 3 con 2 `e minore di 7 possiamo scrivere, seguendo la usuale pratica matematica, (3 + 2) < 7 ma dobbiamo ricordarci che stiamo utilizzando la seguente definizione

(3 + 2) < 7 ≡< (+(3)(2))(7)

dove 3, 2 e 7 sono costanti di ariet`a 0, < `e una costante di ariet`a 0 → (0 → 0) e + `e una costante di ariet`a 0 → (0 → 0).

Esercizio 2.2.17 Scrivere come espressioni con ariet`a le seguenti proposizioni specificando l’ariet`a delle costanti che esse contengono.

1. (A ∧ B) → (A ∨ B) 2. (x < 3) → (2x < 6) 3. . . .

2.2.3 I quantificatori

I connettivi che abbiamo considerato finora, sebbene utili, non costituiscono sicuramente un lin-guaggio matematico sufficiente per esprimere fatti matematici anche semplici: come dire ad esempio che la somma tra due numeri naturali `e commutativa?

Quel che ci manca `e la possibilit`a di fare affermazioni esistenziali ed universali, che riguarda-no cio´e l’esistenza di un particolare elemento o l’insieme di tutti gli elementi di un dominio di cui vogliamo parlare. In matematica lo strumento che permette di risolvere questo problema di espressivit`a `e il ricorso alle variabili combinato con nuove possibilit`a di costruire proposizioni.

Quel che le variabili rendono possibile `e la scrittura delle funzioni proposizionali. In realt`a ne abbiamo gi`a (quasi) incontrata una nell’ultimo esercizio, i.e. (x < 3) → (2x < 6). Non si tratta di una funzione proposizionale ma pi`u semplicemente di una proposizione che contiene una variabile.

Tuttavia il passo da una espressione ad una funzione `e immediato, basta infatti una astrazione, e anche nel nostro caso il passo tra una proposizione che contiene una variabile ed una funzione proposizionale `e breve e basta una astrazione per permetterci di ottenere λx.(x < 3) → (2x < 6).

Ci`o che viene denotato da questa nuova scrittura dovrebbe essere chiaro: si tratta di una funzione che ad ogni elemento del dominio associa una proposizione.

Notiamo che nel seguito, con l’intento di rendere pi`u chiara la notazione, useremo varie no-tazioni per una proposizione, anche contenente variabili, e di conseguenza anche per le funzioni proposizionali. In particolare ricordiamo qui le seguenti

A per una proposizione che pu`o contenere delle variabili anche se esse non sono esplicitamente indicate

A(x) per una proposizione in cui vogliamo porre l’accento sulla variabile x;

vale la pena di notare che A `e applicata ad x e non pu`o quindi essere una espressione di ariet`a 0 e perci`o non pu`o essere una proposizione;

useremo la convenzione che x non appaia libera in A

A[x] per una proposizione in cui vogliamo mettere l’accento sul fatto che in A pu`o apparire la variabile x; questa notazione `e particolarmente comoda in quanto ci permette di scrivere A[t] per dire A[x := t]

Il quantificatore universale

Una volta che abbiamo detto cosa `e una funzione proposizionale λx.A possiamo da essa ottenere una nuova proposizione tramite il quantificatore universale. Come si fa sempre in matematica denoteremo tale proposizione con ∀x.A anche se si tratta solo di zucchero sintattico per l’espressione

∀(λx.A), dove ∀ `e una costante di ariet`a (0 → 0) → 0, capace quindi di trasformare una funzione proposizionale in una espressione di ariet`a 0.

Naturalmente ci resta da verificare che ∀x.A soddisfi le condizioni della definizione 2.2.1.

Per il classico non ci sono problemi particolari. Il significato che si vuole veicolare tramite la scrittura ∀x.A `e che la funzione proposizionale λx.A deve essere vera per ogni elemento del dominio. Visto che il classico suppone di avere una visione globale del dominio egli non ha, in linea di principio, problemi particolari a vedere se essa `e vera su ogni elemento del dominio e in questo caso dir`a che ∀x.A `e vera altrimenti dir`a che essa `e falsa. Alla fin fine per il classico la proposizione

∀x.A non `e poi molto diversa da una ∧ fatta tra tutte le proposizioni ottenute applicando la funzione proposizionale λx.A ai vari elementi del dominio, anche se questi potrebbero essere infiniti.

L’intuizionista sa di non avere una visione globale del dominio, in particolare nel caso questo non sia finito, e quindi non ha modo di seguire la strada del classico. Ma allora cosa potrebbe essere un ticket per l’espressione ∀x.A? Visto che si tratta di vedere se sono tutte vere le proposizioni ottenute applicando una funzione proposizionale a tutti gli elementi del dominio tutto quel che ci serve `e una funzione che vada in parallelo alla funzione proposizionale e che applicata ad un certo elemento del dominio fornisca un ticket per la proposizione che si ottiene applicando la funzione proposizionale allo stesso elemento del dominio.

Esercizio 2.2.18 Trovare un ticket per la proposizione ∀x.(A(x) → A(x)).

Il quantificatore esistenziale

Data una funzione proposizionale λx.A possiamo ottenere una proposizione anche in un secondo modo, cio´e utilizzando il quantificatore esistenziale per ottenere l’espressione ∃(λx.A), dove ∃ `e una costante di ariet`a (0 → 0) → 0, che seguendo l’usuale pratica matematica indicheremo con

∃x.A.

L’espressione ∃x.A viene riconosciuta come una proposizione dal classico che la usa per dire che esiste un elemento del dominio per cui A vale. Infatti per il classico questa operazione `e completamente significativa anche nel caso di un dominio infinito. Si tratta quindi di una operazione non molto diversa da una disgiunzione di tutte le proposizioni ottenute applicando la funzione proposizionale λx.A ai vari, anche infiniti, elementi del dominio.

Di nuovo per l’intuizionista le cose non sono cos`ı semplici. La domanda a cui rispondere per sapere cosa `e un ticket per ∃x.A `e: cosa mi potrebbe convincere della verit`a di una affermazione esistenziale? Abbiamo visto nella prima parte di questo capitolo molti esempi di affermazioni esistenziali e abbiamo fatto notare come ci sia una differenza sostanziale tra la nozione di esistenza che consiste nell’esibire l’oggetto di cui si vuole dimostrare l’esistenza e il limitarsi a far vedere che non `e possibile che tale oggetto non ci sia. Naturalmente le due cose coincidono dal punto di vista del classico che per decidere sull’esistenza di un oggetto deve solo guardare la realt`a e se succede che non `e vero che tutto gli oggetti che ha di fronte (anche una quantit`a infinita di oggetti) non soddisfano la propriet`a desiderata allora vuol dire che c’`e davvero un oggetto che la soddisfa.

Nel caso dell’intuizionista questa identit`a non pu`o essere verificata e quindi per convincersi della

Nel caso dell’intuizionista questa identit`a non pu`o essere verificata e quindi per convincersi della