Levels of Infinity
xamuel.com
xamuel.com
So, in our model 'S' there is some element 'o', such that there is no 'x' in 'S' such that 'x e o' -- that is, no 'x' is in a relation 'e' with 'o'. If we take into account that relation 'e' is supposed to represent set membership in our model, we notice that this object 'o' represents an empty set in our model, the existence of one is ensured by usual set theory axioms. Since every object in the set theory is a set, so is our 'o', and although it represents an empty set in our model, it does not need to be in fact empty -- it is enough that it is empty in the sense of our special membership relation 'e'.
Apart from "empty set" 'o', in our model there are representatives for all the usual sets we know -- the set of natural numbers, reals, functions from naturals to {1, 2} (and {1, 2} as well) -- and under our relation 'e' they behave in exactly the same way as usual sets behave under usual set membership relation.
So far, our models looks exactly like the whole universe, only smaller. But, thanks to some results of model theory (precisely, the Lowenheim-Skolem theorem), we can impose another restruction on our model -- we can require it to be countable.
Now this is really mind blowing -- our model behaves just like the whole universe and yet there is only as many elements in it as there are natural numbers! Sounds quite paradoxical -- you could ask, but what about Goedel's theorem? It sure has to hold, because this is a model of set theory, but yet there are exactly as many reals as naturals in our model -- countably many. How is that even possible?
Well, the answer is quite obvious -- the concept of "cardinality" is not absolute. When we say that two sets have the same cardinality, we mean that there is a bijection between their elements. Since our model is countable, there is a bijection between elements representing natural numbers and the ones representing reals. But there is no paradox -- this bijection is not an element of our model. It shows that that naturals' and reals' representatives are in bijection, but only in the whole universe. When we restrict ourselves to our model an we ask for an element representing such a bijection, none exists. While there are exactly as many 'reals' as there are 'natural numbers' in our model, we cannot see it from inside.
Now, maybe this is the case with our regular numbers -- they are the same in number, but it is impossible for us to see. But the longer one think about this problem, the less sense the question makes. The simplest solution is to accept the fact that sets have no real existence whatsoever, that the mathematician does not explore structure of some abstract constructs, but only manipulates the strings on paper in some defined way. This approach is not very romantic, but is the only way I know of escaping from problems and paradoxes brought by Platonic view on reality.
I think one reason I'm so fascinated by certain abstract mathematical concepts (like this one), in addition to certain theoretical physics concepts that prod at the root of how everything works, is in the hope that someday I will come across something that will trigger some new all-encompassing form of understanding inside me like nothing else ever has. Something, but not necessarily, of eternal consequences.
"[...]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.
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.
It's worth noting that ordinal addition and multiplication are not commutative. 1+ω = ω ≠ ω+1
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.
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.
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.
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.
http://en.wikipedia.org/wiki/White_Light_(novel)
I picked this up at a end of line book shop when I was 13 or 14, along with a bunch of other Wired Press books, and it blew my mind.
Yes 0 is 0. I could also describe it as (5 * 4 * 3 * 0), but how does that help?
When you think about it, there is no such thing as infinity. It's just a word and concept used to describe an amount bigger than you're able able to imagine or comprehend. It's something we use because we need to give a name to the "limit" to the far end of a spectrum.
That's of course a silly example, but I hope it gets my point across.
Also, please note the Cantor's theorem [0] -- this bears some relation to programming, as considering subsets of a set is an important problem.
In short, it makes sense to discuss different infinities.
All that may sound purely academic theory, but please remember current cryptography grew from what once seemed to be just purely academic theory.
----
You said that there is no such thing as infinity, and then you say that it describes a concept. All words describe concepts, don't they? Similarly, I could say, "there is no such thing as node.js, it is just a word and concept we use to describe an event-driven I/O framework for the V8 JavaScript engine on Unix-like platforms". It proves absolutely nothing.
As for the significance of those differences: I can think about two areas where this is fundamental (but there are many more). First, the natural numbers (0, 1, ...) vs rationals vs real numbers is really big in terms of "how many" numbers you have. You can prove than the set of natural numbers and the set of rational numbers is roughy the same size (they are both countable). Now, as you may know, there are some irrational numbers, like square root (2), pi, e, etc... But how many ? The answer is "many more than rationals". One way to define the real numbers (rationals + irrationals) is as limits of a set of rational numbers - i.e. for any real number, you can find a set of rationals which get arbitrarily close to an irrational (we say that rational numbers are dense for the set of real numbers).
Another field where you see the difference: topology vs probability. Roughly speaking, probability is a function which for a set gives you a number between 0 and 1. The key property of probability is that P(A U B U ....) = P(A) + P(B) + ... where A, B, ... are disjoint sets. Another way to look at it is that probability is a special case of the notion of set measure, which is the mathematical way of talking about volume, length, etc... There is a key restriction when defining measure, that is you cannot take arbitrary unions of sets, like say as many as real numbers - actually, you can prove that you cannot build measures if you want arbitrary (uncoutable) unions. This is a naive way to describe the Banach-Tarski paradox, which says that you can split a ball into two new balls which are identitical to the original one.