CS 70 Discrete Mathematics for CSSpring 2008 David Wagner Note 23Infinity and CountabilityConsider a function (or mapping) f that maps elements of a set A (called the domain of f) to elements of setB (called the range of f). For each element x ∈ A (“input”), f must specify one element f(x) ∈ B (“output”).Recall that we write this as f : A → B. We say that f is a bijection if every element a ∈ A has a unique imageb = f(a) ∈ B, and every element b ∈ B has a unique pre-image a ∈ A such that f (a) = b.f is a one-to-one function (or an injection) if f maps distinct inputs to distinct outputs. More rigorously, fis one-to-one if the following holds: ∀x,y . x 6= y ⇒ f(x) 6= f(y).The next property we are interested in is functions that are onto (or surjective). A function that is ontoessentially “hits” every element in the range (i.e., each element in the range has at least one pre-image).More precisely, a function f is onto if the following holds: ∀y ∃x . f(x) = y. Here are some examples tohelp visualize one-to-one and onto functions:One-to-one OntoNote that according to our definition a function is a bijection iff it is both one-to-one and onto.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 ...CS 70, Spring 2008, Note 23 1Why 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 getmapped 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 odd.We 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 eitherf(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.Hence x = y. In the second case, f(x) = f(y) ⇒−(x+1)2=−(y+1)2⇒ x = y. In both cases f(x) = f(y) ⇒ x = y,so taking the contrapositive, f must be one-to-one.Proof (onto): If y ∈ Z is positive, then f(2y) = y, and 2y ≥ 0. Therefore, y has a pre-image in N. If y isnegative, then f(−(2y+ 1)) = y, and −(2y+ 1) ≥ 0. Therefore, y has a pre-image in N in this case, too.Thus every y ∈ Z has a pre-image, so f is onto.Since f is a bijection, this tells us that N and Z have the same cardinality.Now for an important definition. We say that a set S is countable if there is a bijection between S and Nor some subset of N. Thus any finite set S is countable (since there is a bijection between S and the subset{0,1, 2,...,m− 1}, where m = |S| is the size of S). And we have already seen three examples of countableinfinite sets: Z+and 2N are obviously countable since they are themselves subsets of N; and Z is countablebecause we have just seen a bijection between it and N.CS 70, Spring 2008, Note 23 2What 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 introduceanother 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 integers. 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 a one-to-one
View Full Document
Unlocking...