# 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?!

-
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$.

-
@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