Different sizes of infinity | Hacker News Reader

Different sizes of infinity

timetobleed.com

24 pointsmgrouchy43 comments

What really tends to upset people is this:

* Between any two irrationals there is (at least one) rational

* Between any two rationals there is (at least one) irrational

* There are more irrationals than there are rationals.

I think this becomes much more intuitive once one understands that the cardinality of any nondegenerate closed interval is the same as the cardinality of the continuum.

It becomes perhaps even more obvious when you realize that any non-empty open interval (a,b) with a<b is homeomorphic to the reals. Once that really sinks in, much of this becomes easier.

> the cardinality of any closed interval is the same as the cardinality of the continuum.

In English: There are just as many real numbers (rational and irrational combined) in between any two real numbers as there are real numbers total. (That's a somewhat simplified statement as I didn't really define 'closed interval', but it serves to give a taste of the concept.)

If nothing else, statements like those completely break your intuitive notions regarding size in this context and convince you that you can only proceed based on logic and proven theorems. Which is, of course, accurate, at least until you develop a new intuition.

Measure theory is the branch of mathematics concerned with developing new notions of size appropriate to different contexts.

http://en.wikipedia.org/wiki/Measure_(mathematics)

> Measure theory is the branch of mathematics concerned with developing new notions of size appropriate to different contexts.

While this is probably among the most interesting definitions I've ever seen, I'm not sure it is correct. Cardinality, as we've discussed it here, is usually considered to be in the domain of set theory; measure theory assigns measures in a multitude of interesting ways, but, at least in all of it with which I'm familiar, those measures come only from [0, ∞], not from some more exotic domain of values. (A lot of the measure-theory proofs that I know do rely in this being the set of values of a measure—for example, on being able to subtract most of the time, and on having only one kind of infinite measure—so just saying "let's allow different values" doesn't immediately rescue it.)

One point I never see discussed in these things is that you need to take a bit of care with digit-based representations because 0.1111... = 1.000..., 0.0111.... = 0.1000... - an argument could be made that perhaps while you know the number you're constructing via diagonalization doesn't appear in the list of numbers you created, but it may be a different representation of a number that does appear in the list.

The simplest way I know to work around that is by excluding numbers ending in infinite strings of 0s or 1s from the list. Anyone know a nicer way?

The usual way this is done is by selecting a canonical representation for the reals in the list. It's pretty much the same thing as you said, but I don't think you're putting it in the right terms.

The list you're diagonalising (in Cantor's diagonal argument that the reals are uncountable) is a list of real numbers. Each of those reals has a canonical representation, and the reals in the list are ordered according to an order defined on those representations. The argument then demonstrates a method of constructing from those representations a representation of a new real which, by definition, cannot be one of the reals in that list.

Put in those terms it feels a lot less arbitrary than simply excluding certain strings.

Problem there is that you then have to prove that the string you've constructed is in your canonical form, and it might not be.

The ambiguity in digit representations only comes from numbers ending in 1's (in base 2, or ending in 9's in base 10). If you do the argument in a different base than 2 you can avoid the problem: you can construct a number whose base 10 representation consists only of 5's and 6's and which is different from any number in the list.

A careful argument will thus often deal with ternary representations, and always choose the 'ternit' 0 or 1 that is different from the 'ternit' under consideration. It's a bit less elegant than dealing with binary representations, but it does avoid the difficulty you mention.

Steven Rudich's lecture slides on the topic are pretty great, and how I was first introduced to the topic: http://www.cs.cmu.edu/afs/cs/academic/class/15251-s04/Site/M...

Not sure if the lecture itself is available anywhere.

A much harder question is "How many infinities are there?"

http://everything2.com/user/sam512/writeups/How+many+infinit...

Why is that a harder question? It's a direct corollary of Cantor's Theorem that there is no largest cardinal number (assuming the powerset axiom, of course).

It's sort of interesting -- there's also no largest natural number, but we can talk about the size of their cardinality. You can't do that with all of the "infinities" since the collection of ordinals doesn't form an ordinal (Burali-Forti) and you can't form the set of all cardinals.

I'm not saying it's not interesting—in fact, I think it's fascinating—but all of this is implicit in Cantor's Theorem. "Harder question" to me implies there's something there that goes beyond the fundamental result that the powerset of a set X has strictly larger cardinality than X. One might think that it's just harder to understand, but I would dispute that too: if someone thinks they get Cantor's Theorem but has trouble grasping that there is no set of all sets, or largest cardinal number, it just shows that they don't really understand the theorem itself yet.

Ah, I gotcha. Yeah, the question as posed is straightforward, though there's some fun stuff (fixed points of ordinal exponentiation, inaccessibles, etc) floating around in the same neighborhood.

There's no largest integer, but the integers still form a set with an (infinite) cardinality, namely aleph-zero.

Likewise, there's no largest cardinal, but you'd think that the cardinals also formed a set with an (infinite) cardinality of its own.

Fun fact: they don't. There are too many of them.

Like I said in my response to pndmnm, in my view if someone "[would] think that the cardinals also formed a set with an (infinite) cardinality of its own" then they haven't really grasped the theorem yet. It's built into it that if we're always allowed to form the powerset of a set then regardless of how large a cardinal you can find, you can always take its powerset and obtain a larger cardinal.

I never liked Cantor's argument here. I'm sure I'm missing something, but the 'grid' that you set up has infinity rows but 2^infinity columns. The diagonal that you make just cuts off the top-right corner of the grid, and that missing element is one of the remaining rows.

The diagonalization argument just seems like handwaving.

There aren't 2^oo columns - the number of columns is the same as the number of rows. And the argument can be made a lot less handwavey, it can be made very precise in set theoretic terms.

Do you want references?

That would rock, yes.

(But why aren't there 2^oo columns? In order to fill up all possible ...<snap>

I think I got it...

You're not trying to use every possible oo-length binary string, you're just mapping each natural number to an arbitrary (unique) oo-length binary string, so the grid in a square in the end.

Yes.

When working more formally it's actually easier just to show that for every set A the set 2^A is strictly bigger, where 2^A is a common representation for the power set of A, the collection of all subsets.

As an aside, if A and B are sets, the set A^B is

    {f : f:B->A},

the set of all functions from B to A. You can quickly show that if A and B are finite, and |A|=n and |B|=m then |A^B|=n^m, thus matching our intuition. A function in 2^A says for each element of A, choose whether it's in or out. That gives a subset of A, so it makes sense to call the set of subsets 2^A, the power set.

In what follows you need to "read like math." This is not a novel - work through it, don't simply try to read. Draw pictures, use simple examples, try to fund counter-examples. Work on understanding.

So, given a set A, how do we show that |A| < |2^A|? Simple, we take any function from A to 2^A and show that some element of 2^A doesn't get hit. This shows that for every function from A->2^A it's not a matching. Hence no matching exists between A and 2^A, so 2^A is not the same size.

I'll leave it to the interested reader to show that 2^A is never smaller than A.

So how do we show that any function from A to 2^A leaves some element of 2^A unhit?

Let g:A->2^A be any function from A to 2^A. We construct h in 2^A such that h is not in the image of g.

h needs to be a function from A->{0,1}, so for every a in A, we need to say whether h(a)=0 or h(a)=1.

Remembering that g(a) is in 2^A, and hence is a function A->{0,1} we define h:A->{0,1} as:

    h(a) = 0 if (g(a))(a) = 1
    h(a) = 1 if (g(a))(a) = 0

Chase the definitions and you'll find that for every a in A, h != g(a).

This is only tangentially relative, but I find the argument that real numbers may not ever exist in nature to be fascinating. The argument is that all of nature breaks down at the size of plank's constant so every real measurement has a finite resolution.

If you like this you may also like "All about Infinity" (former title, "Infinity Is Not a Number - It's a Free Man")

http://nrich.maths.org/2756

by Katherine Körner.

I thought infinity is infinity; no varying degrees.

How is this different from saying counting to infinity with integers is smaller than counting with floats?

One simply cannot "count" with "real" numbers. But "floats" is probably countable since it's represented with limited digits. However, considering the inherent error associated with it, I wouldn't say it's countable. Also, if you are trying to find an infinite large number, for any arbitrarily large real number, you can find a larger integer and vice versa. But the point here is that there are more real numbers than integers.

This is not "infty" as per computer representations of numbers. This is "infinity" as in "how many counting numbers are there" and "how many reals are there".

We are not dealing with floats. Trivial, for any size being used, the number of floats that can be represented is finite.

So what this is saying is this:

Consider the collection of counting numbers: 1, 2, 3, ... and so on. Call that set N.

There is a set P which has the property that every time you try to match up items of N with items of P, there are items of P left over.

If you have some cups and saucers, and every time you laid them out you had some saucers left over, you'd say you had more saucers. Yes? Well every time we try to match up things from N with things from P we can things from P left over, so we should say we have more of them, right?

But there are infinitely many things in N, so P must be a bigger infinity.

I've always liked the explanation of different sizes of infinity that compares the infinite set of whole numbers to the larger infinite set of fractions.

Those sets have the same cardinality...

The set of fractions isn't larger than the set of whole numbers, so how good an explanation could it be?

There are the same number of whole numbers as there are fractions/rational numbers (my favorite quick proof -- every whole number is a rational number (itself over 1). Map each n/m in lowest terms to 2^n*3^m for an injection of rationals into the integers (by the fundamental theorem of arithmetic)).

That's a really nice way to show that, thanks. I may borrow it for future use.

> There are the same number of whole numbers as there are fractions/rational numbers (my favorite quick proof -- every whole number is a rational number (itself over 1). Map each n/m in lowest terms to 2^n*3^m for an injection of rationals into the integers (by the fundamental theorem of arithmetic)).

Notice that this shows only that there are no more whole numbers than rational numbers, and no more rational numbers than whole numbers. To conclude that there is the same number of each (more generally, that cardinal numbers are totally ordered (EDIT: as ionfish (http://news.ycombinator.com/item?id=4251492) points out, I should have said that the inclusion relation on cardinals is antisymmetric)) is actually a bit delicate; it's called the Schröder–Bernstein theorem (although Wikipedia attaches more names, in a different order: https://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80...).

True, though this "proof" assumes a large amount of additional mathematical machinery in addition to SB (I learned it as Cantor-Schröder–Bernstein originally... I wonder where the inconsistency in the naming comes from). It's not so much a formal set-theoretic proof (of course it could be made so) as a quick demonstration that has a stronger pull on mathematical intuition than the standard proof (and is demonstrating an otherwise provable thing).

The history of the proof is a little messy; the Wikipedia page has a decent summary.

http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theo...

Yes, it does rely implicitly on Cantor–Schröder–Bernstein. That might be a downside, but I think when working informally (that is to say, when not teaching a set theory course) one can simply assert that if there exist injective functions from sets A and B into one another then they are equinumerous.

That being said, although important in the theory of the order of the cardinal numbers, Cantor–Schröder–Bernstein doesn't show that the cardinals are totally ordered. That statement is actually equivalent to the Axiom of Choice, whereas as far as I'm aware Cantor–Schröder–Bernstein holds in ZF.

That's absolutely correct -- trichotomy for arbitrary cardinals (any two cardinals are cardinal-size-comparable) requires AC, but SB doesn't require AC. Trichotomy for the cardinal numbers of well-ordered sets (e.g. ordinals) doesn't require AC.

It's a little irrelevant to this thread... but as long as I'm quoting non-proofs that require lots of extra machinery, I'll give my favorite appeal-to-intuition equivalent of choice: the product of non-empty sets is non-empty (any point in the product of a collection of non-empty sets is a choice function on those sets).

AC is equivalent to a lot of things. There's a collection of them on the Wikipedia page.

http://en.wikipedia.org/wiki/Axiom_of_choice#Equivalents

Something I find pretty interesting is that some of these equivalences break down in weak systems.

http://www.math.uchicago.edu/~antonio/RM11/RM%20talks/mummer...

Yup, I did a few projects on equivalents of AC back in the day. That's just my favorite "appeal to intuition" one (my favorite "appeal to intuition" against AC is: the identity function is the sum of two periodic functions (though this is a consequence and not equivalent)).

Equivalence breakdown in alternate systems is a wonderful topic. I've been trying for a couple years now to figure out how to get back into set theory now that I'm out of academia. Maybe later this summer...

> That being said, although important in the theory of the order of the cardinal numbers, Cantor–Schröder–Bernstein doesn't show that the cardinals are totally ordered.

Good point, thanks; I've corrected my post accordingly.

My favorite proof uses the Wilf-Calkin formula, which provides an explicit enumeration of the rationals without repetition. The Wilf-Calkin tree is related, and provides the basic principles.

http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree

In the tree every rational appears exactly once in lowest terms, and is easily generated recursively.

Careful — "fraction" often means "rational number", and the rationals are countably infinite.

Reply on news.ycombinator.com