Assume Negation for Proof by Contradiction

Question

I have a bunch of rules, which essentially entail that some proposition P can never be true. I now have to prove that P is false using Coq. In order to do so on paper, I would assume that P holds and then arrive at a contradiction, thereby proving that P cannot hold.

I'm not quite sure how to assume that P holds for this proof, which is what I seek help with. My current code:

Variables {…} : Prop.
Hypothesis rule1 : … .
Hypothesis rule2 : … .
.
.
.
Hypothesis rule6 : … .
Variable s : P. (* Assume that P holds for proof by contradiction *)
(* other Coq commands *)
(* proof is done *)

Could someone please confirm whether I'm going about this the right way (else, how should I be doing this?)?

Ptival Ptival · Accepted Answer · 2012-09-26T21:02:48

What you want to do is to prove:

Theorem notP := ~ P.

which boils down to:

Theorem notP := P -> False.

So, with a variable of type P, you need to prove the goal False.

I believe the way you're doing it is acceptable, though you probably want to put that Variable s : p. in a section, so that you can never reach to that s in other places where you wouldn't want to...

Section ProvingNotP.
Variable p : P.
Theorem notP: False.
Proof. ... Qed.
End ProvingNotP.

I think this should work.

Assume Negation for Proof by Contradiction

1 Answers