Class Notes (835,873)
CSC165H1 (167)
Lecture

# tut08solution.pdf

4 Pages
86 Views

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
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.