In preparing for an exam, I'm working through old exam questions and am now trying to figure out if the following first-order formula is valid and if not, then give a model that does not satisfy the formula. FYI, $h$ is a binary predicate.
$\{\exists a,c(a\neq c) \wedge \forall a,c[(a\neq c)\to (h(a,c)\Leftrightarrow \neg h(c,a))] \wedge \forall a,c$ $[h(a,c) \to \exists b(h(a,b)\wedge h(b,c)\wedge b\neq c)]\} \to \neg \{\exists a\forall b[b\neq a\to h(a,b)]\}$
I've reduced it to this equation through 5+ steps:
$\forall a,c(a=c) ∨ \exists a,c\{[(a\neq c)\wedge h(a,c) \wedge h(c,a)] \vee [(a\neq c\wedge \neg h(a,c) \wedge \neg h(c,a)]\} \vee \exists a,c$ $\forall b \{[h(a,c) \wedge \neg h(a,b)]\vee [h(a,c)\wedge h(b,c)]\vee [h(a,c)\wedge (b=c)]\} \vee \forall a\exists b \{b\neq a \wedge \neg h(a,b)\}$
Given we don't know how h is defined, I find it difficult to evaluate this formula. Is there information I'm missing or is there more significance to $h $ being a "binary predicate" than I realize? From what I can tell, I don't see how I can propose a model that that does not satisfy this, so it's Valid.
Thanks so much for the help!
Hint: note that if $A$ is infinite and $<$ is a dense linear order on $A$ (i.e. a linear order such that for all distinct $x,y$ with $x<y$, there exists a point $z$ different from $x$ and $y$ such that $x<z<y$), then $(A,<)$ is a model of the premise of formula (i.e., the part before $\Rightarrow$) with $h^A$ being interpreted as $<$. Can you find such a dense linear order that doesn't satisfy the conclusion of the formula?