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.

In pretty much any Model Theory or Logic textbook you will find the following claim, where $T$ is a theory (a set of $\mathsf{L}$-sentences),

$T$ is consistent if and only if $T$ is satisfiable.

Sometimes it is proved and sometimes it is not, I have read the proof from a few books and I have tried to shorten it as much as possible to what follows,

Assume to the contrary that there exists a theory $T$ such that $T$ is consistent and $T$ is not satisfiable. Since $T$ is not satisfiable, there does not exist any models $\mathcal{M}$ of $T$. So, any $\mathsf{L}$-structure which attempts to model $T$ is a model of $\perp$. Then, $T \vDash \perp$ so by the Completeness Theorem, $T \vdash \perp$; yet this contradicts the assumption that $T$ us consistent. Therefore, $T$ is consistent if and only if $T$ is satisfiable.

My question is as to why we can make the jump from "there does not exist any models of $T$", to "every model of $T$ is a model of $\varphi \wedge \neg \varphi$."

I thought I understood this stuff, but I am reviewing Godel's Completeness Theorem, the Compactness Theorem, and a couple related corollaries and found myself confused on this point. I'm sure it is very simple, but I thought I'd ask. Thanks.

EDIT: In some of the comments it has been indicated that the proof is circular because it uses the completeness theorem but is attempting to prove that direction. I will literally quote exactly from David Marker's, "Model Theory: An Introduction"

Corollary: $T$ is consistent if and only if $T$ is satisfiable.

Proof:

Suppose that $T$ is not satisfiable. Because there are no models of $T$, every model of $T$ is a model of $(\phi \wedge \neg \phi )$. Thus, $T \vDash (\phi \wedge \neg \phi)$ and by the Completeness Theorem $T \vdash (\phi \wedge \neg \phi)$

What is the difference between Marker's proof than the one I gave?

share|improve this question
1  
Why would you think you can't? And furthermore, the negation of such a statement would be obviously false. (since it starts with "there exists a model of T such that....") –  Hurkyl Mar 24 '12 at 0:23
1  
It might help you to rephrase "For every model X of T, <comment about X>" into "For every X, if X is a model of T, then <comment about X>". (assuming, of course, you are comfortable with vacuous implications) –  Hurkyl Mar 24 '12 at 0:27
2  
One direction is easy: If $T$ is satisfiable then $T$ is consistent. The other direction is the Completeness Theorem, definitely not easy since we have to construct a model from syntactic elements. –  André Nicolas Mar 24 '12 at 0:56
2  
The larger problem in your proof is that you are proving the completeness theorem ("if $T$ is consistent then $T$ is satisfiable") and you use the completeness theorem in contrapositive form in the middle of the proof... –  Carl Mummert Mar 24 '12 at 0:56
1  
@Samuel: I think the reason people are objecting is that many people consider that "consistent => satisfiable" is the Completeness Theorem. It looks like the textbook you're quoting from proves an equivalent statement to be the Completeness Theorem (for all statements $\phi$ and sets of statements $T$, we have $T \vDash \phi$ implies $T \vdash \phi$) and then uses it to get a one-line proof of "consistent => satisfiable". The hard work goes into the proof of the Completeness Theorem. –  Ted Mar 24 '12 at 4:39

1 Answer 1

up vote 1 down vote accepted

In order to grasp the fact that there are two equivalent versions of the same theorem, I think it can be useful to review the details of a typical proof of it. See Joseph Shoenfield, Mathematical Logic (1967), page 43 :

Completeness Theorem (First Form : Gödel). A formula $A$ of a theory $T$ is a theorem of $T$ iff it is valid in $T$ [see page 22 : By a model of a theory $T$, we mean a structure for $L(T)$ in which all the non-logical axioms of $T$ are valid (true). A formula is valid in $T$ if it is valid in every model of $T$; equivalently, if it is a logical consequence of the nonlogical axioms of $T$.]

This theorem has a second form, which concerns consistency.

Completeness Theorem (Second Form). A theory $T$ is consistent iff it has a model.

We first show that the second form of the completeness theorem implies the first.

In view of the closure theorem and its corollary, it suffices to prove the first form for a closed formula $A$.

By the corollary to the reduction theorem for consistency [see page 42], $A$ is a theorem of $T$ iff $T \cup \{ \lnot A \}$ is inconsistent.

By the second form of the completeness theorem, this holds iff $T \cup \{ \lnot A \}$ has no model. Now since $A$ is closed, a model of $T \cup \{ \lnot A \}$ is simply a model of $T$ in which $A$ is not valid. Hence $A$ is a theorem of $T$ iff $A$ is valid in every model of $T$.

share|improve this answer

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.