Le (\(L\)-)strutture giocano nella logica del prim’ordine un ruolo analogo a quello delle interpretazioni/valutazioni nel caso della logica proposizionale!
Definiremo ora cosa vuol dire interpretare una \(L\)-formula \(\phi\) in una data \(L\)-struttura \(\mathcal{A}\) e, nel caso \(\phi\) sia un enunciato, daremo una definizione rigorosa di cosa vuol dire che (l’interpretazione di) \(\phi\) è vera in \(\mathcal{A}\), in simboli \[\mathcal{A} \models \varphi .\]
Incominciamo con alcuni esempi.
Sia \(L=\{f,g,c\}\) un linguaggio con due simboli di funzione binaria \(f,g\) e un simbolo di costante \(c\). Sia \(t_{1}\) il termine \(g(x,x)\) e \(t_{2}\) il termine \(f(c,c)\). Interpretando i simboli del linguaggio nelle \(L\)-strutture
\(\mathcal{A}=\langle \mathbb{R},+,\cdot,1\rangle\) e \(\mathcal{B}=\langle \mathbb{Q},+,\cdot,1\rangle\)
possiamo vedere \(t_{1}\) come il termine che rappresenta il polinomio \(x^2\) (scritto nella forma \(x \cdot x\)) e \(t_{2}\) come il termine che rappresenta il numero \(2\) (scritto nella forma \(1+1\)). La formula atomica \((t_{1}=t_{2})\) rappresenta quindi nel nostro linguaggio l’equazione \(x^2=2\).
Questa formula non è nè vera nè falsa in \(\mathcal{A}\), dipende dal valore di \(x\)!
(è vera se a \(x\) assegniamo il valore \(\sqrt{2}\) o \(- \sqrt{2}\), falsa in tutti gli altri casi.)
Consideriamo ora la formula \[\exists x (g(x,x) = f(c,c)).\] Interpretata in \(\mathcal{A}\) o in \(\mathcal{B}\), la formula corrisponde all’affermazione
L’equazione \(x^2 = 2\) ammette soluzioni.
Tale formula risulta vera in \(\mathcal{A} = \langle \mathbb{R}, +, \cdot , 1 \rangle\) (perchè in \(\mathbb{R}\) troviamo le due soluzioni dell’equazione \(\sqrt{2}\) e \(- \sqrt{2}\)) ma falsa in \(\mathcal{B} = \langle \mathbb{Q}, + , \cdot 1 \rangle\) (perchè \(\sqrt{2}\) non è un numero razionale).
La differenza di comportamento tra le formule \(g(x,x) = f(c,c)\) e \(\exists x (g(x,x) = f(c,c))\) quando cerchiamo di valutare se siano vere o meno in \(\mathcal{A}\) e/o \(\mathcal{B}\) dipende dal fatto che la prima formula contiene la variabile libera \(x\), mentre la seconda non ha variabili libere (ovvero è un enunciato).
La verità di \(\exists x(g(x,x)=f(c,c))\) (e, più in generale, degli enunciati) dipende solo dalla struttura in cui decidiamo di valutarla.
La verità di \(g(x,x)=f(c,c)\) (e, più in generale, delle formule con variabili libere) dipende sia dalla struttura scelta che dal valore assegnato ad \(x\) (o più in generale a tutte le variabili libere della formula).
Per dare una definizione rigorosa di cosa vuol dire interpretare una formula in una struttura, bisogna incominciare con l’interpretazione degli \(L\)-termini in una data \(L\)-struttura \(\mathcal{A}\).
L’interpretazione dei simboli di costante e funzione è ovvia, essendo esplicitamente data nella definizione stessa di \(L\)-struttura.
Quello che manca, tuttavia, è il modo per specificare l’interpretazione delle (eventuali) variabili di un termine: a questo scopo, introduciamo l’idea di assegnazione.
Definizione Un’assegnazione (nella \(L\)-struttura \(\mathcal{A}\)) per un insieme di variabili \(\{ x_{1}, x_{2}, \dotsc, x_{n} \}\) è una funzione che associa ad ogni variabile \(x_{i}\) dell’insieme un elemento \(a_{i} \in A\) (per ogni \(1 \leq i \leq n\)). Una tale assegnazione verrà di solito denotata con \[x_{1}/a_{1}, x_{2}/a_{2}, \dotsc, x_{n}/a_{n}\]
Ad esempio, se \(\mathcal{A}\) ha dominio \(\mathbb{N}\), un’assegnazione per l’insieme di variabili \(\{ x,y,z \}\) è una qualunque funzione \(\{ x,y,z \} \to \mathbb{N}\), ad esempio
\(x \mapsto 24\) \(y \mapsto 2\) \(z \mapsto 9\)
o in notazione compatta \[x/24,y/2,z/9\]
Interpretazione di termini
Sia \(\mathcal{A}\) una \(L\)-struttura (con dominio \(A\)) e \(t\) un \(L\)-termine.
L’interpretazione del termine \(t(x_{1}, \dotsc, x_{n})\) in \(\mathcal{A}\) mediante l’assegnazione \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\) si indica con \[t^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\] ed è definita per induzione strutturale:
se \(t\) è la variabile \(x_{i}\) (per qualche \(1 \leq i \leq n\)), allora \(t^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) è l’elemento \(a_{i}\), ovvero l’immagine di \(x_{i}\) mediante l’assegnazione data;
se \(t\) è una costante \(c\), allora \(t^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) è l’elemento \(c^{\mathcal{A}}\);
se \(t\) è \(f ( t_{1} , \dotsc , t_{k} )\), allora \(t^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) è l’elemento \[f^\mathcal{A} ( t_{1}^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}] , \dotsc , t_{k}^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}] ) .\]
Alcune osservazioni
L’interpretazione \(t^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) di \(t(x_{1}, \dotsc, x_{n})\) in \(\mathcal{A}\) mediante \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\) è sempre un elemento del dominio \(A\) di \(\mathcal{A}\).
è possibile che nella lista \(x_{1} , \dotsc, x_{n}\) vi siano anche variabili che in realtà non occorrono in \(t(x_{1}, \dotsc, x_{n})\): l’assegnazione data a tali variabili non influisce nel determinare \(t^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\). In altre parole: l’interpretazione di \(t(x_{1}, \dotsc, x_{n})\) in \(\mathcal{A}\) mediante \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\) dipende solo dai valori che l’assegnazione assume sulle variabili (libere) che occorrono in \(t\). In particolare, se \(t\) non contiene variabili (libere) allora l’interpretazione \(t^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) di \(t\) in \(\mathcal{A}\) non dipende per nulla dall’assegnazione \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\).
Ad esempio, se \(t(x,y,z)\) è il termine \(f(x,f(c,y))\) nel linguaggio \(L = \{ f,c \}\) (con \(f\) simbolo di funzione binario e \(c\) simbolo di costante), allora l’interpretazione \(t^\mathcal{A}[x/12,y/3,z/8]\) di \(t(x,y,z)\) in \(\mathcal{A} = \langle \mathbb{N}, +, 0 \rangle\) mediante \(x/12,y/3,z/8\) non dipende in alcun modo dal fatto che l’assegnazione dà a \(z\) il valore \(8\), visto che \(z\) non occorre in \(t\).
Interpretazione di termini e albero sintattico
Per interpretare correttamente un termine \(t\) in una struttura \(\mathcal{A}\) mediante \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\) si può sfruttare il suo albero sintattico, secondo il seguente algoritmo:
Dato il termine \(t\), se ne costruisce l’albero sintattico.
Se una foglia contiene una costance \(c\) del linguaggio, allora si sostituisce con \(c^\mathcal{A}\).
Se una foglia contiene una variabile \(x_{i}\) (per qualche \(1 \leq i \leq n\)), allora si sostituisce con il valore datole dall’assegnazione, ovvero con \(a_{i}\).
Si procede dal basso verso l’alto sostituendo ciascuna etichetta di un nodo con la sua interpretazione in \(\mathcal{A}\) come segue. Se l’etichetta è del tipo \(f(t_{1}, \dotsc, t_{k})\), nei nodi successori ci saranno i termini \(t_{1}\), …, \(t_{k}\), che nel frattempo saranno stati sostituiti con le loro interpretazioni \(t_{1}^\mathcal{A}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\), …, \(t_{k}^\mathcal{A}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\), rispettivamente; allora si sostituisce l’etichetta del nodo in questione con
\(f^\mathcal{A}( t_{1}^\mathcal{A}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}], \dotsc, t_{k}^\mathcal{A}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}])\).
Ad esempio, dato il liguaggio \(L = \{ f, g, c \}\) interpretiamo in \(\mathcal{A} = \langle \mathbb{N}, + , \cdot, 0 \rangle\) il termine \(t(x,y,z)\) dato da \(f ( x , g ( y, c ) )\) mediante l’interpretazione \(x/2, y/3, z/5\).
Sostituiamo le etichette delle foglie. Poi procediamo sostituendo le etichette dei nodi dal basso verso l’alto.
Il risultato che si ottiene svolgendo i calcoli nell’espressione che abbiamo sostituito all’etichetta della radice è proprio l’interpretazione cercata, ovvero \[ <11>{t^\mathcal {A}[x/2,y/3,z/5]} = 2+(3 \cdot 0) <11>{= 2} .\]
Osservazione: Non abbiamo mai dovuto utilizzare il fatto che \( z \) vada sostituito con \( 5 \): questo perchè \( z \) non compare affatto nel termine dato!
Esempio
Sia \(L = \left \{ f,g \right \}\) con \(f\) e \(g\) simboli di funzione binari, e sia \(t(x,y)\) il termine \(f ( x , g ( y, x ) )\).
Consideriamo la \(L\)-struttura \(\mathcal{A} = \langle \mathbb{N} , + , \cdot \rangle\) e l’assegnazione \(x/ 2 , y / 3\).
Allora \[t^{\mathcal{A}}[x/2, y/3] = 2 + ( 3 \cdot 2 ) = 8 .\]
Se invece \(\mathcal{B}\) è la \(L\)-struttura \(\langle \mathbb{Z}, \cdot, - \rangle\), allora \(t^{\mathcal{B}}[x/{-}2,y/6]\) è \[t^{\mathcal{B}}[x/{-}2,y/6] = (-2) \cdot (6 - (-2)) = (-2) \cdot 8 = -16.\]
Esercizio Sia \(L = \{ f,g,c \}\) con \(f\) e \(g\) simboli di funzione binari e \(c\) simbolo di costante. Consideriamo la \(L\)-struttura \(\mathcal{A} = \langle \mathbb{R}, + , \cdot , 0 \rangle\). Interpretare i seguenti termini in \(\mathcal{A}\) mediante l’assegnazione \(x/ \frac{2}{3} , y/ {-2} ,z/ \sqrt{2}\):
\(t_{1}\): \(f(g(z,z),y)\);
\(t_{2}\): \(g(f(c,c),g(c,c))\);
\(t_{3}\): \(f(c,f(g(x,c),y))\).
\[t_{1}^{\mathcal{A}}\left[x/ \frac{2}{3} , y/ -2 ,z/ \sqrt{2}\right] = (\sqrt{2} \cdot \sqrt{2}) + (-2) = 2 - 2 = 0.\] \[t_{2}^{\mathcal{A}}\left[x/ \frac{2}{3} , y/ -2 ,z/ \sqrt{2}\right] = (0+0) \cdot (0 \cdot 0) = 0 \cdot 0 = 0.\] \[\begin{gathered} t_{3}^{\mathcal{A}}\left[x/ \frac{2}{3} , y/ -2 ,z/ \sqrt{2}\right] = 0 + \left( \left(\frac{2}{3} \cdot 0\right) + (-2) \right) \\ = 0 + (0 + (-2)) = 0 + (-2) = -2 . \end{gathered}\]
Definiamo ora per induzione sulla complessità cosa vuol dire che una \(L\)-formula \(\phi(x_{1}, \dotsc, x_{n})\) è vera in una \(L\)-struttura \(\mathcal{A}\) mediante l’assegnazione \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\), in simboli \[\mathcal{A} \models \phi [ x_{1}/a_{1}, \dotsc, x_{n}/a_{n} ].\]
Se \(\phi\) è una formula atomica del tipo \((t = s)\) con \(t\) ed \(s\) termini, allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se \[t^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}] = s^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}] .\]
Se \(\phi\) è una formula atomica del tipo \((P(t_{1}, \dotsc, t_{k}))\) con \(P\) simbolo di relazione \(k\)-ario e \(t_{1}\), …, \(t_{k}\) termini, allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se \[( t_{1}^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}], \dotsc , t_{k}^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}] )\in P^{\mathcal{A}},\] ovvero se \(t_{1}^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\), …, \(t_{k}^{\mathcal{A}}[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\), che sono elementi del dominio di \(\mathcal{A}\), sono in relazione rispetto all’interpretazione \(P^{\mathcal{A}}\) del simbolo \(P\) in \(\mathcal{A}\).
Esempio
Siano dati
il linguaggio \(L=\{P,f,g,c\}\), con \(P\) simbolo di relazione binario, \(f,g\) simboli di funzione binari e \(c\) simbolo di costante;
la \(L\)-struttura \(\mathcal{A}=\langle \mathbb{Q},<, +,\cdot,1\rangle\);
la formula atomica \(\phi(x,y)\) data da \(P(g(x,x),f(y,c))\);
l’assegnazione \(x/1, y/2\).
Vogliamo determinare se \(\mathcal{A}\models \phi[x/1, y/2].\)
La formula \(\phi(x,y)\) è del tipo \(P(t_{1},t_{2})\), dove \(t_{1}\) è il termine \(g(x,x)\) e \(t_{2}\) è il termine \(f(y,c)\). Quindi
\(\mathcal{A}\models \phi[x/1, y/2]\) se e solo se \(t_{1}^\mathcal{A}[x/1, y/2] < t_{2}^\mathcal{A}[x/1, y/2]\).
Poichè \(t_{1}^\mathcal{A}[x/1, y/2] = 1 \cdot 1 = 1\) e \(t_{2}^\mathcal{A}[x/1, y/2] = 2 + 1 = 3\),
si ha che effettivamente \(t_{1}^\mathcal{A}[x/1, y/2] = 1 < 3 = t_{2}^\mathcal{A}[x/1, y/2],\)
perciò \(\mathcal{A}\models \phi[x/1, y/2]\).
Esercizio Siano \(L\), \(\mathcal{A}\) e \(\phi(x,y)\) come nell’esempio precedente. Sia inoltre \(\psi(x,y)\) la formula \[(f(x,x)=g(y,c)).\]
Determinare se
\(\mathcal{A}\models \phi[x/2,y/1]\) e \(\mathcal{A}\models\psi[x/2,y/1]\).
Se \(\phi\) è una negazione \((\neg \psi)\), allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se non è vero che \(\mathcal{A} \models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\).
Se \(\phi\) è una disgiunzione \((\psi \vee \chi)\), allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se \(\mathcal{A} \models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) oppure \(\mathcal{A} \models \chi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) (o entrambe).
Se \(\phi\) è una congiunzione \((\psi \wedge \chi)\), allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se \(\mathcal{A} \models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) e \(\mathcal{A} \models \chi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\).
Se \(\phi\) è un’implicazione \((\psi \to \chi)\), allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se \(\mathcal{A} \models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) implica che \(\mathcal{A} \models \chi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\).
Se \(\phi\) è una bi-implicazione \((\psi \leftrightarrow \chi)\), allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se \(\mathcal{A} \models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) implica \(\mathcal{A} \models \chi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) e viceversa.
Se \(\phi\) è una formula esistenziale \((\exists y \, \psi)\), allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se per qualche \(b \in A\) si ha che \(\mathcal{A} \models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n},y/b].\)
Se \(\phi\) è una formula universale \((\forall y \, \psi)\), allora \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se per ogni \(b \in A\) si ha che \(\mathcal{A} \models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n},y/b] .\)
La scrittura \(\mathcal{A} \not\models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) significa: non è vero che \(\mathcal{A}\models\phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\), ovvero \(\phi\) non è vera nella struttura \(\mathcal{A}\) mediante l’assegnazione \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\).
In particolare, \(\mathcal{A} \not\models (\exists y \, \psi )[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se per ogni \(b \in A\) si ha che \(\mathcal{A} \not\models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}, y/b]\) e \(\mathcal{A} \not\models (\forall y \, \psi)[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) se e solo se per qualche \(b \in A\) si ha che \(\mathcal{A} \not\models \psi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}, y/b]\) .
Osservazione importante Come nel caso dei termini, la verità di una formula \(\phi(x_{1}, \dotsc, x_{n})\) in una struttura \(\mathcal{A}\) mediante un’assegnazione \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\) dipende solo dai valori che l’assegnazione dà alle variabili che occorrono libere in \(\phi\).
Un esempio Consideriamo il linguaggio \(L=\{ P\}\) con \(P\) simbolo di relazione binario e la formula \(\phi\) \[\exists z (P(x,z)\wedge P(z,y)).\] Sia \(\mathcal{A}=\langle \mathbb{N}, < \rangle\) e consideriamo l’assegnazione \(x/2 ,y/4 ,z/4\).
Osserviamo che solo \(x, y\) sono variabili libere in \(\phi\), mentre \(z\) non lo è.
Per definizione, \(\mathcal{A} \models \exists z (P(x,z)\wedge P(z,y))[x/2,y/4, z/4]\) se e solo se per qualche \(n \in \mathbb{N}\) si ha che \(\mathcal{A} \models (P (x,z)\wedge P(z,y))[x/2,y/4,z/n]\), ossia se e solo se in \(\mathbb{N}\) è vero che
\(2 < n\) e \(n < 4\) per qualche \(n \in \mathbb{N}\).
Per \(n = 3\) si ha che effettivamente \(2 < n < 4\),
quindi \(\mathcal{A} \models (P(x,z)\wedge P(z,y))[x/2,y/4,z/3],\) da cui \(\mathcal{A} \models \phi[x/2,y/4,z/4].\)
Ad essere più precisi, la definizione ricorsiva che abbiamo visto permette di “scaricare” il problema di determinare se \(\phi\) è vera in \(\mathcal{A}\) mediante l’assegnazione \(x_{1}/a_{1}, \dotsc, x_{n}/a_{n}\) sulle sottoformule di \(\phi\) che compaiono nel suo albero sintattico, fino a giungere alle sue sottoformule atomiche (quelle che compaiono nelle foglie dell’albero): queste vengono valutate nella struttura mediante l’assegnazione che man mano si è creata, e a sua volta questo permette, risalendo lungo l’albero, di determinare se è vero o no che \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\).
Riprendiamo l’esempio precedente... è vero che \(\mathcal{A} \models \exists z (P(x,z)\wedge P(z,y))[x/2,y/4,z/4]\), dove \(\mathcal{A}= \langle \mathbb{N}, < \rangle\)?
Figura: Albero sintattico di \( \exists z (P(x,z)\wedge P(z,y)) \)
\( \mathcal {A} \models (P(x,z)\wedge P(z,y))[x/2,y/4,z/n] \)
Un altro esempio è vero che \(\mathcal{A} \models \forall z (P(x,z)\wedge P(z,y))[x/2,y/4,z/4]\), dove \(\mathcal{A}= \langle \mathbb{N}, < \rangle\)?
Figura: Albero sintattico di \( \forall z (P(x,z)\wedge P(z,y))\)
\( \mathcal {A} \models (P(x,z)\wedge P(z,y))[x/2,y/4,z/n] \)
Esercizio Sia \(L = \{ P,f,c \}\) con \(P\) simbolo di relazione binario, \(f\) simbolo di funzione binario e \(c\) simbolo di costante. Determinare se \[% \tag{$*$} \label{goal} \langle \mathbb{R}, {\leq} , \cdot, \sqrt{2} \rangle \models \forall x (f(y , x) = y \wedge \exists z (P(y,z) \wedge P(z, f(c,c)))) [y/0].\]
Nel caso di formule semplici, si può determinare se \(\mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}]\) “interpretando” la formula \(\phi(x_{1}, \dotsc, x_{n})\) in \(\mathcal{A}\) per capirne il significato.
Sia \(L = \left \{ R,f \right \}\) un linguaggio del prim’ordine con \(R\) simbolo di relazione binario ed \(f\) simbolo di funzione binario, consideriamo la formula \(\phi(x,y)\) \[\exists z (f(z,z) = x) \wedge \exists w (R (x,w) \wedge R(w,y))\] e la \(L\)-struttura \(\mathcal{A} = \langle\mathbb{N},< ,+ \rangle\). L’interpretazione di \(\phi(x,y)\) in \(\mathcal{A}\) è
Esiste \(z \in \mathbb{N}\) tale che \(z +z = x\) ed esiste \(w \in \mathbb{N}\) tale che (\(x < w\) e \(w < y\))
ovvero
“ \(x\) è pari e \(x\) e \(y\) sono numeri non consecutivi con \(x\) più piccolo di \(y\) .”
Quindi si ha ad esempio \(\mathcal{A} \models \phi[x/2,y/6]\) ma \(\mathcal{A} \not\models \phi[x/2,y/3]\) e \(\mathcal{A} \not\models \phi[x/3,y/6]\).
Esercizio Siano \(L\) e \(\phi(x,y)\) come nell’esercizio precedente. Consideriamo la \(L\)-struttura \(\mathcal{B} = \langle \mathbb{R}, {<}, + \rangle\). Dimostrare che per ogni \(a,b \in \mathbb{R}\) si ha
\(\mathcal{B} \models \phi[x/a,y/b]\) se e solo se \(a < b\).
Interpretando analogamente a prima la formula \(\phi(x,y)\) in \(\mathcal{B}\) si ottiene
Esiste \(z \in \mathbb{R}\) tale che \(z+z = x\) ed esiste \(w \in \mathbb{R}\) tale che (\(x < w\) e \(w < y\)).
In \(\mathbb{R}\) la prima parte è vera per ogni possibile valore di \(x\) (la metà di un numero reale è ancora un numero reale). La seconda parte è invece vera se e solo se il valore assegnato ad \(x\) è minore del valore assegnato a \(y\) (quando \(x < y\) basta considerare \(w = \frac{x+y}{2}\) per avere \(x < w < y\)). Quindi \[\begin{aligned} \mathcal{B} \models \phi[x/a,y/b] & \text{ \ se e solo se \ }\mathcal{B} \models \exists w (R(x,w) \wedge R(w,y)) [x/a,y/b] \\ & \text{ \ se e solo se \ } a < b.\end{aligned}\]
Verità di un enunciato
Dato che la verità di una formula in una struttura mediante un’assegnazione dipende solo dai valori dati dall’assegnazione alle sue variabili libere, allora per determinare la verità di un enunciato, ovvero di una formula che non ha variabili libere, NON è necessario avere a disposizione nessuna assegnazione.
Per questa ragione, quando \(\phi\) è un enunciato che risulta vero in una struttura \(\mathcal{A}\) scriveremo semplicemente \[\mathcal{A} \models \phi\] e diremo che \(\phi\) è vero (o soddisfatto) in \(\mathcal{A}\), o che \(\mathcal{A}\) è un modello di \(\phi\), o ancora che \(\mathcal{A}\) soddisfa \(\phi\).
La relazione \(\models\) (che è una relazione tra strutture ed enunciati) si chiama anche relazione di soddisfazione. La scrittura \(\mathcal{A} \not\models \phi\) significa che \(\mathcal{A}\) NON è un modello di \(\phi\) (equivalentemente: \(\mathcal{A}\) è un modello di \(\neg \phi\)).
Esempio
Sia \(L = \{ P,f,c \}\) con \(P\) simbolo di relazione binario, \(f\) simbolo di funzione binario e \(c\) simbolo di costante. Consideriamo l’enunciato \(\sigma\) \[\forall x \forall y ( (P(c,y) \wedge {f(x,x) = y}) \to P(x,y)).\]
Interpretando \(\sigma\) nella \(L\)-struttura \(\mathcal{A} = \langle \mathbb{N}, {<} , + , 2 \rangle\) si ottiene
Per ogni \(x,y \in \mathbb{N}\) (se (\(2 < y\) e \(x +x = y\)) allora \(x < y\)),
ovvero
“La metà di un numero pari \(n \in \mathbb{N}\) che sia maggiore di \(2\) è minore di \(n\) stesso”.
Questo è vero perchè se \(n = 2k\) e \(n > 2\), allora \(k > 1\) e quindi \(n = 2k = k+k > k\). Perciò \(\mathcal{A} \models \sigma\).
Non abbiamo avuto bisogno di nessuna assegnazione per valutare \(\sigma\) in \(\mathcal{A}\)!
Esercizio Siano \(L\) e \(\sigma\) come nell’esempio precedente. Dire se \(\sigma\) è vero in ciascuna delle seguenti \(L\)-strutture.
\(\langle \mathbb{Z}, {<}, + , -1 \rangle\)
\(\langle \mathbb{Q}, {\leq}, \cdot, 0 \rangle\)
\(\langle \mathbb{R}, {\geq}, \cdot, 0 \rangle\)
\(\langle \mathbb{Z}, {\geq}, + , 2 \rangle\)
Insiemi di verità
Quando una \(L\)-formula contiene variabili libere ha senso chiedersi quali assegnazioni in una data \(L\)-struttura \(\mathcal{A}\) la rendano vera (in \(\mathcal{A}\)).
Definizione Sia \(L\) un linguaggio, \(\phi\) una \(L\)-formula con \(FV(\phi) = \{ x_{1}, \dotsc, x_{n} \} \neq \emptyset\) e \(\mathcal{A}\) una \(L\)-struttura. L’insieme di verità di \(\phi\) in \(\mathcal{A}\) è l’insieme \[\phi(\mathcal{A}) = \{ (a_{1}, \dotsc, a_{n}) \in A^n \mid \mathcal{A} \models \phi[x_{1}/a_{1}, \dotsc, x_{n}/a_{n}] \}.\]
In altre parole, \(\phi(A)\) è l’insieme delle \(n\)-uple \((a_{1}, \dotsc, a_{n})\) di elementi del dominio di \(\mathcal{A}\) che rendono vera \(\phi\) in \(\mathcal{A}\) quando vengano assegnati alle variabili libere di \(\phi\). Si osservi che il numero di variabili libere determina l’arietà della relazione \(\phi(A)\): se \(\phi\) ha un’unica variabile libera allora \(\phi(A)\) è un sottoinsieme di \(A\), se \(\phi\) ha due variabili libere allora \(\phi(A)\) è un sottoinsieme di \(A^2\) (ovvero una relazione binaria su \(A\)), se \(\phi\) ha tre variabili libere allora \(\phi(A)\) è un sottoinsieme di \(A^3\) (ovvero una relazione ternaria su \(A\)), e così via.
Esempi Sia \(L = \{ f,a \}\) con \(f\) simbolo di funzione binaria e \(a\) simbolo di costante. Consideriamo la formula \(\phi\) \[\exists x (f(x,y) = a).\] Si osservi che \(FV(\phi) = \{ y \}\). Consideriamo ora la \(L\)-struttura \(\mathcal{A} = \langle \mathbb{Z}, + , 0 \rangle\). L’insieme di verità \(\phi(\mathcal{A})\) di \(\phi\) in \(\mathcal{A}\) sarà un sottoinsieme di \(\mathbb{Z}\) (poichè \(\phi\) ha un’unica variabile libera). Più precisamente \[\phi(\mathcal{A}) = \{ k \in \mathbb{Z} \mid \mathcal{A} \models \exists x (f(x,y)= a)[y/k] \},\]
ovvero \(\phi(\mathcal{A})\) è l’insieme di tutti i \(k \in \mathbb{Z}\) per cui esiste un \(x \in \mathbb{Z}\) tale che \(x+k = 0\). Questo è vero per ogni intero \(k\) (basta porre \(x = -k\)), per cui \(\phi(\mathcal{A}) = \mathbb{Z}\).
Considerando invece \(\mathcal{B} = \langle \mathbb{N}, + , 0 \rangle\), si ha che \[\phi(\mathcal{B}) = \{ 0 \} .\]
Sia ora \(L = \{ f,g \}\) con \(f\) e \(g\) simboli di funzione binari e consideriamo la formula \(\phi\) \[f(x,x) = g(x,x).\] In questo caso \(FV(\phi) = \{ x \}\), quindi \(\phi(\mathcal{A})\) sarà un sottoinsieme del dominio di \(\mathcal{A}\).
Se \(\mathcal{A} = \langle \mathbb{R}, +, \cdot \rangle\) si ha che \(r \in \phi(\mathcal{A})\) se e solo se \(\mathcal{A} \models (f(x,x) = g(x,x))[x/r]\) se e solo se \(r + r = r \cdot r\) se e solo se \(r^2 = 2r\). Risolvendo (in \(\mathbb{R}\)) quest’ultima equazione si ottiene \[\phi(\mathcal{A}) = \{ 0,2 \}.\]
Sia \(L = \{ f \}\) con \(f\) simbolo di funzione binario e consideriamo la formula \(\phi\) \[\exists z (f(x,z) = y).\] Si ha \(FV(\phi) = \{ x,y \}\), per cui \(\phi(\mathcal{A})\) sarà un sottoinsieme di \(A^2\), ovvero una relazione binaria sul dominio di \(\mathcal{A}\).
Sia \(\mathcal{A} = \langle \mathbb{N},+ \rangle\). Allora \((n,m) \in \phi(\mathcal{A})\) se e solo se \(\mathcal{A} \models \exists z (f(x,z) = y)[x/n,y/m]\) se e solo se esiste \(k \in \mathbb{N}\) tale che \(n + k = m\). Questo accade esattamente quando \(n \leq m\), perciò \[\phi(\mathcal{A}) = \{ (n,m) \in \mathbb{N}^2 \mid n \leq m \},\] ovvero l’insieme di verità di \(\phi\) in \(\mathcal{A}\) è la relazione di minore o uguale \(\leq\).
Considerando invece \(\mathcal{B} = \langle \mathbb{N}, \cdot \rangle\) si ha che \((n,m) \in \phi(\mathcal{B})\) se e solo se \(m = n \cdot k\) per qualche \(k \in \mathbb{N}\), ovvero \[\phi(\mathcal{B}) = \{ (n,m) \in \mathbb{N}^2 \mid m \text{ è un multiplo di } n \}.\]
Dunque l’insieme di verità di \(\phi\) in \(\mathcal{B}\) è la relazione di divisibilità \(|\).
Sia \(L = \{ P,f,c \}\) con \(P\) simbolo di relazione binario, \(f\) simbolo di funzione binario e \(c\) simbolo di costante. Consideriamo la formula \(\phi\) \[P(f(x,x),c)\] e notiamo che \(FV(\phi) = \{ x \}\).
Se \(\mathcal{A} = \langle \mathbb{Z}, < , + , 0 \rangle\), allora \(k \in \phi(\mathcal{A})\) se e solo se \(k+ k < 0\): questo è vero per \(k < 0\) e falso per \(k \geq 0\), per cui \[\phi(\mathcal{A}) = \{ k \in \mathbb{Z} \mid k < 0 \},\]
cioè \(\phi(\mathcal{A})\) è l’insieme degli interi negativi.
Se invece \(\mathcal{B} = \langle \mathbb{Z} , < , \cdot , 0 \rangle\), allora \(\phi(\mathcal{B})\) è l’insieme vuoto: infatti non c’è nessun intero il cui quadrato sia minore di \(0\).
Sia \(L= \{ P,f \}\) con \(P\) simbolo di relazione binario e \(f\) simbolo di funzione binario. Consideriamo la formula \(\phi\) \[P(y,z) \wedge \exists x \neg(f(y,x) = y ) \wedge \exists x (f(x,x) = z).\] e osserviamo che \(FV(\phi) = \{ y,z \}\). L’insieme di verità di \(\phi\) in \(\mathcal{A} = \langle \mathbb{N}, < , \cdot \rangle\) è l’insieme delle coppie \((n,m) \in \mathbb{N}^2\) tali che
\(n < m\)
esiste un \(k \in \mathbb{N}\) tale che \(n \cdot k \neq n\), ovvero \(n \neq 0\)
\(m\) è un quadrato perfetto.
Quindi \[\phi(\mathcal{A}) = \{ (n,m) \in \mathbb{N}^2 \mid n \neq 0 \text{ e } m \text{ è un quadrato perfetto maggiore di } n \}.\]
Esercizi
Sia \(L = \{ f,g,c \}\) con \(f\) e \(g\) simboli di funzione binari e \(c\) simbolo di costante e sia \(\phi(x,y)\) la formula \[\exists z ( f( f( g(z,z), g(x,z) ) , y) = c)\]
Consideriamo la \(L\)-struttura \(\mathcal{A} = \langle\mathbb{R}, + , \cdot , 0 \rangle\).
è vero che \(\mathcal{A} \models \phi[x/-2,y/1]\)?
è vero che \(\mathcal{A} \models \phi[x/1,y/1]\)?
Determinare l’insieme di verità in \(\mathcal{A}\) di \(\phi(x,y)\).
Dati \(b,c \in \mathbb{R}\), si ha che \(\mathcal{A} \models \phi[b,c]\) se e solo se l’equazione \(z^2 + bz+c = 0\) ammette una soluzione (reale). Quindi \(\mathcal{A} \models \phi[x/-2,y/1]\), \(\mathcal{A} \not\models \phi[x/1,y/1]\) e \[\phi(\mathcal{A}) = \{ (b,c) \in \mathbb{R}^2 \mid b^2-4c \geq 0 \}.\]
Sia \(L = \{ P, f,g,c \}\) un linguaggio dove \(P\) è un simbolo di relazione unario, \(f\) e \(g\) sono simboli di funzione binari e \(c\) un simbolo di costante. Sia \(\mathcal{A}\) la \(L\)-struttura \(\langle \mathbb{R}, \mathbb{Z}, + , \cdot, 1 \rangle\). Determinare l’insieme di verità in \(\mathcal{A}\) delle seguenti formule:
\(f(x,f(c,f(c,c))) = y \wedge P(y)\)
\(\exists z (f(x,g(z,z)) = y)\)
\(P(x) \wedge (g(x,x) = f(c,c))\)
\(\forall y (f(x,y) = y) \vee (x = c)\)
\(P(g(x,x)) \wedge P(f(x,c))\)
\(\exists y (P(y) \wedge P(f(x,y)))\)
Sia \(L = \{ Q,f \}\) con \(Q\) simbolo di relazione binario e \(f\) simbolo di funzione binario. Sia \(\phi\) la \(L\)-formula \[\forall x \exists y (\neg Q(x,z) \vee Q(f(y,x),z)).\] Notiamo che \(FV(\phi) = \{ z \}\). Determinare l’insieme di verità di \(\phi\) in ciascuna delle seguenti strutture:
\(\langle \mathbb{R}, {<} , + \rangle\)
\(\langle \mathbb{N}, | , \cdot \rangle\)
\(\langle \mathbb{Q}, {\geq} , - \rangle\)
\(\langle \mathbb{Z}, {\leq}, \cdot \rangle\)