1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Transitivity in set relations

  1. Oct 11, 2008 #1
    Suppose X, Y, Z are sets. If X ~ Y and Y ~ Z, prove that X ~ Z.

    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.
     
  2. jcsd
  3. Oct 11, 2008 #2

    Mark44

    Staff: Mentor

    The definition you're using for a one-to-one function is wrong. I'm going to dispense with the subscripts and just use a and b.

    Clearly, if a = b, then f(a) has to be equal to f(b), for any a in the domain of f. So that doesn't tell you anything interesting.

    A function f is one-to-one iff whenever f(a) = f(b), then a = b. You have the right idea for what an onto function is.

    I don't think you realize that your function from X to Z is necessarily a composition. I.e., h : X --> Z, where h = f[tex]\circ[/tex]g.

    f maps an element of X to an element of Y, and g maps an element of Y to an element of Z. You need to show that for any z1 and z2 in Z, and where z1 = h(x1), and z2 = h(x2), if h(x1) = h(x2), then it must be true that x1 = x2. That establishes that h is one-to-one.

    Now show that h is onto Z. IOW, for any z in Z, there is some x in X such that h(x) = z.
    Clear?

    Mark
     
  4. Oct 11, 2008 #3
    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?
     
  5. Oct 11, 2008 #4
    by george, i think i got it! :D

    With more help I think I got it:

    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.
    Consider the function h: X → Z where h = f o g.

    To show 1-1:
    Take a and b in Z. Assume h(a) = h(b) which implies 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. since g is onto, there is some y in Y so that g(y) = z. But f is onto, so there is an x in X such that f(x) = y. Which means g(f(x)) = z. thus, h is onto.
    Hence X ~ Z. QED.

    :D
     
  6. Oct 12, 2008 #5

    Mark44

    Staff: Mentor

    Re: by george, i think i got it! :D

    h maps an element of X to an element of Z, so a and b can't be elements of Z. What you need to do, instead, is look at elements in Z (call them z1 and z2), and see what their preimages are. I.e., what elements in Y get carried to z1 and z2, and for those elements in Y, what elements in X get carried to them. Something I think you'll need to use is the fact that both f and g are 1-1 and onto, which means there are inverses for each.
    That's correct, but you could be just a bit more explicit. Namely, for any z in Z, you have found an x in X such that h(x) = f(g(x)) = z.
     
    Last edited: Oct 12, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Transitivity in set relations
  1. Transitive Sets (Replies: 12)

Loading...