With this, we have covered all of the possible ways to assign meaning to formulas via interpretations. Now, we are ready to move onto formally defining the notion of satisfaction. Recall from propositional logic that for a formula $\varphi$, this was determining whether there was an assignment of variables to truth values, or valuation, $t$ such that $\varphi^t = T$. In fact, we have been doing this already through various examples highlighting how our choice of interpretation and environment can change the value assigned to a formula. We will now formally define the value of a formula under an interpretation.
Definition 15.1. An interpretation $\mathcal I$ and environment $E$ satisfy a formula $\varphi$, denoted $\mathcal I \models_E \varphi$ if $\varphi^{(\mathcal I, E)} = T$; they do not satisfy $\varphi$ ($\mathcal I \not\models_E \varphi$) if $\varphi^{(\mathcal I,E)} = F$.
We define the satisfaction relation $\mathcal I \models_E \varphi$ recursively as follows.
If $\mathcal I \models_E \varphi$ for every environment $E$, then $\mathcal I$ satisfies $\varphi$ and we write $\mathcal I \models \varphi$.
Note that, yes, unfortunately, we do use the same symbol here as semantic entailment. Unfortunately, we will also continue to use the same symbol for both satisfication of a formula under an interpretation as well as semantic entailment in the sense that we're used to even for predicate logic.
Definition 15.2. A formula $\varphi$ is
Note that for validity in predicate logic is analogous to tautology in propositional logic. We do not use tautology in the context of predicate logic. Note also that establishing validity of a predicate formula is much more difficult than determining whether a propositional formula is a tautology, which is an understatement. In fact, the problem of determining validity of a first-order formula is an example of a problem that's undecidable.
Now that we have the notion of what it means for a formula to be satisfied by an interpretation, we can move on to establishing the notion of semantic entailment in predicate logic. First, we need to define what it means for a set of formulas to be satisfied by an interpretation.
Definition 15.3. Let $\Sigma$ be a set of formulas, $\mathcal I$ an interpretation, and $E$ an environment. We write $\mathcal I \models_E \Sigma$ if and only if $\mathcal I \models_E \psi$ for every formula $\psi \in \Sigma$.
Definition 15.4. Let $\Sigma$ be a set of formulas and $\varphi$ a formula. We say that $\Sigma$ semantically entails $\varphi$, written $\Sigma \models \varphi$, if and only if for any interpretation $\mathcal I$ and environment $E$, we have $\mathcal I \models_E \Sigma$ implies $\mathcal I \models_E \varphi$.
At first glance, this seems like a pretty straightforward translation of the concept of semantic entailment from propositional logic to predicate logic. And it is true that if we view valuations as interpretations, then this the same idea: under every valuation for which $\Sigma$ is satisfied, we have $\varphi$ is satisfied. So we simply replace the word valuation with interpretation and environment and we have the predicate logic version of semantic entailment.
However, while the basic idea is the same, there is a significant consequence of our new definition. Before, determining whether an entailment held in propositional logic was very straightforward: we just check for satisfaction of $\Sigma$, which means, at worst, building a big truth table and determining which valuations are those for which $\Sigma$ is satisfied. We could do this because there were only at most $2^n$ different valuations if there were $n$ propositional variables involved in the entailment. This approach will not work for predicate logic, because we need to show that the condition holds for every interpretation and environment, and there could be infinitely many of these.
Example 15.5. We will show that $\{(\exists y (\forall x P(x,y)))\} \models (\forall x (\exists y P(x,y)))$. We will prove this by contradiction. Suppose that there exists an interpretation $\mathcal I$ such that $(\exists y (\forall x P(x,y)))^\mathcal I = T$ and $(\forall x (\exists y P(x,y)))^\mathcal I = F$.
Since $(\exists y (\forall x P(x,y)))^\mathcal I = T$, there must be an element $a \in D^\mathcal I$ such that $(\forall x P(x,y))^{(\mathcal I, E[y \mapsto a])} = T$. Then, we must also have $P(x,y)^{(\mathcal I, E[y \mapsto a][x \mapsto c])} = T$ for every element $c \in D^\mathcal I$.
Since $(\forall x (\exists y P(x,y)))^\mathcal I = F$, we have that $(\neg (\forall x (\exists y P(x,y))))^\mathcal I = T$ and equivalently, $(\exists x (\forall y (\neg P(x,y))))^\mathcal I = T$. That is, if $(\forall x (\exists y P(x,y)))^\mathcal I = F$, there is an element $b \in D^\mathcal I$ such that $(\forall y (\neg P(x,y)))^{(\mathcal I, E[x \mapsto b])} = T$ and then for every element $d \in D^\mathcal I$, we have $(\neg P(x,y))^{(\mathcal I, E[x \mapsto b][y \mapsto d])} = T$.
Observe that we have $P(x,y)^{(\mathcal I, E[x \mapsto b][y \mapsto a])} = T$, since $b \in D^\mathcal I$ and $(\neg P(x,y))^{(\mathcal I, E[x \mapsto b][y \mapsto a])} = T$ since $a \in D^\mathcal I$. But this means that $P(x,y)$ evaluates to both $T$ and $F$ under the same interpretation $\mathcal I$ and environment $E[x \mapsto b][y \mapsto a]$, which is a contradiction.
Example 15.6. Here, we'll prove that a semantic entailment doesn't hold. We will show $\{(\forall x (\exists y P(x,y)))\} \not \models (\exists y (\forall x P(x,y)))$. This is a nice reminder that semantic entailment is not symmetric!
Again, remember that in order to show that an entailment doesn't hold, all we need to do is give an interpretation $\mathcal I$ such that $(\forall x (\exists y P(x,y)))^\mathcal I = T$ while $(\exists y (\forall x P(x,y)))^\mathcal I = F$.
We will define the interpretation $\mathcal I$ by the domain $D^\mathcal I = \{1,2,3\}$ and the binary predicate $P^\mathcal I = \{\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle\}$.
First, we will show $(\forall x (\exists y P(x,y)))^\mathcal I = T$. This means that for every element $c \in D^\mathcal I$, we have $(\exists y P(x,y))^{(\mathcal I, E[x \mapsto c])} = T$. Then,
Thus, in each case, we have $(\exists y P(x,y))^{(\mathcal I, E[x \mapsto c])} = T$. Therefore, $(\forall x (\exists y P(x,y)))^\mathcal I = T$.
Now, we need to show that $(\exists y (\forall x P(x,y)))^\mathcal I = F$. In other words, we would have $(\neg (\exists y (\forall x P(x,y))))^\mathcal I = T$ and therefore, we will show that $(\forall y (\exists x (\neg P(x,y))))^\mathcal I = T$. This means that for every element $c \in D^\mathcal I$, we need to show that $(\exists x (\neg P(x,t)))^{(\mathcal I, E[y \mapsto c])} = T$. Then,
Thus, in each case, we have $(\exists x (\neg P(x,y))^{(\mathcal I, E[y \mapsto c])} = T$. Therefore, $(\exists y (\forall x P(x,y)))^\mathcal I = F$.
Example 15.7. We will show that $\emptyset \models ((\forall x(\alpha \rightarrow \beta)) \rightarrow ((\forall x \alpha) \rightarrow (\forall x \beta)))$, where $\alpha$ and $\beta$ are formulas. We will prove this by contradiction. Suppose that there exist an interpretation $\mathcal I$ and environment $E$ such that $$\mathcal I \not \models_E ((\forall x(\alpha \rightarrow \beta)) \rightarrow ((\forall x \alpha) \rightarrow (\forall x \beta))).$$ Then by the satisfaction relation, we must have that $\mathcal I \models_E (\forall x(\alpha \rightarrow \beta))$ and $\mathcal I \not \models_E ((\forall x \alpha) \rightarrow (\forall x \beta))$. But then this means that $\mathcal I \models_E (\forall x \alpha)$ while $\mathcal I \not \models_E (\forall x \beta)$, again by the definition of the satisfaction relation.
Now, since $\mathcal I \models_E (\forall x (\alpha \rightarrow \beta))$ and $\mathcal I \models_E (\forall x \alpha)$, we have that for every element $a \in D^\mathcal I$, we have $\mathcal I \models_{E[x \mapsto a]} (\alpha \rightarrow \beta)$ and $\mathcal I \models_{E[x \mapsto a]} \alpha$. From these we must also have $\mathcal I \models_{E[x \mapsto a]} \beta$ for every $a \in D^\mathcal I$. Therefore, we have $\mathcal I \models_E (\forall x \beta)$, which is a contradiction.
Recall that $\emptyset \models \varphi$ in propositional logic means that $\varphi$ is a tautology. The same idea holds for predicate logic, so in fact, we have just shown that $((\forall x(\alpha \rightarrow \beta)) \rightarrow ((\forall \alpha) \rightarrow (\forall \beta)))$ is valid. Similarly, one can show by a similar argument that $\{(\forall x (\alpha \rightarrow \beta))\} \models ((\forall x \alpha) \rightarrow (\forall x \beta))$.
Example 15.8. Another example, this time considering a generalized version of De Morgan. We will show $(\forall x (\neg \varphi)) \models (\neg(\exists x \varphi))$. First, we suppose that $\mathcal I \models_E (\forall x(\neg \varphi))$. By definition, we have that for every element $a \in D^\mathcal I$, we have $\mathcal I \models_{E[x \mapsto a]} (\neg \varphi)$. Again by definition, we have for every $a \in D^\mathcal I$, $\mathcal I \not \models_{E[x \mapsto a]} \varphi$. In other words, there is no $a \in D^\mathcal I$ such that $\mathcal I \models_{E[x \mapsto a]} \varphi$. Then by definition, $\mathcal I \models_E (\neg (\exists x \varphi))$.
Example 15.9 Now we'll show another entailment that doesn't hold. In propositional logic, to show that $\varphi \not \models \psi$, this involved finding a valuation such that $\varphi^t = T$ and $\psi^t = F$. The same idea holds, just with an interpretation and possibly an environment.
We will show that $\{((\forall x \alpha) \rightarrow (\forall x \beta))\} \not \models (\forall x (\alpha \rightarrow \beta))$, where $\alpha$ and $\beta$ are formulas. We will need to show that there are formulas $\alpha$ and $\beta$ and an interpretation $\mathcal I$ and environment $E$ such that $\mathcal I \models_E ((\forall x \alpha) \rightarrow (\forall x \beta))$ while $\mathcal I \not \models_E (\forall x (\alpha \rightarrow \beta))$.
Let $\alpha = P(x)$ and $\beta = (\neg P(x))$. We define an interpretation $\mathcal I$ with domain $D^\mathcal I = \{a,b\}$ and unary predicate $P^\mathcal I = \{b\}$. Let $E$ be any environment.
First, we will show $\mathcal I \models_E ((\forall x \alpha) \rightarrow (\forall x \beta))$. To show this, we observe that making $(\forall x \alpha)$ evaluate to false makes $((\forall x \alpha) \rightarrow (\forall x \beta))$ evaluate to true by the implication rule. Observe that we have $a \not \in P^\mathcal I$, which gives us $\alpha^{(\mathcal I, E[x \mapsto a])} = F$. Then $(\forall x \alpha)^{(\mathcal I, E)} = F$ and therefore, $((\forall x \alpha) \rightarrow (\forall x \beta))^{(\mathcal I,E)} = T$.
Next, we will show $\mathcal I \not \models_E (\forall x (\alpha \rightarrow \beta))$. To make $(\alpha \rightarrow \beta)$ evaluate to false, we must have $\alpha$ evaluate to true while $\beta$ evaluates to false. Since $b \in P^\mathcal I$, we have $\alpha^{(\mathcal I, E[x \mapsto b])} = T$ and $\beta^{(\mathcal I, E[x \mapsto b])} = F$. Thus, we have $(\alpha \rightarrow \beta)^{(\mathcal I, E[x \mapsto b])} = F$ and therefore, $(\forall x (\alpha \rightarrow \beta))^{(\mathcal I,E)} = F$.
Thus, there is an interpretation $\mathcal I$ under which $((\forall x \alpha) \rightarrow (\forall x \beta)^{\mathcal I} = T$ while $(\forall x (\alpha \rightarrow \beta))^{\mathcal I} = F$. Therefore, by definition, we have $\{((\forall x \alpha) \rightarrow (\forall x \beta))\} \not \models (\forall x (\alpha \rightarrow \beta))$.