1
$\begingroup$

I've been given this first order sentence with a binary relation symbol $R$:

$\forall x \exists y (R(x, y) \land \forall z(R(x, z) \implies (R(y, z) \land (y=z)) ) $

We are then given two structures of this sentence and asked if the structure models the sentence:

  1. $S$ has domain the natural numbers and $R = \{(u, v) : u < v\}$

  2. $S$ has domain the rational numbers and $R = \{(u, v) : u < v\}$

As these are two separate questions, I would expect the answer to change. But it appears that neither of these structures model the equation, as $R(y, z) \land (y=z)$ cannot be true for any z and y. Am I missing something obvious here?

$\endgroup$
3
  • 1
    $\begingroup$ Maybe $R(y,z)\lor (y=z)$ was intended. $\endgroup$
    – André Nicolas
    Commented May 7, 2016 at 15:18
  • $\begingroup$ In the domain $\mathbb N$ of natural numbers, the formula (with $\lor$) is satisfied interpreting $y$ as the immediate successor of $x$ (i.e. as $x+1$). In this case, every successor $z$ of $x$ either coincide with $y=x+1$ or is greater thatn $y$. $\endgroup$
    – Mauro ALLEGRANZA
    Commented May 7, 2016 at 15:39
  • $\begingroup$ It's definitely $\land $ in the paper I was using. Maybe there was a typo. $\endgroup$
    – James Paterson
    Commented May 8, 2016 at 14:21

1 Answer 1

Reset to default
1
$\begingroup$

Apparently, the formula tries to express the existence of a supreme and it's unicity (hence the $y=z$ consequent). Since that kind of number does not exist neither in $\mathbb{N}$ nor in $\mathbb{Q}$, then you can be sure that neither $S_1$ nor $S_2$ model the formula.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .