Cardinality Practice

1.5.4, 1.5.6, 1.5.8, 1.5.9 (Optional: 1.5.10 (outlines the proof to the Schröder-Bernstein theorem))

1.5.4 (later the proof sucks)

Question

a. Show $(a, b) \sim R$ for any interval $(a, b)$ .
b. Show that an unbounded interval like $(a, \infty)$ has the same cardinality as $R$ as well.
c. Using open intervals makes it more convenient to produce the required bijections, but it is not necessary. Show that $[0, 1) \sim (0, 1)$ by exhibiting a bijective function between the two sets.

Proof
a. Consider the function $f : (a, b) \to R$ defined as:

f (x) = \frac{x - \frac{a + b}{2}}{(x - a) (b - x)}

We claim that $f$ is a bijection:

(Injective): Let $f (x_{1}) = f (x_{2})$ . Then:

\begin{aligned} f (x_{1}) & = f (x_{2}) \\ \frac{x_{1} - \frac{a + b}{2}}{(x_{1} - a) (b - x_{1})} & = \frac{x_{2} - \frac{a + b}{2}}{(x_{2} - a) (b - x_{2})} \\ (x_{1} - \frac{a + b}{2}) (x_{2} - a) (b - x_{2}) & = (x_{2} - \frac{a + b}{2}) (x_{1} - a) (b - x_{1}) \\ (2 x_{1} - a - b) (x_{2} - a) (b - x_{2}) & = (2 x_{2} - a - b) (x_{1} - a) (b - x_{1}) \\ (2 x_{1} - a - b) (- x_{2}^{2} + (a + b) x_{2} - a b) & = (2 x_{2} - a - b) (- x_{1}^{2} + (a + b) x_{1} - a b) \\ - 2 x_{1} x_{2}^{2} + (a + b) x_{2}^{2} + 2 [a + b] x_{1} x_{2} - [a + b]^{2} x_{2} + (a + b) a b & = - 2 x_{2} x_{1}^{2} + (a + b) x_{1}^{2} + 2 [a + b] x_{1} x_{2} - [a + b]^{2} x_{1} + (a + b) a b \\ - 2 x_{1} x_{2}^{2} + 2 x_{2} x_{1}^{2} + (a + b) x_{2}^{2} - (a + b) x_{1}^{2} - [a + b]^{2} x_{2} + [a + b]^{2} x_{1} & = 0 \\ (2 x_{2} - (a + b)) x_{1}^{2} + (- 2 x_{2}^{2} + [a + b]^{2}) x_{1} + ((a + b) x_{2}^{2} - [a + b]^{2} x_{2}) & = 0 \\ \frac{}{} & = x_{2} \end{aligned}

☐

1.5.6

Question

a. Give an example of a countable collection of disjoint open intervals.
b. Give an example of an uncountable collection of disjoint open intervals, or argue that no such collection exists.

Proof
a. Define $A = {(i, i + 1) \subseteq R | i \in Z}$ . Clearly each $(i, i + 1) \sim i$ so then $A \sim Z$ .
b. This is impossible. Say such an uncountable collection $A$ exists. For any nonempty interval $I_{n}$ The Density of Q in R says that $\exists r \in Q$ where $r \in I_{n}$ . Assign each $I \in A$ , $r \in I$ implies that $I \subseteq Q$ and thus $I$ is countable.
☐

1.5.8 (finish)

Question

Let $B \subseteq R^{+}$ with the property that $\forall n \in N (a_{1}, . . ., a_{n} \in B \Rightarrow \sum_{i = 1}^{n} a_{i} \leq 2)$ . Then $B$ is either finite or countable.

Proof
Notice that $B \subseteq (0, 2]$ . $B \cap [2, \infty) = {2}$ since any number bigger than $2$ implies that it is not in $B$ . As a result $B \cap [2, \infty)$ is finite.

Similarly notice that $B \cap [1, \infty)$ must be countable. In general if we prove that $B \cap [\frac{2}{n}, \infty)$ is countable, then we are done since $B = ⋃_{n = 1}^{\infty} (B \cap [\frac{2}{n}, \infty))$ which are all countable subsets.

☐

1.5.9

Question

A real number $x \in R$ is called algebraic if there exist integers $a_{i} \in Z$ , not all zero, such that:

a_{n} x^{n} + a_{n - 1} x^{n - 1} + \dots + a_{1} x + a_{0} = 0

Real numbers that are not roots of a polynomial like this are called transcendental number.
a. Show that $\sqrt{2}, \sqrt[3]{2}, \sqrt{3} + \sqrt{2}$ are algebraic.
b. Fix $n \in N$ and let $A_{n}$ be the algebraic numbers obtained as roots of polynomials with integer coefficients that have degree $n$ . Using the fact that every polynomial has a finite number of roots, show that $A_{n}$ is countable.
c. Now, argue that the set of all algebraic numbers is countable. What may we conclude about the set of transcendental numbers?

Proof
a. $\sqrt{2}$ is a solution to $x^{2} - 2 = 0$ . $\sqrt[3]{2}$ is a solution to $x^{3} - 2 = 0$ .
Also $x^{4} - 10 x^{2} + 19 = 0$ has the solution of $\sqrt{3} + \sqrt{2}$ .

b. We'll show $N \sim N^{n} \sim Z^{n} \sim A_{n}$ .
i. $N \sim N^{n}$ for all $n \in N$ since if we define the sets $B_{i, j} = {(k_{1}, . . ., k_{n}) | \forall k_{m} \neq k_{i} (k_{m} = 0) \land k_{i} = j}$ then $B_{i, j}$ is a countable set clearly. Thus then $N^{n} = ⋃_{j = 1}^{\infty} ⋃_{i = 1}^{n} B_{i, j}$ then $N^{n}$ is countable.
ii. Since $N \sim Z$ then the bijection $g : N \to Z$ exists. Then applying $g$ in a piecewise fashion to define $f : N^{n} \to Z^{n}$ shows that $f$ is a bijection as a result.
iii. Use the bijection $h : Z^{n} \to A_{n}$ by choosing the $Z^{n}$ entries to be the polynomials integer coefficients. Clearly $h$ is a bijection since each polynomial has a $Z^{n}$ vector we can construct, and vice versa (surjective), and two polynomials with the same coefficients have the same roots (injective).

c. The set of all algebraic numbers is just $A = ⋃_{n = 1}^{\infty} A_{n}$ so then $A$ is countable. As a result, since $R = A \cup A^{'}$ and $A^{'}$ are all the transcendentals, since $R$ is uncountable then we must have it that $A^{'}$ is uncountable. So there are way more transcendentals than algebraic numbers.
☐

1.5.10 (I did a wrong)

Question

a. Let $C \subseteq [0, 1]$ be uncountable. Show that there exists $a \in (0, 1)$ such that $C \cap [a, 1]$ is uncountable.
b. Now let $A$ be the set of all $a \in (0, 1)$ such that $C \cap [a, 1]$ is uncountable, and set $α = sup A$ . Is $C \cap [α, 1]$ an uncountable set?
c. Does the statement in (a) remain true if 'uncountable' is replaced by "infinite"?

Proof
a.
Choose $a = \frac{1}{2}$ . Then:

C \cap [a, 1] = [0, 1] \cap [\frac{1}{2}, 1] = [\frac{1}{2}, 1]

the set $[\frac{1}{2}, 1] \supseteq (\frac{1}{2}, 1) \sim R$ so then since $R$ is uncountable then $[\frac{1}{2}, 1]$ must be uncountable. Thus then $C \cap [a, 1]$ is uncountable.

A = {a \in (0, 1) | C \cap [a, 1] is uncountable}

Notice in general for any $a \in (0, 1)$ that:

C \cap [a, 1] = [0, 1] \cap [a, 1] = [a, 1]

Notice $[a, 1]$ is always uncountable since $[a, 1] \supseteq (a, 1) \sim R$ . Thus then $C \cap [a, 1]$ is uncountable.

As a result then $A = (0, 1)$ , so then $α = sup A = 1$ .
☐