Algebre di Boole e di Heyting complete

Abbiamo quindi risolto il problema di definire una struttura di verit`a per i connettivi classici e per quelli intuizionisti. E ora il momento di passare ai quantificatori. Tuttavia il passaggio` non dovrebbe essere troppo penoso se ricordiamo che, almeno per il classico, i quantificatori altro non sono che una congiunzione arbitraria e una digiunzione arbitraria sebbene, in qualche senso, uniforme visto che si tratta di istanze della stessa proposizione su tutti gli elementi del dominio (vedremo nel capitolo 5 come risolvere i problemi tecnici che questo approccio richiede).

Questo suggerisce che quel di cui abbiamo bisogno `e un operazione che ci permetta di fare, nel caso del quantificatore universale, l’infimo di tutti i valori di verit`a ottenuti con l’interpretazione delle varie istanze di una certa proposizione e di un’altra operazione che ci permetta di fare, nel caso del quantificatore esistenziale, il supremo degli analoghi valori.

Il problema `e per`o che la definizione di algebra di Boole e di algebra di Heyting non ci garan-tiscono l’esistenza di altri infimi e supremi a parte quelli binari, e quindi quelli finiti, mentre pu`o ben succedere che una funzione proposizionale sia applicata ad una quantit`a non finita di oggetti.

La soluzione pi´u banale a questo problema `e quella di interpretare solamente in strutture che ci garantiscano la presenza di tutti gli infimi e supremi desiderabili.

Definizione 3.1.39 (Algebre di Boole e Heyting complete) Un’algebra di Boole o un’alge-bra di Heyting `e completa se ogni suo sottoinsieme U ha infimo e supremo, che indicheremo rispettivamente conV U e W U .

E chiaro che la soluzione di richiedere che infimo e supremo esistano per ogni sottoinsieme `` e, in un certo senso, esagerata visto che noi abbiamo bisogno solo degli infimi e dei supremi degli insiemi di valori di verit`a determinati dalle funzioni proposizionali e non di un sottoinsieme arbitrario

3.1. RETICOLI E ALGEBRE 27

(si ricordi che le proposizioni, e quindi le funzioni proposizionali, possono essere una quantit`a numerabile mentre i sottoinsiemi di un algebra di Boole o di Heyting possono essere una quantit`a pi`u che numerabile). Pagheremo la semplificazione che abbiamo deciso di fare adesso nel momento in cui dimostreremo il teorema di completezza nel capitolo 5.

Esercizio 3.1.40 Dimostrare che, per ogni insieme S, P(S) `e un algebra di Boole completa.

Esercizio 3.1.41 Dimostrare che l’insieme degli aperti di uno spazio topologico `e un algebra di Heyting completa (sugg.: attenzione all’intersezione arbitraria!).

Esercizio 3.1.42 Trovare un esempio di algebra di Boole non completa (sugg.: notare che ogni algebra finita `e completa).

Capitolo 4

Proposizioni e regole

Nell’ultimo capitolo abbiamo chiarito quali oggetti matematici useremo per lavorare con il concetto di verit`a che avevamo informalmente introdotto nel capitolo 2. Quel che vogliamo fare adesso `e studiare un calcolo che ci permetta di determinare le proposizioni vere in una certa struttura. Tale calcolo (calcolo dei sequenti) avr`a la forma di un insieme di regole che ci permettono di derivare proposizioni vere a partire da proposizioni vere, ma per essere sicuri che questo accada davvero avremo bisogno di essere estremamente precisi sulla nozione di verit`a dell’interpretazione di una proposizione. Per il momento abbiamo precisato come interpretare i connettivi, ma prima di andare avanti conviene aggiungere qualche considerazione relativa alle proposizioni atomiche e alle proposizioni con quantificatori.

4.1 Semantica e sintassi

Iniziamo precisando la definizione di struttura che abbiamo gi`a dato nel capitolo 2.

Definizione 4.1.1 (Struttura) Una struttura U ≡ (U, R, F , C) + A ´e costituita dalle seguenti parti:

• Un insieme di valutazione delle proposizioni A che pu`o essere sia una algebra di Boole che un algebra di Heyting;

• Un insieme non vuoto U detto l’universo della struttura;

• Un insieme non vuoto R di funzioni da elementi di U a valori in A;

• Un insieme, eventualmente vuoto, F di operazioni, vale a dire funzioni totali, su elementi di U e ad immagine in U ;

• Un sottoinsieme, eventualmente vuoto, C di U di costanti, vale a dire elementi particolari e designati di U .

Abbiamo gi`a visto qualche esempio di struttura anche se non abbiamo potuto essere abbastanza precisi sull’uso dell’insieme di valutazione delle proposizioni visto che le algebre di Boole e le algebre di Heyting sono state introdotto solamente nell’ultimo capitolo.

Supponendo di avere una struttura di cui vogliamo parlare, abbiamo gi`a suggerito come risol-vere il problema di determinare un linguaggio per esprimere le affermazioni che su tale struttura vogliamo fare. Infatti, abbiamo detto che il primo requisito che tale linguaggio deve possedere ´e che ci siano abbastanza simboli per denotare tutti gli oggetti che appaiono in R, F e C. Ma questo non ´e sufficiente per esprimere generiche propriet`a di una struttura, propriet`a che valgano cio`e per ogni elemento della struttura. Quel che ci serve ´e la possibilit`a di indicare un generico elemento della struttura, vale a dire che abbiamo bisogno delle variabili. Introduciamo quindi nel linguaggio un insieme numerabile (´e bene averne sempre di riserva!) di simboli per variabili v<sub>0</sub>, v<sub>1</sub>, ... oltre ad un simbolo predicativo P<sub>i</sub><sup>n</sup>, di ariet`a n, per ogni funzione R_i∈ R ad n posti, un simbolo funzionale f_jⁿ, di ariet`a n, per ogni operazione F_jⁿ ∈ F ad n argomenti, ed un simbolo c_k per ogni costante

29

designata appartenente al sottoinsieme C delle costanti. In questo modo ci sar`a nel linguaggio un simbolo per denotare ogni relazione, ogni operazione ed ogni costante designata della struttura che ci interessa.

Usando i simboli finora introdotti si possono costruire induttivamente delle espressioni, che chiameremo termini, nel modo che segue.

Definizione 4.1.2 (Termine) Le seguenti espressioni di ariet`a 0 sono termini

• v, se v ´e una variabile;

• c, se c ´e un simbolo per una costante;

• fj(t1, ..., tn), se t1, ..., tn sono termini e fj ´e un simbolo per una funzione di ariet`a n.

Niente altro ´e un termine.

Possiamo considerare i termini, almeno quelli che non contengono variabili, come i nomi che si possono usare nel linguaggio per denotare elementi dell’universo della struttura. Infatti

• un simbolo per costante ´e il nome nel linguaggio della costante che denota;

• un termine complesso, come f_j(t₁, ..., t_n), ´e il nome nel linguaggio dell’elemento dell’universo della struttura che si ottiene come risultato dell’applicazione della funzione denotata da fj

agli elementi i cui nomi sono t1,...,tn.

Nel caso in cui un termine contenga delle variabili non possiamo pi`u considerarlo come un nome per un preciso elemento del universo della struttura, ma dobbiamo piuttosto considerarlo come un nome per un generico elemento del universo della struttura che pu`o cambiare, al variare delle possibili interpretazioni delle variabili che il termine stesso contiene.

Tuttavia utilizzando solamente i termini non possiamo esprimere affermazioni; ad esempio non possiamo dire quando due termini sono due nomi diversi per lo stesso oggetto dell’universo. Questo

´

e il motivo per cui abbiamo introdotto nel linguaggio anche i simboli predicativi. Utilizzandoli possiamo infatti costruire delle nuove espressioni di ariet`a 0, vale a dire le proposizioni, che abbiamo definito nel capitolo 2.