I have already written about it being impossible to create a single fixed nonrandom computer program for determining the correctness of all existing software or future software.[1] One consequence is that antivirus software can never be perfect. So at a given time, we can’t know which software is correct out of all existing software, whether the procedure to check the software is correct, or whether we caught all the viruses that might be infecting a given computer. Yes, there’s logical computer stuff that is theoretically unknowable. With computer technology being a human invention, maybe we can find some comfort in math, which is thought to be universal. But don’t get your hopes up too much.
People say that math is the language of science, which is basically our current understanding of how things work. Both are backed by logic. We might reasonably expect to be able to logically prove all true statements and disprove all false statements that occur in math. We don’t have to start with the most complex math. Instead, suppose we start with a simple group of numbers, the counting numbers, as in 1, 2 3, up towards infinity. Though counting numbers are more properly known as natural numbers or positive integers, the less typical name of counting numbers emphasizes their simplicity. Surprisingly, there’s enough knowledge available about counting numbers that they are the focus of a branch of math called number theory.[2] Still, they’re just counting numbers. Even a young child knows something about counting.
But, no, we can’t know everything about counting numbers either. In 1931, Kurt Godel published his two incompleteness theorems.[3] The first says that a system of logical statements that is sophisticated enough to contain number theory cannot be both complete and consistent. If the system is consistent, then it contains true statements about number theory that cannot be proved true within that system. It may be possible to prove such statements by using math outside of number theory, however. The second incompleteness theorem says that a system with that level of complexity cannot be used to show its own consistency.
Granted there are several technical details that make these incompleteness theorems seem too obscure to apply to the real world. A system described by these theorems is a set of logical axioms, along with all statements that have been logically derived from those axioms. Axioms are statements that are accepted as true without proof. These particular axioms are expressed in some special formal language, composed of special symbols instead of English words. The derived statements are in that same language. This language of course has its own rules for forming valid sentences. Furthermore it must be possible to generate the axioms of the system as if by a computer algorithm. In my opinion, this seems like a lot of dependence on symbols and structure. So maybe this is really just a limitation of abstract symbol-processing systems.
What is even meant by consistent or complete? In the current context, the term consistent means there are no contradictions within the system. So between the axioms and the statements derived from them, none of them contradict any others. The system is complete if each possible statement in the special language of the system can be proved either true or false in the system. The first incompleteness theorem is saying we can’t have both. Again, this is for manipulating symbols, not necessarily their meaning. The second theorem says that the consistency of the system cannot be proved from the system itself, and it took me a while to realize that this is literally true, not just a vague summary.
The proof of these incompleteness theorems is worth discussing, to better understand what they actually say. How exactly did Godel prove that a system of logic that includes number theory can’t be both complete and consistent? For starters, he coded the various parts of theorems as counting numbers, using a numbering system called Godel numbering.[4] Prime numbers are combined with simple math in a way that guarantees their uniqueness is not lost. A prime number is of course a counting number with no counting-number factors other than itself and one. I’m assuming that being able to encode logic in such a way with counting numbers, is what connects the incompleteness theorems with number theory.
The other key is using a form of the “liar’s paradox,” which has a few well-known variations like the sentence “this sentence is false” or a person saying “I am a liar”.[5] Such a statement can be neither true nor false. In my limited understanding, Godel reportedly used statements roughly equivalent to “this statement is not provable.” If that group of statements is proved, which shows it is true, it is true that it is not provable, which was just demonstrated as false. So it cannot be both proven and true. Encoding such statements with Godel numbering, apparently helped to force a choice between completeness and consistency.
I’ll admit, I feel like using the liar’s paradox is cheating. After all, what can the liar’s paradox really tell us about counting numbers? Reportedly, these incompleteness theorems show that math cannot be fully described by a set of axioms and statements derived from them. in a formal logic system such as described earlier. Maybe number theory is the tipping point for no longer being able to fully automate reasoning. But part of me suspects there’s something wrong with the approach. In his book Godel, Escher, Bach, Douglas Hofstadter proposes that having to choose between consistency and completeness really demonstrates a mismatch between the syntax (the symbolic structure) and the semantics (the underlying meaning).[6] Modern philosopher Steve Patterson suggests the liar’s paradox boils down to just linguistic errors (problems with the use of language – English in that case).[7]
While the incompleteness theorems may involve some trickery, maybe they still actually tell us something. The statements in the system are encoded as counting numbers after all, and so those statements that reference themselves still end up being about numbers. So, yes, there are apparently true things being said about number theory that can’t be proved. What exactly is being said about numbers that is unprovable, I don’t yet know.
Are Godel’s incompleteness theorems applicable only to formal systems? Yes and no. The theorems do apply to formal systems. But the formal language of such a formal system could be sophisticated enough to describe the structure of enough natural language (like English), as used in axioms and theorems about number theory. Then the incompleteness theorems could possibly apply to what might be seen in a research paper about number theory. So in my understanding they can apply to number theory statements in the “real world.”
But do we care if there are obscure theorems about number theory that can’t be proved? A system that contains number theory may of course be more complex than number theory. If we encode the axioms and statements with more sophisticated math like differential calculus, maybe we could end up with true unprovable statements about differential calculus. Then the incompleteness theorems can potentially affect science and engineering as well. At any rate, math has some statements that are true but unprovable. If we consider math knowledge to contain only axioms and what we can prove from them, then there are statements in math that are not knowable in that sense. Worse, in a situation where the group of statements that is causing the contradiction obscures their connection to the liar’s paradox, we may not yet know what we can or can’t know.
References
[1] https://oddstem.com/2019/08/28/the-logically-unknowable-part-1/
[2] https://www.britannica.com/science/number-theory
[3] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems
[4] https://plato.stanford.edu/entries/goedel-incompleteness/sup1.html
[5] https://rationalwiki.org/wiki/Liar_paradox
[6] Hofstadter . Douglas R. Godel Escher Bach: An Eternal Golden Braid. New York: Vintage Books, 1989. Newer edition found at Basic Books: https://www.basicbooks.com/titles/douglas-r-hofstadter/godel-escher-bach/9780465026562/
[7] http://steve-patterson.com/resolving-the-liars-paradox/
(c) Copyright 2019 by Mike Ferrel
l
Odd STEM 