Reflections upon Incompleteness, by Rebecca Goldstein
The incompleteness theorem: a mathematical result that had effects that rippled across the world. Kurt Godel was born in 1906, in what is now the Czech republic. In 1923, he matriculated to the University of Vienna, in hopes of becoming a physicist. But, he decided to switch to logic as his subject of study. While in Vienna, Godel became a member of the influential group of thinkers, known as the Vienna Circle or the Schlick circle. Godel did not agree with all the ideas of the circle, the positivist ideas (something that will be explained later). So, Godel set out to prove the members of the Circle wrong, and in doing so, shed metalight (self-referential understanding) on the entire field of mathematics. He did this through his first Incompleteness theorem, which among other things, provided for the existence of undecidability propositions. The meaning of the incompleteness theorem, and its proof, will briefly be explained later. In 1931, when Godel was only twenty-five, he published his paper containing the proof of the incompleteness theorem, establishing his reputation as a logical maven. Godel stayed in Vienna as an unpaid lecturer, surprisingly, until 1940, when he had to flee from the Nazis to America. He was not Jewish, but was often mistaken for being Jewish, and that put him in danger. Godel was a researcher at the Institute for Advanced Study at Princeton from then until the end of his life, in 1978. During his time at this institution devoted to the study of the theoretical, he lectured, pondered, and talked with his close friend, Albert Einstein. He lived an important life, but not necessarily a normal one.
Before Godel, many mathematicians were positivists: they believed that genuine knowledge could be gained from observation of the world around them. More specifically, many of them, especially Godel’s peers in Vienna, were logical positivists. Logical positivism was the belief that all knowledge, all meaningful truths, comes from logical conclusions, findings reached by logically analytic reasoning, such as mathematical proofs. Godel also vehemently disagreed, along with the author, with the belief (implied or specific) of many of them that ‘man is the measure of all things’. This phrase is more than just pompous and solipsistic: it is also dismissive of the idea that mathematics exists independent of humans’ attempts to tame and contain it with symbols and contrived representations. All of these disagreements on the part of Godel stem from his incompleteness proof.
The incompleteness theorems, of which there were two (a main part and an important corollary) proved that mathematics exists independently of humans. The first incompleteness theorem did this the most. The first incompleteness theorem states that in every consistent formal system, there exists a proposition that is both true and not provable within that system. No formal system is made up only of provable propositions. There will always be something that is true and not provable. What is a formal system, and what is consistency, you might ask? Well a formal system is basically an axiomatic system. An axiomatic system is a self-contained system which contains a set of specific axioms, which must be independent of each other. One axiom does not logically lead to another. The system also contains all of the theorems that are provable using the axioms as their foundations. Along with being independent, an axiomatic system must not be contradictory: it has to be consistent. In other words, logic and theorems stemming from the axioms cannot be used to disprove, negate, those axioms, or any other theorem in the system. Finally, an axiomatic system must be complete. This means that any propropsition expressed in the system must be either provable or disprovable (the negation must be provable).
All that applies to axiomatic systems also applies to formal systems. This is because a formal system is basically an axiomatic system, but formal systems have more stringent requirements. Axiomatic systems need to just have axioms and derived theorems and proofs, but formal systems need to have a language that can be used to show all the steps taken from the axioms to the theorems. The requirements for formal systems are more rigorous because inferring cannot be used to get from axioms to theorems: there have to be clearly defined logical steps. This logic is represented by a handful of symbols, Godel used only nine, which can represent every logical operation in the universe when used in combination with each other. These symbols are the language.
When Godel proved his incompleteness theorem, he proved that all consistent (non-contradictory) formal systems are not complete. This means that there exist propositions that cannot be proved but still are true (they cannot be proven either). Therefore, every formal system that is set forth will never be complete. There will always be truths that are not provable, conjectures that are true but will never turn into a theorem. And if you try to add that unprovable truth to the formal system as an axiom, there will always be another unprovable but true statement constructable in the new system, ad infinitum.
The proof was done through first creating a way to map symbols to numbers in an unique way in such a fashion so that the numbers could be used to reconstruct the symbols and vice versa. Then, this number mapping (called Godel numbering), could be used to turn valid logical proofs expressed in symbols into arithmetic statements that are also valid. This was an enormous feat. Godel created a statement that was also arithmetically valid when translated using Godel numbering that basically said that a thing (G) was true if and only if G was not provable. This has to be true, because if it were false, G would be provable and therefore true. The arithmetic equivalent of this statement was therefore a statement that was true but not provable. Godel had proven that such an arithmetical statement existed, and would exist in every formal system. But how did Godel prove that the statement was true but not provable? Isn’t that impossible? Well, he did it by going outside of the formal system, using information not contained in the system. This means that true but unprovable statements are only unprovable within the system. This is still a big deal though, because it means that there is a true statement in the system that cannot be proved by the axioms that are supposed to be able to prove everything.
Godel’s proof had meta implications. This is because the proof basically said that no system created by humans can be complete. If something is incomplete, true but not provable, there is a missing piece. This missing piece exists abstractly. The missing piece just cannot be seen. The truth cannot be found by logical operations alone, but it is still true. All of this basically proves that mathematics exists independent of humans. Humans do not create math. It also proves that positivists are wrong because not everything is provable. The platonists are right: abstract objects exist, like the missing piece that makes some truths not provable. So, Godel’s proof had implications far more extensive than ordinary proofs.