false

Class Notes
(835,873)

Canada
(509,459)

University of Toronto St. George
(44,017)

Computer Science
(754)

CSC165H1
(167)

Nathalie Fournier
(31)

Lecture

Unlock Document

Computer Science

CSC165H1

Nathalie Fournier

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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.