tut08solution.pdf

4 Pages
86 Views
Unlock Document

Department
Computer Science
Course
CSC165H1
Professor
Nathalie Fournier
Semester
Fall

Description
CSC165H1F Tutorial # 8 | Sample Solutions Fall 2011 1. Prove or disprove that the set S = ff :0Z ! Zg is countable. Intuitively, each element of S cons0sts of an in▯nite amount of information, so we expect that S 0 is not countable. To show this by diagonalization involves the following steps: (a) Describe a representation for every element of S that is u0ique to each element (i.e., di▯erent representations correspond to di▯erent elements). How should we represent a function f : Z ! Z? By listing its values: f(z );f(z );f(z );:::0 1 2 Di▯erent functions correspond to di▯erent lists of values, and every list of values is a function. But what are z ;z 0z ;1::2in this list above? Any complete list of Z will do, e.g., the one from class: z 0 0;z = ▯1;z = 1;z 2 ▯2;z = 3;::: 4 (b) Assume (for a contradiction) that there is a list of every element of S . 0 In other words, there is a list f ;f 0f ;1::;2 ;::: tkat contains every function in S . 0 Then we can describe this list as follows, based on the representation for each function we’ve chosen above: z0 z1 z 2 ::: zk ::: f 0 f0(z0) f 0z 1 f0(z 2 ::: f0(zk) ::: f 1 f1(z0) f 1z 1 f1(z 2 ::: f1(zk) ::: f 2 f2(z0) f 2z 1 f2(z 2 ::: f2(z ) ::: k . . . . ... . . . . . . ▯▯▯ f k fk(z 0 f (zk) 1 (z )k:::2f (z ) ::: k k . . . . . . . . . . . . . .. (c) Describe how to construct a new representation for an element of S by \diagonalizin0" over the list. Consider the function f represented by the following list of values: f0(z 0 + 1;f (1 ) 1 1;f (z 2 + 2;::: In other words, 8i 2 N;f(z ) = f (z ) + 1. i i i (Our choice of \f (z i +i1" is arbitrary, and many other choices would work just as well. The important thing is to guarantee that the values of f are di▯erent from every function in the list for at least one argument.) (d) Show that this representation cannot belong to the list. Then f : Z ! Z, so f 2 S . Thi0 means 9k 2 N;f = f , i.e., f(z )k= f (z );f(0 ) = fk(z 0;::: 1 k 1 In particular, f(z ) k f (z k. k But f(z ) k f (z k + k (by de▯nition), so f (z ) = f kz k + 1, ike.k 0 = 1 (subtracting f (z ) k k from both sides). Hence, by contradiction, S is no0 countable. Dept. of Computer Science, University of Toronto, St. George Campus Page 1 of 4 CSC165H1F Tutorial # 8 | Sample Solutions Fall 2011 2. Prove or disprove that the set S 1 fS ▯ N : size(S) is ▯niteg is countable. Intuitively, each element of S consists of a ▯nite amount of information, so we expect that S is 1 1 countable. To show this, we must come up with a way to list every element of S systematically, i.e., according 1 to some clear pattern that does not miss any element. There is a \trick" involved in this one, i.e., a single idea you must have to make it easier. ▯ sub-list 0: start with ?, ▯ sub-list 1: add 0 to every subset generated so far (in sub-list 0): f0g, ▯ sub-list 2: add 1 to every subset generated so far (in sub-lists 0{1): f1g;f0;1g, ▯ sub-list 3: add 2 to every subset generated so far (in sub-lists 0{2): f2g;f0;2g;f1;2g;f0;1;2g, ▯ sub-list 4: add 3 to every subset generated so far (in sub-lists 0{3): f3g;f0;3g;f1;3g;f0;1;3g;f2;3g;f0;2;3g;f1;2;3g;f0;1;2;3g, ▯ ... The ▯nal list consists of all the sub-lists one after the other. Clearly, every set in this list is a ▯nite subset of N. But how do we argue that every ▯nite subset of N must appear somewhere in the list? The answer hinges on one fact (to be proven further below): + (▯) 8i 2 Z , sub-list i contains every subset of N whose maximum element is i ▯ 1. Consider an arbitrary subset S ▯ N. Let x be the maximum element in S |since S is ▯nite, it contains some maximum element. Then, S appears in sub-list x + 1 (by (▯)). Hence, every ▯nite subset of N appears somewhere in the list. Now, we argue that (▯) is true. Technically, this must be done by induction. We show the result below for your reference|you are not expected to know the structure of inductive proofs, but this is a good example of a proof by \complete induction". + Assume i 2 Z and assume sub-list j contains every subset of N whose maximum element is j ▯1, for j = 0;1;:::;i ▯ 1. Assume S ▯ N and the maximum element in S is i ▯ 1. Then either S ▯ fi ▯ 1g is empty o
More Less

Related notes for CSC165H1

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit