Infinity comes in many different sizes.
Yes, it’s true. Get over it.
Or at least, let’s think about why it so difficult to get over it.
After all, nobody is particularly
bothered when I say “Numbers come in many sizes”.
I suspect the reason is that when people
hear “Infinity” they think of the
Poetic
Definition: Infinity is
the Ultimate Maximum
This notion of Infinity as the Absolute, the Whole, “Something greater than which nothing can be conceived” has a long history in human culture.
Notions of the Infinite are frequently associated with a Supreme Being.
Viewed in this light, the idea of
different sizes of infinity is indeed very confusing.
How can there be a larger or smaller
Ultimate Maximum?
The scientific study of infinity – a
branch of mathematics known as Set Theory – begins by descending from the lofty
heights of the Absolute and starts with a
Prosaic
Definition: An infinite
set is a collection of objects that does not end
Viewed in this light, different sizes of
infinity suddenly look more plausible.
For instance, consider the collections
{0, 1, 2, 3, 4, 5 ...} and {2, 3, 4, 5, …}
Both never end, but the latter has two
fewer members than the former.
Now if you look at {3, 5, 7, 9,….} (the
odd numbers greater than 1), this has infinitely fewer members than both the above.
Surely it is conceivable that, while all
three sets above are infinite, they have different sizes -
just like the numbers 5, 17 and 5000 are
all bigger than 2, but different from each other?
But how can we be sure ?
Let’s start at the very beginning – with
the idea of a Set.
The Joy of Sets
A set is a collection of objects. (Some
technical conditions apply but they can wait.)
We take the objects belonging to the
collection and put curly brackets around them.
{1, 2, 3} is a set. So is {a, b, c} or {Jack,
Jill}.
The objects belonging to a set are called
its members.
1 is a member of {1, 2, 3} and b is a
member of {a, b, c}, but 1 is not a member of {a, b, c} and vice versa.
Of particular interest to us will be N, the set of positive integers (called
“Natural Numbers” by mathematicians).
N = {0, 1, 2, 3, 4,….} is an example of an infinite set, as opposed to the other sets we saw above which are finite.
Once you have a few sets in hand, you can
more sets out of them, using a couple of operations.
Union: Given two sets A and B, their union A ∪ B, consists of all the
members that belong to A or to B.
So, if A = {1, 2, 3} and B = {2, 4, 6},
then A ∪ B = {1, 2, 3, 4, 6}
Using this idea repeatedly, you can
define the union of any number of sets or even an infinite number of sets.
So, for instance, if A1 = {0},
A2 = {0, 1}, A3 = {0, 1, 2} and so on, we can take the
union of all the sets to get A1 ∪ A2 ∪ A3 ∪ ... = {0,1, 2, 3, 4, ….} =
Our old friend N
Intersection: Given
two sets A and B, their intersection A ∩ B, consists of all the
members which belong to both A and B
So, if A = {1, 2, 3} and B = {2, 4, 6},
then A ∩ B = {2}
What if A and B have nothing in common? Let’s say if A = {1, 2, 3} and B = {4, 5, 6}?
Well, in that case, A ∩ B is defined to be the Empty
Set, which contains nothing at all.
The Empty Set is denoted by { }, (there’s
nothing inside the brackets) or the letter ∅
Just like unions, you can also talk about
the intersection of infinitely many sets, although we won’t make much use of
them in this post.
Subsets: A set A is said to be a subset of another set B, if every member of the set A also belongs
to B.
So for instance {2} and {2, 6} are both
subsets of B ={2, 4, 6}.
But {2, 5} is not.
Two important things to note:
-
Any
set is a subset of itself. So {2, 4, 6} is a subset of {2, 4, 6}. (Check that
the definition is satisfied!)
-
The
Empty Set, { }, is always a subset of every set.
These last two facts often confuse
newbies to set theory, but here’s a way to think about it:
To generate a subset of a given set – go
through every member of the set, one by one, and make a decision about whether
to include that member or not.
Every
possible set of decisions corresponds to a valid subset.
So, if A = {3, 4, 5}, you could decide to
include only the first member and exclude the rest.
This gives you the subset {3}.
If you decide to include the first two
and exclude the third, you get {3, 4}
If you decide to include all the members, that gives you the set
A.
If you decide to include none, you get the empty set.
Exercise 1: If a set, A, has n members, show that
there are 2n possible subsets of A
With subsets under our belt, we come to a
crucial concept for studying infinity.
Firstly, note that a set can have other sets as its members.
So, for instance: A = { {1, 2} , {3, 4,
5}, {a, b} } is a set.
Note that {1, 2} and {a,b} are members of A. But { {1,2}, {a,b}} is a subset of A.
However, {1, 2, 5} is not a member of A. (Neither is it
a subset)
Now, are ready to define:
Power Set: The power set of a set A is the set P(A)
consisting of all subsets of A.
Best to illustrate this by example:
If A = {1, 2, 3}, the power set of A is
given by:
P(A) = { { }, {1}, {2}, {3}, {1, 2}, {1,
3}, {2, 3}, {1, 2, 3} }
(Note carefully the placement of curly
brackets and commas)
Exercise 2:
(easy) If A has n members, show that P(A)
has 2n members
(harder) If A = {1, 2}, write down P(
P(A) ) (“power set of power set of A”)
Note that everything we are doing can be
defined for an infinite set like N.
The power set of N will consist of finite subsets like {3, 5, 7} and well as
infinite subsets like
{All the odd numbers}
So, what’s all this got to do with
different sizes of infinity?
Well, the language of sets allows us to
define sizes of sets – finite or
infinite – in a very precise way.
In fancy math-speak, the word used for
“size” is “cardinality”, but we’ll
stick with “size”
Sizing Things Up
Imagine you have forgotten how to count.
Is there any way for you to distinguish
the size of two different sets ?
For instance, is there any way for you to
recognize and convey the fact that {1, 2, 3} has just as many members as {a, b,
c}, but fewer members than {a, b, c, d, e} ?
Turns out that there is.
In fact, this is how pretty much
everybody learns to count but then forgets !
It’s the very basic idea of pairing things up.
The idea is, given two sets A and B, I
will try to pair up every member of A with some member of B - with the
stipulation that different members of A
must be paired with different members of B.
In what follows, I will use the notation
“x -> y” as shorthand for “x is paired with y”
So, if A = {1, 2, 3} and B = {a, b, c},
then: 1 –> a, 2 –> b, 3 –> c is
a valid pairing.
So is: 1 –> b, 2 –> c, 3 –> a.
But: 1 –> a, 2 –> a, 3 –> b is
invalid because 1 and 2 are both paired with a.
But if we took, B ={a, b, c, d, e}
instead, then 1 –> a, 2 –> b, 3 –> c or 1 –> b, 2 –> d, 3 –>
e are both valid ways of pairing all members of A with some members of B (there
are many other ways).
The crucial difference, is that, every member of B = {a, b, c} ended up
getting paired with some member of
{1, 2, 3} but when we took B ={a, b, c, d, e}
instead, then however you try to pair things up, you always end up missing some members of B.
Hence, even without knowing how to count,
one can compare sizes of sets, in a way which matches perfectly with our
intuition of one set having “more things in it” than another one.
Let’s make this official.
Let’s make this official.
Definition 2: Given two sets A and B, we say A = B (A
and B have the same size), if there is some
way of pairing up all members all members
of A with all members of B
Definition 3: Given two sets A and B, we say A < B
(A is smaller than B or B is greater than A) if:
-There is some way of pairing up all members
of A with some members of B (but not
all)
- There is no way of pairing up all members of A with all members of B
Exercise 3: If A is a subset of B, then show that A
≤ B
Notice that proving A = B is relatively
easy because you just have to figure out one
possible way to pair up all the members of the two sets.
Showing that A < B is much trickier. It’s not enough to show some attempt at pairing up the two sets doesn’t work – you need to show that every possible attempt at pairing will fail.
Showing that A < B is much trickier. It’s not enough to show some attempt at pairing up the two sets doesn’t work – you need to show that every possible attempt at pairing will fail.
This requires a good dose of ingenuity as
we shall see later.
So, with these definitions in hand, we
can go ahead and say that {1, 2, 3} ≤ {a, b, c} and
{1, 2, 3} ≤ {a, b, c, d, e}.
Furthermore, {1, 2, 3} = {a, b, c}, but
{1, 2, 3} < {a, b, c, d, e}
“Now this is all very interesting”, you
say, “but the fact is I do know how
to count and I could have told you this much earlier. Why did we take such a
long winded route to this easy conclusion?”
Because
– and this was the great insight of George Cantor, father of Set Theory – this
method of comparing sizes of sets by pairing works perfectly well for infinite
sets, whereas counting fails miserably !!
In another words, we have just managed to
extend the concept of counting from finite to infinite collections.
So, without further ado, allow me to
introduce…
The Smallest Infinity
Let N
= {0, 1, 2, 3, …..}, be the natural numbers. This is the smallest possible
infinite set.
What do I mean by that exactly? Well,
this.
Theorem: For infinite set A, N ≤ A
Proof: Pick any member from A, pair it up with 1.
Now pick up another member, pair it up with 2. Keep going.
Now, if we run out of members to pick up
at the k-th step for some number k, then A had only k members. But that means A
was finite!
So, the process must continue until every
member of N gets paired up with some members of A, but not necessarily all.
Hence, by definition, N ≤ A. □
But are we really sure of this? After all
remember the sets {2, 3, 4, 5,…} and the odd numbers {1, 3, 5, 7,…} ? We had
suspected that these were smaller
than N, but how is that possible if
N is the smallest infinity?
The
answer is that both the sets above have the same size as N.
Look at the pairing 0 -> 2, 1 -> 3,
…., k -> k + 2,….
Convince yourself that using this formula
every single member of {2, 3, 4, 5..} gets paired up with N. Hence they have
the same size.
Similarly, 0 -> 1, 1 ->3, 2 ->
5, …, k -> 2k + 1, …. pairs up N and all the odd numbers.
So, here we have a property of infinite
sets that has absolutely no analogue in the world of the merely finite:
It
is possible to remove members from an infinite set – even infinitely many of
them – and still end with a set of the same size !!
What about the other direction? What if
we add more things to N ?
How about S = {0, 0.5, 1, 1.5, 2, 3, 4,
5, … } where we threw in two more numbers ? Maybe that’s a bigger infinity?
No such luck.
0 -> 0, 1 -> 1.5, 2 -> 1, 3
-> 1.5, 4 -> 2, 5 -> 3, k -> k – 2 for all subsequent numbers k,
and we have paired up N and S with
nothing left over.
In fact, you could have thrown in a
million, a trillion or indeed, any finite
number of extra members to N
without changing its size at all!
Ok, then, let’s get serious.
Let S = {0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5,
…. } (every whole number and whole number + 0.5)
Now we have thrown in infinitely more
things. Could this give something bigger ?
0 -> 0, 1 -> 0.5, 2 -> 1,…., k
-> 0.5k for all numbers k and once again, our hopes are dashed as
everything gets paired up.
It keeps getting worse.
You can add a million sets to N, or a gazillion – each having the
same size as N – and still the size
remains stubbornly unchanged!
In desperation, we go all the way.
Consider an infinite collection of sets, A0, A1, A2
and so on, one for each whole number.
Let
each of these sets be individually as large as N.
The completely stunning – but unequivocal
– answer is:
Just
as large as N, not one bit more!!
At this point, you may legitimately
wonder why we called N the smallest infinity.
Every infinite set which looked like it
might be smaller than N ended up
being the same size.
On the other hand, every attempt to get
something bigger than N failed as well.
Maybe it’s time to call it quits and
admit that there is only one infinity
– the size of the set N.
Not quite.
A Bigger Infinity
Ladies and gentlemen, allow me to
present:
Cantor’s Theorem: Let A be any set, finite or infinite.
Then A < Power set of A
Proof: Let’s explicitly write down what we need
to prove, first.
Let P(A) denote the power set of A.
By definition of A < P(A) we need to
show two things
1) There is some way of pairing up all members
of A with some members of P(A) (but
not all)
2) There is no way of pairing up all members of A with all members of P(A)
To illustrate the ideas, I will use the
set N, but the proof works for
absolutely any set.
Step 1) is easy.
Note that P(A) consists of all possible
subsets of A. In particular, for any member x belonging to A, the set {x}
belongs to P(A). So, simply pair x -> {x} for each x and we are done.
To illustrate using N, we just pair 0 -> {0}, 1 -> {1}, 2 -> {2} and so on….
Step 2) was Cantor’s stroke of genius.
Remember, we need to show that no conceivable pairing will between members
of A and P(A) will work.
So, how do we check through all possible
pairings, especially if there are infinitely many of them ?
We don’t
Instead, we show that no matter what pairing recipe was given to
you to link all members of P(A) and A, it couldn’t possibly have worked.
So, let’s say the World’s Biggest Math
Genius has given you a possible way of pairing them all up.
As per his formula:
-
Every
member x gets paired with some subset of A, which we will call “Pair of x”
-
More
importantly, for any subset of A,
there is some member of A which is paired with this subset.
For any x, look at the subset “Pair of x” as per his formula.
Now ask the question, Does “Pair of x”
contain x?
If the answer is “No”, then include x in
Rogue Subset.
If the answer is “Yes”, then don’t
include x in Rogue Subset.
To illustrate, suppose as per Mr.
Genius’s formula:
0 -> {1, 2, 3}, 1 -> {1, 3, 5, 7,…,
all odd numbers} and 4 -> {1, 6, 11, 13}.
Then, Rogue Subset would include 0 and 4,
but not include 1.
Now take a moment to realize that:
The
Rogue Subset cannot have been paired with any member of A.
How so? Because you intentionally made it that way.
If the subset paired to a member
contained that member then Rogue Subset wouldn’t contain it and vice versa. So,
it is guaranteed that you won’t find
Rogue Subset anywhere on the list of pairs.
Note that this doesn’t depend on any
particular recipe for pairing.
If Mr. Genius realized his mistake and
gave you another pairing recipe, then you would just follow the same procedure
for that recipe and end up with another Rogue Subset.
Every possible attempt is doomed to
failure and this completes Step 2)
This we have shown that A < P(A)
Done !! □
Let’s just take a deep breath and
appreciate the magnitude of what we just proved.
For finite sets, this result is not a big
deal because n < 2n for any number n (Exercise 1).
But the true magic of Cantor’s Theorem
shines through when A is an infinite set.
For at last, we can break through the
tyranny of N and soar upwards to a
provably bigger infinity, the power set of N.
With that small (or is it infinitely large?)
step, our journey has begun.
The Ladder of Infinity
Start by renaming N. Call it I0 – the “zero-th infinity”.
We now know that N < P(N), the power
set of N.
Call that I1
But what worked once, works again. So, P(N) < P(P(N)). Call that I2.
Repeat. Repeat. Repeat again.
What you get is a chain of infinities,
each bigger than the last – I0 < I1 < I2 <
.... < I1000 < …
In other words, not only are there
different sizes of infinity, you get infinitely
many different sizes - one for every
whole number.
(Quick Question: How do we know there are
no infinities between I0 and I1 ?
Leaving already? But we are just getting
started.
Remember how we are allowed to take unions
of sets?
Well then, once we get our infinity of
infinite sets, each bigger than the last, let’s take the union them all !
Look at the Jumbo Set, J = I0 ∪ I1 ∪ I2 ∪ ….∪ ….
J
is a strictly bigger infinite set than all the I’s !!
Why ? Okay, suppose, instead, that J = Ik
for some integer k.
But that can’t be, because J contains all
the members of Ik+1 and Ik < Ik+1
So, Ik < J for all Ik
– in other words, J is bigger than all the I’s.
So, we can think of J as the “infinity-th
infinity”, larger than anything that came before.
Let’s call it Iω
And yes, when this chain gets exhausted,
we take the union once again to get a super jumbo sized infinite set I2ω
Power set, power set, power set, union,
repeat, repeat… – I3ω , I4ω
, I5ω , ….
Union them all and out pops I ω2
Plodding ever onwards, we get I ω3 I ω4 I ω5 ….. Then eventually Iωω
And beyond that as well…
At this point, you may turn around and
ask:
“How many different sizes of infinity are
there? How many rungs on the ladder of infinity?”
Infinitely many, obviously, but now we
have learned to calibrate more finely.
I0 different sizes of infinity
? I1 maybe ? Surely not Iω ?
It can be proved that, in a very well defined sense, there is an I1-th infinity, an I2-th
infinity, an Iω-th infinity, even an Iωω th infinity.
In fact, we can find an infinity - call
it ICrazy – such that ICrazy is the ICrazy th
infinity.
In other words, ICrazy = I ICrazy
That’s crazy ! Yes, I know.
As for your question, the answer is that
there are more rungs on the ladder of infinity than can be counted by any of
the infinities lying on that ladder !
Let’s say that once again - not only are
there different sizes of infinity, there are far, far, far more of them than there are numbers.
In
fact, there are more types of infinity than can be counted by any of the
infinities in our ever increasing ladder.
But what if we joined them all together
and looked at the “Set of all sets” ?
Right away, we have a problem:
Let U be the set of all sets.
From Cantor’s Theorem, we know that U
< P(U)
But by definition, U contains all
sets – which means P(U) is a subset of U.
But then P(U) ≤ U.
Contradiction !
Something has gone seriously wrong. Maybe
it’s time to slow down and take stock of things.
The Universe of Sets
Infinity has traditionally connoted
something mighty and mysterious, possibly beyond human understanding.
But now that we are dealing with
infinities in the plural, it becomes apparent that they behave rather like the
familiar finite (whole) numbers.
Some are bigger than others.
Taking a power set always yields a bigger
infinity, just like adding one always gives a bigger number.
The enormous profusion of infinities,
with entities like Iωω or ICrazy may
be startling, but perhaps no more so than the existence of really large numbers.
It turns out we can even do arithmetic with these infinities – add them up, multiply them, take one infinity
to the power of another and so on.
The fact that there are more different
sizes of infinity than can be counted by any given infinity is precisely
analogous to there being more finite numbers than can be counted by any one
number.
Even the problem we saw with our “Set of
all sets” is very similar to what happens when we talk about the “Biggest
possible number” - adding one should give a bigger number which leads to a
contradiction.
But while it is fairly clear why you
can’t talk about a biggest number, it isn’t quite apparent why we can’t mention
the “set of all sets”.
Isn’t a set just a collection of things ?
So why not the “set of all sets” ?
Remember how I had qualified my
definition of a set with “technical collections apply” ?
It’s time to apply them now.
A set is defined as a collection of things which satisfies a set of rules called the “Zermelo Fraenkel Axioms” – usually abbreviated to ZFC.
A set is defined as a collection of things which satisfies a set of rules called the “Zermelo Fraenkel Axioms” – usually abbreviated to ZFC.
For instance, the ZFC rules say that the
Empty Set is a valid set and taking the power set of a set gives a valid set
(among other things).
However, it so happens that the
“collection of all sets” does not
satisfy ZFC and is therefore not a
set.
So taking its power set and looking at
its size are out of bounds.
Contradiction avoided.
But let’s stick with the analogy just a
little longer.
Once we realize that the finite numbers
never end, it gradually dawns on us that the collection of all finite numbers is not described by some “biggest number”, but
corresponds to something entirely new and incomparably larger.
(Or as your high school teacher would
say, “Infinity is not a number”)
Yes, indeed we can.
What we get is the Universe of Sets.
Associated with the Universe is an
“Infinity beyond all infinities” which Cantor referred to as the Absolute
Infinite.
We are back to the long neglected “poetic
definition” of Infinity – an ultimate maximum which admits nothing larger.
A deeply religious man, Cantor associated
the Absolute Infinite with God – in contrast to the garden variety infinities
we have been discussing, which he called the “transfinite cardinals”
or “transfinite numbers”.
So, at the end of our excursion into the
set theoretic realm, we are left with:
-
The
finite numbers which we all know and love
-
The
transfinite numbers forming our “ladder of infinity”
-
The
Absolute Infinite encompassing and transcending them all
Or maybe we are thinking too small…
Stretching the Universe
Recall that all sets are required to be
in compliance with the ZFC Axioms.
It turns out that all finite sets and the
infinite sets – aka transfinite cardinals – we have seen till now can be
explicitly constructed once we have the ZFC Axioms in place.
For what follows, I’ll call this
collection the “ZFC universe”.
From here onwards, one possible approach
is the
Conservative
View: The universe consists
of all sets which may be constructed from the ZFC Axioms.
In other words, the ZFC universe is everything
you will ever get and you can stop reading now.
Life gets more interesting, however, if
we adopt the
Liberal
View: The universe consists
of all sets which do not contradict the ZFC Axioms.
To see why, we define a set K with the following three properties.
a) I0 < K (where Io is N, our smallest infinity)
b) If a set A < K, then P(A) < K
c) (Union of fewer than K sets which are each smaller than K) < K
So, what’s the big deal ?
For starters, since I0 < K, Property b) implies I1
< K (since I0 = N and I1 = P(N) ).
But repeating the same logic, I2
< K, I3 < K , in fact In < K for every number n.
Now Property c) implies Iω
< K since it is just the unions
of all the In
Then we use Property b) again….
It
turns out that K is at least as
large as the entire ZFC universe !!!
But hang on, didn’t I just say that the
universe of all sets is too large a collection to be a set ?
So am I talking about a set as big as the
universe ?
Can I please make up my mind ?
Well, it all depends on how my mind is made up.
If I take the Conservative stance, then a
monstrous set like K does not exist,
cannot exist.
But if I take the Liberal view, then the
ZFC universe is not “The Universe of All
Sets”, it is merely “the collection
of sets which can be constructed from ZFC” and there is no problem at all with
a set as large as this collection, or
even larger.
With
the introduction of K, we have just stretched
the Universe of sets.
And what a stretch it is!
To begin with, the once-mighty ZFC
universe, which we were about to associate with Absolute Infinity, deflates to
become the Least Inaccessible Cardinal
- K0
And now of course, we can take the power
set of K0, the power set
of the power set, union of all the power sets, all the good old tricks to get a
new ladder of infinities built atop K0
But now we have a new trick up our sleeve
!
Because standing just beyond this new
ladder, we find the next inaccessible cardinal,
K1
And similarly, we get K2 K3 and – yes,
you got it –an infinity of inaccessible cardinals.
And once you got those, triple your fun
by taking the union of them all, then keep going.
Forget the ladder - we are now on the
space elevator of infinity.
As we casually zoom past the inaccessible
cardinals, it is all too easy to forget that the gap between one and the next
is equivalent to the gulf between the smallest infinity I0 and the
entire ZFC universe.
More power sets, more unions, more inaccessibles
– are we stretching the universe of sets to breaking point ?
Not by a very long shot.
Inaccessible cardinals form the bottom
level of the so called Large Cardinal
Hierarchy – the frontier of research in modern set theory.
Inaccessible, Mahlo, weakly compact,
ineffable, measurable, extendible, huge, superhuge… the
chain of Large Cardinals goes on and on.
Each step up the hierarchy is a
gargantuan, mindboggling leap, dwarfing the jump from the smallest infinity
(almost invisible from these heights) to the least inaccessible cardinal and
enlarging the set theoretic universe almost beyond comprehension.
Like ever-frustrated mountaineers, we triumphantly
reach a summit, ready to touch the sky - when the fog rolls back to reveal an
immeasurably higher peak towering overhead and the starry firmament of the
Absolute recedes further than ever.
Does it ever end ? Could it ever end ?
These are, after all, mountains of the
mind, unconstrained by any connection to reality.
What prevents us from spinning out ever
larger cardinals for centuries to come, defining them into existence ad infinitum ?
Answer: The ZFC Axioms.
The only constraint on our “Liberal
worldview” was that our sets should not contradict ZFC.
It turns out that as we climb the large
cardinal hierarchy, we put ever more pressure on the girdle of ZFC – increasing
the possibility of contradiction – until it finally snaps.
Bloated with mathematical hubris, we try
to define a Reinhardt cardinal – an ultimate mountain of infinity that “touches
the Absolute” – and it collapses into inconsistency.
But that is a story for another time.
Sir Please post about Reinhardt cardinal – an ultimate mountain of infinity that “touches the Absolute”.
ReplyDeleteI'll be waiting impatiently.