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
    What is the definition of $\tilde a$? How is addition defined?2012-02-09
  • 0
    @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.2012-02-09
  • 0
    @AndréNicolas Fixed.2012-02-09
  • 0
    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.2012-02-09
  • 0
    @AndréNicolas thank you so much for the hint. Just one question, why are we restricting g′ to b~ ?2012-02-09
  • 0
    @Atma: It is a bit of fussiness on my part. We want to use the fact that if $B$ is a set of size $b$, everything is OK. To say size $b$, we need a function from $\tilde{b}$ to $B$. The function $g'$ is not such a function, since its domain is $\widetilde{b+1}$.2012-02-09
  • 0
    @AndréNicolas Sorry to bother you again, in the last part "Now let h′ be the map that agrees with h..." By map do you mean range of h?2012-02-09
  • 0
    @Atma: By map I mean mapping, or function. Since $\approx$ is defined in terms of the existence of certain $1-1$ onto functions (bijections), in principle we have to produce such a bijection. We could bypass all this and give a more informal proof, but by the sound of things this is supposed to be a pretty formal exercise. What level is the course?2012-02-09
  • 0
    @AndréNicolas thanks again for clarifying that. This is a first year course for problem solving.2012-02-09
  • 0
    @Atma: Ouch! I thought it might be third year or so. I probably used too fancy language. In a sense the result is obvious, add one more element to $B$, you add $1$ to the count of $A\cup B$. The unpleasant part is expressing all this using explicit one to one correspondences.2012-02-09
  • 0
    @AndréNicolas is this correct so far: Let g' be a one-to-one function from b+1~ to B'. We restrict the domain of g' to b~ and call this function g. The range of g contains all points of B except for one point x of B'. By induction hypothesis A U B = a + b~, let h be a one-to-one function from a+b~ to A U B. Hence, we can write (a+b)=a+(b+1)=(a+b)+1. Now let h' be function such that it holds for h on a+b~ and maps the extra element of (a+b)+1~ to x. This h' is a one-to-one funtion to A U B'.2012-02-09
  • 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.