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 am sure I have made a gross misunderstanding of Gödel's completeness theorems, as to me, it seems to follow that all sets of formulas are consistent.

Let $\Gamma$ be a set of formulas. If $\Gamma\vdash\psi$, then by Gödel's completeness theorem, $\Gamma\models\psi$.

Then $\Gamma\not\models(\neg\psi)$.

By Gödel again, $\Gamma\not\vdash(\neg\psi)$.

Hence, $\Gamma$ is consistent.

I am pretty sure there is a flaw in the above argument, but I can't quite pinpoint it.

Any help is sincerely appreciated!

share|improve this question
4  
I think that if $\Gamma$ is inconsistent, then both $\Gamma\models\psi$ and $\Gamma\models\lnot\psi$ hold trivially. –  Marc van Leeuwen Apr 26 '13 at 9:38
add comment

3 Answers

up vote 14 down vote accepted

Two things.

First of all, $\Gamma \vdash \psi$ implying $\Gamma \models \psi$ is known as the Soundness Theorem for the proof system $\vdash$ (i.e., "true premises do not prove false conclusions").

Now on your purported proof, the flaw occurs at "Then $\Gamma \not\models (\neg \psi)$". Namely, $\Gamma \not \models (\neg\psi)$ can only be valid if there is a model of $\Gamma$ in which $\neg \psi$ is false. In particular, we have tacitly assumed existence of a model of $\Gamma$ in the first place.

Thus your proof is circular.

share|improve this answer
add comment

If $\Gamma$ is inconsistent to begin with then it has no models. Therefore $\Gamma\models\psi$ holds vacuously, for every $\psi$.

In particular it follows that if $\Gamma$ is inconsistent then $\Gamma\models\lnot\psi$, contrary to your "proof".

That is, the step $(\Gamma\models\psi)\rightarrow(\Gamma\not\models\lnot\psi)$ requires the assumption that $\Gamma$ is consistent, and therefore resulting in circularity.

share|improve this answer
add comment

Check the second step. $\Gamma \not ⊨ \phi$ means there is a model of $\Gamma$, which cannot happen if $\Gamma$ is inconsistent.

share|improve this answer
3  
Thanks for not reading my answer and Asaf's answer, in which precisely this is remarked. –  Lord_Farin Apr 26 '13 at 22:28
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.