Teoria dei modelli

La teoria dei modelli è una branca della matematica, e più precisamente della logica, che affronta lo studio generalizzato del concetto di struttura, in riferimento alle relazioni tra varie strutture ed in particolare alla soddisfacibilità di date teorie.

Linguaggio

In teoria dei modelli, per linguaggio (o talvolta vocabolario, o segnatura) si intende l'insieme di simboli tramite i quali una teoria è definita, o che una struttura interpreta. Teorie e linguaggi aventi linguaggio $\tau$ si dicono spesso rispettivamente $\tau$-teorie e $\tau$-linguaggi.

Tipicamente (nel caso di teorie e modelli del primo ordine), un linguaggio è costituito da:

• simboli di relazione
• (eventualmente) simboli di funzione
• costanti (che possono essere viste come funzioni 0-arie).

Ad esempio, la teoria dei gruppi si esprime in un linguaggio contenente un simbolo di funzione binaria (solitamente + o *) ed eventualmente (ma non è necessario, dato che può essere introdotto tramite gli assiomi della teoria) un simbolo di costante (solitamente e o semplicemente 1, il cui ovvio significato è quello di unità).

Il linguaggio della teoria dei grafi non orientati comprende sempre un solo simbolo (solitamente rappresentato come E), che però in questo caso è di relazione binaria ($E(x,y)$ significherà "c'è un arco tra x e y"). Tra l'altro, la teoria dei grafi non prevede alcun assioma ed è caratterizzata semplicemente dal suo linguaggio, per cui qualsiasi teoria avente nel suo linguaggio almeno un simbolo di relazione binaria si può considerare un caso particolare della teoria dei grafi.

Modelli e soddisfacibilità

Sia dato un linguaggio $\tau =\{R_{1},R_{2}\dots ,f_{1},f_{2}\dots ,c_{1},c_{2}\dots \}$ ed una teoria $T$ nel linguaggio τ (ovvero un insieme con fissate interpretazioni dei simboli in τ); si dice che struttura $(A,{R_{1}}^{A},{R_{2}}^{A}\dots ,{f_{1}}^{A},{f_{2}}^{A}\dots ,{c_{1}}^{A},{c_{2}}^{A}\dots )$ che interpreta il linguaggio τ soddisfa $T$ (o che la verifica, o equivalentemente che ne è un modello) se ogni funzione $\varphi$ di $T$ è vera in $A$ dopo avere sostituito ad ogni simbolo la sua interpretazione.

Ovviamente, se è vera ogni formula di $T$, saranno vere anche le formule che è possibile derivarne.

Modelli finiti e classi elementari

Dato un linguaggio $\tau$ ed una $\tau$-teoria $T$, si indica con $Mod(T)$ la classe delle strutture che verificano $T$ e con $Mod_{fin}(T)$ il sottoinsieme di quelle finite (formalmente: aventi dominio finito).

Data una qualsiasi classe $K$ di $\tau$-strutture finite chiusa per omomorfismo, esiste una teoria $T$ tale che $K=Mod_{fin}(T)$. Questo si evince facilmente dal fatto che per ogni struttura finita $A$ è possibile trovare una formula $\phi _{A}$ che descrive univocamente $A$ (tale cioé che per ogni struttura $B$ si ha $B\vDash \phi _{A}\leftrightarrow B\cong A$), e la teoria

$T{\stackrel {def}{=}}\{\phi _{A}|A\in K\}$

verifica ovviamente $K=Mod_{fin}(T)$.

Se una tale $T$ è finita, $K$ si dice elementare. Una classe elementare può essere individuata da una singola formula:

$\phi _{T}=\bigwedge _{\psi \in T}\psi$.

Viceversa, una classe descrivibile con una sola formula è evidentemente elementare.