Semantica
Consideriamo un generico linguaggio del prim’ordine \[L = Const \cup Funct \cup Rel .\]
Il nostro obiettivo è quello di definire opportune nozioni
di modello (= \(L\)-struttura) \(\mathcal{A}\) e di interpretazione in \(\mathcal{A}\) di termini e formule di \(L\).
\(L\)-strutture
Una \(L\)-struttura \(\mathcal{A}\) consiste di
un insieme non vuoto, detto universo o dominio della struttura, generalmente indicato con \(|\mathcal{A}|\) o anche con la medesima lettera usata per la struttura, ma in carattere tondo, in questo caso \(A\);
un’interpretazione in \(\mathcal{A}\) di ogni simbolo di \(L\), definita come segue:
se \(R \in Rel\) è un simbolo relazionale \(n\)-ario, la sua interpretazione \(R^\mathcal{A}\) in \(\mathcal{A}\) è una relazione \(n\)-aria su \(A\) , cioè \[R^\mathcal{A} \subseteq A^n = \underbrace{A \times \cdots \times A}_{n \text{ volte}};\]
se \(f \in Funct\) è un simbolo funzionale \(n\)-ario, allora \[f^\mathcal{A} \colon A^n \to A ,\] cioè \(f^\mathcal{A}\) è una funzione \(n\)-aria con argomenti e valori in \(A\);
se \(c \in Const\) è un simbolo di costante, la sua interpretazione in \(\mathcal{A}\) consiste di un elemento \[c^\mathcal{A} \in A .\]
\(L\)-strutture Se \(Rel= \mathopen \{ R_{1}, R_{2}, \dotsc \mathclose \}\), \(Funct = \mathopen \{ f_{1}, f_{2}, \dotsc \mathclose \}\) e \(Const = \mathopen \{ c_{1 \mathclose \}, c_{2}, \dotsc}\), la \(L\)-struttura \(\mathcal{A}\) sarà denotata con \[\langle A , R_{1}^\mathcal{A}, R_{2}^\mathcal{A} , \dots , f_{1}^\mathcal{A} , f_{2}^\mathcal{A} , \dots , c_{1}^\mathcal{A} , c_{2}^\mathcal{A} , \dots \rangle .\]
Esempi di \(L\)-strutture \((1)\)
Vediamo alcuni esempi di \(L\)-strutture, dove \(L = \{ P \}\) con \(P\) simbolo di relazione binario.
\(\mathcal{A}=\langle \mathbb{N},\leq\rangle\). Si tratta della struttura con dominio \(\mathbb{N}\) e in cui il simbolo di relazione binario \(P\) viene interpretato nella relazione binaria \(\leq\) su \(\mathbb{N}\), in simboli \[P^{\mathcal{A}}=\{( n,m)\in \mathbb{N}^2 \mid n\leq m\}.\]
\(\mathcal{B}=\langle \mathbb{N},P^{\mathcal{B}}\rangle\) dove \(P^{\mathcal{B}}\) è la relazione di congruenza modulo \(3\) su \(\mathbb{N}\). Dunque \(\mathcal{B}\) è la struttura con dominio \(\mathbb{N}\) in cui il simbolo di relazione binario \(P\) viene interpretato nella relazione binaria su \(\mathbb{N}\) \[P^{\mathcal{B}}=\{( n,m)\in \mathbb{N}^2 \mid n\equiv m \,\, (\text{mod } 3)\}.\]
\(\mathcal{C}=\langle \mathbb{Z},\leq\rangle\).
\(\mathcal{D}=\langle \mathbb{Z},P^{\mathcal{D}}\rangle\), dove \(P^{\mathcal{D}}\) è la relazione di congruenza modulo \(3\) su \(\mathbb{Z}\).
Sia \(L = \{ P \}\) con \(P\) simbolo di relazione binario. Come negli esempi precedenti, per definire una \(L\)-struttura bisogna specificare:
il suo dominio, che deve essere un insieme non vuoto \(X\);
una qualche relazione binaria \(R\) su \(X\).
Ogni coppia del tipo \(\langle X,R\rangle\) che soddisfi queste due condizioni è una \(L\)-struttura, indipendentemente dalle eventuali proprietà particolari di \(X\) e/o \(R\). Inoltre, cambiando il dominio e/o la relazione binaria su di esso, si ottengono \(L\)-strutture diverse.
Quindi anche i seguenti sono esempi di \(L\)-strutture.
\(\mathcal{E}=\langle X, R\rangle\) dove \(X\) è l’insieme dei residenti del comune di Torino e \(R\subseteq X\times X\) è la relazione definita da “\(a\mathrel{R} b\) se e solo se \(a\) è figlio di \(b\)”, in simboli \[R=\{\langle a,b\rangle\in X\times X \mid \text{ \( a\) è figlio di \( b\)}\}.\]
\(\mathcal{F}=\langle \{a,b,c,d\}, \{( a,a), ( a,b ), ( b,a), ( c,c), ( d,d) \}\rangle\),
\(\mathcal{G}=\langle \{a,b\}, \emptyset\rangle\)
…
Esempi di \(L\)-strutture \((2)\) Sia ora \(L = \{ Q \}\) con \(Q\) simbolo di relazione unario. In questo caso una \(L\)-struttura \(\mathcal{A} = \langle A, Q^{\mathcal{A}} \rangle\) è data da un insieme non vuoto \(A\) (il suo dominio) e da una relazione unaria \(Q^{\mathcal{A}}\) su \(A\), ovvero da un sottoinsieme \(Q^{\mathcal{A}} \subseteq A^1\). Poichè \(A^1\) è identificato con \(A\) stesso, la relazione unaria \(Q^{\mathcal{A}}\) non è altro che un qualche sottoinsieme del dominio di \(\mathcal{A}\).
Sono dunque esempi di \(L\)-struttura:
\(\mathcal{A} = \langle \mathbb{R}, \mathbb{N} \rangle\)
\(\mathcal{B}= \langle \mathbb{N}, Q^{\mathcal{B}} \rangle\), dove \(Q^{\mathcal{B}} = \left \{p \in \mathbb{N} \boldsymbol\mid p \text{ è un numero primo} \right\}\)
\(\mathcal{C} = \langle \mathbb{N} , \emptyset \rangle\)
\(\mathcal{D} = \langle \mathbb{Q}, \{ \frac{1}{2}, -3, \frac{4}{5} \} \rangle\)
\(\mathcal{E} = \langle \mathbb{R}, \mathbb{R} \rangle\)
…
Esempi di \(L\)-strutture \((3)\) Sia ora \(L=\{f\}\) con \(f\) simbolo di funzione binario. Le seguenti sono \(L\)-strutture:
\(\mathcal{A}=\langle \mathbb{Z},+\rangle\) dove \(\mathbb{Z}\) è il dominio di \(\mathcal{A}\) e la somma interpreta il simbolo di funzione binario \(f\) (ossia \(f^{\mathcal{A}}(n,m)=n+m\) per ogni \(( n,m)\in\mathbb{Z}^2\)).
\(\mathcal{B}=\langle \mathbb{N},+\rangle\) dove \(\mathbb{N}\) è il dominio di \(\mathcal{B}\) e la somma interpreta il simbolo di funzione binario \(f\) (ossia \(f^{\mathcal{B}}(n,m)=n+m\) per ogni \(( n,m)\in\mathbb{N}^2\)).
\(\mathcal{C}=\langle \mathbb{Q},\cdot\rangle\) dove \(\mathbb{Q}\) è il dominio di \(\mathcal{C}\) e il prodotto interpreta il simbolo di funzione binario \(f\) (ossia \(f^{\mathcal{C}}(r,q)=r\cdot q\) per ogni \(( r,q)\in\mathbb{Q}^2\)).
Più in generale, per definire una \(L\)-struttura bisogna specificare:
il suo dominio, che deve essere un insieme non vuoto \(X\);
una qualche funzione binaria \(g \colon X^2 \to X\).
Ogni coppia del tipo \(\langle X,g\rangle\) che soddisfi queste due condizioni è una \(L\)-struttura, indipendentemente dalle proprietà particolari di \(X\) e/o \(g\).
\(L = \{ f \}\) con \(f\) simbolo di funzione binario. Altri esempi di \(L\)-strutture sono:
\(\langle \mathbb{R},+\rangle\)
\(\langle \mathbb{R}^*,\cdot\rangle\), dove \(\mathbb{R}^*=\mathbb{R}\setminus\{0\}\) è l’insieme dei numeri reali non nulli
\(\langle \mathbb{R}^+,\cdot\rangle\), dove \(\mathbb{R}^+\) è l’insieme dei numeri reali maggiori di \(0\)
\(\langle \mathbb{Z}_{3},+\rangle\), dove \(\mathbb{Z}_{3}=\{[n]_{3} \mid n\in \mathbb{Z}\}\) è l’insieme delle classi di resto modulo \(3\)
\(\langle \{a,b,c\}, F\rangle\), dove \[F \colon (\{ a,b,c \})^2 \to \{ a,b,c \}, \qquad ( x,y)\mapsto x\] è la funzione che assegna ad ogni coppia la sua prima componente
…
NON è invece una \(L\)-struttura la coppia \(\langle \mathbb{N} , - \rangle\), perchè la sottrazione non è una funzione da \(\mathbb{N}^2\) in \(\mathbb{N}\) (non è definita per tutte le coppie di numeri naturali).
Esempi di \(L\)-strutture \((4)\) Sia \(L=\{P,f,c\}\) un linguaggio con \(P\) simbolo di relazione binario, \(f\) simbolo di funzione binario e \(c\) simbolo di costante. Le seguenti sono \(L\)-strutture.
\(\mathcal{A}=\langle \mathbb{Z}, \leq, +,0\rangle\) dove \(P^{\mathcal{A}}=\{( n,m)\in\mathbb{Z}^2 \mid n\leq m\}\subseteq \mathbb{Z}\times\mathbb{Z}\) interpreta il simbolo di relazione binario \(P\),
\(f^{\mathcal{A}} \colon \mathbb{Z}^2 \to \mathbb{Z}\), \(( n,m)\mapsto n+m\)
interpreta il simbolo di funzione binario \(f\) e \(c^{\mathcal{A}} = 0 \in\mathbb{Z}\) interpreta il simbolo di costante \(c\).
\(\mathcal{B}=\langle \mathbb{Z}, <, \cdot,100\rangle\) dove \(P^{\mathcal{B}}\) è la relazione di minore stretto \(<\), \(f^{\mathcal{B}}\) è la moltiplicazione tra numeri interi e \(c^{\mathcal{B}}\) è il numero intero \(100\).
\(\mathcal{C}=\langle \mathbb{R}, \geq, \cdot,-\sqrt{2}\rangle\) dove \(P^{\mathcal{C}}\) è \(\geq\), \(f^{\mathcal{C}}\) è la moltiplicazione tra numeri reali e \(c^{\mathcal{C}}\) è il numero reale \(-\sqrt{2}\).
…
Alcune precisazioni e osservazioni
è possibile che \(c_{i}^\mathcal{A} = c_{j}^\mathcal{A}\), anche se i simboli di costante sono distinti.
Analogamente, se i simboli di predicato \(R_{i}\) e \(R_{j}\) o i simboli di funzione \(f_{i}\) e \(f_{j}\) hanno la stessa arietà, è possibile che \(R_{i}^\mathcal{A} = R_{j}^\mathcal{A}\) o che \(f_{i}^\mathcal{A} = f_{j}^\mathcal{A}\).
Esempio
Se \(L = \{ P,Q,a,b \}\) con \(P\) e \(Q\) simboli di relazione binari e \(a , b\) simboli di costante, è legittimo considerare la \(L\)-struttura \[\mathcal{A}= \langle \mathbb{N}, \leq , \leq , 0 , 0 \rangle,\] ovvero la struttura con dominio \(A\) e tale che \[P^{\mathcal{A}} = Q^{\mathcal{A}} = \{ (n,m) \in \mathbb{N}^2 \mid n \leq m \}\] e \[a^{\mathcal{A}} = b^{\mathcal{A}} = 0.\]
Alcune precisazioni e osservazioni
Per convenzione, se i simboli di un linguaggio \(L\) sono elencati in un determinato ordine, allora anche le relazioni/funzioni/costanti che li interpretano in una data struttura vanno presentati nello stesso ordine.
Esempio
Se \(L = \{ P, f, g, c \}\) con \(P\) simbolo di relazione binario, \(f\) e \(g\) simboli di funzione binari e \(c\) simbolo di costante, allora dire che \[\langle \mathbb{R}, < , +, \cdot , 3 \rangle\] è una \(L\)-struttura significa che \(\mathbb{R}\) è il dominio della struttura, \(<\) è l’interpretazione di \(P\), la somma \(+\) è l’interpretazione di \(f\), il prodotto \(\cdot\) è l’interpretazione di \(g\) e \(3\) è l’interpretazione di \(c\).
A cosa servono le \(L\)-strutture?
Sia \(L = \{ P \}\) con \(P\) simbolo di relazione binario e sia φ l’enunciato \(\exists x \forall y P(x,y)\), che asserisce che “esiste un \(x\) che è in relazione \(P\) con tutti gli \(y\)”. Non ha senso chiedersi se φ sia vero o falso: la risposta infatti dipenderà da
quali oggetti/elementi decidiamo di considerare
qual’è la relazione \(P\) in questione.
Ad esempio, se decidiamo di considerare i numeri naturali e di identificare \(P\) con l’usuale relazione d’ordine \(\leq\) su tale insieme, allora φ è vero, perchè esiste un elemento, lo \(0\), che è minore o uguale di tutti i numeri naturali. Tecnicamente, quello che abbiamo fatto è considerare la \(L\)-struttura \(\langle \mathbb{N} , \leq \rangle\) e osservare che φ, interpretato in tale struttura, è vero. Se invece consideriamo le \(L\)-strutture \(\langle \mathbb{Z}, \leq \rangle\) oppure \(\langle \mathbb{N}, \geq \rangle\), allora φ risulta falso in esse (perchè?).
Le \(L\)-strutture servono a fornire un “contesto” in cui interpretare le formule del prim’ordine scritte utilizzando il linguaggio \(L\).