Example 14.1. Since interpretations in predicate logic are analogous to valuations in propositional logic, the truth of a particular formula will change depending on our interpretation. Consider the formula $\varphi = P(a, f(b))$, where $P$ is a binary predicate symbol, $a$ and $b$ are constant symbols, and $f$ is a unary function symbol.
First, we'll consider an interpretation $\mathcal I_1$ such that $\varphi^{\mathcal I_1} = T$. Let the domain of $\mathcal I_1$ be $D^{\mathcal I_1} = \mathbb N$. We will define our set of symbols as follows. $$a^{\mathcal I_1} = 2 \quad b^{\mathcal I_1} = 7$$ $$P^{\mathcal I_1} = \{\langle m,n \rangle \mid m \leq n \}$$ $$f^{\mathcal I_1}: n \mapsto n+1$$ In other words, we have $a$ mapped to 2, $b$ mapped to 7, $P$ is the less-than-or-equals relation, and $f$ is the successor function. Under the interpretation $\mathcal I_1$, we have $\varphi^{\mathcal I_1} = T$, since $f^{\mathcal I_1}(7) = 8$ and $\langle 2,8 \rangle \in P^{\mathcal I_1}$ since $2 \leq 8$.
The interpretation $\mathcal I_1$ looks pretty reasonable. However, we can define an interpretation $\mathcal I_2$ such that $\varphi^{\mathcal I_2} = F$. We will see that in defining this interpretation, we have a lot of leeway in defining our interpretation. Let the domain of $\mathcal I_2$ be $D^{\mathcal I_2} = \{0,1\}$. We will define our set of symbols as follows. $$a^{\mathcal I_2} = 1 \quad b^{\mathcal I_2} = 0$$ $$P^{\mathcal I_2} = \{\langle 0,0 \rangle, \langle 0,1 \rangle \}$$ \begin{align*} f^{\mathcal I_2}: 0 & \mapsto 0 \\ 1 & \mapsto 0 \end{align*} Note that we have a pretty artificial looking interpretation here. However, we have defined everything according to the rules. We have assigned our constants to elements of the domain. We have defined an appropriate binary relation. We have defined a total unary function that maps an element of the domain to some other element of the domain. And we can conclude that $\varphi^{\mathcal I_2} = F$, since $f^{\mathcal I_2}(0) = 0$ and therefore $\langle 1,0 \rangle \not \in P^{\mathcal I_2}$.
Now that takes care of a lot of the expressions that we'll be dealing with, but there's a glaring omission: variables. Suppose we have a formula $P(x,t)$, where $x$ is a variable and $t$ is a term, and we want to interpret it in an interpretation $\mathcal I$. How do we do this? A straightforward attempt would be something like $$P^\mathcal I (x^\mathcal I, t^\mathcal I).$$ But what is $x^\mathcal I$? The whole point of variables is that we don't really know what it's supposed to be, and so we can't assign it a particular element of our domain $D^\mathcal I$. Clearly, we need some additional information about how to interpret variables in our model.
Definition 14.2. An environment is a function $E : V \to D^\mathcal I$ that assigns a value in the domain $D^\mathcal I$ to each variable, where the set of variables is denoted by $V$.
Example 14.3. Suppose $D^\mathcal I = \{a,b,c\}$. If our set of variables is $x,y,z$, our environment $E$ could be defined \begin{align*} x &\mapsto a \\ y &\mapsto c \\ z &\mapsto a \end{align*} Note that the domain of the function $E$ is the set of variables in our formula. In the case of this particular example, the domain of $E$ is $\{x,y,z\}$. This is important to keep in mind because in defining an environment, every variable must be assigned some element in the domain, whether or not they are bound.
But what if every variable is bound? In this case, an environment is not needed. This is because bound variables get their meaning from the quantifier they are bound to. On the other hand, free variables have no intrinsic meaning, which is why we must define an environment. The environment gives the free variables meaning. In summary,
Example 14.4. Suppose we have an interpretation $\mathcal I$ with $D^\mathcal I = \mathbb N$. If we have the formula $\varphi = (x = y)$, we can choose environments under the same interpretation $\mathcal I$ that will make $\varphi$ evaluate to true and false. For instance consider the two environments $E_1$ and $E_2$, \begin{align*} E_1 : x &\mapsto 2, \\ y &\mapsto 2, \\ E_2 : x &\mapsto 72, \\ y &\mapsto 3. \end{align*} Then $\varphi^{(\mathcal I,E_1)} = T$, while $\varphi^{(\mathcal I, E_2)} = F$. However, suppose we have a formula $\psi = (0 = 1)$. Since $\psi$ doesn't contain any variables, the interpretation $\mathcal I$ suffices to provide meaning to it; we don't need to define an environment for it.
An interpretation together with an environment will be enough to let us interpret any formula. We will define formally how to apply an environment to a term. Note that we don't need a new definition for formulas, since it will just propagate in the same way as an interpretation does until it gets to the terms.
Definition 14.5. Let $\mathcal I$ be an interpretation and $E$ an environment. For each term $t$, the value of $t$ under $\mathcal I$ and $E$, denoted $t^{(\mathcal I, E)}$ is as follows.
Recall back to propositional logic, when we defined the notion of a valuation on a formula. One of the things we proved about valuations was that every formula under a valuation would be assigned to a single, unique truth value. We can prove something similar to this about terms under an interpretation and environment. Namely, we would like to know that applying an interpretation and environment to a term will always result in the term being assigned an element of the domain.
Proposition 14.6. Let $t$ be a (well-formed) term and let $\mathcal I$ be an interpretation with domain $D^\mathcal I$ and $E$ an environment. Then $t^{(\mathcal I,E)} \in D^\mathcal I$.
We won't present the proof of this fact. However, the proof of this fact can be shown by applying structural induction on $t$ and makes a great exercise.
One way of looking at this is that we interpret $t$ as a function parameterized by an environment $E$. In our definition above, we could say that the interpretation of $t$ interprets $x$ as whatever it is assigned to by $E$, under which $t^\mathcal I$ is parameterized by.
Since this definition is based on terms, the interpretation with an environment applies to a predicate in the same way as it does with functions as you would expect. And therefore, the interpretation of formulas is fairly straightforward for free variables.
The last tricky bit to deal with regarding variables is how to interpret variables that are bound to quantifiers and, by extension, interpreting the quantifiers themselves. First, we require a bit more machinery.
Definition 14.7. Let $E$ be an environment and let $c \in D^\mathcal I$ be an element in the domain of an interpretation $\mathcal I$. We define the environment $E$ with $x$ reassigned to $c$, denoted $E[x \mapsto c]$ by $$E[x \mapsto c](y) = \begin{cases} c & \text{if $y = x$,} \\ E(y) & \text{if $y \neq x$.} \end{cases}$$
Here, we have defined a way to make changes to an environment. If we think back to the analogy of how variables are treated in the programming context, we can think of an environment as defining the values of global variables. And as we saw before, we can have variables that take on a different meaning in a local scope. This is the idea we need to capture with interpreting bound variables. Now, we can define the values of quantified formulas.
Definition 14.8. Let $\mathcal I$ be an interpretation with domain $D^\mathcal I$ and $E$ be an environment. Then the value of a formula $\varphi = (\mathsf{Q}x \alpha)$ under $\mathcal I$ and $E$ is defined by \begin{align*} (\forall x \alpha)^{(\mathcal I,E)} &= \begin{cases} T & \text{if $\alpha^{(\mathcal I, E[x \mapsto c])} = T$ for every $c \in D^\mathcal I$,} \\ F & \text{otherwise,} \end{cases} \\ (\exists x \alpha)^{(\mathcal I,E)} &= \begin{cases} T & \text{if $\alpha^{(\mathcal I, E[x \mapsto c])} = T$ for some $c \in D^\mathcal I$,} \\ F & \text{otherwise,} \end{cases} \\ \end{align*}
As I mentioned just before, we treat the bound variable $x$ as a local variable. This means that the environment that we consider when evaluating $\varphi$ is an environment with $x$ overridden locally. In the case of formulas using $\forall x$, we must check that $\alpha$ evaluates to true whenever $x$ is assigned to every element in our domain, while for those formulas $\exists x$, we only need to determine whether there is at least one element in the domain that we can assign $x$ to in order to have $\alpha$ evaluate to true.
Example 14.9. We will define the interpretation $\mathcal I$. Let domain be $D^\mathcal I = \{a,b\}$. We have a binary predicate $P^\mathcal I = \{\langle a,a \rangle, \langle a,b \rangle, \langle b,b \rangle \}$. We define an environment $E$ by \begin{align*} E: x &\mapsto a \\ y & \mapsto b. \end{align*}
Let's consider some formulas under the interpretation $\mathcal I$ and environment $E$.
Now, consider the formula $(\exists y P(y,x))$. We have $(\exists y P(y,x))^{(\mathcal I,E)} = T$. To see this, recall that in order for this to be true, there has to be an element in the domain that we can map $y$ to based on the assignment of $x$ in our environment in order to satisfy the predicate. Since $E(x) = a$, we can map $y$ to $a$ so that $\langle a,a \rangle \in P^\mathcal I$. In order to do this, we need to define a new environment based on $E$ with the assignment of $y$ overridden, which is exactly $E[y \mapsto a]$. This gives us $\langle E[y \mapsto a](y), E[y \mapsto a](x)\rangle = \langle a, a \rangle \in P^\mathcal I$. Thus, we have $P(y,x)^{(\mathcal I,E[y \mapsto a])} = T$ and have shown that $(\exists y P(y,x))^{(\mathcal I,E)} = T$.
Remember that $E[x \mapsto c]$ is a new environment, where we override the original assignment of the variable $x$ in the environment $E$ with a new variable assignment. Note that we could have chosen $b$ as our domain element to satisfy the formula. You might ask, well do we need to reassign $y$ if $y$ was already assigned by our original environment? The answer is yes, since we need to remember that we are treating the bound $y$ differently from the free $y$. Therefore, we would have needed to define an environment $E[y \mapsto b]$ in order to argue that our formula holds under the given interpretation and environment.
We also have $(\forall x (\forall y P(x,y)))^{(\mathcal I,E)} = F$. To see this, recall that $\langle b,a \rangle \not \in P^\mathcal I$. Then we get $P(x,y)^{(\mathcal I, E[x \mapsto b][y \mapsto a])} = F$. Clearly, it is not the case that every assignment of $x$ and $y$ works.
Now, what if we wanted to determine $(\forall x (\exists y P(x,y)))^{(\mathcal I, E)}$? What we need to do is: for each assignment of $x$ to a domain element, we must find a domain element to map $y$ to in order to satisfy the formula. We can do this by considering the following: \begin{align*} P(x,y)^{(\mathcal I, E[x \mapsto a][y \mapsto a])} &= T\\ P(x,y)^{(\mathcal I, E[x \mapsto b][y \mapsto b])} &= T \end{align*} Here, we have considered all assignments of $x$ and for each assignment of $x$, we have found an assignment of $y$ such that the resulting assignments of $x$ and $y$ ($\langle a,a \rangle$ and $\langle b,b\rangle$) satisfy the relation $P^\mathcal I$.
These last few examples may lead you to the question of whether we really needed to define an environment. Since every variable was bound, we ended up overriding every assignment anyway. And you would be absolutely correct in making this observation! Remember: an environment is only needed when the formula contains free variables. Otherwise, an interpretation is all that is necessary to give the formula meaning.