Teoria dei modelli

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

Linguaggio modifica

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, un simbolo di funzione unaria, ed una costante solitamente $+,-,0$ , oppure $\cdot ,{}^{-1},1$ .

Il linguaggio della teoria dei grafi orientati comprende sempre un solo simbolo (qui rappresentato come $E$ , che in questo caso è di relazione binaria ( $E(x,y)$ significherà "c'è un arco da $x$ a $y$ "). La teoria dei grafi orientati 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 orientati. La teoria dei grafi non orientati richiede che $E$ sia una relazione irriflessiva e simmetrica.

Modelli e soddisfacibilità modifica

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

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

^ Neil Immerman, Descriptive complexity, New York, Springer-Verlag, 1999, ISBN 9780387986005.
^ "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.

Bibliografia modifica

Chen Chung Chang, H. Jerome Keisler. Teoria dei modelli. Boringhieri, 1980
Wilfrid Hodges "Model Theory" Cambridge University Press 1993 ISBN 0521304423
Annalisa Marcja, Carlo Toffalori. Introduzione alla Teoria dei Modelli. Pitagora, Bologna, 1998
Alessandro Berarducci. Teoria dei modelli.

Voci correlate modifica

Teoria dei modelli astratti

Altri progetti modifica

Wikibooks contiene testi o manuali sulla teoria dei modelli
Wikimedia Commons contiene immagini o altri file sulla teoria dei modelli

Collegamenti esterni modifica

Giulio Supino, Alberto Pasquinelli e Aldo Marruccelli, MODELLI, Teoria dei, in Enciclopedia Italiana, IV Appendice, Istituto dell'Enciclopedia Italiana, 1979.
Giulio SUPINO, Gino SACERDOTE, Guido OBERTI e Vittorio PEGORARO, MODELLI, teoria dei, in Enciclopedia Italiana, III Appendice, Istituto dell'Enciclopedia Italiana, 1961.
Silvio Bozzi, Modelli, Teoria dei, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.
modelli, teoria dei, in Dizionario di filosofia, Istituto dell'Enciclopedia Italiana, 2009.
(EN) model theory, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
(EN) Wilfrid Hodges, Model Theory, su Stanford Encyclopedia of Philosophy.
(EN) Opere riguardanti Model theory, su Open Library, Internet Archive.
(EN) Eric W. Weisstein, Model Theory, su MathWorld, Wolfram Research.
(EN) Model theory, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

Controllo di autorità	Thesaurus BNCF 40654 · LCCN (EN) sh85086421 · GND (DE) 4114617-7 · BNF (FR) cb119323610 (data) · J9U (EN, HE) 987007541020605171 · NDL (EN, JA) 00567757

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

[1] Neil Immerman, Descriptive complexity, New York, Springer-Verlag, 1999, ISBN 9780387986005.

[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.

[1]

[2]