|Programmer's Guide To Theory - Aleph Zero The First Transfinite|
|Monday, 28 September 2020|
Page 2 of 2
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.
Aleph-null bottles of beer on the wall,
In book but not in this extract:
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Monday, 28 September 2020 )|