Possible Duplicate:
What is the difference between Gödel's Completeness and Incompleteness Theorems?
what is the relationship between ZFC and first-order logic?

I am a bit confused by a few things that I have read recently.

I have read that ZFC is a first order theory and that any part of mathematics can be expressed in ZFC. Now I know that first order logic is complete, however this would seem to contradict the incompleteness theorems (with I have a basic understanding of). I was wondering where I have gone wrong?

Thanks very much for any help (sorry for the silly question)

  • 1
    $\begingroup$ Re-read the incompleteness theorems ;) $\endgroup$ Oct 3, 2012 at 17:13
  • 1
    $\begingroup$ Long story short: "complete" has at least two meanings. $\endgroup$ Oct 3, 2012 at 17:19
  • $\begingroup$ First order logic is a complete theory (I think). But ZFC consists of first order logic plus the relation $\epsilon$ and the axioms of set theory and is incomplete. $\endgroup$ Oct 3, 2012 at 17:21
  • 5
    $\begingroup$ Proof once again the Gödel was the greatest logician ever: not only did he prove an amazing theorem in his dissertation, but about two years later he proved its negation! $\endgroup$
    – user642796
    Oct 3, 2012 at 17:27
  • $\begingroup$ @AndréNicolas I slap my forehead and stad corrected. $\endgroup$ Oct 3, 2012 at 17:57

2 Answers 2


"Complete" means two different things for a logic (such as first-order-logic) versus for a theory in that logic.

A logic is complete iff: Every sentence that has no counterexample-model can be proved.

A theory is complete iff: Every sentence that has no proof-of-its-negation can be proved.

First-order logic is complete in the first sense. ZFC is (assuming it is consistent) incomplete in the second sense -- that is, there are sentences that ZFC neither proves nor disproves. That's completely compatible with the logic being complete; it just means that for each such sentence there are models of ZFC where it is true, and other models where it is false.


As in the comments is said, the word 'complete' has 2 different meanings.

That the first order logic is complete, is meant that it is complete w.r.t the corresponding first order models, that is: a formula is valid in all models iff it has a proof (a deduction consisting of finitely many formulas, using some specific deduction rules, like modus ponens..)

That ZFC is incomplete, is meant it is incomplete as an axiom system: there is a formula $\phi$ such that neither $\phi$ nor $\lnot\phi$ is not provable from ZFC. (And, in fact, it will be still incomplete if adding any more axioms).


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