Tao Analysis I - 3.6.1

Exercise 3.6.1

Prove Proposition 3.6.4. 

Proposition 3.6.4 Let $X$, $Y$, $Z$ be sets. 

• Then $X$ has equal cardinality with $X$ . 
• If $X$ has equal cardinality with $Y$, then $Y$ has equal cardinality with $X$.
• If $X$ has equal cardinality with $Y$ and $Y$ has equal cardinality with $Z$, then $X$ has equal cardinality with $Z$.

Discussion

The first part of the proposition says that cardinality is symmetric. The second says it is reflective. The third says it is transitive. These are the requirements of an equivalence relation.

We will use properties of bijective functions that we have previously established - that they are symmetric, reflexive and transitive (link).

Reflexive

Let's start with Definition 3.6.1, which says two sets $X$ and $Y$ have equal cardinality iff there exists a bijection $f:X \to Y$ from $X$ to $Y$.

We already know that bijections are reflexive, and so $\#X=\#X$. $\square$

Symmetric

We know bijections are symmetric, and so if $\#X=\#Y \implies \#Y=\#X$. $\square$

Transitive

We know bijections are transitive. That is, the composition of two bijections is also a bijection.  And so $(\#X=\#Y) \land (\#Y=\#Z) \implies \#X=\#Z$. $\square$