# another derivation

• Mar 9th 2010, 10:29 PM
sfitz
another derivation
The problem:

Show that the set $\{\neg(p\rightarrow q), \neg(q\rightarrow r)\}$ is inconsistent.

The hint is to show that $\neg(q\rightarrow r)\vdash q$ and $\neg(p \rightarrow q)\vdash \neg q$

And of course the hint totally makes sense but I just cannot do it! I feel like I've played around all day with the three axioms and MP and tried using the deduction theorem and deriving things from the empty set and trying to reverse engineer the derivation and UGH! I don't understand how to do these things, is there like a method to figuring it out or is it just reverse engineering and trial-and-error or what?

Any help or hints or anything will be MUCH appreciated!
• Mar 10th 2010, 05:16 AM
emakarov
Here is an outline that uses Deduction Theorem (DT). I assume that (not p) is an abbreviation for (p -> false). If negation is a primitive connective (i.e., not an abbreviation for anything), then some steps below need to be adjusted.

Code:

(1) not q        assumption
(2) q            assumption
(3) false        (1), (2), MP
(4) r            (3), EFQ
(5) q -> r      (2), (4), DT; close assumption (2)
(6) not (q -> r) assumption
(7) false        (5), (6), MP
(8) not (not q)  (1), (7), DT; close assumption (1)
(9) q            (8), DNE (double-negation elimination)

• Mar 10th 2010, 07:40 AM
sfitz
We aren't using truth values because with our notation, $\vdash$ means that there is a formal derivation only, while $\models$ means that it's a logical consequence (using truth values). So like the $\vdash$ means you can play around with the shape of the formula only. (At least, in my understanding but obviously I'm a n00b!)

Also how can you assume q and not q? I think the only thing we are allowed to assume is $\neg(q\rightarrow r)$ and then put that in the axioms somehow. Also we don't have the ability to get rid of double negations either.

I'm sorry! Is there something that I'm just not understanding?
• Mar 10th 2010, 08:01 AM
Plato
You understand that we do not have your particular text material.
However, as I read the question here is my take.
$\neg \left( {p \to q} \right) \equiv p \wedge \neg q$
By simplification $\neg q$.
Likewise, $\neg \left( {q \to r} \right) \equiv q \wedge \neg r$
By simplification $q$.
• Mar 10th 2010, 08:06 AM
emakarov
Quote:

We aren't using truth values
I am not talking about truth values either. Everything I wrote above is about derivations.

Since you mentioned the three axioms, MP and the Deduction Theorem, I assume you are using Hlbert-style derivations (see in particular the three axioms -- are they the same that you are using?). Hilbert system is easy to study but hard to use in practice. To construct a complete derivation of the required formula is pretty hard, so I am describing how to build it in theory without actually building it.

In particular, DT is very convenient, but note that this is not a primitive inference rule. It is an algorithm describing how to construct a derivation of $\Gamma\vdash p\to q$ from $\Gamma,p\vdash q$. By looking into the proof, one can actually build the required derivation in every concrete instance, but this is rarely done.

Similarly for DNE: this is not a primitive rule, but for each formula $p$ there is a derivation of $\neg\neg p\to p$. This derivation can be incorporated into bigger derivations.

Quote:

Also how can you assume q and not q?
By using DT. By assuming $q$ and deriving $r$ I mean deriving $q\vdash r$. Then you apply the DT to obtain a derivation of $\vdash q\to r$, where the assumption $q$ is no longer present (it is said to be closed).

Applications of DT can be nested. You can have the following sequence: (1) assume $p$, (2) assume $q$, (3) derive $p, q\vdash r$, (4) apply DT to get $p\vdash q\to r$, (5) continue this derivation to get $p\vdash r'$, (6) apply DT to get $\vdash p\to r'$.
• Mar 10th 2010, 08:12 AM
sfitz
Okay, that makes a lot more sense. I was definitely confused when you said something about not p being the same as p --> false. Those are the axioms that we're using! It's so much easier to find other sources online now that I know the name. For some reason we haven't mentioned the name Hilbert at all in the book, but from what I've looked at so far, that's what it is. It's really helpful to know that you can use nested DTs too. Thank you so much!