Anonymous
Anonymous asked in Science & MathematicsMathematics · 8 years ago

# Show that each of the folioing sets is countable by giving a bijection between the sets and N ∪ {0}:?

(a) The set of even non-negative integers.

(b) The set Z of integers.

Relevance

(a) The set of even non-negative integers is

E ={2n|n in N ∪ {0}} = { 0,2,4,6....}.

Now let f(n) = 2n be a function from N ∪ {0} to E.

2n is injective, because

f(n) = f(m) => 2n = 2m => n=m

and f is also surjective:

let k in E be given. Then k = 2r for some r in N. Then choose r in N, then f(r) = 2r = k. So for every element in E, there exists an element in N ∪ {0} such that the function maps the latter to the first.

I.e : f is a bijection. So E is countable.

(b) Z is given by {...-2, -1, 0, 1, 2, ...}. Consider then function

f(n) = n/2 if n is even

f(n) = -(n+1)/2 if n is odd.

This function is a bijection from N to Z, making Z countable as well. I will leave it up to you to show that htis function is a bijection, i.e showing it is both injective and surjective.