DOC PREVIEW
Berkeley COMPSCI 70 - n20

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 70 - n20

Documents in this Course
Notes 1

Notes 1

12 pages

Note 2

Note 2

6 pages

Notes

Notes

6 pages

Notes

Notes

7 pages

Note 10

Note 10

8 pages

n19

n19

10 pages

n18

n18

10 pages

n17

n17

6 pages

n16

n16

9 pages

n15

n15

10 pages

n14

n14

9 pages

n13

n13

6 pages

n12

n12

7 pages

n11

n11

6 pages

n10

n10

8 pages

n9

n9

5 pages

n8

n8

7 pages

n7

n7

8 pages

n6

n6

5 pages

n5

n5

8 pages

n4

n4

7 pages

n3

n3

10 pages

n2

n2

7 pages

n1

n1

5 pages

Load more
Download n20
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view n20 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view n20 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?