To Infinity, and Beyond:

A recent conversation reminded me that many of my lawyer friends don't know these really cool mathematical items, but enjoy them when they learn about them. I thought, then, that I'd quickly go through them; I'm no math maven these days, but I think I can get them right, substantively even if not with the level of formal precision that hard-core math people might prefer.

Here's the first question: Are there more positive integers (1, 2, 3, 4, 5, ...) or more integer squares (1, 4, 9, 16, 25, ...)? The answer: The two sets are of the same size.

Counterintuitive, some may say: After all, positive integers include all the squares, plus all the nonsquares, as well. In any interval from 1 to n, when n>1, there are more integers than squares; what's more, the ratio increases as n grows. In 1 to a million, for instance, there are a thousand times more integers than squares.

Yet this is quite true, under the standard mathematical definition of equal size. Let's define two sets as equal if there's a one-to-one mapping between them, so that each number in one set corresponds to precisely one number in the other. The mapping here is simple: Map any integer n to n squared, which is to say 1 to 1, 2 to 4, 3 to 9, 4 to 16, 5 to 25, and so on. Every number in the positive integers maps to precisely one square, and vice versa. The two sets are equal.

In fact, as one can easily prove through a similar approach, any two infinite subsets of the positive integers are equal. In fact, this may lead you to replace your old intuition (lots more integers than squares) with a new one (hey, both sets are infinite, and infinity = infinity). But not so fast! Two questions for you: Are there more positive integers or positive rational numbers (numbers that are the ratio of two integers, such as 2/7 or 549/100)? And are there more positive integers or real numbers? More on that soon.

Armen (mail) (www):
Isn't this Cantor's theorem? The whole Aleph Null, etc.
11.21.2007 2:48pm
D is for Dasha:
There are as many positive integers as positive rational numbers, but there are many more real numbers than positive integers. I suppose proofs can be made upon request.
11.21.2007 2:51pm
Don't you just have to do the whole diagonal slash thing? I wish I remembered more of this stuff.
11.21.2007 2:58pm
dps (mail):

Here's the first question: Are there more positive integers (1, 2, 3, 4, 5, ...) or more integer squares (1, 4, 9, 16, 25, ...)? The answer: The two sets are of the same size.

I think this is misleading in that there are only "more" elements when we interpret "more" very narrowly to mean "higher cardinality." Certainly any 2 infinite integer sets have the same cardinality, and certainly "cardinality" corresponds to our intuitive sense of "more" when we're restricted to finite sets, but that's just begging the question.

There are other reasonable ways of defining "more," like measure or Baire category.
11.21.2007 3:05pm
When I was first introduced to Cantor, it seemed almost nutty. But, as they say, you don't learn math, you get used to it.

I seem to recall being told, to give an idea of different levels of infinity, if you pick a random point on a number line, it is (literally) infinitely more likely to be a transcendental number than a rational number. Hard to take at first when it seems rational numbers are numerous enough to fill up all the space on the line.
11.21.2007 3:10pm
Indeed this is Cantor's idea. The important thing to take from here actually is not the results, the idea of size comparison using mappings.

Cantor was trying to understand the problem "what is the size of a set of objects?". The main innovation is Cantor's definition of "having the same size" quoted by Eugene, as well as a similar one for "the set A has at least as many elements as the set B" [when you have a one-to-one mapping between all the elements of A and a subset of B, that is when A has the same number of elements as a subset of B]. This is clearly the right definition, and it completely captures our intuition for the size of finite sets. But it turns out that some properties of size for finite sets are lost when you go to infinite sets (it is possible for a set and its proper subset to have the same size).

PS: for this notion of "A has more elements than B" to make sense, it should be true that if A is at least as large as B, and B is at least as large as A, then they have the same number of elements. Cantor couldn't find a proof, but one was found later.

PPS: Another property of finite sets is that for any A,B either A has at least as many elements as B or the reverse holds. Whether the same holds for infinite sets or not is a touchy point (the subtlety is: assume that there is no embedding of A into B -- why should this say anything about maps from B to A ?). [for the cognoscenti: "any two sets are comparable" is a form of the "Axiom of Choice"]
11.21.2007 3:22pm
dps: I don't think there's any reasonable definition of "having more elements" other than Cantor's. Given additional structure, we have other notions of being relatively "big" and "small" in an ambient space (for example: full measure/measure zero, of first/second category, various measures of dimension), but these are decidedly not notions of number (cardinality).

SteveDK: There's no good notion of a "random point on the number line". There is a good notion of a "random point in the interval [a,b]", and indeed for that notion the probability of picking a rational (or an algebraic) number is zero. Continuing the theme of non-intuitive aspects of mathematical definitions note that "the event has probability zero" and "the event can't occur" don't mean the same thing in this context.
11.21.2007 3:33pm
Fred Red:
I think you should be careful to use the term "cardinality" instead of "size". The set of squares of natural numbers is a strict subset of the set of natural numbers, so it could reasonably be said to be "smaller" if we interpret that to imply an inclusion-based ordering. With this kind of discussion it is important to use the correct jargon or it is easy to become confused about what we are really saying.
11.21.2007 3:37pm
Spartacus (www):
Cantor's proof that the reals are more numerous than the integers (i.e., are uncountable) isone of the coolest simple (as in easy to understand) proofs in math, up there with the proof that the square root of two is irrational (by Pythagoras, I believe).
11.21.2007 3:40pm
John Armstrong (mail) (www):
dps, you make a good point, or at least you try to use fancier words.

Unfortunately, sets don't come with the topological structure to invoke such concepts as Baire category, and they don't come with any measure except for counting measure, which just gives cardinality back again.

The really cool word to use here is "decategorification". We aren't just interested in what sets there are, but how we can map elements from one to another by functions. Sets and functions between them together form something we call a "category".

In this category, sets connected by invertible functions are special. We call them "isomorphic", and consider them to be "the same, for all practical purposes". Passing from sets to cardinal numbers is a process of "decategorification", where we just remember whether two sets are the same or different, but forget how they are the same (an explicit function).

What becomes cool about this is that we can define things like the product of sets or the disjoint union of sets in terms of the category above. Then when we decategorify, these operations of sets become familiar operations on cardinal numbers: multiplication and addition! In fact, all of arithmetic can be derived in this manner.
11.21.2007 3:45pm
Annonymous Coward (mail):
Sadly time was any bright child had picked up One, Two, Three, Infinity (Gamow)from the spinning paperback book rack at the drugstore.

These days quality books are very nearly a free good - 10 cents apiece from used bookstores and library sales racks but distribution to the general population suffers by comparison to the days of intellectual ferment following WWII and Korea and the original GI Bill.

The modern paperback rack is to quality reading as top 40 radio was to quality music.

Hence everything old is new again.

For a legal aspect to innumerancy the Court (years ago) in striking down Oklahoma's rational IMHO law allowing young women to drink at 18 and the young men they dated to drink at 21 - rational since the women weren't driving - the Court confused statistically significant and otherwise significant in its analysis. Like confusion over probability such happens all the time.
11.21.2007 4:11pm
dps (mail):
The problem is that in real life we only interact with finite sets, and our sense of what "size" means doesn't generalize well.

For example, if I were to hold up a finite bag of marbles with the same number of blue marbles as green marbles, then if you pick a marble uniformly, it's just as likely to be green as it is to be blue. Anything else would strain the definition of "equal size."

But this doesn't work for our intuitive sense of an infinite bag of marbles! (E.g., it seems natural to take the Lebesgue Measure and choose a real uniformly from [0, 1]. It's almost always not in the Cantor Set, but those 2 partitions have the same cardinality.)

Eugene's post is misleading in that it suggests that our intuitive sense of "more" - with all its implications for probability, etc. - carries over naturally to the infinite case under this funky mapping definition, when in fact it doesn't.
11.21.2007 4:12pm
Ex parte McCardle:
I get the feeling that, as a Thanksgiving gift to his loyal blog readers, EV is about to prove the Continuum Hypothesis for us. Or is that disprove it?
11.21.2007 4:16pm
CrazyTrain (mail):
Professor: Isn't the term "infinity" no longer in vogue amongst mathematicians? Isn't more conventional, and precise for that matter, to say that both sets have no limit?
11.21.2007 4:18pm
Sk (mail):
"Yet this is quite true, under the standard mathematical definition of equal size. Let's define two sets as equal if there's a one-to-one mapping between them..."

Interesting that math is dependent upon first principles just like morality or philosophy. Because if you DON'T start with that standard mathematical definition, you don't come up with the same answer. And there is no inherent reason to start with that standard mathematical definition (other than because alot of mathematicians do so).

So, if we start with a non-standard mathematical definition

Say, "for any number n, count the number of integers and integer squares between 0 and n..." "What happens if n = infinity?" and the two sets will not be equal.

Say, "any two sets are equal if there is a one-to-one map betweeen them..." and the two sets will be equal.

It's like Socrates:

All men are mortal
Socrates is a man
Ergo, Socrates is mortal

Is only true if the first statement is assumed.

11.21.2007 4:36pm
Mary Katherine Day-Petrano (mail):
I think you need to ask Rainman.
11.21.2007 4:43pm
Mike S.:
As perhaps Ex parte McCardle knows, the usual axioms of set theory cannot resolve the continuum hypothesis (that is, that you can add either the continuum hypothesis or its negation to the set of axioms without a contradiction)

But does this post mean we can look forward to posts on law from mathematical blogs?
11.21.2007 5:08pm
Just Stopping By:
Reminds me of one of my favorite jokes:

Which is more independent, Brazil or the continuum hypothesis?
11.21.2007 5:28pm
Bender (mail):
Mathematical advance is often based on developing the right definitions. Examples are Cantor's definition of cardinality in terms of one-one mappings and Cauchy's definition of limits. In his book, Calculus on Manifolds, Michael Spivak states this explicitly after using careful definitions to develop a rigorous proof of a whole set of classical analysis theorems, the Divergence Theorem, Green's Theorem, Stokes' Theorem, etc. Much of the beauty of mathematics lies in the creativity associated with great mathematical thinking.
11.21.2007 5:56pm
Cornellian (mail):
I want to see EV prove Goldberg's Conjecture. Now that would qualify him for a Supreme Court nomination, IMO.
11.21.2007 6:00pm
New Guinea natives are reputed to count "one, two, many...." This surely gives them a head start on Cantor.
11.21.2007 6:29pm
rkt (mail):
It's been many years, but I still treasure my copy of Gamow's "One, Two, Three, ... Infinity." It is still a wonderful gift for the inquiring mind, perhaps available on abebooks (?).
11.21.2007 6:37pm
John Armstrong (mail) (www):
CrazyTrain: it depends on the context. We say "infinity" all the time, with various precise meanings. Limits come in when you're talking about a sequence of numbers, which might grow larger and larger and larger as you walk down the sequence. In that case there's no limit, because the sequence diverges... to infinity!
11.21.2007 6:57pm
Zathras (mail):
In fact, one definition of an infinite set is a set which has the same cardinality as one of its proper subsets (a subset which is not equal to the entire set.
11.21.2007 8:49pm
Evelyn M. Blaine (mail):
Zathras wrote:
In fact, one definition of an infinite set is a set which has the same cardinality as one of its proper subsets (a subset which is not equal to the entire set.
The technical term for this is "Dedekind infinity". Normally infinity is defined as follows: a set is infinite iff it is not empty and not (there exists a natural number n such that the set is equinumerous with {1,2,3 ... n}). The two definitions are equivalent given AC, but not otherwise. (There's some fairly nifty math about the relation of the cardinalities of infinite and Dedekind-infinite sets without AC; George Boolos has an interesting article somewhere on the role one of the relevant theorems plays in Principia Mathematica.)
11.22.2007 2:45pm