Comparing Size

The basic idea of the size of something is that if two sets are the same size then we can put them into one-to-one correspondence. Clearly if this is the case then the two sets are of the same size as there can't be any "things" hiding in one set that make it bigger than the other set.

This definition seems innocent enough, and it is, but you have to trust it and the conclusions you reach when you use it to compare infinite sets. For example, suppose you take the set Z of all integers then this is clearly an infinite set. Now take the set O of all the odd integers - this set clearly has half the number of things in it.

But wait - if you set up the 1:1 correspondence between O and Z such that each n in O is associated with 2n in Z, we have to conclude that O and Z have the same number of elements - they are both sets with an infinity of elements.

This is the source of the reasonably well-known story featuring Hotel Hilbert named in honor of German mathematician, David Hilbert. The hotel has an infinite number of rooms and on this night they are all full when a tour bus arrives with n new guests. The passengers are accommodated by the simple rule that the existing guest in room m moves to room m+n - thus clearing the first n rooms. If n were 10 then the person in room 1 would move to room 11, room 2 to room 12 and so on. Notice that in this case the pigeon hole principle doesn’t apply. For a finite number of rooms n say putting m>n people into the rooms would imply that at least one room held two or more people. This is not the case if n is infinite as we can make more space.

From a programmers point of view the question really is “how long do the new guests wait before moving into their rooms?” If the move is made simultaneously then all guests come out into the corridor in one time step and move to their new room at time step two. The new guests then move into their new accommodation in one more time step. So the move is completed in finite time. However, if the algorithm is to move guests one per time step you can see that the move will never be completed in finite time because the guest in room 1 would have to wait for the guest in room 1+n to move into room 2+n and so on. It takes infinite time to move infinite guests one guest at a time.

Suppose a coach carrying an infinite number of new guests arrives? Can they be accommodated? Yes, but in this case the move is from room n to room 2n. This frees all odd number rooms and there is an infinity of these. Once again if this is performed simultaneously it takes finite time but if the move is one guest at a time it takes infinity to complete.

What about Hotel Hilbert with a finite but unbounded number of rooms?

In this case when a finite number of new guests appear the same move occurs but now we have to add n rooms to the hotel. Ok this might take a few months but the new guests are accommodated in finite time even if the current guests move one at a time. Finite but unbounded is much more reasonable. This argument also works if a finite but unbounded number of new guests appear. Things only go wrong when the coach turn up with an infinite number of guests. In this case it really does take infinity to build the new rooms – a task that is practically speaking never completed.

In short, you can add or subtract any number from an infinite set and you still have an infinite number, even if the number added or subtracted is infinite. Put more formally, the union of a finite or infinite number of infinite sets is still infinite.

My favorite expression of this fact is:

Aleph-null bottles of beer on the wall,
Aleph-null bottles of beer,
You take one down, and pass it around,
Aleph-null bottles of beer on the wall.

In book but not in this extract:

• In Search of Aleph-One
• What Is Bigger Than Aleph-Zero?
• Finite But Unbounded “Irrationals”
• Enumerations
• Enumerating the Irrationals
• Aleph-One and Beyond
• Not Enough Programs!
• Not Enough Formulas!
• π - the Special Transcendental

Summary

• There is a hierarchy of number types starting from the counting numbers, expanding to the integers, the rationals, the irrationals and finally the complex numbers. Each expansion is due to the need to solve valid equations in the number type that doesn’t have a solution in the number type.

• The two sets are the same size if it is possible to match elements up one to one.

• The size of the set of integers – the usual meaning of infinity – is aleph-zero. The rationals can be put into one to one correspondence with the integers and so there are aleph-zero rationals.

• To find a set with more elements than aleph-zero you need to move to the irrationals. The irrationals cannot be enumerated and there are aleph-one of them.

• The union of any sets of size aleph-zero is a set of size aleph-zero. The Cartesian product of sets of size aleph-zero is a set of size aleph-zero. It is only when you take the power set 2^A do we get a set of size aleph-one.

• The number of programs or equivalent Turing machines is aleph-zero. Therefore there are not enough programs to compute all of the irrationals – the majority are therefore non-computable numbers.

• Similarly there are not enough formulas for all the irrationals and in this sense they are beyond the reach of mathematics.

• The irrationals that are roots of polynomials are called algebraic. However, as there are only aleph-zero polynomials, most of the irrationals are not the roots of polynomials and these are called transcendental.

• The majority of transcendentals are non-computable but some, including numbers like π, are not only computable, but seem to be very easy to compute.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice 
9. Gödel’s Incompleteness Theorem
10. Lambda Calculus ***NEW!
    Part II Bits, Codes and Logic
11. Information Theory 
12. Coding Theory – Splitting the Bit
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info