Modello (logica matematica)

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 ${\displaystyle {\mathcal {T}}}$ in teoria dei modelli, una struttura ${\displaystyle {\mathcal {M}}=(M,\sigma ,I)}$ è definita come modello se

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

dove

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

Dominio

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

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

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

Funzione di interpretazione

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

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

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

• ${\displaystyle S=\{\mathrm {PadreDi} ,\mathrm {Amici} ,a,b,c,d,f,g\}}$, con
  • ${\displaystyle \mathrm {PadreDi} }$ simbolo funzionale,
  • ${\displaystyle \mathrm {Amici} }$ simbolo relazionale,
  • e ${\displaystyle a,b,c,d,f,g}$ simboli costanti;
• ${\displaystyle \mathrm {ar} }$ funzione di arietà tale che:
  • ${\displaystyle \mathrm {ar} (\mathrm {PadreDi} )=1,}$
  • ${\displaystyle \mathrm {ar} (\mathrm {Amici} )=2,}$
  • ${\displaystyle \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 ${\displaystyle I}$ tale che:

• ${\displaystyle 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} ;}$
• ${\displaystyle I(\mathrm {PadreDi} )=h\quad }$ tale che ${\displaystyle \quad h(b)=a,\quad h(d)=c,\quad h(f)=e;}$
• ${\displaystyle I(\mathrm {Amici} )=\{(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 ${\displaystyle \forall x.(p(x)\rightarrow p(x))}$, una soddisfacibile può essere ${\displaystyle \exists x.(g(x)\rightarrow p(x))}$, una insoddisfacibile può essere ${\displaystyle \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

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

Collegamenti esterni

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