# Cardinality and ordinary mathematical induction

How do I approach this problem using ordinary mathematical induction?

Notation: If A and B are sets then we will say they are the same cardinality and write $A\approx B$ if there is a one-to-one and onto function from A to B.

Problem: If A and B are disjoint sets and $A\approx\tilde{a}$ and $B\approx\tilde{b}$ then $A\cup B\approx\widetilde{a+b}$. Prove by induction on $b$ that for every $a$ the statement is true.

-
What is the definition of $\tilde a$? How is addition defined? – Brian M. Scott Feb 9 '12 at 3:22
@AndréNicolas: If $\bar a$ and $\bar b$ are numerals, then probably the assumption $A\approx\bar a$ implies that $A$ must, in particular, be finite. Thus there would be no need to posit finiteness as an implicit assumption. – Henning Makholm Feb 9 '12 at 3:35
@AndréNicolas Fixed. – Atma Feb 9 '12 at 3:39
If by "ordinary induction" you mean "prove it for $0$; prove that if it holds for $k$ then it holds for $k+1$", and $A$ and $B$ can be finite or infinite, then such a proof wold be insufficient; it would only establish the result for $B$ finite. If the notation somehow implies that $B$ is finite, then show the result is true for $B=\emptyset$, for $B\approx\tilde{1}$, and then show that if it is true for $\tilde{k}$ then it is true for $\tilde{k+1}$ by writing $B=B'\cup C$ with $B'\approx \tilde{k}$ and $C\approx\tilde{1}$, and using associativity. – Arturo Magidin Feb 9 '12 at 4:11
@AndréNicolas thank you so much for the hint. Just one question, why are we restricting g′ to b~ ? – Atma Feb 9 '12 at 4:27

## 1 Answer

Fix $a$. As specified, we solve the problem by induction on $b$. The base case $b=0$ is straightforward. We know that there is a bijection $f$ from $\bar{a}$ to $A$. If $b=0$, then $B$ is empty, so $A\cup B=B$. Note that $a+0=a$. So the function $f$ is a bijection from $\overline{a+0}$ to $A\cup B$.

Now suppose that the result is true for a specific $b$. We show that the result is true for $b+1$. It is a good idea to see exactly what we need to show. Let $B'$ be a set of size $b+1$, meaning that there is a bijection from $\overline{b+1}$ to $B'$. We need to show that $A \cup B'$ has size $(a+b)+1$. More formally, we need to find a bijection from $\overline{a+(b+1)}$ to $A\cup B'$. Since by the inductive definition of addition, $a+(b+1)=(a+b)+1$, this is the same problem as finding a bijection from $\overline{(a+b)+1)}$ to $A\cup B'$.

We now proceed with the construction. It is fundamentally very easy. Unfortunately, the formality of the argument tends to hide the simplicity of the idea.

Let $B'$ be a set for which there is a bijection $g'$ from $\overline{b+1}$ to $B'$. Restrict the function $g'$ to $\bar{b}$. Call the resulting function $g$.

The image (range) of $g$ is a set $B$ which contains all but one point $x$ of $B'$. By the induction hypothesis, $\overline{a+b} \approx A\cup B$, so there is a bijection $h$ from \overline{a+b}$to$A\cup B$. Now let$h'$be the function that agrees with$h$on$\overline{a+b}$and that takes the "extra" element of$\overline{(a+b)+1}$to$x$. It is easy to verify that$h'$is a bijection from$\overline{(a+b)+1}$to$A\cup B'$. But by definition$a+(b+1)=(a+b)+1$, so$\overline{a+(b+1)}=\overline{(a+b)+1}$, and hence there is a bijection from$\overline{a+(b+1)}$to$A\cup B'\$. This completes the induction step.

-