Random Axioms and Gödel Incompleteness
Does adding random axioms to Peano Arithmetic make sense?
Giuseppe Peano is the creator of the standard axiomatization of the natural numbers, based on induction. He is also the discoverer of the space filling curve that is now named after him. One of his great contributions was to set up the notation that we now all use for many mathematical concepts.
Today Ken and I want to talk about a method for extending Peano Arithmetic that is based on randomness.
Kurt Gödel’s famous Incompleteness Theorem helped launch several different threads of research. It is not possible to build a formal system that can generate all and only the true statements about integers, whether one uses Peano’s system or others. There is always a true statement about integers that your system cannot prove. Some of the research threads concern the various forms and intuitive meanings that such statements can have, along lines we discussed initially and recently here. For example, the Liar Statement
“I am lying.”
has the following variation as a definition statement:
“The smallest positive integer not definable in under eleven words.”
Bertrand Russell attributed this type of statement to the Oxford University librarian Mr. G. Berry—after a long search I cannot find what “G” stands for. The statement seems to define an integer , but then is definable in ten words, contradicting its own definition.
Others have looked for more “natural” examples of true statements that Peano Arithmetic () cannot prove. Gödel’s Second Incompleteness Theorem shows that cannot prove its own consistency, which while a natural statement, is not one that a practicing mathematician usually thinks about. However, combinatorial principles like Ramsey’s Theorem are used in real proofs. Thus there was immense excitement when Jeff Paris and Leo Harrington proved that a slight modification of Ramsey’s Theorem cannot be proved in . The eminent logician Harvey Friedman has shown there are many other striking examples of combinatorial principles that lie beyond –some even require the vast power of large cardinal axioms of set theory.
Another thread is the search for new axioms that can be added to or set theory that increase its power, allowing more theorems to be provable. No additional axioms can escape incompleteness and preserve consistency, but new axioms can expand the set of provable true sentences. One simple method is to add the statement, formalized in :
The resulting theory is obviously more powerful than , and this can even be iterated.
What I plan to discuss today is a different type of axiom that can be added to . They are based on the use of randomness, where I mean real randomness. The source of random bits used in this method must be really random, not pseudo-random. Even pseudo-randomness in a very strong sense will not work in this approach.
The famous mathematician Andrey Kolmogorov created many wonderful notions, among them the notion of Kolmogorov Complexity. There are many technical variants of this notion, but we will define it informally and then fix one.
Informally, given any string , define to be the shortest length of a “seed” string that when “expanded” yields . The expansion is deterministic, so it follows immediately that not all strings of length can have seeds of length . That is, for all there exist strings such that .
If the strings use a binary alphabet, we can be even more particular about possible values of . For every , at most of the strings of length can have . Thus with probability at least , flipping coins will produce a string with . For a suitable choice of , we call such a string algorithmically random. Note a subtle philosophical contrast:
- A string that results from flipping coins is “random” as an outcome; while
- A string with is intrinsically random.
To make this point specific we have to choose a fixed notion of expansion—i.e., a fixed program such that . Kolmogorov himself proved that any universal Turing machine or programming-language interpreter can be used for the theory: the choice between particular matters only up to an additive constant in the value of any string. Since we ultimately intend to be a non-constant function such as , any such constant will be asymptotically dominated. Still, we carry an additive slack term in our formulas below. Efforts to minimize and related constants via a “concrete definition of Kolmogorov complexity” have been led by John Tromp here. We will assume such an implementation.
Note also that any provides a fixed prefix “quote” string such that always expands to give and we may suppose . Thus with regard to , always . If we are ignoring plus-or-minus differences, then algorithmically random strings are those with Kolmogorov complexity between and . With freedom to set so that the error will be small enough to meet the probability requirements of our constructions below, we can state the above as: A random string is intrinsically random.
For any we imagine flipping really random coins and creating the string of bits
is likely to be true with probability at least . Call this statement . Our plan is to add many such statements to . We want to add as many as possible, but we also want the resulting theory to have a good probability of being not only consistent but also sound. Soundness here means that every theorem, and a-priori every axiom, must be true. The simple idea is to add axioms
so that the probability that all of these axioms are true is at least , for some given .
If we desire an axiom for every length , it suffices to take for some customizable constant . Then the probability that some axiom is false is at most
We can improve the odds even more by taking to be a sparse sequence of lengths. Whatever choice is made, clearly there exists a sound theory with infinitely many of these axioms—and moreover we have defined an infinite coin-flipping process that has a good chance of obtaining one. Call the theory .
A Note on Defining the Axioms
One issue with is that the set of new axioms is not, indeed cannot be, recursively enumerable. This is a consequence of Gregory Chaitin’s theorem, which Wikipedia here mentions as a kind of Gödel-incompleteness statement related to Berry’s paradox. Once we have chosen the program , we can formalize the predicate
in PA or in any formal system that is rich enough to include arithmetic. Chaitin’s theorem then states:
Theorem: A sound formal system with a recursively enumerable axiom set can prove statements of the form for only finitely many . In particular, there is a length such that the system cannot prove that any string with is algorithmically random.
The particular can be viewed as a finite limit on the amount of information that the formal system can “comprehend”—which is essentially the amount of information in its axioms to begin with, more precisely, the amount of information in the program that recursively enumerates them.
It follows that every infinite r.e. set must contain some strings such that is false, where and is as above. Otherwise would give us an r.e. set of axioms for a theory that contradicts Chaitin’s theorem. Thus our set of new axioms for cannot be r.e. It can be co-r.e., however. Thus while our point has been to picture as a “random” theory, it can instead be viewed as a particular subset of True Arithmetic, which has recently been discussed on MathOverflow here.
The main issue is: what is the power of the theory ? Since the it is not one theory, but many theories, we must be careful what we mean by saying that can prove a sentence . Thus we are restricted to statements like:
Let’s denote this by . Indeed let’s take , but other values are fine too.
Clearly will hold for many statements that cannot be proved by , provided it is consistent. This is clear and follows directly from Chaitin’s theorem. The main question, therefore, is this: What “new” statements can be proved now? More precisely, how can we characterize the statements so that ?
It seems that there are two extremes. One is that the new statements are really just statements about the Kolmogorov complexity of strings. If this is all that is added, then the theory is pretty uninteresting, as are all the variants with different values of .
The other extreme is that there are interesting new theorems that are provable by . Could the consistency of be proved, or some other interesting sentences? We do not know.
Cristian Calude has corresponded with us on an earlier form of this topic. His opinion can be summarized by saying that can only prove that certain strings are random. In particular, he does not believe that they can be used to prove the statement asserting that itself, without the new axioms, is consistent.
What interesting statements, if any, are provable in a fixed sound theory with randomness axioms . Or provable with reasonably high probability in a theory with such axioms chosen by random coin flips?