Transcript Estimating Lesson - Indiana University

Cantor’s Diagonal Proof and
Uncountable Numbers:
To Infinity and Beyond!
Donald Byrd
rev. 28 November 2012
Hilbert’s Hotel and Infinite Sets
• Explanation of infinite sets by David Hilbert
• Hotel with finite rooms, all occupied
– Can’t accommodate a new guest
• Hotel with infinite rooms, all occupied
– Can accommodate a new guest
– Move each guest from room n to n+1
• Hotel with infinite rooms, all occupied
– Can accommodate infinite no. of new guests!
– How?
28 Nov. 2012
2
One-to-One Correspondence
• How can you compare size of collections
of things if there are too many to count?
– …for example, infinite collections
• Georg Cantor (1891):
– Put items in each set (collection) in a list
– Try one-to-one correspondence
• There are infinitely many integers, but…
• Cantor proved there are more real nos.!
28 Nov. 2012
3
One-to-One Correspondence between
Infinite Sets (1)
N
--0
1
2
3
4
5
6
8
9
etc.
Even
Numbers
-----------0
2
4
6
8
10
12
14
16
etc.
28 Nov. 2012
Integers
----------0
-1
1
-2
2
-3
3
-4
4
etc.
4
One-to-One Correspondence between
Infinite Sets (2)
N
--0
1
2
3
4
5
6
8
9
etc.
Even
Numbers
-----------0
2
4
6
8
10
12
14
16
etc.
28 Nov. 2012
Integers
----------0
-1
1
-2
2
-3
3
-4
4
etc.
Squares
---------0
1
4
9
16
25
36
49
64
etc.
Positive
Rationals
-----------1
1/2
2/1
1/3
3/1
1/4
2/3
3/2
4/1
etc.
5
“Complete List of Real Numbers”?
1.
.141592653589793238462643383279502884197169399375
10...
2.
.582097494459230781640628620899862803482534211706
79...
3.
.333333333333333333333333333333333333333333333333
33...
4.
.718281828459045235360287471352662497757247093699
95...
5.
.414213562373095048801688724209698078569671875376
94...
6.
.5000000000000000000000000000000000000000000000006
28 Nov. 2012
00...
“Complete List of Real Numbers”?
• Just real numbers between 0 and 1 is enough.
• List might start like this:
1.
.1415926535...
2.
.5820974944...
3.
.3333333333...
4.
.7182818284...
5.
.4142135623...
6.
.5000000000...
7.
.8214808651...
28 Nov. 2012
7
No “Complete List of Real Numbers”!
“Complete List”
1. .1415926535...
2. .5820974944...
3. .3333333333...
4. .7182818284...
5. .4142135623...
6. .5000000000...
7. .8214808651...
etc.
Make a new number:
1. .0415926535...
2.
.5720974944...
3.
.3323333333...
4.
.7181818284...
5.
.4142035623...
6.
.5000090000...
7.
.8214807651...
etc.
• New Number = 0.0721097… isn’t in the list!
• How do we know?
28 Nov. 2012
8
Different Sizes of Infinity
• Proof by contradiction
• Cantor’s conclusion: there are more reals
between 0 and 1 than there are integers!
• Integers are countable
– …also even nos., rational nos., etc.
• Reals (and larger infinities) are
uncountable
– No. of integers = aleph-0; of reals, aleph-1
• Amazed mathematicians
• Led to set theory, new branch of math
28 Nov. 2012
9
Conclusion: Let’s Sing! (1)
• Some versions of A Hundred Bottles of Beer for really
long car trips 
Cf. http://www.informatics.indiana.edu/donbyrd/Teach/Math/InfiniteBottlesOfBeer_FullVer.pdf
• Basic transfinite version 1
Infinite bottles of beer on the wall, infinite bottles of beer;
If one of those bottles should happen to fall,
infinite bottles of beer on the wall.
Infinite bottles of beer on the wall, infinite bottles of beer;
If one of those bottles should happen to fall,
infinite bottles of beer on the wall.
(etc.)
28 Nov. 2012
10
Conclusion: Let’s Sing! (2)
• Basic transfinite version 2 (generalization of ver. 1)
Infinite bottles of beer on the wall, infinite bottles of beer;
If finite bottles should happen to fall,
infinite bottles of beer on the wall.
Infinite bottles of beer on the wall, infinite bottles of beer;
If finite bottles should happen to fall,
infinite bottles of beer on the wall.
(etc.)
28 Nov. 2012
11
Conclusion: Let’s Sing! (3)
• Larger-infinity version
Uncountable bottles of beer on the wall, uncountable bottles of
beer;
If countable bottles should happen to fall,
uncountable bottles of beer on the wall.
Uncountable bottles of beer on the wall, uncountable bottles of
beer;
If countable bottles should happen to fall,
uncountable bottles of beer on the wall.
(etc.)
28 Nov. 2012
12
Conclusion: Let’s Sing! (4)
• General transfinite version
Aleph-n bottles of beer on the wall, aleph-n bottles of beer;
If, where m < n, aleph-m bottles should happen to fall,
aleph-n bottles of beer on the wall.
Aleph-n bottles of beer on the wall, aleph-n bottles of beer;
If, where m < n, aleph-m bottles should happen to fall,
aleph-n bottles of beer on the wall.
(etc.)
• Transfinite and indeterminate version (by Richard Byrd)
Infinite bottles of beer on the wall, infinite bottles of beer;
If infinite bottles should happen to fall,
indeterminate bottles of beer on the wall.
(The End)
28 Nov. 2012
13