Countable Sets For each set defined below, prove that the set described is count
ID: 3183782 • Letter: C
Question
Countable Sets For each set defined below, prove that the set described is countable. 1. Evens = {2n | n E N} 2. N U {T, } (where is the ratio of a circle's circumference to its diameter and is the ratio of a circle's circumference to its radius) 3. The set X of all finite state machines, M = (S, G, go) where S = Nk for some natural number k > 0, and G-S × S and go E S are otherwise unrestricted. (Note that here we are not working with a fixed k, and for example machines with S = N2 and machines with S = N9 are both counted in the set X)Explanation / Answer
1. let , f : N --> evens={2n | n belongs to N } be defined by, f(n) = 2n
to show : f is a bijection
one one : let f(a)=f(b) belongs to even, to show : a=b
f(a)=f(b) => 2a=2b => a=b
hence f is one-one
onto : let y belongs to even, then y=2x for some x in N
then f(x)=2x=y, i.e. for all y in even, there exists x=y/2 in N such that f(x) = f(y/2) = y
hence, f is a bijection from N onto evens.
hence, evens={2n | n belongs to N } is countable, (since N is countable)
2.. let g : N U {, } --> N be defined by, g() = 1; g() = 2 ; g(n) = n+2 for all n in N
to show g is a bijection
one one : clearly 1 and 2 are mapped to , respectively,
and for all n in N, g(n)=g(m) => n+2=m+2 => n=m
hence g is onto.
for 1 in N, the pre image is , i.e. g(1)=
and for 2 in N , the preimage is , g(2)=
and for all n >= 3 in N, the preimage is n-2 , i.e. g(n-2) = n-2+2 = n
hence g is onto
hence g is a bijection from N U {, } onto N
since , N is countable, so N U {, } is countable as well