# Homework Help: Problem showing an equivalence relation

1. May 18, 2014

### Mr. Fest

1. The problem statement, all variables and given/known data
We say that two sets A and B have the "same powerfulness" if there is a bijection from A to B. Show that the relation "have the same powerfulness" is an equivalence relation between sets.

2. Relevant equations
An equivalence relation satisfy the following:
xRx (reflexive)
xRy --> yRx (symmetric)
xRy and yRz --> xRz (transitive)

3. The attempt at a solution
I'm not sure on where to begin to show that they bijective functions are reflexive.

They are symmetric since bijective functions can be reversed with the same domain (and same range).

They are transitive since the function going from A --> B is surjective as well as injective, meaning that the the range of A is a perfect subset of B (the range of the function contains every value of B). So if we then have another function B --> C (regardless of the whether the function B --> C is injective or surjective??) then A --> C as well.

So, I'm not sure how to show or rather explain that a bijective function is reflexive. And also, if my wording of why a bijective function is symmetric and transitive is wrong in any way, please correct me as I'm here to learn.

Appreciate all the help. Thanks in advance!

2. May 18, 2014

### vela

Staff Emeritus
You're overthinking it. Just come up with a bijection from A to A to show that A is related to A.

3. May 18, 2014

### LCKurtz

It isn't the bijective functions that are reflexive. It is the relation "have the same powerfulness" that is reflexive. It would be better stated that A is related to B if there is a [STRIKE]surjection[/STRIKE] bijection from A to B, which, of course, is what having the same power means.

Instead of stating "they are symmetric", you want to show if A is related to B (which means there is a [STRIKE]surjection[/STRIKE] bijection from A to B) then B is related to A. Write down what you are given and what you need to show. Your argument above shows me you know why it is true, but write down the steps.

 Note typo corrections.

Last edited: May 18, 2014
4. May 18, 2014

### Mr. Fest

But if it is a bijection A = B ergo A goes to A? Or am I thinking the wrong way?

5. May 18, 2014

### Mr. Fest

Isn't surjection that A = B and therefore the range of f is equal to B and domain of f-1 is also equal to B.

Just to make it clear, "same powerfulness" has not yet been mentioned in the textbook. I'm doing a chapter on "Functions and relations" where the focus has been on injection, surjection and bijection, equivalence relations and especially congruence modulus and that sort of counting.

Like this: If f is surjective then A = B and if injective f(x1) = f(x2) --> 1 = x2 since every every element of the range is the image of at most one element of the domain (f: A --> B). An effect of the surjection is that find you can find the reverse of the function so that you find each x giving the f(x) (f: B --> A). So, a bijection (having the same powerfulness) is symmetric.

6. May 18, 2014

### vela

Staff Emeritus
I'm not sure what this even means.

To establish reflexivity, you want to show that for any set A, it is related to itself, i.e., that it has the same powerfulness. To show that, you need to show there exists a bijection from A to A. Just give an example of a bijection from A to A, one that'll work for any set A.

7. May 18, 2014

### Mr. Fest

What I meant was that if f: A --> B and A is a perfect subset of B then A = B and ergo A goes to A. Example, y = x + 1 A = (-inf, inf) and B = (-inf, inf) then A = A and A --> B can be seen as A --> A. Is this what you mean/meant?

8. May 18, 2014

### LCKurtz

A=B doesn't make any sense. A might be {cat,dog,mouse,horse,elephant} and B might be {apple,orange,banana,papaya,pineapple}. Also please note my corrections in post #3 where I typed surjection when I meant bijection.

Last edited: May 18, 2014
9. May 19, 2014

### Mr. Fest

A = {1, 2, 3, 5, 7, 9}; B = {1, 2, 3, 5, 7, 9} then A is perfect subset of B correct? And if it is a perfect subset then the set A is equal to the set B, correct?

10. May 19, 2014

### LCKurtz

[STRIKE]NO! A is not a subset of B. They are completely different sets[/STRIKE]. I don't see the relevance of "perfect set" to this problem at all. Two sets are equal if they have the same elements. I think you are confusing set equality with equality of the size of the sets.

 Whoa. I didn't notice you changed my A and B which were different sets to identical sets. My last sentence above still stands.

Last edited: May 19, 2014
11. May 19, 2014

### Mr. Fest

But if two sets are equal, aren't they also equal in size...

12. May 19, 2014

### LCKurtz

Of course. But this thread is getting very confused and I believe you are too. So let's start again. Let's say set $A$ is related to set $B$ (written $A \sim B$) if there is a bijection from $A$ to $B$. Note that this has nothing to do with set equality $A=B$.

How would you show $\sim$ is a transitive relation, that is given$A\sim B$ and $B\sim C$, then $A\sim C$?

If you can do that you can probably do the other two properties that make an equivalence relation.

13. May 19, 2014

### Mr. Fest

Since the function A --> B is bijective you have only one image on B for every element in A and also the function A --> B covers all elements of B. So, if the same is given for B --> C then per definition A --> C and the function is transitive. I'm assuming this is correct?

And if the function A --> A is bijective, then also every element on A is given only one image on A and is therefore reflexive. I'm not sure how to explain it in words to be honest...

When it comes to the symmetricness, then if the function A --> B is bijective it can be reversed since you have only one image on B for every element in A and therefore B --> have the same property and it is therefore symmetric. Is this correct?

14. May 19, 2014

### LCKurtz

A vague paragraph like that tells me you have the idea, but math arguments use equations. You start with what you are given and prove the result. And, at the risk of repeating myself, it is not the function that is transitive, it is the relation $\sim$. Not to mention, what function are you talking about? That's the problem with paragraphs of prose instead of equations.

Here's how you should start. Given $A\sim B$ means there is a bijection $f$ from $A$ to $B$. Given $B\sim C$ means there is a bijection $g$ from $B$ to $C$.

We are trying to prove $A\sim C$, so we have to use the given to find a bijection from $A$ to $C$. You need to give a formula for such a bijection and an argument (equations) that your formula actually is a bijection.

15. May 20, 2014

### Mr. Fest

I'm at work now and I'm not sure if the solutions chapter states any thing like that. But for example f(x) = 2x; x $\in$ R then f: A --> B is bijective. We have a one-to-one correspondence.

It is symmetric since f: A --> B; f(x) = 2x. f: B --> A; f(y) = y/2.

f: A --> B; f(x) = 2x. f: B --> C; f(x) = 3x. Then A --> C since B --> C is f: A --> C; f(x) = 2x*3/2 = 3x. It is transitive.

Now, my problem is to show that it is reflexive...

Is it true to say, that since it is a bijection it is injective per definition and therefore we have that f(x1) = f(x2) if and only if x1 = x2 and therefore it is reflexive...?

Last edited: May 20, 2014
16. May 20, 2014

### LCKurtz

Mr. Fest, I'm afraid there is a level of abstraction here that you just aren't getting. Although you seem to have a general idea for when A and B are the real numbers, there is nothing in the problem about A and B being any specific kind of sets. And instead of addressing my specific suggestions about how to start, you change the subject.

I don't see how to proceed with the problem without working it for you, so I am going to abandon this thread. My last suggestion for you is that you need to sit down with your teacher and discuss these concepts. I think you need more help than we can give you here.

17. May 20, 2014

### Mr. Fest

You asked me to find a bijection so I did. Why not work it out for me? Might understand better if you do...if it's not too much to ask.

18. May 21, 2014

### Staff: Mentor

There is no "the function A-->B". The statement is "there is a bijective function". There can be many of them, and there is no single function specified, but that does not matter.

You have to show that such a function exists to show reflexivity.

That is good.

19. May 22, 2014

### Mr. Fest

Well, f(x) = x is such a function. Because then the image of A is always on A for all x $\in$ A. And we have shown reflexitivity... Also, it is both injective and surjective as we have f(x1) = f(x2) --> x1 = x2 and since every element in range is the image of one and only one element in the domain.

And for transitivity....

We have a bijective function f: A --> B and a function h: B --> C. Since f: A --> B is a bijective function, all of B is covered within the function and therefore we have that A --> C. The set C, is the range of the composite function h(f): A --> C where A is the domain of the bijective function f: A --> B. So, we have transitivity.

Have we now shown that bijection functions have the properties of an equivalence relation, that is, reflexitivity, symmetry and transitivity...?

Maybe I forgot to tell you that the book used in this course is native swedish so that's maybe why I can't express myself properly...

20. May 22, 2014

### micromass

Correct.

The function $h$ should also be bijective. Why can you assume that $h$ is a bijection?

"We have that $A\rightarrow C$", what does this mean?

The composition is usually denoted as $h\circ f$. You will want to show that this composition is a bijection

If you could prove that $h\circ f$ is a bijection, then that would prove transitivity, correct.

A bijection cannot have the properties of an equivalence relation. It doesn't make any sense for a bijection to be reflexive, symmetric or transitive.

It is the relation "there exists a bijection between the two sets" that is reflexive, symmetric and transitive and thus an equivalence relation. It is not the bijections.

21. May 22, 2014

### Mr. Fest

Great!

It's because B is the range of A, and the function f: A --> B is bijective (all elements of B is "used"), therefore the function h: B --> C, where B is the domain will also be bijective. This is what springs to mind at first thought. But I'm not completely certain.

What I meant was that the composition $h\circ f$: A --> C.

This composition is a bijection, since $h\circ f$: A --> C has the same properties as both f: A --> B and h: B --> C. I'm really not sure how to show that $h\circ f$: A --> C is bijective as well. I mean isn't it so per definition?

As I said above, I'm not sure how to do that...

Thank you for clearing that up.

I really hope that you can help me more. It is very appreciated!

22. May 22, 2014

### HallsofIvy

You can't simply assert that a combination of things has the "same properties" as the things! And neither the definition of "bijective" nor "composition" says any thing about the other. You need to prove this is true. To prove the composition is bijective, you need to show it is both injective and surjective, using the definitions.

To show that $h\circ f$ is injective, you must show that "if $h\circ f(x_1)= h\circ g(x_2)$ then $x_1= x_2$". Okay, if $h\circ f(x_1)= h\circ g(x_2)$ then, because h is injective, $g(x_1)= g(x_2)$. Get the idea?

Similarly, to show that $h\circ f$ is surjective, you must show that "if $y\in C$ the there exist $x\in A$ such that $h\circ f(x)= y$. Okay, if $y\in C$ since f is surjective there exist $z\in B$ such that $f(z)= y$. Get the idea?