Modello (logica matematica)

Template:F Un modello di una teoria formale, in logica matematica, è una struttura in cui vengono interpretati gli enunciati della teoria. Sebbene la seguente definizione faccia riferimento alla teoria dei modelli, gli esempi e le definizioni successive fanno riferimento a teoria e logica del primo ordine.

Definizione

Per una data teoria $𝒯$ in teoria dei modelli, una struttura $ℳ=(M,\sigma ,I)$ è definita come modello se

1. il linguaggio usato da $ℳ$ è lo stesso usato nella teoria $𝒯$,
2. ogni proposizione in $𝒯$ è soddisfatta da $ℳ$,

dove

1. $ℳ$ è un dominio (di discorso o di interpretazione),
2. $\sigma$ è una firma (signature),
3. $I$ è una funzione di interpretazione.

Dominio

Il dominio $𝒟$ di una struttura $ℱ$ è definito come un insieme arbitrario; è anche detto dominio di discorso in quanto contiene gli elementi dell'ambiente sul quale si vuole effettuare una descrizione o un ragionamento.

Si noti che, se il dominio è usato in una struttura per la logica del primo ordine, allora non può essere vuoto.

Signature

La signature $\sigma =(S,\mathrm{a}\mathrm{r})$ di una struttura $ℱ$ è un definita formalmente come una coppia i cui elementi sono

1. $S$, l'insieme di simboli di costanti, funzioni o relazioni, ciascuno con un'arietà;
2. una funzione $\mathrm{a}\mathrm{r}:S\to \mathbb{N}$, detta di arietà, che associa ad ogni simbolo in $S$ il numero di argomenti che il simbolo accetta.

Per definizione simboli costanti $c$ sono tali che $\mathrm{a}\mathrm{r}(c)=0$.

Funzione di interpretazione

Una funzione di interpretazione $I$ di una struttura $ℱ$ è una funzione che assegna funzioni e relazioni ai simboli definiti nella signature ed è tale che:

1. $I(c_i)\in 𝒟$, con $c_i$ simbolo costante nel dominio di interpretazione;
2. $I(f_i):S\to ({𝒟}^n\to 𝒟)$, con $f_i$ simbolo funzionale con arietà $n$ e nel dominio di interpretazione;
3. $I(R_i)\subseteq {𝒟}^n$, con $R_i$ simbolo relazionale con arietà $n$ e nel dominio di interpretazione.

Esempio

Un esempio di dominio di discorso, può essere un insieme di persone che siamo interessati a descrivere, ad esempio $𝒟=\{\mathrm{T}\mathrm{o}\mathrm{m},\mathrm{B}\mathrm{i}\mathrm{l}\mathrm{l},\mathrm{J}\mathrm{o}\mathrm{h}\mathrm{n},\mathrm{K}\mathrm{a}\mathrm{t}\mathrm{e},\mathrm{P}\mathrm{e}\mathrm{t}\mathrm{e}\mathrm{r},\mathrm{S}\mathrm{u}\mathrm{e},\mathrm{T}\mathrm{i}\mathrm{m}\}$.

Un esempio di signature $\sigma$ può essere una coppia $(S,\mathrm{a}\mathrm{r})$, dove

• $S=\{\mathrm{P}\mathrm{a}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{D}\mathrm{i},\mathrm{A}\mathrm{m}\mathrm{i}\mathrm{c}\mathrm{i},a,b,c,d,f,g\}$, con
  • $\mathrm{P}\mathrm{a}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{D}\mathrm{i}$ simbolo funzionale,
  • $\mathrm{A}\mathrm{m}\mathrm{i}\mathrm{c}\mathrm{i}$ simbolo relazionale,
  • e $a,b,c,d,f,g$ simboli costanti;
• $\mathrm{a}\mathrm{r}$ funzione di arietà tale che:
  • $\mathrm{a}\mathrm{r}(\mathrm{P}\mathrm{a}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{D}\mathrm{i})=1,$
  • $\mathrm{a}\mathrm{r}(\mathrm{A}\mathrm{m}\mathrm{i}\mathrm{c}\mathrm{i})=2,$
  • $\mathrm{a}\mathrm{r}(x)=0,\mathrm{\forall }x\in \{a,b,c,d,e,f,g\}.$

Facendo riferimento agli esempi di dominio e signature visti sopra, una possibile funzione di interpretazione può essere $I$ tale che:

• $I(a)=\mathrm{T}\mathrm{o}\mathrm{m},I(b)=\mathrm{B}\mathrm{i}\mathrm{l}\mathrm{l},I(c)=\mathrm{J}\mathrm{o}\mathrm{h}\mathrm{n},I(d)=\mathrm{K}\mathrm{a}\mathrm{t}\mathrm{e},I(e)=\mathrm{P}\mathrm{e}\mathrm{t}\mathrm{e}\mathrm{r},I(f)=\mathrm{S}\mathrm{u}\mathrm{e},I(g)=\mathrm{T}\mathrm{i}\mathrm{m};$
• $I(\mathrm{P}\mathrm{a}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{D}\mathrm{i})=h$ tale che $h(b)=a,h(d)=c,h(f)=e;$
• $I(\mathrm{A}\mathrm{m}\mathrm{i}\mathrm{c}\mathrm{i})=\{(f,b),(d,g)\}.$

Soddifacibilità per logiche del primo ordine

Un modello per una formula ben formata di un linguaggio del primo ordine è un modello per il linguaggio in cui l'interpretazione della formula risulti vera. Una formula è detta

• valida se è vera per tutti i modelli;
• soddisfacibile se esiste almeno un modello rispetto al quale è vera;
• insoddisfacibile se non esiste nessun modello in cui è vera.

Per esempio, una formula valida può essere $\mathrm{\forall }x.(p(x)\to p(x))$, una soddisfacibile può essere $\mathrm{\exists }x.(g(x)\to p(x))$, una insoddisfacibile può essere $\mathrm{\forall }x.(p(x)\to ̸p(x))$.

Modelli di teorie assiomatiche

Un modello per una teoria del primo ordine è un modello per il suo linguaggio per cui siano vere tutte le formule che sono assiomi della teoria, e di conseguenza saranno verificate nel modello tutte le formule corrispondenti ai teoremi della teoria.

Voci correlate

• Teoria dei modelli
• Linguaggio del primo ordine
• Teoria del primo ordine
• Correttezza (logica matematica)
• Completezza (logica matematica)
• Consistenza (logica matematica)

Collegamenti esterni

• Template:Collegamenti esterni