# Transitive closure relation.

• Mar 6th 2009, 05:22 PM
scorpion007
Transitive closure relation.
Hi,
The question is as follows:

The transitive closure of a relation R on S x S is another relation on S x S called Tr(R) such that $(s,t) \in Tr(R)$ iif there exists a sequence $s=s_1, s_2, s_3, \ldots, s_n = t$ such that $(s_i, s_{i+1}) \in R$ for each $i$.

a) What is the transitive closure of the successor relation? (Defined previously on N x N as: $\lbrace (m, n) | m = n+1\rbrace$).
b) What is the transitive closure of the > relation?

The book introduced this concept right in this exercise question without showing any examples. I'm a bit stuck as to how I might interpret this somewhat complex definition [of a transitive closure] and derive the solution.
• Mar 6th 2009, 11:52 PM
Relations on NxN
Hello scorpion
Quote:

Originally Posted by scorpion007
Hi,
The question is as follows:

The transitive closure of a relation R on S x S is another relation on S x S called Tr(R) such that $(s,t) \in Tr(R)$ iif there exists a sequence $s=s_1, s_2, s_3, \ldots, s_n = t$ such that $(s_i, s_{i+1}) \in R$ for each $i$.

a) What is the transitive closure of the successor relation? (Defined previously on N x N as: $\lbrace (m, n) | m = n+1\rbrace$).
b) What is the transitive closure of the > relation?

The book introduced this concept right in this exercise question without showing any examples. I'm a bit stuck as to how I might interpret this somewhat complex definition [of a transitive closure] and derive the solution.

The successor relation on $\mathbb{N} \times\mathbb{N}$ contains all ordered pairs of the form $(n+1, n), n \in \mathbb{N}$. And we can form a sequence of such ordered pairs, starting at any $n$, and finishing at any $m. For example, starting at $7$ and finishing at $3$:

$(7,6), (6,5), (5,4),(4,3)$

So the sequence $7, 6, 5, 4, 3$ is an example of a sequence $s_1, s_2, s_3, \dots, s_n$ where $(s_i, s_{i+1}) \in R$, the successor relation. So $(7,3) \in Tr(R)$.

Do you want to see if you can take it from here?

• Mar 7th 2009, 12:48 AM
Relation terminology
Hello scorpion007

Just as a PS to my previous post, to use the correct terminology, the successor relation is defined on $\mathbb{N}$, of course, not $\mathbb{N} \times \mathbb{N}$. The relation is then a subset of $\mathbb{N} \times \mathbb{N}$.

• Mar 7th 2009, 01:30 AM
scorpion007
Quote:

Hello scorpion007

Just as a PS to my previous post, to use the correct terminology, the successor relation is defined on $\mathbb{N}$, of course, not $\mathbb{N} \times \mathbb{N}$. The relation is then a subset of $\mathbb{N} \times \mathbb{N}$.

While I understand that a relation is a subset of the Cartesian product of two sets ( $R \subset S \times T$), my book states, for example, this exact quote, in the fifth question: "5. We define the successor relation on $N \times N$ to be the set ...<the definition follows>".

Is it incorrect? (The book is Discrete Algorithmic Mathematics, 2nd Edition.)
• Mar 7th 2009, 01:41 AM
scorpion007
Quote:

Hello scorpion
The successor relation on $\mathbb{N} \times\mathbb{N}$ contains all ordered pairs of the form $(n+1, n), n \in \mathbb{N}$. And we can form a sequence of such ordered pairs, starting at any $n$, and finishing at any $m. For example, starting at $7$ and finishing at $3$:

$(7,6), (6,5), (5,4),(4,3)$

Ok, but if you started at n = 7, then wouldn't the first pair be (8, 7), since (7 + 1, 7)?

Quote:

So the sequence $7, 6, 5, 4, 3$ is an example of a sequence $s_1, s_2, s_3, \dots, s_n$ where $(s_i, s_{i+1}) \in R$, the successor relation. So $(7,3) \in Tr(R)$.

Do you want to see if you can take it from here?

Ah, I think I see. When they say $s=s_1, s_2, s_3, \ldots, s_n = t
$
, they mean $s_n = t$, not the sequence $(s_1, s_2, \dots, s_n) = t$, correct?
• Mar 7th 2009, 02:00 AM
scorpion007
Ok, so from what I understand, Tr(R) contains ordered pairs such as (7, 3), (7, 4), (100, 5). Generally, any ordered pair (s, t) such that s > t. Formally, $\lbrace (s, t) | s > t \rbrace$. Correct?

Looking at the answer in the book, they have, $\lbrace (s, t) | s < t \rbrace$. Why is that?
• Mar 7th 2009, 04:39 AM
Relation on N
Hello scorpion007
Quote:

Originally Posted by scorpion007
Ok, so from what I understand, Tr(R) contains ordered pairs such as (7, 3), (7, 4), (100, 5). Generally, any ordered pair (s, t) such that s > t. Formally, $\lbrace (s, t) | s > t \rbrace$. Correct?

Looking at the answer in the book, they have, $\lbrace (s, t) | s < t \rbrace$. Why is that?

If you define the successor relation in the way that you have then the ordered pairs are $(n+1, n)$ and hence (I think!) the answer should be $s > t$. But if the successor relation is the other way round, so that $n$ is related to its successor, $n+1$, the ordered pairs then being $(n, n+1)$, then the answer will have $s < t$.

• Mar 7th 2009, 03:54 PM
scorpion007
Ah, thank you. Perhaps it is a mistake in the book, then. They probably meant to define the successor relation as all points (n, m) instead of (m, n).

So for question b), The answer would be "Itself", which is also what the book states. Correct?
• Mar 7th 2009, 11:38 PM
Relations
Hello scorpion007

May I just give my thoughts and hopefully tie up one or two loose ends?
Quote:

Originally Posted by scorpion007
While I understand that a relation is a subset of the Cartesian product of two sets ( $R \subset S \times T$), my book states, for example, this exact quote, in the fifth question: "5. We define the successor relation on $N \times N$ to be the set ...<the definition follows>".

Is it incorrect? (The book is Discrete Algorithmic Mathematics, 2nd Edition.)

I have always defined a binary relation (i.e. one in which two elements are involved) as follows: A binary relation from a set $X$ to a set $Y$ is a set of ordered pairs $(x, y)$ such that $x \in X$ and $y \in Y$. It follows therefore that a relation defines a subset of $X \times Y$.

Now it may be that $X$ and $Y$ are one and the same set - the set $\mathbb{N}$, for instance. So in referring to relations like the ones in this question (> and the 'successor relation'), I would talk about a relation 'from $\mathbb{N}$ to itself', or simply a relation 'on $\mathbb{N}$'.

I would not argue with anyone who wanted to call this a relation 'on $\mathbb{N} \times \mathbb{N}$', but there is a slight danger here that this might be interpreted as a relation that mapped an ordered pair e.g. $(1,2)$ onto another order pair e.g. $(5, 3)$ (for instance, with the relation 'is in the same quadrant as'), rather than mapping a natural number onto another natural number.
Quote:

Originally Posted by scorpion007
Ok, but if you started at n = 7, then wouldn't the first pair be (8, 7), since (7 + 1, 7)?

Strictly speaking, yes, if your first ordered pair is $(n+1, n)$ and $n=7$. But you'll notice I didn't say $n=7$, you did. I simply said 'starting at 7'.
Quote:

Originally Posted by scorpion007
Ah, I think I see. When they say $s=s_1, s_2, s_3, \ldots, s_n = t
$
, they mean $s_n = t$, not the sequence $(s_1, s_2, \dots, s_n) = t$, correct?

Yes.
Quote:

Originally Posted by scorpion007
Ah, thank you. Perhaps it is a mistake in the book, then. They probably meant to define the successor relation as all points (n, m) instead of (m, n).

I think this is much more likely. After all, if the relation is a representation of a mapping of $n$ onto its successor $n+1$ then the natural order for the ordered pair is $(n, n+1)$, and an ' ${s_i}$' sequence then goes in ascending order: $3, 4, 5, 6, 7$.

A confusion will arise if the successor relation is representation of the words '... is the successor of ...', in which case $n+1$ 'is a successor of' $n$, and the ordered pair then gets written as $(n+1, n)$. It's easy to get it the wrong way round, isn't it!

Quote:

Originally Posted by scorpion007
So for question b), The answer would be "Itself", which is also what the book states. Correct?

Yes. This is much less ambiguous!

I hope we've dealt with this question now! And you might like to look at this:
http://www.mathhelpforum.com/math-he...l-posters.html.

• Mar 8th 2009, 04:38 AM
scorpion007
Not to nitpick, but, re:

Quote:

But you'll notice I didn't say n=7, you did. I simply said 'starting at 7'.
You said, originally,

Quote:

And we can form a sequence of such ordered pairs, starting at any n, and finishing at any m<n. For example, starting at 7 and finishing at 3:
How should I have interpreted this, if not n=7, m=3?

Thanks for the explanations, by the way. Very useful.