I am trying to show that equality of cardinality is an equivalence relation.

I am a bit confused as to how I should approach this.

Currently, my understanding of equivalence relation is that a relation needs to be

reflexive, symmetric, and transitive in order to be an equivalence relation.

For instance, if I have

$A = \{1,2,3,5\}$

$R = \{(1,1),(2,2),(3,3),(5,5),(1,5),(5,1)\}$, $R \subseteq A \times A$

$R$ would be an equivalence relation.

If relation $R$ is an equality of cardinality, I am not sure as to how I can

show that it is reflexive, symmetric, and transitive.

Could somebody help me?

  • $\begingroup$ An equivalence relation is a relation on a single set $A$, e.g. a subset of the Cartesian product $A \times A$. Your example fails to be an equivalence relation because it is not a relation on $A \times A$ or $B\times B$, but on $A\times B$. $\endgroup$ – Xander Henderson Oct 20 '19 at 23:23
  • $\begingroup$ Welcome to Maths SX! How do you define equal cardinalities? $\endgroup$ – Bernard Oct 20 '19 at 23:36
  • $\begingroup$ Your example is not an equivalence relation because it is not reflexive. $2 \not R2$ for example. It is symmetric and transitive. $\endgroup$ – Ross Millikan Oct 20 '19 at 23:50

Hint. By definition, two sets $A$ and $B$ have the same cardinality, hence $A\sim B$, if there exists a bijection $A\to B$. On the other hand if we have a bijection $A\to B$ and $B\to C$, we need to show there is a bijection $A\to C$, which would mean that $A\sim B$ and $B\sim C$ implies $A\sim C$ (transitivity); can you try to do so using the fact that composition of bijections is a bijection? To show it is symmetric, given a bijection $A\to B$ we need to find a bijection $B\to A$, which should be easy to show, noting the fact that bijections have inverses which are also bijections. Finally to see $A\sim A$ (reflexivity) we just need to find a bijection from $A$ to itself, which should be easy to see.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy