Prove: if $f:\mathbb{N} \rightarrow A, g:\mathbb{N} \rightarrow B$ are surjections, there exists a surjection $h:\mathbb{N} \rightarrow A \cup B$

Question

I chose my own sets here for A and B as countably infinite pairwise disjoint subsets of $\mathbb{N}$. Can I do this with finite subsets and get an easier answer with the same result?

---

Suppose $A = \mathbb{N}_e$ such that $\mathbb{N}_e$ is the set of all even natural numbers. $\mathbb{N}_e \subset \mathbb{N}$

Also suppose $B = \mathbb{N}_o$ such that $\mathbb{N}_o$ is the set of all odd natural numbers. $\mathbb{N}_o \subset\mathbb{N}$

$\mathbb{N}_e \cup \mathbb{N}_o = \mathbb{N}$

$h: \mathbb{N} \rightarrow A \cup B$ is given by

$h(x) = $

$f(\frac{x}{2})$ if $x\in \mathbb{N}_e$

$g(\frac{x+1}{2})$ if $x\in \mathbb{N}_o$

Let $n \in \mathbb{N}$. If $n \in \mathbb{N}_e$, consider $x = 2n$

$f(x) = \frac{2n}{2} = n$

Let $n \in \mathbb{N}$. If $n \in \mathbb{N}_o$, consider $x = 2n-1$

$g(x) = \frac{(2n-1)+1}{2} = n$

So $h: \mathbb{N} \rightarrow A \cup B$ is surjective.

---

I'm kind of iffy on notation here. I'm wondering when it came to constructing the $h$ function, why it wasn't $f(x)$ if $x \in A$ or something like that. I get these two different things confused all of the time.

---

UPDATE

I understand what's wrong with this. I can't decide what $A$ and $B$ are because they might not actually even by numbers. The function $h$ assigns them numbers to cover everything. Kind of like a room of boys and girls and $f$ maps to all of the boys, and $g$ maps to all the girls? $h$ will map to the union, which is the entire room hence it is surjective.

Answer 1

HINT: You are supposed to be proving a general theorem about all pairs of sets $A$ and $B$ such that there are surjections $f:\Bbb N\to A$ and $g:\Bbb N\to B$, so you are not free to choose specific sets $A$ and $B$. Thus, your argument gets off very much on the wrong foot.

It is useful, however, to look at the sets $\Bbb N_e=\{2n:n\in\Bbb N\}$ and $\Bbb N_o=\{2n+1:n\in\Bbb N\}$. Note that there are bijections

$$\varphi:\Bbb N_e\to\Bbb N:n\mapsto\frac{n}2$$

and

$$\psi:\Bbb N_o\to\Bbb N:n\mapsto\frac{2n-1}2\;.$$

• Verify that $\varphi$ and $\psi$ are bijections.
• Show that $f\circ\varphi$ is a surjection from $\Bbb N_e$ to $A$.
• Show that $g\circ\psi$ is a surjection from ... ?
• Use the previous two points to construct a surjection from $\Bbb N$ to $A\cup B$.

Answer 2

@Brian M. Scott

Shouldn't $\mathbb{N}_o = \{2n -1: n \in \mathbb{N}\}$? Otherwise this will not output $1$.

Let's assume I already verified that $l: \mathbb{N}_e \rightarrow \mathbb{N}$ and $m: \mathbb{N}_o \rightarrow \mathbb{N}$ are bijections.

Then $f \circ l : \mathbb{N}_e \rightarrow A$

$g \circ m: \mathbb{N}_o \rightarrow B$

$h(n) = $

$f(l(n))$ if $n \in \mathbb{N}_e$

$g(m(n))$ if $n \in \mathbb{N}_o$

These composite functions will send the even and odd numbers to $A$ and $B$, respectively. This piecewise function $h$ which includes both thereby is surjective for all of $A \cup B$. (This is not my proof I'm just outlining my thoughts.

Are the functions supposed to be something like

$f(\frac{l(n)}{2})$ if $n \in \mathbb{N}_e$? That's one of the things that confused me. I don't often use the "$\mapsto$" notation in proofs if you can believe it, so this throws me off when it's used on functions.

---

UPDATE

$l(x) = 2x$

$m(x) = 2x-1$

Surjectivity-

If $n \in \mathbb{N}_e$

$h(n) = f(x) $

If $n \in \mathbb{N}_e$

$h(n) = g(x)$, which is surjective.

Answer 3

Let $h$ send the $n$th odd to $f_n$ and the $n$th even to $g_n$.