Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It's interesting, however there is something I quite don't understand:

"[...]we can take 0 and 1, promote them above all the other naturals, and get a new order on the naturals, which looks like (2,3,4,…,0,1). This looks like a shifted-copy of ω, followed by exactly two new things on top. Its order type: ω+2. Similarly we can get ω+3, ω+4, and so on."

I don't understand how that's "infinity + 1" or "infinity + 2" when it's the same number of element, just in a different order.



The answer lies in the difference between a cardinal and an ordinal. A cardinality is a size, an answer to "how many". As in 1, 2, 3... An ordinal is a position. As in first, second, third...

For finite numbers they are trivially equivalent. No so for infinite. If you add 1 to ω you haven't changed the cardinality at all. But if you append a new number after ω then that new number is in a position which doesn't exist anywhere in ω, and therefore it must be a larger ordinal.

So because cardinals and ordinals are different, there is no problem with ω+2 being a larger ordinal than ω, even though it has the same exact cardinality.


Also of some note is the fact that ω+1 has something that ω does not, it has a single unique element that is greater than all other elements, something that ω doesn't have.


No so for infinite. If you add 1 to ω you haven't changed the cardinality at all. But if you append a new number after ω then that new number is in a position which doesn't exist anywhere in ω, and therefore it must be a larger ordinal.

It's worth noting that ordinal addition and multiplication are not commutative. 1+ω = ω ≠ ω+1


I don't really don't like the wording of the author - "infinity + 1" - because it isn't. The omegas are used to describe the ordering of the set and not, in any way, the "magnitude" of the infinity.

Well, I guess the catch phrase "infinity is a number - an infinite number of numbers" is just too good of a "deep wisdom" that people repeat it regardless of how much sense it makes.

Anyway, omega + 2 tells us, to put it simply, that we have a countably infinite subset, followed by a finite subset of two elements. In the same way, omega + omega would mean one countably infinite subset followed by another.

Note that this has no bearing whatsoever in the magnitude of the set. No matter how many omegas you add, you can still project the result onto the "basic" set of natural numbers. The labels don't matter, you aren't limited by the author's example of splitting even/odd. You can try it with sets {x, xx, xxx, ...} and {y, yy, yyy, ...} and they still project onto the naturals just fine.


Nevertheless there is this useful notion of addition for ordinal numbers, as well as multiplication, exponentiation and so on. And so the 'omega + 1' notation is common.

It is an ambiguous notation though -- you need to know whether it's ordinal arithmetic, or cardinal arithmetic, being used. Usually it's clear from context; and of course the two coincide on the plain old natural numbers.

http://en.wikipedia.org/wiki/Ordinal_arithmetic for anyone interested in investigating further.

One interesting fact is that while ordinal arithmetic can satisfy a lot of the properties you'd expect, it's not commutative in general: omega+1 > 1+omega = omega.

As for whether or not ordinals have the right to be considered 'magnitudes' in a sense, or whether only cardinals deserve that name. I think this stuff already strays so far from the realms of normal human intuition about magnitude that this would be more just an argument over definitions than anything else.


Cardinality is a measure of size, and (by definition) all countably infinite sets have the same number of elements based on the principle that any two sets for which we have a bijection between them are of the same size.

Ordinals deal with something else: complexity of orderings upon sets. As the ordinals get "larger", the orderings they represent get increasingly complicated. Once we're past the Church-Kleene ordinal, they're so convoluted that we can't algorithmically compare them.


Ordinals already have an order imposed on them. When you write (2, 3, 4, ...., 0, 1) you are imposing an order and in this particular order 0 has no immediate predecessor. This is key. 0 is the only element with predecessors but no immediate predecessor. The standard ordering of the natural numbers doesn't have this property.

The cardinality of a set is independent of any ordering you put on it. I hope this helps to distinguish between these concepts. Omega+1 has the same cardinality as Omega but different ordinality.

It is true though that a set is uncountable (cardinal concept) if and only if every ordering of it admits elements with predecessors but no immediate predecessor.




Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: