# Prove that a function is bijective

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?

• 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. – Zach Jun 23 '14 at 15:48
• 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$. – 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.

• 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. – Hugh Denoncourt Jun 24 '14 at 0:05
• Absolutely, thanks for catching that. – mathse Jun 24 '14 at 6:18
• I looked over what you did and it seems pretty good for me. Thanks! – 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.

• 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.. – Bardo Jun 23 '14 at 16:46
• Well, for example, if $B\supseteq A$ (or vice versa), why not let $h(x)=g(x)$? – mathse Jun 23 '14 at 17:39
• @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? – mathse Jun 23 '14 at 17:52