5
$\begingroup$

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?

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

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Cort Ammon Dec 8 '15 at 0:53
5
$\begingroup$

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})$.

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

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.