2

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.

Taylor Rendon
  • 2,276
Byebye
  • 277
  • It is three. In principle parentheses should be used, but one ordinarily doesn't bother. And it is True, False, True. – André Nicolas Jun 03 '14 at 11:13
  • @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? – Byebye Jun 03 '14 at 11:21
  • 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). – Mauro ALLEGRANZA Jun 03 '14 at 11:23
  • 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. – André Nicolas Jun 03 '14 at 11:24
  • @AndréNicolas could you explain how I can get that connection to transitivity out of the given definition? – Byebye Jun 03 '14 at 11:27
  • I am wrong on ancestor, it is an order relation but not a linear order relation. – André Nicolas Jun 03 '14 at 11:32
  • @MauroALLEGRANZA Ok, so I would read it as follows: x is less than y or, x equals y or, y less than x, correct? And the formula would only have to adhere to either of those formulas to make it linear? – Byebye Jun 03 '14 at 11:38
  • Sorry, but I'm not familiar with the attribute "linear" for a relation. For sure your reading is correct and it shows that (3) is true for the natural numbers when $R$ is interpreted as "<", because for each "choice" of numbers $x,y$, we have that they satisfy the formula (3). – Mauro ALLEGRANZA Jun 03 '14 at 11:40

1 Answers1

1

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.

Graham Kemp
  • 129,094
  • thank you! I forgot about the Domain of Discourse they set and didn't think of any refutations. My bad, thanks for the answer! – Byebye Jun 03 '14 at 11:41