EECS 70 Discrete Mathematics and Probability TheorySpring 2014 Anant Sahai Note 20To Infinity And Beyond: Countability and ComputabilityThis note ties together two topics that might seem like they have nothing to do with each other. The natureof infinity (and more particularly, the distinction between different levels of infinity) and the fundamentalnature of computation and proof. This note can only scratch the surface — if you want to understand thismaterial more deeply, there are wonderful courses in the Math department as well as EECS172 and graduatecourses like EECS229A that will connect this material to the nature of information and compression as well.CardinalityHow can we determine whether two sets have the same cardinality (or “size”)? The answer to this question,reassuringly, lies in early grade school memories: by demonstrating a pairing between elements of the twosets. More formally, we need to demonstrate a bijection f between the two sets. The bijection sets up aone-to-one correspondence, or pairing, between elements of the two sets. We know how this works for finitesets. In this lecture, we will see what it tells us about infinite sets.Are there more natural numbers N than there are positive integers Z+? It is tempting to answer yes, sinceevery positive integer is also a natural number, but the natural numbers have one extra element 0 /∈ Z+. Uponmore careful observation, though, we see that we can generate a mapping between the natural numbers andthe positive integers as follows:N 0 1 2 3 4 5 . . .↓ & & & & & &Z+1 2 3 4 5 6 . . .Why is this mapping a bijection? Clearly, the function f : N → Z+is onto because every positive integeris hit. And it is also one-to-one because no two natural numbers have the same image. (The image of n isf (n) = n +1, so if f (n) = f (m) then we must have n = m.) Since we have shown a bijection between N andZ+, this tells us that there are as many natural numbers as there are positive integers! Informally, we haveproved that “∞ + 1 = ∞."What about the set of even natural numbers 2N = {0,2,4,6,...}? In the previous example the difference wasjust one element. But in this example, there seem to be twice as many natural numbers as there are evennatural numbers. Surely, the cardinality of N must be larger than that of 2N since N contains all of the oddnatural numbers as well. Though it might seem to be a more difficult task, let us attempt to find a bijectionbetween the two sets using the following mapping:N 0 1 2 3 4 5 . . .↓ ↓ ↓ ↓ ↓ ↓ ↓2N 0 2 4 6 8 10 . . .The mapping in this example is also a bijection. f is clearly one-to-one, since distinct natural numbers getEECS 70, Spring 2014, Note 20 1mapped to distinct even natural numbers (because f (n) = 2n). f is also onto, since every n in the range ishit: its pre-image isn2. Since we have found a bijection between these two sets, this tells us that in fact Nand 2N have the same cardinality!What about the set of all integers, Z? At first glance, it may seem obvious that the set of integers is largerthan the set of natural numbers, since it includes negative numbers. However, as it turns out, it is possible tofind a bijection between the two sets, meaning that the two sets have the same size! Consider the followingmapping:0 → 0, 1 → −1, 2 → 1, 3 → −2, 4 → 2, . . . , 124 → 62, . . .In other words, our function is defined as follows:f (x) =x2, if x is even−(x+1)2, if x is oddWe will prove that this function f : N → Z is a bijection, by first showing that it is one-to-one and thenshowing that it is onto.Proof (one-to-one): Suppose f (x) = f (y). Then they both must have the same sign. Therefore either f (x) =x2and f (y) =y2, or f (x) =−(x+1)2and f (y) =−(y+1)2. In the first case, f (x) = f (y) ⇒x2=y2⇒ x = y. Hencex = y. In the second case, f (x) = f (y) ⇒−(x+1)2=−(y+1)2⇒ x = y. So in both cases f (x) = f (y) ⇒ x = y,so f is injective.Proof (onto): If y ∈ Z is non-negative, then f (2y) = y. Therefore, y has a pre-image. If y is negative, thenf (−(2y + 1)) = y. Therefore, y has a pre-image. Thus every y ∈ Z has a preimage, so f is onto.Since f is a bijection, this tells us that N and Z have the same size.Now for an important definition. We say that a set S is countably infinite if there is a bijection between Sand N. We say a set is countable if it is finite or countably infinite. Thus any finite set S is countable (sincefiniteness means by definition that there is a bijection between S and the set {0,1,2,.. .,m − 1}, wherem = |S| is the size of S). And we have already seen three examples of countably infinite sets: Z+and 2N areobviously countable since they are themselves subsets of N; and Z is countable because we have just seen abijection between it and N.What about the set of all rational numbers? Recall that Q = {xy| x,y ∈ Z, y 6= 0}. Surely there are morerational numbers than natural numbers? After all, there are infinitely many rational numbers between anytwo natural numbers. Surprisingly, the two sets have the same cardinality! To see this, let us introduce aslightly different way of comparing the cardinality of two sets.If there is a one-to-one function f : A → B, then the cardinality of A is less than or equal to that of B. Now toshow that the cardinality of A and B are the same we can show that |A| ≤ |B| and |B| ≤ |A|. This correspondsto showing that there is a one-to-one function f : A → B and a one-to-one function g : B → A. The existenceof these two one-to-one functions implies that there is a bijection h : A → B, thus showing that A and B havethe same cardinality. The proof of this fact, which is called the Cantor-Bernstein theorem, is actually quitehard, and we will skip it here.Back to comparing the natural numbers and the rationals. First it is obvious that |N| ≤ |Q| because N ⊆ Q.So our goal now is to prove that also |Q| ≤ |N|. To do this, we must exhibit an injection f : Q → N. Thefollowing picture of a spiral conveys the idea of this injection:EECS 70, Spring 2014, Note 20 2Each rational numberab(written in its lowest terms, so that gcd(a,b) = 1) is represented by the point (a, b)in the infinite two-dimensional grid shown (which corresponds to Z × Z, the set of all pairs of integers).Note that not all points on the grid are valid representations of rationals: e.g., all points on the x-axis haveb = 0 so none are valid (except for (0, 0), which we take to represent the rational
View Full Document