Why is cardinality of set of even numbers = set of whole numbers?

I recently watched a YouTube video on Banach-Tarski theorem (or, paradox). In it, the presenter builds the proof of the theorem on the basis of a non-intuitve assertion that there as as many even numbers as there are whole numbers, which he 'proves' by showing a 1:1 mapping between the two sets.

But would that constitute a valid proof?

To me, the number-density (per unit length of the number-line) for whole numbers is clearly more than that for even numbers. And this, I'm sure, can also be trivially proved by mathematical induction.

Later, in the same video, it is shown how the interval [0,1] contains as many real numbers as there are in the real number line in its entirety. Once again, using the common-sense and intuitive concept of 'number-density', there would be clearly (infinitely) more real numbers in the entire number line than a puny little section of it.

It seems, the underlying mindset in all of this is: Just "because we cannot enumerate the reals in either set, we'll claim both sets to be equal in cardinality." In the earlier case of even and whole numbers, just "because both are infinite sets, we'll claim both sets to be equal in cardinality." And all this when modern mathematics accepts the concept of hierarchy among even infinites! (First proposed by Georg Cantor?)

Is there a good, semi-technical book on this subject that I can use to wrap my head around this theme, generally? I have only a pre-college level of knowledge of mathematics, with the rest all forgotten.

Solution 1:

This is a tough concept for most people learning about the sizes of infinite sets for the first time. Number density, as you call it, is an intuitive concept, and it makes more sense up front. But there are a couple of problems with it. It seems like you are wanting to define size of a set $A$ by the limit as $n$ goes to infinity of the number of numbers in $A$ less than $n$ divided by $n$. This, again seems natural. But what if my set were not made of numbers? What if it were a set of polygons? Or lines? A set of functions? What if it was a set of sets? There is an even bigger problem. The digits we write down when enumerating a set are really just symbols$^\ast$. The set $\{1,2,3,4,...\}$ is just a collection of symbols. If I change the symbol "1" to "2" and change "2" to "4", "3" to "6", and so on, I get the set $\{2,4,6,...\}$. I changed the way that each symbol looks. Have I really changed the size of the set? Is there a universal way to define the size of a set? There is. There is no confusion about the size of finite sets. It is also easy to see that if a function from a finite set $A$ to another finite set $B$ is one-to-one, and hits everything in $B$, then $A$ and $B$ have the same size. We simply extend the idea to infinite sets. This avoids the problem of having to have a number system pre-defined on the sets. It avoids the problem of relabeling the elements of the sets. And most importantly, it acknowledges that the size of a set is whatever we define it to be. So we choose a definition that is useful. This is a useful definition. In other words, your question "what constitutes a proof" is ill-posed. We do not prove that two sets are the same size if there is a bijective function between them, we define it that way.

As for the set $[0,1]$, it is not hard to find a bijection from $(0,1)$ to $\mathbb R$, so the definition says they are the same size. There is another theorem that says if we add a finite number of elements to an infinite set, then we do not change its cardinality. Thus, $\mathbb R$ and $[0,1]$ have the same cardinality.

As for books, I would suggest Mathematical Proofs, by Gary Chartrand.

$^\ast$Thanks to Todd Wilcox for the revised wording here.

Solution 2:

Once we determine that the notion of one-to-one correspondence defines a meaningful notion (one we refer to as "cardinality"), it then makes sense to determine the consequences. One of the consequences of this definition is that two sets can have equal size even if one is properly contained in the other. If you don't like it, then that's too bad. There are of course distinct but related concepts you can go learn about, like measure or density, but that doesn't change the fact that cardinality is a meaningful notion which captures an important intuition. If you feel a proof that one set has "as many" elements as another set is sketchy, then the issue is that the mathematician interprets "as many as" in terms of one-to-one correspondence whereas you don't.

Let's go back to the very idea of counting. The whole point is that different sets can be "the same" in a certain way even if they have very different-looking elements. The way to "forget" what the elements look like when determing if two sets have equal "size" is to speak of something that does not depend on how elements are labelled, in other words something that doesn't depend on relabelling elements, in other words something that prescribes two sets have the same size whenever there is a one-to-one correspondence between them. This is an important way to generalize the intuition of counting from finite sets to infinite sets.

If you want to think about it geometrically, imagine points in space. Whether two sets of points have "the same number" of points should not change if we move points around. Now consider points at integer coordinates $\dots,-2,-1,0,2,1,\dots$ on the number line. Then mentally zoom in by a factor of $2$ so that now the "same" set of points resides as double integer coordinates $\dots,-4,-2,0,2,4,\dots$. Zooming in shouldn't change the number of points! Now if you take all the points left of $0$, shift them to the right $1$, and then rotate them (say in an ambient 2D plane) over to the positive side of the number line, you end up with points at whole number coordinates $0,1,2,\dots$. This is how I mentally picture bijections between countable sets.

Solution 3:

When we pass from finite to infinite sets, many aspects of our intuition break down and need to be updated. We define cardinality by the existence or not of a bijection. If there is a bijection between two sets they have the same cardinality. If not, the one that can be injected into the other is smaller. When you do this, all infinite subsets of the naturals have the same cardinality, as do the rationals. The reals are strictly greater-Cantor's diagonal proof shows that. We do not say that all sets greater than the naturals have the same cardinality. Cantor's diagonal proof can be used to show that the number of subsets of any set is greater than the number of elements of the set, so the number of sets of reals is greater than the number of reals. Then the sets of sets of reals are greater yet. It is a tower that goes on unimaginably far, but for most of mathematics we don't need very many of them. For a semi-technical introduction, I like Rudy Rucker, Infinity and the Mind.