Breve introduzione alla teoria dei modelli

di Sirio Pasquini

Questo breve elaborato vuole servire a dare un’idea generale di cio cheva sotto il nome di teoria dei modelli. La teoria dei modelli permette di darealla matematica una struttura completamente logica, nel senso che attraver-so di essa e possibile ottenere una rappresentazione formale di ogni teoriamatematica esprimibile esclusivamente attraverso strumenti logici (proposi-zioni, predicati, regole di inferenza. . . ). Si puo infatti sempre pensare cheogni teoria matematica possa essere ricondotta sotto il suo formalismo, no-nostante la gran perte degli studiosi del campo, “faccia” matematica senzausare esplicitamente la teoria dei modelli e senza preoccuparsene troppo; sesi pensa che la sua definizione come area di ricerca a se stante risale al XXsecolo, ci si rende conto che generazioni di matematici ne hanno fatto a menoper tanto tempo. In effetti se la sua utilita fosse limitata ad un mero stru-mento descrittivo, un simile comportamento sarebbe ancora adottato, mala sua importanza va ben oltre. L’importanza che ha la teoria dei modellie dovuta alla possibilita che offre di separare le “frasi” nel linguaggio dellamatematica dalla loro interpretazione e validita sugli oggetti matematici.Questa possibilita puo avere un’importanza fondamentale per comprenderefino in fondo la dipendenza logica tra ipotesi e tesi ed i limiti di validita delleleggi.

Lo scopo di questa trattazione e rendere esplicito (o almeno il piu pos-sibile) la precedente frase. Per fare cio saranno pero necessari un po’ didefinizioni e di noioso formalismo. Si e cercato di evitare i tecnicismi, le no-tazioni pesanti e le dimostrazioni rigorose per rendere la trattazione adattaad un pubblico il piu eterogeneo possibile, ma per limiti intrinsechi dell’au-tore e forse anche della materia, non si e potuta evitare un inconfondibilearoma matematico. Si considerano prerequisiti i concetti di insieme, fun-zione ad un livello intuitivo ed alcuni rudimenti del calcolo proposizionalee predicativo1 con un dettaglio non superiore di quello adoperato nei corsidelle scuole superiori. In tutta la trattazione si fara riferimento alla teoriadel primo ordine che, anche se limitata in potenza descrittiva, permette diafferrare piu velocemente lo spirito della materia essendo piu intuitiva. Sifara comunque un breve cenno agli ordini successivi in 4.

1Un eccellente testo che va oltre l’introduzione qui necessaria per il calcolo deglienunciati e [Lemmon(1975)].

1

1 Linguaggi del primo ordine

Come si e detto, la teoria dei modelli riguarda il linguaggio e la sua in-terpretazione sugli oggetti a cui esso e riferito. Per prima cosa e dunquenecessario specificare meglio quello che si intende per linguaggio; per orail suo obbiettivo principale sara poter costruire sentenze che faranno riferi-mento ad elementi primitivi (punti, insiemi,. . . ), alle relazioni e alle funzionifra di essi. Piu formalmente, un linguaggio predicativo del primo ordine e uninsieme L di simboli, ciascuno appartenente ad una delle seguenti categorie:

• simboli di costante: servono per indicare elementi particolari del lin-guaggio (si pensi allo 0 per l’aritmetica degli interi in Z);

• simboli di variabile: servono per esprimere gli elementi generici. Ineffetti, e sempre comodo e non restrittivo (nel senso che e del tuttoinnocuo) supporre che ce ne sia sempre una quantita arbitraria, in mo-do che da non porre limiti al numero di elementi generici che possanoessere usati nelle frasi;

• simboli di relazione: servono per esprimere le proprieta e le relazionitra gli elementi. Ogni simbolo di relazione e n-ario per qualche n ≥ 1,nel senso che “riguarda ” n elementi primitivi;

• simboli di funzioni: servono ad indicare elementi che “dipendono” inqualche modo da altri elementi. Possono essere ricondotti a particolarisimboli di relazione: se un simbolo di funzione dipende da m elementi,si otterra un simbolo di relazione m + 1-ario, che mette in relazioneciascuna configurazione degli m simboli in ingresso con il risultato.Si supporra di aver fatto questa riscrittura per tutto il resto dellatrattazione.

Inoltre per la formazione delle proposizioni si useranno i simboli dei con-nettivi: ¬, ∧, ∨, ⇒ e ⇐⇒ , (rispettivamente con il significato di “non”, “e”,“o”, “se . . . allora” e “se e solo se”), le parentesi (con lo scopo di definire dellegerarchie) e i quantificatori ∃ e ∀ (rispettivamente “esiste” e “per ogni”). Sesi e infastiditi dal fatto che si faccia uso di simboli esterni al linguaggio, sipuo sempre pensare di estendere L in modo che contenga anche tali simbolidefiniti appartenenti ad una categoria speciale. Come e noto, si potrebbefare a meno di qualche connettivo, essendo infatti possibile esprimerne al-cuni come combinazione di altri, ma e innocuo e certamente piu comodoprenderli in considerazione tutti. Infine si segnala che alcuni autori defini-scono anche un simbolo speciale di identita assieme ai precedenti2. Secondola formalizzazione qui presentata si puo comunque inserire l’identita comesimbolo di relazione 2-ario.

2per esempio si veda [Chang-Keisler(1980)].

2

Una volta dati i simboli e necessario definire una sintassi cioe le regoledi utilizzo di tali simboli al fine costruire delle sentenze o asserzioni. Lacostruzione avviene dando delle regole basilari, utilizzabili iterativamenteper costruire frasi sempre piu complesse. Si definiscono innanzitutto formuleatomiche i simboli di relazione (e funzione) opportunamente completati consimboli di costante o variabili; dato cioe R simbolo di relazione n-ario diL , e presi s1, . . . , sn fra i simboli di costante e variabile (arbitrariamente),allora R(s1, . . . , sn) e una formula atomica; tutte le formule atomiche sonodel tipo precedente, al variare dei simboli nel linguaggio L . A questo puntosi definiscono le formule ben formate (fbf d’ora in poi) a partire dalle seguentiregole:

• data ξ formula atomica, (ξ) e fbf;

• date φ e ψ fbf, allora sono fbf (¬φ), (φ ∧ ψ), (φ ∨ ψ), (φ ⇒ ψ) e(φ ⇐⇒ ψ);

• data φ fbf e x simbolo di variabile, allora (∃x φ) e (∀x φ) sono fbf.

Si fa notare che in alcuni testi si chiamano predicati le fbf contenenti almenoun quantificatore qualsiasi mentre ci si riferisce alle altre come proposizioni.

Per la loro stessa definizione, le fbf sono costruite in modo induttivo (perpassi successivi). I mattoni fondamentali sono le formule atomiche e le fbfsono combinazioni di formule atomiche tramite connettivi e quantificatori.Data quindi una fbf φ, si possono prendere in considerazione tutte le fbfche intervengono nella sua costruzione, dette le sottoformule di φ. Sia ora xun simbolo di variabile che compare in φ; esso e detto vincolato se per ognivolta in cui compare, esiste una sottoformula ψ contenente quell’occorrenzaparticolare di x e tale che la sottoformula immediatamente successiva nellacostruzione di φ contenente ψ e della forma ∃x ψ oppure ∀x ψ. Il simbolo divariabile x e detto libero altrimenti. Sostanzialmente un simbolo di variabilee vincolato se ogni volta che compare esso fa riferimento ad un quantifica-tore. Si definiscono enunciati di L le fbf che non contengono simboli divariabile liberi. La ragione di questa ulteriore scrematura, sara piu chiarain seguito quando sara definita la semantica per gli enunciati. Per ora ci siaccontenti di intuirne il senso considerando che, poiche i simboli di variabileserviranno ad indicare elementi generici, non sarebbe chiaro che senso darloro se comparissero liberi da quantificatori: la frase e da intendersi riferitaa tutti gli elementi, solo ad alcuni, o magari ad uno?

Gli enunciati rappresentano quindi le frasi “sensate” nel nostro linguag-gio (da intendersi qui come sintatticamente corrette). Ora e possibile comin-ciare a parlare di una teoria. Una teoria in un linguaggio L e un qualsiasiinsieme T (non vuoto) di enunciati di L , che sono chiamati gli assiomi diT . Il calcolo proposizionale e predicativo del primo ordine ci permettono,utilizzando delle regole di deduzione (prove condizionali, ragionamenti per

3

assudo. . . ) di derivare delle nuove proposizioni assumendo quelle di T . Insimboli si indica con T ` φ, per dire che dalla teoria T deriva o si deducel’enunciato φ. Si faccia attenzione al fatto che le frasi di T non hanno ancoraun vero e proprio significato: ci si limita a pensare agli assiomi come puntidi partenza per un un procedimento di deduzione squisitamente formale eche di fatto a questo punto non ha alcuna interpretazione a se (per quanto leregole che segue ci sembrino familiari e imparentate con le “normali” dedu-zioni logiche di tutti i giorni); ai simboli di variabile costante e relazione none associato alcun significato. Si vedra nella prossima sezione come avvienequesta interpretazione.

Per la natura del procedimento di deduzione formale, vi sono alcune ca-ratteristica che una teoria puo soddisfare. La piu importante e la coerenza:T e coerente se non esiste un enunciato φ in L per il quale valga T ` φ eT ` (¬φ). In sostanza si richiede che T non contenga contraddizioni, poichediscende dalle regole di deduzione in se e senza bisogno di alcuna ipotesiil principio secondo cui se si deduce qualcosa, non deve essere possibile de-durne anche il contrario3. Si puo poi richiedere agli assiomi di T di essereindipendenti ; un enunciato φ che appartiene a T e indipendente se (la teoriaottenuta eventualmente togliendo φ da) T non deduce la stessa φ o la suanegazione: in simboli φ e indipendente da T se T \ {φ} 0 φ e T \ {φ} 0 ¬φ.L’idea dell’indipendenza per una teoria e di garantire che i suoi assiomi noncontengano inutilmente frasi che sono gia delle deduzioni; non ci sono peroprincipi legati al procedimento di deduzione che la impongano. Diventaimportante quando si vuole comprendere a fondo la dipendenza logica deirisultati: da quali ipotesi seguono quali conseguenze? Si noti inoltre chepresa una teoria, pensare di eliminare gli assiomi non indipendenti fino arenderla costituita da soli indipendenti non e cosı scontato come puo sem-brare a prima vista: come si fa infatti ad essere certi di avere finito? None detto che un enunciato sia sempre deducibile, ossia se lui o la sua nega-zione possano essere dedotti a partire da una teoria. Nel caso in cui cio siagarantito, la teoria e detta completa; per qualsiasi suo enunciato φ, allora oT ` φ o T 0 φ (o entrambi nel caso in cui non sia coerente).

2 Strutture del primo ordine

Finora si e parlato soltanto dei linguaggi, adesso si introdurra la semantica,cioe il modo di mettere in relazione il linguaggio con il significato. Innan-zitutto e necessario chiarire quali sono gli oggetti che sottendono ad unlinguaggio. Si definisce struttura del primo ordine M una coppia di insiemi

3questo non significa che le regole lo vietino o lo impediscano, semplicemente il fatto diavere una contraddizione e in ulteriore contraddizione con tale principio dedotto da ogniteoria.

4

A e P , A e detto insieme degli individui e P delle relazioni4. Su A non sifanno ulteriore ipotesi, mentre si richiede che una relazione R ∈ P non siaaltro che un sottoinsieme del prodotto cartesiano di A con se stesso per nvolte (cioe R ⊆ A×A× · · · ×A) per qualche n intero; la relazione R di P edetta n-aria. A questo punto dovrebbe risultare piuttosto intuitivo come sipossa definire l’interpretazione dei simboli di un linguaggio L . Essa e datadalla funzione o mappa di interpretazione I, una funzione definita da unsottoinsieme di L a valori in A∪P , in modo da mappare simboli di costantiin individui e simboli di relazione n-ari in relazioni n-arie. Un enunciato φdi L e definito in M se ogni simbolo di costante e relazione che comparein φ, appartiene al dominio di definizione di I (cioe ogni simbolo in φ einterpretabile tramite I con un elemento di M). A questo punto si puo dareun set di regole affinche risulti definita la validita in M per gli enunciati diL definiti in M , molto similmente a come si e visto per la definizione difbf. Dato un enunciato definito in M si dice che esso e vero o falso in Msecondo le seguenti regole:

• sia φ un enunciato definito in M del tipo (R(c1, . . . , cn)) (cioe co-struito a partire da una formula atomica); allora φ e detto vero se ilvettore costituito dalle immagini di (s1, . . . , sn) tramite la mappa diinterpretazione, appartiene al sottoinsieme di A×· · ·×A definito dallarelazione immagine di R tramite I. Nel caso contrario (che il vettorenon vi appartenga), φ e detto falso in M ;

• date φ e ψ enunciati definiti in M , allora risultano altrettanto definitiin M gli enunciati (¬φ), (φ ∧ ψ), (φ ∨ ψ), (φ ⇒ ψ) e (φ ⇐⇒ ψ).Per ciascuno di essi il loro valore viene determinato a partire dalle bennote tabelle di verita dei connettivi logici;

• se φ e un enunciato definito in M del tipo (∀x ψ) o (∃x ψ) (con ψ fbf)in cui il simbolo di costante x non compare in ψ (e dunque ψ stessoe un enunciato), allora il valore di verita di φ e uguale a quello di ψ.Altrimenti se x vi compare, si supponga innanzitutto di estendere illinguaggio L aggiungendo un simbolo di costante per ogni individuodi A che non sia gia precedentemente interpretato da I e di ridefinirequindi la mappa di interpretazione in modo che per ogni individuoesista un simbolo che lo esprime. Fatto cio ∀x ψ risulta vera se tuttigli enunciati ottenuti da ψ sostituendo volta per volta ad x lo stessosimbolo di costante associato ad un individuo di A (al variare degliindividui in A) sono veri in M ; φ e falso altrimenti. Similmente ∃x ψrisulta false se tutti gli enunciati ottenuti da ψ sostituendo ad x lo

4non si faccia confusione con i simboli di relazione. A questo punto i due concettisono completamente separati, anche se come si vedra a breve ed e intuitivo, sarannostrettamente connessi dalla semantica.

5

stesso simbolo di costante associato ad un individuo di A sono veri inM e vera altrimenti.

Questo procedimento e noto in letteratura con il nome di semantica diTarski. Per dire in simboli che φ e vera in M si usa M |= φ, se e falsaM |= ¬φ.

Si prenda in considerazione ora un linguaggio L ed una struttura delprimo ordine M , con una mappa d’interpretazione I da L a M . Si pensiinoltre di avere una teoria T di L . M e un modello per T se ogni enunciatodi T risulta (definito e) vero in M ; in tal caso si dice che M soddisfa T eche T e soddisfabile. Per le proprieta del procedimento formale di deduzionedel linguaggio predicativo e grazie alle definizioni che abbiamo dato in pre-cedenza, si ottiene la confortante proprieta che ogni enunciato φ dedotto daT risulta vero in M ; cioe se T ` φ allora M |= φ. Questo implica da se cheuna teoria contraddittoria (non coerente) non puo avere un modello, poichela nostra semantica non permette ad un enunciato definito di essere contem-poraneamente vero e falso. In realta vale anche il viceversa5, nel senso cheogni teoria coerente e soddisfabile. Possiamo dunque dire che:

Teorema. Una teoria T di un linguaggio L e coerente se e solo se esoddisfabile.

3 Un esempio importante

Dovrebbe ora risultare chiara la differenza tra i concetti di deducibilita everita in un modello. Si supponga di voler studiare matematicamente l’o-getto M , struttura del primo ordine e di sviluppare quindi un linguaggio Le una teoria T , ovviamente soddisfatta da M . Un enunciato φ di L puoessere considerato “vero” in due modi (immaginando che sia definito in M):da una parte se e deducibile per T , e dall’altra se lo e in M tramite l’inter-pretazione I. Come si e detto se e deducibile risulta automaticamente veroin M , ma puo succedere che il contrario non accada; cioe un enunciato veroin M tramite la mappa d’interpretazione e le regole di semantica, puo nonessere deducibile a partire da T e dunque non lo si puo pensare strettamentecollegato alla teoria. L’importanza della teoria dei modelli sta proprio neldiscriminare cio che e vero in una teoria matematica in quanto frutto dideduzione da cio che lo e invece solo in un particolare modello, anche se sie sviluppato linguaggio e teoria a partire da esso.

Per rendere piu chiara questa distinzione si vuole presentare un sempliceesempio celebre in letteratura: quello delle geometrie non euclidee. Si trattoinfatti dell’evento storicamente scatenane che costrinse i matematici a porsiil problema che porto alla nasciata della teoria dei modelli. Di fatto sitratta di un esempio in cui M |= φ ma T 0 φ. Si noti che affinche cio sia

5Si veda [Chang-Keisler(1980)] per la dimostrazione

6

possibile si deve avere che φ risulti indipendente dagli assiomi di T (e quindiuna simile situazione non puo verificarsi per una teoria completa, dove tuttigli enunciati sono decidibili). Per comprenderlo a fondo e necessario perotornare un po’ indietro nella storia. . .

Il matematico e filosofo greco Euclide (300 a.c. circa), scrisse il celebretrattato di geometria “Elementi”. In tale libro Euclide, dando alcune defi-nizioni di base, dimostrava un certo numero di risultati di geometria (cheoggi noi sappiamo essere) piana, a partire da alcune “verita evidenti”, diviseda lui tra assiomi e postulati. Durante i secoli successivi, esso venne consi-derato un testo fondamentale per qualsiasi studioso di scienze e venne lettoed analizzato da tanti matematici (e non). In particolare, vi furono grandidiscussioni attorno al quinto postulato, perche sembrava il meno intuitivo6.Esso dice:

Elementi, Postulato V: Se una retta, venendo a cadere su altre due,forma con esse dalla stessa parte due angoli interni la cui somma e minoredi un angolo retto, allora le due rette si incontrano da quella parte in cuistanno i due angoli precedenti.

Per molti anni si penso che, poiche era vero nel piano e molto piu com-plicato degli altri, dovesse essere possibile dedurlo dai primi quattro. Cosımolti furono gli sforzi in tal senso per cercre di dimostrarlo. Bisogno aspet-tare fino al XIX secolo perche Gauss e Bolyai mostrassero invece la suaindipendenza dagli altri assiomi. A partire da cio si cominciarono a cercareteorie per cui valesse la negazione del quinto postulato. La ricerca non fufacile, visto che all’epoca, forse complice anche la visione Kantiana, si con-siderava la geometria di Euclide come l’unica “vera” geometria e che nonavesse senso cercarne un’altra a partire dalla negazione di alcuni assiomi.Fu Lobacevskij intorno al 1930 a trovare il primo esempio di geometria cheverificava tutti gli assiomi di Euclide tranne il quinto definendo che per taleragione venne detta non euclidea. Si tratta della geometria iperbolica7. Po-co piu tardi (1854), Riemann costruı la geometri ellittica, un altro esempiodi geometria non euclidea dove le “rette” non sono infinite. Infine nel 1872Klein dimostro la coerenza dei due precedenti sistemi, mettendo cosı fineall’idea della geometria euclidea come unica possibile. Si espongono ora piuin dettaglio i postulati delle geometrie non euclidee. Si noti innanzitutto cheil quinto postulato puo essere riscritto equivalentemente cosı:

Euclide: Data una retta ed un punto che non vi appartenga, esiste unaed una sola altra retta che passa per tale punto e non s’interseca mai conquella data.

6forse anche allo stesso Euclide, visto che si sforzo di usarlo il meno possibile; si veda[Giustini(1974)].

7la denominazione iperbolica e posteriore di Klein. Lobacevskij la chiamo“immaginaria”.

7

Lobacevskij definı la geometria iperbolica assumendo al suo posto laseguente negazione:

Lobacevskij: Data una retta ed un punto che non vi appartenga, esi-stono infinite rette che passano per tale punto e non intersecano mai quelladata.

Mentre Riemann costruı la geometri ellittica a partire da:Riemann: Data una retta ed un punto che non vi appartenga, non esiste

alcuna altra retta che passa per tale punto e non interseca mai quella data.Un caso particolare facilmente intuibile di geometria non euclidea e quello

della geometria sferica, caso particolare di quella ellittica. Si pensi ai puntisulla superficie di una sfera e si sostituisca al significato di “retta” quellodi “meridiano”; da intendersi qui come circonferenza massima, ottenutaimmaginando di tagliare la sfera con un piano passante per il centro8. Presoinfatti un qualsiasi meridiano si ha che ogni altro meridiano (ed in particolaretutti quelli passanti per un qualsiasi punto) interseca il primo in due punti.Per avere almeno un’idea intuitiva del perche, si immagini di ruotare la sferain modo che il primo meridiano risulti “verticale” come si e abituati a vederlisu di un mappamondo. Fatto cio, e ancora possibile ruotare arbitrariamentela sfera sia in latitudine che in longitudine lasciando che il primo meridianosia ancora verticale. Si puo quindi far in modo che qualsiasi altro meridianopassante per un punto, risulti verticale contemporaneamente al primo; i duemeridiani si toccano ovviamente ai poli.

I tre esempi citati di geometria sono tre modelli della teoria ottenutadagli assiomi de gli “Elementi”, tolto il quinto postulato. Per esso, poicheindipendente dagli altri, esistono modelli in cui e verificato ed altri in cuinon lo e, dato che la teoria che comprende lui o la sua negazione e ancoracoerente. Come sie detto, la comprensione di questa interpretazione harichiesto un certo numero di secoli per essere raggiunta, poiche necessito diun grande salto di astrazione.

4 Cenni sull’ordine superiore

Per tutta la trattazione si e sempre parlato di “primo ordine”, denomina-zione che lascia forti sospetti del fatto che debba esserci qualcosa che vi stasopra. La teoria qui presentata e detta del primo ordine per il limite chepresenta su quantificatori e relazoni: esso possono riferirsi soltanto a singoliindividui di A. Non e possibile esprimere proprieta su insiemi di indivi-dui, ad esempio per definire gli “aperti” di A o descrivere corrispondenzetra elementi ed insiemi, come sarebbe necessario per definire la relazione diappartenenza insiemistica ∈. Di fatto, la teoria qui mostrata permette di

8Non ci si lasci confondere dal fatto che in i meridiani tradizionali della cartografiaterrestre sono solo alcuni e non tutti (l’equatore e un meridiano).

8

descrivere poca della matematica che oggi e oggetto di ricerca. La naturaleestensione dei concetti di linguaggio e struttura visti qui che invece permettequesta maggiore verseatilita e detta di linguaggi e strutture di ordine supe-riore. La via per andare in tal senso e quella di considerare il linguaggiocostituito da soli simboli di costante (oltre che alle variabili) e introdurrespeciali simboli che leghino costanti e variabili al loro tipo, cioe permettanodi definire se si sta parlando di individui, insiemi di individui, relazioni traindividui, individui e insiemi9. . .

La liberta concessa da tale estensione e grande, nel senso che permettedi descrivere ogni branca della matematica. Tale liberta pero e pagata ad uncaro prezzo, non soltanto per l’appesantimento delle notazioni e la perdita diintuitivita, ma soprattuto a causa del celeberrimo teorema di incompletezzadi Godel, il quale garantisce che in una teoria di un linguaggio di ordinesuperiore abbastanza ampia da contenere l’assiomaizzazione dei numeri na-turali secondo Peano (e l’utilita di usare i naturali e grande in matematica),esiste sempre almeno un enunciato non decidibile. Esso ci dice che mol-te teorie matematiche sono quindi non complete, limitando di fatto la loropotenza deduttiva.

9in [Robinson(1970)] si puo trovare una definizione rigorosa di ordine superiore, oltreche ad un interessantissima applicazione della teoria dei modelli, dette estensioni nonstandard.

9

Riferimenti bibliografici

[Chang-Keisler(1980)] C. C. Chang, H. J. Keisler Teoria dei modelliBoringhieri, 1980.

[Giustini(1974)] P. A. Giustini Da Euclide ad Hilbert Bulzoni, 1974.

[Lemmon(1975)] E. J. Lemmon Elementi di logica Laterza, 1975.

[Robinson(1970)] A. Robinson Non standard analysis North Holland, 1970.

[Shenker(1991)] a cura di S. G. Shenker Il teorema di Godel Franco Muzzioe c., 1991.

10