# Complicated FOL Formula {∃a,c(a≠c) ∧ ∀a,c[(a≠c)⇒(h(a,c)⟺ ¬h(c,a))] ∧ ∀a,c[h(a,c) ⇒ ∃b(h(a,b)∧h(b,c)∧b≠c)]} ⇒ ¬{∃a∀b[b≠a⇒ h(a,b)]}

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!

• Please stop deleting your questions. Particularly those that have been answered. You are denying the friendly users who helped you the opportunity to get the appreciation (in terms of upvotes) from the community. Jan 2 '15 at 11:53
• Many many apologies! Jan 2 '15 at 20:19

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?
• The conclusion is $\forall x,\exists z, z\neq x\land h(x,z)$ so if we interpret $h$ to be $<$, the conclusion means "every element has a strictly greater element above it", which is not false in $\mathbb N$ (plus, in my answer the order has to be dense to satisfy the premise. For example, there is no element between $0$ and $1$.) But your example can work, by changing slightly the interpretation of $h$. Do you see how? Hint: does $\geq$ on $\mathbb N$ satisfies the premise of the formula? Jan 3 '15 at 8:35