Numbering Systems Numbering Systems
and Infinity and Infinity
Moreno Marzolla
Dip. di Informatica—Scienza e Ingegneria (DISI) Università di Bologna
http://www.moreno.marzolla.name/
Copyright © 2014, Moreno Marzolla, Università di Bologna, Italy (http://www.moreno.marzolla.name/teaching/CS2013/)
This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 License (CC-BY-SA). To view a copy of this license, visit http://creativecommons.org/licenses/by- sa/3.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San
Francisco, California, 94105, USA.
Image credits: the Web; The Computational Beauty of Nature website http://mitpress.mit.edu/sites/default/files/titles/content/cbnhtml/home.html
Summary
●
Infinity plays an important role in several topics we will
address (e.g., fractals), therefore it is appropriate that
we give a closer look at it
Zeno's Paradox
●
Achille runs 1 Km in 1 min
●
The Tortoise runs 1 / 2 Km in 1 min
●
The Tortoise is given 1Km advantage
– After 1 min, the Tortoise is 1 / 2 Km ahead
– After 1 / 2 min the Tortoise is 1 / 4 Km ahead
– After 1 / 4 min the Tortoise is 1 / 8 Km ahead
●
The Tortoise is always ahead
of Achille !?
Enter Infinity
●
To reach the Tortoise, Achille needs to run for
●
We now know that this sum of infinite elements is indeed finite!
1+ 1
2 + 1
4 + 1
8 +…
1 1/2
1/4 1/8 1/16
∑
i=0∞a
i= 1−a 1 , if 0<a<1
...
Counting numbers: naturals
●
There are infinitely many natural numbers (1, 2, 3, …)
– Even naturals (2, 4, 6, …) are a proper subset of naturals...
– ...so there seem to be less even numbers than natural numbers, right?
●
Wrong!!
– There are as many naturals as there are even naturals
1 2 3 4 5 6 7 8 9 10 11 12 ...
1
2 4 6 8 10 12
2 3 4 5 6
The Extraordinary Hotel
●
The Extraordinary Hotel or the Thousand and First Journey of Ion the Quiet
– Attributed to Stanislaw Lem, but probably written by the russian mathematician Naum Yakovlevich Vilenkin
●
You are the director of an hotel with (countably)
infinitely many rooms {1, 2, 3, ...}
The Extraordinary Hotel
●
The hotel is fully booked, i.e., all rooms are already occupied by a guest
●
A new guest arrives. What should you do?
1 2 3 4 5 6 7 8 ...
g
Hotel (infinitely many rooms, fully booked)
New guest
The Extraordinary Hotel
●
Again, the hotel is fully booked.
●
Now, (countably) infinitely many new guests arrive at the same time. What should you do?
1 2 3 4 5 6 7 8 ...
Hotel (infinitely many rooms, fully booked)
Infinitely many new guests g4
... g3 g2 g1
Complex Systems 10
The Extraordinary Hotel
●
Suppose that there are infinitely many hotels, each with infinitely many rooms.
●
All hotels are fully booked, but all of them (except for one) have to be closed down for restructuring. The one hotel which is not to be closed is empty.
●
Therefore, you should try to fit infinitely many guests from infinitely many hotels into a single (infinite) hotel.
What should you do?
1 2 3 4 5 6 7 8 ...
Hotel (infinitely many rooms, empty)
g1,4
... g1,3 g1,2 g1,1
g2,4
... g2,3 g2,2 g2,1
Counting numbers: rationals
●
(Positive) rational numbers are those of the form p / q, with p, q naturals
●
The set of rational
numbers if countable, and therefore we can define a one-to-one mapping from the set of naturals
– Therefore, there are as many natural numbers as there are rationals
1/1
1/2 2/2
1/3 2/3 3/3
1/4 2/4 3/4 4/4
1/5 2/5 3/5 4/5 5/5
1/6 2/6 3/6 4/6 5/6 6/6
...
Rationals
●
There are infinitely many rationals between any two rational numbers (p / q) < (r / s) (p, q, r, s integers)
– Proof: (p/q + r/s) / 2 = (sp + rq) / 2qs is a rational number between p/q and r/s
●
A single rational number can be used to encode the whole content of the RAM of your PC!
– Proof: the content of the memory of your PC is just a very long but finite sequence of 0 and 1, e.g.,
0110100100101010. Write the sequence as
0.0110100100101010 and you have a rational number encoding the whole value.
Counting numbers: irrationals
●
Irrational numbers are those who can not be expressed as p / q
– They have infinite, nonperiodic decimal representation
●
The set of irrationals is not countable
– Therefore, there are more irrational numbers than rational (and natural) numbers
x11 x12 x13 x14 x15 0.
x21 x22 x23 x24 x25 0.
x31 x32 x33 x34 x35 0.
x41 x42 x43 x44 x45 0.
0. ...
Counting numbers: reals
●
Consider a closed interval I = [a, b], and the open half- infinite interval J = [0, +∞). Are there more real
numbers in J than I?
Counting numbers: reals
●
Consider a closed interval I = [a, b], and the open half- infinite interval J = [0, +∞). Are there more real
numbers in J than I?
●
Answer: both contain the same (infinite) quantity of
real numbers
Conclusions
●
Natural numbers occupy fixed and equally-spaced positions on the real line
●
There are “as many” natural numbers as there are rational numbers
●
Yet, between any two naturals there are infinitely many rationals
●
There are “more” real numbers than rational (or natural) numbers
●
