城南讲马堂

陶哲轩实分析8.3及习题-Analysis I 8.3

2019年4月30日2019年12月13日christangdt留下评论

这一节主要说不可数集合的问题。

Exercise 8.3.1. Let $X$ be a finite set of cardinality $n$ . Show that $2^X$ is a finite set of cardinality $2^n$ .
Solution: If $n=0$ then $X=\emptyset$ and the only element in $2^X$ is $\emptyset$ , so the cardinality of $2^X$ is $2^0=1$ .
Now suppose the statement holds for $n$ , let $X$ be a finite set of cardinality $n+1$ , since $n+1\geq 1,X\neq \emptyset$ , so choose $x\in X$ , then set $X\backslash \{x\}$ has cardinality $n$ , and $2^{X\backslash \{x\}}$ has cardinality $2^n$ . For any set $S\in 2^X \backslash 2^{X\backslash \{x\}}$ , $S$ is a subset of $X$ which contains $x$ . Thus we can see that

$\forall S'\in 2^{X\backslash \{x\}} \implies S'\cup \{x\}\in 2^X\backslash 2^{X\backslash \{x\}}$

And the converse is also true, thus the cardinality of $2^{X\backslash \{x\}}$ equals the cardinality of $2^X\backslash 2^{X\backslash \{x\}}$ , then we have $2^X\backslash 2^{X\backslash \{x\}}$ has cardinality $n$ . Finally, from $2^{X\backslash \{x\}}\cup 2^X\backslash 2^{X\backslash \{x\}}=2^X$ and $2^{X\backslash \{x\}}\cap2^X\backslash 2^{X\backslash \{x\}}=\emptyset$ we have

$\#(2^X)=\#(2^{X\backslash \{x\}} )+\#(2^X\backslash 2^{X\backslash \{x\}} )=2^n+2^n=2^{n+1}$

$\blacksquare$

Exercise 8.3.2. Let $A,B,C$ be sets such that $A\subseteq B\subseteq C$ , and suppose that there is a injection $f:C\to A$ . Define the sets $D_0,D_1,D_2,\dots$ recursively by setting $D_0:=B\backslash A$ , and then $D_{n+1}:=f(D_n)$ for all natural numbers $n$ . Prove that the sets $D_0,D_1,\dots$ are all disjoint from each other (i.e., $D_n\cap D_m =\emptyset$ whenever $n\neq m$ ). Also show that if $g:A\to B$ is the function defined by setting $g(x):=f^{-1}(x)$ when $x\in \bigcup_{n=1}^{\infty}D_n$ , and $g(x):=x$ when $x\notin \bigcup_{n=1}^{\infty}D_n$ , then $g$ does indeed map $A$ to $B$ and is a bijection between the two. In particular, $A$ and $B$ have the same cardinality.
Solution: We can see that $D_0\cap A=\emptyset,D_i\subseteq A,\forall i\geq 1$ , if we assume there’s $d\in D_n\cap D_m,m\neq n$ , we can safely assume $m<n$ , then $\exists d_{m-1}\in D_{m-1},d_{n-1}\in D_{n-1}$ , s.t.

$f(d_{m-1})=f(d_{n-1})=d \implies d_{m-1}=d_{n-1}$

So we can have

$D_n\cap D_m\neq \emptyset \implies D_{n-1}\cap D_{m-1}\neq \emptyset$

Continue for $m-1$ times we would get $D_{n-m}\cap D_0\neq \emptyset$ , which is a contradiction.
Now if $g$ is defined as above, notice that $\bigcup_ {n=1}^{\infty}D_n \subseteq A$ , and if $x\in \bigcup_{n=1}^{\infty}D_n$ , we shall have $f^{-1} (x)\in \bigcup_{n=0}^{\infty}D_n \subseteq B$ , if $x\notin \bigcup_{n=1}^{\infty}D_n$ we have $g(x)=x$ . So g does map $A$ to $B$ .
To prove $g$ is a bijection:
First suppose $g(a)=g(b)$ , if $a,b\notin \bigcup_{n=1}^{\infty}D_n$ we directly get $g(a)=a=b=g(b)$ . If $a,b\in \bigcup_{n=1}^{\infty}D_n$ we have $f^{-1} (a)=f^{-1} (b)$ , thus

$f(f^{-1} (a))=f(f^{-1} (b)) \implies a=b$

The case that $a\in \bigcup_{n=1}^{\infty}D_n$ and $b\notin \bigcup_{n=1}^{\infty}D_n$ is impossible, assume so, then $g(a)=f^{-1} (a)\in \bigcup_{n=0}^{\infty}D_n =(B\backslash A)\cup (\bigcup_{n=1}^{\infty}D_n )$ , and $g(b)=b$ , so we have $b\in (B\backslash A)\cup (\bigcup_{n=1}^{\infty}D_n )$ , since $b\in A$ , we can’t have $b\in B\backslash A$ , then $b\in \bigcup_{n=1}^{\infty}D_n$ , which is a contradiction. The case that $a\notin \bigcup_{n=1}^{\infty}D_n$ and $b\in \bigcup_{n=1}^{\infty}D_n$ is impossible by the same logic. So we finished proving g is an injection.
Next, let any $b\in B$ , we must have one and only one of the two cases valid:

$b\in \bigcup_{n=0}^{\infty}D_n ,\quad b\notin \bigcup_{n=0}^{\infty}D_n$

If $b\in \bigcup_{n=0}^{\infty}D_n$ , then let $x=f(b)\in \bigcup_{n=1}^{\infty}D_n$ , we have $g(x)=f^{-1} (x)=b$ .
If $b\notin \bigcup_{n=0}^{\infty}D_n$ , we must have $b\in A$ since $B\backslash (\bigcup_{n=0}^{\infty}D_n )=A\backslash (\bigcup _{n=1}^{\infty}D_n)\subseteq A$ , we let $x=b$ , then $g(x)=x=b$ . We finished proving $g$ is a surjection.

$\blacksquare$

Exercise 8.3.3. Recall from Exercise 3.6.7 that a set $A$ is said to have lesser or equal cardinality than a set $B$ iff there is an injective map $f:A\to B$ from $A$ to $B$ . Using Exercise 8.3.2, show that if $A,B$ are sets such that $A$ has lesser or equal cardinality to $B$ and $B$ has lesser or equal cardinality to $A$ , then $A$ and $B$ have equal cardinality. (This is known as the Schröder-Bernstein theorem.)
Solution: Let $f:A\to B$ and $g:B\to A$ be injections, we can have $f(A)\subseteq B$ and $g(B)\subseteq A$ , thus $B\subseteq g^{-1} (A)$ . We can see that $f\circ g$ is an bijection from $g^{-1} (A)$ to $f(A)$ . Let

$D_0=B\backslash f(A),\quad D_{n+1}=f(g(D_n))$

Then the sets $D_0,D_1,D_2,\dots$ are disjoint from each other. Let $h:f(A)\to B$ be defined by setting $h(x):=g^{-1} (f^{-1}(x))$ if $x\in \bigcup_{n=1}^{\infty}D_n$ , and $h(x):=x$ if $x\notin \bigcup_{n=1}^{\infty}D_n$ , then due to Exercise 8.3.2, $h$ is a bijection, so $\text{card}(B)=\text{card}(f(A))=\text{card}(A)$ .

$\blacksquare$

Exercise 8.3.4. Let us say that a set $A$ has strictly lesser cardinality than a set $B$ if $A$ has lesser or equal cardinality to $B$ , but $A$ does not have equal cardinality to $B$ . Show that for any set $X$ , that $X$ has strictly lesser cardinality than $2^X$ . Also, show that if $A$ has strictly lesser cardinality than $B$ , and $B$ has strictly lesser cardinality than $C$ , then $A$ has strictly lesser cardinality than $C$ .
Solution: We can find an injection $f:X\to 2^X$ by $f(x)=\{x\}$ , thus $X$ has lesser than or equal cardinality to $2^X$ , and due to Theorem 8.3.1, $X$ doesn’t have equal cardinality to $2^X$ .
To prove the second statement, we can find injections $f:A\to B$ and $g:B\to C$ , thus $f\circ g:A\to C$ is an injection, thus $\text{card}(A)\leq \text{card}(C)$ , now suppose $A$ has equal cardinality to $C$ , then $\text{card}(C)=\text{card}(A)\leq \text{card}(B)$ , combined with $\text{card}(B)\leq \text{card}(C)$ we get $\text{card}(C)=\text{card}(B)$ from Exercise 8.3.3, this is a contradiction since $B$ has strictly lesser cardinality than $C$ .

$\blacksquare$

Exercise 8.3.5. Show that po power set (i.e., a set of the form $2^X$ for some set $X$ ) can be countably infinite.
Solution: If $X$ is finite, then from Exercise 8.3.1 we know that $2^X$ is finite.
If $X$ is countable, then $\text{card}(X)=\text{card}(\mathbf N)$ , from Cantor’s Theorem we know that $\text{card}(2^X )>\text{card}(X)=\text{card}(\mathbf N)$ , so $2^X$ is uncountable.
If $X$ is uncountable, then $\text{card}(2^X )>\text{card}(X)>\text{card}(N)$ , so $2^X$ is uncountable.

$\blacksquare$

陶哲轩实分析8.2及习题-Analysis I 8.2

2019年4月29日2020年8月17日christangdt32条评论

这一节的逻辑构成是这样的：先定义了在countable集合上的级数，并且在绝对收敛下有Fubini定理成立，而后在uncountable集合上也可以定义级数，只要满足任何有限集合的sup存在。如果f是一个定义在uncountable集合上的绝对收敛级数，那么f非退化的点是至多可数的（证明需要用选择公理）。绝对收敛级数有很好理解的series laws，条件收敛级数则有Riemann的结论：可以收敛到任何实数L。这一节的习题主要是完善正文中的定理证明，然而也不易。

Exercise 8.2.1. Prove Lemma 8.2.3.
Lemma 8.2.3. Let $X$ be an at most countable set, and let $f:X\to\mathbf R$ be a function. Then the series $\sum_{x\in X}f(x)$ is absolutely convergent if and only if

$\sup \left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A \text{ finite}\right\}<\infty$

Solution: Exercise 3.6.3 says if there’s a function whose domain is on a finite subset of $\mathbf N$ , then the range of this function is also finite. I’ll use this result later.
Since $X$ is at most countable, $X$ may be finite or countable. If $X$ is finite, then the statement is obviously true. Now we consider the case when $X$ is countable.
First suppose the series $\sum_{x\in X}f(x)$ is absolutely convergent, then there’s a bijection $g:\mathbf N\to X$ such that $\sum_{n=0}^{\infty}f(g(n))$ is absolutely convergent. Given any element $E$ in the set

$S=\left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\right\}$

We know there’s a finite set $A$ such that $E=\sum_{x\in A}|f(x)|$ . So we can have a finite subset $S'$ of $N$ such that $g(S')=A$ , from Exercise 3.6.3 we can have $S'$ is bounded above by some natural number $k$ , so

$E=\sum\limits_{x\in A}|f(x)| =\sum\limits_{n\in S'}|f(g(n))| \leq \sum\limits_{n=0}^k|f(g(n))| \leq \sum\limits_{n=0}^{\infty}|f(g(n))|$

Since this is true for all $E$ , we know that $\sum_{n=0}^{\infty}|f(g(n))|$ is an upper bound of $S$ , so

$\sup S\leq \sum\limits_{n=0}^{\infty}|f(g(n))| <+{\infty}$

On the contrary, if $M=\sup\{\sum_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\}<+{\infty}$ , we assume the series $\sum_{x\in X}f(x)$ is not absolutely convergent, then given a bijection $g:\mathbf N\to X$ , we have $S_N=\sum_{n=0}^N|f(g(n))|$ is not bounded above, so there exists a $k\in \mathbf N$ such that $\sum_{n=0}^k|f(g(n))| >M$ , we let $A=g(\{n:0\leq n\leq k\})$ , then $A$ is finite, and

$\sum\limits_{n=0}^k|f(g(n))| =\sum\limits_{x\in A}|f(x)| >M$

This leads to a contradiction.

$\blacksquare$

Exercise 8.2.2. Prove Lemma 8.2.5.
Lemma 8.2.5. Let $X$ be a set (which could be uncountable), and let $f:X\to\mathbf R$ be a function such that the series $\sum_{x\in X}f(x)$ is absolutely convergent. Then the set $\{x\in X:f(x)\neq 0\}$ is at most countable.
Solution: Since $\sum_{x\in X}f(x)$ is absolutely convergent, the quantity

$M:=\sup \left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A \text{ finite}\right\}$

is well defined. For $\forall n\in \mathbf N$ , consider the set $\{x\in X:|f(x)|>1/n\}$ , this set is finite with cardinality at most $Mn$ , thus use Exercise 8.1.9, we know that

$\{x\in X:f(x)\neq 0\}=\bigcup _{n=1}^{\infty}\{x\in X:|f(x)|>1/n\}$

is at most countable.

$\blacksquare$

Exercise 8.2.3. Prove Proposition 8.2.6.
Solution: Since both $\sum_{x\in X}f(x)$ and $\sum_{x\in X}g(x)$ are absolutely convergent, the sets $S=\{x\in X:f(x)\neq 0\}$ and $B=\{x\in X:g(x)\neq 0\}$ are at most countable. We denote $\sum_{x\in X}f(x)=L$ and $\sum_{x\in X}g(x)=M$ .

( a ) $\sum_{x\in X}(f(x)+g(x))$ is absolutely convergent and

$\sum\limits_{x\in X}(f(x)+g(x))=\sum\limits_{x\in X}f(x)+\sum\limits_{x\in X}g(x)$

Solution: Let $A\subseteq X$ be a finite set, then by proposition 7.1.11 we have

$\begin{aligned}\sum\limits_{x\in A} |f(x)+g(x)| &\leq \sum\limits_{x\in A}|f(x)| +\sum\limits_{x\in A}|g(x)| \\&\leq \sup \left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\right\}+\sup \left\{\sum\limits_{x\in A}|g(x)|:A\subseteq X,A\text{ finite}\right\}\\&<{\infty}\end{aligned}$

which means

$\begin{aligned}&\sup \left\{\sum\limits_{x\in A}|f(x)+g(x)|:A\subseteq X,A\text{ finite}\right\}\\ \leq&\sup \left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\right\}+\sup \left\{\sum\limits_{x\in A}|g(x)|:A\subseteq X,A\text{ finite}\right\}\end{aligned}$

Use Definition 8.2.4 we know that $\sum_{x\in X}(f(x)+g(x))$ is absolutely convergent. Thus

$\sum\limits_{x\in X}(f(x)+g(x)) =\sum\limits_{x\in X,f(x)+g(x)\neq 0} (f(x)+g(x)) =\sum\limits_{x\in S\cup B} (f(x)+g(x))$

$S\cup B$ is at most countable, if $S\cup B$ is finite we can use Proposition 7.1.11(f) to get

$\sum\limits_{x\in S\cup B} (f(x)+g(x)) =\sum\limits_{x\in S\cup B} f(x)+\sum\limits_{x\in S\cup B} g(x) =\sum\limits_{x\in S} f(x) +\sum\limits_{x\in B} g(x)$

If $S\cup B$ is countable, we can have a bijection $h:\mathbf N\to S\cup B$ , s.t.

$\sum\limits_{x\in S\cup B} (f(x)+g(x)) =\sum\limits_{n=0}^{+{\infty}}\bigg(f\Big(h(n)\Big)+g\Big(h(n)\Big)\bigg)$

Let $S_N=\sum_{n=0}^N\bigg(f\Big(h(n)\Big)+g\Big(h(n)\Big)\bigg) =\sum_{n=0}^Nf(h(n)) +\sum_{n=0}^Ng(h(n))$ , we know that when $N\to {\infty}$ , $\sum_{n=0}^Nf(h(n)) \to L$ since $A\subseteq A\cup B$ , by the same logic, $\sum_{n=0}^Ng(h(n)) \to M$ , thus the conclusion is valid.

( b ) If $c$ is a real number, then $\sum_{x\in X}cf(x)$ is absolutely convergent, and

$\sum\limits_{x\in X}cf(x)=c\sum\limits_{x\in X}f(x)$

Solution: If $c=0$ the conclusion is obviously true. Now suppose $c\neq 0$ , Let $A\subseteq X$ be a finite set, then by proposition 7.1.11 we have

$\sum\limits_{x\in A}|cf(x)| =|c| \sum\limits_{x\in A}|f(x)| \leq |c| \sup \left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\right\}<{\infty}$

Thus

$\sup \left\{\sum\limits_{x\in A}|cf(x)|:A\subseteq X,A\text{ finite}\right\}\leq |c| \sup \left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\right\}<{\infty}$

Use Definition 8.2.4 we know that $\sum_{x\in X} cf(x)$ is absolutely convergent. Since we also have $(f(x)\neq 0)\iff (cf(x)\neq 0)$ , we know that

$\sum\limits_{x\in X} cf(x) = \sum\limits_{x\in X,cf(x)\neq 0} cf(x) =\sum\limits_{x\in S} cf(x)$

If $S$ is finite, use Proposition 7.1.11(g) we have $\sum_{x\in S} cf(x) =c\sum_{x\in S} f(x) =c\sum_{x\in X} f(x)$ . If $S$ is countable, we can have a bijection $h:\mathbf N\to S$ , s.t.

$\sum\limits_{x\in S} cf(x) =\sum\limits_{n=0}^{+{\infty}}cf(h(n)) =c\sum\limits_{n=0}^{+{\infty}}f(h(n))$

The last equality comes from Proposition 7.2.14(b).

( c ) If $X=X_1\cup X_2$ for some disjoint sets $X_1$ and $X_2$, then $\sum_{x\in X_1}f(x)$ and $\sum_{x\in X_2}f(x)$ are absolutely convergent, and

$\sum\limits_{x\in X_1\cup X_2}f(x)=\sum\limits_{x\in X_1}f(x)+\sum\limits_{x\in X_2}f(x)$

Conversely, if $h:X\to \mathbf R$ is such that $\sum_{x\in X_1}h(x)$ and $\sum_{x\in X_2}h(x)$ are absolutely convergent, then $\sum_{x\in X_1\cup X_2}h(x)$ is also absolutely convergent, and

$\sum\limits_{x\in X_1\cup X_2}h(x)=\sum\limits_{x\in X_1}h(x)+\sum\limits_{x\in X_2}h(x)$

In the first case, let $A\subseteq X_1$ be any finite set, then $A\subseteq X$ , thus

$\sum\limits_{x\in A}|f(x)| \leq \sup\left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\right\}$

Which gives

$\sup \left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X_1,A\text{ finite} \right \} \leq \sup\left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\right\}$

So $\sum_{x\in X_1}f(x)$ is absolutely convergent.
By the same logic $\sum_{x\in X_2}f(x)$ is absolutely convergent.
Conversely, if $\sum_{x\in X_1} h(x)$ and $\sum_{x\in X_2} h(x)$ are absolutely convergent. Then for any finite set $A\subseteq X$ , we can have $A=(A\cap X_1 )\cup (A\cap X_2)$ , as $X_1$ and $X_2$ are disjoint, we have

$\begin{aligned} \sum_{x\in A}|f(x)| &=\sum\limits_{x\in A\cap X_1}|f(x)| +\sum\limits_{x\in A\cap X_2}|f(x)| \\&\leq \sup\left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X_1,A\text{ finite}\right\}+\sup\left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X_2,A\text{ finite}\right\}\end{aligned}$

Then we have

$\begin{aligned}&\sup\left\{\sum\limits_{x\in A}|f(x)|:A\subseteq (X_1\cup X_2),A\text{ finite}\right\} \\ \leq &\sup\left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X_1,A\text{ finite}\right\}+\sup\left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X_2,A\text{ finite}\right\}\\ <&\infty\end{aligned}$

To prove $\sum_{x\in X_1\cup X_2}f(x) =\sum_{x\in X_1} f(x) +\sum_{x\in X_2} f(x)$ , we only need to consider points where $f$ doesn’t vanish on, thus redefine

$X=\{x\in X:f(x)\neq 0\},\\X_1=\{x\in X_1:f(x)\neq 0\},\\X_2=\{x\in X_2:f(x)\neq 0\}$

we first see the case is clear when $X=X_1\cup X_2$ is finite. Now if one is countable and the other is finite, we may assume $X_2$ is finite, then there’s bijections $g_1:\mathbf N\to X_1$ and $g_2:\{i\in \mathbf N:0\leq i\leq m\}\to X_2$ , such that

$\sum\limits_{x\in X_1} f(x) =\sum\limits_{n=0}^{\infty}f\Big(g_1 (n)\Big) ,\quad \sum\limits_{x\in X_2} f(x) =\sum\limits_{n=0}^mf\Big(g_2 (n)\Big)$

We define a bijection $g:\mathbf N\to X_1\cup X_2$ by

$g(n)=\begin{cases}g_2 (n),&n\leq m\\g_1 (n-m-1),&n>m\end{cases}$

Then $\sum_{x\in X_1\cup X_2} f(x)=\sum_{n=0}^{\infty}f\Big(g(n)\Big)$ , further we have for any $N\in \mathbf N$ :

$\sum\limits_{n=0}^{N+m}f\Big(g(n)\Big) =\sum\limits_{n=0}^mf\Big(g_2 (n)\Big) +\sum\limits_{n=0}^Nf\Big(g_1 (n)\Big)$

Let $N\to +{\infty}$ , we get the conclusion.
If both sets are countable, there’s bijections $g_1:\mathbf N\to X_1$ and $g_2:\mathbf N\to X_2$ such that

$\sum\limits_{x\in X_1} f(x) =\sum\limits_{n=0}^{\infty}f(g_1 (n)) ,\quad \sum\limits_{x\in X_2} f(x) =\sum\limits_{n=0}^{\infty}f(g_2 (n))$

We define a bijection $g:\mathbf N\to X_1\cup X_2$ by

$g(n)=\begin{cases}g_1 (k),&n=2k,k\in N\\g_2 (k),&n=2k+1,k\in N\end{cases}$

Then $\sum_{x\in X_1\cup X_2} f(x) =\sum_{n=0}^{\infty}f(g(n))$ , further we have for any $N\in \mathbf N$ :

$\sum\limits_{n=0}^{2N+1}f(g(n)) =\sum\limits_{n=0}^Nf(g_2 (n)) +\sum\limits_{n=0}^Nf(g_1 (n))$

Let $N\to +{\infty}$ , we get the conclusion.
The statement of $h(x)$ can then be derived by substituting $f$ to $h$ .

( d ) If $Y$ is another set, and $\phi:Y\to X$ is a bijection, then $\sum_{y\in Y}f(\phi(y))$ is absolutely convergent, and

$\sum\limits_{y\in Y}f(\phi(y))=\sum\limits_{x\in X}f(x)$

Solution: First we prove $\sum_{y\in Y}f(\phi (y))$ is absolutely convergent. Choose any finite $A\subseteq Y$ , as $\phi$ is a bijection, $\phi (A)\subseteq X$ is finite. Let

$L=\sup \left\{\sum\limits_{x\in A}|f(x)|:A\subseteq X,A\text{ finite}\right\}<{\infty}$

Then $\sum_{y\in A}|f(\phi (y))| =\sum_{\phi (y)\in \phi (A)}|f(\phi (y))| \leq L$ , so

$\sup \left\{\sum\limits_{y\in A}|f(\phi (y))|:A\subseteq Y,A\text{ finite}\right\}\leq L<{\infty}$

Next, to prove $\sum_{y\in Y}f(\phi (y)) =\sum_{x\in X} f(x)$ , we see that for any $y\in Y$ such that $f(\phi (y))\neq 0$ , we can choose one $x=\phi (y)\in X$ such that $f(x)\neq 0$ , vice versa.(In this step we use the Axiom of Choice if $Y$ and $X$ are uncountable) Thus the sets $\{y\in Y: f(\phi (y))\neq 0\}$ and $\{x\in X:f(x)\neq 0\}$ have the same cardinality, thus are both finite or countable. In the finite case the statement is obviously true by Proposition 7.1.11( c ). If both sets are countable, we let a bijection $g:\mathbf N\to \{y\in Y: f(\phi (y))\neq 0\}$ , then $\phi \circ g:\mathbf N\to \{x\in X:f(x)\neq 0\}$ is also a bijection, and we have

$\sum\limits_{y\in Y}f(\phi (y)) =\sum\limits_{n=0}^{\infty}f(\phi (g(n))) \\ \sum\limits_{x\in X} f(x) =\sum\limits_{n=0}^{\infty}f(\phi \circ g(n)) =\sum\limits_{n=0}^{\infty}f(\phi (g(n)))$

Then we have $\sum_{y\in Y}f(\phi (y)) =\sum_{x\in X} f(x)$ .

$\blacksquare$

Exercise 8.2.4. Prove Lemma 8.2.7.
Lemma 8.2.7. Let $\sum_{n=0}^{\infty}a_n$ be a series of real numbers which is conditionally convergent, but not absolutely convergent. Define the sets $A_+:=\{n\in \mathbf N:a_n\geq 0\}$ and $A_-:=\{n\in \mathbf N:a_n<0\}$ , thus $A_+\cup A_-=\mathbf N$ and $A_+\cap A_-=\emptyset$ . Then both of the series $\sum_{n\in A_+}a_n$ and $\sum_{n\in A_-}a_n$ are not conditionally convergent (and thus not absolutely convergent).
Solution: Let $\sum_{n=0}^{\infty}a_n =L$ , we also know that $\sum_{n=0}^{\infty}|a_n |$ doesn’t exist. Now assume the conclusion is wrong, then one of the three assertions below must be true:

i. $\sum_{n\in A^+}a_n$ converges, but $\sum_{n\in A^-}a_n$ is not conditionally convergent.
ii. $\sum_{n\in A^-}a_n$ converges, but $\sum_{n\in A^+}a_n$ is not conditionally convergent.
iii. both $\sum_{n\in A^+}a_n$ and $\sum_{n\in A^-}a_n$ converges.

In case i and ii, we know that $\sum_{n=0}^{\infty}a_n =\sum_{n\in A^+}a_n +\sum_{n\in A^-}a_n$ , so we can have $\sum_{n\in A^-}a_n =\sum_{n=0}^{\infty}a_n -\sum_{n\in A^+}a_n$ in case i and $\sum_{n\in A^+}a_n =\sum_{n=0}^{\infty}a_n -\sum_{n\in A^-}a_n$ in case ii, both are contradiction since the left side is not convergent but the right side is convergent.
In case iii, we let $\sum_{n\in A^+}a_n =L_1$ and $\sum_{n\in A^-}a_n =L_2$ , thus we have:

$\sum\limits_{n=0}^{\infty}|a_n |=\sum\limits_{n\in A^+}|a_n |+\sum\limits_{n\in A^-}|a_n |=\sum\limits_{n\in A^+}a_n -\sum\limits_{n\in A^-}a_n =L_1-L_2$

which is a contradiction to the fact that $\sum_{n=0}^{\infty}|a_n |$ doesn’t exist. Thus the original conclusion must be true.

$\blacksquare$

Exercise 8.2.5. Explain the gaps marked (why?) in the proof of Theorem 8.2.8.
Solution:
Why1: $A^+$ and $A^-$ are infinite.
Assume not, then one of $A^+$ and $A^-$ are finite, then either $\sum_{n\in A^+}a_n$ or $\sum_{n\in A^-}a_n$ is a finite series, thus must be convergent, a contradiction.

Why2: $\sum_{m=0}^{\infty}a_{f_+ (m)}$ and $\sum_{m=0}^{\infty}a_{f_- (m)}$ are not absolutely convergent.
Since $a_{f_+ (m)}\geq 0,\forall m$ and $a_{f_- (m)}<0,\forall m$ , if we assume $\sum_{m=0}^{\infty}a_{f_+ (m)}$ or $\sum_{m=0}^{\infty}a_{f_- (m)}$ is absolutely convergent, then we can know from Proposition 7.4.3 that $\sum_{m=0}^{\infty}a_{f_+ (m)} =\sum_{n\in A^+}a_n$ or $\sum_{m=0}^{\infty}a_{f_- (m)} =\sum_{n\in A^-}a_n$ , in particular either $\sum_{n\in A^+}a_n$ or $\sum_{n\in A^-}a_n$ is absolute convergent, which is a contradiction.

Why3: The map $j\to n_j$ is injective.
Let $k\neq j$ , then either $k<j$ or $j<k$ , if $k<j$ , the definition of $n_j$ guarantees that $n_j\neq n_k$ . If $k<j$ we can similarly prove $n_k\neq n_j$ , so this map is injective.

Why4: Both Case I and II occur an infinite number of times.
Assume Case I only occurs finite number of times, this means for some $M\in \mathbf N$ , we’ll have

$\sum\limits_{0\leq i<}a_{n_i} \geq L,\quad \forall j>M$

Thus we have $\sum_{0\leq i\leq M}a_{n_i} +\sum_{M<i}a_{n_i} \geq L$ , or $\sum_{M<i}a_{n_i} \geq L-\sum_{0\leq i\leq M}a_{n_i}$ , notice that as $i$ increases, $\sum_{M<i}a_{n_i}$ decreases since all $a_{n_i}<0$ , so $\sum_{M<i}a_{n_i}$ converges, which means $\sum_{n\in A^-}a_n$ converges, a contradiction.
When assume Case II occurs finite number of times, we can prove a contradiction similarly.

Why5: The map $j\to n_j$ is surjective.
For $\forall n\in \mathbf N$ , either $n\in A^+$ or $n\in A^-$ . Assume no $j$ can make $n_j=n$ , this means either Case I or Case II stops at $n$ , so can only occur finite number of times, which is a contradiction.

Why6: $\lim_{j\to {\infty}} a_{n_j}=0$
From Corollary 7.2.6 we have $\lim_{n\to {\infty}} a_{n}=0$ , since both Case I and II occur an infinite number of times, when $j\to {\infty}$ we must have $n_j\to {\infty}$ .

Why7: $\lim_{j\to {\infty}} \sum_{0\leq i<j}a_{n_i} =L$
From Why6 we know that for $\forall \varepsilon>0,\exists J\in \mathbf N$ ,s.t. $|a_{n_j}|<\varepsilon ,(j>J)$ . Start from $n_J$ , we search for a number $K>J$ such that $\sum_{0\leq i<K}a_{n_i} <L$ and $\sum_{0\leq i<K+1}a_{n_i} \geq L$ , this $K$ must exist, otherwise we’ll get a contradiction with Why4.
We denote $S_k=\sum_{0\leq i<k}a_{n_i}$ , notice that:
If $S_k<L$ , we shall add positive $a_{n_i}$ to $S_k$ , the positive adding shall stop once $S_k\geq L$ , so $S_k\leq L+|a_{n_i} |$ , if $k>K>J$ , we can have $S_k\leq L+\varepsilon$ .
If $S_k\geq L$ , we shall add negative $a_{n_i}$ to $S_k$ , the negative adding shall stop once $S_k<L$ , so $S_k>L-|a_{n_i}|$ , if $k>K>J$ , we can have $S_k>L-\varepsilon$ .
Combined we get $|S_k-L|<\varepsilon ,k>K$ , this means $\lim_{k\to {\infty}} S_k=L$ .

$\blacksquare$

Exercise 8.2.6. Let $\sum_{n=0}^{\infty}a_n$ be a series which is conditionally convergent, but not absolutely convergent. Show that there exists a bijection $f:\mathbf N\to\mathbf N$ such that $\sum_{m=0}^{\infty}a_{f(m)}$ diverges to $+\infty$ , or more precisely that

$\liminf\limits_{N\to\infty}\sum\limits_{m=N}^{\infty}a_{f(m)}=\limsup\limits_{N\to\infty}\sum\limits_{m=N}^{\infty}a_{f(m)}=+\infty$ .

Of course, a similar statement holds with $+\infty$ replaced by $-\infty$ .
Solution: We only have to prove $\liminf_{N\to {\infty}}\sum_{m=N}^{\infty}a_f(m) =+{\infty}$ . With the same definition of $A^+$ and $A^-$ in Lemma 8.2.7, we find increasing bijections $f_+:N\to A^+$ and $f_-:N\to A^-$ . We define a sequence $n_0,n_1,n_2,\dots$ of natural numbers recursively as below:
Let $n_0=f_+ (0),n_1=f_- (0)$ . Suppose that $j\geq 2$ is a natural number, and $n_i$ has already be defined for all $i<j$ . Then we let

$k=\max \Big\{n:f_- (n)\in \{n_i:i<j\}\Big\}$

For example, if $j=2$ , then $n_0$ and $n_1$ has been defined, then $k=1$ . Now
(I) If $\sum_{0\leq i<j}a_{n_i} <k$ , we set $n_j=\min\{n\in A^+:n\neq n_i\text{ for all }i<j\}$
(II) If $\sum_{0\leq i<j}a_{n_i}\geq k$ , we set $n_j=\min\{n\in A^-:n\neq n_i\text{ for all }i<j\}$
Intuitively, we compare $\sum_{0\leq i<j}a_{n_i}$ with an increasing $K$ , which increases by $1$ once we add an negative number to the sum. From the proof of Exercise 8.2.5 we can see that

$A^+$ and $A^-$ are infinite.
$\sum_{m=0}^{\infty}a_{f_+ (m)}$ and $\sum_{m=0}^{\infty}a_{f_- (m)}$ are not absolutely convergent.
The map $j\to n_j$ is injective.

And we can prove the following results:

Both Case I and II occur an infinite number of times.

Assume Case I occur only finite number of times, then from some $J$ and $K$ we’ll get $\sum_{0\leq i<J}a_{n_i} \geq K$ and Case II happens infinitely, but as we add negative numbers to $\sum_{0\leq i<J}a_{n_i}$ , we’ll have $\sum_{0\leq i<j}a_{n_i} \leq \sum_{0\leq i<J}a_{n_i}$ , and $K\to {\infty}$ , this will lead to a contradiction since $\sum_{0\leq i<J}a_{n_i}$ is finite.
Assume Case II occur only finite number of times, then from some $J$ and $K$ we’ll get $\sum_{0\leq i<J}a_{n_i} <K$ , and $\sum_{0\leq i<j}a_{n_i}<K\forall j>J$ , this means $\sum_{m=0}^{\infty}a_{f_+ (m)}$ is convergent, a contradiction.

The map $j\to n_j$ is surjective.
$\lim_{j\to {\infty}} a_{n_j}=0$ .

The proofs are similar to that of Exercise 8.2.5.
Finally we shall prove $\lim_{j\to {\infty}} \sum_{0\leq i<j}a_{n_i}>M$ for any $M>0$ , thus complete the proof. For any $M>0$ , we can find a natural number $K>M$ , and as $\lim_{j\to {\infty}} a_{n_j}=0$ , there’s $J$ such that

$|a_{n_j} |<1,\quad \forall j\geq J$

We’ll eventually find a $j'>J$ such that $\sum_{0\leq i<j'}a_{n_i} \geq K+1$ , and adding negative $a_{n_i}$ to the sum would not let the new sum falls below $K$ , once the sum is between $K$ and $K+1$ , we would continue to add positive $a_{n_i}$ and push the sum to $K+2$ and even larger, thus we have $\sum_{0\leq i<j}a_{n_i} \geq K>M,\forall j>j'$ , and the conclusion follows.

$\blacksquare$

陶哲轩实分析8.1及习题-Analysis I 8.1

2019年4月28日2020年2月14日christangdt7条评论

以我相对平庸的智商来说，Analysis I 的第8章是整本书中相对比较难的章节之一，由于（以个人的理解）这章实际是将集合论和实分析的起步阶段内容都介绍了，但是篇幅又不会展开到实分析教科书的程度，对于第一次接触的人毫无疑问是比较棘手的，我虽然之前接触过实分析，大致能理解countable和uncountable的区别，但是从没有非常仔细的思考过著名的选择公理Axiom of Choice，以及其各种等价结论，还有其应用。这一章提供了一个机会。本章的习题也是 Analysis I 中数量比较大，难度也挺高的一部分，基本上如果没有hint，都很难做出来。这种熬脑的感觉在第1节还好，在第5节达到了顶峰。

Exercise 8.1.1. Let $X$ be a set. Show that $X$ is infinite if and only if there exists a proper subset $Y\subsetneq X$ of $X$ which has the same cardinality as $X$ . (This exercise requires the axiom of choice, Axiom 8.1)
Solution: First, if there exists a proper subset $Y\subsetneq X$ which has the same cardinality as $X$ , then assume $X$ is finite, then $Y$ must be finite. Since $X=Y\cup (X\backslash Y)$ , we know that $Y$ and $X\backslash Y$ are disjoint, further $X\backslash Y$ is not empty, so $\#(X\backslash Y)\geq 1$ , and

$\#(X)=\#(Y)+\#(X\backslash Y)=\#(X)+\#(X\backslash Y)\geq \#(X)+1>\#(X)$

which is a contradiction.
On the contrary, if $X$ is infinite, then we can form a set $S$ like this:
Choose $\forall x\in X$ , rename it $x_0$ and let $S_0=\{x_0 \}$ , then choose any element belongs to $X\backslash S_0$ , and rename it $x_1$ , then let $S_1=S_0\cup \{x_1 \}$ . This process shall never stop, since $X$ is infinite and we have the Axiom of Choice. Doing this recursively, we can eventually get a set $S$ (by letting $n\to\infty$ ), obviously $S\subseteq X$ .
We let $Y=X\backslash \{x_0\}$ , then $Y$ is a proper subset of $X$ . For any $x\in X$ , either $x\in S$ or $x\in X\backslash S$ , thus we define a function $f$ from $X$ to $Y$ as follows:

$f(x)=\begin{cases}x_{n+1},&x=x_n\in S\\x,&x\in X\backslash S \end{cases}$

It’ s easy to show that $f$ is a bijection.

$\blacksquare$

Exercise 8.1.2. Prove Proposition 8.1.4.(Well ordering principle).
Proposition 8.1.4. Let $X$ be a non-empty subset of the natural numbers $\mathbf N$ . Then there exists exactly one element $n\in X$ such that $n\leq m$ for all $m\in X$ . In other words, every non-empty set of natural numbers has a minimum element.
Solution: For the sake of contradiction we assume Proposition 8.1.4 is false, then there’s a nonempty set $X\subseteq \mathbf N$ , such that for any $n\in X$ , there exists one $m\in X$ s.t. $m<n$ .
Since $X\neq \emptyset$ , we choose $x\in X$ , and let $x=a_0$ , by our assumption, we can find an element $a_1\in X,a_1<x=a_0$ , once we find $a_n$ , we can by assumption find an element $a_{n+1}\in X$ such that $a_{n+1}<a_n$ , thus we build a infinite descent sequence $(a_n )_{n=0}^{\infty}$ of natural numbers, this contradicts the principle of infinite descent.
If we replace the natural numbers by the integers, then the well-ordering principle doesn’ t work. For example the set $X=\{-1,-2,-3,\cdots \}$ doesn’t have a minimum element.
If we replace the natural numbers by the positive rationals, then the well-ordering principle doesn’ t work. For example the set $X=\{q\in \mathbf Q:q>0\}$ doesn’t have a minimum element.

$\blacksquare$

Exercise 8.1.3. Fill in the gaps marked (why?) in Proposition 8.1.5.
Proposition 8.1.5. Let $X$ be an infinite subset of the natural numbers $\mathbf N$ . Then there exists a unique bijection $f:\mathbf N\to X$ which is increasing, in the sense that $f(n+1)>f(n)$ for all $n\in \mathbf N$ . In particular, $X$ has equal cardinality with $\mathbf N$ and is hence countable.
Solution: I will prove this Proposition in a complete manner.
Recursively define a sequence of natural numbers $a_0,a_1,a_2,\cdots$ using the formula below:

$a_n:= \min \{x\in X:\forall m<n,x\neq a_m \}$

Since $X$ is infinite, the set $\{x\in X:\forall m<n,x\neq a_m \}$ should also be infinite, assume not, then for some n this set is finite, and $\{a_0,a_1,\cdots ,a_{n-1} \}$ is finite, by

$X=\{x\in X:\forall m<n,x\neq a_m \}\cup \{a_0,a_1,\cdots ,a_{n-1} \}$

We deduce $X$ is finite, which is a contradiction.
Since $\{x\in X:\forall m<n,x\neq a_m \}$ is infinite, it’ s not empty for every $n$ , so we can successfully define $\min \{x\in X:\forall m<n,x\neq a_m \}$ by the well-ordering principle.
For $\forall n$ , we know that

$a_{n+1}:= \min \{x\in X:\forall m<n+1,x\neq a_m \}$

By the definition of $a_{n+1}$ we can see $a_{n+1}\neq a_n$ and $a_{n+1}\in \{x\in X:\forall m<n,x\neq a_m \}$ , since $a_n:= \min \{x\in X:\forall m<n,x\neq a_m \}$ , we can deduce $a_n<a_{n+1},\forall n$ . Thus

$a_0<a_1<a_2<\dots$

which means for all $n\neq m,a_n\neq a_m$ , otherwise we would get $a_n<a_n$ or $a_m<a_m$ . Also we know by the definition of $\min (X), a_n\in X,\forall n$ .
Now we define $f:\mathbf N\to X$ by $f(n):= a_n$ , we already show $f$ is 1-to-1. To prove $f$ is surjective, choose $x\in X$ , assume no $n$ can let $f(n)=x$ , then this means $a_n\neq x,\forall n$ , so for every $n, x\in \{x\in X:\forall m<n,x\neq a_m \}$ , thus $x\geq a_n,\forall n$ . As $(a_n )_{n=0}^{\infty}$ is an increasing sequence in natural numbers, we can prove by induction that $a_n\geq n$ , thus $x\geq n$ for every $n$ , we can then deduce $x\geq x+1$ and get a contradiction. So $f$ is surjective, thus bijective.
Last, we assume there’ s another increasing bijective $g:\mathbf N\to X,g\neq f$ , then $\{n\in \mathbf N:g(n)\neq f(n)\}$ is not empty, which means we can define

$m:= \min \{n\in \mathbf N:g(n)\neq f(n)\}$

So $g(m)\neq f(m)=a_m$ , and for all $n<m,g(n)=f(n)=a_n$ , in that case, $g(m)$ must equal some $x\in X$ , since $g$ is increasing, we have $x>g(n),\forall n<m$ , in particular:

$x\in \{x\in X:\forall n<m,x\neq a_n \}\implies x\geq \min \{x\in X:\forall n<m,x\neq a_n \}=a_m$

Together with $g(m)\neq a_m$ we know that $g(m)>a_m\in X$ , since $g$ is strictly increasing, this means $a_m\notin g(\mathbf N)$ , or $g$ is not surjective, a contradiction.

$\blacksquare$

Exercise 8.1.4. Prove Proposition 8.1.8.
Proposition 8.1.8. Let $Y$ be a set, and let $f:\mathbf N\to Y$ be a function. Then $f(\mathbf N)$ is at most countable.
Solution: We define $A$ as what Hint suggests. Consider $f|_A:A\to f(\mathbf N)$ , we prove $f|_A$ is a bijection.
Let $m,n\in A,m\neq n$ , then we shall have $m<n$ or $n<m$ , in either case, we can deduce from the definition of $A$ that $f|_A (m)\neq f|_A (n)$ , so $f|_A$ is injective.
For $\forall y\in f(\mathbf N)$ , we can have $k\in \mathbf N$ , s.t. $y=f(k)$ . Now for all $0\leq n\leq k$ , we can examine $f(n)$ recursively starting from $0$ and choose the first $m$ such that $f(m)=y$ . If $m=k$ , this means $k\in A$ . If $m<k$ , then $m\in A$ and $f(m)=y$ . In either case we have $y\in f|_A (A)$ , so $f|_A$ is surjective.
Since $A$ is a subset of $\mathbf N$ and is at most countable, $f(\mathbf N)$ is at most countable.

$\blacksquare$

Exercise 8.1.5. Use Proposition 8.1.8 to prove Corollary 8.1.9.
Corollary 8.1.9.. Let $X$ be a countable set, and let $f:X\to Y$ be a function. Then $f(X)$ is at most countable.
Solution: $X$ is countable, thus we can find a bijection $g: \mathbf N\to X$ , then $h=f\circ g$ is a function from $\mathbf N$ to $Y$ , thus use Proposition 8.1.8, $f(X)=f(g(\mathbf N))=h(\mathbf N)$ is at most countable.

$\blacksquare$

Exercise 8.1.6. Let $A$ be a set. Show that $A$ is at most countable if and only if there exists an injective map $f:A\to \mathbf N$ from $A$ to $\mathbf N$ .
Solution: If there exists an injective map $f:A\to \mathbf N$ , then $f$ is a bijection from $A$ to $f(A)$ , since $f(A)$ is a subset of $\mathbf N$ and is at most countable, $A$ is at most countable as $f^{-1}$ is a function from $f(A)$ to $A$ and $A=f^{-1} (f(A))$ and use Corollary 8.1.9.
If $A$ is at most countable, then $A$ is finite or $A$ is countable. Then:
For the case $A$ is finite, we can see $A$ has cardinality $n$ for some natural number $n$ . We select a bijection $g$ from $A$ to $\{1,2,\cdots ,n\}$ , and define $f:A\to \mathbf N$ by $f(a)=g(a),\forall a\in A$ , then $f$ is injective since $g$ is bijective.
For the case $A$ is countable, we can find a bijection $f: A\to \mathbf N$ , this function is injective.

$\blacksquare$

Exercise 8.1.7. Prove Proposition 8.1.10.
Proposition 8.1.10. Let $X$ be a countable set, and let $Y$ be a countable set. Then $X\cup Y$ is a countable set.
Solution: We use all the notations from Hint, i.e., define bijections $f:\mathbf N\to X, g:\mathbf N\to Y$ , then $h:\mathbf N\to X\cup Y$ is defined by $h(2n):=f(n),h(2n+1):=g(n)$ .
We need to show $h(\mathbf N)=X\cup Y$ , notice first that $\forall n\in \mathbf N,h(n)\in X$ if $n$ is even, and $h(n)\in Y$ if $n$ is odd, thus $h(n)\in X\cup Y,\forall n\in \mathbf N$ , or $h(\mathbf N)\subseteq X\cup Y$ .
Next, we have

$\begin{aligned}(x\in X\cup Y)&\implies (x\in X)\vee (x\in Y)\implies (x=f(m))\vee (x=g(n))\\&\implies (x=h(2m))\vee (x=h(2n+1))\implies (x\in h(\mathbf N))\end{aligned}$

Thus $X\cup Y\subseteq h(\mathbf N)$ . Then we can have $X\cup Y=h(\mathbf N)$
By Corollary 8.1.9 we know that $X\cup Y$ is at most countable, we remains to show $X\cup Y$ is not finite. Assume so, then $X\cup Y$ has cardinality $n$ for some natural number $n$ . So

$X\subseteq X\cup Y \implies \#(X)\leq n$

But if we let $S=\{1,2,\cdots ,n+1\}$ , then $f:S\to f(S)$ is a bijection, thus $f(S)$ has cardinality $n+1$ , however, $f(S)\subseteq X$ , so $\#(X)\geq n+1$ , this is a contradiction.

$\blacksquare$

Exercise 8.1.8. Use Corollary 8.1.13 to prove Corollary 8.1.14.
Corollary 8.1.13: The set $\mathbf N \times \mathbf N$ is countable.
Corollary 8.1.14: If $X$ and $Y$ are countable, then $X\times Y$ is countable.
Solution: By hypothesis, we have a bijection $f:\mathbf N\to X$ and a bijection $g:\mathbf N\to Y$ . We define a function $h:\mathbf N\times \mathbf N\to X\times Y$ by $h(m,n)=(f(m),g(n))$ , then we have

$\begin{aligned}(h(m,n)=h(m',n'))&\implies (f(m)=f(m'))\wedge (g(n)=g(n'))\\&\implies (m=m')\wedge (n=n' )\implies (m,n)=(m',n')\end{aligned}$

Thus $h$ is injective. And for $\forall (x,y)\in X\times Y$ , we have $x\in X$ and $y\in Y$ , so $\exists m,n\in N$ , s.t. $f(m)=x,g(n)=y$ , thus $h(m,n)=(x,y)$ , which means $h$ is surjective.
Now that $h$ is a bijection, from Corollary 8.1.13 we know $X\times Y$ is countable.

$\blacksquare$

Exercise 8.1.9. Suppose that $I$ is an at most countable set, and for each $\alpha \in I$ , let $A_{\alpha}$ be an at most countable set. Show that the set $\cup_{\alpha\in I}A_{\alpha}$ is also at most countable. In particular, countable unoins of countable sets are countable. (This exercise requires the axiom of choice, Axiom 8.1)
Solution: If $I$ is finite and $A_\alpha$ is finite for every $\alpha$ , then the statement is obvious.
Now suppose $I$ is countable, then we have a bijection $g:\mathbf N\to I$ , for each $\alpha \in I$ such that $A_\alpha \neq \emptyset$ , we assign a function $f_\alpha :\mathbf N\to A_\alpha$ as follows:
If $A_\alpha$ is finite, then it’ s possible to write $A_\alpha =\{x_1,\cdots ,x_n \},n\in \mathbf N$ , then let

$f_\alpha(i)=\begin{cases}x_i,&1\leq i\leq n\\x_1,&i>n\end{cases}$

If $A_\alpha$ is infinite or countable, then we can find a bijection $f':\mathbf N\to A_\alpha$ , we let $f_\alpha =f'$ .
So as long as $A_\alpha$ is nonempty, we have assigned a function $f_\alpha :\mathbf N\to A_\alpha$ . Next, if denote $J=\{\alpha \in I:A_\alpha \neq \emptyset \}$ we define $h: N\times N\to \cup_{\alpha \in J}A_\alpha$ as $h(m,n)=f_{g(m)}(n)$ . Then use Corollary 8.1.13 and Corollary 8.1.9, we can see that $\cup_{\alpha \in J}A_\alpha$ is at most countable. The final statement results from $\cup_{\alpha \in J}A_\alpha =\cup_ {\alpha \in I}A_\alpha$ .

$\blacksquare$

Exercise 8.1.10. Find a bijection $f:\mathbf N\to\mathbf Q$ from the natural numbers to the rationals.
Solution: We define $Q_n=\{a/b:|a|+b\leq n,a\in \mathbf Z,b\in \mathbf N^+\}$ for every $n\in \mathbf N$ , then $Q_0=\emptyset ,Q_1=\{0\}, Q_2=\{0,1,-1\}$ , etc. Each $Q_n$ is finite, thus have cardinality $c_n$ , we can see $c_0=0,c_1=1,c_2=3$ , etc. As $Q_n\subseteq Q_{n+1}$ , we define

$S_n=Q_n\backslash \left(\bigcup _{i=0}^{n-1}Q_i \right),\quad n\in \mathbf N^+$

since $\frac{1}{n-1}\in Q_n$ , but $\frac{1}{n-1}\notin \cup_{i=0}^{n-1}Q_i$ , each $S_n$ is nonempty for $n>1$ , and $S_1=Q_1=\{0\}$ , so each $S_n$ is nonempty for $n\in \mathbf N^+$ . Now we define $q_n=c_n-c_{n-1}$ , then each $S_n$ has cardinality $q_n$ , so $(q_n )_{n=1}^{\infty}$ is a positive increasing sequence.
We define a function $f:\mathbf N\to \mathbf Q$ inductively as follows:
Start from $0$ , we let $f_1 (0)=0$ , which is in fact a bijection from $\{i\in \mathbf N:c_0\leq i<c_1\}$ to $S_1$ .
Then for any $S_n$ , we can find a bijection $g_n:\{i\in \mathbf N:0\leq i<q_n \}\to S_n$ , we then define

$f_n (i)=g_n (i-c_{n-1} ),\quad c_{n-1}\leq i<c_n$

So we know $f_n$ is a bijection from $\{i\in \mathbf N:c_{n-1}\leq i<c_n\}$ to $S_n$ .
Finally we can define $f(k)=f_n (k)$ , in which $n$ is the positive natural number which satisfies $c_{n-1}\leq k<c_n$ , since if $m\neq n$ , we have

$\{i\in \mathbf N:c_{n-1}\leq i<c_n \}\cap \{i\in \mathbf N:c_{m-1}\leq i<c_m \}=\emptyset$

Since any for natural number $n$ , we have $\{0,1,\cdots ,n-1\}\subseteq Q_n$ , so $c_n\geq n$ , which means

$\bigcup_{n=1}^{\infty} \{i\in \mathbf N:c_{n-1}\leq i<c_n\}=\mathbf N$

Thus $f$ is truly a function defined on $\mathbf N$ , and the injectivity of $f$ is clear from the induction process, as we form $f$ from a sequence of bijective functions on disjoint subsets of $\mathbf N$ . We only remains to show $f$ is surjective. Choose any $q\in \mathbf Q$ , then we can write $q=a/b$ , in which $b$ is a positive natural number, we can be sure that $q\in Q_{|a|+b}$ , so

$q\in S_m,\quad 0<m\leq |a|+b$

Thus there’ s a number $k\in \{i\in \mathbf N:c_{m-1}\leq i<c_m\}$ such that $f_m (k)=f(k)=q$ . This means $f$ is surjective.

$\blacksquare$

	匿名发表在《陶哲轩实分析（下）7.2及习题-Analysis II 7.…》
	swimming5cc5e307af发表在《陶哲轩实分析11.2及习题-Analysis I 11.2》
	匿名发表在《陶哲轩实分析3.4及习题-Analysis I 3.4》
	匿名发表在《陶哲轩实分析9.9及习题-Analysis I 9.9》
	匿名发表在《陶哲轩实分析（下）1.2及习题-Analysis II 1.…》