How do I show this is a surjection? Problem: Assume $f: \mathbb{N}_0 \rightarrow X$ and $g: \mathbb{N}_0 \rightarrow Y$ are bijections. Prove that the function $h: \mathbb{N}_0 \rightarrow X \cup Y$ defined as  \begin{align*} h(n) = \begin{cases} f(k) & \text{if} \ n=2k-1 \ \text{is odd}, \\ g(k) & \text{if} \ n = 2k \ \text{is even} \end{cases} \end{align*} is a surjection. Is this a bijection?
I'm not sure how one would go about showing this. I need to show that for every $z \in X \cup Y$ there exists an $n \in \mathbb{N}_0$ such that $h(n) = z$. But I'm confused with the notation here.
 A: $f,g$ are bijections and we are considering:
$$h(n)=\left\{\begin{array}{cl}
f(k) & n=2k-1 \\
g(k) & n=2k
\end{array}\right.$$
Now if $\mathbb{N}_0$ includes 0 this is not a surjection. That is because to get $k=0$ and thus $f(0)$ as a value for $h$ we should have $n=-1$ since $2k-1=2\cdot0-1=-1$. But $-1$ is certainly not in the domain of $h$. If $0\not\in\mathbb{N}_0$, then this is a surjection. Indeed, set $z\in X\cup Y$. If $z\in X$, then $z=f(k)$ for some $k$. Set $n=2k-1$ and $h(n)=z$. $k\in\mathbb{N}_0$ so $k$ is a strictly positive integer, so $2k-1$ is also strictly positive, and thus in the domain of $h$. If $z\in Y$, then $z=g(k)$ for some integer, and $n=2k$ is also a positive integer, strictly positive if $k\gneq0$. If 0 is included in $\mathbb{N}_0$, we must tweak the top branch by adding 2 to it, i.e. consider:
$$h(n)=\left\{\begin{array}{cl}
f(k) & n=2k+1 \\
g(k) & n=2k
\end{array}\right.$$
This way, if $z\in X$, $z=f(k)$, and $2k+1$ is in $\mathbb{N}_0$, i.e. is a nonnegative integer, iff $k$ is one. And the other branch is no problem.
As a bonus, taking the untweaked function with $0\not\in\mathbb{N}_0$ let us see if it is injective. Suppose $h(n)=h(m)$. $h(n)=h(m)$ means $h(n),h(m)$ both belong to the same set, whether it be $X$ or $Y$, and this, by definition of $h$, implies $n$ and $m$ have the same parity (or are congruent modulo 2), i.e. they are either both odd or both even. Suppose they are both even. Then $h(n),h(m)\in X$, and we are in the upper branch. So $h(n)=f(\frac{n+1}{2})$, and similarly for $h(m)$. Now $f$ is injective, so $\frac{n+1}{2}=\frac{m+1}{2}$, which is equivalent to $n=m$. Similarly, if they belong to $Y$, then $h(n)=g(\frac n2)$, and similarly for $m$, so $\frac n2=\frac m2$ which means $n=m$.
Addendum:
Whoops! I just read the above answer and it made me consider something I previously had overlooked: $X\cap Y$. In the above, I assumed $X$ and $Y$ had nothing in common, i.e. $X\cap Y=\varnothing$. Of course, if that is not true, $h$ is not injective, since if $z\in X\cap Y$, $z=f(k)=g(p)$ and so I can find two integers such that $h(n)=z=h(m)$, precisely $2k-1$ and $2p$.
A: The definitions are referencial.
We need to prove


*

*$h$ is a function (using Definition 1).

*The function $h$ is a surjection (using Definition 3).

*The function $h$ is a injection (using Definition 2). This prove that it is a bijection (see Definition 4).



Assuming proved 1.
Proof of 2 ($h$ is a surjection). By Definition 3, we need to prove that for every $z\in X\cup Y$, there exists a $n\in\Bbb N_0$, such that $h(n)=z$. So, let $z\in X\cup Y$. By definition of union, $z\in X$ or $z\in Y$. Suppose that $z\in X$. Then there is a $k\in\Bbb N_0$ such that $f(k)=z$, since $f$ is a bijection (in particular, it's a surjection; see Definition 3). By definition of odd number, clearly $n:=2k-1$ is odd. Thus $h(n)=f(k)=z$ by definition of $h$. Similarly when $z\in Y$. Thus $h$ satisfy the Definition 3. Hence $h$ is a surjection.
Observation about 3. Let $n,m$ in $\Bbb N_0$ and $n\ne m$ (hypothesis to prove that $h$ is a injection). Suppose $n$ and $m$ are odd, with $n=2k_n-1$ and $m=2k_m-1$ by definition of odd number. Clearly $k_n\ne k_m$, so $f(k_n)\ne f(k_m)$ since $f$ is a bijection (in particular, it's a injection; see Definition 2). Thus $h(n)=f(k_n)\ne f(k_m)=h(m)$. Hence $h(n)\ne h(m)$ and $h$ is a injection by Definition 2. Similarly when $n$ and $m$ are even. But when $n$ is odd and $m$ is even (or vice versa), we cannot assert that $f(k_n)\ne g(k_m)$, unless $X$ and $Y$ are disjoint or they no maps to equal outputs . So, in general it is no true that $h$ is an injection.

EXTRA (about injectivity) Suppose $h$ is an injection. 


*

*Let $n$ be an odd number. Clearly $m:=n+1$ is an even number and $n\ne m$, so we have $h(n)\ne h(m)$ (because $h$ is a injection). Also $n=2k-1$ for some $k\in\Bbb N_0$ and $m=2k$ (for the same $k$). Thus $f(k)=h(n)\ne h(m)=g(k)$. Similarly with $n$ even. We conclude that $f(k)\ne g(k)$ for any $k\in\Bbb N_0$ since $n$ was arbitrary, i.e., $f\ne g$. (We can use induction to prove this.) Now we don't have the hypothesis $f\ne g$ to prove that $h$ is a injection.

*Let $n$ be an odd and let $m$ be an even, so $n=2k_n−1$ and $m=2k_m$. By definition of the function $h$, we know that $h(n)=f(k_n)$ and $h(m)=g(k_m)$. With the hypothesis $X\cap Y\ne\emptyset$ and $f(k_n)=x=g(k_m)$ for some $x\in X\cap Y$, we have $h(n)=f(k_n)=g(k_m)=h(m)$, i.e., $h(n)=h(m)$ when $n\ne m$ and hence $h$ cannot be a injection, a contradiction to the hyptohesis $h$ is an injection. So we need the hypothesis $X\cap Y=\emptyset$ to prove that $h$ is an injection.

*Also, since $h$ is an injection, we have that $h$ ia a bijection. Thus $h^{-1}\colon X\cup Y\to \Bbb N_0$ is a function. If $X\cap Y\ne\emptyset$, then $h^{-1}$ cannot be a function unless $f(z)=g(z)$ for every $z\in X\cap Y$. To see this:


*

*Let $O$ be the set of odd numbers and let $E$ be the set of even numbers.

*Since $f$ and $g$ are bijections, they have inverses $f^{-1}$ and $g^{-1}$.

*For some $z\in X\cap Y$ suppose $n=f^{-1}(z)$, $m=g^{-1}(z)$ and $n\ne m$.

*Then $h^{-1}$ cannot be a function because it maps a element to two different elements, and hence it is not an injection.





Definition 1 (Function). Let $X$ and $Y$ sets. Then we define the function $f\colon X\to Y$ the object which, given any input $x\in X$, assigns a unique output $f(x)\in Y$.
Definition 2 (Injection). A function $f$ is an injection if different elements map to different elements: $$x\ne x'\implies f(x)\ne f(x').$$
Definition 3 (Surjection). A function $f$ is a surjection if every element in $Y$ comes from applying $f$ to some element in $X$: $$\text{For every } y\in Y\text{, there exists } x\in X\text{ such that } f(x)=y.$$
Definition 4 (Bijection). Functions which are both injection and surjection are also called bijections.

A: Hint:


*

*Function $\phi(k) = 2k-1$ is a bijection between $\{1,2,3,\ldots\}$ and $\{1,3,5,\ldots\}$.

*Given a bijection $f : \{1,2,3,\ldots\} \to X$, can you find a bijection $f' : \{1,3,5,\ldots\} \to X$?

*If $A \cap B = \varnothing$ and $X \cap Y = \varnothing$ then given bijections $f : A \to X$ and $g : B \to Y$ you can construct a bijection $h : A \cup B \to X \cup Y$ by
$$h(c) = \begin{cases}f(c) & \text{ if } c \in A,\\g(c) & \text{ if } c\in B.\end{cases}$$
To put it into words, suppose you have two collections of arrows like $\bullet \to \bullet$ such that no two arrows have the same head or tail, and the sets of heads and the sets of tails are disjoint, then in the union of these collections we still have the same property.

*What if $X \cap Y \neq \varnothing$?


I hope this helps $\ddot\smile$
