1

Formulas:

  • $\forall x A(x,x)$
  • $\forall x,y,z ((A(x,y) \land A(y,z)) \rightarrow A(x,z))$
  • $\forall x,y((A(x,y) \lor A(y,x)) \rightarrow \exists y \forall x A(y,x))$

What is the best way to show that the conjunction of the above formulas is satisfiable in an arbitrary structure with finite domain?

Remark: On the other hand there is both a counterexample and a satisfying interpretation in an infinite domain, namely the set of natural numbers. Counterexample: interpret $A$ as $\geq$ over $\mathbb{N}$. Satisfying interpretation: interpret $A$ as $\leq$ over $\mathbb{N}$. (Correct me if I am wrong here).

Thanks in advance!

trojan
  • 79

1 Answers1

1

Use $xAy$ for $A(x,y),$ and your first two axioms are reflexivity and transitivity. You may as well take the assumption of the third formula as another axiom, i.e. that $A$ is "connected": any two elements may be compared, and ask about whether there has to be a maximal element in the (finite) set.

Now take a maximal chain (with distinct $b_j$) $$b_1A b_2 A b_3\cdots b_{n-1}A b_n.$$ If the $b_j$ are all the elements of the finite set you're done. Otherwise let $x$ be another element which is not one of the $b_j$. Now by connectedness either $xAb_1$ or $b_1Ax.$ The first of these would make a longer chain, so that doesn't hold, and we have $b_1Ax.$ Now look at $x$ and $b_2$ If it happened that $xAb_2$ we could insert $x$ between $b_1$ and $b_2$ and get a longer chain, (transitivity is used) contradicting longest chain choice. So in fact $b_2Ax$. Continuing along we finally will reach $b_nAx$ and the $x$ gets tacked onto the end of the (maximal) $b_j$ chain for another contradiction.

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • I already had an idea along that line, but I was not quite sure how to carry out the details. So thank you very much for your answer. – trojan Mar 14 '14 at 09:53
  • I realized later that if $A$ is viewed in the $\le$ form, your question is whether there needs to be a minimal element. Of course that doesn't matter because of symmetry of the other axioms under switch of $x,y$, so that one can guarantee a max iff a min is guaranteed. – coffeemath Mar 14 '14 at 11:58