Great Theoretical Ideas In Computer Science Steven Rudich CS 15 251 Lecture 25 Apr 13 2004 Spring 2004 Carnegie Mellon University Cantor s Legacy Infinity And Diagonalization Early ideas from the course Induction Numbers Representation Finite Counting and probability A hint of the infinite Infinite row of dominoes Infinite choice trees and infinite probability Infinite RAM Model Platonic Version One memory location for each natural number 0 1 2 Aristotelian Version Whenever you run out of memory the computer contacts the factory A maintenance person is flown by helicopter and attaches 100 Gig of RAM and all programs resume their computations as if they had never been interrupted The Ideal Computer no bound on amount of memory no bound on amount of time Ideal Computer is defined as a computer with infinite RAM You can run a Java program and never have any overflow or out of memory errors An Ideal Computer Can Be Programmed To Print Out 3 14159265358979323846264 2 2 0000000000000000000000 e 2 7182818284559045235336 1 3 0 33333333333333333333 1 6180339887498948482045 Printing Out An Infinite Sequence We say program P prints out the infinite sequence s 0 s 1 s 2 if when P is executed on an ideal computer a sequence of symbols appears on the screen such that The kth symbol is s k For every k2 P eventually prints the kth symbol I e the delay between symbol k and symbol k 1 is not infinite Computable Real Numbers A real number r is computable if there is a program that prints out the decimal representation of r from left to right Thus each digit of r will eventually be printed as part of the output sequence Are all real numbers computable Describable Numbers A real number r is describable if it can be unambiguously denoted by a finite piece of English text 2 Two The area of a circle of radius one Is every computable real number also a describable real number Computable r some program outputs r Describable r some sentence denotes r Theorem Every computable real is also describable Proof Let r be a computable real that is output by a program P The following is an unambiguous denotation The real number output by the following program P MORAL A computer program can be viewed as a description of its output Syntax The text of the program Semantics The real number output by P Are all real numbers describable To INFINITY and Beyond Correspondence Principle If two finite sets can be placed into 1 1 onto correspondence then they have the same size Correspondence Definition Two finite sets are defined to have the same size if and only if they can be placed into 1 1 onto correspondence Georg Cantor 1845 1918 Cantor s Definition 1874 Two sets are defined to have the same size if and only if they can be placed into 1 1 onto correspondence Cantor s Definition 1874 Two sets are defined to have the same cardinality if and only if they can be placed into 1 1 onto correspondence Do and have the same cardinality 0 1 2 3 4 5 6 7 The even natural numbers and do not have the same cardinality is a proper subset of with plenty left over The attempted correspondence f x x does not take onto and do have the same cardinality 0 1 2 3 4 5 0 2 4 6 8 10 f x 2x is 1 1 onto Lesson Cantor s definition only requires that some 1 1 correspondence between the two sets is onto not that all 1 1 correspondences are onto This distinction never arises when the sets are finite If this makes you feel uncomfortable TOUGH It is the price that you must pay to reason about infinity Do and have the same cardinality 0 1 2 3 4 5 6 7 2 1 0 1 2 3 No way is infinite in two ways from 0 to positive infinity and from 0 to negative infinity Therefore there are far more integers than naturals Actually not and do have the same cardinality 0 1 2 3 4 5 6 0 1 1 2 2 3 3 f x x 2 if x is odd x 2 if x is even Transitivity Lemma If f A B 1 1 onto and g B C 1 1 onto Then h x g f x is 1 1 onto A C Hence and all have the same cardinality Do and have the same cardinality 0 1 2 3 4 5 6 7 The Rational Numbers No way The rationals are dense between any two there is a third You can t list them one by one without leaving out an infinite number of them Don t jump to conclusions There is a clever way to list the rationals one at a time without missing a single one First let s warm up with another interesting one can be paired with x Theorem and x have the same cardinality 4 3 The point x y represents the ordered pair x y 2 1 0 0 1 2 3 4 Theorem and x have the same cardinality 4 6 3 2 3 1 1 0 0 0 The point x y represents the ordered pair x y 7 4 8 5 2 1 2 9 3 4 Defining 1 1 onto f x k 0 For sum 0 to forever do For x 0 to sum do y sum x Let f k The point x y k Onto the Rationals The point at x y represents x y 3 0 1 2 The point at x y represents x y 1877 letter to Dedekind I see it but I don t believe it We call a set countable if it can be placed into 1 1 onto correspondence with the natural numbers So far we know that N E Z and Q are countable Do and have the same cardinality 0 1 2 3 4 5 6 7 The Real Numbers No way You will run out of natural numbers long before you match up every real Don t jump to conclusions You can t be sure that there isn t some clever correspondence that you haven t thought of yet I am sure Cantor proved it He invented a very important technique called DIAGONALIZATION Theorem The set I of reals between 0 and 1 is not countable Proof by contradiction Suppose I is countable Let f be the 1 1 onto function from to I Make a list L as follows 0 decimal expansion of f 0 1 decimal expansion of f 1 k decimal expansion of f k Theorem The set I of reals between 0 and 1 is not countable Proof by contradiction Suppose I is countable Let f be the 11 onto function from to I Make a list L as follows 0 3333333333333333333333 1 3141592656578395938594982 k 345322214243555345221123235 L 0 1 2 3 0 1 2 3 4 L 0 1 2 3 0 1 2 3 4 d0 d1 d2 d3 L 0 1 2 0 1 2 3 4 d0 d1 d2 3 …
View Full Document
Unlocking...