CS 70 Discrete Mathematics for CSFall 2006 Papadimit rio u & Vazirani Lecture 39Infinity and CountabilityConsider a function f that maps elements of a set A (called the domain of f) to elements of set B (called therange of f). Recall that we write this as f : A → B. We say that f is a bijection if every element a ∈ A has aunique image b = f(a) ∈ B, and every element b ∈ B has a unique pre-image a ∈ A : f(a) = b.f is a one-to-one function (or an injection) then if f maps distinct inputs to distinct outputs. More rigorously,f is one-to-one if the following holds: x 6= y ⇒ f(x) 6= f(y).The next property we are interested in is functions that are onto (or surjective) . A mapping 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 mapping function f is onto if the following holds: ∀y,∃x : f(x) = y. Here are someexamples to help visualize what constitutes one-to-one and onto mappings: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 questionreassuringly lies in early grade school memories: by demonstrating a pairing between elements of the twosets. Saying this more formally, it is by demonstrating a bijection f between the two sets. The bijection setsup a one to one correspondence or pairing between elements of the two sets. We know how this works forfinite sets. 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 : Z+→ N is one-to-one (prove it). The mapping isalso onto because every image n ∈ N is hit: the pre-image n+1 maps to it. We will never run out of positiveintegers; informally this says “∞+ 1 = ∞.”CS 70, Fall 2006, Lecture 39 1Since we have shown a bijection between N and Z+, this tells us that there are as many natural numbers asthere are positive integers! What about the infinite set of even natural numbers 2N = {0,2,4,6,...}? In theprevious example, the difference was just one element. But in this example, there seems to be twice as manynatural numbers as there are even natural numbers. Surely, the cardinality of N must be larger than 2N sinceN contains all of the odd natural numbers! Though it might seem to be a more difficult task, let us attemptto find a bijection between the two sets with this 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 even natural numbersget mapped to distinct natural numbers. Can you prove this more rigorously? The mapping is also onto,since every n in the range is hit: its pre-image is 2n. Since we have found a bijection between these two sets,this tells us that in fact N and 2N actually have the same cardinality!In this lecture, we will see that there are different “orders” of infinity. If we are given a set B and can find abijective function from N or some subset of N to our set, then we will call B a countable set (this name waschosen since the natural numbers are often considered the counting numbers).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 mapping 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 towards a contradiction that f(x) = f(y). Then they both must have the samesign. Therefore either f(x) =x2and f(y) =y2. So f(x) = f(y) ⇒x2=y2⇒ x = y. Contradiction. Thesecond case is very similar, f(x) =−(x+1)2and f(y) =−(y+1)2. So f(x) = f(y) ⇒−(x+1)2=−(y+1)2⇒ x = y.Contradiction, and thus f is one-to-one.Proof (onto): If y is positive, then f(2y) = y. Therefore, y has a pre-image. If y is negative, then f(−(2y+1)) = y. Therefore, y has a pre-image. Thus, f is onto.Since f is a bijective function, this tells us that N and Z have the same size! Another way to describe thismapping is: positive integers ↔ even natural numbers, negative integers ↔ odd natural numbers. Whatabout the set of all rational numbers? Recall that Q = {xy| x,y ∈ Z, y 6= 0}. Informally, we are asking thequestion: ∞× ∞ > ∞?Surely there are more rational numbers than natural numbers. After all there are infinitely many rationalnumbers between any two natural numbers. Surprisingly, the two sets have the same cardinality! To seethis, let us introduce another 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 correspondsCS 70, Fall 2006, Lecture 39 2to 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. Consider the following picture of a spiral to helpconvince yourself:Each rational numberabcan be represented by the point (a,b) on the grid. We can map everyabto thedistance of the point (a,b) along this spiral starting at the origin (e.g. 0 ↔ (0,0), 1 ↔ (1,0), 2 ↔ (1,1), . . . ).Why is this mapping a bijection? We have to be extremely careful, since f : Q →
View Full Document