5

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
4
  • 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
    Commented Aug 26, 2015 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
    Commented Aug 26, 2015 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
    Commented Aug 26, 2015 at 19:55
  • Yep, that's correct. Congratulations!
    – user2953
    Commented Aug 27, 2015 at 19:47

2 Answers 2

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.

3
  • 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.
    – user2953
    Commented Aug 24, 2015 at 20:55
  • @Keelan I added the answers you are missing. Is it unwanted to answer homework questions?
    – Jo Wehler
    Commented Aug 24, 2015 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.
    – user2953
    Commented Aug 24, 2015 at 21:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .