Transitive closure relation.

Printable View

March 6th 2009, 04: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.
March 6th 2009, 10:52 PM
Grandad

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<n$ . 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?

Grandad
March 6th 2009, 11:48 PM
Grandad

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}$ .

Grandad
March 7th 2009, 12:30 AM
scorpion007

Quote:

Originally Posted by Grandad

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}$ .

Grandad

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.)
March 7th 2009, 12:41 AM
scorpion007

Quote:

Originally Posted by Grandad

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<n$ . 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:

Originally Posted by Grandad

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?

Grandad

Ah, I think I see. When they say $s=s_1, s_2, s_3, \ldots, s_n = t<br />$ , they mean $s_n = t$ , not the sequence $(s_1, s_2, \dots, s_n) = t$ , correct?
March 7th 2009, 01: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?
March 7th 2009, 03:39 AM
Grandad

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$ .

Grandad
March 7th 2009, 02: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?
March 7th 2009, 10:38 PM
Grandad

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<br />$ , 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.

Grandad
March 8th 2009, 03: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.