城南讲马堂

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

2019年5月7日2019年12月19日christangdt2条评论

9.1节讨论实数轴的子集，但内容更多像是一个基本概念的汇总介绍。首先严格的定义了区间Interval，然后引入了adherent point，一个子集所有的adherent point构成其closure，在实数轴上，interval的closure就是闭区间。其后定义一个集合是闭的如果其包含所有的adherent point，这里很重要的一点是集合的adherent point与在集合内的序列的极限lim有一个对应关系，adherent point又可以分为limit point和isolated point。最后，定义了有界集bounded set，介绍了实数轴上的Heine-Borel定理。

Exercise 9.1.1. Let $X$ be any subset of the real line, and let $Y$ be a set such that $X\subseteq Y\subseteq \overline{X}$ . Show that $\overline{Y}=\overline{X}$ .

Solution: From $X\subseteq Y$ we have

$\begin{aligned}(x\in \overline X)&\implies (\forall \varepsilon >0,\exists a\in X, \text{ s.t. }|x-a|<\varepsilon )\\&\implies (\forall \varepsilon >0,\exists a\in Y, \text{ s.t. }|x-a|<\varepsilon )\\&\implies (x\in \overline Y)\end{aligned}$

Conversely, let $y\in \overline Y$ , then $\forall \varepsilon >0,\exists b\in Y,s.t.|y-b|<\varepsilon /2$ , since $b\in \overline X$ , we know $\exists a\in X,s.t.|b-a|<\varepsilon /2$ , thus $|y-a|\leq |y-b|+|b-a|<\varepsilon /2+\varepsilon /2=\varepsilon$ , so $y\in \overline X$ .

$\blacksquare$

Exercise 9.1.2. Prove Lemma 9.1.11.
Lemma 9.1.11 (Elementary properties of closures). Let $X$ and $Y$ be arbitrary subsets of $\mathbf R$ . Then $X\subseteq \overline{X},\overline{X\cup Y}=\overline{X}\cup\overline{Y}$ , and $\overline{X\cap Y}\subseteq \overline{X}\cap \overline{Y}$ . If $X\subseteq Y$ , then $\overline{X}\subseteq \overline{Y}$ .

Solution:
$X\subseteq \overline X$ :
$\forall x\in X,\exists x\in X,s.t.|x-x|=0<\varepsilon$ for $\forall \varepsilon >0$ .

$\overline {X\cup Y}=\overline X\cup \overline Y$ :

$\begin{aligned}(x\in \overline X)&\implies (\forall \varepsilon >0,\exists x'\in X,s.t.|x-x'|<\varepsilon )\\&\implies (\forall \varepsilon >0,\exists x'\in X\cup Y,s.t.|x-x'|<\varepsilon )\\&\implies (x\in \overline{X\cup Y})\end{aligned}$

The case $y\in \overline Y$ is similarly proved. So $\overline X\cup \overline Y\subseteq \overline {X\cup Y}$ . Conversely,

$(x\in \overline{X\cup Y})\implies (\forall \varepsilon >0,\exists a\in X\cup Y,s.t.|x-a|<\varepsilon )$

Suppose $x\notin \overline X$ , then we can find a $\varepsilon _0$ , s.t. $\forall x'\in X, |x-x'|\geq \varepsilon_0$ , then when $\varepsilon <\varepsilon _0$ , the $a\in X\cup Y$ we choose such that $|x-a|<\varepsilon$ must belongs to $Y$ , so $x\in \overline Y$ .

$\overline {X\cap Y}\subseteq \overline X\cap \overline Y$ :

$\begin{aligned}(x\in \overline{X\cap Y})&\implies (\forall \varepsilon >0,\exists a\in X\cap Y,\text{ s.t. }|x-a|<\varepsilon )\\&\implies (\forall \varepsilon >0,\exists a\in X,\text{ s.t. }|x-a|<\varepsilon )\wedge (\forall \varepsilon >0,\exists a\in Y,\text{ s.t. }|x-a|<\varepsilon )\\&\implies (x\in \overline X)\wedge (x\in \overline Y)\implies x\in \overline X\cap \overline Y\end{aligned}$

$(X\subseteq Y)\implies (\overline X\subseteq \overline Y):$

$\begin{aligned}(x\in \overline X)&\implies (\forall \varepsilon >0,\exists x'\in X,\text{ s.t. }|x-x'|<\varepsilon )\\&\implies (\forall \varepsilon >0,\exists x'\in Y,\text{ s.t. }|x-x' |<\varepsilon )\\&\implies (x\in \overline Y)\implies (\overline X\subseteq \overline Y)\end{aligned}$

$\blacksquare$

Exercise 9.1.3. Prove Lemma 9.1.13.
Lemma 9.1.13. The closure of $\mathbf N$ is $\mathbf N$ . The closure of $\mathbf Z$ is $\mathbf Z$ . The closure of $\mathbf Q$ is $\mathbf R$ , and the closure of $\mathbf R$ is $\mathbf R$ .The closure of the empty set $\emptyset$ is $\emptyset$ .

Solution:
i. The closure of $\mathbf N$ is $\mathbf N$ :
We have $\mathbf N\subseteq \overline {\mathbf N}$ by Lemma 9.1.11. Let $x\in \overline {\mathbf N}$ , then assume $x\notin \mathbf N$ , we can find a $n\in \mathbf N,n<x<n+1$ , let $\varepsilon =(\min \{x-n,n+1-x\})/2$ , then no element $k$ of $\mathbf N$ can satisfy $|x-k|<\varepsilon$ , so $x\in \mathbf N$ and $\overline{\mathbf N}\subseteq \mathbf N$ .

ii. The closure of $\mathbf Z$ is $\mathbf Z$ :
Let $\mathbf N'=-\mathbf N$ , then by i) we have $\overline{\mathbf N'}=\mathbf N'$ , and also we have $\mathbf Z=\mathbf N'\cup \mathbf N$ , thus $\overline{\mathbf Z}=\overline {\mathbf N'\cup \mathbf N}=\overline {\mathbf N' }\cup \overline{\mathbf N}=\mathbf N'\cup \mathbf N=\mathbf Z$ .

iii. The closure of $\mathbf Q$ is $\mathbf R$ :
Obviously $\overline {\mathbf Q}\subseteq \mathbf R$ , and for $\forall r\in \mathbf R,\forall \varepsilon >0$ , by Proposition 5.4.14 we have some $q\in \mathbf Q$ s.t. $r<q<r+\varepsilon$ . Thus $r\in \overline {\mathbf Q}$ , so $\overline {\mathbf Q}=\mathbf R$ .

iv. The closure of $\mathbf R$ is $\mathbf R$ :
Obviously $\overline{\mathbf R} \subseteq \mathbf R$ , and we have $( \mathbf Q\subseteq \mathbf R)\implies \overline {\mathbf Q}=\mathbf R\subseteq \overline{\mathbf R}$ by Lemma 9.1.11.

v. The closure of $\emptyset$ is $\emptyset$ :
Assume we have $a\in \overline \emptyset$ , then for $\forall \varepsilon >0$ , we shall find some $b\in \emptyset , \text{ s.t. }|a-b|<\varepsilon$ , but this is impossible since no element belongs to $\emptyset$ .

$\blacksquare$

Exercise 9.1.4. Give an example of two subsets $X,Y$ of the real line such that $\overline{X\cap Y}\neq\overline{X}\cap \overline{Y}$ .

Solution: Let $X=[0,1),Y=(1,2],X\cap Y=\emptyset ,\overline {X\cap Y}=\emptyset$ by Lemma 9.1.13, but

$\overline X=[0,1],\quad \overline Y=[1,2],\quad\overline X\cap \overline Y=\{1\}$

$\blacksquare$

Exercise 9.1.5. Prove Lemma 9.1.14.
Lemma 9.1.14. Let $X$ be a subset of $\mathbf R$ , and let $x\in \mathbf R$ . Then $x$ is an adherent point of $X$ if and only if there exists a sequence $(a_n)_{n=0}^{\infty}$ , consisting entirely of elements in $X$ , which converges to $x$ .

Solution: If $x$ is an adherent point of $X$ , then for any $n\in \mathbf N$ , the set ${y\in X:|y-x|<1/n}$ is non-empty, thus use axiom of choice we can find a $a_n\in X$ for each $n$ , and $|a_n-x|<1/n$ , the sequence $(a_n)_{n=0}^{\infty}$ converges to $x$ . Conversely, if there’s a sequence $(a_n)_{n=0}^{\infty} \in X$ converges to $x$ , then $\forall \varepsilon >0, \exists N\in \mathbf N, \text{ s.t. }|a_N-x|<\varepsilon$ , since $a_N\in x, x$ is an adherent point of $X$ .

$\blacksquare$

Exercise 9.1.6. Let $X$ be a subset of $\mathbf R$ . Show that $\overline{X}$ is closed. (i.e., $\overline{\overline{X}}=\overline{X}$ ). Furthermore, show that if $Y$ is any closed set that contains $X$ , then $Y$ also contains $\overline{X}$ . Thus the closure $\overline{X}$ of $X$ is the smallest closed set which contains $X$ .

Solution: Let $a$ be an adherent point of $\overline X$ , then $\forall \varepsilon >0,\exists b\in \overline X$ , s.t. $|a-b|<\varepsilon /2$ . For this $b$ , there’s $x\in X$ , s.t. $|b-x|<\varepsilon /2$ . Thus $|a-x|\leq |a-b|+|b-x|<\varepsilon$ .
So $a\in \overline X$ , thus $\overline {\overline X}=\overline X$ .
If $X\subseteq Y$ and $Y$ is closed, then $\overline X \subseteq \overline Y=Y$ by Lemma 9.1.11.

$\blacksquare$

Exercise 9.1.7. Let $n\geq 1$ be a positive integer, and let $X_1,\dots,X_n$ be closed subsetes of $\mathbf R$ . Show that $X_1\cup X_2\cup \dots\cup X_n$ is also closed.

Solution: Use induction, when $n=1$ the conclusion is obviously true.
Suppose the conclusion is true when $n=k$ , then by Lemma 9.1.11

$\begin{aligned}\overline {X_1\cup X_2\cup \dots \cup X_{k+1}}&=\overline {X_1\cup X_2\cup \dots \cup X_k }\cup \overline {X_{k+1}}\\&=(X_1\cup X_2\cup \dots \cup X_k )\cup X_{k+1}\\&=X_1\cup X_2\cup \dots \cup X_{k+1}\end{aligned}$

So the statement is true for positive integer $n$ .

$\blacksquare$

Exercise 9.1.8. Let $I$ be a set (possibly infinite), and for each $\alpha\in I$ let $X_{\alpha}$ be a closed subset of $\mathbf R$ . Show that the intersection $\bigcap_{\alpha\in I}X_{\alpha}$ (defined in (3.3)) is also closed.

Solution: Let a be an adherent point of $\bigcap _{{\alpha}\in I}X_{\alpha}$ , then $\forall \varepsilon >0,\exists b\in \bigcap_{{\alpha}\in I}X_{\alpha}$ , s.t. $|a-b|<\varepsilon$ .
Because $b\in X_{\alpha},\forall {\alpha}\in I$ , we have $a\in \overline {X_{\alpha} }=X_{\alpha},\forall {\alpha}\in I$ , thus $a\in \bigcap_{{\alpha}\in I}X_{\alpha}$ , thus $\bigcap_{{\alpha}\in I}X_{\alpha}$ is closed.

$\blacksquare$

Exercise 9.1.9. Let $X$ be a subset of the real line, and $x$ be a real number. Show that every adherent point of $X$ is either a limit point or an isolated point of $X$ , but cannot be both. Conversely, show that every limit point and every isolated poit of $X$ is an adherent point of $X$ .

Solution: Let $x$ be an adherent point of $X$ , if $x$ is also an adherent point of $X\backslash \{x\}$ , then $x$ is a limit point of $X$ . If not, then we can find a $\varepsilon _0>0$ , s.t $\forall y\in X\backslash \{x\}$ , we have $|x-y|\geq \varepsilon _0$ , let $\varepsilon =\varepsilon _0/2$ we see $x$ is an isolated point of $X$ .
Conversely, a limit point of $X$ is an adherent point of $X\backslash \{x\}$ , thus an adherent point of $X$ since $X\backslash \{x\}\subseteq X$ and by Lemma 9.1.11. An isolated point of $X$ belongs to $X$ and is surely an adherent point of $X$ by Lemma 9.1.11.

$\blacksquare$

Exercise 9.1.10. If $X$ is a non-empty subset of $\mathbf R$ , show that $X$ is bounded if and only if $\inf (X)$ and $\sup (X)$ are finite.

Solution: If $\inf (X)$ and $\sup (X)$ are finite, let $M=\max{|\inf(X) |,|\sup (X) |}+1>0$ , then for $\forall x\in X$ , we have $\inf (X)\leq x\leq \sup (X)$ and thus

$\begin{aligned} -1-\max\{|\inf(X) |,|\sup (X)|\}&\leq -\max\{|\inf(X) |,|\sup (X)|\}\leq |\inf (X)|\\ &\leq \inf (X)\leq x\leq \sup (X)\\&\leq |\sup (X)|<\max\{|\inf(X)|,|\sup (X)|\}+1\end{aligned}$

Thus $-M\leq x\leq M$ and $X$ is bounded. Conversely, if $X$ is bounded, then $\exists M>0$ , s.t.

$-M\leq x\leq M,\quad \forall x\in X$

This means $-M$ is a lower bound of $X$ and $M$ is an upper bound of $X$ , thus we have

$-M\leq \inf (X)\leq \sup (X)\leq M$

which means $\inf (X)$ and $\sup (X)$ are finite.

$\blacksquare$

Exercise 9.1.11. Show that if $X$ is a bounded subset of $\mathbf R$ , then the closure $\overline{X}$ is also bounded.

Solution: $X$ is bounded, then $\exists M>0$ , s.t. $-M\leq x\leq M,\forall x\in X$ . Let $\varepsilon =1$ , then for $\forall x'\in \overline X,\exists x\in X$ , s.t. $|x-x'|<1$ , so $x-1<x'<x+1$ , or

$-M-1\leq x-1<x'<x+1\leq M+1,\quad \forall x'\in \overline X$

Thus $\overline X$ is bounded since $M+1>M>0$ .

$\blacksquare$

Exercise 9.1.12. Show that the union of any finite collection of bounded subsets of $\mathbf R$ is still a bounded set. Is this conclusion still true if one takes an infinite collection of bounded subsets of $\mathbf R$ ?

Solution: Let $X_1,X_2,\dots ,X_n$ be bounded subsets of $\mathbf R$ , then we can find $M_i>0,i=1,2,\dots ,n$ , s.t.

$X_i\subset [-M_i,M_i ],\quad i=1,2,\dots ,n$

Let $M=\max{M_1,M_2,\dots ,M_n }>0$ , then $[-M_i,M_i ]\subseteq [-M,M]$ for $i=1,2,\dots ,n$ , thus

$X_1\cup X_2\cup \dots \cup X_n\subset [-M,M]$

which means $X_1\cup X_2\cup \dots \cup X_n$ is bounded.
The conclusion is not true when we take an infinite collection of bounded subsets of $\mathbf R$ , for example take $X_n=[-n,n],n\in \mathbf N$ , then $\bigcup _{i=1}^{\infty} X_i =(-{\infty} ,+{\infty} )$ .

$\blacksquare$

Exercise 9.1.13. Prove Theorem 9.1.24.
Theorem 9.1.24. (Heine-Borel theorem for the line). Let $X$ be a subset of $\mathbf R$ . Then the following two statements are equivalent:
( a ) $X$ is closed and bounded.
( b ) Given any sequence $(a_n){n=0}^{\infty}$ of real numbers which takes values in $X$ (i.e., $a_n\in X$ for all $n$ ), there exists a subsequence $(a_{n_j})_{j=0}^{\infty}$ of the original sequence, which converges to some number $L$ in $X$ .

Solution:
( a ) implies ( b ): if $X$ is bounded and $(a_n)_{n=0}^{\infty} \in X$ , then $(a_n)_{n=0}^{\infty}$ is bounded, so by Bolzano-Weierstrass theorem, there exists a subsequence $(a_{n_j})_{j=0}^{\infty}$ which converges to $L$ . Since $X$ is closed, $L\in X$ by Corollary 9.1.17.
( b ) implies ( a ): first since every convergent sequence $(a_n)_{n=0}^{\infty} \in X$ has all it’s subsequence converges to the same limit, so if $(a_n)_{n=0}^{\infty} \in X,a_n\to L$ , we can know there’s a subsequence which converges to $L$ , thus $L\in X$ . By Corollary 9.1.17, $X$ is closed. Assume $X$ is not bounded, then for every $n\in \mathbf N$ , we can find a $a_n\in X, s.t. |a_n |>n$ , we can see $(a_n)_{n=0}^{\infty} \in X$ , thus there exists a subsequence $(a_{n_j})_{j=0}^{\infty}$ which converges to $L$ . So we may find a $J$ s.t.

$|a_{n_j}-L|<1 \implies |a_{n_j}|<|L|+1,\quad\forall j>J$

We can find $N\in \mathbf N$ , s.t. $|L|+1\leq N$ , so $|a_{n_j }|<N,\forall j>J$ , but as $j\to {\infty} ,n_j\to {\infty}$ , we shall have $n_j>N$ and $|a_{n_j}|>N$ for some $n_j>n_J$ , this is a contradiction.

$\blacksquare$

Exercise 9.1.14. Show that any finite subset of $\mathbf R$ is closed and bounded.

Solution: By Exercise 9.1.7 and Exercise 9.1.12, we get the conclusion.

$\blacksquare$

Exercise 9.1.15. Let $E$ be a bounded subset of $\mathbf R$ , and let $S:=\sup (E)$ be the least upper bound of $E$ . Show that $S$ is an adherent point of $E$ , and is also an adherent point of $\mathbf R\backslash E$ .

Solution: For $\forall \varepsilon >0$ , we can find $x\in E$ , s.t. $S-\varepsilon <x<S$ , so $|x-S|<\varepsilon$ , thus $S$ is an adherent point of $E$ . Also we have $x\leq S,\forall x\in E$ , so we shall have $(S,S+\varepsilon )\cap E=\emptyset$ , so there is point in $\mathbf R\backslash E$ which belongs to $(S,S+\varepsilon)$ , so $S$ is an adherent point of $\mathbf R\backslash E$ .

$\blacksquare$

陶哲轩实分析8.5及习题-Analysis I 8.5-part 1

2019年5月6日2019年12月13日christangdt14条评论

这一节在集合上建立一个序order，序分为偏序、全序和良序，依次递进。之后又引入了强归纳法和超限归纳法（zorn引理），这一节的内容安排在数学分析课程中不多见，常见于实变函数或者实分析的开头。个人认为这一节的精华在于习题，给出了很多Axiom of choice和Zorn引理的等价形式，习题做得也是相当吐血。可以想见搞集合论和拓扑学的人脑力有多充沛了。由于习题过长，本节分成两部分

Exercise 8.5.1. Consider the empty set $\emptyset$ with the empty order relation $\leq_{\emptyset}$ (this relation is vacuous because the empty set has no elements). Is this set partially ordered? totally ordered? well-ordered? Explain.
Solution: This set is partially ordered, totally ordered and well-ordered, since each condition judging the order property of a set requires elements, since $\emptyset$ contains no element, all conditions are true.

$\blacksquare$

Exercise 8.5.2. Give examples of a set $X$ and a relation $\leq$ such that
( a ) The relation $\leq$ is reflexive and anti-symmetric, but not transitive;
( b ) The relation $\leq$ is reflexive and transitive, but not anti-symmetric;
( c ) The relation $\leq$ is anti-symmetric and transitive, but not reflexive.
Solution:
( a ) There is a tournament between Federer, Nadal and Djokovic, each plays a match against the other two. Define $X=\{Federer,Nadal,Djokovic\}$ , and define $x\leq y$ if there’s no match played between $x$ and $y$ , or $y$ defeats $x$ if there’s a match played between the two.
Then for any $x\in X$ , $x\leq x$ since there’s no match played.
If $x\leq y$ and $y\leq x$ , then there can’t be a match played between $x$ and $y$ , so $x=y$ , meaning they are in fact one player.
If $x\leq y$ and $y\leq z$ , we can’t deduce $x\leq z$ , since we may have Federer defeats Nadal, Nadal defeats Djokovic, but Federer can’t ensure he defeats Djokovic.

( b ) $X=2^N$ , $\leq$ means: $(x\leq y)\iff \max y\geq a,\forall a\in X$ . This relation is not anti-symmetric since we can let $x=\{1,2,3\},y=\{1,3\}$ , then $x\leq y$ and $y\leq x$ , but $x\neq y$ .

( c ) Let $X=\mathbf N$ , and the relation “ $x\leq y$ ” is true if $x<y$ in the natural number system compare rules, then this relation is not reflexive.
Since no elements can satisfy $(x\leq y)\wedge (y\leq x)$ , anti-symmetric is also true.
If $x\leq y$ and $y\leq z$ , we can see $x<y$ and $y<z$ , so $x<z$ in the natural number system, thus $x\leq z$ .

$\blacksquare$

Exercise 8.5.3. Given two positive integers $n,m\in \mathbf N\backslash \{0\}$ , we say that n divides $m$ and write $n/m$ , if there exists a positive integer $a$ such that $m=na$ . Show that the set $\mathbf N\backslash \{0\}$ with the ordering relation $|$ is a partially ordered set but not a totally ordered one. Note that this is a different ordering relation from the usual $\leq$ ordering of $\mathbf N\backslash \{0\}$ .
Solution:
Reflexive: for any $n\in \mathbf N\backslash \{0\}$ , we have $n=n1$ , $1$ is a positive integer, thus $n|n$ .
Anti-symmetric: if $n|m$ and $m|n$ , then there’s $a,b\in \mathbf N^+$ , s.t. $m=na,n=mb$ , so $m=abm$ , or $ab=1$ , which means $a=b=1$ , thus $m=n$ .
Transitive: if $n|m$ and $m|k$ , we know there’s $a,b\in \mathbf N^+$ , s.t. $m=na,k=mb$ , so $k=nab=(ab)n$ . As $ab\in \mathbf N^+$ , we see that $n|k$ .
No totally orderings: for positive integers $2$ and $3$ , we have neither $2|3$ or $3|2$ .

$\blacksquare$

Exercise 8.5.4. Show that the set of positive reals $\mathbf R^+:=\{x\in \mathbf R:x>0\}$ have no minimal element.
Solution: Assume so, then there’s a minimal element $y$ of $\mathbf R^+$ , by definition, $y\in \mathbf R^+$ , and there’s no element $y'\in \mathbf R^+$ such that $y'0$ , we have $y/2>0$ , so $y/2\in \mathbf R^+$ , and as $y/2+y/2=y$ , we know $y/2<y$ , a contradiction.

$\blacksquare$

Exercise 8.5.5. Let $f:X\to Y$ be a function from one set $X$ to another set $Y$ . Suppose that $Y$ is partially ordered with some ordering relation $\leq_Y$ . Define a relation $\leq_X$ on $X$ by defining $x\leq_X x'$ if and only if $f(x)<_Yf(x')$ or $x=x'$ . Show that this relation $\leq_X$ turns $X$ into a partially ordered set. If we know in addition that the relation $\leq_Y$ makes $Y$ totally ordered, does this mean that the relation $\leq_X$ makes $X$ totally ordered also? If not, what additional assumption needs to be made on $f$ in order to ensure that $\leq_X$ makes $X$ totally ordered?
Solution:
Reflexive: since $x=x$ , we have $x\leq _X x$ .
Anti-symmetric: if $x\leq _X y$ and $y\leq _X x$ , then from $x\leq _X y$ we can have $f(x) <_Y f(y)$ or $x=y$ , from $y\leq _X x$ we can have $f(y) <_Y f(x)$ or $y=x$ . So we can deduce either $x=y$ , thus the conclusion holds, or $f(x) <_Y f(y)$ and $f(y) <_Y f(x)$ both valid, but the latter case is impossible since

$(f(x) <_Y f(y))\wedge (f(y) <_Y f(x))\implies (f(x) \leq _Y f(y))\wedge (f(y) \leq _Y f(x))\\implies f(y)=f(x)$

But $f(x) <_Y f(y)$ means $f(x)\neq f(y)$ , so a contradiction.
Transitive: if $x\leq _X y$ and $y\leq _X z$ , then we shall have $f(x) <_Y f(y)$ or $x=y$ and $f(y) <_Y f(z)$ or $y=z$ . We split the cases:

i) $f(x) <_Y f(y)$ and $f(y) <_Y f(z)$ , then $x\neq y$ and $y\neq z$ , from Y being partially ordered, we can get $f(x) \leq _Y f(z)$ , also we must have $f(x)\neq f(z)$ because if assume so, then $f(z) <_Y f(y)$ and $f(y) <_Y f(z)$ both valid, which means $f(y)=f(z)$ , a contradiction. Thus in this case we deduce $f(x) <_Y f(z)$ , or $x\leq _X z$ .
ii) $f(x) <_Y f(y)$ and $y=z$ , then $f(y)=f(z)$ , so $f(x) <_Y f(z)$ , or $x\leq _X z$ .
iii) $x=y$ and $f(y) <_Y f(z)$ , then $f(x)=f(y)$ , so $f(x) <_Y f(z)$ , or $x\leq _X z$ .
iv) $x=y$ and $y=z$ , then $x=z$ and $x\leq _X z$ .

If $Y$ is totally ordered by $\leq_Y$ , then we can’t say that $\leq_X$ makes $X$ totally ordered also, the additional assumption should be that $f$ is injective. Since $\forall x,y\in X$ , if $x\neq y$ and $f(x)=f(y)$ , then we have neither $x \neq_Xy$ nor $y \leq_Xx$ .

$\blacksquare$

Exercise 8.5.6. Let $X$ be a partially ordered set. For any $x$ in $X$ , define the order ideal $(x)\subset X$ to be the set $(x):=\{y\in X:y<x\}$ . Let $(X):=\{(x):x\in X\}$ be the set of all order ideals, and let $f:X\to (X)$ be the map $f(x):=(x)$ that sends every element of $x$ to its order ideal. Show that $f$ is a bijection, and that given any $x,y\in X$ , that $x\leq_Xy$ if and only if $f(x)\subseteq f(y)$ . This exercise shows that any partially ordered set can be represented by a collection of sets whose ordering relation is given by set inclusion.
Solution: Let $f(x)=f(z)$ , then $(x)=(z)$ , or $\{y\in X:y\leq x\}=\{y\in X:y\leq z\}$ , since $x\in \{y\in X:y\leq x\}$ , we have $x\leq z$ , by the same logic $z\leq x$ , as $X$ is partially ordered, we have $x=z$ . So $f$ is an injection.
Next, let $\forall A\in (X)$ , then we can write $A=(x)=\{y\in X:y\leq x\}$ for some $x\in X$ , thus we can have $f(x)=A$ . So $f$ is a surjection, and thus a bijection.
Given any $x,y\in X$ , if $x\leq y$ , then by the definition of $(x)$ and transitivity of $\leq$ :

$\forall a\in (x)=f(x)\implies a\leq x\implies a\leq y\implies f(x)\subseteq f(y)$

On the other hand, if $f(x)\subseteq f(y)$ , then $\forall a\in (x),a\in (y)$ , in particular $x\in (y)$ , so $x\leq y$ .

$\blacksquare$

Exercise 8.5.7. Let $X$ be a partially ordered set, and let $Y$ be a totally ordered subset of $X$ . Show that $Y$ can have at most one maximum and at most one minimum.
Solution: We first suppose $Y$ have two minimum, $a,b\in Y$ , then for any $y\in Y$ , we can’t have $y<a$ , and we can’ t have $y<b$ . Now as $Y$ is totally ordered, we shall have either $a\leq b$ or $b\leq a$ or both. If $a\leq b$ , since we can’t have $a<b$ , we must have $a=b$ . If $b<a$ , we must also have $b=a$ . Thus there’s at most one minimum.
The case of maximum can be similarly proved.

$\blacksquare$

Exercise 8.5.8. Show that every finite non-empty subset of a totally ordered set has a minimum and a maximum. Conclude in particular that every finite totally ordered set is well-ordered.
Solution: Let $X$ be a totally ordered set, and let $Y$ be a finite non-empty subset, we use induction on $\text{card}(Y)$ . Apparently $\text{card}(Y)\geq 1$ , if $\text{card}(Y)=1$ , there’s only one element $y\in Y$ , which is the maximum and minimum of $Y$ .
Now suppose the conclusion holds when $\forall Y\subseteq X,card(Y)=n$ , let $Y\subseteq X$ such that $\text{card}(Y)=n+1$ , then $\text{card}(Y)\geq 1$ , so we can choose $y\in Y$ , then the set $Y\backslash \{y\}$ has cardinality $n$ , thus has a maximum $M$ and a minimum $m$ , as $y\neq M,y\neq m$ , we can compare $y$ with $m,M$ to determine the new maximum and minimum of $Y$ , the comparison is possible since $Y$ is totally ordered.
Since every subset of a finite subset is finite, thus has a minimum, we can conclude a finite totally ordered subset is well-ordered.

$\blacksquare$

Exercise 8.5.9. Let $X$ be a totally ordered set such that every non-empty sybset of $X$ has both a minimum and a maximum. Show that $X$ is finite.
Solution: Assume $X$ is infinite, then first $X$ has a minimum since $X\subseteq X$ , let this minimum be $x_0$ .
Then let $x_1:=\min (X\backslash \{x_0 \})$ , and recursively define

$x_n:=\min (X\backslash \{x_0,\dots,x_{n-1} \}),\quad \forall n\geq 2$

We can see that $x_0<x_1<\cdots$ in $X$ , thus the set $\{x_i:i\in \mathbf N\}$ is a non-empty subset of $X$ , thus has a maximum, but this set is infinite and strictly increasing, the existence of a maximum would lead to a contradiction.

$\blacksquare$

Exercise 8.5.10. Prove Proposition 8.5.10, without using the axiom of choice.
Solution: We set $Y$ as the hint suggests, and assume $Y$ is non-empty, then $\exists n\in X,n\in Y$ , thus we can find $m\in X$ , s.t. $m\leq _X n$ and $P(m)$ is false, which means the set

$Y_n:=\{m\in X:m\leq n\text{ and }P(m)\text{ is false}\}\subseteq X$

is non-empty, so we can find a minimum $m'$ of $Y_n$ . Obviously $P(m')$ is false. We can further deduce that $P(m)$ is true for all $m\in X$ with $m<_X m'$ , otherwise $m$ would replace $m'$ to be the minimum of $Y_n$ . But now if we apply the implication condition, we’ll get $P(m')$ is true, which leads to a contradiction.

$\blacksquare$

Exercise 8.5.11. Let $X$ be a partially ordered set, and let $Y$ and $Y'$ be well-ordered subsets of $X$ . Show that $Y\cup Y'$ is well-ordered if and only if it is totally ordered.
Solution: First suppose $Y\cup Y'$ is well-ordered, choose any $a,b\in Y\cup Y'$ , if $a=b$ the conclusion is obvious since $X$ is partially ordered and $a\leq a=b$ by reflexivity. In the case $a\neq b$ , the set $\{a,b\}\subseteq Y\cup Y'$ is non-empty, thus has a minimum, which could be either $a$ or $b$ , and we could have either $a<b$ or $b<a$ , so we can have either $a\leq b$ or $b\leq a$ , proving $Y\cup Y'$ is totally ordered.
Next suppose $Y\cup Y'$ is totally ordered, given any non-empty subset $A\subseteq Y\cup Y'$ , we shall have $A=(A\cap Y)\cup(A\cap Y' )$ , at least one of the two sets shall be non-empty. If we do have one of the two sets empty, then $A\subseteq Y$ or $A\subseteq Y'$ , since $Y$ and $Y'$ are well-ordered, we can find a minimum of $A$ .
If both sets are non-empty, since $Y$ and $Y'$ are well-ordered, we can find

$m_1=\min(A\cap Y),\quad m_2=\min (A\cap Y')$

If $m_1=m_2$ , we are done finding a minimum of $A$ , if $m_1\neq m_2$ , as $m_1,m_2\in Y\cup Y'$ , we must have either $m_1\leq m_2$ or $m_2\leq m_1$ , combined with $m_1\neq m_2$ , we can get $m_1<m_2$ or $m_2<m_1$ , so we select out a minimum of $A$ . Which proves $Y\cup Y'$ is well-ordered.

$\blacksquare$

Exercise 8.5.12. Let $X$ and $Y$ be partially ordered sets with ordering relations $\leq_X$ and $\leq_Y$ respectively. Define a relation $\leq_{X\times Y}$ on the Cartesian product $X\times Y$ by defining $(x,y)\leq_{X\times Y}(x',y')$ if $x<_Xx'$ , or if $x=x'$ and $y\leq_Yy'$ . Show that $\leq_{X\times Y}$ defines a partial ordering on $X\times Y$ . Furthermore, show that if $X$ and $Y$ are totally ordered, then so is $X\times Y$ , and if $X$ and $Y$ are well-ordered, then so is $X\times Y$ .
Solution:

$\leq _{X\times Y}$ is a partial ordering on $X\times Y$ :
Reflexivity: we have $x=x$ and $y\leq _Y y$ by the reflexivity of $\leq _Y$ , so $(x,y) \leq _{X\times Y} (x,y)$
Anti-symmetric: let $(x,y) \leq _{X\times Y} (x',y' )$ and $(x',y') \leq _{X\times Y} (x,y)$ , then we first consider $x$ and $x'$ , we can’t have $x<_X x'$ , which contradicts $(x',y') \leq _{X\times Y} (x,y)$ , we also can’t have $x'<_X x$ , which contradicts $(x,y) \leq _{X\times Y} (x',y' )$ , so $x=x'$ , then we have $y\leq _Y y'$ and $y' \leq _Y y$ , by the anti-symmetric of $\leq _Y$ , we have $y=y'$ . In total, $(x,y)=(x',y')$ .
Transitivity: let $(x,y) \leq _{X\times Y} (x',y' )$ and $(x',y') \leq _{X\times Y} (x'',y'')$ , we first consider $x,x'$ and $x''$ : as $(x\leq _X x' )\wedge (x' \leq _X x'' )$ is always true, we must have $x\leq _X x''$ . If $x=x'=x''$ is not true, then $x<_X x''$ , which gives $(x,y) \leq _{X\times Y} (x'',y'' )$ . If $x=x'=x''$ , then we shall deduce $(y\leq _Y y' )\wedge (y' \leq _Y y'' )$ , by the transitivity of $\leq _Y$ , we have $y\leq _Y y''$ and $(x,y) \leq _{X\times Y} (x'',y'' )$ .

If $X$ and $Y$ are totally ordered, then so is $X\times Y$ :
For any $(x,y),(x',y' )\in X\times Y$ , we have $x,x'\in X$ , so either $x\leq _X x'$ or $x'\leq _X x$ or both. If only one of the two is true, then $x\neq x'$ , thus either $x<_X x'$ or $x'<_X x$ , which means either $(x,y) \leq _{X\times Y} (x',y' )$ or $(x',y') \leq _{X\times Y} (x,y)$ .
If both of the two are true, then $x=x'$ , thus we have $y,y'\in Y$ , so either $y\leq _Y y'$ or $y'\leq _Y y$ or both. Thus we must have either $(x,y) \leq _{X\times Y} (x',y' )$ or $(x',y') \leq _{X\times Y} (x,y)$ .

If $X$ and $Y$ are well-ordered, then so is $X\times Y$ :
Choose any non-empty subset $A\subseteq X\times Y$ , we can have $A=B\times C,B\subseteq X,C\subseteq Y$ , both $B$ and $C$ are non-empty, thus we can have minimums, let $b:=\min B$ and $c:=\min C$ , then $(b,c)\in X\times Y$ . For any $(x,y)\in A$ , we have $x\in B,y\in C$ . So if $b\neq x$ we must have $b<x$ , which means $(b,c) \leq _{X\times Y} (x,y)$ . If $b=x$ , then $c\leq _Y y$ is true for any $y\in C$ , so we also have $(b,c) \leq _{X\times Y} (x,y)$ . In total, we can conclude $(b,c)$ is the minimum of $A$ , which means $X\times Y$ is well ordered.

$\blacksquare$

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

2019年5月5日2021年2月24日christangdt2条评论

选择公理，很惭愧的说在读这本书之前都没有意识到其存在，从有限维推广到无限维的时候很自然的就用了，当然从应用数学的角度，可以很安全地假定选择公理一定成立。这里Tao秉承了他一贯的严格性。

Exercise 8.4.1. Show that the axiom of choice implies Proposition 8.4.7. Conversely, show that if Proposition 8.4.7. is true, then the axiom of choice is also true.
Solution: We know that $X$ is a set, and for each $x\in X$ , the set $Y_x={y\in Y:P(x,y)\text{ is true}}$ is not empty, use Axiom of Choice, we define $f:X\to Y$ by setting $f(x)$ to be one element $y\in Y_x$ , this function is well-defined, so $P(x,f(x))$ is true for all $x\in X$ .
Conversely, if $I$ is a set and $X_{\alpha} \neq \emptyset,\forall {\alpha} \in I$ , let $P(x,y)={x\in I,y\in \bigcup_{{\beta} \in I}X_{\beta}:y\in X_x}$ , then for every ${\alpha} \in I$ , there’s at least one $y\in \bigcup_{{\beta} \in I}X_{\beta}$ such that $P({\alpha},y)$ is true. By Proposition 8.4.7, there’s a function $f:I\to \bigcup_{{\beta} \in I}X_{\beta}$ , such that $P({\alpha} ,f({\alpha} ))$ is true for all ${\alpha} \in I$ , so we have $f({\alpha} )\in X_{\alpha} , \forall {\alpha} \in I$ . This function is what we search for in the axiom of choice.

$\blacksquare$

Exercise 8.4.2. Let $I$ be a set, and for each $\alpha \in I$ let $X_{\alpha}$ be a non-empty set. Suppose that all the sets $X_{\alpha}$ are disjoint from each other, i.e., $X_{\alpha}\cap X_{\beta}=\emptyset$ for all distinct $\alpha, \beta\in I$ . Using the axiom of choice, show that there exists a set $Y$ such that $\#(Y\cap X_{\alpha})=1$ for all $\alpha \in I$ (i.e., $Y$ intersects each $X_{\alpha}$ in exactly one element). Conversely, show that if the above statement was true for an arbitrary choice of sets $I$ and non-empty disjoint sets $X_{\alpha}$ , then the axiom of choice is true.
Solution: By the axiom of choice, there’s a function $(x_{\alpha})_{{\alpha} \in I}$ which assigns to each ${\alpha} \in I$ an element $x_{\alpha} \in X_{\alpha}$ . Let $Y=\{x_{\alpha}:{\alpha} \in I\}$ , which is the range of $(x_{\alpha})_{{\alpha} \in I}$ , then $Y\cap X_{\alpha} =\{x_{\alpha}\}$ for all ${\alpha} \in I$ , thus $\#(Y\cap X_{\alpha})=1$ .
Conversely, if $I$ is a set and $X_{\alpha} \neq \emptyset,\forall {\alpha} \in I$ , let $Y_{\alpha} =\{{\alpha} \}\times X_{\alpha}$ , then each $Y_{\alpha}$ is non-empty, and $Y_{\alpha} \cap Y_{\beta} =\emptyset$ for all distinct ${\alpha} ,{\beta} \in I$ . Use the condition, we can see that there’s a set $Y$ such that $\#(Y\cap Y_{\alpha} )=1,\forall {\alpha} \in I$ . For each ${\alpha} \in I$ , we define $f({\alpha})$ to be the element that $({\alpha} ,f({\alpha}))\in Y\cap Y_{\alpha}$ , since there can only be one such element, $f$ is successfully defined, and $({\alpha} ,f({\alpha}))\in Y_{\alpha} \implies f({\alpha} )\in X_{\alpha}$ , which means the axiom of choice is true.

$\blacksquare$

Exercise 8.4.3. Let $A$ and $B$ be sets such that there exists a surjection $g:B\to A$ . Using the axiom of choice, show that there exists an injection $f:A\to B$ with $g\circ f:A\to A$ the identity map; in particular $A$ has lesser or equal cardinality to $B$ in the sence of Exercise 3.6.7. Conversely, show that if the above statement is true for arbitrary sets $A,B$ and surjections $g:B\to A$ , then the axiom of choice is true.
Solution: For each $a\in A$ , we see that there exists $g^{-1} (a)\in B$ since $g$ is a surjection, which means the set $g^{-1} (\{a\})$ is not empty. By the axiom of choice, we can find a function $f:A\to B$ such that $f(a)\in g^{-1} (\{a\})$ . To see that $f$ is an injection, suppose $f(a)=f(b)$ , then $g(f(a))=g(f(b))$ , but by definition, $g(f(a))\in \{a\},g(f(b))\in \{b\}$ , so we have $a=b$ .
Conversely, we further need the amendment from Terence Tao in his blog:

So if for arbitrary sets $A,B$ and a surjection $g:B\to A$ , we can have an injection $f:A\to B$ with $g\circ f:A\to A$ the identity map, then let $I$ be a set and $X_{\alpha} \neq \emptyset,\forall {\alpha} \in I$ , and $X_{\alpha} \cap X_{\beta} =\emptyset$ for all distinct ${\alpha} ,{\beta} \in I$ . We shall find a $Y$ such that $\#(Y\cap X_{\alpha} )=1,\forall {\alpha} \in I$ .
We define a function $g:\bigcup_{{\beta} \in I}X_{\beta} \to I$ as follows: for $\forall x\in \bigcup_{{\beta} \in I}X_{\beta} ,g(x)={\alpha}$ if $x\in X_{\alpha}$ , since $X_{\alpha} \cap X_{\beta} =\emptyset$ for all distinct ${\alpha} ,{\beta} \in I$ , $x$ can only belong to one $X_{\alpha} \subseteq \bigcup_{{\beta} \in I}X_{\beta}$ , which means $g$ is well-defined. Further as $X_{\alpha} \neq \emptyset,\forall {\alpha} \in I, g$ is a surjection. So we can have an injection $f:I\to \bigcup _{{\beta} \in I}X_{\beta}$ with $g\circ f:I\to I$ the identity map, i.e.

$g(f({\alpha}))={\alpha} ,\quad \forall {\alpha} \in I$

Now define $Y=\{f({\alpha}): {\alpha} \in I\}\subseteq \bigcup_{{\beta} \in I}X_{\beta}$ , then given ${\alpha} \in I$ , we know that $f({\alpha} )\in X_{\alpha}$ , so

$f({\alpha})\in Y\cap X_{\alpha} ,\quad \forall {\alpha} \in I$

meaning that $\#(Y\cap X_{\alpha})\geq 1,\forall {\alpha} \in I$ . On the other hand, assume we have $a\neq b\in Y\cap X_{\alpha}$ for some ${\alpha} \in I$ , then $a,b\in Y$ , thus there’s $m\neq n\in I$ such that

$a=f(m),\quad b=f(n)$

Since $m\neq n$ , at least one of $m,n$ doesn’t equal ${\alpha}$ , we further assume $m\neq {\alpha}$ .
From $a\neq b\in Y\cap X_{\alpha}$ we also we have $a,b\in X_{\alpha}$ , thus $f(m)\in X_{\alpha}$ , but $f(m)\in X_m$ and $m\neq {\alpha}$ , we deduce $f(m)\in X_m\cap X_{\alpha}$ , or $X_m\cap X_{\alpha} \neq \emptyset$ , this is a contradiction, so we must have $a=b$ , this means $\#(Y\cap X_{\alpha} )=1$ .
Using Exercise 8.4.2 we can see the axiom of choice is true.

$\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.…》