Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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!

share|improve this answer
    
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. –  Benedict Eastaugh Feb 2 '12 at 19:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.