(1) (a) describe why Z X Z must be countable.
(b) By part (a) we know that N ≡ Z X Z, and hence there must be a one-to-one correspondence between N and Z X Z. Provide one such one-to-one correspondence f : N → Z X Z. Note, it may be easiest to describe your map using a sketch of Z X Z.
(2) Proved in that a finite product of countable sets is countable. It is not true however that a countable product of count- able sets must be countable. Here you will see one ex of a countable product of finite sets that is not countable.
For each i ≡ N let A_{i} = {0,1} and let
the set of all sequences of 1's and 0's. The set A is a countable product of finite and hence countable sets. Prove that A is not countable.
(3) A complex number z is "algebraic" if it is a root of some integral polynomial (a polynomial with integer coefficients). That is z is algebraic if there is some
p(x) = a0 + a1x + a2x^{2} +........+ a_{k}x^{k} a_{i} ≡ Z and at least one ai ≠ 0 with p(z) = 0. For ex, the polynomial p(x) = -4+4x-x^{2}+x^{3} factors to p(x) = (x- 1)(x - 2i)(x + 2i) and so has roots x = 1 and x = ± 2i, thus 1, 2i and -2i are algebraic numbers. Let A denote the set of all algebraic numbers in C, and prove that A is countable by the following steps.
(a) For each n ≡ N, let Pn denote the set of integral polynomials of degree n. Prove that for each n the set P_{n} is countable.
(b) Now let P be the set of all integral polynomials. describe why P must be countable.
(c) Given a particular integral polynomial p(x) of degree k, let R_{p} be the set of all roots of p(x). What can be said about the number of elements in R_{p}?
(d) Using parts (a), (b) and (c), prove that A, the set of all algebraic integers, is countable.