# Draft/​wiki: Infinities and measuring infinite sets: A quick reference

EDIT: This is now on the Wiki as “Quick refer­ence guide to the in­finite”. Do what you want with it.

It seems when­ever any­thing in­volv­ing in­fini­ties or mea­sur­ing in­finite sets comes up it gen­er­ates a lot of con­fu­sion. So I thought I would write a quick guide to both to

1. Ad­dress com­mon confusions

2. Act as a use­ful refer­ence (per­haps this should be a wiki ar­ti­cle? This would benefit from oth­ers be­ing able to edit it; there’s no “com­mu­nity wiki mode” on LW, huh?)

3. Re­mind peo­ple that some­times in­vent­ing a new sort of an­swer is nec­es­sary!

I am try­ing to keep this con­cise, in some cases sub­sti­tut­ing Wikipe­dia links for ex­pla­na­tion, but I do want what I have writ­ten to be un­der­stand­able enough and in­for­ma­tive enough to an­swer the com­monly oc­cur­ring ques­tions. Please let me know if you can de­tect a par­tic­u­lar prob­lem. I wrote this very quickly and ex­pect it still needs quite a bit more work to be un­der­stand­able to some­one with very lit­tle math back­ground.

I re­al­ize many peo­ple here are fini­tists of one stripe or an­other but this comes up of­ten enough that this seems use­ful any­way. Apolo­gies to any con­struc­tivists, but I am go­ing to as­sume clas­si­cal logic, be­cause it’s all I know, though I am point­ing out ex­plic­itly any uses of choice. (For what this means and why any­one cares about this, see this com­ment.) Also as I in­tend this as a refer­ence (is there *any* way we can make this ed­itable?) some of this may be things that I do not ac­tu­ally know but merely have read.

Note that these are two sep­a­rate top­ics, though they have a bit of over­lap.

Pri­mar­ily, though, my main in­ten­tion is to put an end to the fol­low­ing, which I have seen here far too of­ten:

Myth #0: All in­fini­ties are in­finite car­di­nals, and car­di­nal­ity is the main method used to mea­sure size of sets.

The fact is that “in­finite” is a gen­eral term mean­ing “larger (in some sense) than any nat­u­ral num­ber”; differ­ent sys­tems of in­finite num­bers get used de­pend­ing on what is ap­pro­pri­ate in con­text. Fur­ther­more, there are many other meth­ods of mea­sur­ing sizes of sets, which sac­ri­fice uni­ver­sal­ity for higher re­s­olu­tion; car­di­nal­ity is a very coarse-grained mea­sure.

## Topic #1: Sys­tems of in­fini­ties (for do­ing ar­ith­metic with)

#### Car­di­nal numbers

First, a re­view of what they rep­re­sent and how they work at the ba­sic level, be­fore we get to their ar­ith­metic.

Car­di­nal num­bers are used for mea­sur­ing sizes of sets when we don’t know, or don’t care, about the set’s con­text or com­po­si­tion. First, the stan­dard ex­pla­na­tion of what we mean by this: Say we have two farm­ers, who each have a large num­ber of sheep, more than they can count. How can they de­ter­mine who has more? They pair off the sheep of the one against the sheep of the other; whichever has sheep left over, has more.

So given two sets X and Y, we will say X has smaller car­di­nal­ity than Y (de­noted |X|≤|Y|, or some­times #X≤#Y) if there is a way to as­sign to each el­e­ment x of X, a cor­re­spond­ing el­e­ment f(x) of Y, such that no two dis­tinct x1 and x2 from X cor­re­spond to the same el­e­ment of Y. If, fur­ther­more, this cor­re­spon­dence cov­ers all of Y—if for each y in Y there is some x in X that had y as­signed to it—then we say that X and Y have the same car­di­nal­ity, |X|=|Y| or #X=#Y.

Note that by this defi­ni­tion, the set N of nat­u­ral num­bers, and the set 2N of even in­te­gers, have the same size, since we can match up 1 with 2, 2 with 4, 3 with 6, etc. This even though it seems 2N should be only “half as large” as N! This is why I em­pha­size: Car­di­nal­ity is only one way of mea­sur­ing sizes of sets, one that is not fine enough to dis­t­in­guish be­tween 2N and N. Other meth­ods of mea­sur­ing their size will have 2N only half as large as N.

It is true, but not ob­vi­ous, that if |X|≤|Y| and |Y|≤|X|, then |X|=|Y|; this is the Schroeder-Bern­stein the­o­rem. Hence we can sen­si­bly talk about “the car­di­nal­ity” of a set X as be­ing some ab­stract prop­erty of it—if |X|≤|Y| then X has smaller car­di­nal­ity and Y has larger car­di­nal­ity, and so on. We can make this more con­crete, and define an ac­tual car­di­nal­ity ob­ject |X| (or #X), us­ing ei­ther the ax­iom of choice or Scott’s trick (if you ad­mit the ax­iom of foun­da­tion) or even proper classes if we ad­mit those, but this will not be rele­vant here. We will use |X|<|Y| to mean “|X|≤|Y| but |X|≠Y”.

Note that it is also not ob­vi­ous that given any two sets X and Y, we must have ei­ther |X|≤|Y| or |Y|≤|X|; in­deed, this state­ment is true if and only if we ad­mit the ax­iom of choice. So take note:

Myth #1: In­fini­ties must come in a lin­ear or­der­ing.

Fact: If the ax­iom of choice is false, then there are nec­es­sar­ily in­finite car­di­nals which are not the same size, and yet for which nei­ther can be said to be larger! If we do ad­mit the ax­iom of choice, then the car­di­nal num­bers must be not only lin­early-or­dered but in fact be well-or­dered.

The car­di­nal­ity of the set of nat­u­ral num­bers, |N|, is also de­noted ℵ0. If we ad­mit the ax­iom of [de­pen­dent] choice, this is the small­est in­finite car­di­nal. Here by “in­finite” car­di­nal I mean one that is larger than the size of any finite set (0, 1, 2, etc.).

##### Quick aside on par­tial orderings

Many of you are prob­a­bly won­der­ing how to think about some­thing like “nei­ther larger nor smaller, but not the same”. For­mally, we say that, with­out choice, the or­der­ing on the car­di­nal num­bers is a par­tial or­der. Be­cause these are so com­mon I’ll go ahead and define this here—gen­er­ally, a par­tial or­der on a set S is a re­la­tion (usu­ally de­noted “≤”) on S such that:

1. For ev­ery x in S, x≤x (re­flex­ivity)

2. For any x and y in S, if x≤y and y≤x, then x=y (an­ti­sym­me­try)

3. For any x,y,z in S, if x≤y and y≤z, then x≤z (tran­si­tivity)

If we ad­di­tion­ally re­quired that for any x and y in S, we have ei­ther x≤y or y≤x, we’d have a to­tal or­der (also called a lin­ear or­der).

OK, but still, what does “nei­ther larger nor smaller, yet not the same” mean in gen­eral? How can you vi­su­al­ize it? Well, the canon­i­cal ex­am­ple of a par­tial or­der would be, if we have any set S, we can par­tially or­der its sub­sets by defin­ing A≤B to mean A⊆B. So if S={1,2,3,4}, then {1,2} is larger than {1} and {2}, and smaller than {1,2,4}, but in­com­pa­rable to {3} or {2,3} or {2,3,4}.

Another ex­am­ple would be, if we have or­dered n-tu­ples of real num­bers, we could define (x1,...,xn)≤(y1,...,yn) if xi≤yi for each i. You might imag­ine these as, say, stats of char­ac­ters in a game; then x≤y would mean that char­ac­ter y is bet­ter than char­ac­ter x in ev­ery way. To say that x and y are in­com­pa­rable would mean that—though in prac­tice one might be bet­ter on the whole—nei­ther is ob­vi­ously bet­ter. More gen­er­ally, in any game, you could define a par­tial or­der on strate­gies by x≤y if y dom­i­nates x.

Note that par­tial or­ders are suffi­ciently com­mon that for many math peo­ple the word “or­der” means “par­tial or­der” by de­fault.

#### Car­di­nal arithmetic

Given sets X and Y, |X|+|Y| will de­note the car­di­nal­ity of the “dis­joint union” of X and Y, which is the union of X and Y, but with each el­e­ment tagged with which of the two it came from, so that we don’t lose any­thing to over­lap (i.e., if an el­e­ment is in both X and Y, it will oc­cur twice, once with an “X” tag and once with a “Y” tag.) |X||Y| will de­note the car­di­nal­ity of the set X×Y, the Carte­sian product of X and Y, which is the set of all or­dered pairs (x,y) with x in X and y in Y. How­ever, if we ad­mit the ax­iom of choice, this ar­ith­metic is not very in­ter­est­ing for in­finite sets! It turns out that given car­di­nal num­bers μ and λ, if ei­ther is in­finite and nei­ther is zero, then μ+λ=μλ=max(μ,λ). Hence, if you need a sys­tem of in­fini­ties in which x+y is go­ing to be strictly big­ger than x and y, car­di­nal num­bers are the wrong choice. (The ar­ith­metic of car­di­nals gets more in­ter­est­ing once you al­low for adding or mul­ti­ply­ing in­finitely many at once.)

There is also ex­po­nen­ti­a­tion of car­di­nals; |X||Y| de­notes the car­di­nal­ity of the set XY of all func­tions from Y to X, i.e., the num­ber of ways of pick­ing one el­e­ment of X for each el­e­ment of Y. Given any set X, 2|X| is the car­di­nal­ity of its power set ℘(X), the set of all its sub­sets. Can­tor’s di­ag­o­nal ar­gu­ment shows that for any set X, 2|X|>|X|; in par­tic­u­lar, there is no largest car­di­nal num­ber.

Ap­pli­ca­tion: Mea­sur­ing sizes of sets when we don’t care about the con­text or com­po­si­tion.

#### Or­di­nal numbers

I’m afraid there’s no quick way to ex­plain these. The rea­son is that they are used to rep­re­sent two things—ways of well-or­der­ing things, and po­si­tions in an “in­finite list”—ex­cept, of course, that these are ac­tu­ally fun­da­men­tally the same thing, and to un­der­stand or­di­nals you need to wrap your head around this un­til you can see both si­mul­ta­neously. Hence I sug­gest you just go read Wikipe­dia, or some other stan­dard text, if you want to learn how these work. I will just speak briefly on their ar­ith­metic. Note that the or­di­nals too are or­dered—lin­early or­dered and well-or­dered, at that.

Un­like with the car­di­nals, ad­di­tion and mul­ti­pli­ca­tion of two or­di­nals will of­ten get you a larger or­di­nal. In par­tic­u­lar, for any or­di­nal λ, λ+1 is a larger or­di­nal. How­ever the mul­ti­pli­ca­tion of or­di­nals is non­com­mu­ta­tive. In fact, even the ad­di­tion of or­di­nal num­bers is non­com­mu­ta­tive! And dis­tribu­tivity only holds on one side; a(b+c)=ab+ac, but (a+b)c need not be ac+bc. So if you need com­mu­ta­tivity, or­di­nals (with their usual op­er­a­tions) are the wrong choice.

Con­trast the small­est in­finite or­di­nal, de­noted ω, with ℵ0, which is (as­sum­ing choice) the small­est in­finite car­di­nal. 1+ℵ0=ℵ0+1=ℵ0, and 1+ω=ω, but ω+1>ω. 2ℵ0=ℵ02=ℵ0, and 2ω=ω, but ω2>ω. ℵ02=ℵ0, but ω2>ω. And in a re­ver­sal of what you might ex­pect if you just com­plete the pat­tern, 2^ℵ0>ℵ0, but 2ω=ω.

#### Or­di­nal num­bers… with nat­u­ral operations

There’s an al­ter­nate way of do­ing ar­ith­metic on the or­di­nals, referred to as the “nat­u­ral op­er­a­tions”. Th­ese sac­ri­fice the con­ti­nu­ity prop­er­ties of the or­di­nary op­er­a­tions, but in re­turn get com­mu­ta­tivity, dis­tribu­tivity, can­cel­la­tion… the things we need to make the alge­bra nice. There’s a nat­u­ral ad­di­tion, a nat­u­ral mul­ti­pli­ca­tion, and ap­par­ently a nat­u­ral ex­po­nen­ti­a­tion, though I don’t know what that last one might be.

If you’ve heard “the or­di­nals em­bed in the sur­re­als”, and were very con­fused by that state­ment be­cause the sur­re­als are com­mu­ta­tive when the or­di­nals are not, the an­swer is that the cor­rect state­ment is that the or­di­nals with nat­u­ral op­er­a­tions em­bed in the sur­re­als, rather than the or­di­nals with their usual op­er­a­tions.

#### The ex­tended [pos­i­tive] real line

Some­times, we just use the set of non­nega­tive real num­bers with an in­finity el­e­ment (de­noted ∞, un­sur­pris­ingly) tacked on. Be­cause some­times that’s all you need. So:

Myth #2: Any place where you have in­fini­ties, you have the pos­si­bil­ity for differ­ing de­grees of in­finity.

Fact: Some­times such a thing just wouldn’t make sense.

Ap­pli­ca­tion: This is what we do in mea­sure the­ory—i.e. any­where in­te­gra­tion or ex­pected value (and hence, in the usual for­mu­la­tions, util­ity) is in­volved. If you want to claim that in your util­ity func­tion, op­tions A and B both have in­finite util­ity, but the util­ity of B is more in­finite than that of A… first you’re go­ing to have to make a frame­work in which that makes sense. Such a thing might in­deed make sense, but you’ll have to ex­plain how, as our usual frame­work for util­ity doesn’t al­low such things. (The prob­lem is that adding mul­ti­ple dis­tinct in­fini­ties tends to ruin the con­ti­nu­ity prop­er­ties of the real num­bers that make in­te­gra­tion pos­si­ble in the first place, but I’m sure if you look some­one must have come up with some method for get­ting around that in some cases.)

Some­times we al­low nega­tive num­bers and -∞ as well, though this can cause a prob­lem be­cause there’s no sen­si­ble way to define ∞+(-∞). (0∞, on the other hand, is just 0. We make this defi­ni­tion be­cause, e.g., the area of an in­finitely-long-but-in­finitely-thin line should still be 0.)

#### The pro­jec­tive line

Some­times we don’t even care about the dis­tinc­tion be­tween a “pos­i­tive in­finity” and a “nega­tive in­finity”; we just need some­thing that rep­re­sents some­thing larger in mag­ni­tude than all real num­bers, but which you’d ap­proach re­gard­less of whether you got large and nega­tive or large and pos­i­tive. So we take the real num­bers R, tack on an in­finity el­e­ment ∞, and we have the real pro­jec­tive line. Note that this doesn’t de­pend at all on the real num­bers be­ing or­dered, so we can do the same with the com­plex num­bers and get the com­plex pro­jec­tive line, a.k.a. the Rie­mann sphere.

Ap­pli­ca­tion: If you want to as­sign 1/​x some con­crete “value” when x=0, well, this isn’t go­ing to make sense in a sys­tem where you have to dis­t­in­guish ∞ from -∞.

#### Hyper­real numbers

What non­stan­dard anal­y­sis uses. Th­ese are more used as a means to de­duce prop­er­ties of the real num­bers than used for their own sake. You can’t even speak of “the” hyp­per­real num­bers, be­cause then you’d have to spec­ify what ul­tra­filter you were us­ing. Even just prov­ing these ex­ist re­quires a form of choice. You prob­a­bly don’t want to use these to rep­re­sent any­thing.

#### The sur­real num­bers: the in­finity kitchen sink*

For when you ab­solutely, pos­i­tively, have to make sense of an ex­pres­sion in­volv­ing in­finite quan­tities. The sur­real num­bers are pretty much as in­finite as you could pos­si­bly want. They con­tain the or­di­nals with their nat­u­ral op­er­a­tions, but they al­low for so much more. Do you need to take the nat­u­ral log­a­r­ithm of ω? And then di­vide π by it? And then raise the whole thing to the √(ω2+πω) power? And then sub­tract ω√8? In the sur­real num­bers, this all makes sense. Some­how. (And if you need square roots of nega­tive num­bers, you can always pass to the sur­com­plex num­bers, which I guess is the ac­tual kitchen sink.)

*The char­ac­ter­is­tic 0 in­finity kitchen sink, any­way. Char­ac­ter­is­tic 2 has its own in­finity kitchen sink, the nim­bers. I don’t know about other char­ac­ter­is­tics. I also have to won­der if there’s some set of char­ac­ter­is­tic 0 “in­finity kitchen sinks” that nat­u­rally ex­tend the p-adics...

Ap­pli­ca­tion: Again, kitchen sink.

#### ...and many more

Often the thing to do is make an ad-hoc sys­tem to fit the oc­ca­sion. For in­stance, we could sim­ply take the real num­bers R and tack on an el­e­ment ∞, in­sist it obey the or­di­nary rules of alge­bra, and or­der ap­pro­pri­ately. (For­mally, take the ring R[T], and or­der lex­i­co­graph­i­cally. Then per­haps ex­tend to R(T), or what­ever else you might like. And of course call it “∞” rather than “T”.) So (∞+1)(∞-1)=∞2-1, etc. What is this good for? I have no idea, but it’s a sim­ple brute-force way of toss­ing in in­fini­ties when needed.

#### Also: func­tions, which are prob­a­bly more ap­pro­pri­ate a lot of the time

Let’s not for­get—of­ten­times the ap­pro­pri­ate thing to do is not to start toss­ing about in­fini­ties at all, but rather shift from think­ing about num­bers to think­ing about func­tions. You know what’s larger than any con­stant num­ber? x. What’s even larger? x2. (If we only con­sider polyno­mial func­tions, this is equiv­a­lent to the “brute-force” sys­tem above, un­der the equiv­alence x↔∞.) Much larger? ex. Is x too large? Maybe you want log x. Etc.

## Topic #2: Ways of mea­sur­ing in­finite sets

The thing about mea­sur­ing in­finite sets is that we have a trade-off be­tween dis­crim­i­na­tion and ap­pli­ca­bil­ity. Car­di­nal­ity can be ap­plied to any set at all, but it’s a very coarse-grained way of mea­sur­ing things. If you want to mea­sure a sub­set of the plane, you’d be bet­ter off ask­ing for its area… just don’t think you can ask for the “area” of a set of in­te­gers.

#### Car­di­nal num­bers (again)

The most ba­sic method. Every set has a car­di­nal­ity. But the cost of such uni­ver­sal­ity is a very low re­s­olu­tion. The set of nat­u­ral num­bers has car­di­nal­ity ℵ0, but so does the set of even num­bers, the set of ra­tio­nal num­bers, the set of alge­braic num­bers, the set of com­putable real num­bers...

Note that the set of real num­bers is much larger and has car­di­nal­ity 2^ℵ0. (This is not to be con­fused with ℵ1, which (as­sum­ing choice again) is the sec­ond-small­est in­finite car­di­nal. The ques­tion of whether 2^ℵ0=ℵ1 is known as the con­tinuum hy­poth­e­sis.)

If we are work­ing with sub­sets T of a given set S, we can do a bit bet­ter by not just look­ing at |T|, but also at |S-T| (the size of the com­ple­ment of T in S). For in­stance, the set of nat­u­ral num­bers greater than 8, and the set of even nat­u­ral num­bers, both have car­di­nal­ity ℵ0, but within the con­text of the nat­u­ral num­bers, the former has finite com­ple­ment (num­bers at most 8), while the lat­ter has in­finite com­ple­ment (all odd num­bers).

#### Oc­ca­sion­ally: ordinals

If the sets you’re work­ing with come with well-or­der­ings, you can con­sider the type of well-or­der­ing as a “size”, and thus mea­sure sizes with or­di­nals. If they don’t have well-or­der­ings, this doesn’t ap­ply.

#### Mea­sure: the old fallback

Most com­monly we use the no­tion of a mea­sure to mea­sure sizes of sub­sets T of a given set S. This just means that we des­ig­nate some of the sub­sets T of S as “mea­surable” (with a few re­quire­ments—the whole set S must be mea­surable; com­ple­ments of mea­surable sets must be mea­surable; a union of countably many mea­surable sets must be mea­surable) and as­sign them a num­ber called their mea­sure, which I’ll de­note μ(T). μ takes val­ues in the ex­tended pos­i­tive real line (see above): It can be any non­nega­tive real num­ber, or just a flat ∞. We re­quire that the empty set have mea­sure 0, that if A and B are dis­joint sets then μ(A∪B)=μ(A)+μ(B) (called “finite ad­di­tivity”), and more gen­er­ally that if we have a countable col­lec­tion of sets A1, A2, …, with none of them over­lap­ping any of the oth­ers, then the mea­sure of their union is the sum of their mea­sures. (Called “countable ad­di­tivity”; this in­finite sum au­to­mat­i­cally makes sense be­cause all the num­bers in­volved are non­nega­tive.)

The func­tion μ it­self is called a mea­sure on S. So if we have a set S and a mea­sure on it, we have a way to mea­sure the sizes of sub­sets of it (well, the mea­surable ones, any­way). Of course, this is all very non-spe­cific; by it­self, this doesn’t help us much.

For­tu­nately, the set of real num­bers R comes equipped with a nat­u­ral mea­sure, known as Lebesgue mea­sure. So does n-di­men­sional Eu­clidean space for ev­ery n. And in­deed so do a lot of the nat­u­ral spaces we en­counter. So while sim­ply shout­ing “there’s a mea­sure!”, with­out stat­ing what that mea­sure might be, does not solve any prob­lems, in prac­tice there’s of­ten one nat­u­ral mea­sure (up to mul­ti­pli­ca­tion by some pos­i­tive con­stant). See in par­tic­u­lar: Haar mea­sure.

If we have a set S with a mea­sure μ such that μ(S)=1, then we have a prob­a­bil­ity space. This is how we for­mal­ize prob­a­bil­ity math­e­mat­i­cally: We have some set S of pos­si­bil­ities, equipped with a mea­sure, and the mea­sure of a set of pos­si­bil­ities is its prob­a­bil­ity. Ex­cept, of course, that I’m sure many here would in­sist only on finite ad­di­tivity rather than countable ad­di­tivity...

Note that if μ(S) is finite, then μ(S-T)=μ(S)-μ(T). How­ever, if μ(S)=∞, and μ(T)=∞ also, this doesn’t work; ∞-∞ is not defined in this con­text, and μ(S-T) could be any ex­tended non­nega­tive real num­ber. So note that if we’re work­ing in a set of in­finite mea­sure, and we’re com­par­ing sub­sets which them­selves have in­finite mea­sure, we can pos­si­bly gain some ex­tra in­for­ma­tion by com­par­ing the mea­sures of the com­ple­ments as well.

Here on LessWrong, when dis­cussing mul­ti­verse-based no­tions, we’ll typ­i­cally as­sume that the set of uni­verses comes equipped in some way with a nat­u­ral mea­sure. If the uni­verses are the many wor­lds of MWI, then this mea­sure will be pro­por­tional to squared-norm-of-am­pli­tude.

#### Mea­sur­ing sub­sets of the nat­u­ral numbers

So it seems like 2N should be half the size of N, right? Well there’s an easy way to ac­com­plish this: Given a set A of nat­u­ral num­bers, we define its nat­u­ral den­sity to be limn→∞ A(n)/​n, where A(n) de­notes the num­ber of el­e­ments of A that are at most n. At least, we can do this if the limit ex­ists. It doesn’t always. But when it does it does what we want pretty well. What if the limit doesn’t ex­ist? Well, we could use a lim­sup or a liminf in­stead, and get up­per and lower den­si­ties. Or take some other ap­proach, such as Sch­nirel­mann den­sity, where we just take an inf.

Of course, for sets of den­sity 0, this may not be enough in­for­ma­tion. Here we can pull out an­other trick from above: Don’t use num­bers, use func­tions! We can just ask what func­tion A(n) ap­prox­i­mates (asymp­tot­i­cally). For in­stance, the prime num­bers have den­sity 0, but a much more in­for­ma­tive state­ment is the prime num­ber the­o­rem, which states that if P is the set of prime num­bers, then P(n)~n/​(log n).

#### ...etc...

Of course, the real point of all these ex­am­ples was sim­ply to demon­strate: Depend­ing on what sort of thing you want to mea­sure, you’ll need differ­ent tools! So there’s many more tools out there, and some­times you may just need to in­vent your own...

• Ex­cel­lent. I want more out­put from the al­gorithm that gen­er­ated this post.

• Us­ing Solomonoff In­duc­tion I calcu­late that the most likely al­gorithm which gen­er­ates this post ter­mi­nates im­me­di­ately af­ter out­putting the last char­ac­ter.

• OK, put this now on the wiki. (Mo­dulo some for­mat­ting I didn’t bother to fix.) Do what you want with it.

• Here’s the out­put of my proofread­ing al­gorithm, which runs when­ever I read some­thing.

In the sec­tion Car­di­nal ar­ith­metic, you have that the set X×Y is the carte­sian product of A and B.

In The ex­tended [pos­i­tive] real line you have ‘with a an in­finity el­e­ment’.

In Hyper­real num­bers you have ‘”the” hyp­per­real num­bers’.

In your foot­note to The sur­real num­bers you have ‘some a set of char­ac­ter­is­tic 0 “in­finity kitchen sinks”’.

In Car­di­nal num­bers (again), the words ‘set of’ should be used one more or at least 4 fewer times.

The world needed this ar­ti­cle. I’m so glad you wrote it. It ob­vi­ously needs to be in a more promi­nent place, and mak­ing it a wiki seems like a good idea.

• Thanks, fixes made. LW doesn’t have a CW mode, so I guess I should post this on the ac­tual wiki?

• How do I get the × html en­tity?

• In a com­ment, SFAIK, you don’t. How posts are writ­ten and how com­ments are writ­ten are not con­sis­tent. Though if you’re will­ing to rely on peo­ple de­fault­ing to the cor­rect en­cod­ing, you could always just paste the char­ac­ter in di­rectly...

• if you’re will­ing to rely on peo­ple de­fault­ing to the cor­rect encoding

This site has proper Con­tent-Type head­ers, so it should work fine in all sane browsers.

• Oh, that’s good to know! I hon­estly didn’t think to check that. I’d for­got­ten they ex­isted.

• I’ll try that now.

• It worked! (At least for me.)

• A heroic effort, for which you should be ap­plauded. Mi­sun­der­stand­ings of ba­sic mea­sure the­ory are the cause of many avoid­able dis­agree­ments.

(0∞, on the other hand, is just 0. We make this defi­ni­tion be­cause, e.g., the area of an in­finitely-long-but-in­finitely-thin line should still be 0.)

I agree that in many con­texts it’s ob­vi­ous what we should mean by 0∞, in a way that it isn’t usu­ally for ∞−∞, but not that this defi­ni­tion is ei­ther always use­ful, or uni­ver­sally ac­cepted.

• Blorst horst.

I would like it if you paired each “myth” line with an ex­plicit “truth” line that gave the tl;dr for us, maybe even us­ing sim­ple lan­guage e.g.

Myth: The car­di­nal­ities of in­finite sets can be com­pared like or­di­nary num­bers. Real­ity: If the ax­iom of choice is false, you can have one set’s car­di­nal­ity be both larger and smaller than an­other’s

(maybe even a short blurb ex­plain­ing the ax­iom of choice’s role)

I could still un­der­stand you, but it cer­tainly helped that I’d bor­rowed my friend’s topol­ogy book over the sum­mer.

Rather than mak­ing a big list, some more struc­ture and an ac­tual con­clu­sion to topic #1 would have helped ce­ment things in my brain.

Since this turned out pretty long, you could ac­tu­ally split the top­ics into sep­a­rate posts in a se­ries. And with a lit­tle edit­ing I would be all for these be­ing top-level posts rather than dis­cus­sion se­cion.

• Real­ity: If the ax­iom of choice is false, you can have one set’s car­di­nal­ity be both larger and smaller than an­other’s

Ac­tu­ally with­out the ax­iom of choice, one set’s car­di­nal­ity can be nei­ther larger nor smaller than an­other’s.

• Blorst horst.

OK, I have to ask, how ex­actly did that be­come visi­ble?

I would like it if you paired each “myth” line with an ex­plicit “truth” line that gave the tl;dr for us, maybe even us­ing sim­ple lan­guage e.g.

Myth: The car­di­nal­ities of in­finite sets can be com­pared like or­di­nary num­bers. Real­ity: If the ax­iom of choice is false, you can have one set’s car­di­nal­ity be both larger and smaller than an­other’s

Ah, this is a good idea, es­pe­cially be­cause the cor­rec­tion you pro­pose is not quite cor­rect. :) It would be nei­ther larger nor smaller. I see I made the mis­take there of as­sum­ing fa­mil­iar­ity with par­tial or­ders, which was fool­ish; I for­got peo­ple need to be ex­plic­itly in­tro­duced to those.

(maybe even a short blurb ex­plain­ing the ax­iom of choice’s role)

Hm, do you re­ally think that would help? I was try­ing to more of provide a quick refer­ence of facts, while refer­ring el­se­where for proofs.

• Blorst horst.

OK, I have to ask, how ex­actly did that be­come visi­ble?

Magic. Also, you might have pressed a but­ton.

(maybe even a short blurb ex­plain­ing the ax­iom of choice’s role)

Hm, do you re­ally think that would help? I was try­ing to more of provide a quick refer­ence of facts, while refer­ring el­se­where for proofs.

You can still do that to a large de­gree, but I think that even for a LW au­di­ence it would be helpful to say what it is, state that it was used in the proof, and ex­plain briefly why we should keep both ax­iom-of-choice-is-true and ax­iom-of-choice-is-false cases in mind.

• Magic. Also, you might have pressed a but­ton.

What I mean is, did you see it when I ac­ci­den­tally posted it the first time, be­fore I deleted it, or did you some­how see it af­ter I then deleted it (in which case my name would have ap­peared as “[deleted]”), or were you some­how able to find the old ver­sion af­ter I posted the new one?

• Saw it the first time, com­posed first draft of com­ment then, tried to post and found out it had been deleted, was sad.

• I would like it if you paired each “myth” line with an ex­plicit “truth” line that gave the tl;dr for us, maybe even us­ing sim­ple language

I would have gone the other way and aban­doned the at­tempt to ar­range things in a list. I.e., I would have made the struc­ture sim­pler, e.g., sec­tions di­vided into para­graphs, e.g., no at­tempt to num­ber any­thing.

• OK, added an aside on par­tial or­ders, high­lighted more ex­plic­itly why you might use a par­tic­u­lar sys­tem (or stated it, if I hadn’t be­fore), bolded the cor­rec­tions to the myths. I wrote an aside on choice, etc., as Man­fred sug­gested, but that got to be too long so I haven’t in­cluded it here.

• I sus­pect that par­tial or­ders are one of the most gen­er­ally use­ful ab­stract tools that math-ori­ented peo­ple pos­sess and oth­ers lack.

Also, look­ing for­ward to the aside on choice.

• I’ll just post that as a com­ment here, since IMO it didn’t re­ally fit in the main body. Since it’s still in­tended as a side­note to the origi­nal ar­ti­cle, it’s re­ally just about how drop­ping things would af­fect the origi­nal ar­ti­cle, and why peo­ple would want to.

Quick aside on fini­tism, con­struc­tivism, foun­da­tion, choice, etc.

Again, none of this is re­ally rele­vant if you want to keep ev­ery­thing finite. I’m go­ing to as­sume you all have a good han­dle on nice finite things like ra­tio­nal num­bers.

Of course, not ev­ery­one agrees on just what can be safely as­sumed when deal­ing with the in­finite. The ax­iom of choice states that given any col­lec­tion of sets, no two over­lap­ping each other, there is some set con­sist­ing of one el­e­ment from each. I.e., there is some way to “choose” one el­e­ment from each, si­mul­ta­neously. This prob­a­bly seems ob­vi­ous—and in­deed, if you only have finitely many sets to make choices for, this doesn’t even need to be stated, it’s just a con­se­quence of clas­si­cal logic that you can pick them one at a time. But al­low­ing it in gen­eral has some un­in­tu­itive con­se­quences; per­haps more im­por­tantly, it’s non-con­struc­tive—the ax­iom as­sures you there is such a choice, but it can’t in any mean­ingful way tell you what it is. So con­struc­tivists, who in­sist that any proof that some­thing ex­ists, ought to also tell you what it ac­tu­ally is, will have no truck with it. Weaker forms of it, for those who are un­com­fortable with choice but don’t in­sist on con­struc­tivism, in­clude:

• The ax­iom of countable choice—You can make countably many choices si­mul­ta­neously. This is gen­er­ally too weak to do much of any­thing with.

• The ax­iom of de­pen­dent choice—A stronger form of countable choice, this al­lows you to make countably many choices, where each is al­lowed to de­pend on the pre­vi­ous ones. This gets used im­plic­itly a lot, but yes, it is in fact a form of choice.

• The Boolean prime ideal the­o­rem or ul­tra­filter lemma—Not go­ing to ex­plain this here.

Of course, if you’re such a con­struc­tivist that you’re ac­tu­ally a fini­tist, then I guess you prob­a­bly ac­cept choice, see­ing as it’s true for finite col­lec­tions of sets! (In clas­si­cal logic, any­way. I’ll get to that in a mo­ment.)

The ax­iom of foun­da­tion is per­haps also worth not­ing as some­what ques­tion­able. It just rules out cir­cu­lar (self-con­tain­ing) or oth­er­wise ill-founded sets. I doubt any­one here par­tic­u­larly wants to ad­mit those, and I don’t know that con­struc­tivists have any prob­lem with it; it’s some­what ques­tion­able mostly be­cause it’s es­sen­tially never rele­vant. Ill-founded sets don’t re­ally cause any real patholo­gies. I only even men­tion it here be­cause of my men­tion of Scott’s trick be­low.

Fi­nally, on logic: Real con­struc­tivists ac­tu­ally go a bit fur­ther than just pul­ling out ax­ioms they don’t like; they would in­sist clas­si­cal logic it­self is too pow­er­ful. They re­ject the prin­ci­ple of the ex­cluded mid­dle, and use a weaker form of logic, in­tu­ition­is­tic logic, which does not in­clude it. So if you ever hear a math­e­mat­i­cian say “Well, for that, you have to as­sume that ev­ery se­quence of whole num­bers is ei­ther the con­stant zero se­quence, or in­cludes some nonzero whole num­ber”, re­lax, they’re not in­sane, just con­struc­tivist.

Note in par­tic­u­lar that in­tu­ition­is­tic logic is not strong enough to get you “finite choice” by it­self—in­deed, if you have finite choice, you get the prin­ci­ple of the ex­cluded mid­dle and the whole thing col­lapses back to clas­si­cal logic. So per­haps you could in­deed be fini­tist but still re­ject choice; in any case, if I’m not mis­taken, I think even un­der in­tu­ition­is­tic logic, finite choice still holds for many sets that will prac­ti­cally come up.

The biggest an­noy­ance of drop­ping choice (in par­tic­u­lar de­pen­dent choice) is that con­di­tions that were formerly equiv­a­lent stop be­ing so, and you need to make dis­tinc­tions that were pre­vi­ously ir­rele­vant. This gets much worse if you pass to in­tu­ition­is­tic logic, and start hav­ing to spec­ify just what you mean by “real num­bers”!

(Then of course there are en­tirely differ­ent set the­o­ries out there—I’ve been im­plic­itly as­sum­ing ZFC or NBG, but this should only change things for the more set-the­o­ret­i­cal sorts of in­fini­ties, not the more usual ones.)

• This is the best ex­po­si­tion about in­fini­ties I have ever read. Great stuff!

I skipped the hy­per­re­als and I paid par­tic­u­lar at­ten­tion to ap­pli­ca­tions (e.g., Rie­mann sphere). The biggest benefit I got from the ex­po­si­tion (that I know about) is the con­cept of the set of the com­putable re­als and how its car­di­nal­ity com­pares to the in­te­gers and the re­als. That helped me in­crease my un­der­stand­ing of com­putabil­ity.

• Th­ese are more used as a means to de­duce prop­er­ties of the real num­bers than used for their own sake. You can’t even speak of “the” hyp­per­real num­bers, be­cause then you’d have to spec­ify what ul­tra­filter you were us­ing. Even just prov­ing these ex­ist re­quires a form of choice. You prob­a­bly don’t want to use these to rep­re­sent any­thing.

Yes, but note that given a non-patholog­i­cal ul­tra-filter two differ­ent ver­sions of the hy­per-re­als will look for most pur­poses the same.

• Wrong sec­tion. Posts like this go on the main page! :)