Cantor's Problems

1.6.3a, 1.6.5, 1.6.10

1.6.3

Question

Supply rebuttals to the following complaints about the proof of Cantor's Diagonalization Method:
a. Every rational number has a decimal expansion, so we could apply this
same argument to show that the set of rational numbers between 0 and 1
is uncountable. However, because we know that any subset of $Q$ must be
countable, the proof must be flawed.
b. Some numbers have two different decimal representations. Specifically,
any decimal expansion that terminates can also be written with repeating
9’s. For instance, 1/2 can be written as .5 or as .4999 . . . . Doesn’t this
cause some problems?

Proof
a. We know that any rational number's decimal expansion must have repeating digits (otherwise, it's irrational). But the constructed new number must have non-repeating digits (since it's different for each one for each of the repeating digits), so the new number must be irrational.

b. No this doesn't. If anything we can restrict the thought experiment to deal with one of the two cases. Alternatively, we can least each number with it's counterpart expansion, doubling the size of the list. Either way, we still would construct a number different from each version of the decimal expansion, so it's still a unique number not on the list.
☐

1.6.5

Question

a. Let $A = {a, b, c}$ . List the eight elements of $P (A)$ .
b. If $A$ is finite with $n$ elements, show that $| P (A) | = 2^{n}$ .

Proof
a. $P (A) = {\emptyset, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A}$ .
b. We'll do an induction on $n$ .

For $n = 1$ then $A = {a}$ where $a$ is the random element. Then $P (A) = {\emptyset, {a}}$ so clearly $| P (A) | = 2 = 2^{1} = 2^{n}$ for this case.

For the inductive step suppose the case holds for $n$ elements. Then consider the set $A_{n + 1}$ with $n + 1$ elements. Then we can define:

A_{n + 1} = A_{n} \cup {a}

where ${a}$ is a singleton, taken from $A_{n + 1}$ , such that $a \notin A_{n}$ . We know that $| P (A_{n}) | = 2^{n}$ by the inductive hypothesis. Notice that for each of the $2^{n}$ sets from $P (A_{n})$ that $a$ can go in any of these to make a new subset (since the subsets from $P (A_{n})$ don't have $a$ by construction), so then we expect to get $2^{n} + 2^{n}$ subsets for $P (A_{n + 1})$ . But $2^{n} + 2^{n} = 2 \cdot 2^{n} = 2^{n + 1}$ as required.
☐

1.6.10 (finish)

Question

Determine if the sets have the same cardinality by finding a bijection, or showing one doesn't exist:
a. Is the set of all functions from ${0, 1} \to N$ countable or uncountable?
b. Is the set of all functions from $N \to {0, 1}$ countable or uncountable?
c. Given a set $B$ , a subset $A$ of $P (B)$ is called an antichain if no element of $A$ is a subset of any other element of $A$ . Does $P (N)$ contain an uncountable antichain?

Proof
a. It's countable. Consider the injection $g : ({0, 1} \to N) \to N$ defined by:

g (f) = 2^{f (0)} 3^{f (1)}

(injective): Say $f_{1}, f_{2} \in ({0, 1} \to N)$ are such that $g (f_{1}) = g (f_{2})$ . Then:

\begin{aligned} g (f_{1}) & = g (f_{2}) \\ 2^{f_{1} (0)} 3^{f_{1} (1)} & = 2^{f_{2} (0)} 3^{f_{2} (1)} \end{aligned}

Since prime factorizations are unique, this implies that $f_{1} (0) = f_{2} (0)$ and $f_{2} (1) = f_{1} (1)$ . Since all the inputs equal each output between the two functions, then $f_{1} = f_{2}$ showing injectivity.

We actually don't need to show surjectivity here, since we know that $g$ is injective then at most all the $g$ 's count below $N$ , showing $g$ is countable.

b. It's countable. Consider again an injection $h : N \to ({0, 1} \to N)$ defined by:

h (n) =

☐