2
$\begingroup$
Find a common domain for the variables x,y, and z for which the statement   ∀x∀y((x≠y)→∀z((z=x)∨(z=y)))  is true and another domain for which it is false. 

This problem stumped me. I wrote:

The statement is true for any binary domain (such as {0,1})  and false for any non binary domain. 

The corrected paper stated that "non binary domain" was incorrect. I am guessing that this is simply a matter of sloppy wording and that "greater than binary" would be correct.

It also stated that I needed to justify my answer. Can anyone give me a starting point for how I would approach a proof?

1 Answers 1

1

For true: The thing says that if $x\ne y$, that is, if $x$ and $y$ are different objects in the domain, then anything in the domain is equal to $x$ or to $y$.

There are a couple of choices of domain $M$ that will work. If $M$ has two elements, the sentence will obviously hold. More subtly, a one-element domain will work, for then there won't be a pair $x$, $y$ such that $x\ne y$. Now make up a fun domain $M$ with two elements, and/or a fun domain with one element. Numbers are boring.

For false: All yours!

  • 0
    More formally, let $\varphi$ be the sentence $\forall{x} \forall{y} ((x \neq y) \rightarrow \forall{z} (z = x \vee z = y))$. Then $\forall{D} ( D \models \varphi \leftrightarrow |D| \leq 2 )$. Note that once we formulate it in these terms it becomes clear that the empty domain also satisfies $\varphi$, as universal quantifications over empty domains are trivially true.2012-02-02