Hacker News Reader

Comment by bmitc | Hacker News Reader

The non-sandwich analogy is called Hilbert’s hotel.

Saying that two sets have the same cardinality is equivalent to them having a bijection between them.

So the claim is that the natural numbers and the natural numbers plus a sandwich have the same cardinality. This can be proved by the bijection:

    0 -> sandwich
    1 -> 0
    2 -> 1
    3 -> 2
      .
      .
      .
    n -> n-1
      .
      .
      .

There is actually more though! If you had an infinite but countable amount of sandwiches (that is a sandwich for every natural number), that plus the natural numbers still has the same cardinality as just the natural numbers. There, the bijection is

    0 -> sandwich_0
    1 -> 0
    2 -> sandwich_1
    3 -> 1
    4 -> sandwich_2
    5 -> 2
      .
      .
      .

No natural number or sandwich is left out by this mapping.

View on HN

Don't stop there! Let's have a countably infinite variety of sandwiches, with a countably infinite number of sandwiches of each variety.

Still enough natural numbers to eat them all, one per.

But still not enough sandwiches to feed all the (so-called) real numbers one sandwich each!

But if sandwiches grew on trees, and we had an infinite branching tree with two branches at each branching point, and every branch has a (pair of) sub-branches, then natural numbers could not eat all the sandwiches, and the sandwiches could feel all the (so-called) real numbers.

Because everyone gave me such good and well meaning answers perhaps you’ll permit me a follow up.

As I understand it we can say the cardinality of the reals is 2^aleph_0. Why is it cheating to create a bijection thusly:

    0 -> 0
    1 -> 1/(2^aleph_0)
    2 -> 2/(2^aleph_0)

etc?

Problem 1: 1/(2^aleph_0) isn't a real number. The real numbers don't contain infinitesimals. It's possible to formalize a number that behaves like 1/(2^aleph_0) "ought to" (surreals would be one possible approach), but the result won't be a real number.

Problem 2: There's no natural number that maps to (say) 1. Even if you do allow 1/(2^aleph_0), there's no finite number n that would make n/(2^aleph_0) = 1. With any reasonable definitions of the operations involved here, n/(2^aleph_0) would always be infinitesimal, so it would never equal a non-infinitesimal.

Problem 3: You're still skipping over infinitely many numbers. If 1/(2^aleph_0) is a number (and again, this requires going beyond the real numbers) and 1.5 is a number, then 1.5 * 1/(2^aleph_0) = 1.5/(2^aleph_0) is also a number, but no natural number gets mapped to that.

1/(2^{\aleph_0}) isn’t something that has a clear meaning.

2^{\aleph_0} is a cardinal number, which isn’t really a number in the sense of “an element of a field” or something like that. Dividing by it isn’t a well defined thing.

And, you certainly can’t just multiply any real number (or, any real number between 0 and 1) by 2^{\aleph_0} and get a different integer as a result.

(Now, if you work in the surreal numbers, you can define things like n/(2^{\aleph_0}) (identifying cardinals with the first ordinal of that cardinality), but these would not be real numbers. They would all be infinitesimal , smaller than 1/k for all positive integers k, and yet bigger than 0. Similarly in the surreal numbers, you could multiply real numbers between 0 and 1 by 2^{\aleph_0}, but you would get surreal numbers which are larger than every integer (in fact, larger than any countable ordinal))

Summary: What you wrote doesn’t define a mapping from the integers to the real numbers . (It can be interpreted as defining a map from integers to something else though.)

I am not entirely sure what you wrote or are asking, but if you're interested in this stuff, come take the course (or read the book) I mentioned here:

https://news.ycombinator.com/item?id=27846666

Are real numbers uniformly spaced? Or are there clusters?

Reply on news.ycombinator.com