11 18 2008 Ideas from the course 15 251 Great Theoretical Ideas in Computer Science Induction Numbers Representation Finite Counting and Probability A hint of the infinite Infinite row of dominoes Infinite sums formal power series 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 1000 Gig of RAM and all programs resume their computations as if they had never been interrupted An Ideal Computer It can be programmed to print out 2 1 3 e 2 0000000000000000000000 0 33333333333333333333 1 6180339887498948482045 2 7182818284559045235336 3 14159265358979323846264 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 Printing Out An Infinite Sequence A program P prints out the infinite sequence s0 s1 s2 sk if when P is executed on an ideal computer it outputs a sequence of symbols such that The kth symbol that it outputs is sk For every k N P eventually outputs the kth symbol I e the delay between symbol k and symbol k 1 is not infinite 1 11 18 2008 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 output Are all real numbers computable Describable Numbers A real number R is describable if it can be denoted unambiguously by a finite piece of English text 2 Two The area of a circle of radius one Are all real numbers describable Computable describable Is every computable real number also a describable real number Theorem Every computable real is also describable And what about the other way Computable R some program outputs R Describable R some sentence denotes R Computable describable Theorem Every computable real is also describable MORAL A computer program can be viewed as a description of its output Proof Let R be a computable real that is output by a program P The following is an unambiguous description of R The real number output by the following program P Syntax The text of the program Semantics The real number output by P 2 11 18 2008 Correspondence Principle Are all reals describable Are all reals computable We saw that computable describable but do we also have describable computable If two finite sets can be placed into 1 1 onto correspondence then they have the same size Questions we will answer in this and next lecture Correspondence Definition Georg Cantor 1845 1918 In fact we can use the correspondence as the definition Two finite 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 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 Two sets are defined to have the same cardinality if and only if they can be placed into 1 1 onto correspondence 3 11 18 2008 Do N and E have the same cardinality N 0 1 2 3 4 5 6 7 E 0 2 4 6 8 10 12 The even natural numbers E and N do have the same cardinality N 0 1 2 3 4 5 E 0 2 4 6 8 10 f x 2x is 1 1 onto E and N do not have the same cardinality E is a proper subset of N with plenty left over The attempted correspondence f x x does not take E onto N 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 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 You just have to get used to this slight subtlety in order to argue about infinite sets 4 11 18 2008 Do N and Z have the same cardinality N 0 1 2 3 4 5 6 7 Z 2 1 0 1 2 3 No way Z 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 no N and Z do have the same cardinality Transitivity Lemma N 0 1 2 3 4 5 6 Z 0 1 1 2 2 3 3 f x x 2 if x is odd x 2 if x is even Transitivity Lemma Do N and Q have the same cardinality Lemma If f A B is 1 1 onto and g B C is 1 1 onto Then h x g f x defines a function h A C that is 1 1 onto N 0 1 2 3 4 5 6 7 Q The Rational Numbers Hence N E and Z all have the same cardinality 5 11 18 2008 No way Don t jump to conclusions 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 There is a clever way to list the rationals one at a time without missing a single one Theorem N and N N have the same cardinality First let s warm up with another interesting example N can be paired with N N Theorem N and N N have the same cardinality 4 Theorem N and N N have the same cardinality 4 3 The point x y represents the ordered pair x y 2 1 0 0 1 2 3 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 6 11 18 2008 Defining 1 1 onto f N N N let i 0 will range over N Onto the Rationals for sum 0 to forever generate all pairs with this sum for x 0 to sum y sum x define f i the point x y i 3 0 1 2 The point at x y represents x y The point at x y represents x y Countable Sets Cantor s 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 N Hence N E Q and Z are all countable 7 11 18 2008 Do N and R have the same cardinality N 0 1 2 3 4 5 6 7 R The Real Numbers Now hang on a minute You can t be sure that there isn t some clever correspondence that you haven t thought …
View Full Document
Unlocking...