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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to show that a theory $T$ is complete if and only if $Th(M) = T^\vdash$ for some model $M$ where $Th(M)$ denotes the set of all sentences that are true in $M$. What I have so far:

$\implies$: Let $T$ be complete. Then for every sentence $\varphi$ of the language $L$, either $T \vdash \varphi$ or $T \vdash \lnot \varphi$. If $\varphi \in T^\vdash$ then by soundness, $\varphi \in Th(M)$. If $\varphi \in Th(M)$ then since $T$ is complete, $\varphi \in T^\vdash$.

$\Longleftarrow$: Let $M$ be some model of $T$ such that $T^\vdash = Th(M)$. Let $\varphi$ be any formula of $L$. We want to show that either $T \vdash \varphi$ or $T \vdash \lnot \varphi$.

Here's where I'm stuck. How can I finish the other direction of the proof? Thanks for your help.

share|cite|improve this question
up vote 6 down vote accepted

Note that for every $\varphi$ either $M\models\varphi$ or $M\models\lnot\varphi$. If $M\models\varphi$ then $\varphi\in Th(M)=T^\vdash$ and therefore $T$ can prove it, otherwise this holds for $\lnot\varphi$.

Therefore $T$ is complete.

share|cite|improve this answer
Why do we have $M \models \varphi$ or $M \models \lnot \varphi$ for every $\varphi$? – Rudy the Reindeer Nov 21 '12 at 16:29
@Matt: You can prove this by induction on the structure of $\varphi$. For atomic formula this is by the definition of the truth in $M$ (simply check whether a relation holds or not); the connectives are simple; and for $\exists x\varphi,\forall x\varphi$ one uses the definition of $M\models\exists x\varphi$. – Asaf Karagila Nov 21 '12 at 16:32

Something seems amiss here. A theory $T$ with syntactic consequence relation $\vdash$ is complete iff for every $\varphi$ in the language of $T$, either $T \vdash \varphi$ or $T \vdash \neg\varphi$.

Suppose $T$ is an inconsistent first-order theory so for all $\varphi$, $T \vdash \varphi$. Then $T^{\vdash}$ is the set of all sentences of $T$'s language, and $T$ is trivially complete. But there is no model $M$ such that $Th(M)$ contains all those sentences.

Note that you in fact assume soundness in the first part of your proof: but that wasn't given (and completeness doesn't imply soundness).

share|cite|improve this answer
My question is about classical FOL, sorry for not mentioning it. – Rudy the Reindeer Nov 23 '12 at 8:46
And thanks for pointing out the case where $T$ is incomplete. – Rudy the Reindeer Nov 23 '12 at 8:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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