Aleph-One and Beyond

The size of the real numbers is called aleph-one and it is the size of the continuum – that model of space where between each point there is not only another point but an infinity of points. Aleph-zero is the sort of infinity we usually denote by ∞ and so aleph-one is bigger than our standard sort of countable infinity. This all seems a little shocking - we now have two infinities.

You can show that aleph-one behaves in the same way as aleph-zero in the sense that you can take any lots of elements away, even aleph-one elements, and there are still aleph-one elements left. After the previous discussion, you can also see why the reals are not effectively enumerable and lead to a new order of infinity – they need two infinite loops. Of course, the problem with these loops is that the inner loop never ends so the outer one never gets to step on to the next real number in the enumeration.

This raises the question of what we did to get from aleph-zero to aleph-one and can we repeat it to get to aleph-two? The answer is yes. If two sets A and B are aleph-zero in size then we already know that all of the usual set operations A U B, i.e. set A union B, is everything in both sets – often said as an infinity plus an infinity is the same infinity - and A X B all of the pairs obtained by taking one from A and one from B (the Cartesian product) for example also have aleph-zero elements. However, there is another operation that we haven't considered - the power set.

If you have a set of elements A, then the power set of A, usually written 2^A, is the set of all subsets of A including the empty set and A. So if A={a,b} the power set is {0,{a},{b}, A}. You can see why it is called the power set as a set with two things in it gives rise to a power set with four things, i.e. 2²=4. This is generally true and if A has n elements its power set has 2ⁿ elements. Notice that this is a much bigger increase than other set operations, i.e A U A has 2n elements and A X A has n² elements.

The power set really does seem to change gear on the increase in the number of elements. So much so that if A has aleph-zero elements then it can be proved that 2^A, i.e. the power set, has aleph-one elements. And, yes, if A has aleph-one elements its power set has aleph-two elements, and so on.

• In general if A has aleph-n elements, the power set 2^A has aleph-(n+1) elements. There is an infinity of orders of infinity.

Notice also that the reals, R, are related to the power set of the integers, just as the rationals, Q, are related to the Cartesian product of the integers, i.e. R=2^Z and Q=Z X Z with suitable definitions and technical adjustments.

The set of alephs is called the transfinite numbers and it is said that this is what sent Cantor crazy but you should be able to see that it is perfectly logical and there is no madness within.

So finally, are there aleph-zero, i.e. a countable infinity, of transfinite numbers or are there more? The answer is we don't know and it all hinges on the answer to the question "is there a set with an order of infinity between aleph-zero and aleph-one".

That there isn't is the so-called continuum hypothesis, and it forms Hilbert's 23rd problem and here we get into some very deep mathematics and an area of active research.

In book but not in this extract:

• Not Enough Programs!
• Not Enough Formulas!
• Transcendental and Algebraic Irrationals
• π - 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
   Extract 2: Turing Thinking ***NEW!
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
    Part II Bits, Codes and Logic
11. Information Theory 
12. 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

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