Teoria dei modelli: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
template vari |
creata. anche se è da ritoccare |
||
Riga 4:
La '''teoria dei modelli''' è una branca della matematica, e più precisamente della [[logica matematica|logica]], che affronta lo studio generalizzato del concetto di ''[[struttura (matematica)|struttura]]'', in riferimento alle relazioni tra varie strutture ed in particolare alla soddisfacibilità di date [[teoria#Matematica|teorie]].
== Linguaggio ==
In teoria dei modelli, per ''linguaggio'' (o talvolta ''segnatura'') si intende l'insieme di simboli tramite i quali una teoria è definita, o che una struttura interpreta. Teorie e linguaggi aventi linguaggio <math>\tau</math> si dicono spesso rispettivamente <math>\tau</math>-teorie e <math>\tau</math>-linguaggi.
Tipicamente (nel caso di teorie e modelli [[Linguaggio_del_primo_ordine|del primo ordine]]), un linguaggio è costituito da:
* simboli di relazione
* (eventualmente) simboli di funzione
* costanti (che possono essere viste come funzioni [[arietà|0-arie]]).
Ad esempio, la teoria dei [[gruppo (matematica)|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 <math>e</math> o semplicemente 1, il cui ovvio significato è quello di unità).
Il linguaggio della teoria dei [[grafo|grafi]] [[grafo#Grafi orientati e grafi semplici|non orientati]] comprende sempre un solo simbolo (solitamente rappresentato come '''E'''), che però in questo caso è di ''relazione'' binaria (<math>E(x,y)</math> 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 una almeno un simbolo di relazione binaria si può considerare un caso particolare della teoria dei grafi.
== Modelli e soddisfacibilità ==
Sia dato un linguaggio <math>\tau=\{R_1,R_2 \dots, f_1, f_2 \dots, c_1, c_2 \dots\}</math> ed una teoria <math>T</math> nel linguaggio ''τ'' (ovvero un insieme con fissate interpretazioni dei simboli in ''τ''); si dice che struttura <math>(A, {R_1}^A,{R_2}^A \dots, {f_1}^A, {f_2}^A \dots, {c_1}^A, {c_2}^A \dots)</math> che interpreta<ref>"A interpreta il linguaggio ''τ'' significa semplicemente che ad ogni simbolo di relazione/funzione <math>\sigma</math> corrisponde una relazione/funzione della stessa arietà in <math>A</math>; si noti che l'utilizzo di <math>A</math> sia per indicare il dominio della struttura che la struttura stessa è improprio, ma semplifica la notazione.</ref> il linguaggio ''τ'' ''soddisfa'' <math>T</math> (o che la ''verifica'', o equivalentemente che ne è un ''modello'') se ogni funzione <math>\varphi</math> di <math>T</math> è vera in <math>A</math> dopo avere sostituito ad ogni simbolo la sua interpretazione.
Ovviamente, se è vera ogni formula di <math>T</math>, saranno vere anche le formule che è possibile derivarne.
== Modelli finiti e classi elementari ==
Dato un linguaggio <math>\tau</math> ed una <math>\tau</math>-teoria <math>T</math>, si indica con <math>Mod(T)</math> la classe delle strutture che verificano <math>T</math> e con <math>Mod_{fin}(T)</math> il sottoinsieme di quelle finite (formalmente: ''aventi dominio finito'').
Data una qualsiasi classe <math>K</math> di <math>\tau</math>-strutture finite chiusa per omomorfismo, esiste una teoria <math>T</math> tale che <math>K=Mod_{fin}(T)</math>. Questo si evince facilmente dal fatto che per ogni struttura finita <math>A</math> è possibile trovare una formula <math>\phi_A</math> che descrive univocamente <math>A</math> (tale cioé che per ogni struttura <math>B</math> si ha <math>B \vDash \phi_A \leftrightarrow B \cong A</math>), e la teoria
:<math>T\stackrel{def}{=}\{\phi_A | A \in K\}</math>
verifica ovviamente <math>K=Mod_{fin}(T)</math>.
Se una tale <math>T</math> è finita, <math>K</math> si dice elementare. Una classe elementare può essere individuata da una singola formula:
:<math>\phi_T = \bigvee_{\psi \in T} \psi</math>.
Viceversa, una classe descrivibile con una sola formula è evidentemente elementare.
{{portale|matematica}}
| |||