Teoria dei modelli

Da Wikipedia, l'enciclopedia libera.
bussola Disambiguazione – Se stai cercando altri significati del termine "modello", vedi modello.

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[modifica | modifica sorgente]

In teoria dei modelli, per linguaggio (o talvolta vocabolario[1], 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à[modifica | modifica sorgente]

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 la 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[2] 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[modifica | modifica sorgente]

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.

Note[modifica | modifica sorgente]

  1. ^ Neil Immerman, Descriptive complexity, Springer-Verlag~New York, 1999.
  2. ^ "A interpreta il linguaggio τ" significa semplicemente che ad ogni simbolo di relazione/funzione \sigma corrisponde una relazione/funzione della stessa arietà in A; si noti che l'utilizzo di A sia per indicare il dominio della struttura che la struttura stessa è a rigore improprio, ma semplifica la notazione.

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica