In the previous post, Goodstein's Theorem, a statement about the properties of certain sequences of natural numbers, was proven using infinite ordinals. The use of a method "outside" arithmetic makes it reasonable that this proof cannot be encoded in the language of Peano Arithmetic (PA), the formal logical system for discussing the natural numbers. A stronger statement is also true: there is no proof of Goodstein's Theorem in PA because it cannot be deduced from the axioms of PA.
But how does one go about proving something unprovable? Certainly it is intractable to check every possible method, as the diversity of such attempts could be infinite. Mathematicians take a different approach, using tools from what is called model theory. In mathematical logic, a model of a collection of axioms is a specific structure within which the axioms (and all theorems derived from them) are interpreted to be true. Recall that the axioms of PA mentioned five specific objects, that were assumed to be given from the start: a set N, a specific member, 0, a function S from N to itself, and two binary operations on N, + and *. Of course, to actually do arithmetic we interpret N as the set of natural numbers, 0 as the number 0, S as the "successor" function taking in a number n and returning n+1, and + and * as the usual addition and multiplication. Until we provide an interpretation of to what these objects refer, namely a model, they are just symbols! We may prove statements about them, such as the fact that S(0) and S(S(0)) are distinct members of N, but this is just a mathematical sentence resulting as the end product of a series of formal deductive rules.
Any collection A = (NA,0A,SA,+A,*A) of a set NA, a member 0A of the set, a function SA:NA→NA, and two binary operations +A and *A that satisfies the axioms is a model of PA. Of course, we know fairly well what we mean by "natural numbers", namely {0,1,2,...} with 0 the first element, S sending 0 to 1, 1 to 2, etc, and the usual addition and multiplication. The entire point of selecting axioms for PA is to study ℕ = (N,0,S,+,*), the standard natural numbers. A natural question (called the question of categoricity) arises: is the standard model the only type of model for PA, or are there others? The answer is no; there are other, non-standard models A that still satisfy every axiom of PA. These were first discovered by Norwegian mathematician Thoralf Skolem in 1934. To be clear, they are not the natural numbers, at least, not as we intend them to be. Their existence exemplifies another limitation of first-order logic: axiom systems often fail to specify structures uniquely and hence fail to capture some features of the field to be studied.
Non-standard models often serve as an essential tool in independence proofs. First, we know from the previous post that the standard model ℕ of PA does satisfy Goodstein's Theorem (the standard model has the properties the natural numbers possess within the larger field of set theory, the methods of which were used in the proof). This means that the negation of Goodstein's Theorem cannot be a theorem of PA, since there is a model satisfying both the axioms and the theorem. If one could find a model of PA in which the negation of Goodstein's Theorem were true, then this would prove independence, because there would be models in which it is true and others in which it is false! Kirby and Paris used precisely this method in their 1982 proof of the result.
But what do non-standard models of natural numbers actually look like? First, we may infer what they have in common. PA axiom 1 guarantees the existence of a number 0. Axiom 2 gives it successors S(0), S(S(0)), etc. Axiom 3 says that S(n) = S(m) implies m = n. Therefore, all the successors generated from 0 are distinct from one another. This means that any model A has a set of natural numbers NA containing the analogues of 0, 1, 2, and so on. The set of standard natural numbers N is thus contained in NA for every A. The difference is that non-standard models have extra numbers!
At first brush, having additional "non-standard" numbers seems to contradict the Peano axioms, specifically the fifth, the axiom schema of induction. It states that if 0 has some property and that any n having the property implies that n + 1 does as well, then all natural numbers have the property. The spirit of this axiom schema, if not the letter, is that beginning at 0 and knocking down the inductive dominoes will eventually reach every natural number. If we could choose the property to be "is in the set {0,1,2,...} (the standard natural numbers N)" then this would immediately rule out nonstandard models: 0 is this set, and for any n in the set, its successor is also standard, so all of NA is contained in {0,1,2,...} and hence we would have NA = {0,1,2,...}. Unfortunately, it is impossible to define the set {0,1,2,...} inside of the first-order logic formulation. It is also impossible to simply add an axiom "there are no other numbers besides 0, 1, 2, etc." for the same reason. Both approaches require infinitely long logical sentences to formulate, which are forbidden in the finitary system of first-order logic.
Though the axioms of PA cannot rule out non-standard natural numbers, they are forced by the axioms to satisfy some strange conditions. Any nonstandard number c must be greater than all standard numbers. Further, PA can prove that 0 is the only number without a successor, so a "predecessor" to c, which we may call c - 1, must exist. Similarly, c - 2, c - 3, etc. must exist, as must, of course, c + 1, c + 2, etc. These must all be new non-standard numbers. Therefore, the existence of one non-standard number guarantees the existence of a whole non-standard "copy" of the integers: {...,c - 2,c - 1,c,c + 1,c + 2,...}. However, it gets much, much worse. The operation of addition is part of Peano Arithmetic, so there must be a number c + c, that may be proven to be greater than all numbers c + 1, c + 2, and so on. From here, we get another new infinite collection of non-standards {...,c + c - 2,c + c - 1,c + c,c + c + 1,c + c + 2,...}. A similar story occurs for c + c + c = c*3 and larger numbers as well, but we can also go in reverse. One can prove in PA that every number is either even or odd; that is, for any n, there is an m satisfying either m + m = n (if n is even), or m + m + 1 = n (if n is odd). This theorem means that c is even or odd, so there must be a smaller non-standard d with d + d = c or d + d + 1 = c. This d has its own infinite set of non-standard neighbors. The reader may continue this type of exercise and eventually derive the type of picture illustrated above: any non-standard model of natural numbers must contain the standard numbers plus (at least) an infinite number of copies of the integers, ℤ, one for each member of the set of rational numbers, ℚ.
As strange as these models are, they cannot be ruled out in PA, nor is there a natural addition to the axioms that may do so. Rather than being just a defect of first-order logic however, non-standard models are a useful tool for examining the structure of different theories. Now that we have a non-standard model at our disposal, it seems reasonable that Goodstein's Theorem should fail for some non-standard models: "Goodstein sequences" beginning at non-standard natural numbers do not seem likely to terminate at zero. After all, they have infinitely many copies of the integers to move around in! These sequences often cannot be computed explicitly, but using other logical machinery, one can prove the fact that they do not necessarily terminate. This establishes the independence of the theorem from PA.
Goodstein sequences, interesting in their own right for their rapid growth, allow an interesting perspective on Peano Arithmetic and its limitations. The questions of independence and non-standard models arise frequently in the foundations of mathematics, as we seek to define precisely the scope of our mathematical theories.
Sources: http://www.cs.tau.ac.il/~nachumd/term/Kirbyparis.pdf, http://blog.kleinproject.org/?p=674, http://www.ams.org/journals/proc/1983-087-04/S0002-9939-1983-0687646-0/S0002-9939-1983-0687646-0.pdf, http://settheory.net/model-theory/non-standard-arithmetic, http://www.columbia.edu/~hg17/nonstandard-02-16-04-cls.pdf, http://boolesrings.org/victoriagitman/files/2015/04/introToPAModels.pdf, http://lesswrong.com/lw/g0i/standard_and_nonstandard_numbers/
Hi,
ReplyDeleteThank you very much for the clear and concise explanation. I've been looking for this for a while.