4/7/2009115-251Great Theoretical Ideas in Computer Science∞Cantor’s Legacy: Infinity and DiagonalizationLecture 23 (April 7, 2009)Ideas from the courseInductionNumbers, Number theory and AlgebraRepresentationFinite Counting and ProbabilityAutomata and Computation A hint of the infiniteInfinite row of dominoesInfinite sums (formal power series)Infinite choice trees, and infinite probability Infinite RAM ModelPlatonic 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.The Ideal Computer:no bound on amount of memoryno bound on amount of timeIdeal 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 ComputerIt can be programmed to print out:2: 2.0000000000000000000000…1/3: 0.33333333333333333333…φ: 1.6180339887498948482045…e: 2.7182818284559045235336…π: 3.14159265358979323846264…4/7/20092Printing 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 kthsymbol that it outputs is sk-For every k∈N, P eventually outputs the kthsymbol. I.e., the delay between symbol k and symbol k+1 is not infinite.Computable Real NumbersA 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 NumbersA 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?Is every computable real number, also a describable real number?And what about the other way?Computable R: some program outputs RDescribable R: some sentence denotes RComputable ⇒ describableTheorem:Every computable real is also describableProof: Let R be a computable real that is output by a program P. The following is an unambiguousdescription of R:“The real number output by the following program:” PMORAL: A computer program can be viewed as a description of its output.Syntax: The text of the programSemantics: The real number output by P4/7/20093Are all reals describable?Are all reals computable?We saw thatcomputable ⇒describable, but do we also havedescribable ⇒computable?Questions we will answer in this (and next) lecture…Correspondence PrincipleIf two finite sets can be placed into 1-1 onto (bijective) correspondence, then they have the same size.Correspondence DefinitionIn 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 (bijective) 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.If there exists a bijection between them.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.If there exists a bijection between them.4/7/20094Do 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 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 EontoN.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. Lesson: Cantor’s definition only requires that some1-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 beplaced into 1-1 onto correspondence.You just have to get used to this slight subtlety in order to argue about infinite sets!4/7/20095Do 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 samecardinality!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 evenTransitivity LemmaLemma: If f: A→B is a bijection, and g: B→C is a bijection.Then h(x) = g(f(x)) defines a functionh: A→C that is a bijection too.Hence, N, E, and Z all have the same cardinality.Do N and Q have the same cardinality?N= { 0, 1, 2, 3, 4, 5, 6, 7, …. }Q = The Rational NumbersNo 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.4/7/20096Don’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 example:N can be paired with N×NTheorem: N and N×N have the same cardinalityTheorem: N and N×N have the same cardinality0 1 2 3 4 ……43210The point (x,y)represents the ordered pair (x,y)Theorem: N and N×N have the same cardinality0 1 2 3 4 ……432100123456789The point (x,y)represents the ordered pair (x,y)The first few tuples output…(0,0)(0,1), (1,0)(0,2), (1,1), (2,0)(0,3), (1,2), (2,1), (3,0)…4/7/20097Defining bijection f: N -> N×N let i := 0; //will range over Nfor (sum = 0 to forever) {//generate all pairs with this sumfor (x = 0 to sum) {y := sum-xdefine f(i) := the point (x,y)i++;}} Onto the Rationals!The point at x,y represents x/y The point at x,y represents x/yCantor’s 1877 letter to Dedekind:“I see it, but I don't believe it!”Countable SetsWe call a set countable if it can be placed into 1-1 onto correspondence with the natural numbers N.HenceN, E, Q and Z are all countable.4/7/20098Do N and R have the same cardinality?N = { 0, 1, 2, 3, 4, 5, 6, 7, … }R = The Real NumbersNo way!You will run out of natural numbers long before you match up every real.Now hang on a minute!You can’t be sure that there isn’t some clever correspondence that you haven’t thought of yet.I am
View Full Document