30 - Uncountable sets

!Screenshot 2023-11-17 at 3.09.40 PM.png
!Screenshot 2023-11-18 at 2.58.25 PM.png
!Screenshot 2023-11-18 at 2.58.20 PM.png
!Screenshot 2023-11-18 at 2.57.53 PM.png
\mathfrak{c} = $c$

HW 30

Ben Finch

E 30.1
The function $f (x) = a + (b - a) x$ takes an input $x$ from the interval (0, 1) and maps it to the interval (a, b).

(Injective)
Assume $f (x_{1}) = f (x_{2})$ . Substituting the function, we get $a + (b - a) x_{1} = a + (b - a) x_{2}$ .
Simplifying, $(b - a) x_{1} = (b - a) x_{2}$ . Since $a < b$ , $b - a$ is non-zero, we can divide by $b - a$ to get $x_{1} = x_{2}$ . Thus, the function is injective.

(Surjective)
Let $y \in$ (a, b). We want to show there exists an $x \in (0, 1)$ such that $f (x) = y$ .

Define $x = \frac{y - a}{b - a}$ . Note that since $y$ is in (a, b), $a < y < b$ , and hence $0 < \frac{y - a}{b - a} < 1$ . Thus, $x$ is in the interval (0, 1). We find:

\begin{aligned} f (x) & = a + (b - a) x \\ = a + (b - a) (\frac{y - a}{b - a}) \\ = a + \frac{(b - a) (y - a)}{b - a} \\ = a + y - a \\ = y \end{aligned}

Since for every $y$ in (a, b), there exists an $x$ in (0, 1) such that $f (x) = y$ , $f$ is surjective.

Since $f$ is injective and surjective, $f$ is bijective. $◻$

E 30.2
Define the bijection $f : [0, 1) \to (0, 1)$ as follows:

Map 0 to 1/2.
Map 1/2 to 1/3.
Map 1/3 to 1/4, and so on, in general mapping $1 / n$ to $1 / (n + 1)$ for all positive integers $n$ .
For all other $x \in [0, 1)$ that are not of the form $1 / n$ (rational), map $x$ to itself.

This function is injective because each element in $[0, 1)$ maps to a unique element in $(0, 1)$ . It is also surjective because every element in $(0, 1)$ either is an image of an element in $[0, 1)$ not of the form $1 / n$ , or is the image of some $1 / n$ .

Thus $| [0, 1) | = | (0, 1) | = c$ .

$◻$

E 30.3
Define a function $f : [0, 1] \to (0, 1)$ as follows:

f (x) = {\begin{cases} \frac{1}{n + 2} & if x = \frac{1}{n + 1} for some natural number n \\ x & if x \neq \frac{1}{n + 1} for any natural number n \\ \frac{1}{2} & if x = 0 \end{cases}

(injective)
If $f (x) = f (y)$ for some $x$ and $y$ in $[0, 1]$ , then either both $x$ and $y$ are of the form $\frac{1}{n + 1}$ for some $n$ , or neither of them is, or both are equal to 0. If both $x$ and $y$ are of the form $\frac{1}{n + 1}$ , then $f (x) = f (y)$ implies $\frac{1}{n + 2} = \frac{1}{n + 2}$ , which is true. In this case, $x$ and $y$ are the same. If both $x$ and $y$ are not of the form $\frac{1}{n + 1}$ for any $n$ and are also not equal to 0, then $f (x) = f (y)$ implies $x = y$ , as both are equal to themselves. In this case, $x$ and $y$ are the same. If both $x$ and $y$ are equal to 0, then $f (x) = f (y)$ implies $\frac{1}{2} = \frac{1}{2}$ , which is true. In this case, $x$ and $y$ are the same. Therefore, $f$ is injective.

(surjective)
For any $y$ in $(0, 1)$ , if $y$ is not of the form $\frac{1}{n + 2}$ for any natural number $n$ , then there exists $x$ in $[0, 1]$ such that $f (x) = y$ (since $f (y) = y$ for these values). If $y$ is of the form $\frac{1}{n + 2}$ for some $n$ , then $y = \frac{1}{n + 2}$ will be in $(0, 1)$ . So, for these values as well, there exists $x$ in $[0, 1]$ such that $f (x) = y$ . For $y = \frac{1}{2}$ , we have $f (0) = \frac{1}{2}$ , so the value 0 is correctly mapped to $\frac{1}{2}$ . Therefore, $f$ is surjective.

Since $f$ is both injective and surjective, it is a bijection, so $[0, 1]$ and $(0, 1)$ have the same cardinality, proving that the interval $[0, 1]$ has continuum cardinality. $◻$

E 30.4
Assume by way of contradiction that the set of irrational numbers ( $R - Q$ ) is countable. We know $R = Q \cup R - Q$ . By Corollary 29.7, $Q$ is countable. If both $Q$ and $R - Q$ are countable, then by Theorem 29.1, their union, which is $R$ , should also be countable. However, this is a contradiction, since by Corollary 30.5, $R$ is uncountable. Thus the set of irrational numbers is not countable. $◻$

An example of a subset of the irrational numbers that is countably infinite is the set $S = {\sqrt{2} \cdot x : x \in N}$ .

E 30.5
For all $r \in R$ we have $r = r + 0 i \in C$ . So $R \subseteq C$ . By Collary 30.5, $R$ is uncountable. Thus by theorem 30.7, $C$ must be uncountable. $◻$

E 30.6
Proof.
Assume, by way of contradiction, that the set of all infinite sequences of 0's and 1's, denoted by $\prod_{i = 1}^{\infty} {0, 1}$ , is countable. Then we can list all sequences in the form of $S_{1}, S_{2}, S_{3}, \dots$ where each $S_{i}$ is an infinite sequence of 0's and 1's.

Construct a new sequence $S$ by selecting the $i$ th digit of $S_{i}$ for each $i$ and flipping it (i.e., if the digit is 0, change it to 1, and if it is 1, change it to 0). The resulting sequence $S$ will differ from each $S_{i}$ in the list at the $i$ th position, ensuring that $S$ is not equal to any sequence in the list.

This new sequence $S$ cannot be part of our original list because it was constructed to have at least one digit different from every sequence in the list. This contradicts our assumption that the set of all sequences was countable, as we have found a sequence not included in our list.

Hence, the assumption that $\prod_{i = 1}^{\infty} {0, 1}$ is countable must be false, implying that the set is indeed uncountable. $◻$