Results 1 to 12 of 12

Math Help - [SOLVED] Transitivity in set relations

  1. #1
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98

    Question [SOLVED] Transitivity in set relations

    Suppose X, Y, Z are sets. If X ~ Y and Y ~ Z, prove that X ~ Z.

    I thought we already proved this in my discrete math class, but I couldn't find it in my notes .

    Okay my work on the proof so far is:

    Suppose X, Y, Z are sets. Let X ~ Y and Y ~ Z. By equivalence, there are functions f and g such that f: X → Y where f is 1-1 and onto, and g: Y → Z where g is 1-1 and onto.
    So now I have to show that there is a function h: X → Z that is 1-1 and onto. This is where I got stuck. Like for showing 1-1, I need to assume two elements (x_1, x_2) are equal and then show that when I plug them in function h, I get the same answer. For showing onto, I pick an arbitrary element z in Z and get an element in X that maps to z.

    My thinking/scratch work:
    Since f is 1-1, then when x_1 = x_2 then f(x_1) = f(x_2). f's range is Y and so f(x_1) and f(x_2) are in Y and so those are also equal since g is 1-1. So somehow it's tying that all together to show that h is 1-1. How can I do that clearly?

    Now for onto, since f is onto, there is a y in Y such that there is an x in X that maps to y. I can use that 'y' in Y to map to a z in Z since g is onto. So can I then say that since x maps to y then x maps to z?

    I hope my work isn't too confusing.
    Thanks for your time.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    Suppose X, Y, Z are sets. If X ~ Y and Y ~ Z, prove that X ~ Z.

    I thought we already proved this in my discrete math class, but I couldn't find it in my notes .

    Okay my work on the proof so far is:

    Suppose X, Y, Z are sets. Let X ~ Y and Y ~ Z. By equivalence, there are functions f and g such that f: X → Y where f is 1-1 and onto, and g: Y → Z where g is 1-1 and onto.
    So now I have to show that there is a function h: X → Z that is 1-1 and onto. This is where I got stuck. Like for showing 1-1, I need to assume two elements (x_1, x_2) are equal and then show that when I plug them in function h, I get the same answer. For showing onto, I pick an arbitrary element z in Z and get an element in X that maps to z.

    My thinking/scratch work:
    Since f is 1-1, then when x_1 = x_2 then f(x_1) = f(x_2). f's range is Y and so f(x_1) and f(x_2) are in Y and so those are also equal since g is 1-1. So somehow it's tying that all together to show that h is 1-1. How can I do that clearly?

    Now for onto, since f is onto, there is a y in Y such that there is an x in X that maps to y. I can use that 'y' in Y to map to a z in Z since g is onto. So can I then say that since x maps to y then x maps to z?

    I hope my work isn't too confusing.
    Thanks for your time.
    there is a theorem that says:

    let \alpha and \beta be functions.
    (a) if \alpha and \beta are onto, then \beta \circ \alpha is onto
    (b) if \alpha and \beta are 1-1, then \beta \circ \alpha is 1-1

    (do you have to prove this theorem? if it was mentioned before in class, i'd just state it)

    Note that your function h is actually g \circ f
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,803
    Thanks
    1692
    Awards
    1
    We are given that there are two bijections:
    f:X \leftrightarrow Y\quad \& \quad g:Y \leftrightarrow Z.
    What can be said about g \circ f ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by Jhevon View Post
    there is a theorem that says:

    let \alpha and \beta be functions.
    (a) if \alpha and \beta are onto, then \beta \circ \alpha is onto
    (b) if \alpha and \beta are 1-1, then \beta \circ \alpha is 1-1

    (do you have to prove this theorem? if it was mentioned before in class, i'd just state it)

    Note that your function h is actually g \circ f
    Yeah we have to prove transitivity so I can't just state the theorem I sure wish I could! I don't see how h is the composition of g with f. It's the cross product that is throwing me off. So you're saying I'm putting in the function f for my domain in g (the composition) which is h. But how will I get to A x B from f? Wow, I think I am utterly confusing myself further. Thanks for looking at this post.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    Yeah we have to prove transitivity so I can't just state the theorem I sure wish I could! I don't see how h is the composition of g with f. It's the cross product that is throwing me off. So you're saying I'm putting in the function f for my domain in g (the composition) which is h. But how will I get to A x B from f? Wow, I think I am utterly confusing myself further. Thanks for looking at this post.
    what do you mean cross-product? i think you are confusing the ideas here with those in your other thread

    there is nothing to do with cross-product here. it is just a general fact of functions that compositions take elements from the first function in the composition (the right-most function) to the codomain of the last function in the composition (the left-most function)

    if f : X \mapsto Y and g : Y \mapsto Z are functions (f onto), then their composition is g \circ f : X \mapsto Z. it starts with elements in the domain of f, and takes them to the domain of g where they are then mapped to the codomain of g
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by Jhevon View Post
    what do you mean cross-product? i think you are confusing the ideas here with those in your other thread

    there is nothing to do with cross-product here. it is just a general fact of functions that compositions take elements from the first function in the composition (the right-most function) to the codomain of the last function in the composition (the left-most function)

    if f : X \mapsto Y and g : Y \mapsto Z are functions (f onto), then their composition is g \circ f : X \mapsto Z. it starts with elements in the domain of f, and takes them to the domain of g where they are then mapped to the codomain of g
    I literally LOL'ed when I realized I totally got my threads mixed up! Thanks for pointing that out. Okay, I'm going to look at this some more and see what I can work out.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98

    attempt

    Okay, here's what I got so far:

    X~ Y implies that there is a function f: X → Y that is 1-1 and onto.
    Y ~ Z implies that there is a function g: Y → Z that is 1-1 and onto.
    I need to prove X ~ Z which implies there is a function h: X → Z that is 1-1 and onto.

    To show 1-1:
    Take a and b in Z. Assume h(a) = h(b).
    That implies g(a) = g(b). Since f and g are 1-1, a = b. So h is 1-1.

    To show onto:
    Let z be in z. f is onto which means there is an x in X such that f(x) = y.
    g is onto which means there is a y in Y such that g(y) = z.
    Therefore, f(x) = g(f(x)) = z. So h is onto.

    Am I on the right track?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    Okay, here's what I got so far:

    X~ Y implies that there is a function f: X → Y that is 1-1 and onto.
    Y ~ Z implies that there is a function g: Y → Z that is 1-1 and onto.
    I need to prove X ~ Z which implies there is a function h: X → Z that is 1-1 and onto.

    To show 1-1:
    Take a and b in Z. Assume h(a) = h(b).
    That implies g(a) = g(b). Since f and g are 1-1, a = b. So h is 1-1.

    To show onto:
    Let z be in z. f is onto which means there is an x in X such that f(x) = y.
    g is onto which means there is a y in Y such that g(y) = z.
    Therefore, f(x) = g(f(x)) = z. So h is onto.

    Am I on the right track?
    you are thinking, and you are very close. the problem is, there is a lack of coherency in your proof. for one, you never stated what your function h was. it should be the function fog, which your work seems to show, but you never said that. so one would wonder how assuming these things about h implies the things about f and g that you pointed out. you made no connection between h and f and g. other than that, a little tightening up of the argument should suffice. very good first attempt though
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by Jhevon View Post
    you are thinking, and you are very close. the problem is, there is a lack of coherency in your proof. for one, you never stated what your function h was. it should be the function fog, which your work seems to show, but you never said that. so one would wonder how assuming these things about h implies the things about f and g that you pointed out. you made no connection between h and f and g. other than that, a little tightening up of the argument should suffice. very good first attempt though
    Thank you. Okay, so here's my correction:

    Proof: Suppose X, Y, Z are sets. Let X ~ Y and Y ~ Z.
    X~ Y implies that there is a function f: X → Y that is 1-1 and onto.
    Y ~ Z implies that there is a function g: Y → Z that is 1-1 and onto.
    (Need to prove X ~ Z which implies there is a function h: X → Z that is 1-1 and onto). Let h: X → Z such that h is fog.

    To show 1-1:
    Take a and b in Z. Assume h(a) = h(b).
    That implies f(g(a)) = f(g(b)). Since g is 1-1, g(a) = g(b).
    Since f is 1-1, a = b. So h is 1-1.

    To show onto:
    Let z be in Z. f is onto which means there is an x in X such that f(x) = y.
    g is onto which means there is a y in Y such that g(y) = z.
    Therefore, f(x) = g(f(x)) = z. So h is onto.

    h is 1-1 and onto therefore X ~ Z. QED.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    Thank you. Okay, so here's my correction:

    Proof: Suppose X, Y, Z are sets. Let X ~ Y and Y ~ Z.
    X~ Y implies that there is a function f: X → Y that is 1-1 and onto.
    Y ~ Z implies that there is a function g: Y → Z that is 1-1 and onto.
    (Need to prove X ~ Z which implies there is a function h: X → Z that is 1-1 and onto). Let h: X → Z such that h is fog.
    ok, so i made a mistake in my last post (which you should have caught, since i said the correct thing in previous posts). the function should be gof, not fog. fog does not go from X to Z, in fact, it is not a properly defined function.

    anyway, it sounds more mathy to say something like, "consider the function h : X \mapsto Z defined by h = g \circ f"

    To show 1-1:
    Take a and b in Z. Assume h(a) = h(b).
    That implies f(g(a)) = f(g(b)). Since g is 1-1, g(a) = g(b).
    Since f is 1-1, a = b. So h is 1-1.
    so yeah, again, it should be g(f(a)) = g(f(b)) as the thing you start out with. strangely, your proof works if you make that only that change with no other alteration, meaning, it was wrong as stated before.

    we have g(f(a)) = g(f(b)). since g is 1-1, this implies f(a) = f(b). but since f is 1-1, this means a = b, so that h is 1-1.

    To show onto:
    Let z be in Z. f is onto which means there is an x in X such that f(x) = y.
    g is onto which means there is a y in Y such that g(y) = z.
    Therefore, f(x) = g(f(x)) = z. So h is onto.
    again, just a little rearranging here. Let z \in Z. since g is onto, there is some y \in Y so that g(y) = z. But f is onto, so that there is some x \in X such that f(x) = y. But that means g(f(x)) = z. thus, h is onto

    thus we have shown h is 1-1 and onto, therefore X ~ Z. QED.
    nothing much wrong with this sentence
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98

    awesome

    Quote Originally Posted by Jhevon View Post
    ok, so i made a mistake in my last post (which you should have caught, since i said the correct thing in previous posts). the function should be gof, not fog. fog does not go from X to Z, in fact, it is not a properly defined function.

    anyway, it sounds more mathy to say something like, "consider the function h : X \mapsto Z defined by h = g \circ f"

    so yeah, again, it should be g(f(a)) = g(f(b)) as the thing you start out with. strangely, your proof works if you make that only that change with no other alteration, meaning, it was wrong as stated before.

    we have g(f(a)) = g(f(b)). since g is 1-1, this implies f(a) = f(b). but since f is 1-1, this means a = b, so that h is 1-1.

    again, just a little rearranging here. Let z \in Z. since g is onto, there is some y \in Y so that g(y) = z. But f is onto, so that there is some x \in X such that f(x) = y. But that means g(f(x)) = z. thus, h is onto

    nothing much wrong with this sentence
    awesome! thank you very much for all your help. i get it now! i just love the feeling when struggling math students have a 'eureka' moment and the light finally comes on and we "get" the problems. math can be cool thanks again!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    awesome! thank you very much for all your help. i get it now! i just love the feeling when struggling math students have a 'eureka' moment and the light finally comes on and we "get" the problems. math can be cool thanks again!
    haha, i love that too. i saw you had such a moment with Plato as well, and i couldn't help but feel proud of you and happy for you, though it was not me that helped you. i bet it made Plato feel good as well. though he wouldn't admit it probably
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Relations
    Posted in the Discrete Math Forum
    Replies: 33
    Last Post: April 24th 2010, 12:45 PM
  2. [SOLVED] Transitivity of Algebraic extension Fields
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 19th 2010, 01:59 PM
  3. [SOLVED] Help with equivalence relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2009, 06:44 PM
  4. [SOLVED] Equivalance Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 10th 2009, 02:10 AM
  5. [SOLVED] Showing Transitivity of a Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 23rd 2009, 11:16 PM

Search Tags


/mathhelpforum @mathhelpforum