良序性(Well-ordering principle)

• 若集合$S$為全序集合，且$\forall E \subset S$, $E \neq \phi$必定存在最小元素(least element)，則稱$(S, \leq)$為良序集合。

• E.g. 自然數$\mathbb{N}$為良序集合；但是整數集合$\mathbb{Z}$不為良序集合，因為負整數的集合不含最小元素。

Archimedean property

• 由實數的完備性可得到此性質：$a, b$為任意的正實數，則不論$b$有多大，必須可以找到$a$的整數倍大於$b$。

• Theorem: $a,b \in \mathbb{R}^+$, $\exists n \in \mathbb{N}$, $\ni$ $na> b$.
  • Proof (by contradiction).
  • Suppose $x,y \in \mathbb{R}$ with $x > 0$ such that $nx \leq y$ $\forall n \in \mathbb{N}$.
  • Let $\phi \neq S =\lbrace nx \vert \ \forall n \in \mathbb{N} \rbrace$, then $S$ is bounded above.
  • By least-upper-bound property $\exists \ a = \sup S \in \mathbb{R^{+}}$.
  • $\therefore nx \leq a,\ \forall n \in \mathbb{N}$ $\Rightarrow$ $nx \leq a-x, \forall n \in \mathbb{N}$.
  • The above statement shows that $a-x$ is an upper bound of set $S$, but $a -x < a$, and $a=\sup S$.
  • Thus the assumption $nx \leq y$ $\forall n \in \mathbb{N}$ is false. (QED).

• 必定存在大於任意實數 $r$的整數。 Corollary: $\forall r \in \mathbb{R}^+$ $\exists \ n \in \mathbb{N}$ $\ni$ $n > r$.
• Corollary: $\lim_{n \rightarrow \infty} \frac{1}{n} = 0.$
• Corollary: $\forall x \in \mathbb{R}\ \exists n \in \mathbb{Z} \ni n \leq x < n+1$，通常此整數記為$[x]$
  • Proof: $\because \forall \epsilon > 0$, $\exists n_0 \in \mathbb{N}$ $\ni$ $n_0 \epsilon >1$ (Archimedean prop.) $\therefore \frac{1}{n_0} < \epsilon \ \forall n \geq n_0$.

• Corollary: $\forall x \in \mathbb{R}\ \exists n \in \mathbb{Z} \ni n \leq x < n+1$，通常此整數記為$[x]$
  • Proof:
  • 若$x \in \mathbb{Z}$，則得$n=x$。
  • 若$x > 0$，依Archimedean property，集合$S =\{ m \in \mathbb{N} | m > x \}$不是空集合，因為$S \subset \mathbb{N}$。
  • 依正整數的良序性，$S$存在最小元素$k$，因此$k > x$ 且$k-1 \leq x$。
  • 同理可證$x < 0$ (QED)。

• Theorem: 任意兩個實數間必定在有理數
  • If $x,y \in \mathbb{R} \text{ and }x < y$, then $\exists \ p \in \mathbb{Q} \ni x < p < y$.
  • Proof: 假設 $x > 0$ and $y > 0$.
  • Claim: If $y -x > 1$ then $\exists n \in \mathbb{N} \ni x < n < y$.
    • Because $S = \lbrace p \in \mathbb{N} \vert p > x\rbrace$, by Archimedean property we get $S \neq \phi$.
    • By well-ordering principle, $S$ has la least element $n$ such that $x < n \leq x+1< y$.

可數與不可數集合 (Countable and uncountable set)

• 集合$S$是否可數，可分為以下三類。

• 可數有限個元素(Countable finite)

• 可數無限個元素(Counable infinite)：exists 1-to-1 function between set $S$ and natural number $\mathbb{N}$。

• 不可數(Uncountable): 如果$S$不為countable時，即為uncountable。

• Theorem:可數集合$S$中的任意子集合$A$仍為可數，因為很容易得出$A$與$\mathbb{N}$存在1-to-1 function。
• Theorem: Let ${E_n},\ n \in \mathbb{N}$ are a sequence of countable sets, $S = \cup_{n \in \mathbb{N}} E_n$ is countable set.