Models of Arithmetic

Definition of a standard arithmetic structure

A structure for $\Lang{L_A}$source is standard if it is isomorphic to $\Struct{N}$source.

Standard structures are exhausted by numeral values

If a structure $\Struct{M}$source is standard, then its domain is the set of values of the standard numerals, i.e.,

Proof

Clearly, every $\Value{\num{n}}{M} \in \Domain{M}$source. We just have to show that every $x \in \Domain{M}$source is equal to $\Value{\num{n}}{M}$source for some $n$source. Since $\Struct{M}$source is standard, it is isomorphic to $\Struct{N}$source. Suppose $g\colon \Nat \to \Domain{M}$source is an isomorphism. Then $g(n) = g(\Value{\num{n}}{N}) = \Value{\num{n}}{M}$source. But for every $x \in \Domain{M}$source, there is an $n \in \Nat$source such that $g(n) = x$source, since $g$source is surjective.

Explain

If a structure $\Struct{M}$source for $\Lang{L_A}$source is standard, the elements of its domain can all be named by the standard numerals $\num{0}$source, $\num{1}$source, $\num{2}$source, dots, i.e., the terms $\Obj{0}$source, $\Obj{0}'$source, $\Obj{0}''$source, etc. Of course, this does not mean that the elements of $\Domain{M}$source are the numbers, just that we can pick them out the same way we can pick out the numbers in $\Domain{N}$source.

Exercise on the converse domain claim

Show that the converse of reference prop:standard-domain is false, i.e., give an example of a structure $\Struct{M}$source with $\Domain{M} = \Setabs{\Value{\num{n}}{M}}{n \in \Nat}$source that is not isomorphic to $\Struct{N}$source.

A numeral-generated model of Q is standard

If $\Sat{M}{\Th{Q}}$source, and $\Domain{M} = \Setabs{\Value{\num{n}}{M}}{n \in \Nat}$source, then $\Struct{M}$source is standard.

Proof

We have to show that $\Struct{M}$source is isomorphic to $\Struct{N}$source. Consider the function $g\colon \Nat \to \Domain{M}$source defined by $g(n) = \Value{\num{n}}{M}$source. By the hypothesis, $g$source is surjective. It is also injective: $\Th{Q} \Proves \eq/[\num{n}][\num{m}]$source whenever $n \neq m$source. Thus, since $\Sat{M}{\Th{Q}}$source, $\Sat{M}{\eq/[\num{n}][\num{m}]}$source, whenever $n \neq m$source. Thus, if $n \neq m$source, then $\Value{\num{n}}{M} \neq \Value{\num{m}}{M}$source, i.e., $g(n) \neq g(m)$source.

We also have to verify that $g$source is an isomorphism.

1. We have $g(\Assign{\Obj{0}}{N}) = g(0)$source since, $\Assign{\Obj{0}}{N} = 0$source. By definition of $g$source, $g(0) = \Value{\num{0}}{M}$source. But $\num{0}$source is just $\Obj{0}$source, and the value of a term which happens to be a constant symbol is given by what the structure assigns to that constant symbol, i.e., $\Value{\Obj{0}}{M} = \Assign{\Obj{0}}{M}$source. So we have $g(\Assign{\Obj{0}}{N}) = \Assign{\Obj{0}}{M}$source as required.

2. $g(\Assign{\prime}{N}(n)) = g(n+1)$source, since $\prime$source in $\Struct{N}$source is the successor function on $\Nat$source. Then, $g(n+1) = \Value{\num{n+1}}{M}$source by definition of $g$source. But $\num{n+1}$source is the same term as $\num{n}'$source, so $\Value{\num{n+1}}{M} = \Value{\num{n}'}{M}$source. By the definition of the value function, this is $= \Assign{\prime}{M}(\Value{\num{n}}{M})$source. Since $\Value{\num{n}}{M} = g(n)$source we get $g(\Assign{\prime}{N}(n)) = \Assign{\prime}{M}(g(n))$source.

3. $g(\Assign{+}{N}(n,m)) = g(n+m)$source, since $+$source in $\Struct{N}$source is the addition function on $\Nat$source. Then, $g(n+m) = \Value{\num{n+m}}{M}$source by definition of $g$source. But $\Th{Q} \Proves \num{n+m} = (\num{n} + \num{m})$source, so $\Value{\num{n+m}}{M} = \Value{\num{n}+\num{m}}{M}$source. By the definition of the value function, this is $= \Assign{+}{M}(\Value{\num{n}}{M},\Value{\num{m}}{M})$source. Since $\Value{\num{n}}{M} = g(n)$source and $\Value{\num{m}}{M} = g(m)$source, we get $g(\Assign{+}{N}(n, m)) = \Assign{+}{M}(g(n), g(m))$source.

4. $g(\Assign{\times}{N}(n, m)) = \Assign{\times}{M}(g(n), g(m))$source: Exercise.

5. $\tuple{n,m} \in \Assign{<}{N}$source iff $n < m$source. If $n < m$source, then $\Th{Q} \Proves \num{n} < \num{m}$source, and also $\Sat{M}{\num{n} < \num{m}}$source. Thus $\tuple{\Value{\num{n}}{M}, \Value{\num{m}}{M}} \in \Assign{<}{M}$source, i.e., $\tuple{g(n), g(m)} \in \Assign{<}{M}$source. If $n \not< m$source, then $\Th{Q} \Proves \lnot \num{n} < \num{m}$source, and consequently $\Sat/{M}{\num{n} < \num{m}}$source. Thus, as before, $\tuple{g(n), g(m)} \notin \Assign{<}{M}$source. Together, we get: $\tuple{n,m} \in \Assign{<}{N}$source iff $\tuple{g(n), g(m)} \in \Assign{<}{M}$source.

Explain

The function $g$source is the most obvious way of defining a mapping from $\Nat$source to the domain of any other structure $\Struct{M}$source for $\Lang{L_A}$source, since every such $\Struct{M}$source contains elements named by $\num{0}$source, $\num{1}$source, $\num{2}$source, etc. So it isn't surprising that if $\Struct{M}$source makes at least some basic statements about the $\num{n}$source's true in the same way that $\Struct{N}$source does, and $g$source is also bijective, then $g$source will turn into an isomorphism. In fact, if $\Domain{M}$source contains no elements other than what the $\num{n}$source's name, it's the only one.

Uniqueness of the standard isomorphism

If $\Struct{M}$source is standard, then $g$source from the proof of reference prop:thq-standard is the only isomorphism from $\Struct{N}$source to $\Struct{M}$source.

Proof

Suppose $h\colon \Nat \to \Domain{M}$source is an isomorphism between $\Struct{N}$source and $\Struct{M}$source. We show that $g = h$source by induction on $n$source. If $n = 0$source, then $g(0) = \Assign{\Obj{0}}{M}$source by definition of $g$source. But since $h$source is an isomorphism, $h(0) = h(\Assign{\Obj{0}}{N}) =\Assign{\Obj{0}}{M}$source, so $g(0) = h(0)$source.

Now consider the case for $n+1$source. We have

Explain

For any denumerable set $M$source, there's a bijection between $\Nat$source and $M$source, so every such set $M$source is potentially the domain of a standard model $\Struct{M}$source. In fact, once you pick an object $z \in M$source and a suitable function $s$source as $\Assign{\Obj{0}}{M}$source and $\Assign{\prime}{M}$source, the interpretations of $+$source, $\times$source, and $<$source is already fixed. Only functions $s\colon M \to M \setminus \{z\}$source that are both injective and surjective are suitable in a standard model as $\Assign{\prime}{M}$source. The range of $s$source cannot contain $z$source, since otherwise $\lforall[x][\eq/[\Obj 0][x']]$source would be false. That sentence is true in $\Struct{N}$source, and so $\Struct{M}$source also has to make it true. The function $s$source has to be injective, since the successor function $\Assign{\prime}{N}$source in $\Struct{N}$source is, and that $\Assign{\prime}{N}$source is injective is expressed by a sentence true in $\Struct{N}$source. It has to be surjective because otherwise there would be some $x \in M \setminus \{z\}$source not in the domain of $s$source, i.e., the sentence $\lforall[x][(\eq[x][\Obj 0] \lor \lexists[y][\eq[y'][x]])]$source would be false in $\Struct{M}$source---but it is true in $\Struct{N}$source.

Explain

We call a structure for $\Lang{L_A}$source standard if it is isomorphic to $\Struct{N}$source. If a structure isn't isomorphic to $\Struct{N}$source, it is called non-standard.

Definition of standard and nonstandard numbers

A structure $\Struct{M}$source for $\Lang{L_A}$source is non-standard if it is not isomorphic to $\Struct{N}$source. The elements $x \in \Domain{M}$source which are equal to $\Value{\num{n}}{M}$source for some $n \in \Nat$source are called standard numbers (of $\Struct{M}$source), and those not, non-standard numbers.

Explain

By reference prop:standard-domain, any standard structure for $\Lang{L_A}$source contains only standard elements. Consequently, a non-standard structure must contain at least one non-standard element. In fact, the existence of a non-standard element guarantees that the structure is non-standard.

A nonstandard element forces a nonstandard structure

If a structure $\Struct{M}$source for $\Lang{L_A}$source contains a non-standard number, $\Struct{M}$source is non-standard.

Proof

Suppose not, i.e., suppose $\Struct{M}$source standard but contains a non-standard number $x$source. Let $g\colon \Nat \to \Domain{M}$source be an isomorphism. It is easy to see (by induction on $n$source) that $g(\Value{\num{n}}{N}) = \Value{\num{n}}{M}$source. In other words, $g$source maps standard numbers of $\Struct{N}$source to standard numbers of $\Struct{M}$source. If $\Struct{M}$source contains a non-standard number, $g$source cannot be surjective, contrary to hypothesis.

Exercise separating the first three Q axioms

Recall that $\Th{Q}$source contains the axioms

Give structures $\Struct{M_1}$source, $\Struct{M_2}$source, $\Struct{M_3}$source such that

1. $\Sat{M_1}{!Q_1}$source, $\Sat{M_1}{!Q_2}$source, $\Sat/{M_1}{!Q_3}$source;

2. $\Sat{M_2}{!Q_1}$source, $\Sat/{M_2}{!Q_2}$source, $\Sat{M_2}{!Q_3}$source; and

3. $\Sat/{M_3}{!Q_1}$source, $\Sat{M_3}{!Q_2}$source, $\Sat{M_3}{!Q_3}$source;

Obviously, you just have to specify $\Assign{\Obj{0}}{M_i}$source and $\Assign{\prime}{M_i}$source for each.

Explain

It is easy enough to specify non-standard structures for $\Lang{L_A}$source. For instance, take the structure with domain $\Int$source and interpret all non-logical symbols as usual. Since negative numbers are not values of $\num{n}$source for any $n$source, this structure is non-standard. Of course, it will not be a model of arithmetic in the sense that it makes the same sentences true as $\Struct{N}$source. For instance, $\lforall[x][\eq/[x'][\Obj{0}]]$source is false. However, we can prove that non-standard models of arithmetic exist easily enough, using the compactness theorem.

True arithmetic has an enumerable nonstandard model

Let $\Th{TA} = \Setabs{!A}{\Sat{N}{!A}}$source be the theory of $\Struct{N}$source. $\Th{TA}$source has an enumerable non-standard model.

Proof

Expand $\Lang{L_A}$source by a new constant symbol $c$source and consider the set of sentences

Any model $\Struct{M^c}$source of $\Gamma$source would contain an element $x = \Assign{c}{M}$source which is non-standard, since $x \neq \Value{\num{n}}{M}$source for all $n \in \Nat$source. Also, obviously, $\Sat{M^c}{\Th{TA}}$source, since $\Th{TA} \subseteq \Gamma$source. If we turn $\Struct{M^c}$source into a structure $\Struct{M}$source for $\Lang{L_A}$source simply by forgetting about $c$source, its domain still contains the non-standard $x$source, and also $\Sat{M}{\Th{TA}}$source. The latter is guaranteed since $c$source does not occur in $\Th{TA}$source. So, it suffices to show that $\Gamma$source has a model.

We use the compactness theorem to show that $\Gamma$source has a model. If every finite subset of $\Gamma$source is satisfiable, so is $\Gamma$source. Consider any finite subset $\Gamma_0 \subseteq \Gamma$source. $\Gamma_0$source includes some sentences of $\Th{TA}$source and some of the form $\eq/[c][\num{n}]$source, but only finitely many. Suppose $k$source is the largest number so that $\eq/[c][\num{k}] \in \Gamma_0$source. Define $\Struct{N_k}$source by expanding $\Struct{N}$source to include the interpretation $\Assign{c}{N_k} = k+1$source. $\Sat{N_k}{\Gamma_0}$source: if $!A \in \Th{TA}$source, $\Sat{N_k}{!A}$source since $\Struct{N_k}$source is just like $\Struct{N}$source in all respects except $c$source, and $c$source does not occur in $!A$source. And $\Sat{N_k}{\eq/[c][\num{n}]}$source, since $n \le k$source, and $\Value{c}{N_k} = k+1$source. Thus, every finite subset of $\Gamma$source is satisfiable.

Explain

We know that there are non-standard structures that make the same sentences true as $\Struct{N}$source does, i.e., is a model of $\Th{TA}$source. Since $\Sat{N}{\Th{Q}}$source, any model of $\Th{TA}$source is also a model of $\Th{Q}$source. $\Th{Q}$source is much weaker than $\Th{TA}$source, e.g., $\Th{Q} \Proves/ \lforall[x][\lforall[y][\eq[(x + y)][(y+x)]]]$source. Weaker theories are easier to satisfy: they have more models. E.g., $\Th{Q}$source has models which make $\lforall[x][\lforall[y][\eq[(x + y)][(y+x)]]]$source false, but those cannot also be models of $\Th{TA}$source, or $\Th{PA}$source for that matter. Models of $\Th{Q}$source are also relatively simple: we can specify them explicitly.

Example of the K model of Q

Consider the structure $\Struct{K}$source with domain $\Domain{K} = \Nat \cup \{a\}$source and interpretations

To show that $\Sat{K}{\Th{Q}}$source we have to verify that all axioms of $\Th{Q}$source are true in $\Struct{K}$source. For convenience, let's write $x^\nssucc$source for $\Assign{\prime}{K}(x)$source (the “successor” of $x$source in $\Struct{K}$source), $x \nsplus y$source for $\Assign{+}{K}(x, y)$source (the “sum” of $x$source and $y$source in $\Struct{K}$source, $x \nstimes y$source for $\Assign{\times}{K}(x, y)$source (the “product” of $x$source and $y$source in $\Struct{K}$source), and $x \nsless y$source for $\tuple{x,y} \in \Assign{<}{K}$source. With these abbreviations, we can give the operations in $\Struct{K}$source more perspicuously as

We have $n \nsless m$source iff $n<m$source for $n$source, $m \in \Nat$source and $x \nsless a$source for all $x \in \Domain{K}$source.

$\Sat{K}{\lforall[x][\lforall[y][(\eq[x'][y'] \lif \eq[x][y])]]}$source since $\nssucc$source is injective. $\Sat{K}{\lforall[x][\eq/[\Obj 0][x']]}$source since $0$source is not a $\nssucc$source-successor in $\Struct{K}$source. $\Sat{K}{\lforall[x][(\eq[x][\Obj 0] \lor \lexists[y][\eq[x][y']])]}$source since for every $n>0$source, $n = (n-1)^\nssucc$source, and $a = a^\nssucc$source.

$\Sat{K}{\lforall[x][\eq[(x + \Obj 0)][x]]}$source since $n \nsplus 0 = n+0 = n$source, and $a\nsplus 0 = a$source by definition of $\nsplus$source. $\Sat{K}{\lforall[x][\lforall[y][\eq[(x + y')][(x + y)']]]}$source is a bit trickier. If $n$source, $m$source are both standard, we have:

This is of course a bit more detailed than needed. For instance, since $a \nsplus z = a$source whatever $z$source is, we can immediately conclude $a \nsplus a^\nssucc = a$source. The remaining axioms can be verified the same way.

$\Struct{K}$source is thus a model of $\Th{Q}$source. Its “addition” $\nsplus$source is also commutative. But there are other sentences true in $\Struct{N}$source but false in $\Struct{K}$source, and vice versa. For instance, $a \nsless a$source, so $\Sat{K}{\lexists[x][x < x]}$source and $\Sat/{K}{\lforall[x][\lnot x<x]}$source. This shows that $\Th{Q} \Proves/ \lforall[x][\lnot x < x]$source.

Exercise completing the verification of K

Prove that $\Struct{K}$source from reference ex:model-K-of-Q satisfies the remaining axioms of $\Th{Q}$source,

Find a sentence only involving $\prime$source true in $\Struct{N}$source but false in $\Struct{K}$source.

Example of the L model of Q

Consider the structure $\Struct{L}$source with domain $\Domain{L} = \Nat \cup \{a, b\}$source and interpretations $\Assign{\prime}{L} = \nssucc$source, $\Assign{+}{L} = \nsplus$source given by

Since $\nssucc$source is injective, $0$source is not in its range, and every $x \in \Domain{L}$source other than $0$source is, axioms $!Q_1$source--$!Q_3$source are true in $\Struct{L}$source. For any $x$source, $x \nsplus 0 = x$source, so $!Q_4$source is true as well. For $!Q_5$source, consider $x \nsplus y^\nssucc$source and $(x \nsplus y)^\nssucc$source. They are equal if $x$source and $y$source are both standard, since then $\nssucc$source and $\nsplus$source agree with $\prime$source and $+$source. If $x$source is non-standard, and $y$source is standard, we have $x \nsplus y^\nssucc = x = x^\nssucc = (x \nsplus y)^\nssucc$source. If $x$source and $y$source are both non-standard, we have four cases:

So, $\Sat{L}{!Q_5}$source. However, $a \nsplus 0 \neq 0 \nsplus a$source, so $\Sat/{L}{\lforall[x][\lforall[y][\eq[(x+y)][(y+x)]]]}$source.

Exercise expanding L to a full model of Q

Expand $\Struct{L}$source of reference ex:model-L-of-Q to include $\nstimes$source and $\nsless$source that interpret $\times$source and $<$source. Show that your structure satisfies the remaining axioms of $\Th{Q}$source,

Exercise on a two-cycle successor

In $\Struct{L}$source of reference ex:model-L-of-Q, $a^\nssucc = a$source and $b^\nssucc = b$source. Is there a model of $\Th{Q}$source in which $a^\nssucc = b$source and $b^\nssucc = a$source?

Explain

We've explicitly constructed models of $\Th{Q}$source in which the non-standard elements live “beyond” the standard elements. In fact, that much is required by the axioms. A non-standard element $x$source cannot be ${} \nsless 0$source, since $\Th{Q} \Proves \lforall[x][\lnot x<0]$source (see reference lem:less-zero). Also, for every $n$source, $\Th{Q} \Proves \lforall[x][(x < \num{n}' \lif (\eq[x][\num{0}] \lor \eq[x][\num{1}] \lor \dots \lor \eq[x][\num{n}]))]$source (reference lem:less-nsucc), so we can't have $a \nsless n$source for any $n>0$source.

Explain

Any non-standard model of $\Th{TA}$source is also one of $\Th{PA}$source. We know that non-standard models of $\Th{TA}$source and hence of $\Th{PA}$source exist. We also know that such non-standard models contain non-standard “numbers,” i.e., elements of the domain that are “beyond” all the standard “numbers.” But how are they arranged? How many are there? We've seen that models of the weaker theory $\Th{Q}$source can contain as few as a single non-standard number. But these simple structures are not models of $\Th{PA}$source or $\Th{TA}$source.

The key to understanding the structure of models of $\Th{PA}$source or $\Th{TA}$source is to see what facts are derivable in these theories. For instance, already $\Th{PA}$source proves that $\lforall[x][\eq/[x][x']]$source and $\lforall[x][\lforall[y][\eq[(x+y)][(y+x)]]]$source, so this rules out simple structures (in which these sentences are false) as models of $\Th{PA}$source.

Suppose $\Struct{M}$source is a model of $\Th{PA}$source. Then if $\Th{PA} \Proves !A$source, $\Sat{M}{!A}$source. Let's again use $\nszero$source for $\Assign{\Obj{0}}{M}$source, $\nssucc$source for $\Assign{\prime}{M}$source, $\nsplus$source for $\Assign{+}{M}$source, $\nstimes$source for $\Assign{\times}{M}$source, and $\nsless$source for $\Assign{<}{M}$source. Any sentence $!A$source then states some condition about $\nszero$source, $\nssucc$source, $\nsplus$source, $\nstimes$source, and $\nsless$source, and if $\Sat{M}{!A}$source that condition must be satisfied. For instance, if $\Sat{M}{!Q_1}$source, i.e., $\Sat{M}{\lforall[x][\lforall[y][(\eq[x'][y'] \lif \eq[x][y])]]}$source, then $\nssucc$source must be injective.

The interpreted order in a model of PA

In $\Struct{M}$source, $\nsless$source is a linear strict order, i.e., it satisfies:

1. Not $x \nsless x$source for any $x \in \Domain{M}$source.

2. If $x \nsless y$source and $y \nsless z$source then $x \nsless z$source.

3. For any $x \neq y$source, $x \nsless y$source or $y \nsless x$source