Urgent Help Given p ⇒ q, use the Fitch System to prove ¬q ⇒ ¬p.

132 Views Asked by At

I think I'm close but I don't know what to do next. Help, please. All I've done is this:

1.p=>q Premise

2.~q assumption

3.p assumption

4.q implication elimination 1,3

5.q&~q and introduction 2,4

I tried with "negation introduction" 3,5 but I can't.

Here is the link of the exercise. http://intrologic.stanford.edu/exercises/exercise_04_10.html

1

There are 1 best solutions below

5
On BEST ANSWER

We need to prove of $p \to q \vdash \sim q \to p$.

As our goal has $\to$ as its main logical connective, we will use Conditional Introduction. In your system, has the following format:

$$\phi \vdash \psi \\ \overline{\phi \to \psi}$$

Now, we have to provide a proof of $\sim q \vdash \sim p$. To accomplish it, assume $\sim q$ and derive $\sim p$.

$ \def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} \def\Ae#1{\qquad\mathbf{\forall E} \: #1 \\} \def\Ai#1{\qquad\mathbf{\forall I} \: #1 \\} \def\Ee#1{\qquad\mathbf{\exists E} \: #1 \\} \def\Ei#1{\qquad\mathbf{\exists I} \: #1 \\} \def\R#1{\qquad\mathbf{R} \: #1 \\} \def\ci#1{\qquad\mathbf{\land I} \: #1 \\} \def\ce#1{\qquad\mathbf{\land E} \: #1 \\} \def\ii#1{\qquad\mathbf{\to I} \: #1 \\} \def\ie#1{\qquad\mathbf{\to E} \: #1 \\} \def\be#1{\qquad\mathbf{\leftrightarrow E} \: #1 \\} \def\bi#1{\qquad\mathbf{\leftrightarrow I} \: #1 \\} \def\qi#1{\qquad\mathbf{=I}\\} \def\qe#1{\qquad\mathbf{=E} \: #1 \\} \def\ne#1{\qquad\mathbf{\neg E} \: #1 \\} \def\ni#1{\qquad\mathbf{\sim I} \: #1 \\} \def\IP#1{\qquad\mathbf{IP} \: #1 \\} \def\x#1{\qquad\mathbf{X} \: #1 \\} \def\DNE#1{\qquad\mathbf{DNE} \: #1 \\} $ $$ \fitch{p \to q}{ \fitch{\sim q}{ \vdots\\ \sim p }\\ \sim q \to \sim p }\\ $$

In order to derive $\sim p$, we would need to use Negation Introduction. In your system, has the following format:

$$\phi \to \psi \\ \underline{\phi \to \sim\psi} \\ \sim \phi$$

So, in your example, we need provide to proofs: $p \to q$ and $p \to \sim q$. We already have $p \to q$ as one of the premises, we would set-up the proof of $p \to \sim q$:

$$ \fitch{p \to q}{ \fitch{\sim q}{ \fitch{p}{ \vdots\\ \sim q }\\ \sim p }\\ \sim q \to \sim p }\\ $$

In full:

$$ \fitch{1.\, p \to q}{ \fitch{2.\, \sim q}{ \fitch{3.\, p}{ \fitch{4.\, q}{ 5.\, q \R{4} }\\ 6.\, q \to q \ii{4-5} \fitch{7.\, q}{ 8.\, \sim q \R{2} }\\ 9.\, q \to \sim q \ii{7-8} 10.\, \sim q \ni{6,9} }\\ 11.\, p \to \sim q \ii{3,10} 12.\, \sim p \ni{1,11} }\\ 13.\, \sim q \to \sim p \ii{2,12} }\\ $$