I'm revising counterexamples for my logic exam next term, and one of them has me absolutely stumped. I have to provide a counterexample to refute the following claim:

∀x∃yPxyy v ∃x¬∃y∃zPxyz is logically true

The solutions say that the answer is:

Domain of discourse: {0, 1}
|P| in the L2-structure: {<0, 0, 1>, <1, 0, 1>}

Now, I can see that to refute the claim you have to show that there is a structure where both sides of the disjunction are false, and I can see how the first half of it is made false, but the negation of the existential in the second half is confusing me a lot - I can't wrap my head around the concept of it. Why is <1, 0, 1> impossible for the second half to yield in this domain of discourse?

Any help would be greatly appreciated.


Consider Px01; it is clearly true for both cases : x=0 and x=1, i.e. for all elements of the domain.

Thus, ∀x∃y∃zPxyz is true. But this is equivalent to : ¬∃x¬∃y∃zPxyz which is the negation of the right disjunct.

  • Why are the two equivalent?
    – user18883
    Jan 8 '16 at 22:02
  • @user18883 because : "all crows are black" means "does not exist a crow that is not black". Jan 8 '16 at 22:05
  • Ahhh yes I see. So how would I deduce from just the original question that it was <1, 0, 1> specifically that would disprove the right disjunct?
    – user18883
    Jan 8 '16 at 22:17
  • Ah, no, don't worry, I get it. Thank you for your help!
    – user18883
    Jan 8 '16 at 22:31

The second half is saying that for some object x, the relation P is never instantiated with x as the first term (there are no y and z such that Pxyz). To refute the claim just make sure that P applies to all possible objects as first terms. Here P is instantiated for both 0 and 1 as first terms so the model indeed refutes the claim.

You can view the negation as applying to both existentials combined (it's not true that there exists a y and a z such that...).

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.