# What does Gödel's Incompleteness Theorem prove?

Does Gödel's incompleteness theorem only prove that you can't have a formal system which describes number theory which is both complete and consistent, or is it more general? In other words: does it prove that any formal system is either inconsistent or incomplete?

• The usual axiomatizations of propositional logic are formal systems that are both consistent and complete. – MJD Dec 7 '15 at 19:58

## 2 Answers

There are formal systems that are both consistent and complete.

However, there is no formal system that has all of the following properties:

• it is strong enough to cover number theory
• it is recursively decidable whether a formula is well-formed, whether a sentence is an axiom, and whether a sequence of sentences is a proof
• the system is consistent
• the system is complete
• A useful layman's phrasing of the second bullet which I find gets close enough to the correct meaning to be useful: the system tries to prove its own correctness. – Cort Ammon Dec 8 '15 at 0:53

Not exactly. Let $L = \{+,\times, 0, 1, <\}$ and define $Th_L(\mathbb{N})= \{\varphi$ in $L$$:$ $\mathbb{N} \models \varphi \}$.

This is complete and consistent (since it clearly has a model) which encompasses arithmetic. Godel's Theorem states that this collection cannot be recursive (or even recursively enumerable), i.e. there is no finitary algorithm which tells us which sentences in $L$ are in $Th_L(\mathbb{N})$.

• The incompleteness theorem implies that $Th_L(\mathbb{N})$ is not recursively enumerable, which is a stronger statement than yours. – Rob Arthan Dec 8 '15 at 23:38
• @RobArthan: Thanks for the catch. – Kyle Dec 9 '15 at 1:27