Chapter 33 Using interpretations
33.1 Validities and contradictions
Suppose we want to show that ‘$\exists xA(x,x)\to B(d)$’ is not a validity. This requires showing that the sentence is not true in every interpretation; i.e., that it is false in some interpretation. If we can provide just one interpretation in which the sentence is false, then we will have shown that the sentence is not a validity.
In order for ‘$\exists xA(x,x)\to B(d)$’ to be false, the antecedent (‘$\exists xA(x,x)$’) must be true, and the consequent (‘$B(d)$’) must be false. To construct such an interpretation, we start by specifying a domain. Keeping the domain small makes it easier to specify what the predicates will be true of, so we will start with a domain that has just one member. For concreteness, let’s say it is just the city of Paris.
 domain:

Paris
The name ‘$d$’ must refer to something in the domain, so we have no option but:
 $d$:

Paris
Recall that we want ‘$\exists xA(x,x)$’ to be true, so we want all members of the domain to be paired with themselves in the extension of ‘$A$’. We can just offer:
 $A(x,y)$:

blank${}_{x}$ is identical with blank${}_{y}$
Now ‘$A(d,d)$’ is true, so it is surely true that ‘$\exists xA(x,x)$’. Next, we want ‘$B(d)$’ to be false, so the referent of ‘$d$’ must not be in the extension of ‘$B$’. We might simply offer:
 $B(x)$:

blank${}_{x}$ is in Germany
Now we have an interpretation where ‘$\exists xA(x,x)$’ is true, but where ‘$B(d)$’ is false. So there is an interpretation where ‘$\exists xA(x,x)\to B(d)$’ is false. So ‘$\exists xA(x,x)\to B(d)$’ is not a validity.
We can just as easily show that ‘$\exists xA(x,x)\to B(d)$’ is not a contradiction. We need only specify an interpretation in which ‘$\exists xA(x,x)\to B(d)$’ is true; i.e., an interpretation in which either ‘$\exists xA(x,x)$’ is false or ‘$B(d)$’ is true. Here is one:
 domain:

Paris
 $d$:

Paris
 $A(x,y)$:

blank${}_{x}$ is identical with blank${}_{y}$
 $B(x)$:

blank${}_{x}$ is in France
This shows that there is an interpretation where ‘$\exists xA(x,x)\to B(d)$’ is true. So ‘$\exists xA(x,x)\to B(d)$’ is not a contradiction.

‣
To show that $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$ is not a validity, it suffices to find an interpretation where $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$ is false.

‣
To show that $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$ is not a contradiction, it suffices to find an interpretation where $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$ is true.
33.2 Logical equivalence
Suppose we want to show that ‘$\forall xS(x)$’ and ‘$\exists xS(x)$’ are not logically equivalent. We need to construct an interpretation in which the two sentences have different truth values; we want one of them to be true and the other to be false. We start by specifying a domain. Again, we make the domain small so that we can specify extensions easily. In this case, we will need at least two objects. (If we chose a domain with only one member, the two sentences would end up with the same truth value. In order to see why, try constructing some partial interpretations with onemember domains.) For concreteness, let’s take:
 domain:

Ornette Coleman, Miles Davis
We can make ‘$\exists xS(x)$’ true by including something in the extension of ‘$S$’, and we can make ‘$\forall xS(x)$’ false by leaving something out of the extension of ‘$S$’. For concreteness, let’s say:
 $S(x)$:

blank${}_{x}$ plays saxophone
Now ‘$\exists xS(x)$’ is true, because ‘$S(x)$’ is true of Ornette Coleman. Slightly more precisely, extend our interpretation by allowing ‘$c$’ to name Ornette Coleman. ‘$S(c)$’ is true in this extended interpretation, so ‘$\exists xS(x)$’ was true in the original interpretation. Similarly, ‘$\forall xS(x)$’ is false, because ‘$S(x)$’ is false of Miles Davis. Slightly more precisely, extend our interpretation by allowing ‘$d$’ to name Miles Davis, and ‘$S(d)$’ is false in this extended interpretation, so ‘$\forall xS(x)$’ was false in the original interpretation. We have provided a counterinterpretation to the claim that ‘$\forall xS(x)$’ and ‘$\exists xS(x)$’ are logically equivalent.
To show that $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{A}$}$ and $\colorbox[rgb]{0.992156862745098,0.956862745098039,0.980392156862745}{$\mathcal{B}$}$ are not logically equivalent, it suffices to find an interpretation where one is true and the other is false.
33.3 Validity, entailment and satisfiability
To test for validity, entailment, or satisfiability, we typically need to produce interpretations that determine the truth value of several sentences simultaneously.
Consider the following argument in FOL:
To show that this is invalid, we must make the premise true and the conclusion false. The conclusion is a conditional, so to make it false, the antecedent must be true and the consequent must be false. Clearly, our domain must contain two objects. Let’s try:
 domain:

Karl Marx, Ludwig von Mises
 $G(x)$:

blank${}_{x}$ hated communism
 $a$:

Karl Marx
Given that Marx wrote The Communist Manifesto, ‘$G(a)$’ is plainly false in this interpretation. But von Mises famously hated communism, so ‘$\exists xG(x)$’ is true in this interpretation. Hence ‘$\exists xG(x)\to G(a)$’ is false, as required.
Does this interpretation make the premise true? Yes it does! Note that ‘$G(a)\to G(a)$’ is true. (Indeed, it is a validity.) But then certainly ‘$\exists x(G(x)\to G(a))$’ is true, so the premise is true, and the conclusion is false, in this interpretation. The argument is therefore invalid.
In passing, note that we have also shown that ‘$\exists x(G(x)\to G(a))$’ does not entail ‘$\exists xG(x)\to G(a)$’, i.e., that $\exists x(G(x)\to G(a))\u22ad\exists xG(x)\to G(a)$. Equally, we have shown that the sentences ‘$\exists x(G(x)\to G(a))$’ and ‘$\mathrm{\neg}(\exists xG(x)\to G(a))$’ are jointly satisfiable.
Let’s consider a second example:
Again, we want to show that this is invalid. To do this, we must make the premises true and the conclusion false. Here is a suggestion:
 domain:

Canadian citizens currently in a domestic partnership with another Canadian citizen
 $L(x,y)$:

blank${}_{x}$ is in a domestic partnership with blank${}_{y}$
The premise is clearly true on this interpretation. Anyone in the domain is a Canadian citizen in a domestic partnership with some other Canadian citizen. That other citizen will also, then, be in the domain. So for everyone in the domain, there will be someone (else) in the domain with whom they are in a domestic partnership. Hence ‘$\forall x\exists yL(x,y)$’ is true. However, the conclusion is clearly false, for that would require that there is some single person who is in a domestic partnership with everyone in the domain, and there is no such person, so the argument is invalid. We observe immediately that the sentences ‘$\forall x\exists yL(x,y)$’ and ‘$\mathrm{\neg}\exists y\forall xL(x,y)$’ are jointly satisfiable and that ‘$\forall x\exists yL(x,y)$’ does not entail ‘$\exists y\forall xL(x,y)$’.
For our third example, we’ll mix things up a bit. In chapter 30, we described how we can present some interpretations using diagrams. For example:
Using the conventions employed in chapter 30, the domain of this interpretation is the first three positive whole numbers, and ‘$R(x,y)$’ is true of x and y just in case there is an arrow from x to y in our diagram. Here are some sentences that the interpretation makes true:

‣
‘$\forall x\exists yR(y,x)$’

‣
‘$\exists x\forall yR(x,y)$’ (witness for $x$: $1$)

‣
‘$\exists x\forall y(R(y,x)\leftrightarrow x=y)$’ (witness for $x$: $1$)

‣
‘$\exists x\exists y\exists z((\mathrm{\neg}y=z\wedge R(x,y))\wedge R(z,x))$’ (witness for $x$: $2$)

‣
‘$\exists x\forall y\mathrm{\neg}R(x,y)$’ (witness for $x$: $3$)

‣
‘$\exists x(\exists yR(y,x)\wedge \mathrm{\neg}\exists yR(x,y))$’ (witness for $x$: $3$)
This immediately shows that all of the preceding six sentences are jointly satisfiable. We can use this observation to generate invalid arguments, e.g.:
$\forall x\exists yR(y,x),\exists x\forall yR(x,y)$  $\therefore \forall x\exists yR(x,y)$  
$\exists x\forall yR(x,y),\exists x\forall y\mathrm{\neg}R(x,y)$  $\therefore \mathrm{\neg}\exists x\exists y\exists z(\mathrm{\neg}y=z\wedge (R(x,y)\wedge R(z,x)))$ 
and many more besides.
An interpretation which refutes a claim—to logical truth, say, or to entailment—is called a counterinterpretation, or a countermodel.
We’ll close this section, though, with a caution about the relationship between (in)validity and (non)entailment. Recall FOL’s limitations: it is an extensional language; it ignores issues of vagueness; and it cannot handle cases of validity for ‘special reasons’. To take one illustration of these issues, consider this naturallanguage argument:

Every fox is cute.

∴
All vixens are cute.
This is valid: necessarily every vixen is a fox, so it is impossible for the premise to be true and the conclusion false. Now, we might sensibly symbolize the argument as follows:
However, it is easy to find countermodels which show that $\forall x(F(x)\to C(x))\u22ad\forall x(V(x)\to C(x))$. (Exercise: find one.) So, it would be wrong to infer that the English argument is invalid, just because there is a countermodel to the relevant FOLentailment.
The general moral is this. If you want to infer from the absence of an entailment in FOL to the invalidity of some English argument, then you need to argue that nothing important is lost in the way you have symbolized the English argument.
Practice exercises
A. Show that each of the following is neither a validity nor a contradiction:

1.
$D(a)\wedge D(b)$

2.
$\exists xT(x,h)$

3.
$P(m)\wedge \mathrm{\neg}\forall xP(x)$

4.
$\forall zJ(z)\leftrightarrow \exists yJ(y)$

5.
$\forall x(W(x,m,n)\vee \exists yL(x,y))$

6.
$\exists x(G(x)\to \forall yM(y))$

7.
$\exists x(x=h\wedge x=i)$
B. Show that the following pairs of sentences are not logically equivalent.

1.
$J(a)$, $K(a)$

2.
$\exists xJ(x)$, $J(m)$

3.
$\forall xR(x,x)$, $\exists xR(x,x)$

4.
$\exists xP(x)\to Q(c)$, $\exists x(P(x)\to Q(c))$

5.
$\forall x(P(x)\to \mathrm{\neg}Q(x))$, $\exists x(P(x)\wedge \mathrm{\neg}Q(x))$

6.
$\exists x(P(x)\wedge Q(x))$, $\exists x(P(x)\to Q(x))$

7.
$\forall x(P(x)\to Q(x))$, $\forall x(P(x)\wedge Q(x))$

8.
$\forall x\exists yR(x,y)$, $\exists x\forall yR(x,y)$

9.
$\forall x\exists yR(x,y)$, $\forall x\exists yR(y,x)$
C. Show that the following sentences are jointly satisfiable:

1.
$M(a),\mathrm{\neg}N(a),P(a),\mathrm{\neg}Q(a)$

2.
$L(e,e),L(e,g),\mathrm{\neg}L(g,e),\mathrm{\neg}L(g,g)$

3.
$\mathrm{\neg}(M(a)\wedge \exists xA(x)),M(a)\vee F(a),\forall x(F(x)\to A(x))$

4.
$M(a)\vee M(b),M(a)\to \forall x\mathrm{\neg}M(x)$

5.
$\forall yG(y),\forall x(G(x)\to H(x)),\exists y\mathrm{\neg}I(y)$

6.
$\exists x(B(x)\vee A(x)),\forall x\mathrm{\neg}C(x),\forall x\left[(A(x)\wedge B(x))\to C(x)\right]$

7.
$\exists xX(x),\exists xY(x),\forall x(X(x)\leftrightarrow \mathrm{\neg}Y(x))$

8.
$\forall x(P(x)\vee Q(x)),\exists x\mathrm{\neg}(Q(x)\wedge P(x))$

9.
$\exists z(N(z)\wedge O(z,z)),\forall x\forall y(O(x,y)\to O(y,x))$

10.
$\mathrm{\neg}\exists x\forall yR(x,y),\forall x\exists yR(x,y)$

11.
$\mathrm{\neg}R(a,a)$, $\forall x(x=a\vee R(x,a))$

12.
$\forall x\forall y\forall z[(x=y\vee y=z)\vee x=z]$, $\exists x\exists y\mathrm{\neg}x=y$

13.
$\exists x\exists y((Z(x)\wedge Z(y))\wedge x=y)$, $\mathrm{\neg}Z(d)$, $d=e$
D. Show that the following arguments are invalid:

1.
$\forall x(A(x)\to B(x))\therefore \exists xB(x)$

2.
$\forall x(R(x)\to D(x)),\forall x(R(x)\to F(x))\therefore \exists x(D(x)\wedge F(x))$

3.
$\exists x(P(x)\to Q(x))\therefore \exists xP(x)$

4.
$N(a)\wedge N(b)\wedge N(c)\therefore \forall xN(x)$

5.
$R(d,e),\exists xR(x,d)\therefore R(e,d)$

6.
$\exists x(E(x)\wedge F(x)),\exists xF(x)\to \exists xG(x)\therefore \exists x(E(x)\wedge G(x))$

7.
$\forall xO(x,c),\forall xO(c,x)\therefore \forall xO(x,x)$

8.
$\exists x(J(x)\wedge K(x)),\exists x\mathrm{\neg}K(x),\exists x\mathrm{\neg}J(x)\therefore \exists x(\mathrm{\neg}J(x)\wedge \mathrm{\neg}K(x))$

9.
$L(a,b)\to \forall xL(x,b),\exists xL(x,b)\therefore L(b,b)$

10.
$\forall x(D(x)\to \exists yT(y,x))\therefore \exists y\exists z\mathrm{\neg}y=z$