集合 (set)

• 集合中的元素需明確定義，一個元素$s$必定屬於集合$S$ ($s \in S$)，或是不屬於集合$S$ ($s \notin S$)。

• 集合中的元素不會重複且無排列關係。

• 空集 $\phi$為任何集合的子集合 ($\phi \subseteq S$)，所以一個包含有$n$個元素的有限集合($|S| = n$)的子集合個數為　$C^{n}_0 + C^{n}_1 + \cdots + C^{n}_n = 2^n$。

有序集合 (Order set)

• 定義：有序集合
  • 在集合$S$的序列(order)是一種關係(relation)，記為$(S, \leq)$，且滿足以下性質：
  • (反身性, reflexive) $\forall x \in S,\ x \leq x$.
  • (反對稱性，antisymmetric) $\forall x, y \in S$, if $x \leq y$ and $y \leq x$, then $x = y$.
  • (遞移性，transitive) $\forall x, y, z \in S$, if $x \leq y$, and $y \leq z$, then $x \leq z$.

全序集合 (Total order set)

• 定義：全序集合
  • $\forall x,y \in S,\ x \leq y \text{ or } y \leq x$.
  • 由定義可得全序集合中任兩個元素必定可以比較大小。
  • 可得出$(\mathbb{R}^n, \leq )$, $n=1$時為全序集合，但$n \geq 2$ 為有序集合。

集合的上界與下界(upper bound and lower bound of set)

• $(S, \leq)$為有序集合，$E \subseteq S$。

• 定義：有上界(bounded above)
  • $\exists b \in S \ni \forall x \in E, \ x \leq b$.
  • 稱$b$為集合$E$的上界。
• 定義：有下界(bounded below)
  • $\exists a \in S \ni \forall x \in E, \ x \geq a$.
  • 稱$a$為集合$E$的下界。

• $a, b$不需為集合$E$的元素，其原因是若$E$為open set或是非連續集合(如有理數集合)時可能無法直接用集合內元素定義上下界。

• 若集合$E$同時存在有上、下界時，稱為有界集合(bounded set)。

最小上界與最大下界(supremum and infmum)

• $(S, \leq)$為有序集合，且$E \subseteq S$。

• 定義：Least upper bound or supremum (最小上界)
  • $b = \sup E$ 為集合$E$的最小上界若
  • $b$為集合$E$的上界，而且比$b$小的實數都不是$E$的上界。
• 定義：Greatest lower bound or infmum (最大下界)
  • $a = \inf E$ 為集合$E$的最大下界若
  • $a$為集合$E$的下界，而且比$a$大的實數都不是$E$的下界。

• $\sup S, \inf S$由定義可知若存在時具唯一性。

• E.g. $[a,b]$, $[a,b)$, $(a,b]$, and $(a,b)$四個集合的sup均為$b$，inf均為$a$。

• E.g. $\lbrace r\in \mathbb{Q} \vert r \geq 0 \cap r^2 < 2 \rbrace$的sup為$\sqrt{2}$, inf為0。

最小上界性質(least-upper-bound property)

• 定義：令$(S, \leq)$為有序集合，則least-upper-bound property即集合$\phi \neq E \subset S$有上界時，則最小上界必定為$S$的元素($\sup E \in S$)。

• E.g. 有理數$\mathbb{Q}$不滿足最小上界性質。

  • 令$A = \lbrace x \in \mathbb{Q}^{+} \vert x^2 < 2 \rbrace$.
  • 集合$A$有上界(is bounded above)
    • 但是$\sup A = \sqrt{2} \notin \mathbb{Q}$.

• Theorem: 若$S$為有序集合，且有最小上界性質，令$\phi \neq B \subset S$有下界(bounded below)，則集合$B$的最大下界必為$S$的元素($\inf B \in S$).
  • Let $L$ be the set of all lower bounds of $B$.
  • $\therefore \forall x \in B$, $x$ is an upper bound of $L$.
  • $\therefore a = \sup L \in B \in S$.
  • claim $a = \int B$
    • $a \in L$ i.e. if $x \in B$ then $a \leq x$. (所有集合$B$中的元素必定大於等於$a$)
    • If $a > c$, then $c \notin B$.
    • Given $a > c$, because $a = \sup L$, $\therefore$ $c$ is not an upper bounded of $L$

實數的完備性

• 定理: 實數系的完備性，可用來保證最小上界與最大下界的存在性。
  1. 實數集合 $\mathbb{R}$ 中，每個非空有上界的子集合有最小上界。
  2. 實數集合 $\mathbb{R}$ 中，每個非空有下界的子集合有最大下界。
  • Proof(1)
  • 令$\phi \neq S \subseteq \mathbb{R}$，且有上界。
  • 令$A =\{ a \in \mathbb{R} | \exists x \in S \ni x > a \}$.
  • 令$B= \{ b \in \mathbb{R} | \forall x \in S \ni x \leq b \}$.(集合$S$所有上界形成的集合)
  • $\because S \neq \phi \therefore A \neq \phi$.
  • $\because S$有上界，所以$B \neq \phi$.
  • 根據定義可得$A \cup B = \mathbb{R},\ A \cap B = \phi$, 而且$A < B$。
  • 因此根據完備性的定義，存在$r \in \mathbb{R} \ni \forall a \in A, a \leq r \text{ and } \forall b \in B, b \geq r$.
  • 只要能證明$r \in B$，則因為$B$是所有上界形成的集合，就可得$r = \sup S$.
  • (反證法)
  • 若$r \notin B$，則$r \in A$，根據定義$\exists s \in S \ni r < s$。
  • $\because s \in S \text{ and } (r+s)/2 < s$，$\therefore (r+s)/2 \in A \text{ and} (r+s)/2 > r$, 與$r$的性質矛盾。
  • 所以$r \in B$，因此存在最小上界。(QED)。

  • ---

  • Proof(2): (由(1)的結論證明)
  • 令$\phi \neq T \subset \mathbb{R}$, 且有下界。
  • 令$S = \{ x \in \mathbb{R}| -x \in T \}$，可得$S \neq \phi$。
  • 因為$T$有下界，因此$S$有上界，所以$S$有最小上界$b = \sup S$。
  • 以下證明$-b = \inf T$.
  • $\forall y \in T, -y \in S \Rightarrow -y \leq b$，所以$-b$是$T$的下界。
  • $\forall \epsilon > 0, b - \epsilon < b \therefore \exists x_0 \in S \ni x_0 > b - \epsilon$.
  • $\therefore - x_0 < (-b) + \epsilon$, $\because - x_0 \in T, \therefore (-b) + \epsilon$不是$T$的下界。
  • 因此$-b$是$T$ 的最大下界(QED)。

• Theorem (Approximation property)
  • $\phi \neq S \subseteq \mathbb{R}$, and $\sup S = b$
  • then $\forall a < b \exists x \in S \ni a < x \leq b$.
  • 最小上界(最大下界)若存在時，則集合內任一元素與最小上界間必定存在其它的元素。
  • Proof: $\forall x \in S,\ x \leq b$.
  • If we had $x \leq a,\ \forall x \in S$, then $a$ is an upper bound of $S$ which is smaller than $b$ (contradition).
  • $\therefore x > a$ for at least one $x \in S$. (QED).

最小上界與最大下界性質

• 當實數的非空子集合$S$沒有上界時，則沒有最小上界，此時記為$\sup S = \infty$.
• 當實數的非空子集合$S$沒有下界時，則沒有最大下界，此時記為$\inf S = -\infty$.

• 對於空集合$\phi$，因為對於任意實數$r$，空集合中沒有任何元素大於或小於$r$，因此定義$\sup \phi = -\infty, \inf \phi = \infty$.

• Theorem:基本性質一
  • $\phi \neq S \subset \mathbb{R}, \text{ and } c \in \mathbb{R}$, let $cA = \{ cx | x \in A \}$
  • 若 $c > 0$, 則當$A$有上界時，$cA$也有上界，且$\sup (cA) = c (\sup A)$
  • 若 $c > 0$, 則當$A$有下界時，$cA$也有下界，且$\inf (cA) = c (\inf A)$
  • 若 $c < 0$, 則當$A$有上界時，$cA$也有下界，且$\inf (cA) = c (\sup A)$
  • 若 $c < 0$, 則當$A$有下界時，$cA$也有上界，且$\sup (cA) = c (\inf A)$
  • Proof(3), 令$\sup A = r$
  • Ley $y \in cA \therefore y/c \in A \Rightarrow r \geq y/c$.
  • $\because c < 0 \therefore y \geq c r$，所以$cr$是集合$cA$的下界[1]。
  • $\forall \epsilon > 0, r + \epsilon/c < r$。
  • $\because r = \sup A \therefore \exists x \in A \ni x > r + \epsilon/c \Rightarrow cx < cr + \epsilon$.
  • $\because cx \in cA$，所以$\forall \epsilon > 0,\ cr + \epsilon$不是$cA$的下界[2].
  • 由[1,2]可知$cr$為$cA$的最大下界。(QED)。
• Theorem:基本性質二
  • $A, B \subset \mathbb{R}$為實數中兩個非空子集合。
  • 若$A \subset B$當$B$有上界時，$A$也有上界，且$\sup A \leq \sup B$.
  • 若$A \subset B$當$B$有下界時，$A$也有下界，且$\inf A \geq \inf B$.
  • (兩實數集合最多相交於一點) 若$A$中每個元素$x$與$B$中每個元素$y$均滿足$x \leq y$，則$A$有上界，$B$有下界，且$\sup A \leq \inf B$.
  • (兩實數集合相交或沒有交集)$\forall x \in A, \ \exists y \in B \ni x \leq y$，且$B$有上界時，則$A$也有上界，且$\sup A \leq \sup B$.
  • $\forall x \in A, \ \exists z \in B \ni x \geq z$，且$B$有下界時，則$A$也有下界，且$\inf A \leq \inf B$.
  • E.g. $A=[1,2],\ B=[0,4], \sup A= 2 \leq \sup B =4, \inf A =1 \geq \inf B = 0$.
  • E.g. $A=[1,2],\ B=[2,4], \sup A= 2 \leq \inf B =2$.

• Theorem:基本性質三
  • $A, B \subset \mathbb{R}$為實數中兩個非空子集合。
  • 令$A+B = \{x+y | x \in A,\ y \in B \}$,
  • 當$A,\ B$都有上界時，$A+B$也有上界，且$\sup (A+B) = \sup A + \sup B$.
  • 當$A,\ B$都有下界時，$A+B$也有下界，且$\inf (A+B) = \inf A + \inf B$.
  • 令$AB = \{xy | x \in A,\ y \in B \}$, 且$B \subset \mathbb{R}^{+}$
  • 當$A,\ B$都有上界時，$AB$也有上界，且$\sup(AB) = (\sup A)(\sup B)$.
  • 當$A,\ B$都有下界時，$AB$也有下界，且$\inf(AB) = (\inf A)(\inf B)$.