modelli, teoria dei

modelli, teoria dei

Parte della logica matematica che studia le relazioni tra insiemi di espressioni di un linguaggio formale e insiemi di strutture in cui quelle espressioni sono valide.

Cenni storici

Sebbene l’espressione teoria dei m. sia stata usata per la prima volta da Tarski all’inizio degli anni Cinquanta, molti importanti risultati già ottenuti prima nell’ambito della semantica logica sono catalogabili nella teoria dei modelli. Il teorema di Löwenheim-Skolem, dimostrato in forma definitiva nel 1920, può essere considerato il primo risultato relativo alla teoria dei modelli. A questa possono riferirsi pure il teorema di completezza per la logica del primo ordine di Gödel (1930), nonché i suoi teoremi di incompletezza per ogni teoria formale sufficientemente espressiva da contenere l’aritmetica di Peano (1931). Un altro importante contributo a questa teoria fu nel 1933 la precisa formulazione di Tarski del concetto d’interpretazione di un insieme di espressioni formalizzate in una struttura. Notevoli conseguenze per i successivi sviluppi provengono anche dalla dimostrazione, data da Skolem nel 1934, della non caratterizzabilità dei numeri naturali nell’ambito della logica elementare mediante un insieme finito o numerabile di assiomi, cioè dell’esistenza di estensioni proprie dell’insieme dei numeri naturali, le quali godono delle stesse proprietà numeriche esprimibili mediante la logica elementare con identità e con le funzioni di addizione e moltiplicazione, estensioni che saranno in seguito chiamate m. non standard o patologici dell’aritmetica. Anche dalle ricerche condotte in algebra provengono sia suggerimenti per la teoria dei m., sia possibilità di applicazione dei risultati ottenuti in essa. Così, per es., il principio di finitezza enunciato da A.I. Mal′cev è stato poco dopo da lui stesso applicato in algebra. La dissertazione di A. Robinson On the metamathematics of algebra del 1949 affronta in modo esplicito lo studio dell’analogia tra le teorie algebriche (specialmente quella dei campi) e la teoria generale delle teorie elementari. Infine, a partire dal 1950, specialmente a Berkeley per opera di Tarski e della sua scuola, la teoria dei m. riceve la definitiva sistemazione su cui si fondano le ricerche relative alla teoria assiomatica degli insiemi (Gödel, Tarski, P.J. Cohen, Dana Scott), alle logiche con espressioni di lunghezza infinita (Tarski, Carol R. Karp), ai fondamenti del calcolo delle probabilità (H. Gaifman, Scott, P. Krauss, J.E. Fenstad), e così via.

Semantica delle teorie elementari

Le espressioni di una teoria elementare T acquistano un significato quando ai simboli del suo linguaggio L si dà un’interpretazione in una struttura costituita da un dominio di individui e, per ciascun simbolo non logico di L, da opportuni enti relativi a quel dominio. Per es., se T è il sistema assiomatico di Peano, T potrà acquistare un significato se viene interpretato nella struttura costituita dal dominio dei numeri naturali (per le variabili individuali di T), dalla costante «zero» (per il simbolo non logico 0), dalla funzione «successore» (per il simbolo non logico s), dalle operazioni di addizione e moltiplicazione ordinarie (rispettivamente per i simboli non logici + e ·); il simbolo = sarà considerato come simbolo logico da interpretare sempre sul predicato diadico «è uguale a». Definiamo i concetti di interpretazione e di struttura per il linguaggio L di una teoria elementare T (per questo ➔ anche logica matematica). Una interpretazione I per il linguaggio L di una teoria elementare T consiste in una struttura (o universo) U(α) e in una determinata applicazione dei predicati e delle funzioni di L. La struttura U(α) è formata: (1) da un insieme non vuoto α detto dominio degli individui o anche universo; (2) per ogni simbolo di predicato n-adico P ∈ L, da una relazione n-aria P_α su α (cioè, un sottoinsieme della potenza cartesiana α_n); per il simbolo del predicato diadico «=», la struttura conterrà la relazione binaria «è uguale a»; (3) per ogni simbolo di funzione a n argomenti f ∈ L, da una operazione (o funzione) f_α: α_n→α; in partic., per ogni costante individuale (funzione a zero argomenti) c ∈ L, c_α risulta essere un individuo del dominio α. L’applicazione individuata dalla I associa P_α a P e f_α a f (in partic. c_α a c), per ogni P, f, c ∈ L. Per qualsiasi interpretazione i connettivi enunciativi e i quantificatori sono applicati sulle corrispondenti funzioni di verità e di quantificazione, mentre le variabili individuali libere potranno essere applicate in tutti i modi possibili sugli individui del dominio della struttura e quelle vincolate nei modi consentiti dall’interpretazione dei quantificatori. Una formula di L è detta vera in una interpretazione I del linguaggio se e soltanto se per ogni valore delle variabili individuali libere essa riceve valore vero sotto I. Fissata un’interpretazione I per il linguaggio L, ogni formula di L senza variabili individuali libere è vera o falsa; invece una formula contenente variabili libere (cioè non nell’ambito di un quantificatore), che rappresenta una relazione sul dominio degli individui, può risultare vera per alcuni valori del dominio e falsa per altri. Ossia, per una data interpretazione I, ogni formula chiusa risulta o vera o falsa, ogni formula aperta può non risultare né vera né falsa. Per es., la formula chiusa ∀x∃y (2x=y), se il dominio dell’interpretazione è l’insieme dei numeri naturali risulta vera; la formula aperta 2x=y per la stessa interpretazione non risulta né vera né falsa. Una formula di L dicesi logicamente valida (o valida) se e solo se è vera per qualunque interpretazione; dicesi soddisfacibile se e solo se esiste almeno un’interpretazione che la rende vera. Una formula di L dicesi contraddittoria se e solo se è falsa per ogni interpretazione. Si dice che una formula K è conseguenza logica (o conseguenza) di una formula H (o in generale di un insieme M di formule) se e solo se le interpretazioni che rendono vera H (tutte le formule di M) rendono vera anche K. Due formule H e K si dicono logicamente equivalenti se e solo se ciascuna è conseguenza dell’altra. Un’interpretazione per un linguaggio L dicesi un m. per un insieme M di formule di L (in partic. per una teoria T o per una formula H) se e solo se tutte le formule di M (di T o la formula H) sono vere per quella interpretazione. Talvolta si usa chiamare m. di una teoria T il dominio α dell’interpretazione se questa è m. per T; analogamente si parla di validità (soddisfacibilità) in α di una teoria T se ogni (qualche) interpretazione del suo linguaggio relativa al dominio α è m. di T. Una formula si dice valida in una teoria T se è conseguenza degli assiomi non logici di T o, equivalentemente, se è vera in ogni m. di T. Due strutture U(α) e U(β) si dicono elementarmente equivalenti per un certo linguaggio L se e solo se ogni formula esprimibile in L è vera in U(α) esattamente quando è vera in U(β); ciò implica che le due strutture sono m. delle stesse teorie. Consideriamo, per es., la teoria G, i cui assiomi non logici sono:

[G 1] x + (y + z) = (x + y) + z

[G 2] x + 0 = x

[G 3] ∃ y (x + y) = 0.

Il linguaggio L di G ha i simboli non logici + e 0. Interpretiamo L sulla struttura costituita dall’insieme Z dei numeri interi relativi, dall’operazione di addizione ordinaria (per la funzione binaria +) e dalla costante zero (per il simbolo 0). I tre assiomi risultano veri per questa interpretazione del linguaggio; si dice perciò che Z è m. di G o che questa interpretazione è m. di G. La teoria G è quindi soddisfacibile (in Z). Analogamente risultano m. di G gli insiemi Q, R e C dei numeri razionali, reali e complessi muniti dell’ordinaria addizione. I m. di G costituiscono i gruppi.

Caratterizzazione e completezza

Un linguaggio del primo ordine L′ si dice un’estensione del linguaggio L se tutti i simboli non logici di L appartengono anche a L′. Una teoria T′ si dice un’estensione o soprateoria della teoria T (e T sottoteoria di T′) se il linguaggio di T′ è un’estensione di quello di T e tutti i teoremi di T sono teoremi di T′; ovviamente, perché sussista la seconda condizione basta che tutti gli assiomi non logici di T siano teoremi di T′. Un’estensione T′ di T dicesi semplice se T e T′ hanno lo stesso linguaggio. Due teorie sono equivalenti se ciascuna è un’estensione dell’altra, cioè se le due teorie hanno lo stesso linguaggio e gli stessi teoremi. Sia L′ un’estensione di L e sia U′(α) una struttura per L′; tralasciando alcune relazioni e funzioni di U′(α) si ottiene una struttura U(α) per L. Si dice allora che U′(α) è l’espansione di U(α) a L′ e che U(α) è la restrizione di U′(α) a L. Evidentemente U(α) e U′(α) hanno lo stesso dominio di individui. Il problema della caratterizzazione per una teoria elementare T consiste nel ricercare le condizioni necessarie e sufficienti affinché una formula di T sia un teorema di T. Una prima soluzione di questo problema viene espressa dal teorema di completezza semantica di Gödel: «una formula di una teoria elementare T è un teorema se e solo se è valida in T», o, equivalentemente, «una teoria T è consistente se e solo se ha un m.». Questo teorema stabilisce l’equivalenza tra la nozione sintattica di derivabilità e quella semantica di validità. Da esso si ottiene un altro notevole teorema: «due teorie formulate nello stesso linguaggio sono equivalenti se e solo se hanno gli stessi m.». Anche il concetto di completezza sintattica può essere riformulato nell’ambito della teoria dei modelli. Una teoria T si dice sintatticamente completa se e solo se, per ogni enunciato H formulabile nel suo linguaggio, o H o ¬H è derivabile in T. Sussiste il teorema: «una teoria T è sintatticamente completa se e solo se tutte le coppie di m. di T sono elementarmente equivalenti per il linguaggio di T». Applicando questo teorema si può facilmente dimostrare che la teoria G, prima presentata, non è sintatticamente completa. Infatti, siano U(α) e U(β) due gruppi, il primo abeliano e il secondo no. Essi sono entrambi m. di G ma non elementarmente equivalenti perché la formula x+y=y+x è vera nella prima struttura e non è vera nella seconda.

Compattezza e teoria dei modelli

Una teoria si dice finitamente assiomatizzabile se può avere un numero finito di assiomi non logici. Vale il teorema di compattezza: «una formula è valida in una teoria T se e solo se è valida in qualche sottoteoria finitamente assiomatizzabile di T» o, equivalentemente, «una formula è una conseguenza di un insieme M di enunciati se e solo se è conseguenza di un sottoinsieme finito di M». Corollario: «una teoria T ha un m. se e solo se tutte le sottoteorie finitamente assiomatizzabili di T hanno un m.». Facciamo delle applicazioni alla teoria C i cui m. sono esattamente i campi. I primi due assiomi non logici di C, [C1] e [C2], sono [G1] e [G2] della teoria G prima considerata, mentre l’assioma [G3] può, qui, essere così formulato:

[C3] x + (−1) ∙ x = 0.

Gli altri assiomi non logici di C sono:

[C4] x + y = y + x

[C5] (x ∙ y) ∙ z = x ∙(y ∙ z)

[C6] x ∙ 1 = x

[C7] x ≠ 0 ⇒ ∃ y (x ∙ y = 1)

[C8] x ∙ y = y ∙ x

[C9] x ∙ (y + z) = (x ∙ y) + (x ∙ z)

[C10] 0 = 1

Se, poi, agli assiomi di C aggiungiamo, per es., gli altri assiomi non logici

[¬A2] 1 + 1 ≠ 0

[¬A3] 1 + 1 + 1 ≠ 0

[¬A4] 1 + 1 + 1 + 1 ≠ 0

[A5] 1 + 1 + 1 + 1 + 1 ≠ 0

la nuova teoria C(5), soprateoria di C, è la teoria dei campi di caratteristica 5. Generalizzando, C(n) rappresenta la teoria di campi di caratteristica n. La teoria, C(0), dei campi di caratteristica zero si ottiene quindi aggiungendo a quelli di C un’infinità numerabile di assiomi non logici [¬An] (con n che assume tutti i valori dei numeri naturali >1). Ciò premesso, il teorema di compattezza applicato a C(0) conduce ad affermare che una formula valida in C(0) è valida anche in tutti i C(n) con n non minore di un certo n₀. Segue da ciò che la teoria C(0) non può essere fondata su un numero finito di assiomi, altrimenti l’enunciato di tutti gli assiomi di C(0) sarebbe valido anche in un certo C(n₀), il che è assurdo. In modo analogo si vede anche che non è possibile individuare una soprateoria di C che formalizzi la teoria elementare dei campi finiti.

Definibilità e teoria dei modelli

Sia S un insieme di simboli non logici del linguaggio di una teoria T. Un simbolo predicativo P∉S si dice definibile in termini di S in T se esiste una formula H i cui simboli non logici appartengano a S tale che in T sia derivabile l’equivalenza

Px … z ⇔ H.

Analogamente, un simbolo funzionale f∉S è definibile in termini di S in T se esiste una formula H i cui simboli non logici appartengano a S tale che sia derivabile in T l’equivalenza

y = f (x, …, z) ⇔ H.

Siano U(α) e U(β) le strutture relative a due interpretazioni per il linguaggio L di una teoria T, sia s un simbolo non logico di L non appartenente a S e φ una biiezione tra α e β. Si dice che φ è un s-isomorfismo di U(α) e U(β) se φ è un isomorfismo delle restrizioni di U(α) e U(β) al linguaggio L_s il cui unico simbolo non logico è s. Sussiste il teorema di definibilità di Beth: «sia S un insieme di simboli non logici del linguaggio L di una teoria T e sia t un simbolo non logico di L (predicativo o funzionale) non appartenente a S. Allora t è definibile in termini di S in T se e solo se per tutte le coppie di m. di T, U(α) e U(β), e per ogni biiezione φ di α in β che sia s-isomorfismo per tutti gli s ∉ S, φ è anche t-isomorfismo». Anche questo è, dunque, un esempio di proprietà sintattica che può essere espressa in termini di teoria dei modelli. In un lavoro del 1953 Beth aveva dimostrato questo teorema con il metodo da lui detto delle tavole semantiche, intermedio tra quello della teoria della dimostrazione e quello della teoria dei modelli. Nel 1956 Robinson ne ha data una dimostrazione in termini di sola teoria dei modelli.

Categoricità e teoria dei modelli

Sia ℵ_m un generico numero cardinale infinito. Un linguaggio L di una teoria elementare T dicesi ℵ_m-linguaggio se l’insieme dei simboli non logici di L ha cardinalità ≤ℵ_m; in tal caso T dicesi ℵ_m-teoria. Se m=0, si usa pure l’espressione linguaggio e, rispettivamente, teoria numerabile. Sussiste il teorema della cardinalità di Tarski: una ℵ_m-teoria che ha un m. infinito ne ha uno di cardinalità ℵ_m. Una teoria si dice categorica se tutte le coppie di suoi m. sono isomorfe. Esempi di teorie elementari categoriche hanno solo m. finiti; infatti se una teoria ha un m. infinito, per il teorema della cardinalità, essa ha m. di diversa cardinalità e perciò non isomorfi. Ciò suggerisce una definizione più accurata di categoricità. Una teoria T dicesi ℵ_m-categorica se tutte le coppie di m. di essa di cardinalità ℵ_m sono isomorfe. Per una teoria numerabile T sono allora possibili quattro casi: (1) T è ℵ_m-categorica per tutti gli m. Così avviene, per es., per la teoria che non ha simboli, né assiomi non logici. (2) T è ℵ_m-categorica per m≥1. Si dimostra che è tale la teoria elementare, CAC, dei campi algebricamente chiusi. CAC si ottiene da C aggiungendo un’infinità numerabile di assiomi che asseriscono, per ogni n≥1, che tutti i polinomi di grado n hanno uno zero nel campo:

[C'1] y ≠ 0 ⇒ ∃ x (y ∙ x + z = 0)

[C'2] y ≠ 0 ⇒ ∃ x (y ∙ x² + z ∙ x + w = 0)

(3) T non è ℵ_m-categorica per nessun m. Si dimostra che è tale la teoria elementare CRC dei campi realmente chiusi (cioè tali che ogni elemento positivo del campo ha una radice quadrata in esso e tutti i polinomi di grado dispari a coefficienti nel campo hanno in esso uno zero). CRC si ottiene aggiungendo a C gli assiomi

[C11] 0 < x ⇒ ∃ y (y² = x)

e tutti i [C′n] con n dispari; inoltre, per ottenere la teoria elementare dei campi ordinati:

[O1] ¬ (x < x)

[O2] x < y ⇒ (y < z ⇒ x < z)

[O3] x < y ⋁ x = y ⋁ y < x

[O4] x < y ⇒ x + z < z

[O5] (0 < x ⋀ 0 < y) ⇒ 0 < x ∙ y.

(4) T è ℵ_m-categoria solo per m = 0. Si dimostra che è tale la teoria D i cui assiomi non logici sono [O1], [O2], [O3] e, inoltre:

x < y ⇒ ∃ z (x < z ⋀ z < y)

∃ x (x y)

∃ x (y x).

Oltre i quattro casi elencati, in base a un teorema dimostrato da M.D. Morley nel 1963, non sono possibili altri casi, per una teoria numerabile T. La descritta definizione di categoricità trova frequenti applicazioni nella teoria dei m. grazie al teorema di Los-Vaught: «se T è una ℵ_m-teoria consistente con m. infiniti e ℵ_m-categorica, allora essa è completa».

Problema del prefisso

Le espressioni di una teoria elementare in forma normale prenessa (➔ anche logica matematica) possono essere classificate in base al tipo di prefisso. Sarà esistenziale un’espressione elementare in forma normale prenessa il cui prefisso contiene solo quantificatori esistenziali; sarà universale quella in cui il prefisso contiene solo quantificatori universali; sarà una ∀∃-formula quella nel cui prefisso nessun quantificatore universale è preceduto da un quantificatore esistenziale; ecc. Si pone il problema di sapere se queste diverse classi di formule possono essere caratterizzate mediante proprietà specifiche degli insiemi di universi che soddisfano quelle formule. S’intuisce facilmente che, se un enunciato esistenziale H è vero in un universo U(α), esso è vero anche in ogni estensione di U(α). Ciò vale, come è ovvio, anche per ogni enunciato K logicamente equivalente a H. Nel 1954 Tarski ha dimostrato che questa affermazione è invertibile, cioè: «se un enunciato K, vero in un universo U(α), è vero in qualunque estensione di U(α), allora K è logicamente equivalente a un enunciato esistenziale». Risultati analoghi sono stati ottenuti nel 1957 anche da J. Loś e R. Suszko riguardo alle ∀∃-formule.

Ultraprodotti

I concetti di ultrafiltro, ultraprodotto e ultrapotenza sono stati utilizzati per dimostrare il teorema di compattezza. Particolari proprietà di tali ultraprodotti hanno consentito di dimostrare alcuni teoremi relativi al calcolo dei predicati del primo ordine anche nei casi in cui quei teoremi non erano esprimibili nel linguaggio logico di primo ordine.