1
$\begingroup$

I'm working through a real analysis textbook, so I don't want the full answer. I'm only looking for a hint on this problem.

The book starts the proof like this: let $f$ be a bijection of $\mathbb{N}_m$ onto $A$, and let $g$ be a bijection of $\mathbb{N}_n$ onto $B$. Define $h$ on $\mathbb{N}_{m+n}$ as $h(i):=f(i)$ for $i=1, ..., m$, and $h(i):=g(i)$ for $i=m+1,...,m+n$. Show that $h$ is a bijection from $\mathbb{N}_{m+n}$ onto $A \cup B$.

Ok, so with that, I started out proving that $h$ is an injection into $A \cup B$. The usual method for this is to prove that if $h(i)=h(j)$, where $i,j=1,...,m+n$, then $i=j$. I think I proved this by looking at four cases.

  1. $1 \leq i,j \leq m$. In this case, $h(i)=f(i)$ and $h(j)=f(j)$, so because $f$ is a bijection, we know that $f(i)=f(j)$ implies that $i=j$.

  2. $ 1 \leq i \leq m$ and $m+1 \leq j \leq m+n$. We know that $i \neq j$ (obviously), so we want to prove that in this case, $h(i) \neq h(j)$. By definition, $h(i)=f(i)$ and $h(j)=g(j-m)$. Because $f$ is a bijection into $A$ and $g$ is a bijection into $B$, and $A \cap B = \emptyset$, we know that $f(i) \neq g(j-m)$, so $h(i) \neq h(j)$.

  3. This case is identical to case 2, except that $m+1 \leq i \leq m+n$ and $1 \leq j \leq m$, so the logic is reversed.

  4. The final case, where $m+1 \leq i,j \leq m+n$, is similar to case 1, because since $h(i)=g(i)$ and $h(j)=g(j)$, we can use the fact that $g$ is a bijection to prove that $g(i)=g(j)$ implies that $i=j$.

This is where I got stuck. I know I need to prove that $h$ is surjective, but am I on the right track for proving that it's injective? I think proving that $h$ is a surjection shouldn't be too hard, but I don't know if I'm approaching this part of the proof correctly.

$\endgroup$
2
  • 2
    $\begingroup$ I think you should have $h(i) = g(i-m)$. $\endgroup$
    – copper.hat
    Oct 16, 2013 at 0:05
  • $\begingroup$ $a \unites b$ will definitely give you a set of $|a|+|b|$ elements since no elements are common. (Their intersection is null). Isn't this an explanation? I'm only a high schooler; please correct me if I'm wrong. $\endgroup$ Mar 19, 2020 at 16:04

1 Answer 1

1
$\begingroup$

Your function $h$ isn’t well-defined: the domain of $g$ is $N_n$, not $\{m+1,\ldots,m+n\}$. You could, however, let $h(i)=g(i-m)$ for $i\in\{m+1,\ldots,m+n\}$. This is the definition that you actually use in Case 2, but in Case 4 you revert to the incorrect definition. Once you repair that error, your proof that $h$ is injective will be fine. (And surjectivity of $h$ won’t be much of a problem, since $f$ and $g$ are surjective.)

$\endgroup$
2
  • $\begingroup$ Yeah that makes a lot more sense; just a typo on my part I guess. Thanks! $\endgroup$
    – M T
    Oct 18, 2013 at 14:47
  • $\begingroup$ @Michael: You’re welcome! $\endgroup$ Oct 18, 2013 at 14:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .