Modello (logica matematica)

In logica matematica, un modello di una teoria formale è un'interpretazione che rende vera tutti 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 ${\mathcal {T}}$ in teoria dei modelli, una struttura ${\mathcal {M}}=(M,\sigma ,I)$ è definita come modello se

il linguaggio usato da ${\mathcal {M}}$ è lo stesso usato nella teoria ${\mathcal {T}}$ ,
ogni proposizione in ${\mathcal {T}}$ è soddisfatta da ${\mathcal {M}}$ ,

dove

${\mathcal {M}}$ è un dominio (di discorso o di interpretazione),
$\sigma$ è una firma (signature),
$I$ è una funzione di interpretazione.

Dominio

Il dominio ${\mathcal {D}}$ di una struttura ${\mathcal {F}}$ è 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 {ar} )$ di una struttura ${\mathcal {F}}$ è un definita formalmente come una coppia i cui elementi sono

$S$ , l'insieme di simboli di costanti, funzioni o relazioni, ciascuno con un'arietà;
una funzione $\mathrm {ar} \colon 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 {ar} (c)=0$ .

Funzione di interpretazione

Una funzione di interpretazione $I$ di una struttura ${\mathcal {F}}$ è una funzione che assegna funzioni e relazioni ai simboli definiti nella signature ed è tale che:

$I(c_{i})\in {\mathcal {D}}$ , con $c_{i}$ simbolo costante nel dominio di interpretazione;
$I(f_{i})\colon S\rightarrow ({\mathcal {D}}^{n}\rightarrow {\mathcal {D}})$ , con $f_{i}$ simbolo funzionale con arietà $n$ e nel dominio di interpretazione;
$I(R_{i})\subseteq {\mathcal {D}}^{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 ${\mathcal {D}}=\{\mathrm {Tom} ,\mathrm {Bill} ,\mathrm {John} ,\mathrm {Kate} ,\mathrm {Peter} ,\mathrm {Sue} ,\mathrm {Tim} \}$ .

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

$S=\{\mathrm {PadreDi} ,\mathrm {Amici} ,a,b,c,d,f,g\}$ $S=\{\mathrm {PadreDi} ,\mathrm {Amici} ,a,b,c,d,f,g\}$ , con
- $\mathrm {PadreDi}$ simbolo funzionale,
- $\mathrm {Amici}$ simbolo relazionale,
- e $a,b,c,d,f,g$ simboli costanti;
$\mathrm {ar}$ $\mathrm {ar}$ funzione di arietà tale che:
- $\mathrm {ar} (\mathrm {PadreDi} )=1,$
- $\mathrm {ar} (\mathrm {Amici} )=2,$
- $\mathrm {ar} (x)=0,\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 {Tom} ,\quad I(b)=\mathrm {Bill} ,\quad I(c)=\mathrm {John} ,\quad I(d)=\mathrm {Kate} ,\quad I(e)=\mathrm {Peter} ,\quad I(f)=\mathrm {Sue} ,\quad I(g)=\mathrm {Tim$
$I(\mathrm {PadreDi} )=h\quad$ tale che $\quad h(b)=a,\quad h(d)=c,\quad h(f)=e;$
$I(\mathrm {Amici} )=\{(f,b),(d,g)\}.$

Soddisfacibilità 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 $\forall x.(p(x)\rightarrow p(x))$ , una soddisfacibile può essere $\exists x.(g(x)\rightarrow p(x))$ , una insoddisfacibile può essere $\forall x.(p(x)\not \rightarrow 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

Collegamenti esterni

(EN) Eric W. Weisstein, Model, su MathWorld, Wolfram Research.

Portale Informatica

Portale Matematica