I saw that thing that if you biject set of all the natural numbers and a set of all the even numbers, they are able to pair. I don't think you can compare two infinites just like this I believe there's still a way to solve it better.

My solution is: Let $E$ be all the even numbers. Let $O$ be all the odd numbers. If you put together the even numbers and the odd numbers, this is called the natural numbers.

Now what need to do is biject between $E\cup O$ and $E$, what that happens is that $E$ is removed and what is left is $O$ and nothing. Isn't it means that they don't biject?

What I want to know is that why I am wrong.

  • $\begingroup$ The function you picked is not a bijection, that is true. However, maybe there's another function that you did not think of that is a bijection. $\endgroup$
    – Lee Mosher
    Commented Jun 10, 2014 at 16:20
  • $\begingroup$ @LeeMosher Maybe I need to say that they able to pair? Because I meant that, that is what was said in the video. $\endgroup$
    – KugBuBu
    Commented Jun 10, 2014 at 16:21
  • $\begingroup$ Your main error is attempting to biject between the two-element set $\{\{E\},\{O\}\}$ and the one-element set $\{\{E\}\}$, rather than between two infinite sets. If you didn't intend $\{\{E\},\{O\}\}$ and $\{\{E\}\}$ to be a two-element set and a one-element set, then your error is mis-use of notation leading to confusion. $\endgroup$ Commented Jun 10, 2014 at 16:22
  • $\begingroup$ @AndreasBlass I am bad at math. But you are saying that biject between sets of subsets isn't depended on the content inside those subsets? Like biject between {{A},{B}} and {{C},{D}} and they are able to match? Even that they have different number of elements in total inside those subsets? I would like you could put it as an answer. $\endgroup$
    – KugBuBu
    Commented Jun 10, 2014 at 16:36
  • $\begingroup$ Any two two-elements sets (like the ones in your latest comment, assuming $A\neq B$ and $C\neq D$) have a bijection between them, regardless of what the elements are, even if those elements are themselves sets of very different sizes (or sets of sets of different sizes, etc.). $\endgroup$ Commented Jun 10, 2014 at 16:44

2 Answers 2


You set up is: $E$ is the set of even numbers, $O$ is the set of odd numbers, and $E\cup O$ (that is, all the members of either $E$ or $O$) is just the set of all natural numbers.

The task is to find a bijection between $E\cup O$ and $E$. When we do this, we end up with $O$ and $\{\}$ (presumably the thinking is that we've taken $E$ away from each).

What this shows is that a very natural function between the two sets – identity – is not a bijection. That is, when we map $f:E\to E\cup O$ with $n\mapsto n$, the image of the function is just $E$ – we miss out 'half' of the target set.

But for the sets to be the same size, we don't require that every function between them is a bijection. We just require that some function between them is a bijection. We can still use the standard example of a bijection, where $n\mapsto n/2$, which is a bijection.

  • 1
    $\begingroup$ If the "every" vs. "some" part seems suspicious to you, note that the distinction shows up in finite sets as well. For example, the function $n \mapsto 0$ is not a bijection between $\{0, 1\}$ and $\{0, 1\}$, but those two sets are obviously the same size. $\endgroup$ Commented Jun 11, 2014 at 8:58

Here is a bijection between $\{0,1,2,3,\ldots\}$ and the subset of all even numbers in that set: \begin{align} 0 & \longleftrightarrow 0 \\ 1 & \longleftrightarrow 2 \\ 2 & \longleftrightarrow 4 \\ 3 & \longleftrightarrow 6 \\ 4 & \longleftrightarrow 8 \\ 5 & \longleftrightarrow 10 \\ & {}\quad\vdots \end{align}

If you think of any even number, I know that there will be exactly one number in the left column that it corresponds to, even if I don't know which even number you picked. And if you think of any number in the left column, I know that there will be exactly one number in the right column that it corresponds to, even if I don't know which number you picked.

One of the difference between finite and infinite sets is that there can be a bijection between an infinite set and a proper subset of itself.

  • $\begingroup$ That's what the video said, this isn't answering why I am wrong with spliting the natural numbers to even and odd numbers and then solve. $\endgroup$
    – KugBuBu
    Commented Jun 10, 2014 at 17:16
  • 1
    $\begingroup$ I don't see that there's anything wrong with partitioning the natural numbers into even and odd numbers, but it would be incorrect to say that that somehow implies that the bijection illustrated above doesn't exist. $\endgroup$ Commented Jun 10, 2014 at 17:18
  • $\begingroup$ But if you solve it in a different way you get different result. Mathematics doesn't approve. $\endgroup$
    – KugBuBu
    Commented Jun 10, 2014 at 17:25
  • $\begingroup$ You don't get a different result if the question is whether some bijection exists. You've established that a bijection between the two sets exists. The fact that there also exists a bijection between one of the sets and a proper subset of the other does not contradict that. $\endgroup$ Commented Jun 10, 2014 at 17:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .