# How to deal with ¬∃ (negated existential quantifier) in a proof?

I need to prove that the following premises lead to a contradiction.

1. ∀x (P(x) → Q(x))
2. ∃x ¬Q(x)
3. ¬∃x (¬P(x))

A couple of things are confusing me.

1. Does the first premise say that if x is a P then it is a Q, meaning there can still be x's that are not Ps
2. How do I deal with ¬∃ in a logic system? I know the equivalent of premise 3 is ∀x ¬(¬P(x)), But I assume I need to prove that if I wish to use it?

What makes it more confusing is that the whole question is only for 4 marks and I cannot see a solution that will use so few steps.

After some much needed sleep, the answer came easily

``````  1. ∀x (P(x) → Q(x))   --- Premise
2. ∃x ¬Q(x)           --- Premise
3. ¬∃x (¬P(x))        --- Premise
|  4. x0 ¬Q(x0)       --- Assume
|  5.  P(x0) → Q(x0)  --- ∀x elim 1
|  |  6.  P(x0)       --- Assume
|  |  7.  Q(x0)       --- → elim 6, 5
|  |  8.  ⊥           --- ⊥ intro 7, 4
|  9.  ¬P(x)          --- ¬ intro 6 - 8
| 10.  ∃x (¬P(x))     --- ∃x into 9
| 11.  ⊥              --- ¬ elim 10, 3
12.  ⊥                 --- ∃x elim 4 - 11, 2
``````
• What's happening in steps 4 and 5? You could assume ~Q(x) based on premise 2, but not ~P(x), because the existential quantifier in premise 3 is negated. – user2953 Aug 26 '15 at 19:43
• Step 4 I introduce value to substitute in the free variables. In step 5 I assume ¬P(x0) so that I can arrive at a contradiction when I introduce the existential qualifier. This is the logic system used in "Logic in Computer Science Modelling and reasoning about systems". Previously I used Fitch, and I am really struggling with this system. – Leon Aug 26 '15 at 19:48
• Ah, now I see. There is a case distinction between 5 and 8. I can't comment on the syntax as I don't know this system. I don't see what 12 is doing however. Based on Q(x0) you cannot conclude forall x Q(x), because you don't know if Q(x1). Try instead to make premise 2 concrete by introducing a q0 for which ~Q(x0) holds. Then you can prove that ~P(x0), and thus exists x ~P(x) which is in contradiction with 3. – user2953 Aug 26 '15 at 19:55
• Yep, that's correct. Congratulations! – user2953 Aug 27 '15 at 19:47

1. Indeed. A logical implication "p → q" is true if either p is false or q is true - in other words, it is only false if p is true but q false.

This means that we can say that ∀ x; P(x) → Q(x) is equivalent to ∀ x; Q(x) ∨ ¬P(x): for every x either Q(x) has to be true or P(x) has to be false, or both.

2. In this case, you need to show that the system holds a contradiction. So, if you can arrive at ∃ x; ¬P(x), you have shown a contradiction with premise 3 and you are done.

Premise 3 is equivalent to ∀x ¬(¬P(x)), which is equivalent to ∀x P(x). With premise 1) follows ∀x Q(x), which contradicts premise 2, q.e.d.