I've got a question about linear relations in predicate logic.

I've got the follow definition where R is a relation of x has a Relation to y.

$$\forall x \forall y(Rxy \vee x = y \vee Ryx)$$

How do I read this? Are there 3 formulas? Or just 2?

Also, what would be the correct answers to the question: Do the following sentences describe a linear relation?

(1) being an ancestor of . . . on the set of human beings, (2) being a parent of . . . on the set of human beings, (3) the ‘less than’ relation < on the natural numbers,

My answers would be False,False, False.

Thanks in advance, Rope.

  • $\begingroup$ It is three. In principle parentheses should be used, but one ordinarily doesn't bother. And it is True, False, True. $\endgroup$ – André Nicolas Jun 3 '14 at 11:13
  • $\begingroup$ @AndréNicolas Could you explain how you got to those answers? I'm guessing that ancestor of.. is linear because every y has a relation to an ancestor x? But the definition contains a disjunction so the other formulas shouldn't be bothered with? But the same can be said about the "parent of.." relation. So why is that false? Same goes for the less than relation, why is that true if the parent of relation is false? $\endgroup$ – Byebye Jun 3 '14 at 11:21
  • $\begingroup$ For 3), you simply have to replace $R$ with "<" to get : $(x < y ∨ x = y ∨ y < x)$ which is obviously true for the natural numbers (it is called : trichotomy). $\endgroup$ – Mauro ALLEGRANZA Jun 3 '14 at 11:23
  • $\begingroup$ For a linear order relation, we need to have transitivity. A parent of one of my parents is not one of my parents. Contrast that with ancestor. An ancestor of one of my ancestors is one of my ancestors. $\endgroup$ – André Nicolas Jun 3 '14 at 11:24
  • $\begingroup$ @AndréNicolas could you explain how I can get that connection to transitivity out of the given definition? $\endgroup$ – Byebye Jun 3 '14 at 11:27

It's three. Read it as: $\forall x\forall y \big((Rxy)\vee (x=y)\vee (Ryx)\big)$

This is true is at least one of those conditions is true for any pair of $(x,y)$.

It is false if there exists at least one pair $(x,y)$ such that none of those conditions are true.

The statement, "x is the ancestor of y, or x is y, or y is the ancestor of x", is false because x and y may be, for instance, siblings (or unrelated), in which case neither would be an ancestor of the other.

Contrast to $\forall x\in \mathbb{N},\forall y \in \mathbb{N}, (x<y)\vee(x=y)\vee(y<x)$. Which is self evidently true since natural numbers are ordered.

  • $\begingroup$ thank you! I forgot about the Domain of Discourse they set and didn't think of any refutations. My bad, thanks for the answer! $\endgroup$ – Byebye Jun 3 '14 at 11:41

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.