Suppose that \Gamma is TF-consistent but \Gamma is not SD-consistent. We will derive a contradiction. [\Gamma is TF-consistent] translates to [there is a tva \tau such that \tau |= \Gamma [\Gamma is not SD-consistent] translates to [\Gamma is not not SD-inconsistent]. which in turn translates to: [\Gamma is SD-inconsistent] This means we have an SD derivation: Premises \Gamma .... ..... justifications wffs " " justification \beta justifications wffs " " justification ¬\beta We have assumed there is a tva \tau |= \Gamma. By the Soundness Theorem, this 'truth' will flow through the derivation, so that \tau |= \beta and \tau |= ¬\beta. If \tau |= ¬\beta, then (\tau |= \beta) is false. This contradicts \tau |= \beta. With this contradiction we have completed the demonstration that the sentence is true.

*Comments on the strategy*
It is valuable to restate the original sentence in as concrete terms as
possible. Thus TF-consistent says a certain kind of line exists in
the truth table. SD-inconsistent means
there is a particular derivation with specific
lines (\beta and then ¬\beta).
Typically, a sentence which is keyed to a negative concept suggests one of
two strategies (which are also basic in SD and SD+).
(a) Argue towards a contradiction.
(b) Consider the contrapositive of any conditional involving negative
statements. (See the solution to (b) below, where this strategy is used.)

Suppose that \Gamma is not TF-consistent. [\Gamma is not TF-consistent] translates to [No tva \tau has the property \tau |= \Gamma] Therefore, by the usual case for empty sets, the following conditional holds: (Comment by Ganong: Whenever \tau |= \Gamma (i.e., never), ....) [If \tau |= \Gamma then \tau|= A& ¬A]. Equivalently: [\Gamma |= A& ¬A]. By the Completeness Theorem, if [\Gamma |= A& ¬A] then [\Gamma |- A& ¬A]. (comment by Ganong: On a test, I would want the derivability symbol here to have a subscript (SD, or SD+, depending on the context); it is too hard to type this in html.) So we now have [\Gamma |- AA& ¬A]. Applying ¬EL and then ¬EL on this last formula, this guaranteed derivation becomes a demonstration that [\Gamma is SD-inconsistent]. [\Gamma is not SD-consistent] translates to [\Gamma is not not SD-inconsistent]. which in turn translates to: [\Gamma is SD-inconsistent] This completes the argument that: if [\Gamma is TF-inconsistent] then [\Gamma is SD-inconsistent]. This is the contrapositive of the original sentense. As such it is logically equivalent and both sentences are true.

Suppose that \alpha is a tautology and \Gamma is a set of sentences.

Every tva \tau |= \alpha.

Therefore if \tau|= \Gamma then \tau|= \alpha.

This means that \Gamma |= \alpha.

By completeness, \Gamma |- \alpha.

This means that \alpha is a SD-theorem of \Gamma.

This is just a special case of (c). The same argument works, without reference to whether \Gamma is SD-consistent.

Consider an example with only one letter A. {This a good strategy in any case where you are not even sure what the sentencesmeans.} In terms of a single letter A, we have the following examples of wffs: contingent: {A, \not A, A -> ¬A, ... }; not contingent: tautologies { Av¬ A, A->A, ... }; contradictions { A&¬ A, ... }. The sentence proposes that some set of sentence \Gamma will give derivations of {A, ¬A, ... } but not { Av¬A, A->A, ... } or { A&¬A, ... }. We now see two very real problems: If \Gamma|- A and \Gamma|- ¬ A, then \Gamma|- A&¬ A. because of the &I rule. Every set \Gamma gives derivations of tautoligies: \Gamma|- Av¬A. Each of these events is the evidence we need to conclude the statement is false.

This is a good example for considering the contrapositive: If [\Gamma is not SD+-consistent] then [every sentence is an SD+-theorem of \Gamma]. Equivalently, this says: If [\Gamma is SD+-inconsistent] then [every sentence \alpha is an SD+-theorem of \Gamma]. We now translate to see what this means. Suppose [\Gamma is SD+-inconsistent]. This means we have an SD derivation: Premises \Gamma .... ..... justifications wffs ." " justification \beta justifications wffs ." " justification ¬\beta With this derivation in front of us, and any wff \alpha, we can just patch on the lines: Assumption +- ¬\alpha R | \beta R +- ¬\beta ¬ ER \alpha This new longer derivation demonstrates that [\Gamma|- \alpha]. Equivalently [every sentence \alpha is an SD+-theorem of \Gamma]. This completes the demonstration of the contrapositive of the original sentence.## Section 5.6.6 (g) Page 222:

There is a set \Gamma with no SD+-theorems.

FalseLook at the argument for (c). By the same argument applied to any \Gamma, all tautologies such as

A v ¬A are SD-theorems of \Gamma.

## Section 5.6.6 (h) Page 222:

If SL is the set of SD+theorems of \Gamma then \Gamma must be SD+ inconsistent.

TrueSuppose all wffs of SL are SD+-theorems of \Gamma. In particular, A & ¬A is an SD+-theorem of \Gamma. We have

Premises \Gamma .... ...... justifications wffs ." " justification i A & ¬A Add the two additional lines &EL i A \alpha &ER i ¬A ¬\alphaThis completes a demonstration that \Gamma is SD+-inconsistent.

## Section 5.6.6 (i) Page 222:

If \Gamma |- P v (R -> ¬Q) then \Gamma |- P v (¬R v ¬Q).

TrueAssume \Gamma |- P v (R -> ¬Q). We have two options.

(i) We take the guaranteed SD-derivation of P v (R -> ¬Q) and graft on the derivation (in SD) starting with P v (R -> ¬Q) and ending with P v (R -> ¬Q). [You can figure one out - using vE and ¬E etc.]

(ii) We can use soundness to get: \Gamma |= P v (R -> ¬Q).

Then use truth tables to check that [ {P v (R -> ¬Q)}|= P v (¬R v ¬Q) ]. Therefore \Gamma |= P v (¬R v ¬Q). Finally completeness gives the desired fact: \Gamma |- P v (¬R v ¬Q)

## Section 5.6.6 (j) Page 222:

The rule of De Morgan is dispensible in SD+.

TrueA rule is

dispensibleif we can prove the same theorems without this rule (we just happen to need longer derivations).Assume that \Gamma |- \beta in SD.

By soundness \Gamma |= \beta (in SL).

By Completeness of SD \Gamma |- \beta using just rules of SD.We conclude that every rule in SD+ is dispensible.

However the rules of SD+ sure are nice: they let us find proofs in a reasonable time!

## Section 5.6.8 (b) Page 222:

If { } |= \alpha then \Gamma |= \alpha.

TrueSuppose { } |= \alpha. By Completeness, { } |- \alpha.

(no premises) justifications wffs ." " justification i \alpha If we just graft on the set \Gamma as premises, this is still a derivation:Premises \Gamma justifications wffs ." " justification \alphaThis completes the proof that \Gamma |= \alpha.

## Section 5.6.8 (c) Page 222:

If there is a tva which satisfies \Gamma but does not satisfy \alpha, then \alpha is not SD-derivable from \Gamma.

TrueSuppose there is a tva which satisfies \Gamma but does not satisfy \alpha.

This means that not[ \Gamma |= \alpha].,br> By the contrapositive of soundness, not [ \Gamma |- \alpha].

Back to 2090 Home Page