3

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!.

Meera Unni
  • 427
  • 1
  • 4
  • 16
  • Do you know how to show $\mathbb{N}$ has the same cardinality as $\mathbb{N} \times \mathbb{N}$? Do you have cardinality inequalities? – N8tron May 23 '18 at 12:58
  • No, sorry I don't. I'm so far familiar with the basics of set theory. – Meera Unni May 23 '18 at 12:59

2 Answers2

2

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.

Mike Earnest
  • 75,930
0

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$.

Anguepa
  • 3,129
  • 2
    I think the crux of the problem is that you are not given $X$ and $Y$ are disjoint – Mike Earnest May 23 '18 at 13:03
  • If they are not disjoint you can work with three sets, $X\cap Y, X\setminus Y, Y\setminus X$. They are pairwise disjoint. Either the first is infinite and the last two finite, the first is finite and the last two infinite, or they are all infinite. Using the above idea you should be able to handle each of the cases. – Ross Millikan May 23 '18 at 13:10
  • @MikeEarnest I added to the answer – Anguepa May 23 '18 at 13:12
  • Since the poster doesn't seem familiar with much set theory, it may be worth adding Cantor's definition of an infinite set: A set $Y$ is infinite if it is bijective to a proper subset. – N8tron May 23 '18 at 13:14