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.
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 and are functions (f onto), then their composition is . it starts with elements in the domain of , and takes them to the domain of where they are then mapped to the codomain of
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
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.
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 defined by "
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.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.
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 . since is onto, there is some so that . But is onto, so that there is some such that . But that means . thus, is ontoTo 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.
nothing much wrong with this sentencethus we have shown h is 1-1 and onto, therefore X ~ Z. QED.