Model Theory-logic 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?!
 A: 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$.
