1 Logic 1.9 First order logic 1.11 First order equivalences

1.10 Interpretations

A WFF isn’t true or false until you specify a truth assignment for its variables. Similarly, a first order formula isn’t true or false on its own. Before we can get a truth value we have to give an interpretation.

Definition 1.10.1.

An interpretation of a first order formula consists of a set $A$ , called the domain of the interpretation, and a relation on $A$ for each relation symbol in the formula.

In the interpreted formula, the variables can be elements of the domain $A$ of the interpretation. We write $\forall x\in A$ to mean “for every $x$ in $A$ ”, and $\exists x\in A$ to mean “there exists an element $x\in A$ .”

Once we’ve given an interpretation, we can try to decide if the formula is true or false in that interpretation.

Example 1.10.1.

Here are some interpretations of the first order formula

\forall x\;\exists y\;R(x,y).

The notation $\mathbb{N}$ means the set of all natural numbers $\{0,1,2,\ldots\}$ .

•

Domain $\mathbb{N}$ , relation $R$ is $<$ . The interpreted formula is written

$\forall x\in\mathbb{N}\;\exists y\in\mathbb{N}\;x<y.$

The interpreted formula is true. For every natural number $x$ there does exist a natural number $y$ with $x<y$ , e.g. $y$ could be the natural number $x+1$ .
•

Domain $\mathbb{N}$ , relation $R$ is $>$ . The interpreted formula is written

$\forall x\in\mathbb{N}\;\exists y\in\mathbb{N}\;x>y.$

The interpreted formula is false. It’s not true that for every natural number $x$ there exists a natural number $y$ such that $x>y$ . For example, $x$ could be 0 in which case no natural number $y$ satisfies $x>y$ .

Example 1.10.2.

This is a slight variation on the formula from the previous example.

\exists y\forall x\;R(x,y)

Again, to give an interpretation we have to give a domain — a set $A$ for the elements represented by $y$ and $x$ to belong to — and a relation $R$ on $A$ . The interpreted statement will be true if and only if there is an element $y\in A$ such that every $x\in A$ is related to $y$ by the interpretation of the relation $R$ .

Is this formula true in the following interpretations?

•

Domain $\mathbb{N}$ , relation $R(x,y)$ is $x\leqslant y$ .
•

Domain $\mathbb{N}$ , relation $R(x,y)$ is $x\geqslant y$ .

(The answer is no for the first one and yes for the second.)

We already know how to determine the truth value in a particular interpretation of a formula just involving the logical connectives.

1.10.1 Truth of quantified formulas

The rules for deciding whether a formula containing a quantifier is true in an interpretation with domain $A$ are:

•

An interpreted formula $\forall x\in A\;\phi$ is true if for every element $a$ of $A$ , substituting $a$ into $\phi$ in place of $x$ gives a true statement.
•

An interpreted formula $\exists x\in A\;\phi$ is true in an interpretation if there is an element $a$ of $A$ such that substituting $a$ into $\phi$ in place of $x$ gives a true statement.

(There are some subtleties in doing substitution into logical formulas caused by the concepts of free and bound variables, but they are beyond the scope of MATH0005. If you want to learn more, take MATH0037 Logic in your third year or read the book by Goldrei in the further reading for this chapter.)

Example 1.10.3.

Here are two first order formulas:

•

$F_{1}=\exists x\neg\exists y\;P(x,y)$
•

$F_{2}=\forall y\neg\forall x\;P(x,y)$

Let’s try and determine whether $F_{1}$ and $F_{2}$ are true in some interpretations.

(1)
Consider the interpretation with domain $\{0,1,2\}$ and where the relation $P(x,y)$ is interpreted as $x<y$ .
- •
  
  $F_{1}$ is interpreted as saying there is an $x\in\{0,1,2\}$ such that it is not the case that there is a $y$ in $\{0,1,2\}$ such that $x<y$ . That’s true: if $x=2$ then it is not the case that there is a $y$ in $\{0,1,2\}$ with $x<y$ .
- •
  
  $F_{2}$ is interpreted as saying for every $y\in\{0,1,2\}$ it is not the case that for all $x\in\{0,1,2\}$ we have $x<y$ . We could find if this is true by checking each $y$ in turn. But it’s simpler to just notice that whatever $y$ is, $x$ could take the same value, and then $x<y$ will be false. So $F_{2}$ is also true.
(2)
Next, consider the interpretation with domain $\{0,1,2\}$ and where the relation $P(x,y)$ is interpreted as $x\leqslant y$ .
- •
  
  $F_{1}$ is interpreted as saying there is an $x\in\{0,1,2\}$ such that it is not the case that there is a $y$ in $\{0,1,2\}$ such that $x\leqslant y$ . That’s false: $y$ can always take the same value as $x$ , and then $x\leqslant y$ .
- •
  
  $F_{2}$ is interpreted as saying for every $y\in\{0,1,2\}$ it is not the case that for all $x\in\{0,1,2\}$ we have $x\leqslant y$ . But when $y=2$ , it is the case that for all $x\in\{0,1,2\}$ we have $x\leqslant y$ . So $F_{2}$ is false in this interpretation.
(3)
Finally, consider the interpretation with domain $\mathbb{N}$ and where the relation $P(x,y)$ is interpreted as $x<y$ .
- •
  
  $F_{1}$ is interpreted as saying there is an $x\in\mathbb{N}$ such that it is not the case that there is a $y$ in $\mathbb{N}$ such that $x<y$ . That’s false: for every $x\in\mathbb{N}$ the number $y=x+1$ is in $\mathbb{N}$ too, and $x<y$ .
- •
  
  $F_{2}$ is interpreted as saying for every $y\in\mathbb{N}$ it is not the case that for all $x\in\mathbb{N}$ we have $x<y$ . This is true: whatever $y$ is, we can take $x=y$ and then it is not the case that $x<y$ .

It was awkward to determine the truth or falsity of these formulas in the given interpretations. One thing that would be helpful would be to transform them into equivalent, simpler formulas. We know about logically equivalent WFFs for propositional calculus, but right now we don’t know how to define logical equivalence in first order logic.