Results 1 to 10 of 10

Math Help - Transitive closure relation.

  1. #1
    Senior Member
    Joined
    Jul 2006
    Posts
    364

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Relations on NxN

    Hello scorpion
    Quote Originally Posted by scorpion007 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    Quote Originally Posted by Grandad View Post
    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.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    Quote Originally Posted by Grandad View Post
    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 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Relation on N

    Hello scorpion007
    Quote Originally Posted by scorpion007 View Post
    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

    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Relations

    Hello scorpion007

    May I just give my thoughts and hopefully tie up one or two loose ends?
    Quote Originally Posted by scorpion007 View Post
    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 View Post
    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 View Post
    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 View Post
    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 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    Not to nitpick, but, re:

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

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof concerning a transitive closure
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2011, 12:26 PM
  2. Relation between topological closure and algebraic closure
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: November 4th 2010, 02:45 PM
  3. Transitive Closure
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 27th 2010, 06:33 AM
  4. transitive closure, cardinality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 24th 2010, 04:13 PM
  5. Transitive closure
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 14th 2008, 11:06 PM

Search Tags


/mathhelpforum @mathhelpforum