Tell me more ×
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.

Is the completeness theorem for first order logic relevant to the following theorem?

Let $S$ and $T$ be two sets of sentences in the language of set theory, and suppose, for some class $M$ we can prove from $T$ that $M\neq0$ and $M$ is a model for $S$. Then $\operatorname{Con}(T)\to \operatorname{Con}(S)$.

If $S$ were inconsistent we could prove $\phi\wedge\neg\phi$ for some (or any) sentence $\phi$. Then, arguing from $T$, we can prove $S$ is true in $M$ and hence $\phi^{M}\wedge\neg\phi^{M}$, which would be a contradiction. Hence $T$ is inconsistent.

The second sentence of this proof is really what confuses me. I feel like there is a “provable$\Rightarrow$ true” application somewhere here (if $S\vdash\phi$ and $S\vdash\neg\phi$ then $\phi$ and $\neg\phi$ are true in any interpretation that makes all sentences of S true). But this does not hold for second order logic (if $S$ is ZF for instance, or $\phi$ quantifies over subsets), or does it? Maybe I'm missing something simple.

share|improve this question
There's no second-order logic here: ZF is a first-order theory, and quantifying over sets is first-order in ZF. – Zhen Lin Dec 13 '12 at 8:17
1  
Informally, the argument is simply that if $S$ is inconsistent, it has no model, so if $T$ proves that $S$ has a model, $T$ must also be inconsistent. – Brian M. Scott Dec 13 '12 at 8:21
Ok, so let's walk through that line in the proof. Assume S⊢ϕ and S⊢¬ϕ. T proves S is true in M, hence ϕ and ¬ϕ are true in M by completeness theorem. But then M cannot be a model of S. So T proves both S is true in M, and S is not true in M. Thus T inconsistent. Could you alternatively just use "true⇒ provable" to say that T proves ϕM∧¬ϕM and be done? – David L. Dec 13 '12 at 8:30

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.