1
$\begingroup$

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.

  • 0
    It is not "hence we can write $(a+b)$." That part is a typo, and the $a+(b+1)$ is equal to $(a+b)+1$ by the inductive definition of addition. Please see my post, I did some editing, not much. It really is pretty ugly, for proving something so obvious. The problem is the use of the one to one correspondence (function) language, which forces us to construct functions.2012-02-09

1 Answers 1

0

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.