Question

prove using the Hilbert System

{¬q} ⊢ (p→q)→(¬p)

This means that I can assume (¬q) and must prove (p→q)→(¬p)

The only things I have available to me are these axioms
A1 (A -> (B->A))
A2 ((A -> (B->C)) -> ((A->B)->(A->C)))
A3 (((~A) -> (~B)) -> (B->A))

and modus ponens which states if we have A->B and A we can infer B

I can't use any other theorems only these axioms

Answer 1

I've spent a long time trying to find this proof and I think I have it to the point where all I need to prove is just the (¬p) part

Answer 2

do u know the Deduction Theorem

Answer 3

I do know it, but I can't use it unless I can derive it using the axioms

Answer 4

I have used the axioms to the point where I can assume (p→q) though

Answer 5

the deduction them says then if \(\Sigma\cup\{\psi\}\vdash\phi\) then
\(\Sigma\vdash(\psi\to\phi)\)

Answer 6

yeah, but I need to prove this explicitly with the whole thing being a line of steps applying only the axioms and modus ponens

my prof implied that there was a way to get the result of the deduction theorem with only the axioms though

Answer 7

ok. i get it.

Answer 8

can u post the proof u have so far?

Answer 9

sorry. but i can't figure it out.

Answer 10

well I found a problem with what I have

Answer 11

me either really

Answer 12

I keep trying to simplify down to well I have (¬q) →(¬p) somehow

Answer 13

but I really just can't make it there

Answer 14

all I can get to is ((¬¬q)→(¬¬p))→((¬q) →(¬p)) A3

Answer 15

but I don't know how I can get to ((¬¬q)→(¬¬p)) so I can modus ponens it away

Answer 16

i was trying to the same

Answer 17

there was a more involved way of getting there, but I have to use other proofs as theorems

Answer 18

and those theorems used the deduction theorem

Answer 19

which meant I couldn't do them in line with everything else like they wanted me to

Answer 20

this proofs can be very exasperating.

Answer 21

yes they can. I've spent more hours than I should have on this one. It's my first one too, so I thought I may have overlooked some way to use the axioms

Answer 22

there are 2 others that I'm stuck on too.

⊢ ((¬p)→p)→p

and

⊢ p→(¬¬p)

do you think you could maybe take a stab at these ones too?

Answer 23

I don't feel like I'm going to be able to get the first one

Answer 24

when is your homework due?

Answer 25

tomorrow night at midnight.

Answer 26

so u have a whole day

Answer 27

well I have a midterm to study for on thursday, so I was hoping to finish it tonight.

Answer 28

i understand

Answer 29

Thanks for your help though, I really appreciate it. Working on these by myself for so long hasn't been very pleasant haha