Linguaggio: sintesi e sfide

Riepilogo

Questa lezione chiude l’unità dedicata al linguaggio della logica proposizionale. Ricostruisce la catena deduttiva che va dalla distinzione tra validità e verità, e dall’analisi dei paradossi, alla leggibilità unica delle formule e alla formalizzazione di enunciati e argomenti, indicando a ogni anello quale principio si usa e in quale lezione si dimostra; colloca quanto ottenuto rispetto al piano del corso e spiega perché il linguaggio già costruito pone la domanda dell’unità seguente, dedicata alla deduzione. Ripete nella sua valutazione d’uscita le abilità della valutazione d’ingresso e termina con sei sfide, di difficoltà superiore a quella dei problemi delle lezioni, che richiedono di combinare gli strumenti di più lezioni.

Obiettivi di apprendimento

Ricostruire l’ordine logico dei risultati dell’unità, identificando il principio su cui poggia ciascuno e la lezione in cui si dimostra.
Spiegare come si concatenano il principio di chiusura, la scomposizione in parole, il lemma del peso e la leggibilità unica, e perché da quest’ultima dipendono le definizioni ricorsive e il confronto tra formalizzazioni.
Distinguere ciò che l’unità ha dimostrato da ciò che ha ammesso come ipotesi (la bivalenza, lo schema di verità, il principio di induzione e la lettura della negazione congiunta) e da ciò che ha lasciato alle unità seguenti.
Risolvere problemi che combinano il lemma diagonale, il conteggio delle stringhe, l’induzione sulle formule, l’argomento del peso e lo sviluppo delle abbreviazioni.

Ciò che l’unità ha ottenuto

L’unità si era proposta di costruire, a partire da un alfabeto di due simboli, un linguaggio in cui ogni formula si legga in un solo modo, di dimostrare con rigore le proprietà di quel linguaggio e di gettare un ponte tra esso e la lingua in cui ragioniamo. Il proposito è stato raggiunto con poche riserve, ciascuna dichiarata al suo posto: la bivalenza e lo schema di verità, che la prima lezione non ha ammesso come verità ma come ipotesi esplicite, per esaminare che cosa accade quando le si sostiene insieme; il principio di induzione sui naturali, che si ammette come il quinto assioma di Peano; la lettura informale della negazione congiunta, che si stipula e che l’unità di semantica trasformerà in definizione; e l’indispensabile della teoria degli insiemi (appartenenza, inclusione e unione), che è stato insegnato dove serviva. Con queste riserve, il cammino percorso può leggersi come un’unica catena deduttiva in quattro tratti.

Ragionare e parlare del linguaggio

La lezione su che cos’è la logica matematica ha fissato l’oggetto del corso: non la verità degli enunciati, che spetta a ciascuna scienza, ma la sua trasmissione. Un argomento è valido quando la sua forma non ammette alcuna istanza con premesse vere e conclusione falsa, e da questa definizione si è dedotta l’unica cosa che la validità garantisce: se le premesse sono vere, lo è anche la conclusione; donde un argomento valido con conclusione falsa ha qualche premessa falsa, e una forma è non valida esattamente quando ha un controesempio. Lo stesso risultato ha trasformato l’analisi dei paradossi in un procedimento: se i passi di un ragionamento che termina in una contraddizione sono validi, qualche ipotesi è falsa, e risolvere il paradosso è trovare quale. Così si è trattato il mentitore, in cui la bivalenza e lo schema di verità non possono sostenersi insieme per una frase che si dichiara falsa, e così si sono trattati il paradosso di Berry e l’aggettivo «eterologico». Dal barbiere si è ricavato un lemma generale, il lemma diagonale, che dimostra che il barbiere non esiste e che il principio di comprensione senza restrizioni è contraddittorio. La lezione ha stabilito, infine, la distinzione tra linguaggio oggetto e metalinguaggio, e tra l’uso di un’espressione e la sua menzione, che governa tutto ciò che segue: i risultati dell’unità sulle formule non sono formule, ma metateoremi.

La lingua dei cerchi e dei dischi

La lezione sul linguaggio della logica proposizionale ha introdotto gli insiemi e le stringhe, ha contato le stringhe di ogni lunghezza (ce ne sono $2^{n}$ di lunghezza $n$ , e $2^{N + 1} - 2$ di lunghezza da $1$ a $N$ ) e ha costruito la lingua di base: le variabili $v_n = \sigO^{n}\sigI$ e un’unica regola, che da due formule $\varphi$ e $\psi$ forma $\sigI\varphi\psi$ . La clausola «nient’altro è una formula» è stata resa precisa definendo le formule come le stringhe che appartengono a tutti gli insiemi chiusi, e da questa definizione si è dedotto il principio di chiusura, con il quale si è dimostrato che ogni formula è una variabile o è $\sigI\varphi\psi$ , e non entrambe le cose, che ogni formula termina con un disco e che contiene un numero dispari di dischi. L’osservazione che le variabili e il disco isolato formano un codice prefisso ha dato la scomposizione unica in parole, e con essa la nozione di peso. La lezione ha costruito anche il metalinguaggio con cui si lavora da lì in avanti: le metavariabili, la negazione congiunta scritta $(\varphi \downarrow \psi)$ e le sei abbreviazioni ufficiali, ciascuna definita una sola volta a partire dalle precedenti, sicché ogni espressione abbreviata designa una sola stringa.

Induzione e leggibilità unica

La lezione sull’induzione sui numeri naturali e sulle formule ha giustificato i conteggi che la lezione precedente aveva concluso con «e così via», ha dedotto l’induzione forte da quella semplice e, applicando la prima alla lunghezza, ha ottenuto l’induzione strutturale, che risulta essere la stessa induzione sui naturali trasferita alle formule. Con questo strumento ha dimostrato il lemma del peso: ogni formula pesa $+1$ , e ogni prefisso per parole proprio e non vuoto pesa al più $0$ . Ne seguono, in quest’ordine, che nessuna formula è prefisso proprio di un’altra e che ogni formula composta si legge in un unico modo. La leggibilità unica è l’anello da cui pende il resto dell’unità: giustifica il procedimento di decisione che la lezione sul linguaggio aveva descritto come un debito che si salda, e legittima le definizioni per ricorsione (la lunghezza, il numero di variabili e di dischi connettivi, le sottoformule, la profondità e la sostituzione), che senza di essa potrebbero assegnare a una formula due valori diversi.

Dall’italiano alle formule

La lezione sulla formalizzazione del linguaggio naturale ha gettato il ponte verso la lingua. Ha fissato la convenzione delle lettere $p$ , $q$ , $r$ , $s$ e $t$ come nomi di cinque variabili determinate, ha richiesto che ogni formalizzazione dichiari il suo dizionario e ha dedotto, dalla sola lettura stipulata della negazione congiunta, la lettura di ogni abbreviazione. Con la leggibilità unica ha dimostrato che due raggruppamenti distinti degli stessi connettivi sono formule distinte, e con la definizione ricorsiva della lunghezza ha calcolato quanto misurano le abbreviazioni sviluppate, il che dà un criterio rapido per separare le formalizzazioni. Ha mostrato che il condizionale materiale è falso solo quando l’antecedente è vero e il conseguente falso, e che questa è l’unica lettura, dipendente solo dalla verità delle parti, che rende veri i teoremi condizionali della matematica; ha indicato ciò che la formalizzazione perde (quantificatori, tempo, causalità, modalità) e si è conclusa formalizzando argomenti completi come un insieme di premesse $\Gamma$ e una conclusione.

La figura seguente riunisce i quattro tratti in un’unica catena. Ogni nodo della colonna è una definizione o un risultato, numerato secondo l’ordine logico e unito da un arco agli anelli precedenti che la sua dimostrazione usa; attorno fluttuano i sostegni, cioè i principi a cui la catena ricorre di continuo, ciascuno unito da un tratto pieno agli anelli che vi si appoggiano e da uno punteggiato all’anello in cui viene stabilito, salvo quelli ammessi senza dimostrazione, che si disegnano come corone circolari. Facendo clic su un sostegno si evidenziano tutti gli anelli che lo usano, e ogni anello rimanda alla lezione in cui si dimostra. Si osservi che il procedimento di decisione, benché sia esposto nella lezione sul linguaggio, occupa il suo posto logico dopo la leggibilità unica, sulla quale si appoggia.

Sostegni della catena

ABivalenza. Ogni proposizione è vera o falsa, e non entrambe le cose; essere falsa equivale a non essere vera. Si ammette come ipotesi esplicita nell’analisi dei paradossi. Ammesso senza dimostrazione in questa unità.
BSchema di verità. Una frase è vera se e solo se ciò che dice è il caso. Si ammette come ipotesi esplicita; la soluzione di Tarski lo conserva, ma solo per le frasi di un linguaggio che non contiene il proprio predicato di verità. Ammesso senza dimostrazione in questa unità.
CPrincipio di induzione. Se una proprietà vale per $1$ e, ogni volta che vale per un naturale $k$ , vale per $k + 1$ , allora vale per tutti i naturali. È il quinto assioma di Peano, e si ammette. Ammesso senza dimostrazione in questa unità.
DLemma diagonale. Nessun oggetto $b$ di una collezione soddisfa $R(b, x) \Leftrightarrow \neg R(x, x)$ per ogni $x$ della collezione. Stabilito in: 3. Lemma diagonale.
EPrincipio di chiusura. Una proprietà che hanno tutte le variabili e che passa da $\varphi$ e $\psi$ a $\sigI\varphi\psi$ è posseduta da tutte le formule. Stabilito in: 5. Principio di chiusura.
FInduzione strutturale. L’induzione sulla complessità delle formule, dedotta dall’induzione forte sulla lunghezza: il suo caso base sono le variabili, e il suo passo induttivo, l’unica regola di formazione. Stabilito in: 9. Induzione strutturale.
GLeggibilità unica. Se $\sigI\varphi\psi = \sigI\varphi'\psi'$ , con le quattro stringhe formule, allora $\varphi = \varphi'$ e $\psi = \psi'$ . Stabilito in: 11. Leggibilità unica.
HLettura della negazione congiunta. La formula $(\varphi \downarrow \psi)$ è vera esattamente quando $\varphi$ e $\psi$ sono entrambe false. È l’unica lettura che si stipula; le altre si deducono da essa, e l’unità di semantica la renderà precisa. Ammesso senza dimostrazione in questa unità.

Tratto 1 Ragionare e parlare del linguaggio
- Distinguere la validità dalla verità e confutare una forma non valida con un controesempio.
- Riconoscere le ambiguità del linguaggio naturale e separare le letture di un enunciato.
- Distinguere il linguaggio oggetto dal metalinguaggio, e l’uso di un’espressione dalla sua menzione.
- Analizzare un paradosso isolandone le ipotesi e decidendo quale debba essere abbandonata.
1. Che cosa garantisce la validità. Se un argomento è valido e tutte le sue premesse sono vere, la sua conclusione è vera; donde un argomento valido con conclusione falsa ha qualche premessa falsa, e una forma è non valida esattamente quando ha un controesempio.
  Dimostrato in: Che cos’è la logica matematica.
2. Il paradosso del mentitore. Applicati alla frase $m$ , «la frase $m$ è falsa», la bivalenza e lo schema di verità danno $V(m) \Leftrightarrow \neg V(m)$ ; per un linguaggio che contiene $m$ , una delle due ipotesi deve essere abbandonata, e la via d’uscita di Tarski è che nessun linguaggio contenga il proprio predicato di verità, sicché $m$ non può essere formata.
  Usa: 1. Che cosa garantisce la validità. Si appoggia su: A (Bivalenza), B (Schema di verità). Dimostrato in: Che cos’è la logica matematica.
3. Lemma diagonale. Se $R$ è una relazione tra gli oggetti di una collezione $D$ , tale che ogni $R(x, y)$ è vera o falsa, nessun $b$ di $D$ soddisfa $R(b, x) \Leftrightarrow \neg R(x, x)$ per ogni $x$ di $D$ .
  Si appoggia su: A (Bivalenza). Dimostrato in: Che cos’è la logica matematica.
4. Il barbiere e Russell. Non esiste un uomo del villaggio che rada esattamente gli uomini del villaggio che non si radono da sé; e il principio di comprensione senza restrizioni è contraddittorio, perché afferma l’esistenza dell’insieme $Z = \{ x : x \notin x \}$ .
  Si appoggia su: D (Lemma diagonale). Dimostrato in: Che cos’è la logica matematica.
Tratto 2 La lingua dei cerchi e dei dischi
- Descrivere insiemi di stringhe e contare le stringhe di ogni lunghezza.
- Definire le formule come il più piccolo insieme chiuso e dedurne il principio di chiusura.
- Dimostrare proprietà di tutte le formule e usarle per scartare stringhe.
- Scomporre una stringa in parole e sviluppare le abbreviazioni fino alla lingua di base.
1. Principio di chiusura. L’insieme $\mathcal{F}$ delle formule è il più piccolo insieme di stringhe che contiene le variabili $v_n = \sigO^{n}\sigI$ e che, con $\varphi$ e $\psi$ , contiene $\sigI\varphi\psi$ ; pertanto, una proprietà che hanno le variabili e che passa da $\varphi$ e $\psi$ a $\sigI\varphi\psi$ è posseduta da tutte le formule.
  Dimostrato in: Il linguaggio della logica proposizionale.
2. Forma delle formule. Ogni formula è una variabile o è $\sigI\varphi\psi$ con $\varphi$ e $\psi$ formule, e non entrambe le cose: ogni variabile comincia con $\sigO$ , e ogni formula composta con $\sigI$ .
  Si appoggia su: E (Principio di chiusura). Dimostrato in: Il linguaggio della logica proposizionale.
3. Ultimo simbolo e numero di dischi. Ogni formula termina con un disco e contiene un numero dispari di dischi; donde né la concatenazione di due formule né la stringa $\sigI\varphi$ sono formule.
  Si appoggia su: E (Principio di chiusura). Dimostrato in: Il linguaggio della logica proposizionale.
4. Scomposizione in parole. Ogni stringa che termina con un disco si scompone in un unico modo in parole, cioè in variabili $\sigO^{n}\sigI$ e dischi isolati, perché ogni parola termina con il suo unico disco e nessuna è prefisso proprio di un’altra.
  Dimostrato in: Il linguaggio della logica proposizionale.
Tratto 3 Induzione e leggibilità unica
- Dimostrare per induzione semplice e forte, e dedurne l’induzione sulla complessità delle formule.
- Dimostrare il lemma del peso e dedurne la leggibilità unica.
- Decidere se una stringa è una formula e ricostruirne la formazione.
- Definire funzioni sulle formule per ricorsione e dimostrare relazioni tra di esse.
1. Induzione strutturale. L’induzione forte si deduce da quella semplice; applicata alla lunghezza, dà il principio di induzione sulla complessità: se le variabili hanno una proprietà e questa passa da $\varphi$ e $\psi$ a $\sigI\varphi\psi$ , tutte le formule la hanno.
  Usa: 6. Forma delle formule. Si appoggia su: C (Principio di induzione). Dimostrato in: Induzione sui numeri naturali e sulle formule.
2. Lemma del peso. Se ogni occorrenza di variabile pesa $+1$ e ogni disco connettivo $-1$ , ogni formula pesa $+1$ e ogni prefisso per parole proprio e non vuoto di una formula pesa al più $0$ ; in particolare, ogni formula ha un’occorrenza di variabile in più dei dischi connettivi.
  Usa: 8. Scomposizione in parole. Si appoggia su: F (Induzione strutturale). Dimostrato in: Induzione sui numeri naturali e sulle formule.
3. Leggibilità unica. Nessuna formula è prefisso proprio di un’altra; donde, se $\sigI\varphi\psi = \sigI\varphi'\psi'$ con le quattro stringhe formule, allora $\varphi = \varphi'$ e $\psi = \psi'$ .
  Usa: 7. Ultimo simbolo e numero di dischi, 8. Scomposizione in parole, 10. Lemma del peso. Dimostrato in: Induzione sui numeri naturali e sulle formule.
4. Procedimento di decisione. Una stringa che termina con $\sigO$ non è una formula; se termina con $\sigI$ , la si scompone in parole. Se la prima parola è una variabile, la stringa è una formula esattamente quando quella variabile è la sua unica parola. Se è un disco, si tiene il debito dopo di esso: se non si annulla mai, la stringa non è una formula; se si annulla, il taglio tra $\varphi$ e $\psi$ si trova dove ciò accade per la prima volta, e ogni tratto si esamina allo stesso modo, tenendo conto che la stringa vuota non è una formula.
  Usa: 6. Forma delle formule, 7. Ultimo simbolo e numero di dischi, 8. Scomposizione in parole. Si appoggia su: G (Leggibilità unica). Dimostrato in: Il linguaggio della logica proposizionale.
5. Definizione per ricorsione. Dati un valore per ogni variabile e una regola che calcola il valore di $\sigI\varphi\psi$ a partire da $\varphi$ , da $\psi$ e dai loro valori, esiste esattamente una funzione sulle formule che li rispetta; così si definiscono la lunghezza, le sottoformule, la profondità e la sostituzione, che produce sempre formule.
  Usa: 6. Forma delle formule. Si appoggia su: C (Principio di induzione), F (Induzione strutturale), G (Leggibilità unica). Dimostrato in: Induzione sui numeri naturali e sulle formule.
Tratto 4 Dall’italiano alle formule
- Formalizzare enunciati con un dizionario esplicito, decidendo la portata di ogni connettivo.
- Sviluppare abbreviazioni per decidere se due formalizzazioni sono la stessa formula.
- Distinguere il condizionale materiale dal «se… allora» della lingua e indicare ciò che la formalizzazione perde.
- Formalizzare argomenti completi come un insieme di premesse e una conclusione.
1. Lunghezza delle abbreviazioni. Se $L(\varphi) = a$ e $L(\psi) = b$ , le stringhe di $\neg\varphi$ , $(\varphi \vee \psi)$ , $(\varphi \rightarrow \psi)$ e $(\varphi \wedge \psi)$ misurano $2a + 1$ , $2a + 2b + 3$ , $4a + 2b + 5$ e $8a + 8b + 15$ ; due formalizzazioni di lunghezze diverse sono formule distinte.
  Usa: 13. Definizione per ricorsione. Dimostrato in: Formalizzazione del linguaggio naturale.
2. Portata e formule distinte. I raggruppamenti $((p \wedge q) \vee r)$ e $(p \wedge (q \vee r))$ sono stringhe distinte: se coincidessero, la leggibilità unica, applicata due volte, obbligherebbe la variabile $r$ a coincidere con la formula composta $(p \wedge q)$ .
  Usa: 6. Forma delle formule. Si appoggia su: G (Leggibilità unica). Dimostrato in: Formalizzazione del linguaggio naturale.
3. Condizionale materiale. L’implicazione $(\varphi \rightarrow \psi)$ , che abbrevia $(\neg\varphi \vee \psi)$ , è falsa solo quando $\varphi$ è vera e $\psi$ falsa; è l’unica lettura, dipendente solo dalla verità delle parti, che rende veri i teoremi condizionali della matematica.
  Si appoggia su: H (Lettura della negazione congiunta). Dimostrato in: Formalizzazione del linguaggio naturale.

Verso la deduzione. La catena si ferma dove il linguaggio è costruito e gli argomenti sono formalizzati come un insieme di premesse e una conclusione. Resta da decidere quando una formula segue da altre: prima manipolando simboli con regole, nell’unità seguente, e poi badando alla loro verità.