Tao Analysis I - 3.6.5

Exercise 3.6.5

Let $A$ and $B$ be sets. Show that $A \times B$ and $B \times A$ have equal cardinality by constructing an explicit bijection between the two sets. Then use Proposition 3.6.14 to conclude an alternate proof of Lemma 2.3.2.

Proposition 3.6.14 are the six proposals regarding cardinal arithmetic we saw in the previous exercise.

Let's remind ourselves of Lemma 2.3.2 (Multiplication is commutative): Let $n, m$ be natural numbers. Then $n \times m = m \times n$.

Note that $A$ and $B$ are not specified to be finite. 

A possible bijection $f$ between $A \times B$ and $B \times A$ is one which simply swaps the components of the ordered pair

$$f((a,b)) = (b,a) \text{ for } (a,b) \in A \times B$$

This function is surjective because for every $(b,a) \in B \times A$ there exists an $(a,b) \in A \times B$ such that $f((a,b))=(b,a)$. The function is injective because $f((a,b))=f((a',b'))=(b,a)$ implies $(a,b)=(a',b')$.

Since a bijection exists between $A \times B$ and $B \times A$, the two sets have the same cardinality (even if they are not finite). $\square$

Now, because there is a bijection between $A \times B$ and $B \times A$, the two sets have the same cardinality. 

By Proposition 3.6.14 (e), the cardinality of the set $A \times B$ is $\#A \times \#B$. Similarly the cardinality of the set $B \times A$ is $\#B \times \#A$. Here $\#A$ and $\#B$ are natural numbers, and so requires the sets $A$ and $B$ to be finite.

If we name $m=\#A$ and $n=\#B$, the equality of cardinality gives us $m \times n = n \times m$, proving Lemma 2.3.2. $\square$