Lesson 8

Model \(\mathbb{N}\) could be called the standard model for number theory, because, admittedly, we defined the vocabulary \(\Sigma_{\mathbb{N}}\) with this model in mind. However, there are other, nonstandard models appropriate for the vocabulary of number theory. For example, the model \(\mathbb{Z}_{p}\), where \(p > 1\) is an integer, has as universe the set \(\{0, 1, …, p-1\}\). \(0^{\mathbb{Z}_p}= 0\), and all operations are defined modulo \(p\). That is, for any \(m\) and \(n\) in the universe, \(\sigma^{\mathbb{Z}_p}(n) = n + 1 \bmod p\), \(m +^{\mathbb{Z}_p}n = m + n \bmod p\), and similarly for the other operations. For \(<\), we say that two numbers \(m\) and \(n\) less than \(p\) are related by \(<^{\mathbb{Z}_p}\) if \(m < n\). All variables are mapped to \(0\), say. Notice that, whether \(\mathbb{Z}_{p} \models \forall x \exists y (x = y + y)\) depends on the parity of \(p\). However, \(\mathbb{Z}_{p} \not\models \forall x (x < x + 1)\) (take \(x = p - 1\)).

For \(\mathbb{Z}_{p}\) it is relatively easy to find a sentence that differentiates it from \(\mathbb{Z}\). Unfortunately, there are more “stubborn” nonstandard models of number theory. We shall describe the simplest one, called \(\mathbb{N}'\), by defining only \(\sigma\) on it (the other ingredients of number theory can be defined in a compatible manner that we omit). The universe of \(\mathbb{N}'\) contains all nonnegative integers, and all complex numbers of the form \(n + mi\), where \(n\) and \(m\) are integers (positive, zero, or negative), and \(i = \sqrt{-1}\) is the imaginary unit. The successor function according to this nonstandard model maps a nonnegative integer \(n\) to \(n + 1\), and a complex integer \(n + mi\) to \((n + mi) + 1\). That is, the graph of the successor function, besides the usual half-line of nonnegative integers, contains now an infinity of parallel disjoint lines. As we said before, \(\mathbb{N}'\) is a very stubborn nonstandard model: We will show later that there is no set of first-order sentences that differentiates between \(\mathbb{N}\) and \(\mathbb{N}'\).

But one can think of models appropriate to \(\Sigma_{\mathbb{N}}\) that do not deal with numbers at all. For example, here is another “model of number theory,” called \(L\): The universe of \(L\) consists of \(2^{\{0,1\}^*}\), the set of all languages over the symbols \(0\) and \(1\). \(0^{L} = \varnothing\), the empty language. For any language \(\ell\), \(\sigma^{L}(\ell) = \ell^{*}\), where \(*\) denotes Kleene star. Also, \(+^{L}\) is union, \(\times^{L}\) is concatenation, and \(\uparrow^{L}\) is intersection. Finally, \(<^{L}\) is set inclusion (not necessarily proper). It so happens that \(L \models \forall x(x < x + 1)\). In proof, recall that \(1\) is a shorthand for \(\sigma(0)\), and \(\sigma^{L}(0^{L}) = \varnothing^{*} = \{\varepsilon\}\), where \(\varepsilon\) denotes an empty string. And it is true that, for any language \(x\), its union with \(\{\varepsilon\}\) (as with any other set) contains \(x\) as a subset. Therefore, for any language \(\ell \subseteq \{0,1\}^{*}\), \(L_{x = \ell}\models x < x + 1\), and thus \(L \models \forall x(x < x + 1)\).