An iPhone app for a nonstandard model of number theory?
This is a talk at the City Tech C-LAC (Center for Logic, Algebra, and Computation) Seminar, February 14, 2012.
Slides
A rigorous study of number theory, the properties of the natural numbers under the operations of addition and multiplication and the usual ordering, began more than two millenia ago in ancient Greece.
But it was only in the late 19th century that the first explicit axiomatization for it was proposed by Giuseppe Peano. Reinterpreted in first-order logic, the generally accepted language of formal mathematics formulated in the early 20th century by Thoralf Skolem, the Peano axioms consisted of two lists. The first finite list summarized the fundamental properties of addition, multiplication, and the ordering. The second infinite list consisted of induction axioms for every first-order definable number theoretic property. Because first-order logic does not allow quantification over properties, expressing induction required an infinite list. Could anything else besides the natural numbers possibly satisfy the Peano axioms? The answer came from several fundamental results about first-order logic established in the 1930's. In 1931, Kurt Gödel proved the first incompleteness theorem showing that there is a true number theoretic property that is not provable from the Peano axioms. A model of the Peano axioms together with the negation of such a property had to be different from the natural numbers. An even stranger result already followed from Gödel's countable compactness theorem (1930) showing that any collection of first-order properties in a countable language, whose every finite subset has a model, has a countable model. Using the countable compactness theorem, we can show that for every infinite binary sequence $s$, there is a countable model of ALL true number theoretic properties that has an element that is divisible by the $n^{\text{th}}$ prime number if and only if the $n^{\text{th}}$ digit of $s$ is $1$. Yes, there are models of number theory with elements divisible by infinitely many primes! Finally, once Anatoly Maltsev proved the uncountable version of the compactness theorem, it followed that there are models of the Peano axioms (even of all true number theoretic properties) of every infinite cardinality. Unintuitive as it may seem, there are uncountable models of number theory. We call the natural numbers the standard model of the Peano axioms and all these other models nonstandard.
Wouldn't it be nice to actually construct a nonstandard model of number theory? In other words, does there exist an algorithms to compute the addition and multiplication of some such model? Well, first off, does there exist an algorithm to compute the addition and multiplication on the natural numbers? Of course, without it there would be no debate in education circles about the use of calculators in the classroom. And, of course, there is an iPhone app for it as well. Almost. A calculator or an iPhone app or any other computing device can only add and multiply numbers up to whatever size is allowed by its memory capacity. But let's all be theoreticians here and suppose that our computing devices do have infinite memory as in the Turing model. So can we have an iPhone app for a nonstandard model of the Peano axioms (allowing for infinite memory)? Is the question even meaningful? Computers manipulate numbers and elements of a nonstandard models are not numbers. But that is easily addressed since if the nonstandard model is countable we might as well assume for all intents and purposes that its elements are numbers. After all that's what allows computers to manipulate all other objects that are not numbers such as text, images, etc. So a more precise formulation of the question becomes: is there a countable nonstandard model of the Peano axioms and a way to associate its elements with the natural numbers so that we can write an algorithm to calculate the nonstandard operations of addition and multiplication for it?
In 1959, Stanley Tennenbaum showed that the answer is NO! It is simply not possible to get our hands on a nonstandard model of the Peano axioms. Put broadly (vaguely) the reason is that any nonstandard model of the Peano axioms codes information that cannot be accessed algorithmically. These creatures are too complex for those limited hands of ours. This is not to imply that we cannot study the properties of these truly fascinating structures, a thriving field of research of which I am a proud member. It is just that we can never have an iPhone app for one.
In this talk, I will outline the background and the proof of Tennenbaum's theorem.
