Exercises

1.

2^Z+ contains some infinite members and some finite members. Let F be the set of all finite elements of 2^Z+. F, by an argument running in parallel to that given by Cantor in his proof that 2^Z+ is not countably infinite, can likewise be shown to be uncountable. Say whether this is true or false, and prove that you are correct.

2.

The proof of Cantor's Theorem (2.3) can be given in a graphical way, using the array shown just below. Produce the proof. As a hint, recast the sets in list L from the previous proof as a set of functions having the following form. Notice that these functions are based upon corresponding elements from L. Also, work from the array shown below the definition of this function schema.

$$s_n(p)=\left\{ \begin{array}{rl} 1 & \mbox{if $p \in S_n$} \\ 0 & \mbox{if $p \not\in S_n$} \end{array} \right.$$

$$\begin{array}{c\vert ccccc} & 1 & 2 & 3 & 4 & \ldots \\ \h... ...\ \vdots & \vdots & \vdots & \vdots & \vdots & \\ \end{array}$$

3.

Adapt the graphical proof given in the previous exercise in order to show that the real number interval from 0 to 1 is not countably infinite. As a hint, consider the following three ingredients (function schema, array, and ``anti-diagonal" sequence).

$$d'=\left\{ \begin{array}{rl} 1 & \mbox{if $d$ = 2} \\ 2 & \mbox{otherwise} \end{array} \right.$$

$$\begin{array}{c\vert ccccc} & 1 & 2 & 3 & 4 & \ldots \\ \h... ...\ \vdots & \vdots & \vdots & \vdots & \vdots & \\ \end{array}$$

$$\bar{D}(L) \, = \, s_1(1)', s_2(2)', \ldots$$

4.

Where A and B are any two sets, we write B^A for the set of all functions from A to B. Show that there is a bijection between $\{0, 1\}^A$ and the power set of A, that is, 2^A.

5.

Prove that N $^{\mbox{{\bf N}}}$ is uncountable using diagonalization.