DOC PREVIEW
Berkeley COMPSCI 70 - Infinity and Countability

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 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 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 70 - Infinity and Countability

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

n20

n20

10 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 Infinity and Countability
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 Infinity and Countability 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 Infinity and Countability 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?