Many of us have a sense for physical units like 750 mL, 12 ounces, or a six-pack. But what does it mean to have an infinite size?

The math is fascinating. Perhaps the most remarkable result is that infinity is not a single size. One can talk intelligently about different sizes or types of infinity. This was first and famously demonstrated by Georg Cantor in the late 1800s, in work that laid groundwork for the field of set theory.

Set theory is one of my favorite subjects, but perhaps it is not for everyone. Luckily there is another way to approach infinity because of a new proof using game theory.

What is the size of a set of objects?

Size is the most basic property of a set. It is the number of objects in a set. We refer to the size of a set when we say things like “there are 5 people in front of me” or “a theater has 200 seats.”

Sometimes we do not care about absolute size but instead comparative size. For instance, in an election, it is most important to know which candidate gets more votes. What we usually do is count the number of votes for each side and then make a comparison.

But amazingly we don’t have to count to compare the size of two things. My favorite set theory textbook has the explanation of why:

To see how this is done, consider the problem of determining whether the set of all patrons of some theater performance has the same number of elements as the set of all seats. To find the answer, the ushers need not count the patrons or the seats. It is enough if they check that each patron sits in one, and only one seat, and each set is occupied by one, and only one, theatergoer.

In essence, comparing size is equivalent to the process of pairing elements. If elements from two sets pair up exactly one-for-one, then the sets are the same size. If one set has unpaired elements (say unfilled seats), then it is bigger.

This is common sense when dealing with finite sets, but things get nuanced and defy physical logic when we analyze infinite sets.

Countably infinite

The numbers we count with (the set of numbers {1, 2, 3, …}) are called natural numbers. The set keeps on going forever and so there are an infinite number of elements. Because we can “count” how many objects are in the set, the set’s size is described as being countably infinite.

How do other sets compare in size? The surprising part is that many sets are also countably infinite, even though they would first appear to be smaller or larger. We have to use the pairing process and not our intuition to decide the size.

For instance, consider the set of numbers {2, 3, 4, …}, that is, the natural numbers except for 1. Though this set has one element missing, it is in fact the same size as the natural numbers. The reason is it can be paired up exactly one-for-one with the natural numbers. Every number n from the natural numbers gets paired with the number n + 1 from this new set. Since both sets keep going on indefinitely, the pairing is proper and works. Hence the new set, though seemingly smaller, is also countably infinite.

The result can be hard to swallow in a physical sense. Imagine an infinite theater with seats labeled with the natural numbers that is originally full with people. The set {2, 3, 4, …} can be thought of physically as the seating arrangement of people if we asked the first person to leave the theater and then asked everyone to move back one seat. The theater would somehow still be full despite losing one person. And even more strange is that if the first person returns, we could clear the first seat by asking everyone to move up one seat.

One mathematician, Hilbert, presented many other similar paradoxes of the infinite. He used an infinite hotel and so such problems fall under Hilbert’s Hotel paradox.

The physical analogies make the math seem absurd, but in fact everything is sound and well-derived. So I keep myself straight by thinking about things as abstract pairings.

Other sets are also countably infinite, even though they too seem to be of different size. The even numbers are exactly the same size as the natural numbers, as each number n can be paired with 2n. Similarly, the odd numbers are countably infinite, and so is any infinite subset of the natural numbers, like the prime numbers.

Amazingly the set of rational numbers–the fractions of natural numbers (and their negatives)–is also countably infinite. Here is one illustration of how you can “count” the fractions.

At this point every set we have come up with is countably infinite. So it’s worth asking: are there any sets bigger? It turns out there are bigger sets that are “uncountably” infinite. This is where the game theory proof comes in.

Game theory: proof of the uncountably infinite

I’ll summarize the proof below.

The game involves two-players, Alice and Bob, picking numbers on the interval [0,1]—the set of real numbers (all the decimals) between the numbers 0 and 1. Here are the rules:

1. Alice initially picks some subset S of the interval [0,1].
2. Alice starts the game by picking a number a₁ between 0 and 1.
3. Bob then picks a number b₁ bigger than Alice’s choice a₁ but less than 1.
4. Alice then picks a number a₂ bigger than her previous choice a₁ but less than Bob’s previous choice b₁.
5. In general, Alice and Bob alternate picking numbers between the two previous numbers played. That is, on turn n Alice has to pick a number a_n such that a_n-1 < a_n < b_n-1 and Bob has to pick a number b_n such that a_n < b_n < b_n-1.
6. A famous theorem guarantees that the sequence of numbers a₁, a₂, … converges to a number. Call this number X.
7. If X is in the set S, then Alice wins. Otherwise Bob wins.

The proof that [0,1] is uncountably infinite

The above proof has three parts:

1. If S is countably infinite, then Bob has a winning strategy.
2. Alice can always win the game.
3. The set [0,1] is uncountable.

Here are the details on the individual steps.

1. If S is countably infinite, then Bob has a winning strategy.

Imagine the set S is countably infinite. Then the set can be enumerated as s₁, s₂, and so on (like seats in an infinite theater). It turns out Bob can always make sure that the sequence does not converge to any of these values. That is, Bob can make sure X does not equal any s_n.

Here’s the strategy: on turn n, Bob picks s_n if it is a legal move, and otherwise picks anything. This will guarantee it.

Why? If Bob does get to pick s_n, then he forces the remaining numbers to be smaller than s_n so the sequence cannot converge to s_n.

On the other hand, if Bob cannot pick s_n, then he can pick any legal move. The only reason Bob could not pick s_n is if Alice has already picked a number higher than s_n. Accordingly, the remaining numbers picked in the game will be larger than s_n so the sequence would converge a number larger than s_n. Thus Bob can just pick any allowable number on this turn and continue.

Bob can continue this strategy to make sure that the sequence never converges to any element of S. This means X would not be in S and Bob would win. In summary, if S is countably infinite, Bob can always win the game.

Unfortunately, the odds are stacked against Bob.

2. Alice can always win the game.

Alice can pick S to be any subset of the interval [0,1]. This means Alice can pick the entire subset [0,1]–cheap, yes, but effective. Since Alice and Bob are always picking numbers between 0 and 1, the sequence must converge in the interval. Hence Alice can always win the game.

3. The set [0,1] is uncountably infinite.

This follows directly! By point 1, if [0,1] were countably infinite, then Bob could win the game. But by point 2 he cannot win, and therefore the set [0,1] must be larger and uncountably infinite.

Crashing's are violent and violent are the crashes,
Oh pity, the fragile canoe in she.
Undone was she by his and outclassed was her's by him.
Ragged out and torn apart was her feminine dignities, by the brutality in his filthy canine.
Alas!,doomed are her dreams and damned are her zeals, Her life,now a trod. So,
Get up, all you motherly angels-Fight this deadly act,
Egress forth thy anger, leathalize thy endurance-butcher out this bastardly bastardy with utmost gut and Courage!

Prompted at Acrostic Only

Prompted at NaiSaiKu Challenge..

Ahem!. Well, I know that there’s some brickbats in store for me today..:P. This is my second math misery this week [Lolz!]. But, yeah- all said; I still feel that this one is pretty lucid and perhaps a bit spicy too- Thus paving a pathway for a nice rapot!.

Coming to the theme, I always wondered as to why probability of success could not be calculated. Now, let me explain- Last week I installed some utterly crap symbian s60v2 game on to my N72, it had these so called real-life congruent-mirror-technology behind it; The aim of the game was to help a “person”[who happens to be the hero of the game!] achieve his expectations; If the explanation sounded drifting, I’ll sneak in an example scenario here, Its like if the “person” “expects” to win the Wimbledon grand slam, you need to make him achieve that!.

Initially I felt that the game had a lot of logical fallacies and some “pot holes” of horribly blatant blunders. But after the first round of novical play- I felt that this had a very high content of rich mathematics involved- Yes! Some really cool and interesting probabilistic approaches were on cards. So, as usual (jobless me)- I started musing about this, and to my amaze – the ideas started flowing at some extra-ordinary speed, my pipe-line was overflowing, yet the processor was stable and making some fabulous round of computations. And when it all ended after a mano-man of about 60minutes, I was done. And what I ended up formulating was the success probability of a person X in the Universe of Discourse. Here’s some insight into it---

Let's apply the notion of mathematical expectation to the example of a novice player seeking admittance to a tennis club. To be admitted, the fellow had to beat in two successive games members G (good) and T (top) of the club. With probabilities g and t (t < g) of winning against G and T, the fellow had to choose between to possible orders of games: GTG or TGT. Paradoxically, the second choice appeared to be preferable gaining the fellow the membership with the probability gt(2 - t) against the smaller gt(2 - g) for the sequence GTG.
We shall be looking for the expected number of wins. Using L for a loss and W for a win for the aspiring novice, we shall consider two sample spaces. Following the havils, the space consists of 8 possible outcomes of a sequence of three games:

LLL, LLW, LWL, LWW, WLL, WLW, WWL, WWW

However note that in the sequences LLL, LLW, WLL, WLW the third game is superfluous as the result of the first two make it impossible for the fellow to win two successive games, whereas the third game is unnecessary in the last two sequences WWL, WWW because the two first wins already gain the fellow admittance to the club. This makes possible and reasonable to consider a smaller sample space:

LL, LWL, LWW, WL, WW

For the sequence TGT we have the following probabilities:

Win/Loss sequence Probability

LLL (1 - t)(1 - g)(1 - t)
LLW (1 - t)(1 - g)t
LWL (1 - t)g(1 - t)
LWW (1 - t)gt
WLL t(1 - g)(1 - t)
WLW t(1 - g)t
WWL tg(1 - t)
WWW tgt

for the first sample space and


Win/Loss sequence Probability
LL (1 - t)(1 - g)
LWL (1 - t)g(1 - t)
LWW (1 - t)gt
WL t(1 - g)
WW tg

for the second. In both cases, the probabilities add up to 1, as required. Choosing the easier way out, we verify this only for the latter:

(1 - t)(1 - g) + (1 - t)g(1 - t) + (1 - t)gt + t(1 - g) + tg
= (1 - t)(1 - g) + [(1 - t)g(1 - t) + (1 - t)gt] + t(1 - g) + tg
= (1 - t)(1 - g) + (1 - t)g + t(1 - g) + tg
= [(1 - t)(1 - g) + t(1 - g)] + [(1 - t)g + tg]
= (1 - g) + g
= 1.
Now we introduce the random variable N that denotes the number of wins for the candidate. In the first case, N may be 0, 1, 2, or 3; in the second case, the are only three possible values: 0, 1,2.

The expectations E1 and E2 are
E1(N, TGT) = 0•(1 - t)(1 - g)(1 - t)
+ 1•(1 - t)(1 - g)t
+ 1•(1 - t)g(1 - t)
+ 2•(1 - t)gt
+ 1•t(1 - g)(1 - t)
+ 2•t(1 - g)t
+ 2•tg(1 - t)
+ 3•tgt
= 2t + g

and, correspondingly,
E2(N, TGT) = 0•(1 - t)(1 - g)
+ 1•(1 - t)g(1 - t)
+ 2•(1 - t)gt
+ 1•t(1 - g)
+ 2•tg
= t + g + tg - t2g.

Similarly,
E1(N, GTG) = t + 2g and
E2(N, GTG) = t + g + tg - tg2.

Since t < g, we see that

E1(N, TGT) < E1(N, GTG),

as expected (pun intended). We also have

E2(N, TGT) < E2(N, GTG),

which ameliorates the paradoxical situation that arose from the pure count of probabilities. Although, the probability of gaining the membership playing the top guy first is larger then when playing first just a good member, the expected number of the wins is greater when postponing the confrontation with the top player.

So whats astounding is that the player can actually have very high expectations of wining the tourney. Wow!, I was stunned!!- I have heard people bog down since they are under-dogs and few other yombering around saying that they have no chance what so ever of achieving their goals. Now, all you people out there, read this mathematical snippet and get inspired to conquer the world!. Your chances are not meager by any means, its just that you need to apply things and have a solidiifed state of mind!. Lolz and talking about solidification, I hope to follow this up with some proof for the same along Chemistry of Human Physical Biology..:P

But, till then- Hold your breath and say Sigh!- I can also beat Federer!(Ok, girls and more pontificially ladies you can use Ana Ivanovic too! :P)