Take the 2-minute tour ×
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.

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|improve this question
add comment

2 Answers

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|improve this answer
    
Why do we have $M \models \varphi$ or $M \models \lnot \varphi$ for every $\varphi$? –  Matt N. Nov 21 '12 at 16:29
2  
@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
add comment

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|improve this answer
    
My question is about classical FOL, sorry for not mentioning it. –  Matt N. Nov 23 '12 at 8:46
    
And thanks for pointing out the case where $T$ is incomplete. –  Matt N. Nov 23 '12 at 8:47
add comment

Your Answer

 
discard

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.