Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
16  
One set having "as many" elements as another should not depend on how the elements are labelled. For instance, $\rm\{one,two,three,\cdots\}$ should be equinumerous to $\{1,2,3,\cdots\}$. Thus, the notion of one-to-one correspondence. The concept of density is distinct from the concept of cardinality. – arctic tern Mar 29 at 3:59
4  
Google "Hilbert's Grand Hotel." that should get you started. – Doug M Mar 29 at 4:00
11  
We define cardinality in terms of maps. That is what we mean. – Zachary Selk Mar 29 at 4:02
4  
There are many different ways to talk about "how big a set is." For example, the set of real numbers from $[0,1]$ compared to the set of real numbers from $[0,2]$. In terms of cardinality, they are the same. In terms of Lebesgue measure, the second is of measure $2$ while the first was of measure $1$. In similar fashion, the cardinality of the sets in question might seem unintuitive (interestingly, the set of all rational numbers is countable, yet dense on the real number line), but moving away from the intuitive idea of "how many" from geometry, applying the definitions is needed. – JMoravitz Mar 29 at 4:06
6  
@nxs Abstract math is founded on axioms and definitions, which on the one hand seem arbitrary and artificial, but on the other hand are chosen because they are useful in describing the real world. – Alex S Mar 29 at 4:18
up vote 21 down vote accepted

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.

share|cite|improve this answer
3  
Banach-Tarski is a nice exercise demonstrating a strange result, but it should never be mistaken for something we could actually do to a ball of chocolate, as it ignores the fact that matter is made up of atoms and molecules. Putting that aside, never fear! If some chocolate particles accidentally got relabeled wood particles, just find a bijection with another set of chocolate particles, and use this to switch out the bad ones. – Alex S Mar 29 at 4:57
3  
"A number is just a symbol." Perhaps a number can just be a symbol, but normally in mathematics it is more than just a symbol. – ThomasW Mar 29 at 6:51
3  
A cautious +1 for "numbers are just symbols". A possible refinement of that statement might be "the groups of digits that we write down to represent numbers are just symbols". The numbers themselves have distinct properties regardless of representation (e.g., the object represented by "A" in base 16 has the same properties as it has when represented by "10" in base 10). With respect to cardinality, there is no difference between the objects we traditionally denote by "1" and "2", but in other areas, those two objects of course have different properties. – Todd Wilcox Mar 29 at 12:37
1  
@ToddWilcox You're right. I was perhaps a bit too flippant with my original statement (see my recent edit). Regardless, we could decide to change the properties of all the numbers in a set (move to a different ordering, topology, or algebraic structure) and not change the cardinality. – Alex S Mar 29 at 13:46
3  
There is an intuition that if one set is a proper subset of another (that is, all members of A are members of B but there are members of B that are not in A), then the first set is "smaller" than the second. By that definition, though, there is no sense of which of two disjoint sets is "larger". – Malvolio Mar 29 at 19:00

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.

share|cite|improve this answer
    
Thanks! Will check out the book also. – nxs Mar 29 at 5:12

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.

share|cite|improve this answer
    
Thanks, first off! While I understand now that cardinality is a different notion than density, in the context of Banach-Tarski's sphere duplication, I think the labeling or the 'identity' of the set members does matter. For example, if you're duplication a sphere of chocolate using their process, you would want all infinitesimally small particles of chocolate to be in the resulting spheres and not particles of some other material like plastic or sand. (Ignore here the finite and limiting sizes of atoms). But if my intention is to duplicate a sphere of glass that I use as a paper-weight... – nxs Mar 29 at 4:29
    
... then, obviously I would care less if the identify of the constituent particles in the duplicated object is plastic or glass or wood. – nxs Mar 29 at 4:30
1  
@nxs Keep in mind that Banach-Tarski's theorem uses a lot more than just cardinality arguments (has almost nothing to do with it). It uses the concept of measure (which is another, much more complex way of assigning a "size" to a set). You should also avoid using ill defined terms (infinitesimally small particles of chocolate, what does that even mean?). – YoTengoUnLCD Mar 29 at 4:42
1  
@nxs: Chocolate is not made of points, but chocolate bits, and if you like fundamental particles.. Pure points and perfect lines exist only in mathematics and not in the real world. So there are as many points on the real line as there are between 0 and 1 on that same line, but that has no implication whatsoever for the real world. – user21820 Mar 29 at 13:28
1  
@nxs To go with your chocolate particle analogy, for every particle in either of the new spheres we can pinpoint the place on the original sphere that this particle came from. So if that point was chocolate before the transformation, since the only thing we have done is move it - it remains chocolate. (This assumes the infinite divisibility of chocolate as well as the axiom of choice) – Taemyr Mar 29 at 16:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.