Levels of Infinity(xamuel.com)
xamuel.com
Levels of Infinity
http://www.xamuel.com/levels-of-infinity/
24 comments
Nice explanation, though I dont see how this leads you into becoming a formalist at the end. That countable models exist for the set theoretic universe, seems like part of the phenonmena of infinite structures having perfect reflections in subsets. This is, of course, much more breathtaking than the more usual facts like the natural numbers having the same cardinality as even numbers since cardinality is transcended and the whole universe collapses into a countable set.
I wonder if others feel the same way:
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.
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.
I think I have similar feelings. The deep reason for me to read about advanced mathematics, theoretical physics and science in general is the hope that one day this accumulated knowledge will let me understand the world we live in in a better way; a hope of getting a framework of thought that allows to experience and do things that previously I couldn't.
Yes, I experienced a significant shift in my worldview when I first learned Goedel's incompleteness theorems.
I first got into transfinite numbers through a book by Rudy Rucker, "Infinity and The Mind." I tried explaining this subject to a Doctoral candidate once, at around 2am - and he accused me of having come off my meds.
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.
"[...]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.
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
It's worth noting that ordinal addition and multiplication are not commutative. 1+ω = ω ≠ ω+1
[deleted]
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.
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.
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 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.
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.
[deleted]
For a fictional, tripped-out exploration of the various levels of infinity, try Rudy Rucker's White Light:
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.
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.
I remember watching Open University program when I was about that age that worked through Cantor's diagonal argument - I vividly remember being spellbound that such a seemingly simple argument could has such a profound and counter intuitive result.
It is a famous anecdote that Cantor was not quite as surprised when he came up with his "diagonal proof" (reals are uncountable) but when he saw that the points on the plane can be mapped to points on the line, i.e. the infinities are the same. There just seems to be more points in R^2 than R, this is highly counterintuitive.
These mathematics seem highly dubious to me. It's like they just found a bunch of different ways to describe the same thing, Infinity.
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.
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.
Those are very conventional mathematics, and most core concepts have been settled for a century now. Cantor in particular paved the way toward a better understanding of many related concepts in that area.
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.
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.
Back at the uni, I was shown a nice proof that one infinity (the (infinite) count of natural numbers) is not the same as another infinity (the count of real numbers, IIRC). Basically, it was shown no mathematical function can be constructed that maps one onto another, IIRC.
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.
----
[0] http://en.wikipedia.org/wiki/Cantor_theorem
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.
----
[0] http://en.wikipedia.org/wiki/Cantor_theorem
> 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.
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.
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.
Well, I'm not a mathematician but I've always thought there were different "strengths" of infinity. Consider for instance that both lim(x -> ∞) x and lim(x -> ∞) x^2 are infinity, however lim(x -> ∞) x / x^2 and lim(x -> ∞) x^2 / x are not the same thing.
That's of course a silly example, but I hope it gets my point across.
That's of course a silly example, but I hope it gets my point across.
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.