0
$\begingroup$

Gödel’s first incompleteness theorem (GT1) states that for every algorithmic set of axioms (AlgoS) capable of expressing basic arithmetic, there exists a true arithmetical statement GS (the Gödel statement of S) that AlgoS cannot prove. This immediately implies that no AlgoS can imply GT1 soundly. For since GT1 implies the truth of GS for every AlgoS, if an AlgoS proved GT1 it would imply the truth of its own GS, and this is exactly what GT1 (and GS itself) states that AlgoS cannot do. (This can easily be shown formally in several ways.)

The above result has an important philosophical consequence. Gödel himself, and then others (including Roger Penrose) later, tried to show that GT1 somehow implied that human mathematical thinking has a significant non-algorithmic component. These attempts are widely held to have been unsuccessful. Result (1) above, however implies directly that if human mathematicians have in fact ever proven GT1 soundly, the thought processes involved cannot properly be modeled as entirely algorithmic. Result (1) thus lets us recognize that the existence of such proofs directly implies the existence of mathematically significant non-algorithmic aspects of human mathematical thought.

$\endgroup$
2
  • 1
    $\begingroup$ This argument is incorrect, and based on a common misreading of the first incompleteness theorem. Using your terminology, Godel shows that every consistent algorithmic set of axioms capable of expressing basic arithmetic is incomplete. Plenty of theories (for example, ZFC is massive overkill here) suffice to prove the incompleteness theorem, but they don't prove their own consistency so there is no tension here (cf. Godel's second incompleteness theorem). $\endgroup$
    – Noah Schweber
    Sep 1, 2022 at 4:36
  • $\begingroup$ An inconsistent system is not an algorithm. I am using the word in the standard logical sense: "A precisely described routine procedure that can be applied and systematically followed through to a conclusion." (Concise Oxford Dictionary of Mathematics, 4th edition (New York: Oxford U. Press, 2009)). $\endgroup$
    – Neil Sims
    Sep 2, 2022 at 5:48

1 Answer 1

Reset to default
0
$\begingroup$

Yes. The first line should have read "for every consistent algorithmic set. . ." This is needed not only for the sentence as a whole to be correct (as per the commentator's comment), but also for the truth of the expression "imply GT1 soundly." Sorry about that. With this correction, the rest of the argument should hold (since proofs by necessarily inconsistent axiom sets, although potentially valid, will not be sound")

$\endgroup$
1
  • $\begingroup$ An inconsistent system is not an algorithm. I am using the word in the standard logical sense: "A precisely described routine procedure that can be applied and systematically followed through to a conclusion." (Concise Oxford Dictionary of Mathematics, 4th edition (New York: Oxford U. Press, 2009)). $\endgroup$
    – Neil Sims
    Sep 2, 2022 at 5:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .