Is Transitivity Valid in Set Relations?

[pzzldstudent]

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.

 

[Mark44]

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.

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$$\circ$$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

 

[pzzldstudent]

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$$\circ$$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

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?

 

[pzzldstudent]

by george, i think i got it! :D

Okay, here's what I got so far:

Am I on the right track?

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

 

[Mark44]

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.

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.

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.

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.