Lesson 6

We are now turning to some interesting and more concrete examples. We shall now define a model \(\mathbb{N}\), appropriate to the vocabulary of number theory. Its universe \(U = \{0, 1, 2, 3, … \}\) is the set of all nonnegative whole numbers. To the constant \(0\), \(\mathbb{N}\) assigns the number \(0^{\mathbb{N}}= 0\). To the function \(\sigma\), \(\mathbb{N}\) assigns the unary function \(\sigma^{\mathbb{N}}(n) = n + 1\). Similarly, to \(+\) it assigns addition, to \(\times\) multiplication, and to \(\uparrow\) exponentiation. Two numbers \(m\) and \(n\) are related by \(<^{\mathbb{N}}\) if \(m\) is less than \(n\). Finally, assume that \(\mathbb{N}\) maps all variables to, say, \(0\) (recall that the values assigned to variables by a model are not very important by the Lemma).

We claim that \(\mathbb{N}\models \forall x(x < x + 1)\). To prove this, we have to use our knowledge about the properties of numbers to verify that, for any natural number \(n\), \(\mathbb{N}_{x = n}\models x < x + 1\). That is, we must show that, for all \(n\), \(n <^{\mathbb{N}}n +^{\mathbb{N}}1^{\mathbb{N}}\). But this is equivalent to saying that \(n < n + 1\), which we know is true of every number \(n\).

On the other hand, \(\mathbb{N}\not\models \forall x \exists y (x = y + y)\). The reason is that \(\mathbb{N}_{x = 1}\not\models \exists y (x = y + y)\), or equivalently \(\mathbb{N}_{x = 1}\models \forall y \neg(x = y + y)\), which means that \(1 \neq n + n\) for all whole numbers \(n\), which is clearly a true statement.

Arguing about model \(\mathbb{N}\) adds another dimension to the slippery distinction between logic and the metalanguage. In order to find out whether \(\mathbb{N}\models \phi\), we invoke our mathematical knowledge of the properties of integers, the very subject to which we are supposed to be gaining some insight by this exercise. We only do this for the purpose of illustrating the concepts of model and satisfaction. Our ultimate goal is to be able to mechanize this process, and develop techniques that discriminate between those sentences that are satisfied by \(\mathbb{N}\) (i.e., the theorems of number theory) and those that are not. Later, this goal will prove unattainable in a most interesting and devastating way.