2

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?

10
  • 3
    When a statement is shown to be demonstrable, it is said to be "provable" -as the term suggest...it is provable. "Truth" here is a technical concept, meaning that something is true only under assignment (interpretation). While all "true" statements in First Order logic are provable (which coincides with your current understanding), there are some statements (like Godel's) which are "true" but not provable as they are not "universally" true, but only true in some model (and false in some model). Hence they are not "provable". Read Godel's Completeness Theorem.
    – Ajax
    Mar 31 at 17:36
  • 1
    Your assumption that mathematical propositions are only true if they are derivable from axioms is itself suspect. One way of understanding the consequence of Gödel's first incompleteness theorem is that it expresses the limitations of axiom systems.
    – Bumble
    Mar 31 at 18:08
  • 3
    Truth, in the sense you are using it here, is a semantic notion. It is not equivalent to proof as you suggest. On the other hand, (mathematical) proof is a syntactic notion. Gödel's result is essentially saying that semantics cannot be reduced to syntax.
    – nwr
    Mar 31 at 18:23
  • 1
    See Gödel’s Incompleteness Theorems for a good overview: G's sentence is not like „This sentence is false“. The gist is to find a sentence G such that neither G nor ¬G is provable in the formal system of arithmetic. Apr 1 at 5:53
  • 1
    And see Paris–Harrington theorem for a theorem regarding a certain combinatorial principle in Ramsey theory that is true but not provable in Peano arithmetic. We assert that it is true because we prove it - as per every other mathematical theorem - but the proof is not formalizable with the resources of first-order arithmetic. Apr 1 at 6:28

3 Answers 3

2

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.

5

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.

2
  • Unlike the twin-prime conjecture, heuristically the Goldbach-Hypothesis is not true with probability one. Extremely close to 1, but not 1..
    – gnasher729
    Apr 2 at 12:05
  • 1
    +1 very informative!
    – J D
    Apr 2 at 13:07
2

The theorem only shows that in any formal axiomatic system F meeting some criteria, there is a proposition GF that is provable from the axioms if and only if ¬GF 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 GF 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.

3
  • 1
    While Gödel used "truth" only for illustrative purposes in his original paper, that's mostly of historical interest. Thanks to Tarski's work that was yet to appear, proving that if PA is sound then there is a true sentence G,..... is now mathematically unproblematic and simply the semantic version of the theorem. The philosophical implications of this fact may of course be less obvious.
    – Johannes
    Apr 1 at 6:38
  • @Johannes I don't know if you're the one who downvoted my answer, but your comment doesn't actually disagree with it. You gloss over the "if PA is sound" condition, but it's still there.
    – benrg
    Apr 1 at 7:22
  • Hi, I downvoted another answer here not this one. Not sure I understand your point, soundness is defined in terms of truth (which was given a rigorous definition by Tarski), and this is how the semantic version of the theorem is given in e.g. Peter Smith's book . You said 'ask them what they mean by "true"', and I simply pointed out what most people mean by it in logic.
    – Johannes
    Apr 1 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.