Hacker News Reader

You know the Infinite Hotel problem, right?

You have a Hotel with infinite rooms in it. An Infinite Bus shows up with infinite passengers. As each passenger comes into the lobby, you give them the next room key, so that everyone gets a room.

An hour later another Infinite Bus shows up. Oh dear. Now what will you do? You call the manager and he says no problems. What you're going to do is go to room 1, apologize and ask them to kindly relocate to room 2. Offer a complimentary breakfast by way of apology. Then go to each subsequent room and ask the inhabitants to move from their room number to 2n. Now that all of the current guests have moved to their new, even numbered rooms, you can put the second bus into the odd numbered rooms and everyone is happy.

As Standup Maths recently pointed out, the problem is that we think of infinity as "count until you get really tired of counting and then it's one more than that". Which is just not a workable definition and causes problems.

That example doesn't help you with Galileo's Paradox. In fact it says after the infinitely many new guests arrived, there are now still just "as many" guests as before, even though the new guests are a proper subset of the total guests. The problem is whether you accept this definition of "as many". You could also follow Galileo and say that size comparisons of infinite quantities don't make sense.

To be honest, I don't like any of these "examples" at all because they attempt to map "intuitive" concepts, which are things like "size", "more than" and "fewer than" when applied to something that is finite, to something where that intuition doesn't even make sense in the infinite realm.

I mean, in your example, how can the first "infinite bus" ever empty in the first place to fill up the infinite hotel? After all, if it's an infinite bus, people will always keep streaming out of it. When you ask the guests to move from door x to 2x, that request never finishes, so you never are able to stop and then ask for guests from the other infinite bus to access the odd rooms.

What actually helped me understand the concept of the cardinality of infinite sets is to get rid of the whole notions of "size", "more than", "fewer than", etc. and instead just stick to the concept of mapping: is there a single, deterministic function that can output a unique value Y, where Y exists in some particular set, for every input value X, where X comes from another set.

Honestly, I think trying to use the same words like "size of" when talking about infinite sets was a mistake.

"I mean, in your example, how can the first "infinite bus" ever empty in the first place to fill up the infinite hotel?"

This is easy, you need to shout at the people so each person leaves the bus twice as fast as the previous one. For example the frst person needs 1 minute to leave the bus, the second 0.5 minute, etc. In 2 minutes the bus is empty :)

If it breaks your brain less, you can think of it as the tour guide comes off bus 1 comes in and ask if there is enough room. The clerk says yes and the people start filing off the bus. Eventually they all will get a room. Then an hour later a second bus shows up and asks the same. Now the clerk isn’t sure.

Of course you can’t have an infinite hotel. The construction time would be murder and you can only manage so many people so you have an infinite number of cleaning staff reporting to an infinite number of middle managers. And it takes you forever to do pay stubs. But that’s why it’s a thought experiment.

> But that’s why it’s a thought experiment.

My point is I think it's a bad thought experiment. In my opinion just using the actual "mapping" concept directly is much less confusing than clumsily reusing the definition of "size" and other concepts that are really irrelevant in an infinite world.

This is an interesting idea but I don't get how it works in practice. For instance, the two sets {1,2,3,4} and {A,B,C} are such that none is equal to a proper subset of the other. Are you suggesting these be treated as "the same size as" one another? Because if so, then {1,2,3,4} is "the same size as" both {A,B,C} and {A,B,C,D}, even though {A,B,C} is not "the same size as" {A,B,C,D}.

On the other hand, we can say that although {A,B,C} is not equal to any proper subset of {1,2,3,4}, it is in bijection with a proper subset, such as {1,2,3}. Although this is true, if we use this definition of "the same size as," we again get that the naturals are "the same size as" the set of all squares.

> For instance, the two sets {1,2,3,4} and {A,B,C} are such that none is equal to a proper subset of the other.

The existence of an injective function is what makes subset {A,B,C} a "proper subset" [sic] of {1,2,3,4}, in context of comparing their size.

The terminology could be chosen better, but I think the intended meaning is clear.

This is exactly what I wrote about in my second paragraph, isn't it? The intended meaning is not clear, because this definition again makes the set of naturals the same size as the set of squares.

> On the other hand, we can say that although {A,B,C} is not equal to any proper subset of {1,2,3,4}, it is in bijection with a proper subset, such as {1,2,3}. Although this is true, if we use this definition of "the same size as," we again get that the naturals are "the same size as" the set of all squares.

Ah, I see. I have't read your comment properly, I guess.

That's a fair point, it really seems that comparing sets in general only makes sense in terms of bijections, which makes infinite sets as comparable as finite sets.

> For instance, the two sets {1,2,3,4} and {A,B,C} are such that none is equal to a proper subset of the other. Are you suggesting these be treated as "the same size as" one another?

No. The paradox is that intuitively

1. If there is bijection between F and G, they are the same size.

2. If F is a proper subset of G, F and G are not the same size.

For finite numbers, these principles are compatible, but for infinities, it can happen that they contradict each other.

Ok. So are you suggesting a notion of "size" such that A is a smaller "size" than B if and only if A is extensionally equal to a proper subset of B? This would lead to a partial order on all sets. As a result, the perfect squares would smaller than the naturals, but also it would make many sets incomparable in size, including the natural numbers and the set {A}.

Or if this is not what you are suggesting, what are you suggesting?

I find Galileo's conclusion plausible that neither principle holds for infinite sets.

Being able to understand the way in which mathematical usage of phrases like “the same size as” is different than intuitive uses of the same phrase is becoming increasingly important. Only six months ago I was seeing a dozen YouTube videos a day claiming g “Physics proved that the universe is not real!” because some physicist decided to overload the “real” operator in the English language.

> That there are infinities of various sizes follows if you accept Hume's Principle, which says "the number of things with the property F equal the number of things with the property G if and only if there is a one-to-one correspondence between those that are F and those that are G."

I don't think that accepting(?) principles(?) is the right way to think about it.

This ordering on this family of infinities is as much of a definition as everything else. You don't accept principles when you talk about matrices, or circles or rings.

Matrices and rings are technical terms without preexisting intuitions, but "the same size" seems to be an intuitive concept, like "natural number" or "circle". So presumably any definition should be compatible with our existing concepts. Although Galileo argues against size having an intuitive sense for infinities.

> So presumably any definition should be compatible with our existing concepts.

Yes, this is the wrong way (IMO) to think about it. The right way is to notice that it is a definition, and to think about it like every other definition. It has the name "same size", because it has some properties common with "same size" of finite cardinalities, but not all properties common.

And this is the proper way to think about every other definitions and objects as well, even if they are technical terms, or borrowed from common English. (BTW I believe that rings are called rings, because of some similarities with rings.)

It always made more sense to me to define things as "one to one AND that one set's of elements is not absolutely contained in the other set." This would make the integers bigger than the even integers because 2Z in Z but would mean that the evens and the odds are the same size, since they are disjoint sets. Though both are obviously categorically countable.

But I'm not a (set) theorist and I'm sure this has been explored before. Does anyone have a link and/or concise explanation? (papers are fine) Would this definition result in similarity weird conclusions? (Infinities are weird)

I mean this doesn't actually solve the issue: 2Z and 3Z are the same size under this definition.

> 2Z and 3Z are the same size under this definition

That's quite the intention actually. The motivation here is that there is clearly a 1-to-1 and onto (bijective) mapping between these sets. While we can set a clear map even from Z to 2Z (T: x -> 2x) there are other maps that work perfectly as well. For example if we take the ideal/subset of Z such that we use every other number (i.e. the evens) then this also corresponds to 2Z but we still have an infinite number of numbers left over.

Let's be more clear

Z = {Z+} + {Z-} + {0} = {2Z+} + {(2n+1)Z+} + {2Z-} + {(2n+1)Z-} + {0}

2Z = {2Z+} + {2Z-} + {0}

Then if we do Z - 2Z we get {(2n+1)Z+} + {(2n+1)Z-} (or the odds without 0). In other words, we have infinity plus infinity but one of the infinities is fully contained in the other infinity. It does seem reasonable to think that these may not be the same size, just as we would say that the uncountable infinities is larger than the countable infinities. In fact, the logic is quite similar here.

Note though, that the sibling comment (to you) gave a counter example as to where there might still be issues. Because by this setup we'd still have the number of primes equal to the size of even integers. So I asked about rates of going to infinity.

Consider the following sets: the primes (let's call it P), the odd numbers (let's call that O), the odd numbers except for 3 (and let's call this O3).

Using your definition O would be equal in size to P, P would be equal in size to O3, but O3 would be smaller in size than O.

Ah thanks! That's an obvious counter example!

But as a followup, are there definitions that rely the rate at which sets approach infinity? P clearly "fills" its set more slowly than the even integers whereas the evens and odds "fill" the set in similar times. This would obviously mean 2Z, 3Z, and 3Z - {3} would be the same size (unless we invoke the disjoint requirement), but these could be used categorically like Big O notation (which can be refined).

Would this an even useful metric? Are set theorists even interested in differentiating these infinities?

Edit: I also gave a bit more motivation in the reply to your sibling comment. Short is that if we do "Z - 2Z" we can get the two sets of positive odds and negative odds without {0}. It seems reasonable that since we can do this decomposition and match in the normal manner that since there is a remainder that one would be larger than another but this also does not clear up the example you provided with primes.

I always thought that a "growth rate" definition of sizes of infinity makes more sense than Hume's principle. Then the odd numbers approach infinity half as fast as the natural numbers. But that only works for ordered quantities.

It seems like Hume's Principle is only a matter of semantics, not of mathematics. The concept of one-to-one correspondence is useful even if we don't refer to it as size. All existing proofs would be equally valid even if we didn't accept this definition of 'size', since it would still be true that there is or isn't a correspondence between two sets, even if we refer to it in a different way.

Well, set theory contains axioms specifically to introduce sets of such "size". These axioms aren't just definitions.

Given that a one-to-one correspondence is just a renaming, and renaming things doesn't change how many there are, this seems sound.

It's not just a renaming. The following is true: The square numbers are a proper subset of the natural numbers. If you switch "square numbers" and "natural numbers" it is false. If two terms can't be exchanged salva veritate, they are not equivalent.

Your failure to do the actual renaming doesn't make the renaming a failure. No one has claimed that the set of squares is extensionally equal to the naturals. The existence of a bijection has nothing to do with extensional equality of the given sets. It's not even a particularly strong equivalence among those in everyday use. I guess the category theorists have a cute name for this (morphism? Who knows...), but it is to set cardinality as homomorphism are to groups.

But in fact even if the claim had been about extensional equality, HoTT shows how this can be carried out correctly: the equivalence between two types (which is supposed to be actual Leibniz equality, not merely equinumerosity as in the example) must be used, as if a function, to transport actual terms between the two types. Using this mechanism, the subtype of square naturals is in fact extensionally equal to the naturals. For example, the term `f 4` where `f` is the transport along `squares = N` is in fact the sum of the multiplicative identity with itself. This is what I meant by actually doing the renaming.

He said "just" a renaming, which suggests just the names change while the meaning stays the same, which isn't the case. Maybe he meant it in some different "HoTT" sense, but he clearly said

> Given that a one-to-one correspondence is just a renaming, and renaming things doesn't change how many there are, this seems sound.

which would only be the case for renaming salva veritate -- or by begging the question in favor of one-to-one correspondence being sufficient for something being the "same size" and against proper subsethood being sufficient for something being not the same size. But that's exactly the question when arguing for or against Hume's Principle, not something which can be assumed.

> He said "just" a renaming, which suggests just the names change while the meaning stays the same, which isn't the case.

Huh? That's exactly what's happening.

If you rename 1, 2, and 3 to one, two, and three, the names have changed and the meanings haven't. As you note, this is what "renaming" means. It used to be true that 1 + 2 = 3, but now that's gibberish and one + two = three instead.

Nothing about that changes if you instead rename 1, 2, and 3 to 88, 89, and 90. It will still be true that 88 + 88 = 89. You don't get to reinterpret what the name means after you assign it.

Well, then the squares are still a proper subset of the natural numbers, while still being in a one-to-one correspondence, so Galileo's Paradox remains. Then renaming didn't change anything.

The problem is that infinity is not a number. Infinity plus one is equal to infinity. This is not a trait that any number has. There is no number where you can add one and get the same number. The subset of an infinite set can itself be infinite. If you can map bi-directionality (which you can for square numbers and naturals) between an infinite set and its' infinite subset, then they are equivalent in size. Your problem is that you expect infinity (well, one type of infinity, there are ordered infinities [edit: when I said infinities, I meant infinite numbers, which the common infinite is not an infinite number, it's infinity], but that's outside our scope here) to be ordered, which it is not. Numbers are ordered, but infinity is not a number and is not ordered in the numbers.

> The problem is that infinity is not a number. Infinity plus one is equal to infinity. This is not a trait that any number has. There is no number where you can add one and get the same number.

This is all false. What you describe is a violation of the Archimedean principle. "Numbers" are a wider concept than the Archimedean principle.

It’s still just a renaming. In fact you might even perform the renaming and thus form the bijection without even realizing it, if you talked about “the first square number,” “the second square number,” etc.

It is an injection, but not a surjection.

You need neither though. For example:

y = x ^ 2 when even, (x+1) ^ 2 otherwise

> It is an injection, but not a surjection.

It's a bijection. (And therefore obviously also a surjection.) "One-to-one correspondence" is a correct, but incomplete, description.

∄ x ∈ ℕ: x² = 5

Unless you consider the domain of f the "renamed" range, in which case yes tautologically it is bijective.

You're talking past one another. The other poster is discussing a correspondence between N and S, where S is the set of squares. So the function being discussed is f: N -> S, f(n) = n^2, which is obviously bijective.

You seem to be talking about the function f: N -> N, which isn't surjective, but I don't see the relevance. Any surjective function can be made non-surjective by considering a larger range.

> You seem to be talking about the function f: N -> N, which isn't surjective, but I don't see the relevance.

It's worse than just irrelevant. The claim is that we have two sets, ℕ and S, that are the same size. The argument that they are the same size is the observation that we've demonstrated a bijection between them.

No one ever mentioned a function from ℕ to ℕ, because that would tell you nothing about S. It would be like saying "in order to show that 5 is odd, observe that 2 and 2 are both even". The idea is gibberish.

We are only taking sizes here not “is it a group” etc.

So let’s play that old 21s drinking game, but infinitely instead of 1 to 21, and rename 1 to 1, 2 to 4, 3 to 9 and so on, up to x for any x. Same set, different lingo.

That you can’t map back 5 is irrelevant although kind of leaves a bad taste.

If mathematicians have to choose between two definitions where one results in the task not making sense, and the other gives rise to a new theory with nontrivial open problems, the choice is easy :)

:)

But Galileo's objection would seem to imply that there should be more infinities, not fewer.

A definition like "F and G are the same size if there is a one-to-one correspondence, except when F is a proper subset of G, then F is smaller" wouldn't work, because that isn't an equivalence relation. While "is the same size" seems in fact to be such an equivalence relation. For example, there might be a set H, such that H would be "the same size as" F and as G (due to one-to-one correspondence), but F would be smaller than G (due to proper subsethood). This would violate transitivity.

I'm not saying there's a definition that works down that path (I don't know); I'm saying that "we only have multiple infinities because of this definition, which people objected to because it didn't give us enough infinities" seems a little muddled.

The argument seems to be rather that intuitions for size and subsethood and bijection aren't compatible anymore, which is a reductio argument against assuming that size comparisons make any sense for infinities at all.