2
$\begingroup$

Find a universe for variables x, y, and z for which the statement ∃x∃y∀z((x = z) ∨ (y = z)) is true and another universe in which it is false.

I'm not sure if I am approaching this question the right way, but the way I think of it is like this: say one universe is all real numbers, then the statement would be true. Now I have to find another universe where this statement is false, but I can't find any universe where this statement would be false. I might be thinking of this question the wrong way though.

$\endgroup$
  • $\begingroup$ If it were true in the real numbers, what would $x$ and $y$ be? $\endgroup$ – MJD Oct 7 '17 at 4:26
  • $\begingroup$ Why would you think the statement is true for the reals? $\endgroup$ – Graham Kemp Oct 7 '17 at 4:27
5
$\begingroup$

The statement $$\exists x\exists y\forall z\;\bigl((x = z) \lor (y = z)\bigr)$$ asserts that there exist elements $x,y$ in the universe such that, for each $z$ in the universe, either $z=x,\;\,$or $z=y,\;\,$or both (i.e., $z$ is equal to one of $x,y$).

Based on that understanding, the statement is true for a given universe if and only if the universe is nonempty and has at most two elements.

If the universe has exactly one element, $a$ say, let $x=y=a$.

If the universe has exactly two elements, $a,b$ say, let $x=a, y = b$.

In both of the above cases, the statement is true, since any $z$ would have to be equal to one of $x,y$ (there's no way $z$ can avoid that).

On the other hand, if the universe has at least $3$ elements, $a,b,c,\;$say, there's no way to choose $x,y$ so that each $z$ is equal to one of $x,y$. If such elements $x,y$ were to exist, the set $\{x,y\}$ would have at most two elements, hence the statement would be false for at least one of the test cases $z=a, z=b, z=c$.

Key point: The order of the quantifiers matters.

For example, if you change the statement to $$\forall z\exists x\exists y\;\bigl((x = z) \lor (y = z)\bigr)$$ the new statement asserts that for each $z\;$in the universe, there exist elements $x,y\;$in the universe such that $x=z,\;$or$\;y=z,\;\,$or both.

But the new statement is true in any universe since, for any choice of $z$, we can simply choose $x=z,\;$and then for $y$, we can choose any element of the universe (e.g., $y=z$).

$\endgroup$
  • $\begingroup$ By th OPs comment I suspect the confusion comes from ignoring the order of the quantifiers, and actually they reasoned starting from the universal quantifier, i.e. "for all z there exists at least ...". Maybe you could highlight that the order of the quantifiers makes all the difference. $\endgroup$ – Rolazaro Azeveires Oct 7 '17 at 8:57
  • 1
    $\begingroup$ Good suggestion. I edited my answer to address that point. $\endgroup$ – quasi Oct 7 '17 at 9:12
  • $\begingroup$ Yeah I was having a lot of trouble with the order of the quantifiers and figuring out if they mattered or not. I really appreciate the help but I'm still a bit confused on why the statement would be true if ∀z was in the front as opposed to the back. $\endgroup$ – Spectre Oct 7 '17 at 20:35
  • $\begingroup$ Because if $\forall z$ was first, then for each $z$, the choice of $x,y$ is allowed to depend on the selected $z$, since once chosen, $z$ is constant. $\endgroup$ – quasi Oct 7 '17 at 20:37
  • $\begingroup$ If $\exists x\exists y$ is first, it's the $x,y$ that must be chosen first, and they can't force the choice of $z$ $\endgroup$ – quasi Oct 7 '17 at 20:39

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.