The different types (not sizes!) of infinity

post by Stuart_Armstrong · 2018-01-28T11:14:00.000Z · score: 104 (39 votes) · LW · GW · 31 comments

In a recent conversation, a smart and mathy friend of mine revealed they didn't understand Cantor's diagonal argument. Further questionning revealed that she was using the wrong concept of infinity. I thought I'd pass on my explanations from there.

What is infinity? Does one plus infinity make sense? What about one over infinity? Well, it all depends what concept of infinity you're using. Roughly speaking, infinity happens when you take a finite concept and add a "and then that goes on for ever and ever" at the end. There are four major examples:

  1. If you take the concept of "size" and push that to infinity, you get the infinite cardinals.
  2. If you take the concept of "ordered set" and push that to infinity, you get the infinite ordinals.
  3. If you take the concept of "increasing function" and push that to infinity, you get the poles and limits of continuous functions - a major part of real analysis.
  4. And if you take normal algebra and push that to infinity, you get the hyperreals.

To add to the confusion, there are normally only two symbols for infinity to go around - ω and ∞ - even though there are at least four very different concepts (honourable mention also goes to the infinities of complex analysis and algebraic geometry, which are like more limited versions of the real analysis one).

So, does ω+1 make sense (as something different from ω)? It does, for the ordinals and hyperreals only. What about ω-1, similarly? That only makes sense for the hyperreals. And -ω? That works for the hyperreals and real analysis. 1/ω? This is well defined for the hyperreals (where it is not equal to 0), and is arguably well-defined for real analysis, where it would be equal to 0.

Is ω times 2 the same as ω? "Yes", say real analysis and cardinals; "No", say ordinals and hyperreals. How about there being many different infinities of different sizes? That makes sense for all of these, except real analysis.

So when talking about "infinity", be careful that you're using the right concept of infinity, and don't mix one with another, or import the intuitions of one area into an arena where it doesn't make sense.

***

EDIT: See also Scott Garrabrant's comment [LW · GW]:

Starting with the natural numbers:

31 comments

Comments sorted by top scores.

comment by Scott Garrabrant · 2018-01-29T18:32:22.341Z · score: 44 (14 votes) · LW · GW

Starting with the natural numbers:

Cardinals: How many are there?

Ordinals: What comes next?

Limits: Where are they going?

Hyperreals: What is bigger than all of them?

comment by Scott Garrabrant · 2018-01-29T18:26:08.324Z · score: 29 (7 votes) · LW · GW

I think Surreals and Hyperreals are serving a very similar function. The Surreals take a total order as a foundation, and then push that up to infinity, then define algebraic opperations. The Hyperreals start with the large set of indexed lists of real numbers, define algebraic opperations pointwise, and then to make them totally ordered. They both seem like they are about combining ordered set, and infinity, and getting the algebraic stuff for free.

Ordererd set is about and , which is what defines the Surreals/Hyperreals. Ordinals are not abot that, and are instead about pushing the notion of successor to infinity.

comment by Chris_Leong · 2018-01-29T21:47:43.486Z · score: 5 (1 votes) · LW · GW

The problem for the Hyperreals for many applications is that aren't uniquely ordered (sadly I can't remember the name of the thing you need to define to get a unique ordering).

comment by Scott Garrabrant · 2018-01-30T07:47:32.812Z · score: 8 (2 votes) · LW · GW

Ultrafilter

comment by Qiaochu_Yuan · 2018-01-31T09:05:38.191Z · score: 28 (8 votes) · LW · GW

So, there are many mathematical posts of this form it would be extremely low-effort for me to write, and I'd be happy to write more such posts, except that I don't know what people are confused about in this way. Anyone have any requests and / or confusions they'd be willing to share?

comment by Stuart_Armstrong · 2018-01-31T13:44:54.707Z · score: 14 (3 votes) · LW · GW

Can't think of anything; this only came up because somebody failed to understand concepts I found easy.

comment by Ben Pace (Benito) · 2018-01-31T08:06:09.514Z · score: 19 (5 votes) · LW · GW

Paul Graham recently wrote a short essay about the value of things that are both general and surprising. I used to think infinities were of different sizes, not types, and I consequently didn't know what the types were. The post cleared up this basic yet deep confusion for me really quickly, and I expect similarly for many others. For these reasons, I've curated this post.

comment by Stuart_Armstrong · 2018-01-31T13:31:41.793Z · score: 4 (1 votes) · LW · GW

Cool, thanks. What does "curating this post" entail?

comment by Ben Pace (Benito) · 2018-01-31T21:56:54.912Z · score: 14 (3 votes) · LW · GW

There are a couple of different filters on the LessWrong homepage, and the 'Curated Content' filter is the most widely used - it gets on average 2 posts per week, and are the posts on LW that are the most widely read. For example, it's filter always selected for visitors to the site who aren't logged in, and I expect it's the most used RSS feed.

Posts appear in Curated Content when I or another mod curate them :-)

comment by ricraz · 2018-01-30T00:31:37.342Z · score: 16 (5 votes) · LW · GW

"So, does 1+ω make sense (as something different from ω)? It does, for the ordinals and hyperreals only. "

I am confused because for ordinals, 1+ω = ω. Did you mean ω+1?

comment by Stuart_Armstrong · 2018-01-30T07:38:17.504Z · score: 8 (2 votes) · LW · GW

You are right, I got the order of addition wrong. Corrected now.

comment by MakerOfErrors · 2018-02-02T02:30:49.746Z · score: 13 (4 votes) · LW · GW

I've been keeping 330 browser tabs open with the intention of getting back to each and every one of them some day. And finally one of those tabs comes in handy! This just proves that I should never close anything.

This is a video explaining the distinctions between cardinals and ordinals. This post may be useful in letting people know that there are different types of infinities, but it does nothing for actually explaining them. There are probably other good resources available online for those who want to know, but this is the only one I've ever seen. (Wikipedia is hopeless here.)

comment by cousin_it · 2018-02-01T12:32:45.678Z · score: 13 (3 votes) · LW · GW

Hmm, your post was at the top two days ago, and now it's at the top of today's posts. Does editing adjust the post date forward? This seems like a bug that many people will want to exploit :-)

comment by habryka (habryka4) · 2018-02-01T18:01:30.579Z · score: 5 (1 votes) · LW · GW

Huh, weird. Right now we reset the postedAt date when you move something out of your drafts, so maybe Stuart or a mod accidentally moved it into drafts and then out of it again?

The general pattern of moving things into drafts and then out again seems like a fine thing to have, especially if someone does significant revision in the meantime, but we do want to avoid people abusing it.

comment by cousin_it · 2018-02-01T18:34:33.037Z · score: 6 (2 votes) · LW · GW

The whole drafts thing is weird. I have a draft I can't delete, with someone's comment stuck on it.

Oh well. This still doesn't compare to the royal annoyance of how clicking a comment permalink makes it show up above the post. Every time I fall for that, I have to remind myself that life is short and the world's brokenness will outlive me.

comment by habryka (habryka4) · 2018-02-01T18:39:53.785Z · score: 5 (1 votes) · LW · GW

Ah, yeah. We should make a proper delete available.

And agree that I would like to improve comment linking at some point. Sorry for the suffering that appears to be causing you. Actually curious about what aspect causes the suffering.

comment by cousin_it · 2018-02-01T19:02:45.434Z · score: 16 (5 votes) · LW · GW

No worries Oliver! You've done a ton of good work too and I should say thanks more often, not complain all the time. And sorry for dragging this thread toward meta.

The annoyance is mostly because the current system is strictly less useful than showing the comment in full context right away. I will want to read upthread and downthread. Let me do that by looking and scrolling, don't make me click a small target first.

comment by habryka (habryka4) · 2018-02-05T05:03:04.850Z · score: 12 (4 votes) · LW · GW

Comment links now do the reasonable thing! Sorry for the confusion in the meantime!

comment by cousin_it · 2018-02-05T09:04:00.696Z · score: 10 (2 votes) · LW · GW

Works great, thank you!!

comment by habryka (habryka4) · 2018-02-01T19:15:00.359Z · score: 5 (1 votes) · LW · GW

Thanks! :)

Ah yeah, agree with that. I actually just had an idea for how I might be able to implement that without annoying technical changes. I will give it a try now (30% on it working out, but no promises).

comment by Stuart_Armstrong · 2018-02-01T20:49:23.408Z · score: 4 (1 votes) · LW · GW

I think that's because it just got curated.

comment by zulupineapple · 2018-01-29T11:51:03.313Z · score: 12 (3 votes) · LW · GW

More generally, don't assume that the same word means the same thing in different fields. Although, in this case, I'd say it's the mathematician's fault for being so incredibly obtuse.

But what about your friend and Cantor's argument? Was she confusing the "size" infinities with the "limit" infinities?

comment by Stuart_Armstrong · 2018-01-29T12:10:44.287Z · score: 7 (2 votes) · LW · GW

She was indeed confusing those two infinities, so couldn't grasp how there could be different sizes - a singularity/pole that rises faster to infinity, is still just a singularity, so it made no sense to her that infinities could be bigger than each other.

comment by Richard_Kennaway · 2018-01-29T12:49:23.098Z · score: 7 (2 votes) · LW · GW

Why did Cantor's diagonalisation not make it make sense to her, or at least show her that whatever was right, her intuition was wrong?

comment by Stuart_Armstrong · 2018-01-29T13:00:52.798Z · score: 4 (1 votes) · LW · GW

Because she wasn't thinking of infinity as being a list or a set (she wasn't thinking of cardinal infinities). So any list-based method seemed an illegitimate way of talking about infinity. (oh, and she was certainly willing to believe that the proof was correct - she didn't think all those mathematicians throughout the ages were wrong! She just didn't understand it).

comment by David Chudzicki (dchudz) · 2018-04-28T16:06:19.060Z · score: 11 (2 votes) · LW · GW
To add to the confusion, there are normally only two symbols for infinity to go around - ω and ∞

This post is the first I recall seeing ω used to refer to a cardinal. (The smallest infinite cardinal is usually called א‎₀.)

And I think hyperreals are probably a much less common topic than the other three, so at least we have different notation for the top three of these four notions (ω for the ordinal, א‎₀ for the cardinal, ∞ for the limit).

I'm not confident in this, but also: It looks to me like ω can be considered the same number in the ordinals, surreals, and hyperreals (since the surreals contain both of the other two). So I guess that's probably why we use the same notation, and why it's not really a serious ambiguity.

comment by roystgnr · 2018-01-29T18:36:54.944Z · score: 6 (2 votes) · LW · GW
So, does 1+ω make sense? It does, for the ordinals and hyperreals only.

It make sense for cardinals (the size of "a set of some infinite cardinality" unioned with "a set of cardinality 1" is "a set with the same infinite cardinality as the first set") and in real analysis (if lim f(x) = infinity, then lim f(x)+1 = infinity) too.

What about -1+ω? That only makes sense for the hyperreals.

And for cardinals (the size of the set difference between "a set of some infinite cardinality" and "a subset of one element" is the same infinite cardinality) and in real analysis (if lim f(x) = infinity, then lim -1+f(x) = infinity) too.

comment by Scott Garrabrant · 2018-01-29T18:40:08.579Z · score: 13 (3 votes) · LW · GW

The cardinal set difference one is not well defined. If I remove the evens from the integers, I have infinitely many left over. If I remove the integers from the integers, I have nothing.

The limits are also not well defined with addition and subtraction, as you can add a function that goes to infinity with one that goes to negative infinity and get all sorts of stuff. Hyperreals are what you get when you take the limits and try to make them well defined under that stuff.

comment by Stuart_Armstrong · 2018-01-29T20:58:10.096Z · score: 4 (1 votes) · LW · GW

Have rephrased as "So, does 1+ω make sense as something different from ω?".

comment by AlexMennen · 2018-01-30T04:28:28.323Z · score: 8 (2 votes) · LW · GW

1+ω = ω, for the usual ordering convention for ordinal addition.

Edit: I can't figure out how to delete my comment, but ricraz already said this.
https://www.lesserwrong.com/posts/GhCbpw6uTzsmtsWoG/the-different-types-not-sizes-of-infinity/xDfSmdiQATFF4sLPt

comment by Chris_Leong · 2018-01-29T21:59:30.418Z · score: 5 (1 votes) · LW · GW

Many of these notions of infinity simply add resolution to other notions of infinity. In the finites, what counts as a distinct number is generally clear (except for the infintesimals), but for the infinites, sometimes it is convenient to merge what could be considered distinct numbers togethers. For example, since there is a bijection from X to X+1, and hence from X to X+n, for any finite n, we are tempted to treat all these entities as the same as we really can't distinguish them very well. Unfortunately, some people conflate an inability to distinguish elements as the seperate elements not having their own existence, but it is well known, for example, that there are numbers that exist, but which can't be explicitly described and no-one says that these elements are all the "one" element.