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.

1 Answer

Relevance
  • Yoran
    Lv 5
    8 years ago
    Best Answer

    (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.

Still have questions? Get your answers by asking now.