Hi guys just a quick question
Is the following true or false. give argument or counterexample, as appropriate.
{ } is an inconsistent set of sentences iff the argument from as premises to as conclusion is valid.
Thanks in advance
From left to right:
Assume {A, B ~C} is an inconsistent set of premises. Therefore (A&B&~C) is a contradiction. Therefore, ~(A&B&~C) is true, which by de Morgan's law is equivalent to ~Av~BvC. If ~A, then A, B |-- C is valid vacuously because one of the premises, A, is false. If ~B, the same applies, mutatis mutandis. If C, then the sequent is valid trivially.
From right to left:
Assume A, B |-- C is valid. Assume, for reductio, that A, B, and ~C are all true. Then, since A is true and B is true, by the validity of the sequent, C is true, which means that ~C is false, contra hyp.
Recall that consistency pertains to provability and validity pertains to entailment.
And you are familiar with the notation '|-' for "proves" and '|=' for "entails"?
Have you proven that the argument from {A B} to C is valid if and only if {A B} proves C (i.e., {A B} |= C if and only if {A B} |- C)?
(I.e., more generally, have you proven the soundness and completeness theorems for whatever system - I surmise first order logic - you're talking about?)
Suppose we have proven the soundness and completeness theorems:
Prove left to right in the problem:
If {A B ~C} is inconsistent, then {A B ~C} |- C , so, by soundness, {A B ~C} |= C.
Now, suppose, A and B are both satisfied in a model M with variable assignment v, while assuming, toward a contradiction, that C is not satisfied in M with v. Then ~C is satisfied in M with v, so {A B ~C} are satisfied in M with v, so, since {A B ~C} |= C, we have {A B ~C C} satisfied in M with v, which is impossible since no formula C and ~C are both satisfied in a model with a variable assignment.
Prove right to left in the problem:
If {A B} |= C then, by completeness, {A B} |- C, so {A B ~C} is inconsistent, since, by monotonicity, {A B ~C) |- C and {A B ~C} |- ~C.