Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 7 more comments

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.