Gödel


A SyndWich of #TEOT, #TLOM, #TEMAF, & more…

by Prof. Prasanta S. Bandyopadhyay, & Prof. Gordon G. Brittan, Jr., Montana State University, Bozeman (MT)

“No matter how elaborate a philosophical system you work out, in the end, it’s got to be incomplete.” (Woody Allen, Crimes and Misdemeanors)

Introduction: We have been invited by SynTalk to write a note on some of the episodes. We have chosen Gödel’s incompleteness results as the topic of our discourse (based on the SynTalk episodes titled #TEOT (The Everything of Theory), #TLOM (The Limits of Mathematics), & #TEMAF (The Errors Mistakes and Failures)). At least four questions intrigued the discussants on these episodes. For e.g., (i) how Gödel’s incompleteness theorems could affect theories of physics which contain mathematics, (ii) what mathematics can or can’t prove, (iii) why axioms of mathematics are self-limited, and (iv) why a computer program cannot solve undecidable problems for which there exist no decision procedure. Since all of these questions are tied to Gödel’s incompleteness results in one way or another, we will discuss them first. However, our primary intention is to explore whether Gödel’s incompleteness results raise concerns regarding the rigor and completeness of physical theories. The potential concern is that even the most successful theories of physics could have at least one true statement regarding physics that is not deducible from it (see John D. Barrow, 1998 and 2006).

This brief discussion is intended to explain Gödel’s incompleteness results ­­– what follows and what does not follow from them – always keeping physical theories as a primary focus.

Gödel’s Incompleteness Results and Alleged Consequence for Theories of Physics: In 1931, Gödel proved two incompleteness results. The first incompleteness theorem states that for any consistent formalized system that contains elementary arithmetic (including the basic operations of addition and multiplication of natural numbers), there exists a sentence G of the formalized system such that neither G nor its negation is provable within the system. According to the second incompleteness theorem, no consistent formal system containing elementary arithmetic can prove its own consistency, provided that the notion of “provability in the system” is suitably formalized within the system itself.

Here, we need to distinguish ‘logical entailment’ and ‘deductive derivability’ to understand the scope of the incompleteness results. Logical entailment is a semantic notion: for a theory T to logically entail a statement S means that every interpretation that makes the propositions of T true must also make S true. In contrast, deductive derivability is a syntactic notion: for a sentence S to be deductively derivable from theory T means that under some rigorous deduction system like the natural deductive system, there is a proof of S from statements in T. Prior to his two incompleteness theorems, Gödel proved a fundamental logical result, known as the completeness theorem, which showed that for any theory T, formalized in first-order logic (i.e., that quantified only over individuals and not sets), the notions of logical entailment and deductive derivability coincide: A statement S is logically entailed by T if and only if S is deductively derivable from T.

One alleged implication of the incompleteness results is that at least some predictions of physical theories which rely for their derivation on mathematics at least as complex as number theory are if true unprovable. The crisp version of this argument goes like this: If mathematics contains true statements which are not provable, and physics depends on mathematics for making predictions, then some of the key parts of physical theories could contain true statements that are not provable.

What Follows from Gödel’s Theorems? To forestall a possible confusion at the outset, it is important to emphasize that an incomplete theory need not be a false theory; such a theory may still be ‘correct’ or ‘sound’, by which we mean that all statements deductively derivable from it are true. A theory’s incompleteness just implies that there are some truths of the theory which are not derivable from it.  That a theory fails to imply a statement only means that the theory does not say whether that statement is true or false. This point about a theory being incomplete holds irrespective of Gödel’s incompleteness results.

With that in mind, Gödel’s first incompleteness theorem can be restated more semantically as follows:  If a formal deductive system containing elementary arithmetic is sound (in the above sense), then it must necessarily be incomplete, that is, there will be true sentences which cannot be proved by the system, given a specific understanding of ‘proved by’. Now physics, when formalized as a theory whose statements express truths about the physical world, will (if consistent) be a sound formal system containing (presumably) elementary arithmetic, and so the first incompleteness theorem will apply: It must necessarily be an incomplete formal system.

It is widely thought that Gödel’s results shattered Hilbert’s Program. To escape paradoxes and inconsistencies in mathematics, Hilbert invited mathematicians to come up with a system formalizing mathematics whose consistency can be proved by ‘finitistic’ methods. Here the ‘consistency of the system’ means that the system is incapable of proving both a sentence S and its negation. The word ‘finitistic’ is vague, but under most reasonable interpretations, a ‘finitistic’ procedure must be a computable procedure (‘general recursive’ in the standard Turing-Church sense), and therefore can be carried out within any formal system containing elementary arithmetic. Gödel’s second incompleteness theorem implies that no consistent system formalizing mathematics (which necessarily contains elementary arithmetic) can prove its own consistency, provided that the notions of provability and consistency are suitably formalized for expression within the system itself. This last italicized clause is crucial. In contrast to the first theorem, the validity of the second theorem depends quite heavily on how the notions of consistency and provability are formalized within the system. Later research has showed that, if that formalization is done differently (from the normally intended way), then the system may prove ‘its own consistency’! However, if we agree to formalize the notions of provability and consistency in the standard way, then Hilbert’s program is certainly destroyed by Gödel’s results, since the consistency of any standard formalization of mathematics (such as Zermelo-Fraenkel Set theory) can never be established via a weaker (‘more finitistic’) system.  In particular, if we interpret a ‘finitistic argument’ to be ‘one that can be carried out within first order arithmetic’ (such as first order Peano Arithmetic or some restricted version of it), then there are theorems of infinitistic mathematics (e. g., set theory or second order arithmetic) which are unprovable by finitistic mathematics.

Quine thought that these incompleteness results have other consequences, such as in understanding why we are unable to derive some truths from self-evident truths by self-evident steps. He writes, “Actually, even the truths of elementary number theory are presumably not in general derivable, we noted, by self-evident steps from self-evident truths. We owe this insight to Gödel’s Theorem, which was not known to the old-time philosophers”. On the same page, he writes, that “it is now recognized that deduction from self-evident truths and observation is not the sole avenue to truth nor even to reasonable belief”. He defines ‘self-evident’ truths as those that everyone accepts without question. Additionally, they do not depend on any other belief or observation for their support. What he means is that they follow as the conclusions of zero-premise arguments in systems of natural deduction and therefore do not require any support. They follow as the conclusions of zero premise arguments in systems of natural deduction and therefore do not require any support. Although nothing in what follows depends on the point, it might be doubted whether the first psychological criterion of self-evidence in terms of ‘acceptance’ is equivalent to the second logical criterion in terms of ‘deduction’.

Quine’s comments on Gödel’s results and their connection to self-evident truths are rather casual. In a broad sense, what he writes about Gödel’s results are correct, but Gödel’s results are much more specific and concrete than is the debate over self-evident truths based on self-evident steps in the history of western philosophy and Quine’s comments can be taken as typical of the way in which these results are sometimes ‘generalized’ by philosophers.

One charitable way to make sense of Quine’s remarks on Gödel’s results is to connect them to what he says in one of his celebrated articles on “Two Dogmas of Empiricism”. For him, there are two dogmas. One is the analytic/synthetic distinction. The other is foundationalism, i.e., the reduction (derivation) of sentences about one area of investigation (e.g., physics, mathematics) to (from) epistemologically secure — (in fact, incorrigible) — sentences in another area (sense-data or logic). He rejects foundationalism (and with it the idea of philosophy as ‘queen of the sciences’, etc.). So, the reconstruction of connecting his earlier comment on Gödel and his stance toward empiricism proceeds as follows:

  1. If foundationalism/reductionism works anywhere, it should work in elementary number theory.
  2. Gödel showed that it does not work in elementary number theory.

Therefore, foundationalism/reductionism does not work anywhere.

This is the sense in which Quine’s argument works against Hilbert via the route to Gödel’s incompleteness results. Hilbert is a foundationalist when it comes to mathematics; in a big picture, this reconstruction shows how Gödel’s results challenge Hilbert’s Program of foundationalism in philosophy of mathematics. Quine simply extends the same line of argument to reductionist programs typical of Western philosophy since the 18th century, and particularly characteristic of Anglo-Saxon philosophy (logicism, behaviorism, instrumentalism, etc.) in the 20th century.

What does not follow from Gödel’s Theorems? It follows from the incompleteness theorems that there may be some truths of physics (for example) that are not logical consequences of any finite axiomatization of physical theories. As far as we know, we are unaware of any serious problem this could generate. It is not a consequence of the theorems that any physical theory will have consequences which are false. Gödel’s theorems at most entail that the physical theories do not entail every truth about physics. However, they do not entail that any consequence of any such physical theory that makes use of arithmetic is false.

Conclusion: In view of worries regarding the possibility of unproven statements in physical theories because of Gödel’s incompleteness results, we discuss what these incompleteness results really yield. To reiterate, the incompleteness results show that physical theories do not imply every truth expressible within them. However, we have yet to come across any reason to believe that this possibility generates any genuine limitation on physical theories. For when one worries whether physical theories are ‘genuinely incomplete’ or not, the worry has to do with whether there are types of phenomena (e.g., those at stake in the EPR thought-experiment) that are not explicable within the present resources of quantum theory, and not with the possibility that some (possibly insignificant) true data-predictions for example are not derivable from it.

One might nonetheless wonder why this (i.e., the possibility of some unproven statements in physics) should not be taken seriously. There are two considerations that might ease the worry. First, there are some practical issues even in the application of theories of physics to real world situations. Second, the worry is an issue concerning the foundations of scientific inference.

The first consideration has to do with application. Observations and measurements are always subject to error and uncertainty, and they extend also to the constants which appear in many standard equations. Some equations used in physics cannot be solved directly, hence approximate methods are used, especially when computers are available to do the heavy lifting. Since we are far from being able to answer all the questions of physics with theories that we now have, it is not clear why the additional problem of not being able to deduce all the correct answers from a mathematical theory of physics should worry us.

The second consideration has to do with inference. It is well-known that Frege, working on the foundations of arithmetic, assumed the consistency of a particular set of set-theoretical axioms, which Russell later proved to be inconsistent. Gödel’s second incompleteness result that, on certain intuitive assumptions, the consistency of suitably strong set-theoretical axioms cannot be demonstrated further undermined foundationalist attempts to do so. The point is that this and other foundational debates have no longer stopped mathematics from being applied to solve real world problems such as those in physics and chemistry (P.S Bandyopadhyay and M.R. Forster, eds., “Introduction” to Handbook of Philosophy of Statistics, Elsevier, 2011). Additionally, few physical theories are formulated formally with the kind of axioms which Gödel’s theorems require (though on occasion some of them have been). Therefore, the worry concerning the possibility of some unproven true statements in physics does not pose a significant threat to the overwhelmingly successful application of theories of physics to the prediction and explanation of real-world phenomena.

However, this sort of worry concerning whether Gödel’s results might affect theories of physics is common to philosophers who are interested not so much in the predictions to which scientific theories give rise as in their claims to ‘genuine knowledge’. As philosophers, we do not have to tread as far as Woody Allen, in his Crimes and Misdemeanors, when he boldly asserts: “No matter how elaborate a philosophical system you work out, in the end, it’s got to be incomplete”. Nonetheless, we philosophers admit that though that our worries are abstract and epistemological, they are nonetheless (to a small percentage of the population!) worth-discussing.

Acknowledgment: We would like to thank Kevin Beiser, John G. Bennett, James Hawthorne, and especially Abhijit Dasgupta for numerous helpful comments while this SyndWich was being written.

(Prof. Prasanta S. Bandyopadhyay is a philosopher with interests in epistemological and methodological issues in probability, logic, & statistics (in particular Bayesian inference). He is currently a Professor at Montana State University in Bozeman (MT). Prof. Gordon G. Brittan, Jr. is a philosopher with interests in  philosophy and history of science, technology, & mathematics (logic, algebra), and Kant. He retired from MSU in 2008 and is currently Professor Emeritus. We have not had the opportunity of hosting either Prof. Bandyopadhyay or Prof. Brittan, Jr. on a SynTalk episode yet, but hope that such an opportunity would arise sometime in the future. ‘Gödel’ was written on/around November 19, 2019)