1

Prop: For sets A and B, say A ~ B iff there exists a bijection from A to B. Then ~ is an equivalence relation on sets.

I understand that an equivalence relation holds the properties of reflexive, symmetric, and transitive. I am also aware of their definitions, however, I am struggling to write a proof for this proposition.

I would assume we can suppose there is a bijection between A and B, as this would imply there is a bijection between the two. This would also mean that the two sets have equal cardinality but from this point on I am completely lost, the direction of the proof seems very unclear.

A hidden answer (written proof) would be great with some visible guidance or hints so enhance my understanding.

Thank you.

Zdravstvuyte94
  • 101
  • Hint: To prove symmetry, you must show there's a bijection from $B$ to $A$ when you know there is one from $A$ to $B$. Can you figure out what is should be? Rewrite the other two conditions (reflexive,, transitive) in terms of the existence of bijection, and find one. (I'm pretty sure this question is an exact duplicate of another on this site.) – Ethan Bolker Dec 16 '18 at 22:57
  • @EthanBolker That's actually the strategy needed for the symmetric condition. – J.G. Dec 16 '18 at 22:58
  • @EthanBolker Isn't that symmetry you stated in the opening of your post? Reflexivity would be essentially showing each set is bijective with itself. – PrincessEev Dec 16 '18 at 22:58
  • 1
    @J.G. Yes thanks fixed. – Ethan Bolker Dec 16 '18 at 23:00

3 Answers3

1

Showing that these properties hold is a straightforward application of the definitions, with some elementary properties of bijections. So, I suspect what you are having trouble with is formulating a proper proof. I will show reflexivity as an example.

We want to show that for any set $A$, we have $A \sim A$. Because of how we defined $\sim$, this means that for any set $A$, we need to show that there exists a bijection $f : A \rightarrow A$. How do we show this? We must construct such a function explicitly. Since we know nothing of the contents of $A$, there is really only one choice: the identity function.

Let $f : A \rightarrow A$ be the function such that $f(a) = a$ for every $a \in A$. We must check that $f$ is bijective. First, $f$ is injective: if $f(a) = f(b)$, then $a = f(a) = f(b) = b$, so $a = b$. Next, $f$ is surjective: if $a \in A$, then there exists an element $x \in A$ such that $f(x) = a$: namely, $x = a$.

So, we have shown that for any set $A$, we can construct a bijection $f : A \rightarrow A$, which shows that $A \sim A$. This shows the reflexivity of $\sim$. Others have provided hints for the other two properties.

Sambo
  • 6,243
0

Since $f(x)=x$ bijects $A$ to $A$, $\sim$ is reflexive. Write a similar proof $\sim$ is symmetric, using the fact bijections have inverses; write a similar proof $\sim$ is transitive, using a composition of bijections.

J.G.
  • 115,835
0

We only need to show three properties:

Reflexiveness:

Does there exist for ANY set $A$ a bijective function between the set and itself? If so, we can say that $A \sim A$.

Hint, what if there were a function that assigns $f(a)=a$ for all $a \in A$, how do we call this function?

Symmetry: If $A \sim B$, there exists a bijection between these two sets. Any bijective function is also invertible, so does there exist a bijection between $B$ and $A$? if so, we can say that $B \sim A$

Transivity:

Finally, if $A\sim B$ and $B \sim C$, we know there are bijective functions $f$ and $g$, what do we know about the composition of two bijective functions?

Good luck!