[Math] 5. 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.

discrete mathematicslogicpredicate-logicquantifiers

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.

Best Answer

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$).

Related Question