Le strutture descritte da un insieme di proposizioni

Finora ci siamo concentrati sulla possibilit`a di utilizzare un linguaggio per descrivere una particolare struttura. Tuttavia, una volta che `e comparso sulla scena, il linguaggio pu`o anche giocare un ruolo diverso, e in realt`a esso `e spesso usato in matematica astratta in tale ruolo.

Scritto infatti un insieme di proposizioni possiamo chiederci se ci sono strutture che rendono vere tali proposizioni. Nella sezione precedente abbiamo visto che questo `e possibile quando ci siamo accorti che potevamo interpretare in strutture diverse le stesse proposizioni riguardanti l’operazione di successore. La questione non `e pi`u quindi di trovare le proposizioni che caratterizzano un modello ma piuttosto di trovare i modelli che soddisfano certe proposizioni; si tratta, in qualche senso, del problema duale del precedente.

Tanto per fare un esempio ben noto che viene dall’algebra possiamo considerare un linguaggio che contenga, come nel caso precedente una costante Eq di ariet`a 0 → (0 → 0) per costruire proposizioni atomiche, una costante ∗, anch’essa di ariet`a 0 → (0 → 0), per denotare una operazione binaria e una costante u di ariet`a 0 per denotare un particolare elemento. Supponiamo quindi di avere le seguenti tre proposizioni scritte utilizzando tale linguaggio

(associativa) ∀x.∀y.∀z.Eq(∗(∗(x)(y))(z))(∗(x)(∗(y)(z))) (neutro) ∀x.Eq(∗(x)(u))(x) ∧ Eq(∗(u)(x))(x) (inverso) ∀x.∃y.Eq(∗(x)(y))(u)

Non `e difficile riconoscere, dietro una notazione un po’ pesante, le solite condizioni che definiscono la struttura di gruppo. Le strutture per rendere vere queste proposizioni sono quindi quelle costruite nel modo seguente

hU, {=}, {·}, {1}i

dove · `e una operazione binaria sugli elementi di U e 1 `e un particolare elemento di U , a patto che

· e 1 soddisfino le condizioni richieste dalle proposizioni specificate, e si tratta naturalmente dei gruppi.

Questo nuovo modo di usare il linguaggio porta per`o con se la necessit`a di essere molto precisi nella definizione della nozione di interpretazione di una proposizione in una struttura visto che adesso non siamo pi`u in presenza di un linguaggio costruito ad hoc per una struttura. Per il momento quel che possediamo, in virt`u della teoria delle espressione dell’appendice B, `e una precisa definizione di come si costruisca un linguaggio, ma per sapere quando l’interpretazione di una proposizione risulta vera in una struttura quel che ci serve `e una “matematizzazione” della nozione di verit`a: `e quel che faremo nel prossimo capitolo.

Capitolo 3

La struttura della verit` a

Dopo la discussione presentata nel capitolo precedente sulle nozioni di verit`a matematica, affron-tiamo ora il problema di fornire una controparte formale di quelle spiegazioni intuitive. Infatti questo passo sar`a necessario nel momento in cui vorremo far vedere che c’`e una corrispondenza tra ci`o che `e vero in una famiglia di strutture e ci`o che `e dimostrabile formalmente a partire da un certo insieme di proposizioni (vedi capitolo 5).

3.1 Reticoli e algebre

Se dovessimo limitarci ad accontentare il classico il nostro compito, almeno nel caso di proposizioni che non usano i quantificatori, sarebbe semplice. Basterebbe infatti strutturare la verit`a in due valori: il vero, che possiamo indicare con 1, e il falso, che possiamo indicare con 0; perci`o l’insieme dei valori de verit`a sarebbe semplicemente 2l ≡ {0, 1}.

Se poi volessimo porre tali valori di verit`a in un disegno che rappresenti la relazione d’ordine

“essere pi`u vero di”, ponendo pi`u in alto i valori pi`u veri, ci ritroveremmo con la struttura di verit`a della figura 3.1

Se adesso volessimo dire come interpretare i connettivi che abbiamo introdotto nel precedente capitolo 2 non dovremo fare altro che ricorrere alle famose tabelline di verit`a che per completezza ricordiamo qui sotto.

Definizione 3.1.1 (Tabelline di verit`a) Le seguenti tabelline definiscono delle operazioni su 2l:

∧ 0 1

0 0 0

1 0 1

∨ 0 1

0 0 1

1 1 1

ν 0 1 1 0

Infatti, tutto quel che dobbiamo fare ora per interpretare le proposizioni del linguaggio `e dire se una proposizione `e interpretata in 1 (vero) o in 0 (falso).

0 1

Figura 3.1: algebra di Boole su 2 elementi

19

Definizione 3.1.2 (Interpretazione in 2l) Siano A e B proposizioni in un linguaggio per una struttura U . Allora una mappa V dall’insieme delle proposizioni in 2l `e una interpretazione proposizionale se soddisfa le seguenti condizioni:

V(>) = 1 V(⊥) = 0

V(A ∧ B) = V(A) ∧ V(B) V(A ∨ B) = V(A) ∨ V(B)

V(¬A) = νV(A)

Tuttavia il passaggio al caso in cui le proposizioni contengano anche quantificatori, e pi`u ancora l’analisi del caso intuizionista, richiedono un lavoro un po’ pi`u dettagliato. Vediamo prima di tutto come generalizzare quel che abbiamo fatto finora in modo che sia utilizzabile anche nel caso intuizionista dove non possiamo limitarci a considerare due soli valori di verit`a visto che oltre alle proposizioni vere, i.e. dotate di ticket, e alle proposizioni false, cio´e tali che l’assumere che abbiano ticket porterebbe a trovare un ticket anche per ⊥, ci sono anche tutte le proposizioni per le quali non ho (ancora?) un ticket ne per loro ne per la loro negazione.

L’idea resta quella di considerare una struttura basata su un insieme, i cui elementi rappresen-tano i valori di verit`a, e una relazione d’ordine a ≤ b su tale insieme, che sia riflessiva, transitiva e antisimmetrica (per le definizioni delle propriet`a delle relazioni si veda l’appendice A.2.1), e che intende esprimere l’ordinamento “b `e almeno tanto vero che a” o, equivalentemente, “se a `e vero allora anche b `e vero”.

Tuttavia se vogliamo poter interpretare tutte le proposizioni che abbiamo considerato nel ca-pitolo 2 un semplice insieme ordinato non ci basta e dobbiamo arricchirlo con delle operazioni ad hoc come abbiamo fatto qui sopra nella definizione 3.1.1 nel caso dell’insieme 2l.

Tanto per cominciare per poter interpretare congiunzione e disgiunzione abbiamo bisogno di opportune operazioni. Analizziamo prima il caso della congiunzione. Sappiamo che sia nel caso classico che in quello intuizionista succede che A ∧ B `e vero se e solo se A `e vera e B `e vera¹. Ma allora, per ogni interpretazione V(−), dobbiamo sicuramente avere che V(A ∧ B) ≤ V(A) e V(A ∧ B) ≤ V(B).

D’altra parte se c ≤ V(A) e c ≤ V(B) allora c ≤ V(A ∧ B) deve valere perch´e se assumiamo la verit`a di c allora ne possiamo ricavare la verit`a di V(A) e quella di V(B) che, per il significato che abbiamo attribuito a ∧ ci porta alla verit`a di V(A ∧ B).

Quindi per interpretare la congiunzione tra due proposizioni ci servir`a che ogni coppia di ele-menti a e b abbia infimo inf(a, b), i.e. il massimo dei minoranti comuni di a e b, cio´e un elemento tale che inf(a, b) ≤ a, inf(a, b) ≤ b e, per ogni c, se c ≤ a e c ≤ b allora c ≤ inf(a, b). Quindi d’ora in avanti considereremo solamente insiemi parzialmenti ordinati in cui tale operazione sia sempre definita.

Esercizio 3.1.3 Dimostrare che l’operazione di infimo `e associativa, commutativa e che 1 `e il suo elemento neutro.

Possiamo ragionare in modo analogo per quanto riguarda la disgiunzione, ma in questo caso la condizione da soddisfare `e che A ∨ B `e vera se e solo se `e vera A o `e vera B². Quindi `e immediato accorgersi che V(A) ≤ V(A ∨ B) e V(B) ≤ V(A ∨ B). D’altra parte, in maniera esattamente duale che per il caso della congiunzione, abbiamo pure che se V(A) ≤ c e V(B) ≤ c allora V(A ∨ B) ≤ c e quindi quel che ci serve `e che il nostro insieme parzialmente ordinato sia pure dotato del supremo sup(a, b) per ogni coppia di elementi a e b, i.e. il minimo dei maggioranti di a e b.

Esercizio 3.1.4 Dimostrare che l’operazione di supremo `e associativa, commutativa e che 0 `e il suo elemento neutro.

Esercizio 3.1.5 Dimostrare che, per ogni a e b, inf(a, sup(a, b)) = a e sup(a, inf(a, b)) = a.

1Naturalmente essere vero per l’intuizionista significa possedere un ticket, ma la sostanza non cambia visto che se abbiamo un ticket per A e un ticket per B allora possiamo farne la coppia e avere quindi il ticket per A ∧ B e se abbiamo il ticket per A ∧ B questo deve essere una coppia costituita da un ticket per A e un ticket per B.

2La cosa `e ovvia per il classico ma vale anche per l’intuizionista. Infatti se abbiamo un ticket per A o per B allora abbiamo sicuramente anche un ticket per A ∨ B e, viceversa, un ticket per A ∨ B altro non `e che un ticket per A o un ticket per B cui viene aggiunta l’indicazione di quale delle due.

3.1. RETICOLI E ALGEBRE 21

Una struttura che goda delle propriet`a che abbiamo individuato finora merita una definizione, anzi due.

Definizione 3.1.6 (Reticolo: approccio relazionale) Un reticolo `e un insieme parzialmente ordinato (S, ≤) tale che ogni coppia di elementi di S abbia infimo e supremo rispetto a ≤.

Definizione 3.1.7 (Reticolo: approccio algebrico) Un reticolo `e un insieme S dotato di due operazione ∧ e ∨ che soddisfino le seguenti condizioni

(associativa) a ∧ (b ∧ c) = (a ∧ b) ∧ c a ∨ (b ∨ c) = (a ∨ b) ∨ c (commutativa) a ∧ b = b ∧ a a ∨ b = b ∨ a

(assorbimento) a ∧ (a ∨ b) = a a ∨ (a ∧ b) = a

Esercizio 3.1.8 Dimostrare che le due definizioni 3.1.6 e 3.1.7 sono equivalenti (sugg.: in un verso si ponga a ∧ b ≡ inf(a, b) e a ∨ b ≡ sup(a, b) e nell’altro si definisca a ≤ b ≡ (a = a ∧ b))

Esistono “in natura” molti esempi di reticoli. Si vedano per cominciare i seguenti esercizi che ne definiscono alcuni tra i pi`u noti.

Esercizio 3.1.9 Dimostrare che, per qualunque insieme S, l’insieme P(S) con le operazioni di intersezione e unione `e un reticolo dotato di elemento minimo e massimo.

Esercizio 3.1.10 Dimostrare che le operazioni min e max definiscono un reticolo su un qualun-que insieme linearmente ordinato. Verificare quindi che nel caso della struttura sull’insieme 2l le operazioni ∧ e ∨ sono proprio min e max.

Esercizio 3.1.11 Dimostrare, senza utilizzare l’esercizio 3.1.8, che in un reticolo definito come in 3.1.7 vale che

(idempotenza) a ∧ a = a a ∨ a = a

Quindi i reticoli sono le strutture ideali per interpretare congiunzione e disgiunzione, anche se, vista la presenza di > e ⊥ dovremo limitarci ai soli reticoli con elemento minimo e massimo. Infatti, per poter interpretare > e ⊥, che sono sicuramente la pi`u vera e la meno vera tra le proposizioni, ci serve aggiungere la condizione che il nostro insieme ordinato abbia massimo elemento 1 e minimo elemento 0 in modo che presa una qualunque interpretazione V(−) possiamo porre, come abbiamo fatto nella definizione 3.1.2, V(>) = 1 e V(⊥) = 0.

Esercizio 3.1.12 Costruire esempi di reticoli dotati di minimo e massimo elemento, aventi solo minimo elemento e aventi solo massimo elemento e senza massimo e minimo elemento.

Tuttavia se analizziamo con un po’ pi`u di attenzione i connettivi di congiunzione e disgiunzio-ne ci possiamo accorgere che, sia per il classico che per l’intuizionista, vale la condiziodisgiunzio-ne che la congiunzione si distribuisce sulla disgiunzione, i.e.

(distributiva 1) A ∧ (B ∨ C) `e vera se e solo se (A ∧ B) ∨ (A ∧ C) `e vera e la disgiunzione distribuisce sulla congiunzione, i.e.

(distributiva 2) A ∨ (B ∧ C) `e vera se e solo se (A ∨ B) ∧ (A ∨ C) `e vera

mentre esistono anche reticoli che distributivi non sono e questi non sono quindi adatti per fornire una interpretazione completamente corretta.

Esercizio 3.1.13 Costruire esempi di reticoli distributivi e non distributivi.

Esercizio 3.1.14 Esibire un ticket per la proposizione (A ∧ (B ∨ C)) → ((A ∧ B) ∨ (A ∧ C)) e un ticket per la proposizione (A ∨ (B ∧ C)) → ((A ∨ B) ∧ (A ∨ C)).

Figura 3.2: reticoli non distributivi

Per fortuna, in virt`u di un famoso teorema di Birkhoff, che non dimostreremo in queste note (vedi [Bir67]), non `e difficile riconoscere i reticoli non-distributivi. Infatti, abbiamo gi`a fatto notare che possiamo rappresentare ogni reticolo con un grafo in cui gli elementi maggiori sono disegnati pi`u in alto (diagrammi di Hasse). Allora un reticolo `e non distributivo se e solo se con contiene alcun sottoreticolo della forma rappresentata in figura 3.2, dove per sottoreticolo intendiamo un sottoinsieme del reticolo di partenza chiuso per le operazioni di infimo e supremo di tale reticolo.

Esercizio 3.1.15 Dimostrare che se un reticolo soddisfa ad una delle uguaglianze richieste dalla distributivit`a allora esso soddisfa anche all’altra.

Esercizio 3.1.16 Dimostrare che i reticoli rappresentati nella figura 3.2 non sono distributivi.