Cantor’s Legacy: Infinity And DiagonalizationEarly ideas from the courseInfinite RAM ModelThe Ideal Computer: no bound on amount of memory no bound on amount of timeAn Ideal Computer Can Be Programmed To Print Out:Printing Out An Infinite Sequence..Computable Real NumbersDescribable NumbersSlide 9Theorem: Every computable real is also describableSlide 11Slide 12Slide 13Correspondence PrincipleCorrespondence DefinitionGeorg Cantor (1845-1918)Cantor’s Definition (1874)Slide 18Do N and E have the same cardinality?Slide 20Slide 21Slide 22Slide 23Do N and Z have the same cardinality?Slide 25Slide 26Transitivity LemmaDo N and Q have the same cardinality?Slide 29Slide 30Slide 31Theorem: N and NxN have the same cardinalitySlide 33Defining 1,1 onto f: N -> NxNSlide 35Slide 36Slide 371877 letter to Dedekind: I see it, but I don't believe it!Slide 39Do N and R have the same cardinality?Slide 41Slide 42Slide 43Theorem: The set I of reals between 0 and 1 is not countable.Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Standard NotationTheorem: Every infinite subset S of S* is countableStringing Symbols TogetherSlide 60Slide 61Slide 62Slide 63Slide 64Slide 65Power SetTheorem: S can’t be put into 1-1 correspondence with P(S)Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Cantor’s Legacy: Infinity And DiagonalizationGreat Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2004Lecture 25 Apr 13, 2004 Carnegie Mellon University�Early ideas from the courseInductionNumbersRepresentationFinite Counting and probability----------A hint of the infinite:Infinite row of dominoes.Infinite choice trees, and infinite probabilityInfinite 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 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 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 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 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 printed as part of the output sequence.Are all real numbers computable?Describable NumbersA 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 rDescribable r: some sentence denotes rTheorem: Every computable real is also describableProof: 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:” PMORAL: A computer program can be viewed as a description of its output.Syntax: The text of the programSemantics: The real number output by P.Are all real numbers describable?To INFINITY …. and Beyond!Correspondence PrincipleIf two finite sets can be placed into 1-1 onto correspondence, then they have the same size.Correspondence DefinitionTwo 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 infinityDo 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 evenTransitivity LemmaIf f: AB 1-1 onto, and g: BC 1-1 ontoThen h(x) = g(f(x)) is 1-1 onto ACHence, , , and all have the same cardinality.Do and have the same cardinality?= { 0, 1, 2, 3, 4, 5, 6, 7, …. }= 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.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 xTheorem: and xhave the same cardinality0 1 2 3 4 ……43210The point (x,y)represents the ordered pair (x,y)Theorem: and xhave the same cardinality0 1 2 3 4 ……432100123456789The point (x,y)represents the ordered pair (x,y)Defining 1,1 onto f: -> xk;=0; For sum = 0 to forever do{For x = 0 to sum do {y := sum-x;Let f(k):= The point (x,y); k++
View Full Document
Unlocking...