Need Help With Elementary Proof

Question

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.

Answer 1

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.

Answer 2

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!

Answer 3

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.