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

Question

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.

Answer 1

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.

Answer 2

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.