One way to say two sets of things are of equal size is if we can pair up all the elements of one set with all the elements of the other.

If we're ok with extending that to sets of infinite things (we can still pair elements of each set, we'd just never be able to finish listing all the pairs), then we can say that the natural numbers and "the set containing the natural numbers and a sandwich" are of equal size because we could pair 1 from the first set with the sandwich from the second set, pair 2 from the first set with 1 from the second set, 3 from the first set with 2 from the second set, etc etc.

There's no element of either set without a match in the other set, so they have the same cardinality as the natural numbers, with or without the sandwich.

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.

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?

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.)

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.

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?

Because it's the same size. I can show it's the same size because I can just change the labels on the sets (label change of elements doesn't change group size) and go back and forth. In this case, 0 is the sandwich, and all the nonnegative numbers get relabelled down by one. Going back, sandwiches become 0 and you add one to nonnegative numbers. So they've got to be the same size, if I can go back and forth and everything just gets a new label and I don't miss anything.

The cardinality of infinite sets is unintuitive. We can create a one to one correspondence between the Naturals+Sandwich set and the Naturals set (for example, assign sandwich to 0, 0 to 1, 1 to 2, 2 to 3, etc). That means they have the same cardinality.

It's even possible to add an infinite number of elements to an infinite set and retain the same cardinality (the Integers set has the same cardinality as the Naturals set).

You can create a bijection between that set and the set of natural numbers, defined by the function f:

0 <-> sandwich

1 <-> 0

...

n+1 <-> n

By definition, if you can biject two sets, they have the same cardinality.

Because cardinality of finite sets is intuitive, but cardinality of infinite sets is less intuitive and totally different. The natural numbers plus a sandwich is mixing the two together in a single argument, which doesn't really track.

For the same reason that integers have the same cardinality as only odd numbers. You can create a 1:1 mapping between them.

Not just one-to-one (injective) but also onto (surjective). :)