Results 1 to 6 of 6

Math Help - Transitive Relations

  1. #1
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100

    Transitive Relations

    Hi. I have this problem.

    Let \theta be a binary relation on a set A, which is not necessarily transitive.
    Define a binary relation \theta^* on A as follows: for any a,b \in A, where k \ge 2 is an integer (which relies on a and b), such that a=a_1, b=a_k and a_i \theta a_{i+1} for all i=1,2,...,k-1. \theta* is called the transitive closure of \theta.
    Prove that \theta^* is a transitive relation on A.

    This is what I did... but not sure if it really make sense though.

    Suppose <a_1, a_2> and <a_2,a_k> are in \theta^*.
    Show that <a_1,a_k> is in \theta^*.
    By definition of \theta^*,
    <a_1, a_2> is in \theta^m for some m
    <a_2,a_k> is in \theta^n for some n
    Then <a_1, a_k> is in \theta^m\theta^n=\theta^{m+n} which is contained in \theta^*. Hence \theta^* must be transitive. i.e. \theta^* is a transitive relation on A.

    What I'm not sure what I have done is choosing an artribrary number in the sequence between a and b is correct, it is where I chose a_2. Also shall I use a_1 and a_k instead of a and b in my proof? Or should i just stick with a and b?

    Thanks heaps for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    OK, some critique. One of the main rules is that every variable must be introduced either by "for all", "any", etc. or "there exists", "some", etc.

    Quote Originally Posted by lpd View Post
    Define a binary relation \theta^* on A as follows: for any a,b \in A, where k \ge 2 is an integer (which relies on a and b), such that a=a_1, b=a_k and a_i \theta a_{i+1} for all i=1,2,...,k-1.
    The structure of you sentence is as follows: For any a and b ..., where ..., such that ... and ... . What happens for any such a and b? Next, "where k is an integer (which relies on a and b)" is not good because it is not clear how precisely k relies on a and b. Finally, you did not introduce a_2, a_3, etc.

    I would say: "for any a,b\in A, define a\theta^*b if there exist a sequence a_1,\dots,a_k of elements of A where a=a_1, b=a_k and a_i \theta a_{i+1} for all i=1,2,...,k-1".

    Quote Originally Posted by lpd View Post
    Suppose <a_1, a_2> and <a_2,a_k> are in \theta^*.
    Now that the definition has ended, the scope of a, b, k, a_1, ..., a_k is closed and they are just names with no assigned meanings. The proof opens a new scope. So, to answer your question, it does not make sense to choose a_2 as an arbitrary element of the sequence between a and b. So far, a and b are undefined. You should say, e.g.: Consider arbitrary a, b, c\in A and assume that a\theta^* b and b\theta^* c.

    Quote Originally Posted by lpd View Post
    By definition of \theta^*, <a_1, a_2> is in \theta^m for some m
    I think a remark about the relationship between \theta^* and \theta^m for various m would be merited since the actual definition does not mention powers of \theta. This relationship may seem obvious to a sophisticated reader, but our discussion is not at that level.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    Cool. This is just what I needed! Need help with constructing a proof! Okay, let me try again.

    For any a,b\in A, define a\theta^*b if there exist a sequence a_1,\dots,a_k of elements of A where a=a_1, b=a_k and a_i \theta a_{i+1} for all i=1,2,...,k-1.

    Consider arbitrary a, b, c\in A and assume that a\theta^* b and b\theta^* c

    By definition of \theta^*,
    <a, c> is in \theta^m for some m
    <c,b> is in \theta^n for some n

    Then <a, b> is in \theta^m\theta^n=\theta^{m+n} which is contained in \theta^*. Hence \theta^* must be transitive. i.e. \theta^* is a transitive relation on A.

    (What should I write for the explaination of \theta^m? Should I say something along the lines of... as \theta^m for some m is defined by the artibrary values of <a, c>.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    Should I say something along the lines of... as \theta^m for some m is defined by the artibrary values of <a, c>.
    I did not understand this phrase, namely, what it means to be "defined by".

    After the definition of \theta^*, I would say: "Note that by definition of \theta^m, a\theta^*b iff there exists an m such that a\theta^mb. In particular, \theta^m\subseteq\theta^* for all m." Otherwise, I repeat that saying "By definition of \theta^*, <a, c>
    is in \theta^m for some m" looks strange since the definition of \theta^* does not mention powers of \theta.

    Consider arbitrary a, b, c\in A and assume that a\theta^* b and b\theta^* c

    By definition of \theta^*,
    <a, c> is in \theta^m for some m
    <c,b> is in \theta^n for some n
    It should say that \langle a,b\rangle\in\theta^m and \langle b,c\rangle\in\theta^n, not \langle a,c\rangle and \langle c,b\rangle.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    Thanks for that.

    I was just wondering, wasn't I supposed to prove that a,b is transitive on \theta^*, because a is at the start of the sequence, and b is the end?

    Edit: is it because if we show that if a,c is transitive, then the sequence, a, b will also?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    One can say "transitive" only about a relation. A pair of elements a,b cannot be transitive.

    When proving that \theta^* is transitive, you assume that \langle a,b\rangle \in\theta^* and \langle b,c\rangle \in\theta^* for some a,b,c. This means that \langle a,b\rangle \in\theta^m and \langle b,c\rangle \in\theta^n for some m,n. It does not imply that \langle a,c\rangle \in\theta^m and \langle c,b\rangle \in\theta^n for some m,n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations, reflexive and transitive
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 5th 2010, 02:36 AM
  2. Composition of transitive relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 5th 2010, 04:41 PM
  3. Union of Transitive Relations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 8th 2008, 08:39 AM
  4. relations transitive
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 7th 2008, 06:09 AM
  5. Transitive Relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 20th 2008, 07:58 AM

Search Tags


/mathhelpforum @mathhelpforum