1
$\begingroup$

Ok so i was given the following problem: if $\Sigma \vdash \psi $ then the set $\Sigma\cup${$\lnot\psi$} is not consitent .Prove it by using only the theorems of completeness and correctness

which basically say that: $\Sigma \vdash \psi \Leftrightarrow \Sigma\vDash\psi$ or in other words: when a set of types $\Sigma$ is consistent its also satisfiable and backwards

Any ideas??? Remember we cannot use proof by contradiction, we want to prove by using only the above theorems.

$\endgroup$
  • $\begingroup$ What is $[\psi]$? $\endgroup$ – Wojowu Jan 17 '16 at 14:18
  • $\begingroup$ i added parentheses now, is it better? Makes sense to you? $\endgroup$ – Aggelos Sfakianos Jan 17 '16 at 14:20
  • 3
    $\begingroup$ $\{\psi\}$ would make it even clearer. However, don't you mean that this set is consistent? The problem as written is incorrect. $\endgroup$ – Wojowu Jan 17 '16 at 14:21
  • $\begingroup$ no its not. I say if $\Sigma \vdash \psi$ is true , then the set created out of union of $\Sigma$ and $\psi$ is not consistent $\endgroup$ – Aggelos Sfakianos Jan 17 '16 at 14:28
  • 1
    $\begingroup$ This is wrong in that case. Provided $\Sigma$ is itself consistent, then adding any statement which it proves won't make it inconsistent. $\endgroup$ – Wojowu Jan 17 '16 at 14:40
1
$\begingroup$

Thanks to completness and correctness, your problem is equivalent to showing that if $\Sigma\models\psi$ then $\Sigma\cup\{\neg\psi\}$ is not satisfiable. Both of the statements "$\Sigma\models\psi$" and "$\Sigma\cup\{\neg\psi\}$ is not satisfiable" assert, by definition, that certain sorts of models cannot exist. Write out and compare what those sorts of models are, and you'll have your proof.

$\endgroup$
  • $\begingroup$ what do you mean by models?? i am even more confused now... give me an example at least.... thanks $\endgroup$ – Aggelos Sfakianos Jan 17 '16 at 15:22
  • 1
    $\begingroup$ If you don't know what models are, then what do you mean by "$\Sigma\models\psi$ and what do you mean by "satisfiable"? The usual definitions of those concepts involve models. $\endgroup$ – Andreas Blass Jan 17 '16 at 15:24
  • 1
    $\begingroup$ by model you mean valuation $\upsilon$?? $\endgroup$ – Aggelos Sfakianos Jan 17 '16 at 15:28
  • $\begingroup$ Aha! It seems you're asking only about propositional logic, not first-order logic. In that case, yes, substitute "valuation" for "model". ("Model" would be the appropriate concept in first-order logic, where the same result holds.) $\endgroup$ – Andreas Blass Jan 17 '16 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.