1

I'm reading a book about structures on collections, chapter equivalence relations, and I try to get through the explanation of transitive closure. They use the following example:

$A$ is a collection of people. In $A$ the relation $R$ is defined by $xRy$ if $x$ is a parent of $y$.

This parent relation is a relation that is not transitive. Surely, if $a$ is a parent of $b$, and $b$ is a parent of $c$, then $a$ is (in general) not a parent of $c$. Using the parent relation we can define the ancestor relation: $a$ is an ancestor of $b$ if there exists a string of people $c_1, c_2,\ldots, c_n$ for which $a = c_1$, $b = c_n$ and $c_i$ is a parent of $c_{i + 1}$ for each $i \in \{1, \ldots, n - 1\}$. The relation 'ancestor of' is transitive.

We shall now look how we can define the grandparent relation from the parent relation. Let $R$ be the parent relation, $R = \{(x, y)\mid x\text{ is a parent of }y \}$. Then we have: $a$ is a grandparent of $b$ if there is a $p$ of which $a$ is its parent and $p$ is the parent of $b$. The relation 'grandparent of' is then equal to the collection $\{(x, y)\mid\text{there is a }p\text{ for which }xRp\text{ and }pRy\}$.

This last sentence is what confuses me. How exactly does this collection have $(x, y)$? Because to me it seems that what is in the collection is $x\to p\to y$, and not $x\to y$. I cannot for the life of me figure out how this definition is tying $x$ to $y$.

Garth Marenghi
  • 1,115
  • In your ancestor definiton, I suppose you want $b=c_n$ instead of $b=c_2$, right? – Hagen von Eitzen Jul 21 '13 at 14:03
  • You're complety correct - I changed it. – Garth Marenghi Jul 21 '13 at 14:04
  • 2
    Well, the grandparent example should make this clear. You can say "This is my grandfather" and this realets you and your grandfather. Only in order to prove this fact about your relation, you'd have to exhibit your mother or father and say "This is my grandfather because my mother/father is his doughter/son" – Hagen von Eitzen Jul 21 '13 at 14:05
  • I'm not quite getting it yet. You mean to say that it is implicit? That the collection does not explicitly say (x, y), but rather (x, p), (p, y)? And does it have to do with not saying 'parent' but grandparent? Because in the beginning it says: "if a is a parent of b, and b is a parent of c, then a is not a parent of c". But instead of saying the relation is called 'parent of' to 'grandparent of', it does work? I'm so confused by this :-) – Garth Marenghi Jul 21 '13 at 14:17

1 Answers1

1

You are confusing between two different ways of expressing relationships. A relationship on the elements of a set is the collection $R$ of ordered pairs $(x,y)$ such that $x$ is related to $y$ if and only if $(x,y) \in R$. We also express the fact that $x$ is related to $y$ as $xRy$. Thus, a relationship $R$ is a collection of things that we write as $xRy$ for different choices of $x$ and $y$, which we could also write as a collection of ordered pairs $(x,y)$ and name the collection of ordered pairs as $R$! So, define $$\begin{align} P &= \{(x,y) \colon x ~\text{is a parent of}~y, ~\text{that is},~ xPy\}\\ G &= \{(a,b) \colon \exists ~ p ~\text{such that} (a,p)\in P ~\text{and}~ (p,b) \in P, ~\text{that is},~ aGb \} \end{align}$$ as the parent and grandparent relationships.

Dilip Sarwate
  • 25,197
  • First of, thanks for your answer. Although I'm not getting some of the things you wrote, I do notice now that the set (collection?) G is defined with the help of the set (again, collection?) P. But am I right in saying that all this feels implicit? – Garth Marenghi Jul 21 '13 at 14:42
  • Yes, $a$ cannot be a grandparent of $b$ unless $a$ has a child who is a parent of $b$, and so the definition of $G$ must be derived from the definition of $P$. It is a step along the way to deriving the transitive closure $A$ "$x$ is an ancestor of $y$" of the relationship $P$. But note that it is not necessary for a relationship to have any rime or reason. For the same bunch of people, we can pick an arbitrary collection of pairs and call it $H$ where $xHy$ if $x$ is an heir of $y$. It could well be that $xPy$ and $xHy$ where the second is unlikely in real life if the first is true. – Dilip Sarwate Jul 21 '13 at 14:53
  • I think I'm getting it. I think that where my confusion comes from is that I think that what comes after the 'such that' in the set notation is what makes the set, but they actually are the rules for the elements in the set. – Garth Marenghi Jul 21 '13 at 19:45