Differences

This shows you the differences between two versions of the page.

--- math104-f21:hw5 [2021/09/25 23:34]
pzhou
+++ math104-f21:hw5 [2026/02/21 14:41] (current)
@@ Line 12: / Line 12: @@
 . Prove that the set of maps $\{f: \N \to \{0,1\}\}$ is not countable.
+===== Solution =====
+. Let $(a_n)$ be any sequence that enumerate of $\Q$. For any $x \in \R$, to show that $x$ is a subsequential limit of $a_n$, we only need to show that for any $\epsilon>0$ and $N>0$, there is a $n>N$, with $|a_n - x| < \epsilon$. Suppose there is no such an $n$, i.e., for all $n > N$, we have $|a_n - x|>\epsilon$, then that means there are at most $N$ rational numbers within $[x-\epsilon, x+\epsilon]$, which is absurd.
+. Let $A_n = \sup \{ a_m | m \geq n\}$, and $B_n = \sup \{ b_m | m \geq n\}$, and $C_n = \sup \{a_m + b_m \mid m \geq n\}$. We claim that $C_n \leq A_n + B_n$. Indeed, for any $m \geq n$, $a_m + b_m \leq A_n + B_n$, hence $A_n + B_n$ is an upper bound of the set $\{a_m + b_m \mid m \geq n\}$, thus $C_n \leq A_n + B_n$. Hence, taking limit $n\to \infty$, we get $\lim_n C_n \leq \lim A_n + \lim B_n$.
+. To enumerate $\Z$, we can do $0,  1, -1,  + 2, -2,  \cdots $.
+To enumerate $\Z^2$, we define a function $f: \Z^2 \to \N$, $f(a,b) = |a| + |b|$. For $n \in \N$, let  $A_n = f^{-1}(n) = \{(a,b) \in \Z^2 \mid |a|+|b|=n\}$. Then $\Z^2 = \sqcup_{n \in \N} A_n$, and each $A_n$ is a finite set. We can enumerate $A_0$, then $A_1$, ...
+. Let $P_n$ denote the set of integer coefficient polynomials of at most degree $n$,  $P_n = \{a_0 + a_1 x + \cdots + a_n x \mid a_i \in \Z \}$. Then the set of integer coefficient polynomial $P = \cup_{n=0}^n P_n$, each each $P_n = \Z^{n+1}$. Since finite product of countable set is countable, we have $P_n$ is countable for all $n$. Since countable union of countable sets are countable, we have $P$ being countable.
+. This is done is class. See Rudin Thm 2.14.
+{{math104-f21:pasted:20211001-220110.png}}

Lecture Notes

User Tools

Site Tools

Differences

Page Tools