4

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. – Keelan 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. – Keelan Aug 26 '15 at 19:55
  • Yep, that's correct. Congratulations! – Keelan Aug 27 '15 at 19:47
5
  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.

3

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.

Added due to @Keelan's remark.

ad your first question: Yes, your are right.

ad your second question: If no element x exists with F(x) true then for all elements x the property F(x) is false, hence ¬F(x) is true.

  • I'm voting this down because it's a direct answer to a homework question and doesn't answer the questions 1 and 2 from the question. – Keelan Aug 24 '15 at 20:55
  • @Keelan I added the answers you are missing. Is it unwanted to answer homework questions? – Jo Wehler Aug 24 '15 at 21:05
  • There are different on that, but it is commonly frowned upon. Personally, I always prefer to give a hint. I removed the downvote because you added answers to the questions in the OP, for which thanks. – Keelan Aug 24 '15 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.