Prove the Cartesian product of two finite sets is finite without using cardinality.

I am using ZFC and the following definitions:

$x$ is finite iff it is in bijection with a natural number;

$x$ is infinite iff it contains an injective image of $\omega$, the set of natural numbers.

Alternatively, we also have the following definition for finite:

A set $x$ is finite if every nonempty element of the power-set of x has an inclusion minimal element.

How can this be proved making use of these definitions? Note, cardinality has not been introduced at this point.

• "$x$ is finite iff it is in bijection with a natural number." Why not use then that $|A\times B|=|A|\times |B|$ for finite sets $A$ and $B$. If $|A|=a$ and $|B|=b$, why not come up with an explicit bijection between $A\times B$ and $[ab]$? – JMoravitz Sep 25 '17 at 0:20
• @JMoravitz note the fact that cardinality hasn't come up yet my guess is it's for a class and they should show some effort. – user451844 Sep 25 '17 at 0:26
• If $A$ and $B$ are finite, we can find natural numbers $n$ and $m$ and bijections $f:A\to\{1,\ldots,n\}$ and $g:B\to\{1,\ldots,m\}$. Using $f$ and $g$, can we find a bijection $h:A\times B\to\{1,\ldots,nm\}$? – John Griffin Sep 25 '17 at 0:30
• We don't know what have come up in class already. Did you learn induction? Induction on finite sets style Kuratowski? Something else? – Asaf Karagila Sep 25 '17 at 5:09
• @AsafKaragila We have learned induction! – IgnorantCuriosity Sep 25 '17 at 10:21

Fix $A$. Now you can prove this by induction on the cardinality of $B$, noting that the base case, $B$ with $0$ elements, is trivial (what is $A\times\varnothing$?), and by proving that $A\times(B\cup\{b\})=(A\times B)\cup(A\times\{b\})$ when $b\notin B$.

Of course, this is predicated on you already knowing that the union of two finite sets is finite. If you have not proved that yet, you should prove this as well, and this is also done by induction.

Let both $X_1$ and $X_2$ be finite sets with bijective maps

$\tag 1 \sigma_1: X_1 \to n_1$ $\tag 2 \sigma_2: X_2 \to n_2$

to the natural numbers $n_1$ and $n_2$.

The Cartesian product of the functions $\sigma_1$ and $\sigma_2$ gives a bijection

$\tag 3 \sigma_1 \times \sigma_2: X_1 \times X_2 \to n_1 \times n_2$

If you have defined the product of two natural numbers $n_1$ and $n_2$ then you know that $n_1 n_2$ can be put into a bijective correspondence with $n_1 \times n_2$. If you only have addition, then you have some more work to do.

The successor function $S$ can be used to define the multiplication of the natural numbers once you have addition 'bijectively nailed as a disjoint union'.

For multiplication,

$\tag 4 a × 0 = 0$

$\tag 5 a × S(b) = (a × b) + a$

and you 'nail down' the product $a \times b$ of two natural numbers to the cartesian product of two finite sets. Of course this brings us right back to Asaf's answer:

$\tag 6 A\times(B\cup\{\hat b\})=(A\times B)\cup(A\times\{\hat b\}) \; \; \hat b \notin B$