Problem showing an equivalence relation

[Mr. Fest]

Homework Statement

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.

Homework Equations

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

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!

 

[vela]

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

 

[LCKurtz]

Homework Statement

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.

Homework Equations

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

The Attempt at a Solution

I'm not sure on where to begin to show that they bijective functions are reflexive.

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.

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

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.

[Edit] Note typo corrections.

 

[Mr. Fest]

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

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

 

[Mr. Fest]

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 surjection from A to B, which, of course, is what having the same power means.

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.

Instead of stating "they are symmetric", you want to show if A is related to B (which means there is a surjection 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.

Like this: If f is surjective then A = B and if injective f(x₁) = f(x₂) --> ₁ = x₂ 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.

 

[vela]

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

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.

 

[Mr. Fest]

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.

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?

 

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

 

[Mr. Fest]

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.

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?

 

[LCKurtz]

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?

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

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

 

[Mr. Fest]

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

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

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

 

[LCKurtz]

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

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.

 

[Mr. Fest]

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.

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?

 

[LCKurtz]

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?

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.

 

[Mr. Fest]

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.

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(x₁) = f(x₂) if and only if x₁ = x₂ and therefore it is reflexive...?

 

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

 

[Mr. Fest]

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.

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.

 

[mfb]

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?

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.

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

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

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?

That is good.

 

[Mr. Fest]

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.

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(x₁) = f(x₂) --> x₁ = x₂ and since every element in range is the image of one and only one element in the domain.

That is good.

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

 

[micromass]

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(x₁) = f(x₂) --> x₁ = x₂ and since every element in range is the image of one and only one element in the domain.

Correct.

And for transitivity...

We have a bijective function f: A --> B and a function h: B --> C.

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

Since f: A --> B is a bijective function, all of B is covered within the function and therefore we have that A --> C.

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

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.

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

So, we have transitivity.

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

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

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.

 

[Mr. Fest]

Correct.

Great!

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

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.

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

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

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

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?

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

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

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.

Thank you for clearing that up.

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

 

[HallsofIvy]

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?

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?

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!