Teoria dei modelli: differenze tra le versioni
m Bot: parentesi quadre automatiche nel template {{nota disambigua}} |
|||
Riga 1: | Riga 1: | ||
{{nota disambigua|altri significati del termine "modello"| |
{{nota disambigua|altri significati del termine "modello"|modello}} |
||
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]]. |
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]]. |
Versione delle 19:04, 16 set 2015
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[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 si dicono spesso rispettivamente -teorie e -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 , oppure .
Il linguaggio della teoria dei grafi orientati comprende sempre un solo simbolo (qui rappresentato come , che in questo caso è di relazione binaria ( significherà "c'è un arco da a "). La teoria dei grafi non 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 sia una relazione irriflessiva e simmetrica.
Modelli e soddisfacibilità
Sia dato un linguaggio ed una teoria nel linguaggio τ (ovvero un insieme con fissate interpretazioni dei simboli in τ); si dice che la struttura che interpreta[2] il linguaggio τ soddisfa (o che la verifica, o equivalentemente che ne è un modello) se ogni funzione di è vera in dopo avere sostituito ad ogni simbolo la sua interpretazione.
Ovviamente, se è vera ogni formula di , saranno vere anche le formule che è possibile derivarne.
Modelli finiti e classi elementari
Dato un linguaggio ed una -teoria , si indica con la classe delle strutture che verificano e con il sottoinsieme di quelle finite (formalmente: aventi dominio finito).
Data una qualsiasi classe di -strutture finite chiusa per omomorfismo, esiste una teoria tale che . Questo si evince facilmente dal fatto che per ogni struttura finita è possibile trovare una formula che descrive univocamente (tale cioè che per ogni struttura si ha ), e la teoria
verifica ovviamente .
Se una tale è finita, si dice elementare. Una classe elementare può essere individuata da una singola formula:
- .
Viceversa, una classe descrivibile con una sola formula è evidentemente elementare.
Bibliografia (in italiano)
- A. Marcja, C. Toffalori. Introduzione alla Teoria dei Modelli. Pitagora Editrice, Bologna, 1998
- A. Berarducci. Teoria dei modelli.
- D. Zambella. Dispense del corso di logica e teoria dei modelli.
Note
- ^ Neil Immerman, Descriptive complexity, Springer-Verlag~New York, 1999.
- ^ "A interpreta il linguaggio τ" significa semplicemente che ad ogni simbolo di relazione/funzione corrisponde una relazione/funzione della stessa arietà in ; si noti che l'utilizzo di sia per indicare il dominio della struttura che la struttura stessa è a rigore improprio, ma semplifica la notazione.