Gödel’s Incompleteness Theorem: How can truth go deeper than proof?

Question

My current understanding:

Math starts with a set of basic (purportedly self-evident) statements that are taken as a given without the need to prove them true, like e.g., a + b = b + a etc. Such initial statements are called axioms.

Any further mathematical statement though is only considered true when shown to be in accordance with the axioms. To the contrary, if in disagreement with at least one of the axioms, a corresponding statement is considered false.

Gödel’s Incompleteness Theorem

However, according to Gödel there are statements like "This sentence is false" which are true despite how they cannot be successfully reduced to the pre-existing axioms, i.e. cannot be proven true.

What confuses me:

What I encounter difficulty with to understand is the precise definition of truth in the context of the incompleteness theorem. First, truth is defined as a state where a statement is demonstrated (“proven”) to be in accordance with the axioms, i.e. truth is established by proof. Then however, truth is claimed to exist even if a statement cannot be proved true given the current set of axioms, suggesting that the knowledge that some statement is true can be reached by “bypassing” any proof.

My question:

Doesn’t the above imply that truth can be established without the requirement of any proof? If so, why then the need to prove any statement at all to demonstrate it is true?

Answer 1

An excellent point! Yes, if something can't be proved, then we do not have much reason to believe it. We believe Godel sentences are true because we can "prove" them. We can't prove them within the system for which we construct the Godel sentence, but we can "prove" them in the human mind, outside that system.

A Godel sentence P is a particular sentence that cannot be proved within the formal system S that it is expressed in. P is a statement within the universe of S; for example, if S is a system of arithmetic, P would be a statement about numbers.

But humans "know" that P is true (assuming S is sound), because we can use our brains to interpret P, based on how P was constructed. We interpret P as saying, "P cannot be proved in formal system S." It seems hard to deny (to us) as a result of this interpretation, that P must be true. Because if P were false, then P would be provable in system S, and we're assuming S is sound, which would mean P is true. So, by this logic, P can't be false.

However, assuming P is true and S is sound, neither P nor not-P is provable in S. This means that if we add "not P" as an axiom to S and go on making deductions in S ∪ {"not P"}, we won't reach a contradiction with the other theorems of S.

We can view this whole situation as humans having an additional, unknown set of inference rules, implemented in our brains. And these rules are what let us conclude that P must be true. We can't say beforehand what all these rules are, because we don't fully understand how we think.

Are there also Godel sentences for the way humans think? First of all, see the Berry paradox:

The Berry paradox is a self-referential paradox arising from an expression like "The smallest positive integer not definable in under sixty letters" (a phrase with fifty-seven letters).

The Berry paradox gives a warning of the challenges and contradictions that arise when trying to reason in natural language.

But, with that warning in mind, a Godel sentence for the way humans think might go something like this. A Godel sentence for arithmetic is a statement P saying, effectively, "There is no proof of P in arithmetic." Now, analogously, let R = "There can be no rational justification in the human mind to conclude R." Here we have replaced "proof in arithmetic" with "rational justification in the human mind." So at least at first glance, R kinda-sorta looks like a Godel sentence for the human mind.

If there is no rational justification to conclude R, then R must be true, by its definition. And if there is a rational justification to conclude R, then we would also have to say R is true, because we assume rational justifications are sound. So R must be true. And yet, the above seems to be a rational justification for R. So all we have is another paradox.

Answer 2

At least in the case of arithmetic, the concept of arithmetical truth can be defined as a type of non-computable extension of the Peano axiomatic system. Basically the idea is to consider the set of all well-formed formulas (WFFs) expressing arithmetical claims in first-order arithmetic (the syntax of the Peano axioms, which are expressed using the formalism of first-order logic), then consider the subset that are provably true or false using the Peano axioms and the inference rules of first-order logic, and then say that the truth-values of the remaining WFFs must respect a condition called ω-consistency, given the truth-value of the provable WWFs. This is equivalent to adding a new non-computable rule of inference, the ω-rule, to the standard inference rules of first-order logic; with this new expanded set of inference rules, it would be possible to determine the truth-value of every WFF starting just from the Peano axioms. This doesn't conflict with Gödel’s Incompleteness Theorem, since the notion of a "formal system" Gödel was using would, in modern terms, be restricted to computable rules for deducing arithmetical propositions.

To get a sense of how the ω-rule works, consider the Goldbach conjecture, which states that every even whole number greater than 2 can be expressed as the sum of two prime numbers. I would bet that someday someone will either find a proof of the conjecture that can be expressed in the Peano system, or someone will find a counter-example, but until one of those happens, there is at least the conceptual possibility of a third option: that the theorem is true, but not provable given the computable inference rules of the Peano system. But even if this were true, it is clear that for every specific even whole number N, we can use the Peano system to either prove a statement like "there exists a pair of prime numbers x,y such that N=x+y" or a statement like "there does not exist a pair of prime numbers x,y such that N=x+y". After all, for each even whole number N there are only a finite number of prime numbers smaller than N, so one only has to check a finite number of cases in order to prove one of those two types of statements.

The ω-rule says that if you have some predicate P(N), like the predicate "can either be expressed as the sum of two primes, or is not an even whole number greater than 2", and you've proved P(N) for every finite value of N, you are allowed to infer a proposition of the form "for all natural numbers N, P(N)". In this case, if the Peano axioms allowed you to prove "there exists a pair of prime numbers x,y such that N=x+y" for every even whole number N greater than 2, the ω-rule would allow you to jump from that infinite set of provable propositions to the new proposition "for all even whole numbers N which are greater than 2, there exists a pair of prime numbers x,y such that N=x+y". There may be no computable way to deduce that general proposition from the Peano axioms since a computable algorithm can't check an infinite number of cases before spitting out an answer, but it's still a mathematically well-defined inference rule. (As for 'ω-consistency', in this example it would say that if you have proven that every specific N respects the conjecture, you aren't allowed to then say the "for all even whole numbers..." proposition above is false, i.e. you can't say Goldbach's conjecture is false if there is no specific counter-example)

Beyond this specific example with Goldbach's conjecture, it's provable that all well-formed formulas in first-order arithmetic would be decidable from the Peano axioms using the combination of the inference rules of first-order logic and the ω-rule. (Assigning truth-values to all WFFs in first-order arithmetic this way would be one definition of what mathematicians call true arithmetic). This result was seen as having major philosophical significance by Rudolf Carnap; in fact the ω-rule is also sometimes called the Carnap rule, though the book Logical Empiricism at Its Peak mentions on p. 381 that Carnap was not the first to define this rule (I'm not sure whether or not he was the first to prove that true arithmetic could be derived from the Peano axioms using the rule). Carnap wanted to defend the idea that the truths of mathematics were all analytic rather than synthetic, since he and other members of the Vienna Circle advocated a view called logical empiricism (or 'logical positivism') which said an assertion could only be "cognitively meaningful" if it was either empirically testable, or could be understood as an analytic truth, like a formal logic proof of some conclusion from some premises. The logical empiricists emphatically rejected Kant's notion that mathematics could be seen as an example of synthetic a priori knowledge--in a piece describing the main views of the Vienna Circle which Carnap co-wrote, one assumption is translated here as "The fundamental thesis of modern empiricism [i.e. logical positivism] consists in denying the possibility of synthetic a priori knowledge." So if the ω-rule can be considered a type of infinitary "logical" rule (depending only on the form of the propositions, not any semantic understanding of their meaning), then in this sense all of true arithmetic can be seen as merely a type of logical deduction from the Peano axioms.

Answer 3

The theorem only shows that in any formal axiomatic system F meeting some criteria, there is a proposition G_F that is provable from the axioms if and only if ¬G_F is provable from the axioms. Therefore, the system is either inconsistent (if both are provable) or incomplete (if neither is provable).

Anyone who claims that G_F is true is not talking about the theorem any more, but about some philosophical interpretation of it. You should ask them what they mean by "true".

The standard proof of the theorem constructs a sentence that can be interpreted as saying "this sentence is not provable in F". That's true if the system is incomplete, but false if it's inconsistent. So "seeing" that it's true is equivalent to "seeing" that F is consistent. Of course, we don't know that F is consistent. We just guess that it's consistent because we've tried and failed to find an inconsistency, or because we've "proven" its consistency in some other system like ZF that may or may not be consistent. There's no theorem that says that an equally reliable guessing process can't be formalized within F, and the theorem "F is consistent if ZF is" is provable in F, so neither of these approaches shows that we're any better than F, despite what some people seem to believe.