Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|cite|improve this question

marked as duplicate by Asaf Karagila, Andrés Caicedo, Norbert, Thomas, J. M. is back. Oct 5 '12 at 13:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Re-read the incompleteness theorems ;) –  Clive Newstead Oct 3 '12 at 17:13
Long story short: "complete" has at least two meanings. –  Trevor Wilson Oct 3 '12 at 17:19
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. –  Michael Greinecker Oct 3 '12 at 17:21
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! –  Arthur Fischer Oct 3 '12 at 17:27
@AndréNicolas I slap my forehead and stad corrected. –  Michael Greinecker Oct 3 '12 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.

share|cite|improve this answer

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.