Transitivity in set relations

In summary, if X ~ Y and Y ~ Z, then there exists a function h: X → Z that is 1-1 and onto. To show that h is 1-1 and onto, we can use the fact that X ~ Y and Y ~ Z imply the existence of functions f: X → Y and g: Y → Z that are both 1-1 and onto. By composing f and g, we can construct h, which will also be 1-1 and onto. Therefore, X ~ Z.
  • #1
pzzldstudent
44
0
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.
 
Physics news on Phys.org
  • #2
pzzldstudent said:
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[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
 
  • #3
Mark44 said:
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

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?
 
  • #4
by george, i think i got it! :D

pzzldstudent said:
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
 
  • #5


pzzldstudent said:
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.
pzzldstudent said:
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.
 
Last edited:

1. What is transitivity in set relations?

Transitivity in set relations is a property that states that if one element is related to a second element, and the second element is related to a third element, then the first element is also related to the third element. In other words, if A is related to B and B is related to C, then A is also related to C.

2. How is transitivity related to mathematical sets?

In mathematical sets, transitivity is an important property that helps establish relationships between elements. It allows us to make logical deductions and inferences based on the relationships between elements in a set.

3. What are some examples of transitive relations?

Some examples of transitive relations include "is a subset of" in mathematics, "is taller than" in height comparisons, and "is a parent of" in family relationships.

4. How does transitivity differ from reflexivity and symmetry?

Reflexivity is the property that states every element is related to itself, while symmetry is the property that states if A is related to B, then B is also related to A. Transitivity is a combination of both properties, stating that if A is related to B and B is related to C, then A is also related to C.

5. Why is transitivity important in mathematics and other sciences?

Transitivity is important in mathematics and other sciences because it allows us to establish relationships between elements and make logical deductions based on those relationships. It also helps us understand and analyze complex systems and phenomena by breaking them down into smaller, more manageable sets and their relationships.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
347
  • Calculus and Beyond Homework Help
Replies
9
Views
462
  • Calculus and Beyond Homework Help
Replies
2
Views
152
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
459
  • Calculus and Beyond Homework Help
Replies
3
Views
108
  • Calculus and Beyond Homework Help
Replies
2
Views
608
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
Back
Top