1
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 2 '15 at 11:53
  • $\begingroup$ Many many apologies! $\endgroup$
    – Orbitz233
    Jan 2 '15 at 20:19
1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Jan 3 '15 at 8:35
  • $\begingroup$ Ah my bad, I misread the last bit of the formula. You only have the problem of the density of the order then. So consider the set of non-negative rational numbers, and it works just fine! Remember to accept the answer if you found it useful, so that the question appears as answered in the search feature. $\endgroup$ Jan 3 '15 at 10:12
  • $\begingroup$ This is very helpful! Thanks so much! $\endgroup$
    – Orbitz233
    Jan 3 '15 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.