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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given the following formula: $$\bigg[\forall x P(x,x) \wedge \forall x \forall y \forall z\bigg( P(x,y) \wedge P(y,z) \Rightarrow P(x,z)\bigg) \wedge \forall x \forall y (P(x,y) \vee P(y,x)) \bigg] \Longrightarrow \exists y \forall x P(y,x) $$ It is known that this formula is always true if x,y,z are in any domain with finite size, but not always true in infinite case!!

I believe that the first part can be proved by induction! If the domain contains only one point x then formula is true. Suppose its true for a domain of size k, how to prove the k+1 case?

For the second part I need to find a counterexample for such P in some infinite domain, say the integers.

Any help?!

share|cite|improve this question
Why did you remove the question? – Qiaochu Yuan Dec 7 '10 at 7:45
I have rolled back the question to Arturo's last edit. – Aryabhata Dec 7 '10 at 7:56

The premises tell you that $P$ is reflexive and transitive, as well as total; this means that it is a total pre-order on the domain. The conclusion is that the pre-order has a smallest element.

How would you go about doing it by induction? Well, suppose you know the result holds in any domain with fewer than $k$ elements, and your domain has $k$ elements. Pick $x_0\in D$ ($D$ the domain), and let $D'=D\setminus\{x_0\}$, and let $P'=P\cap D'\times D'$. If you can prove that $P'$ satisfies the premises of the formula relative to $D'$ (given that $P$ satisfies them relative to $D$), then you'll be able to conclude that there is a $y\in D'$ such that $(y,x)\in P'$ for every $x\in D'$. Now, how can $y$ fail to be an element with the right property if you now consider it in $D$? And if that happens, can you find an element that will work?

As to a counterexample, given my first paragraph, does something suggest itself?

Okay, you are asking for some more help on getting the induction going.

Let $n$ be the number of elements in the model $D$. We want to prove the formula holds for $D$. We do so by induction on $n$.

The base case is $n=1$. To establish the proposition, we are allowed to assume the premise holds: that for all $x\in D$ we have $P(x,x)$, that for all $x$, $y$, and $z$ in $D$, if $P(x,y)$ and $P(y,z)$ both hold, then $P(x,z)$ holds; and that for all $x$ and $y$ in $D$, either $P(x,y)$ holds or $P(y,x)$ holds. We want to show that there exists a $y\in D$ such that for all $x\in D$, $P(y,x)$ holds.

Since $D = \{x_1\}$ has a single element, what can $y$ be? It must be $x_1$. So you need to show that for every $x$ in $D$, $P(x_1,x)$ holds. Surely this is easy.

Okay, so now assume that you know the proposition is true in any domain with $k$ elements, and assume that $D=\{x_1,x_2,\ldots,x_k,x_{k+1}\}$ has $k+1$ elements. We are also allowed to assume that $P(x,x)$ holds for all $x\in D$, that for all $x,y,z$ in $D$, if $P(x,y)$ and $P(y,z)$ holds, then $P(x,z)$ holds; and that for all $x$ and $y$ in $D$, either $P(x,y)$ holds or $P(y,x)$ holds. We want to show that there is a $y\in D$ such that for all $x\in D$, $P(y,x)$ holds.

Consider $D'=D-\{x_{k+1}\}$, and let $P'$ be a binary relation on $D'$ defined by $$P'(x,y)\text{ in $D'$} \Leftrightarrow P(x,y) \text{in $D$.}$$ Verify that $P'$ satisfies the premise of the proposition in $D'$: for all $x\in D'$, $P'(x,x)$ holds; if $P'(x,y)$ and $P'(y,z)$ hold, then $P'(x,z)$ hold; and for all $x$ and $y$ in $D'$, either $P'(x,y)$ holds or $P'(y,x)$ holds.

By the induction hypothesis, the formula is true in $D'$; so if the premise is also true in $D'$, then the conclusion is true in $D'$. So there is a $y_0\in D'$ such that for all $x\in D'$ you have $P'(y_0,x)$.

Now, go back to $D$; $y_0$ is in $D$, and for every $x\in D$, if $x\in D'$ (that is, if $x\neq x_{k+1}$) then $P(y_0,x)$ holds. Now, what happens to $x_{k+1}$? Well, by our premises, either $P(y_0,x_{k+1})$ holds, or else $P(x_{k+1},y_0)$ holds because $y_0$ and $x_{k+1}$ are both in $D$. Think about what each of those two things would tell you in terms of trying to find a $y\in D$ such that $P(y,x)$ holds for all $x$ in $D$.

share|cite|improve this answer
@John: It cannot be $x\lt y$, because then it would not satisfy reflexivity. – Arturo Magidin Dec 2 '10 at 21:13
@John: Sounds like a reasonable enough thing to try... – Arturo Magidin Dec 2 '10 at 21:31
@John: Huh? $y_0$ is already chosen. What you are trying to find is a $y$ that will satisfy $\forall x\in D, yPx$. You already know that $y_0$ satisfies $y_0Px$ for all $x\in D'$. The only question is whether you have $y_0Px_{k+1}$ (in which case you are done by taking $y=y_0$), or whether you have $x_{k+1}Py_0$, in which case $y_0$ is no good because it does not satisfy the condition that $\forall x\in D, y_0Px$. But if you have $x_{k+1}Py_0$, then what can you choose to play the role of $y$ instead, and why? – Arturo Magidin Dec 4 '10 at 6:35
@John. Exactly. – Arturo Magidin Dec 5 '10 at 21:06

Your Answer


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.