2
$\begingroup$

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

  • 0
    Why did you remove the question?2010-12-07
  • 0
    I have rolled back the question to Arturo's last edit.2010-12-07

1 Answers 1