Programmer's Guide To Theory - In Search Of Aleph-One
Written by Mike James   
Monday, 25 January 2021
Article Index
Programmer's Guide To Theory - In Search Of Aleph-One
Finite But Unbounded
Aleph-One And Beyond

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 2A, 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. 22=4. This is generally true and if A has n elements its power set has 2n 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 n2 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 2A, 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 2A 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=2Z 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

aleph0aleph1

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 2A 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.

cover600

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.

Banner


The WinterJS Javascript Runtime Is Asking For Your Attention
11/04/2024

WinterJS is a brand new Javascript runtime by Wasmer which comes with the claim that it's the fastest of them all. Let's find out if that holds true.



CISA Offers More Support For Open Source
22/03/2024

The Cybersecurity and Infrastructure Security Agency (CISA) has announced a number of key actions that they hope will improve the open source ecosystem.


More News

raspberry pi books

 

Comments




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



Last Updated ( Monday, 25 January 2021 )