Programmer's Guide To Theory - Aleph Zero The First Transfinite
Monday, 28 September 2020
Article Index
Programmer's Guide To Theory - Aleph Zero The First Transfinite
Comparing Size

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.


Aleph0

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 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
  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 ***NEW!
  7. Kolmogorov Complexity and Randomness
    Extract 1:Kolmogorov Complexity 
  8. Algorithm of Choice
  9. Gödel’s Incompleteness Theorem
  10. Lambda Calculus
    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?
  16. Extract 1: Where Do The Big Os Come From 
  17. Recursion
    Extract 1: Why Recursion
  18. NP Versus P Algorithms
    Extract 1: NP & Co-NP 
  19. 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


RubyMine Adds Ruby3 RBS Support
19/04/2021

RubyMine 2021.1 has been released with improvements including Ruby 3.0 RBS support and better code completion. Other improvements include space integration and the inclusion of Code With Me.



Computer Comes First In Crossword Competition
02/05/2021

After more than a decade of competing in the annual American Crossword Puzzle Tournament, Dr. Fill, a computer program devised by Matt Ginsberg came at the top of the rankings. It convincingly be [ ... ]


More News

square

 



 

Comments




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


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
  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 ***NEW!
  7. Kolmogorov Complexity and Randomness
    Extract 1:Kolmogorov Complexity 
  8. Algorithm of Choice
  9. Gödel’s Incompleteness Theorem
  10. Lambda Calculus
    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?
  16. Extract 1: Where Do The Big Os Come From 
  17. Recursion
    Extract 1: Why Recursion
  18. NP Versus P Algorithms
    Extract 1: NP & Co-NP 
  19. Extract 2: NP Complete 

<ASIN:1871962439>

<ASIN:1871962587>




Last Updated ( Monday, 28 September 2020 )