Bijection of sets

Question

Let $N$ be the set of natural numbers. Suppose there is a bijection between $N$ and set $X$. Suppose there is also a bijection between $N$ and set $Y$ Then is the inference that there is a bijection between $N$ and $X\cup$Y true ?.

The answer is yes, but I cant seem to understand why. I reasoned that for an element in $X$ that maps to $X$ and to $Y$, with $X\cup$Y the relation would be many-one. However it would be onto as both $X$ and $Y$ are onto so $X\cup$Y ought to be onto as well. Any help would be great!.

Answer 1

The intuition is this: if there is a bijection between $N$ and $X$, then the elements of $X$ can be written in an infinite list, where each element of $X$ appears exactly once: $$ x_1,x_2,x_3,\dots $$ The same is true for $Y$: $$ y_1,y_2,y_3,\dots $$ To prove there is a bijection between $N$ and $X\cup Y$, we need to find a list which contains each element of $X\cup Y$ exactly once. A tempting choice is to interleave the previous two lists. $$ x_1,y_1,x_2,y_2,x_3,y_3\dots $$ In a formula, the proposed bijection $f:N\to X\cup Y$ is $f(n)=x_{n/2}$ when $n$ is even, and $f(n)=y_{(n+1)/2}$. when $n$ is odd.

This function is definitely surjective, but it may not be injective. The problem is that there may be elements which are in both $X$ and $Y$, so they would appear twice in the above list, once in the $X$ half, once in the $Y$ half. One solution is to simply delete those elements from the above list, and then smush it back together. For example, if all of the odd elements $x_{2n+1}$ of $X$ were also present in $X$, the previous function could be fixed as follows: $$ \require{cancel}\cancel{x_1},y_1,x_2,y_2,\cancel{x_3},y_3,x_4,y_4,\cancel{x_5},y_5,\dots\implies y_1,x_2,y_2,y_3,x_4,y_4,y_5,\dots $$ Now we have an infinite list which completely enumerates the elements of $X\cup Y$ without repeats, so we are done.

Answer 2

Let $N_0$ be the set of even numbers and $N_1=N\setminus N_0$ the odd numbers. Let $f:N\rightarrow X$ and $g: N\rightarrow Y$ be bijections. Now try to built bijections $f_0: N_0\rightarrow N$ and $f_1 : N_1\rightarrow N$. Finally consider the function $h:N\rightarrow X\cup Y$ defined as follows. For every $x\in N_0$ it holds that $h(x)=f(f_0(x))$ and for every $x\in N_1$ it holds that $h(x)=g(f_1(x))$. Then $h$ is a bijection (given that $X$ and $Y$ are disjoint).

If $X$ and $Y$ are not disjoint then consider $Y'=Y\setminus X$. If $Y'$ is infinite then try to show that $Y'$ is still in bijection with $N$ and then do as above with $Y'$ in place of $Y$. Otherwise there is some $n$ such that $|Y|=n$. Built $h$ so that $h(\{0,\ldots, n-1\})=Y'$ and, for any $x\geq n$, $h(x)=f(f_2(x))$, where $f$ is the bijection $N\rightarrow X$ and $f_2$ is the bijeciton $\{n,n+1,\ldots\}\rightarrow N$ given by $x\mapsto x-n$.