[Math] Find a universe for variables x, y, and z for which the statement is true and another universe in which it is false.

logicquantifiers

Find a universe for variables $x, y$, and $z$ for which the statement

$∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y)))$

is true and another universe in which it is false.

Is there a more efficient method than trial and error (i.e. assign universe to all real numbers, assign numbers to x, y, z) ?

By universe, should I choose something like all real numbers? Or a set such as {0,1}?

Best Answer

A bit of intuition: Consider the formula $$∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y)))$$

Note that it actually says

For the universe $U$, if any arbitrary objects $x$ and $y$ are different, then any other arbitrary $z$ is either equal to $x$ or $y$.

Then we see that the referred formula will be true in any interpretation which universe $U$ has two (or one too, by vacuity) elements. It will be false otherwise.

A bit of symbolism:

I'm afraid of being pedant, so don't read this if my symbolism may confuse you. First we recall the notions of interpretation of a First Order language. Given a language L, and a L-structure $M$, the domain of $M$ (we shall denote it by $|M|$) can be any set, as long it is non-empy and countable (so as an answer to your question, $\{0,1\}$ is clearly allowable).

Let $M$ be an interpretation such that $M \vDash ∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y)))$.

This means that the formula is true in $M$. We state:

$M \vDash ∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y)))$ iff $1\leq |M| \leq 2$

1. Let $|M|=1$. The formula is true, since $x ≠ y$ is false for every value of $x$ or $y$.

2. Let $|M|=2$. The formula is true, since $x ≠ y$ is true for every value of $x$ or $y$, but $∀z((z = x) ∨ (z = y)))$ is not false.

2. Let $|M|=k$, where $k\neq 1, k\neq 2$. The formula is false, since $x ≠ y$ is true for every value of $x$ or $y$, but obviously $∀z((z = x) ∨ (z = y)))$ is false (Pigeonhole principle).

Examples of structures:

$\{0,1\}$, $\{0,2\}$, $\{3,5\}$... true

$\{0,1,2\}$, $\{0,2,3\}$, $\{1,2,5\}$... false