So, the problem sounds like this. You have two bijective functions $f:\mathbb{N} \to A$, $g:\mathbb{N} \to B$. We define the function $ h:\mathbb{N} \to A \cup B $, defined as: $$ h(n) = \begin{cases} f(n), & \text{if $n$ is even} \\ g(n), & \text{if $n$ is odd} \\ \end{cases} $$

Is $h$ bijective? How do you prove this? I know that you need to prove that $h$ is 1-1 and onto. How do you do that? If I attempt to write somtehing I lose myself on the way. Can somebody show me how it's done?

  • $\begingroup$ Try splitting it into cases for two integers $m$ and $n$: Both even, $m$ even and $n$ odd, both odd. Then check your definitions of 1-1 (injective) and onto (surjective) for each of the cases. $\endgroup$ – Zach Jun 23 '14 at 15:48
  • $\begingroup$ Another good reason why your function $h$ may not be bijective is that you define $h$ as follows: $g(1),f(2),g(3),f(4),g(5),\ldots$ - in other words, you skip many values for both $g$ and $f$. $\endgroup$ – mathse Jun 23 '14 at 18:20

The OP asked another question, namely, how to construct a bijective function $h:\mathbb{N}\rightarrow A\cup B$ from two bijective functions $f:\mathbb{N}\rightarrow A$ and $g:\mathbb{N}\rightarrow B$. To do so, let $h(1)=f(1)$ and let

$$h(n+1)= g(k)\text{ for smallest $k$ such that } g(k) \notin \{h(1),\ldots,h(n)\}$$

if $h(n)=f(m)$ for some $m$ and

$$h(n+1)=f(k)\text{ for smallest $f(k)$ such that } f(k) \notin \{h(1),\ldots,h(n)\}$$

if $h(n)=g(m)$ for some $m$. Then $h$ is injective and surjective.

  • 1
    $\begingroup$ You mean $h(n+1) = g(k)$, where $k$ is the smallest natural number such that $g(k) \not\in \{h(1),\ldots,h(n)\}$ (if $h(n) = f(m)$ for some $m$)? After all, the sets $A$ and $B$ need not be well-ordered themselves. $\endgroup$ – Hugh Denoncourt Jun 24 '14 at 0:05
  • $\begingroup$ Absolutely, thanks for catching that. $\endgroup$ – mathse Jun 24 '14 at 6:18
  • $\begingroup$ I looked over what you did and it seems pretty good for me. Thanks! $\endgroup$ – Bardo Jun 24 '14 at 9:46

$h$ is in general not bijective. As a counterexample, let $f:\mathbb{N}\rightarrow\mathbb{N}$ with $f(x)=x$ (identity function) and let $g:\mathbb{N}\rightarrow\mathbb{N}$ with $g(x)=x\pm 1$. Let $g(x)=x+1$ if $x$ is odd and let $g(x)=x-1$ if $x$ is even. Then $g$ looks as follows $(2,1,4,3,6,5,8,7,...)$ for $(1,2,3,4,5,6,7,8,...)$. Clearly, both $f$ and $g$ are bijective (why?). But if you let $m=1$ and $n=2$ then $h(1)=g(1)=2=f(2)=h(2)$, so $h$ is not injective.

But I would believe that you forgot to say that $A$ and $B$ are supposed to be disjoint.

  • $\begingroup$ Well A and B are not supposed to be disjoint. Thank you for your explanation. Then, how would you find a bijective function $h:\mathbb{N} \to A \cup B $ ? This is what I was trying to do and I thougt that the function h defiend above would be a good candidate.. $\endgroup$ – Bardo Jun 23 '14 at 16:46
  • $\begingroup$ Well, for example, if $B\supseteq A$ (or vice versa), why not let $h(x)=g(x)$? $\endgroup$ – mathse Jun 23 '14 at 17:39
  • $\begingroup$ @Bardo Below, I have given a more general solution to your question. I think it should be correct, but if you have doubts, why not open another thread? $\endgroup$ – mathse Jun 23 '14 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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