Exercise 3.6.5 (Cartesian product of A,B and B,A have equal cardinality)

Before we prove this, just note that we do not require that $A$ and $B$ be finite for the first part to be true. But we do have to check two cases: (1) At least one of $A$ or $B$ is empty, (2) Neither are empty.

Proof. Let $A$ and $B$ be sets. Consider the following sets:

(1) If at least one of $A$ or $B$ is empty, then, by Exercise 3.5.8, we have $A\times B=\varnothing$ and $B\times A=\varnothing$. This implies, by Exercise 3.6.2, that $\#(A\times B)=0$ and $\#(B\times A)=0$, implying $\#(A\times B)=\#(B\times A)$, as was to be shown (technically, I did not make an explicit bijection for this case, but it should be easy to do).

(2) Now suppose neither $A$ nor $B$ is empty. Let’s define a function $f:A\times B\to B\times A$ by $f((a,b))=(b,a)$.

Let’s show $f$ is injective (one-to-one). Let $a_1,a_2\in A$ and $b_1,b_2\in B$ such that $f((a_1,b_1))=f((a_2,b_2))$. We want to show this implies $(a_1,b_1)=(a_2,b_2)$. Well, $f((a_1,b_1))=f((a_2,b_2))$ implies $(b_1,a_1)=(b_2,a_2)$ by definition of $f$. Then, by Definition 3.5.1, we have $b_1=b_2$ and $a_1=a_2$, which is logically equivalent to $a_1=a_2$ and $b_1=b_2$. Then, by Definition 3.5.1 again, we have $(a_1,b_1)=(a_2,b_2)$. Hence, $f$ is injective.

Let’s show $f$ is surjective (onto). Let $(b^{\prime },a^{\prime })\in B\times A$ be any element of $B\times A$. We want to show there exists a $y\in A\times B$ such that $f(y)=(b^{\prime },a^{\prime })$. Indeed, choosing $y=(a^{\prime },b^{\prime })$ makes it true. Hence, $f$ is surjective (if this argument isn’t to your liking, then an alternative is to show the forward image $f(A\times B)$ equals $B\times A$).

By showing $f$ is injective and surjective, we have shown it is bijective (a one-to-one correspondence). This implies, by Definition 3.6.1, that $A\times B$ and $B\times A$ have equal cardinality.

Now we prove Lemma 2.3.2 using the above and Proposition 3.6.14. Suppose we have two finite sets $X$ and $Y$ with $\#(X)=n$ and $\#(Y)=m$. By part (e) of Proposition 3.6.14, we have $\#(X\times Y)=n\times m$ and $\#(Y\times X)=m\times n$. We proved above that $X\times Y$ and $Y\times X$ must have equal cardinality. Thus, $n\times m=m\times n$, proving Lemma 2.3.2.