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.
 A: 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. 
