# [SOLVED] Transitivity in set relations

• Oct 11th 2008, 03:27 PM
ilikedmath
[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.
• Oct 11th 2008, 03:39 PM
Jhevon
Quote:

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.

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$
• Oct 11th 2008, 03:43 PM
Plato
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$ ?
• Oct 11th 2008, 03:54 PM
ilikedmath
Quote:

Originally Posted by Jhevon
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.
• Oct 11th 2008, 04:01 PM
Jhevon
Quote:

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 :D

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$
• Oct 11th 2008, 04:32 PM
ilikedmath
Quote:

Originally Posted by Jhevon
what do you mean cross-product? i think you are confusing the ideas here with those in your other thread :D

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.
• Oct 11th 2008, 04:57 PM
ilikedmath
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?(Wondering)
• Oct 11th 2008, 05:05 PM
Jhevon
Quote:

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?(Wondering)

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
• Oct 11th 2008, 05:13 PM
ilikedmath
Quote:

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.
• Oct 11th 2008, 05:29 PM
Jhevon
Quote:

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 $h : X \mapsto Z$ defined by $h = g \circ f$"

Quote:

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.

Quote:

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

Quote:

thus we have shown h is 1-1 and onto, therefore X ~ Z. QED.
nothing much wrong with this sentence :D
• Oct 11th 2008, 05:43 PM
ilikedmath
awesome
Quote:

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 $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 :D

(Clapping)awesome! thank you very much for all your help. i get it now! (Rofl) 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 (Cool) thanks again!
• Oct 11th 2008, 05:48 PM
Jhevon
Quote:

Originally Posted by ilikedmath
(Clapping)awesome! thank you very much for all your help. i get it now! (Rofl) 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 (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 (Giggle)