A surjection from three countably infinite subsets of the natural numbers?

Question

I am trying to construct such a surjection.

More specifically, given

$f: \mathbb{N} \rightarrow A$

$g: \mathbb{N} \rightarrow B$

$h: \mathbb{N} \rightarrow C$

as surjections, where $A,B,C \subset \mathbb{N}$ and are countably infinite.

I have some find some surjection $j$ such that

$j: \mathbb{N} \rightarrow A \cup B \cup C$ is a surjection.

Obviously decomposing $\mathbb{N}$ into the evens and odds is trivial, but having to do 3 separate sets is a little more confusing.

---

Define $j: \mathbb{N} \rightarrow A \cup B \cup C$ for $x \in \mathbb{N}$ as

$j(x) = $

• $3(f(x)) -2$ if $x \in A$
• $3(g(x)) -1$ if $x \in B$
• $3(h(x))$ if $x \in C$

Let $y \in (A \cup B \cup C)$.

If $y = 3x-2$ for $x \in \mathbb{N}$, choose $x = \frac{y+2}{3}$

$j(x) = 3*\frac{y+2}{3}-2$

$j(x) = y$

If $y = 3x-1$ for $x \in \mathbb{N}$, choose $x = \frac{y+1}{3}$

$j(x) = 3*\frac{y+1}{3}-1$

$j(x) = y$

If $y = 3x$ for $x \in \mathbb{N}$, choose $x = \frac{y}{3}$

$j(x) = 3*\frac{y}{3}$

$j(x) = y$

So $j$ is surjective.

I cut out the intermediate algebra points for two of the cases, but you see my point. I may have flubbed the notation in some parts. Please let me know what works and what doesn't.

Answer 1

Hint: Consider sending $3n-2$, $3n-1$, and $3n$ to the $n^{th}$ element of $A$, $B$, and $C$, respectively, using your original surjections.

Answer 2

And for $m$ disjoint sets, consider $jm+k$ for $0 \le k \le m-1$.

Answer 3

You have the right idea but your wording is completely backwards. $A$, $B$ and $C$ are not necessarily sets of natural numbers so you definition of $j(x)$ makes no sense. You say $j(x) = 3(f(x)) - 2$ if $x \in A$. Well, first off $x$ is a natural number so probably $x \not \in A$ ever. Second of all $f(x) \in A$ so $f(x)$ is probably not a natural number so $3f(x) -2$ might not be defined. And then if, by chance $3(f(x)) -2 $ is defined, you have no reason to assume $3(f(x)) - 2 \in A \cup B \cup C$.

Pretty much you have universally gotten the range (output) completely confused with the domain (input) universally.

What you want to do is define:

$j(x) = $

if $x = 3k -2$ for some $k \in \mathbb N$ then $j(x) = f(k) \in A$.

if $x = 3k - 1$ for some $k \in \mathbb N$ then $j(x) = g(k) \in B$.

if $x = 3k$ for some $k \in \mathbb N$ then $j(x) = h(k) \in C$.

[Although It'd be more sophisticated to say $x \equiv 1 \mod 3$ etc. than $x = 3k -2$ etc.]

Answer 4

From your wording saying "decomposing $ \mathbb{N} $ into odds and evens is trivial" I'm going to assume that you know how to construct a surjection in the case of two countable subsets of $ \mathbb{N} $.

So construct $ i : \mathbb{N} \to D $ where $ D = A \cup B $. Since D is also a countable subset of $\mathbb{N}$ you can use the same method to create $ j $ from $ h $ and $ i $.

The question might be cluing you into that being the solution that they are looking for because of the way that they skip i.