4
$\begingroup$

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.

2 Answers 2

6

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.

  • 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$.2012-11-21
3

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

  • 0
    And thanks for pointing out the case where $T$ is incomplete.2012-11-23