Do Godel's incompleteness theorems create a contradiction/paradox?

Question

I have seen Godel's theorems presented as a paradox. However, I was only able to infer it's supposed to be one because it proves mathematics to be incapable to be consistent AND complete at the same time and I don't see incompleteness as detrimental/problematic.

Answer 1

The short answer is that Gödel's incompleteness theorems are not contradictory, and arguably they are not paradoxical either, except in so far as they upset our preconceptions about provability and axiomatizability. They do express important limitations on what can be proved in formal systems.

A longer answer is that Gödel's incompleteness theorems are concerned with formal systems that are capable of interpreting arithmetic and are capable of expressing formal relationships of provability or derivability. They make use of the following concepts:

• A first-order theory is a set of sentences, typically expresssed in a formal language.
• A theory is consistent if, for any sentence Φ, Φ and ¬Φ are not both provable.
• A theory is negation complete if, for any sentence Φ, either Φ or ¬Φ is provable.
• A theory is (recursively) axiomatizable if there is a decidable subset called the axiom set such that all of the sentences of the theory can be proved from that axiom set. This is logically equivalent to the property that a theory is computably enumerable or semidecidable.

Gödel's first incompleteness theorem can then be expressed as saying that no theory can have all of the following properties:

1. Consistent.
2. Negation complete.
3. Recursively axiomatizable.
4. Sufficiently strong to interpret arithmetic, specifically, at least as strong as Robinson Arithmetic (Q).

You can have any three of the four, but not all four.

The result appears paradoxical, because it seems to imply that there are statements that are true but not provable. In fact, how you interpret this result will depend on your preferred understanding of the philosophy of mathematics, and there are at least a dozen of those. Gödel himself was a mathematical platonist and he did indeed understand his result as demonstrating that there are propositions in arithmetic that are true but not provable. We could deploy a semantic theory, such as model theory, to allow us to speak of what is 'true'. Using model theory we could say that there are sentences of arithmetic that are true in the standard interpretation but unprovable. Alternatively, we could be content to say that our understanding of arithmetic is not axiomatizable. Or we could maintain that the formal version of derivability used within Gödel's proof falls short of what is provable or demonstrable in some broader sense. Or we could even reject the logic underlying Gödel's result, as the intuitionists do, and jettison the law of excluded middle.

Although there are different accounts of the implications, the theorems themselves have been proved rigorously, and have been checked by thousands of competent mathematicians, and are not disputed, except by cranks. There are also corresponding results in computability theory and in modal logic.

Answer 2

Gödel's (first) Incompleteness Theorem most definitely says that, if the usual axioms for number theory are consistent (which they are widely believed to be), then there most definitely exist true statements that cannot be proved, in that system. This much does not depend on anyone's interpretation of the result or anyone's preferred understanding of the philosophy of mathematics.

Gödel showed that in axiom systems strong enough to express basic arithmetic, there exists a valid statement P such that P means "There is no proof of me".

Now suppose such a statement were false. That would imply that there exists a proof of it. But in that case, the statement is true. In a consistent system we can't have a statement that is both true and false. Thus we have shown that, assuming a consistent system, the statement cannot be false. That leaves only the possibility that it is true, and so P is a statement that is both true and unprovable.

But note that we used meta-reasoning to reach this conclusion, so we have not proved it true within the system under discussion.