GÖDEL-INCOMPLETENESS AND FORMAL PIETY: A Lecture in Aphoristic Style For Philosophers Who Aren’t Professional Logicians or Mathematicians.
By Robert Hanna
APP EDITOR’S NOTE
You can also download or read a complete .pdf version of this essay HERE.
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, 1967, pp. 596–617, also available online HERE.
What follows is a informal presentation of Kurt Gödel’s brilliant and famous 1931 argument for the incompleteness of mathematical logic — understood as per Whitehead’s and Russell’s Principia Mathematica, and essentially similar systems — together with some concluding remarks on (what I take to be) the larger philosophical significance of Gödel-incompleteness.
It’s short-&-sweet, in lecture-format and an aphoristic style, intended for philosophers who aren’t professional logicians or mathematicians.
II. The Lecture, in 30 Steps
1. Logicism is — or more precisely, was — the logical, mathematical, and philosophical project of explanatorily reducing mathematics to logic.
Logicism is closely, and indeed essentially, associated with the emergence, rise, and fall of classical Analytic philosophy from roughly 1900 to 1950.[i]
It’s a necessary condition of carrying out the logicist reduction of mathematics to logic, that every true mathematical sentence be provable within a logical system.
2. In the late 19th century, Gottlob Frege had attempted this logicist reduction for arithmetic in Basic Laws of Arithmetic.[ii]
And in Principia Mathematica, an early 20th century treatise by A.N. Whitehead and Bertrand Russell,[iii] 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 ended the logicist project in its classical Frege-Whitehead-Russell version, and also put a serious kink in the project of classical Analytic philosophy.
3. Intriguingly, and significantly, Gödel’s argument uses an extremely surprising mathematical discovery (or invention) made by Georg 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.[iv]
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, perhaps surprisingly, that the whole numbers (0, 1, 2, 3 …) and also the integers (the whole numbers and their negative mirror) and rational numbers (integers plus all repeating and terminating decimals), and all sets of numbers based on basic (primitive recursive) mathematical operations over the rationals, have the same cardinality (i.e., 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.
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.
The appearance of a contradiction in logical system is A Very Bad Thing,[v] 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.
5. The systemwide logical property of soundness says that all the theorems (provable sentences) of a system are true sentences of that system.
6. And the systemwide logical property of completeness says that all the true sentences of a system are theorems (provable sentences) of that system.
7. Against the theoretical backdrop of those systemwide logical properties, how does one go about demonstrating Gödel-incompleteness?
8. Starting with a Principia-style system of mathematical logic, you add to it the basic axioms of (Peano) arithmetic, i.e.,
(1) 0 is a number,
(2) the successor of any number is a number,
(3) no two numbers have the same successor,
(4) 0 is not the successor of any number,
(5) 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.
9. Then you assume that the enriched system is consistent, sound, and complete.
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.
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 every time you think it or say it, and the fact of self-guaranteeing self-reference is essentially the same.)
So in effect, then, Gödel mapped the definition of truth into the system itself.
12. Now, using each provably true sentence’s Gödel number, you create a top-down denumerably infinite vertical list of all the provably true sentences.
13. Then you use Cantor’s diagonalization method to show that there is at least one provably true sentence that is not on that list.
14. Since, by hypothesis, you’ve already created a denumerably infinite list of all the provably true sentences, such a sentence must be unprovable.
In effect, by virtue of its non-denumerable or transfinite Gödel number, that sentence says of itself that it’s unprovable.
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).
16. But if it’s false that it’s unprovable, then the sentence has to be provable.
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!
(A paradox is a hyper-contradiction, aka a badass contradiction.)
Note: 13–17 basically present a version of the notorious Liar Paradox, i.e., the sentence that says of itself that it’s false: so if it’s true then it’s false, and if it’s false then it’s true, hence necessarily it’s true if and only if it’s false.
(Once there was a Cretan who said that all Cretans are liars: so was he telling the truth or not?
If he was, then he wasn’t, but if he wasn’t, then he was.
Interestingly, you can get out of this contradiction just by denying that there ever was such a silly Cretan: but the Liar Paradox isn’t contingently solvable in this way.)
18. Since you’ve shown that the system contains not only an unprovable sentence, but also a contradiction (indeed a paradox), therefore the system is inconsistent (indeed badass inconsistent), which is a Very Bad Thing.
19. Now you face a super-hard systemwide choice: consistency or completeness?
In order to retain the consistency of the system, you have to give up its completeness (i.e., you have to give up the property that all true sentences are provable).
20. Therefore, 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.
21. And in this way, the project of logicism also fails, because in order to retain consistency in enriched Principia-style systems, you have to give up completeness, and therefore not all true sentences of mathematics are provable, hence mathematics is not explanatorily reducible to logic.
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.
23. But as we’ve also seen, mapping truth into the system in this way leads to inconsistency, on the assumption of its completeness.
24. Hence, in order to show that any such enriched Principia-style system is consistent, on the assumption of its incompleteness, you 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.[vi]
I’ll conclude with some remarks on (what I take to be) the larger philosophical significance of Gödel-incompleteness.
25. By piety in the specifically scientific (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 logic in terms of something else already presupposes logic, and is self-undermining-ly (if that’s a word) circular.
More generally, then, it seems that logic cannot itself be justified or explained except in terms of itself, and therefore logic seems to be unjustifiable and inexplicable.
That predicament is what 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.[vii]
26. 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.”[viii]
In other words, we’ve reached a basic or primitive starting point of explanations or justifications, and we simply rationally accept that; moreover, to ask for further explanations and justifications would lead to self-undermining circularity.
This acceptance can also be regarded, Kant-wise, as picking out a transcendental fact.[ix]
27. 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 or justifications.
Correspondingly, I think that Gödel’s incompleteness theorems 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.
28. Indeed, Gödel himself held that logically unprovable truths of mathematics would have to be known directly by mathematical intuition.[x]
In turn, I think that one of those logically unprovable truths of mathematics is Cantor’s thesis that there are non-denumerably infinite, aka transfinite, numbers, since diagonalization requires what Immanuel Kant calls spatial intuition (Anschauung),[xi] and therefore diagonalization isn’t strictly logical.
29. 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.[xii]
30. And one last remark, by way of a coda: I also think that contemporary physics manifests a precise natural-scientific analogue of Gödel-incompleteness, and that the right scientific and philosophical attitude to take towards this fact is a precise natural-scientific analogue of Gödelian formal piety, namely natural piety.[xiii]
But that’s another philosophical story for another day.[xiv]
[i] See, e.g., R. Hanna, THE FATE OF ANALYSIS: Analytic Philosophy From Frege To The Ash-Heap of History (2020 version), esp. chs. I and VII, available online HERE.
[ii] G. Frege, The Basic Laws of Arithmetic, trans. M. Furth (Berkeley and Los Angeles, CA: Univ. of California Press, 1964).
[iii] See, e.g., A.N. Whitehead and B. Russell, Principia Mathematica to *56 (Cambridge: Cambridge Univ. Press, 1962).
[iv] G. Cantor, “Ueber eine elementare Frage der Mannigfaltigkeitslehre,” Jahresbericht der Deutschen Mathematiker-Vereinigung 1 (1891): 75–78.
[v] Actually, some post-classical Analytic philosophers think that contradictions aren’t such a very bad thing after all, and are correspondingly prepared to admit contradictions, including paradoxes, into (non-classical, “deviant”) systems. See, e.g., See, e.g., G. Priest, In Contradiction (Dordrecht: Martinus Nijhoff, 1987); and G. Priest, “What is So Bad about Contradictions?,” Journal of Philosophy 95 (1998): 410–426. It’s worth noting, however, that even those wild-&-crazy, contradiction-loving, deviant logicians (aka dialetheists) still want systematically to rule out explosion, which is called paraconsistency. Explosion is Hell.
[vi] Several of the ideas in this presentation of Gödel-incompleteness, especially including the crucial role played by Cantor’s diagonalization method, were suggested to me by reading Jörgen Veisdal’s compact and informative “Cantor’s Diagonal Argument,” Medium (6 July 2020), available online at URL = <https://medium.com/cantors-paradise/cantors-diagonal-argument-c594eb1cf68f>; and for a more detailed presentation, see S. Feferman, “The Nature and Significance of Gödel’s Incompleteness Theorems,” available online at URL = <https://www.academia.edu/160391/The_nature_and_significance_of_G%C3%B6dels_incompleteness_theorems>.
[vii] H.M. Sheffer, “Review of Principia Mathematica, Volume I, second edition,” Isis 8, (1926): 226–231, at p. 228.
[viii] L. Wittgenstein, Philosophical Investigations, trans. G.E.M. Anscombe (New York: Macmillan, 1953), §217, p. 85e.
[ix] See R. Hanna, Rationality and Logic (Cambridge, MA: MIT Press, 2006), ch. 3, also available online in preview at URL = <https://www.academia.edu/21202624/Rationality_and_Logic>.
[x] See, e.g., W. Tait, “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, 2010), vol. 33, pp. 88–108.
[xi] See I. Kant, Critique of Pure Reason, trans. P. Guyer and A. Wood (Cambridge: Cambridge Univ. Press, 1998), pp. 172–192 (A19/B33-A49/B73).
[xii] See, e.g., R. Hanna, Kant and the Foundations of Analytic Philosophy (Oxford: Clarendon/OUP, 2001), also available online in preview at URL = <https://www.academia.edu/25545883/Kant_and_the_Foundations_of_Analytic_Philosophy>; and R. Hanna, Kant, Science, and Human Nature (Oxford: Clarendon/OUP, 2006), ch. 6, also available online in preview at URL = < https://www.academia.edu/21558510/Kant_Science_and_Human_Nature>.
[xiii] See R. Hanna, “The Incompleteness of Physics” (September 2020 version), available online at URL = <https://www.academia.edu/44019662/The_Incompleteness_of_Physics_September_2020_version_>.
[xiv] I’m grateful to Michael Cifone for inviting this lecture and also (indirectly) suggesting the sub-title.
AGAINST PROFESSIONAL PHILOSOPHY REDUX 489
Mr Nemo, W, X, Y, & Z, Tuesday 13 October 2020
Please consider becoming a patron!