0

Prove that ∀Z · ∃Q · (p(Q) → p(Z)) ⊨ ∀Z · (∃Q · p(Q)) → p(Z) does not hold by giving a suitable structure

I am working on this problem but am frankly stumped.
I read this as "for All Z such that there exists a Q such that if p(Q) then p(Z) has equivalence to all Z such that there exists a Q if p(Z)

Is this reading of the question correct?

What would a "suitable structure" be and how would you find it?

If anyone can help it would be greatly appreciated.

Thank you.

Anand
  • 23

2 Answers2

1

The right reading would be: The statement "For all $Z$ there exists a $Q$ such that $p(Q)$ implies $p(Z)$" semantically entails "For all $Z$, if there exists $Q$ with $p(Q)$, then $p(Z)$".

Note that there is no equivalence mentioneed and semantic entailment (or consequence) means that all models with the first property also have the second property. The task is to come up with a model / structure where the first is rue and the second is not. Assume there are two obejcts $A$, $B$ with $p(A)$ and $\neg p(B)$. Then fir any given $Z\in\{A,B\}$ you can always pick $Q=B$ and from this see that the first statement is true. But for $Z=B$ we can pick $Q=A$ and see that the second statement is not true in this structure.

Hagen von Eitzen
  • 374,180
  • I am trying to understand this. If we take:

    ∀Z = “all people″

    and we look at the three cases:

    p(A) = A is a human p(A) = A is a cat p(A) = A is a female

    the first one will always be true, the second will always be false, and the third will sometimes be true and sometimes be false.

    Then the left hand side can read: For all people there exists a Q such that if Q is a female this implies all people are female.

    The right hand side is for all people there exists Q with Q being female, then all people are female.

    Is this a correct interpretation?

     – Anand Feb 25 '14 at 22:32
  • The left hand side you gave the interpretation to $(\forall Z (\exists Q P(Q))) \rightarrow (\forall P(Z))$, which is obviously not what you meant to say. I suggest: "for every person Z, there exists a person Q such that if Q is female then Z is female." – DanielV Feb 26 '14 at 02:46
  • Similar issue with the right hand side. I suggest "for every person Z, if there is any female then Z is a female". – DanielV Feb 26 '14 at 02:48
0

It's easier if you consider the three cases:

  • P is always true
  • P is always false
  • P is sometimes true and sometimes false

The left hand side is true in all cases.

The right hand side is true in the first two cases. In the third case, consider Z for which $P(Z)$ is false. There still exists a $Q$ for which $P(Q)$ holds, but $P(Z)$ is false, so you get $\text{true} \rightarrow \text{false}$. So any structure under which $P$ is sometimes true and sometimes false over your universal domain works as a counter example, such as $P(x) = 0$ for a domain of more than 1 element.

DanielV
  • 23,556