Gödel’s two incompleteness theorems (Gödel, 1967) say (i) that all Principia Mathematica-style systems of mathematical logic based on the Peano axioms for arithmetic will contain undecidable/ unprovable sentences (first theorem), and (ii) that no such system of mathematical logic can prove its own consistency, hence the truth of mathematical axioms has to be demonstrated outside those systems (second theorem)—for example, by acts of rational human mathematical intuition.

ELABORATION

What follows in the rest of this entry is an informal presentation, in 30 steps, of Kurt Gödel’s brilliant, famous, and philosophically devastating argument for the incompleteness of mathematical logic (Göedel, 1967), where “mathematical logic” is understood as per Whitehead’s and Russell’s Principia Mathematica, and essentially similar systems, together with some concluding remarks on the larger philosophical significance of Gödel-incompleteness for classical Analytic philosophy in particular and the Analytic tradition more generally.

STEP 1.

Logicism is—or more precisely, was—the logical, mathematical, and philosophical project of explanatorily and ontologically reducing mathematics to logic. Logicism was closely, and indeed essentially, associated with the emergence, rise, and fall of classical Analytic philosophy from 1880 to 1950. More generally, it’s a necessary condition of carrying out the logicist reduction of mathematics to logic in the classical Frege (for arithmetic only) and Whitehead-&-Russell (for all of mathematics) sense that every true mathematical sentence be provable within a Principia-style logical system.

STEP 2.

In the late 19th century, Frege had attempted this logicist reduction for arithmetic in Basic Laws of Arithmetic. And in Whitehead’s and Russell’s Principia Mathematica, they present a system of mathematical logic that was supposed to be the logical vehicle for doing this for all of mathematics: it’s a classical bivalent quantified (over individuals and functions) polyadic (many-place) predicate logic. But Gödel-incompleteness killed the logicist project in its classical Fregean and/or Whiteheadian-&-Russellian versions, alike, and thereby put a serious kink in the project of classical Analytic philosophy.

STEP 3.

Intriguingly, and significantly, Gödel’s argument uses an extremely surprising mathematical discovery (or invention) made by Cantor: the diagonalization argument for the existence of transfinite numbers, i.e., non-denumerable infinities, i.e., infinite sets that cannot be put into a 1-1 correspondence with the infinite set of natural numbers (Cantor, 1891, 2019). How did Cantor do this? Let’s assume that the set of natural numbers (i.e., 1, 2, 3...) is infinite: then a set of numbers is denumerably infinite if and only if it can be put into a 1-1 correspondence with the set of natural numbers. It turns out that the whole numbers (0, 1, 2, 3 …) and also the integers (the whole numbers and their negative mirror) and also the rational numbers (integers plus all repeating and terminating decimals), and also all sets of numbers based on basic (primitive recursive) mathematical operations over the rationals, all have the same cardinality (counting-number-osity) as the natural numbers, because they can be paired 1-1 with the natural numbers. Basically, Cantor created a method for displaying a top-down vertical list of all the number sequences in the system of positive rational numbers (and since the negative numbers are just a mirror of the positive ones, they don’t differ except in their being marked as negative). Then he constructed or “drew” a diagonal line across the list. Since, by hypothesis, a complete list contains all the rationals, and there are infinitely many rationals, then the infinite number picked out by the diagonal isn't on the list, hence its cardinality is non-denumerable but still infinite, aka transfinite. Moreover, because the list is a two-dimensional array, and since the constructed diagonal line that runs across it systematically picks out a number that is not displayed within the two-dimensional space of the array, then it in effect represents a third and higher spatial dimension over and above the two-dimensional array. So, in effect, transfinite numbers are higher-dimensional numbers.

STEP 4.

Now, the systemwide logical property of consistency says that a system contains no contradictions, where a contradiction is a sentence that’s the conjunction of a sentence and its negation. Contradictions are logically necessarily false, i.e., false in every logically possible world. Classically, the appearance of a contradiction in any logical system is A Very Bad Thing,^[1] because, starting with a contradiction as your sole premise, you can prove any sentence whatsoever, no matter how false (or silly for that matter). This systemwide logical property of contradictions is rightly called explosion.

STEP 5.

The systemwide logical property of soundness says that all the theorems (provable sentences) of a system are true sentences of that system.

STEP 6.

And the systemwide logical property of completeness says that all the true sentences of a system are theorems (provable sentences) of that system.

STEP 7.

Next, assume the normatively strict direct relevance of those three systemwide logical properties. Against that theoretical backdrop, how does one go about demonstrating Gödel-incompleteness?

STEP 8.

Starting with a Principia-style system of mathematical logic, add to it the basic axioms of (Peano) arithmetic, namely: (i) 0 is a number, (ii) the successor of any number is a number, (iii) no two numbers have the same successor, (iv) 0 is not the successor of any number, and (v) any property which belongs to 0, and also to the successor of every number which has the property, belongs to all the numbers, taken together with the primitive recursive functions over the natural numbers—the successor function, addition, multiplication, exponentiation, etc.

STEP 9.

Then, assume that the enriched system is consistent, sound, and complete.

STEP 10.

Because the enriched system represents arithmetic via the Peano axioms and the primitive recursive functions, there will be a denumerably infinite number of true sentences in the system.

STEP 11.

Gödel created a way to number each of the (true or false) sentences in such an enriched system, aka their Gödel-numbers, so because the enriched system is assumed to be sound, there will be a denumerably infinite number of provably true sentences, each of which has its own Gödel number. In effect, its Gödel-number says “I am provable, I am true.” This might remind you of Descartes’s “I am, I exist,” which, necessarily, is true whenever you think it or say it (Descartes, 1984: p. 17), and the fact of necessarily self-guaranteeing self-reference is essentially the same. So in effect, then, Gödel mapped the definition of truth into the system itself.

STEP 12.

Then, using each provably true sentence’s Gödel number, we create a top-down denumerably infinite vertical list of all the provably true sentences.

Step 13.

Then, we use Cantor’s diagonalization method to show that there is at least one provably true sentence that is not on that list.

STEP 14.

Since, by hypothesis, we’ve already created a denumerably infinite list of all the provably true sentences, such a sentence must be unprovable. Moreover, in effect, by virtue of its non-denumerable or transfinite Gödel number, that sentence says of itself that it’s unprovable.

STEP 15.

But if it’s unprovable, then, since we’re assuming completeness, that sentence also has to be false, by modus tollens (every true sentence is provable, but if it’s not provable, then it’s not true, i.e., it’s false).

STEP 16.

But if it’s false that it’s unprovable, then the sentence has to be provable.

STEP 17.

So the sentence is both provable and unprovable: contradiction! But even worse than that, necessarily, that sentence is provable if and only if it’s not provable: paradox!

STEP 18.

Since we’ve shown that the system contains not only an unprovable sentence, but also a contradiction (indeed a paradox), therefore the system is inconsistent (indeed hyper-inconsistent), which, from the standpoint of classical logic, is a Very Bad Thing.

STEP 19.

Now we face a super-hard systemwide choice: consistency or completeness? In order to retain the consistency of the system, as per classical logic, we have to give up its completeness (i.e., we have to give up the property that all true sentences are provable).

STEP 20.

Thus, every Principia-style system enriched by the axioms of Peano arithmetic and the primitive recursive functions, insofar as it’s consistent, contains true but unprovable sentences, and therefore it’s incomplete. That’s Gödel’s first incompleteness theorem.

STEP 21.

And in this way, the project of classical logicism also fails, because in order to retain consistency in enriched Principia-style systems, we have to give up completeness, and therefore not all true sentences of mathematics are provable, hence mathematics is not explanatorily reducible to logic.

STEP 22.

Now, we’ve reached this conclusion by assuming that provability is sufficient for truth (soundness), and by showing that every provably true sentence in an enriched Principia-style system can be listed by using its Gödel number, which as we saw above, in effect says that it's true, hence in effect mapping the definition of truth into the system itself.

STEP 23.

But as we’ve also seen, mapping truth into the system in this way leads to inconsistency, on the assumption of its completeness.

STEP 24.

Hence, in order to show that any such enriched Principia-style system is consistent, on the assumption of its incompleteness, we have to define truth outside that system, i.e., the consistency of the system cannot be demonstrated inside the system itself. And that’s Gödel’s second incompleteness theorem.^[2]

STEP 25.

Given all that, since it’s a necessary condition of carrying out the logicist reduction of mathematics to logic in the classical Fregean and/or Whiteheadian-&-Russellian sense that every true mathematical sentence be provable within a Principia-style logical system, then the project of classical logicism is kaput.

STEP 26.

By piety in the specifically scientific and/or philosophical sense, I mean the rational acceptance of certain facts as basic or primitive, such that any further attempt to explain or justify those facts in terms of something else would invoke those very facts, and therefore lead to self-undermining circularity. For example, in order to explain or justify logic, logic must also be presupposed and used, hence any attempt to explain or justify logic in terms of something else already presupposes logic, and is self-undermining-ly (if that's a word) circular. More generally, then, logic cannot itself be explained or justified except in terms of itself, and therefore logic is both inexplicable and unjustifiable, i.e., rationally groundless. That predicament is what the Harvard logician Harry Sheffer called The Logocentric Predicament:

The attempt to formulate the foundations of logic is rendered arduous by a … “logocentric” predicament. In order to give an account of logic, we must presuppose and employ logic.
(Sheffer, 1926: p. 228)

STEP 27.

Now, one approach to The Logocentric Predicament is simply to accept that circularity; as the later Wittgenstein says of other similar predicaments in Philosophical Investigations:

If I have exhausted the [explanations or] justifications I have reached bedrock, and my spade is turned. Then I am inclined to say: “This is simply what I do.
(Wittgenstein, 1953: p. 85e, §217)

In other words, Wittgenstein is saying, we’ve reached a basic or primitive starting point of explanation or justification, and we simply rationally accept that; moreover, to ask for further explanations and justifications would lead to self-undermining circularity. In turn, this acceptance can also be regarded, Kant-wise, as picking out a transcendental fact (Hanna, 2006a: ch. 3)

STEP 28.

By formal piety, then, I mean the rational acceptance of certain formal-logical facts as basic/primitive—and arguably transcendental—starting points for formal-logical explanations and/or justifications. Correspondingly, I think that Gödel’s incompleteness theorems brilliantly manifest formal piety, in that (i) they rationally accept incompleteness as a basic/primitive fact about any enriched Principia-style system, so that acceptance is built into our concepts of mathematics and logic themselves, and (ii) they rationally accept truth as a basic/primitive fact about any enriched Principia-style system, a fact that is never to be (completely) captured by provability, and that must be defined and known outside any such system. More generally, Cantor’s mathematics of transfinite or “transcendental” numbers, which bears witness to higher-dimensional infinities, Gödel’s incompleteness theorems, which bear witness to the inherently non-logical character of mathematical truth, and Alfred Tarski’s semantic conception of truth, which bears witness to Gödel-incompleteness, the Liar Paradox, and the semantic irreflexivity of truth—all brilliantly manifest formal piety.

STEP 29.

In view of the incompleteness theorems, Gödel held that logically undecidable and unprovable truths of mathematics would have to be known directly by mathematical intuition (Tait, 2010). In turn, I think that one of those logically undecidable and unprovable truths of mathematics must be Cantor’s thesis that there exist non-denumerably infinite, aka transfinite, aka transcendental, numbers, since diagonalization requires what Kant calls spatial intuition (Anschauung) (Kant, 1997: pp. 172-192, A19-49/B33-73) and therefore diagonalization isn’t strictly logical.

STEP 30.

If so, then Gödel-incompleteness, since it presupposes Cantorian diagonalization, would require spatial intuition in the Kantian sense; therefore, against the backdrop of Kant’s or Kantian philosophy, this would also entail that mathematics is synthetic a priori, not analytic (Hanna, 2001: ch. 5, 2006b: ch. 6).

REFERENCES

(Cantor, 1891). Cantor, G. “Ueber eine elementare Frage der Mannigfaltigkeitslehre.” Jahresbericht der Deutschen Mathematiker-Vereinigung 1: 75–78.

(Cantor, 2019). Cantor, G. “A Translation of G. Cantor’s ‘Ueber eine elementare Frage der
Mannigfaltigkeitslehre’.” Trans. P.P. Jones et al. 23 August. Available online at URL = https://www.researchgate.net/publication/335364685_A_Translation_of_G_Cantor's_Ueber_eine_elementare_Frage_der_Mannigfaltigkeitslehre.

(Descartes, 1984). Descartes, R. “Meditations on First Philosophy.” In Descartes, R. The Philosophical Writings of Descartes. Trans. J. Cottingham et al. 3 vols., Cambridge: Cambridge Univ. Press. Vol. 1. Pp. 3-62.

(Feferman, 2006). Feferman, S. “The Nature and Significance of Gödel’s Incompleteness Theorems.” Unpublished MS, 2006. Available online at URL =  https://www.academia.edu/160391/The_nature_and_significance_of_Gödels_incompleteness_theorems.

(Gödel, 1967). Gödel, K. “On Formally Undecidable Propositions of Principia Mathematica and Related Systems.” In J. Van Heijenoort (ed.), From Frege to Gödel. Cambridge, MA: Harvard Univ. Press. Pp. 596-617.

(Hanna, 2001). Hanna, R. Kant and the Foundations of Analytic Philosophy. Oxford: Clarendon/Oxford Univ. Press.

(Hanna, 2006a). Hanna, R. Rationality and Logic. Cambridge: MIT Press.

(Hanna, 2006b). Hanna, R. Kant, Science, and Human Nature. Oxford: Clarendon/Oxford Univ. Press.

(Kant, 1997). Kant. I., Critique of Pure Reason, trans. P. Guyer and A. Wood, Cambridge,
Cambridge Univ. Press.

(Priest, 1987). Priest, G. In Contradiction. Dordrecht: Martinus Nijhoff.

(Priest, 1998). Priest, G. “What Is So Bad About Contradictions?” Journal of Philosophy 95: 410-426.

(Sheffer, 1926). Sheffer, H.M. “Review of Principia Mathematica, Volume I, second edition.” Isis 8: 226-231.

(Tait, 2010). Tait, W. “Gödel on Intuition and Hilbert’s Finitism.” In S. Feferman, C. Parsons, and S. Simpson, (eds.), Kurt Gödel: Essays for His Centennial. Cambridge: Association For Symbolic Logic, Lecture Notes in Logic. Vol. 33. Pp. 88-108.

(Veisdal, 2020). Veisdal, J. “Cantor’s Diagonal Argument.” Medium (6 July 2020). Available online at URL = https://medium.com/cantors-paradise/cantors-diagonal-argument-c594eb1cf68f.

(Wittgenstein, 1953). Wittgenstein, L. Philosophical Investigations. Trans. G.E.M. Anscombe. New York: Macmillan.

PHILOSOPHICAL CONCEPTS: A TO Z

An annotated, encyclopedic philosophical dictionary or philosophical lexicon — an endless work-in-progress, forever open to critical examination, revision, and updating.

planksipRobert Hanna

If you feel so inclined, please feel free to show your support for Robert via his Patron page (https://www.patreon.com/philosophywithoutborders) or purchase his recently published book, The Fate of Analysis (2021).

The Fate of Analysis (2021)

Robert Hanna’s twelfth book, The Fate of Analysis, is a comprehensive revisionist study of Analytic philosophy from the early 1880s to the present, with special attention paid to Wittgenstein’s work and the parallels and overlaps between the Analytic and Phenomenological traditions.

By means of a synoptic overview of European and Anglo-American philosophy since the 1880s—including accessible, clear, and critical descriptions of the works and influence of, among others, Gottlob Frege, G.E. Moore, Bertrand Russell, Alexius Meinong, Franz Brentano, Edmund Husserl, The Vienna Circle, W.V.O. Quine, Saul Kripke, Wilfrid Sellars, John McDowell, and Robert Brandom, and, particularly, Ludwig Wittgenstein—The Fate of Analysis critically examines and evaluates modern philosophy over the last 140 years.

In addition to its critical analyses of the Analytic tradition and of professional academic philosophy more generally, The Fate of Analysis also presents a thought-provoking, forward-looking, and positive picture of the philosophy of the future from a radical Kantian point of view.

Purchase from The Mad Duck Coalition