Atomic formulas

Remember that we started our discussion in this chapter by setting our aim at assigning truth values to formulas. Once we have assigned meaning to our constants and predicates, we are in the position to do just that! Again, the basic idea underlying the mathematical machinery is not very difficult to grasp, but it is a very fundamental insight in several areas of thought, including philosophy, linguistics, and mathematics, and it was only precisely formulated around the middle of the 20$^\text{th}$ century by the Polish logician Alfred Tarski.

We can illustrate this basic idea algorithmically, by looking at how one may go on calculating truth-values for atomic formulas, once a structure $\mathbf{S}$ is specified. Let’s take some arbitrary constants from our language $\mathcal{L}_0$, using $a$, $b$, and $c$. Let’s also take some arbitrary predicates of the language, using $P$, $Q$, and $R$. We can further specify that $P$ is of arity $1$, $Q$ is of arity $2$, and $R$ is of arity $3$.

Now let’s take some rather arbitrary atomic formulas, let’s say:

1. $P(a)$

2. $P(c)$

3. $Q(a, c)$

4. $Q(c, a)$
5. $R(a, b, c)$
6. $R(a, c, b)$

What if I ask you to decide whether these formulas are true or false? In that case, you should say: I cannot do that, since you haven’t given me a domain $\mathbf{D}$ and an interpretation $\mathbf{I}$ that would tell me what these formulas mean, and against what I should evaluate them! Relative to different structures, different atomic formulas may be true or false, so there is no way to answer this question without first specifying a structure $\mathbf{S}$. So let’s do just that.

Take a domain $\mathbf{D}=\{\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}\}$, and an interpretation function such that:

1. $I(a)=\mathbf{a}$, $I(b)=\mathbf{b}$, $I(c)=\mathbf{c}$;

2. 1. $I(P)=\{\mathbf{a}, \mathbf{d}\}$;

   2. $I(Q)=\{\langle\mathbf{a}, \mathbf{c}\rangle, \langle\mathbf{d}, \mathbf{a}\rangle, \langle\mathbf{a}, \mathbf{d}\rangle\}$;

   3. $I(R)=\{\langle\mathbf{a}, \mathbf{b}, \mathbf{c}\rangle, \langle\mathbf{b}, \mathbf{c}, \mathbf{b}\rangle, \langle\mathbf{b}, \mathbf{b}, \mathbf{b}\rangle\}$.

Call this the structure $\mathbf{S}$. Now we can ask: which of the formulas are true relative to the structure $\mathbf{S}$? To answer this question, again, we need to do some very simple calculations.

The basic idea is this. To each constant of the language, the interpretation function $I$ assigns a member of the domain (see list item 1 above). And to each predicate (of arity $n$), the interpretation function assigns a set of $n$-tuples (see list item 2 above).

Next, all you have to do is check the value of a constant (or list of constants) under $I$, and compare it against the value of the relevant predicate under $I$. If the value of the constant (or sequence of constants) is in the value of the predicate under $I$, the atomic formula is true, otherwise, it is false.

Take the formula $P(a)$ (the formula (1) above). Is it true in $\mathbf{S}$? Well, we see that $I(a)=\mathbf{a}$. And we also see that $I(P)=\{\mathbf{a}, \mathbf{d}\}$. Since $I(a)$ (which is just $\mathbf{a}$) is in the set $I(P)$, the atomic formula $P(a)$ is true. On the other hand, if we take $P(c)$ (the formula (2) above), we see that $I(c)=\mathbf{c}$, and $\mathbf{c} \notin I(P)$, so $I(c) \notin I(P)$. So $P(c)$ is false in $\mathbf{S}$.

This may seem a bit elaborate, but really, all you are doing is checking if the value of the constant under $I$ is in the set that is the value of the predicate $P$.

There is a special way of representing the relation ‘the formula $X$ is true in the structure $\mathbf{S}$’. It is written like this: $\mathbf{S} \models X$. You can also read it as: $\mathbf{S}$ models $X$. This is simply because $\mathbf{S}$ ‘models’ a world in which $X$ would be true. So again, $\mathbf{S}\models P(a)$ ($\mathbf{S}$ models $P(a)$), but $\mathbf{S}\not\models P(c)$ ($\mathbf{S}$ does not model $P(c)$).

Predicates with more than $1$ arity aren’t more elaborate than this. The only difference is that now you have to check that the values of the constants under $I$ are in the value of the predicate as an $n$-tuple, and of course, in the right order.

Take $Q(a, c)$ (formula (3) above). Again, $I(a)=\mathbf{a}$, and $I(c)=\mathbf{c}$, so the question is whether $\langle\mathbf{a}, \mathbf{c}\rangle \in I(Q)$. By definition, $I(Q)=\{\langle\mathbf{a}, \mathbf{c}\rangle, \langle\mathbf{d}, \mathbf{a}\rangle, \langle\mathbf{a}, \mathbf{d}\rangle\}$. So $\langle\mathbf{a}, \mathbf{c}\rangle \in I(Q)$. So $\mathbf{S} \models Q(a, c)$, or $Q(a,c)$ is true in $\mathbf{S}$. On the other hand, $Q(c, a)$ would make us consider wether $\langle\mathbf{c}, \mathbf{a}\rangle \in I(Q)$, which as you can see it is not. So $\mathbf{S}\not\models Q(c, a)$ (formula (4)), or $Q(c, a)$ is false in $\mathbf{S}$.

Note that we can also take the reverse of this question. Namely, instead of considering whether a given formula is true in $\mathbf{S}$, we can start with $\mathbf{S}$ and consider which formulas are true in it. This is really just the reverse reasoning. For example, you can inspect $I(R)$, and see that $I(R)=\{\langle\mathbf{a}, \mathbf{b}, \mathbf{c}\rangle, \langle\mathbf{b}, \mathbf{c}, \mathbf{b}\rangle, \langle\mathbf{b}, \mathbf{b}, \mathbf{b}\rangle\}$. You can also see that $I(b)=\mathbf{b}$. Now, since $\langle\mathbf{b}, \mathbf{b}, \mathbf{b}\rangle \in I(R)$, that means $R(b, b, b)$ is true in $\mathbf{S}$, or $\mathbf{S} \models R(b, b, b)$.

Note that the structure above was rather trivial and intuitive. But we can give a completely different structure $\mathbf{N}$ and ask again whether the above formulas are true or false in that structure. Let $\mathbf{N}=\langle\mathbb{N}^+, I'\rangle$. In other words, the structure $S$ is such that its domain $\mathbf{D}=\mathbb{N}^+$, the set of all positive natural numbers.

We now specify a new interpretation $I'$, that interprets our formulas in $\mathbf{N}$.

1. $I'(a)=1$, $I'(b)=2$, $I'(3)=c$;

2. 1. $I'(P)=\{n \mid n\text{ is even}\}$;

   2. $I'(Q)=\{\langle n, k\rangle \mid n < k\}$;

   3. $I'(R)=\{\langle n, k, i\rangle \mid n+k=i\}$.

In other words, under $I'$, $P(x)$ means ‘$x$ is even’, $Q(x, y)$ means ‘$x$ is less than $y$’, and $R(x, y, z)$ means ‘$x+y=z$’. And $a$ under $I'$ means $1$, $b$ means $2$, and so on.

Then, we can consider $P(a)$ and $P(c)$ again. Well, doing the calculations, neither $1$ nor $3$ are even numbers, so $P(a)$ and $P(c)$ are both false.

On the other hand, one of $Q(a, c)$ and $Q(c, a)$ must be true, since $a$ and $c$ mean distinct numbers. In particular, $Q(a, c)$ means $1$ is smaller than $3$, and $Q(c, a)$ means $3$ is smaller than $1$ under $I'$. So $\mathbf{N}\models Q(a, c)$, but not $Q(c, a)$.

And incidentally, $R(a, b, c)$ is true in $\mathbf{N}$, since $1+2=3$. But $1+3\neq 2$, so $R(a, c, b)$ is false in $\mathbb{N}$.

Putting it all together

Now we are in the position to further extend our definition to include assigning truth values to atomic formulas. It goes like this: