# Thread: [SOLVED] Transitivity in set relations

1. ## [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.

2. Originally Posted by ilikedmath
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 $\displaystyle \alpha$ and $\displaystyle \beta$ be functions.
(a) if $\displaystyle \alpha$ and $\displaystyle \beta$ are onto, then $\displaystyle \beta \circ \alpha$ is onto
(b) if $\displaystyle \alpha$ and $\displaystyle \beta$ are 1-1, then $\displaystyle \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 $\displaystyle h$ is actually $\displaystyle g \circ f$

3. We are given that there are two bijections:
$\displaystyle f:X \leftrightarrow Y\quad \& \quad g:Y \leftrightarrow Z$.
What can be said about $\displaystyle g \circ f$ ?

4. Originally Posted by Jhevon
there is a theorem that says:

let $\displaystyle \alpha$ and $\displaystyle \beta$ be functions.
(a) if $\displaystyle \alpha$ and $\displaystyle \beta$ are onto, then $\displaystyle \beta \circ \alpha$ is onto
(b) if $\displaystyle \alpha$ and $\displaystyle \beta$ are 1-1, then $\displaystyle \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 $\displaystyle h$ is actually $\displaystyle 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.

5. Originally Posted by ilikedmath
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 $\displaystyle f : X \mapsto Y$ and $\displaystyle g : Y \mapsto Z$ are functions (f onto), then their composition is $\displaystyle g \circ f : X \mapsto Z$. it starts with elements in the domain of $\displaystyle f$, and takes them to the domain of $\displaystyle g$ where they are then mapped to the codomain of $\displaystyle g$

6. Originally Posted by Jhevon
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 $\displaystyle f : X \mapsto Y$ and $\displaystyle g : Y \mapsto Z$ are functions (f onto), then their composition is $\displaystyle g \circ f : X \mapsto Z$. it starts with elements in the domain of $\displaystyle f$, and takes them to the domain of $\displaystyle g$ where they are then mapped to the codomain of $\displaystyle 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.

7. ## 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?

8. Originally Posted by ilikedmath
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

9. Originally Posted by Jhevon
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.

10. Originally Posted by ilikedmath
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 $\displaystyle h : X \mapsto Z$ defined by $\displaystyle 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 $\displaystyle z \in Z$. since $\displaystyle g$ is onto, there is some $\displaystyle y \in Y$ so that $\displaystyle g(y) = z$. But $\displaystyle f$ is onto, so that there is some $\displaystyle x \in X$ such that $\displaystyle f(x) = y$. But that means $\displaystyle g(f(x)) = z$. thus, $\displaystyle h$ is onto

thus we have shown h is 1-1 and onto, therefore X ~ Z. QED.
nothing much wrong with this sentence

11. ## awesome

Originally Posted by Jhevon
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 $\displaystyle h : X \mapsto Z$ defined by $\displaystyle 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 $\displaystyle z \in Z$. since $\displaystyle g$ is onto, there is some $\displaystyle y \in Y$ so that $\displaystyle g(y) = z$. But $\displaystyle f$ is onto, so that there is some $\displaystyle x \in X$ such that $\displaystyle f(x) = y$. But that means $\displaystyle g(f(x)) = z$. thus, $\displaystyle 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!

12. Originally Posted by ilikedmath
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