Search 75,910 tutors
FIND TUTORS
Ask a question
0 0

Prove that Z x Z is countable

Tutors, please sign in to answer this question.

1 Answer

It's countable. First of all, Z is countable.

Here is one way. First, enumerate the integers as 0, 1, -1, 2, -2, 3, -3, ...

Now make an array and trace a diagonal zigzag as illustrated to enumerate Z2:

          0          1         -1         2          -2          3        -3   ...

0     (0,0)     (1,0)  -  (-1,0)    (2,0)  -  (-2,0)    (3,0)  - (-3,0) ...

          |     ⁄          ⁄           ⁄          ⁄           ⁄           ⁄

1     (0,1)     (1,1)     (-1,1)    (2,1)     (-2,1)    (3,1)    (-3,1) ...

                ⁄          ⁄           ⁄          ⁄           ⁄

-1    (0,-1)   (1,-1)    (-1,-1)   (2,-1)    (-2,-1)   (3,-1)   (-3,-1) ...

          |     ⁄         ⁄            ⁄          ⁄

2     (0,2)     (1,2)     (-1,2)    (2,2)     (-2,2)    (3,2)    (-3,2) ...

                ⁄          ⁄           ⁄

-2    (0,-2)   (1,-2)    (-1,-2)   (2,-2)    (-2,-2)   (3,-2)   (-3,-2) ...

          |     ⁄         ⁄

3     (0,3)     (1,3)     (-1,3)     (2,3)     (-2,3)    (3,3)    (-3,3) ...

               ⁄

-3    (0,-3)   (1,-3)    (-1,-3)    (2,-3)    (-2,-3)   (3,-3)  (-3,-3)

...       ...        ...          ...          ...         ...         ...        ...