Proving bijection is an equivalence relation

7.2k Views Asked by At

If $M = \{A_n\}_{n=1}^\infty$ is a collection of sets. Consider a relation $R$ on $M$ where $ A_mRA_n$ if there exists a bijection from $A_m$ to $A_n$.

Here is my work so far. For symmetry if we assume $A_mRA_n$ then $A_nRA_m$ just by the definition of a bijection (not sure if there needs more to be said). For reflexivity, I am not too sure how I would show that $\forall n, A_nRA_n $, but I have an intuitive idea. But for transitivity I have no clue at all. My question is, how would I go about starting to prove reflexivity and transitivity and is my proof for symmetry fine?

1

There are 1 best solutions below

0
On BEST ANSWER

(1) Symmetry: a bijection is injective and surjective and has an inverse which is also a bijection. So if $\phi: A_n \to A_m$ is a bijection then $\phi^{-1}$ exists and $\phi^{-1} : A_m \to A_n$. So, $A_nRA_m \implies A_mRA_n$

(2) Reflexivity: define $\phi : A_n \to A_n $ as the identity mapping. This is a bijection. So, $A_nRA_n$

(3) Transitivity: If $\phi: A_n \to A_m$ and $\psi: A_m \to A_p$ are bijections then their composition $\psi.\phi: A_n \to A_p$ is a bijection. So, $A_nRA_m$ and $A_mRA_p \implies A_nRA_p$