Hacker News Reader

Comment by sreekotay | Hacker News Reader

Is that right?

So if a set is infinite but a provably strict subset of another - would we not say that set/infinity is smaller?

No, because with infinities, even if a set is a subset of another, you may still be able to find one element in the first set that corresponds to every element of the other set.

For example, the natural numbers are a subset of the whole numbers, but there is a natural number that corresponds to every whole number. To see this, we can order the whole numbers like this: {0, -1, 1, -2, 2, -3, 3, ...}, and we can easily see that we can now assign one natural number to each of them (0 -> 0, -1 -> 1, 1 -> 2, -2 -> 3, ...). Since you'll never run out of naturals, you won't ever find a whole number that doesn't have a corresponding natural number.

Since assigning a natural number this way is equivalent to counting the elements of the other set (in this scheme, I could say that -2 is the 3rd whole number), this type of infinity is called "countable infinity". The natural numbers, the whole numbers, and the rational numbers are all countably infinite. In contrast, the irrational numbers and the real numbers are not. In fact, even the real interval [0, 1] is not countable, so this interval is considered to have more elements than N (the set of natural numbers).

Note that while there is only one countable infinity, there are many uncountable infinities - so not all uncountably infinite sets are considered as large. If you're curious about this area, the study of these concepts is done via "transfinite numbers" - particularly, the transfinite cardinal numbers (there are also transfinite ordinals).

Surprisingly, no. For example, even though every whole number is also a rational number, mathematicians would say the size (or more accurately, the cardinality) of the set of whole numbers is the same as that of the set of rational numbers.

I'm personally a fan of the Infinite Hotel Paradox as an introduction to the subject.

Not only is the answer "no" like the sibling comment says, but in fact one definition of an infinite set is that it can be put into one-to-one correspondence with a strict subset of itself. In other words, infinite sets are precisely those for which your concept of size doesn't work.

Another sibling comment used the even/odd example, but that's not necessary to dispel this particular misconception. Consider the set of non-negative integers and the set of positive integers. That is, {0,1,2,3,...} and {1,2,3,4,...}. The latter is a strict subset of the former. Maybe I have just done mathematics for too long, but to me these are intuitively, "obviously" the same size. What would it even mean for one of them to be smaller? Which one is the same size as {-1,-2,-3,...}, if either of them? Even doing folk mathematics, if the size of the first is "infinity" then the size of the second is "infinity minus one which is still infinity".

There are the same number of even integers as there are even and odd integers

If they are the same number what number is it.

It's called ℵ 0 (Aleph 0).

I like when someone asks a question that looks snarky, maybe rhetorical like saying "what you are saying is nonsense, look, this question cannot be answered", but then there is a perfectly valid answer

The answer isn't all that valid. ℵ₀ is just a name defined by the statement "the number of integers is ℵ₀". You could also call it Bob. If you don't think Bob would be a valid name, you should reject ℵ₀ too.

The name isn't unique either; by definition, ℵ₀ is equal to ℶ₀. This should be a clue that the term ℵ₀ is not actually meant to identify the number in question. Rather, what's going on is that there is a conceptual system of ℵ numbers, and another conceptual system of ℶ numbers, and the number at index 0 in each of those systems is the cardinality of the naturals.

But I don't think Bob is a valid name because if I use it to refer to the cardinality of the naturals, nobody would know what I'm talking about.

I don't see why I have to reject aleph null just because I reject Bob.

If it were called "Bob", students would inevitably read their profs' handwriting as "eight hundred six", leading to all sorts of hilarious confusion.

> ℵ₀ is equal to ℶ₀

That's the definition of ℶ₀. So of course they are equal.

"Two" is also just a name for the successor of 1. I could also call it "bob" and thus "two" would not be unique, but I don't see the point. The fact is that the cardinal of countable numbers is a mathematical concept which has a name, and can be manipulated. Which is what matters, and what the parent poster maybe did not understand.

> "Two" is also just a name for the successor of 1. I could also call it "bob" and thus "two" would not be unique, but I don't see the point.

There is no point, because 2 is well defined.

That is also true of the ℶ numbers, but it is not true of the ℵ numbers. That's why, in that case, it's necessary to have multiple names for the same number.

> The fact is that the cardinal of countable numbers is a mathematical concept which has a name, and can be manipulated.

No, that's not a fact, that's what I'm saying.

The cardinality of the naturals is a mathematical concept. It is referred to as "the cardinality of the naturals", or by many similar phrases.

But it is not referred to by the name ℵ₀. ℵ₀ is a name that refers to a different concept, the cardinality of the ordinal number ω. The two cardinalities are equal, but ℵ₀ specifically refers to one of them, conceptually, rather than the other.

ℶ₀ refers to a different concept again. That's the one that is meant to be manipulable.

You could (using "is a subset" as a partial order), but you can't make a total order. Any way you try to compare size of sets where neither is subset of the other, while preserving your intuition of "size" will run into trouble.

You make "the ordinals" sort of using your idea, but that isn't really measurement of "size"; it's more like an assignment of ranks.

Reply on news.ycombinator.com