顯示具有 數學分析 標籤的文章。 顯示所有文章
顯示具有 數學分析 標籤的文章。 顯示所有文章

1/09/2025

[數學分析] 連續函數族的逐點上包絡函數不一定連續

連續函數有諸多用途,一般在參數最佳化領域中常見的情況是考慮所謂的上包絡函數(upper envelope function)。


Definition: 定義函數族 \(\{f_t : t \in T\} \) 其中 \(T\) 為 index set 並考慮對任意 \(x \in X\),現在定義上包絡函數(upper envelope function) 或者 逐點上確界函數(pointwise supremum function)
$$ F(x) := \sup_t f_t(x)$$


Question: 一個有趣的問題是如果這些函數族成員都是連續函數,那麼取 supremum 之後所得到的新函數 \(F\) 是否仍為連續呢?

答案是否定的。以下例子說明甚至是定義在緊緻集合上的連續函數族也沒有保證上包絡函數連續。

Example: 考慮一連續函數族 \( \{f_t: t \in [0, T]\} \) 其中 \(f_t(x) := x^t\) 對 \(x \in [0,1]\) 且 \(t \in [0,1]\) 並定義 \(f_0 = 0\)。 則函數族的上包絡函數為 $$ \sup_t f_t(x) = \begin{cases} 1, & x \in (0, 1] \\ 0, & x = 0\end{cases}$$ 讀者不難發現此函數在 \(x=0\) 處有不連續跳點。


Comment: 在最佳控制與數理經濟中有個非常有用的定理可以刻畫上包絡函數的連續性稱作 Berge's Maximum Theorem 有興趣的讀者可以自行查閱。





8/11/2024

[數學分析] 連續函數性質與sublevel set 關係

 考慮 $f: X \to \mathbb{R}$ 為連續函數,則其sublevel set $$L_s := \{x \in X: f(x) \leq s\}$$ 為閉集(closed set)。

Proof.

首先注意到 $(-\infty, s]$ 為在 $\mathbb{R}$ 的 closed set (why?),並且注意到 $f$ 的 sublevel set 可由連續函數 $f$ 的像原(preimage) 表示,亦即, $$f^{-1}((-\infty, s]) = \{x \in X: f(x) \leq s\}$$ 由連續函數等價定理:函數 $f$ 為連續若且唯若對於 $\mathbb{R} $ 中任意 closed set $A$ ,其 $f^{-1}(A) $ 為 closed。現令 $A:=(-\infty, s]$,且 $f$ 為連續,故 $L_s = f^{-1}((-\infty, s])$ 為 closed set。

2/09/2020

[數學分析] 一類 max/min operator 作用在分式 的等式

令函數 $f: \mathbb{N} \to (0,\infty)$,則下列等式成立
$$
\min_{0 \leq k \leq N} \frac{f(k)}{\max_{i\leq k}f(i)} = \min_{0\leq \ell \leq k \leq N} \frac{f(k)}{f(\ell)}
$$

Proof: 
$$\frac{f(k_0)}{f(\ell_0)} := \min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}
$$ 其中 $\ell_0\leq k_0$ 使得  $\text{min}_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}\leq\frac{f(k_0)}{f(\ell_0)}$。

另一方面,令
$$\frac{f(k_1)}{f(\ell_1)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}
$$ 且 $\ell_1\leq k_1$,則我們必定有
$$\frac{f(k_0)}{f(\ell_0)}\leq\frac{f(k_1)}{ \max_{i\leq k_1}\;f(i)}\leq\frac{f(k_1)}{f(\ell_1)}$$
由上述結果,我們得到
$$
\frac{f(k_0)}{f(\ell_0)}=\frac{f(k_1)}{f(\ell_1)}
$$ 亦即
$$\min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}$$ 至此得證。$\square$

1/04/2019

[測度論] 關於 Almost Everywhere

給定測度空間 $(X,\mathcal{M},\mu)$我們說 某性質 $P$ almost everywhere 成立 意思是 對所有非零測度集合此性質 $P$ 都成立。(換言之,除零測度集之外,此性質 $P$ 都成立。)

Lemma:
假設 $f(x) \geq 0$ 且 $f$ 為 $(\mathcal{M}, \mathcal{B}_{\mathbb{R}})$ 可測。假設 $\int f d\mu = 0$ 則 $f(x) = 0$ almost everywhere (i.e., $\mu\{x: f(x)>0\} = 0$)

Proof:
令 $E:= \{x:f(x)>0\}$,我們要證明 $\mu(E) = 0$ 。為此,我們首先證明 $\mu(E_n) = 0$ 其中 $E_n :=\{x: f(x) > 1/n\}$。觀察以下事實 $\cup_n E_n = E$ 且 $E_n \uparrow E$。

觀察
\[
\mu(E_n) := \int 1_{E_n}  \;\;\;\;(*)
\]注意到對任意 $x\in E_n$,我們有 $f(x) > 1/n $,此等同於 $n f(x) > 1$ ,故對任意 $x\in E_n$, $nf(x) 1_{E_n}(x) > 1 \cdot 1_{E_n}(x)$ 。將此用到 $(*)$ 我們得到
\[
\mu(E_n) = \int 1_{E_n} < \int nf(x)1_{E_n} \leq \int nf(x) =n \underbrace{\int f(x) d\mu(x)}_{=0}
\]亦即
\[
\mu(E_n) = 0
\]最後我們檢驗
$$\mu(E) = \mu(\cup_n E_n) = \lim_n \mu(E_n) = 0$$即為所求。$\square$


Lemma 2:
給定 測度空間 $(X,\mathcal{M}, \mu)$ 且 $\mu$ 為complete measure,若 $f$ 為 $(\mathcal{M},\overline{\mathcal{B}}_{\mathbb{R}})$ measurable 且 $f=g$ almost everywhere 則 $g$ 亦為 $(\mathcal{M},\overline{\mathcal{B}}_{\mathbb{R}})$ measurable。

Proof:
要證明 $g$ 為 $(\mathcal{M},\overline{\mathcal{B}}_{\mathbb{R}})$ measurable,我們令 $I:=[a,\infty] \in \overline{\mathcal{B}}_{\mathbb{R}} $ 且僅需證明
$$
g^{-1}(I) \in \mathcal{M}
$$
為此,我們定義集合
\[
M:=\{x: f(x) \neq g(x)\}
\]且 $M \subset N$ 其中 $N$ 為 null set 滿足 $N \in \mathcal{M}$,亦即 $\mu(N)=0$ (故 $
\mu(M)=0$)。觀察
$$
g^{-1}(I) = \underbrace{(g^{-1}(I) \cap M^c)}_{\in \mathcal{M}} \cup \underbrace{(g^{-1}(I)\cap M)}_{\subset N \in \mathcal{M}} \in \mathcal{M}
$$至此證明完畢。$\square$

Lemma 3
令 $\{f_n\}$ 為在 $(X,\mathcal{M},\mu)$ 上的 measurable 函數數列,若 $\mu$ 為 complete measure,且 $\lim_n f_n(x)  = f(x)$ almost everywhere 則 $f$ 為 measurable 。

Proof:
注意到如果 $\lim_n f_n(x) = f(x)$ 逐點收斂,則 $f$ 必然為 measurable (因為 $\lim f_n = \limsup f_n = \liminf_n f_n$ 且 $\limsup f_n$ 與 $\liminf f_n$ 都 measurable)。若 $\lim_n f_n(x) = f(x)$ almost everywhere 令 $N:=\{x: \lim_n f_n(x) \text{ does not exists}\}$ 且 $N \in \mathcal{M}$ 且 $\mu(N)=0$。定義新的函數 $g_n : X \to [-\infty,\infty]$ 滿足
\[ g_n(x):= \begin{cases}
      f_n(x) & x \in N^c \\
      0 & x \in N
   \end{cases}
\]則對任意 $x\in X$,$\lim_n g_n(x)$ 存在,因為
\[ \lim_n g_n(x):= \begin{cases}
      f(x) & x \in N^c \\
      0 & x \in N
   \end{cases} \;\;\;\;(*)
\]將此極限記作 $g(x) := \lim_n g_n(x)$。由於 $N^c,N \in \mathcal{M}$ 故 $g$ 為 mesurable。除此之外,由 $(*)$ 我們得到 $g(x) = f(x)$ almost everywhere。由 Lemma 2 可知 $f$ 為 mesurable。至此證明完畢。 $\square$







10/30/2017

[數學分析] 一類 分式與極小值 的不等式

Theorem
對任意 $i=1,...,m$,若 $a_i \geq 0$ 且 $b_i \geq 0$ 則下列不等式成立
\[
\frac{\sum_{i=1}^m a_i }{\sum_{i=1}^m b_i } \geq \min_i \frac{a_i}{b_i}
\]

Proof:
令 $i^*$ 為 某 index $i$ 使得 $\min_i \frac{a_i}{b_i}$ 成立,亦即 $i^*$ 滿足
\[\frac{{{a_{{i^*}}}}}{{{b_{{i^*}}}}} = \mathop {\min }\limits_i \frac{{{a_i}}}{{{b_i}}}\]我們要證明定理中的不等式成立。以下以各個擊破的方法來求證:

CASE 1:首先注意到若 $a_{i^*} = 0$ 則我們欲證明的不等式自動成立。

CASE 2: 故 假設 $a_{i^*} >0$,注意到若 $b_{i^*} =0$ 則我們得到兩邊不等式為無窮,故不等式仍然成立,故我們不妨假設  $a_{i^*} >0$ 且 $b_{i^*} > 0$ (*),現在觀察
\[
\frac{{\sum\limits_{i = 1}^m {{a_i}} }}{{\sum\limits_{i = 1}^m {{b_i}} }} = \frac{{{a_{{i^*}}} + \sum\limits_{i = 1}^{m - 1} {{a_i}} }}{{{b_{{i^*}}} + \sum\limits_{i = 1}^{m - 1} {{b_i}} }} = \frac{{{a_{{i^*}}}\left( {1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{a_i}}}{{{a_{{i^*}}}}}} } \right)}}{{{b_{{i^*}}}\left( {1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{b_i}}}{{{b_{{i^*}}}}}} } \right)}}\;\;\;\; (**)
\]注意到對任意 $i$ 而言,我們有
\[\frac{{{a_{{i^*}}}}}{{{b_{{i^*}}}}} \leqslant \frac{{{a_i}}}{{{b_i}}}\]又因為 $(*)$ 我們可推得對任意 $i$ 而言,下式成立
\[\frac{{{b_i}}}{{{b_{{i^*}}}}} \leqslant \frac{{{a_i}}}{{{a_{{i^*}}}}}\]故
\[\frac{{{b_i}}}{{{b_{{i^*}}}}} \leqslant \frac{{{a_i}}}{{{a_{{i^*}}}}} \Rightarrow 1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{b_i}}}{{{b_{{i^*}}}}}}  \leqslant 1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{a_i}}}{{{a_{{i^*}}}}}} \]現在將此不等式代入 $(**)$ 我們得到
\[\frac{{{a_{{i^*}}}\left( {1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{a_i}}}{{{a_{{i^*}}}}}} } \right)}}{{{b_{{i^*}}}\left( {1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{b_i}}}{{{b_{{i^*}}}}}} } \right)}} \leqslant \frac{{{a_{{i^*}}}\left( {1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{a_i}}}{{{a_{{i^*}}}}}} } \right)}}{{{b_{{i^*}}}\left( {1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{a_i}}}{{{a_{{i^*}}}}}} } \right)}} = \frac{{{a_{{i^*}}}}}{{{b_{{i^*}}}}}\]亦即
\[\frac{{\sum\limits_{i = 1}^m {{a_i}} }}{{\sum\limits_{i = 1}^m {{b_i}} }} \leqslant \frac{{{a_{{i^*}}}}}{{{b_{{i^*}}}}} = \mathop {\min }\limits_i \frac{{{a_i}}}{{{b_i}}}\]至此得證。$\square$

11/26/2015

[數學分析] 三角多項式 與 三角級數 (1)

三角多項式表示一個函數可以透過 多個三角函數 方式表示,具體定義如下。

============================
Definition: Trigonometric polynomial
我們說 $f(x)$ 為一個 三角多項式( trigonometric polynomial) 若 $f$ 具有下列形式:
\[
f(x) := \sum_{n=0}^N a_n \cos(nx) + b_n \sin (nx) \ \ \ \ \ (*)
\]其中 $a_n, b_n \in \mathbb{C}$ 且 $x \in \mathbb{R}$。;或者上式可等價寫為 複數形式
\[
f(x) := \sum_{n=-N}^N c_n e^{i n x}
\]對任意 $c_n \in \mathbb{C}$ 與 $x \in \mathbb{R}$
============================

Comment:
注意到對於 式子 $(*)$ 可改寫為
\[f(x) = \sum\limits_{n = 0}^N {{a_n}} \cos (nx) + {b_n}\sin (nx) = {a_0} + \sum\limits_{n = 1}^N {{a_n}} \cos (nx) + {b_n}\sin (nx)\]

==========================
FACT 1: Trigonometric polynomial $f$ 為週期函數且週期為 $2 \pi$。
==========================

Proof: 亦即我們要證明 $f(x+2 \pi) = f(x)$,故
\[\begin{array}{l}
f(x + 2\pi ): = \sum\limits_{n =  - N}^N {{c_n}} {e^{in\left( {x + 2\pi } \right)}} = \sum\limits_{n =  - N}^N {{c_n}} {e^{in\left( x \right)}}{e^{in\left( {2\pi } \right)}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \sum\limits_{n =  - N}^N {{c_n}} {e^{in\left( x \right)}}\underbrace {\left[ {\cos n2\pi  + i\sin n2\pi } \right]}_{ = 1} = \sum\limits_{n =  - N}^N {{c_n}} {e^{in\left( x \right)}} = f\left( x \right) \ \ \ \ \square
\end{array}\]

==========================
FACT 2: 下列等式成立:
\[\frac{1}{{2\pi }}\int_{ - \pi }^\pi  {{e^{imx}}} {e^{ - inx}}dx = \left\{ \begin{array}{l}
0,\begin{array}{*{20}{c}}
{}
\end{array}n \ne m\\
1,\begin{array}{*{20}{c}}
{}
\end{array}n = m
\end{array} \right.\]==========================
Proof: omitted.

==========================
FACT 3: Trigonometric polynomial $f$ 的係數 $c_n$ 可由下列積分決定:
\[
c_n = \frac{1}{2 \pi}\int_{-\pi}^\pi f(x) e^{-inx}dx
\]==========================
Proof:
\[\begin{array}{*{20}{l}}
{\frac{1}{{2\pi }}\int_{ - \pi }^\pi  f (x){e^{ - inx}}dx = \frac{1}{{2\pi }}\int_{ - \pi }^\pi  {\sum\limits_{m =  - N}^N {{c_m}} {e^{imx}}} {e^{ - inx}}dx}\\
{\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{2\pi }}\sum\limits_{m =  - N}^N {{c_m}} \int_{ - \pi }^\pi  {{e^{imx}}} {e^{ - inx}}dx}
\end{array}\]利用 FACT 2 可得
\[\frac{1}{{2\pi }}\int_{ - \pi }^\pi  f (x){e^{ - inx}}dx = \frac{1}{{2\pi }}\sum\limits_{m =  - N}^N {{c_m}} \underbrace {\int_{ - \pi }^\pi  {{e^{imx}}} {e^{ - inx}}dx}_{ = 1\begin{array}{*{20}{c}}
{}
\end{array}if\begin{array}{*{20}{c}}
{}
\end{array}n = m} = {c_n} \ \ \ \ \square\]

===================
FACT 4: Trigonometric polynomial $f$ 為 實數函數 若且唯若 $c_n^* = c_{-n}$ ( 其中$( \cdot )^*$) 表示 complex conjugate。
===================

Proof:
$(\Rightarrow)$ 假設 Trigonometric polynomial $f$ 為 Real-valued 函數,我們要證明 $c_n^* = c_{-n}$ 。故由於 $f$ 為 Real-valued 函數,我們有 $f^* = f$;亦即
\[\begin{array}{l}
c_n^* = {\left( {\frac{1}{{2\pi }}\int_{ - \pi }^\pi  f (x){e^{ - inx}}dx} \right)^*} = \frac{1}{{2\pi }}\int_{ - \pi }^\pi  {{f^*}} (x){e^{inx}}dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{2\pi }}\int_{ - \pi }^\pi  f (x){e^{inx}}dx = \frac{1}{{2\pi }}\int_{ - \pi }^\pi  {\sum\limits_{m =  - N}^N {{c_m}} {e^{imx}}} {e^{inx}}dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \frac{1}{{2\pi }}\sum\limits_{m =  - N}^N {{c_m}} \int_{ - \pi }^\pi  {{e^{imx}}} {e^{inx}}dx = {c_{ - n}}.
\end{array}\]

$(\Leftarrow)$ 假設  $c_n^* = c_{-n}$ ,我們要證 Trigonometric polynomial $f$ 為 Real-valued 函數。亦即要證明 $f^* = f$。現在觀察
\[{f^*}(x) = {\left( {\sum\limits_{n =  - N}^N {{c_n}} {e^{inx}}} \right)^*} = \sum\limits_{n =  - N}^N {c_n^*} {e^{ - inx}} = \sum\limits_{n =  - N}^N {c_{ - n}^{}} {e^{ - inx}}\]令 $m:=-n$ 可得
\[{f^*}(x) = \sum\limits_{n =  - N}^N {c_n^*} {e^{ - inx}} = \sum\limits_{m =  - N}^N {c_m^{}} {e^{imx}} = f\left( x \right) .\ \ \ \ \square
\]

接著我們可以定義 Trigonometric Series 如下:

========================
Definition: Trigonometric Series 
我們說 Trigonometric Series 為具有下列形式的無窮級數
\[
\sum_{n=-\infty}^\infty c_n e^{-inx}
\]且由先前 Trigonometric polynomial 的係數定法,我們可以一樣定義對一個週期函數 $f$ 的 $m$-th Fourier Coefficient :
\[
c_m := \frac{1}{2 \pi} \int_{-\pi}^\pi f(x) e^{-imx}dx
\]========================

========================
Definition: Fourier Series 
Fourier Series 為一個 Trigonometric Series 且其係數為 Fourier coefficient of $f$,我們將 Fourier Series 記做
\[
f \sim \sum_{n = -\infty}^\infty c_n e^{inx}
\]========================
注意:上述並非等號;單純表示 $c_n$ 是來自 $f$ 的 Fourier Series coefficient。

故我們想問 "何時可以讓 $f$ 與 Fourier Series 等號成立? " 或者說 基於怎樣的測量基準之下,此兩者可以被適當的逼近?

我們將回答此問題於更廣義的 Fourier Series 之上,在後面的文章會在做介紹。


[數學分析] 三角多項式 與 三角級數 (2)- Generalized Fourier Series

現在我們定義廣義 Fourier Series :

=================
Definition: (Orthogonal System of Functions)
令 $\{\phi_n\}$, $n \in \mathbb{N}$ 為在 $[a,b]$ 上 的 Complex-valued 函數 sequence 且滿足下列積分
\[
\int_a^b \phi_n(x) \phi_m^*(x) dx =0, \;\; \text{ if $n \neq m$}
\]那麼我們稱 $\{\phi_n\}$ 為在 $[a,b]$ 上 orthogonal 或稱 (orthogonal system of functions on $[a,b]$) 。除此之外,若積分
\[
\int_a^b \phi_n(x) \phi_n^*(x) dx =1
\]我們稱 $\{\phi_n\}$ 為在 $[a,b]$ 上 orthonormal 或稱 (orthonormal system of functions on $[a,b]$) 。
=====================

Comments: 
一般而言,若我們取 $\{\phi_n\}$  $n \in \mathbb{N}$ 為在 $[0, 2\pi]$ 上 的 Complex-valued 函數 sequence 且滿足 $\phi_n(x):= exp(inx)$  則讀者可自行驗證此 函數 sequence 為 orthogonal


=====================
Definition: (n-th Fourier Coefficient of $f$)
若 $\{\phi_n\}$ 為 orthonormal on $[a,b]$ 且 對任意 $n \in \mathbb{N}$,
\[
c_n:=\int_a^b f(x) \phi_n^*(x) dx
\]我們稱 $c_n$ 為 $n$-th Fourier coefficient of $f$ (relative to $\{\phi_n\}$)
=====================
上述 $^*$ 為 complex conjugate。


=====================
Definition: Generalized Fourier Series
Generalized Fourier Series of $f$ (relative to $\{\phi_n\}$) 定義為
\[
f(x) \sim \sum_{n=1}^\infty c_n \phi_n(x)
\]其中 $c_n=\int_a^b f(x) \phi_n^*(x) dx $。
====================

Theorem: Bessel's inequality
若 $\{\phi_n\}$ 為 orthnormal on $[a,b]$ 且若 $f(x) \sim \sum_{n=1}^\infty c_n \phi_n(x)$ 則 \[
\sum_{n=1}^\infty |c_n|^2 \le \int_a^b |f(x)|^2 dx
\]


====================
Theorem: Best Approximation of Fourier Series 
令 $\{\phi_n\}$ 為在 $[a,b]$ 上 的 Complex-valued 函數 sequence ,且 $\phi_n$ 為 orthogonal。現在定義 $n$-th partial sum of Fourier Series of $f$ 如下
\[
s_n (x):= \sum_{m=1}^n c_m \phi_m(x)
\]且令 $t_n$ 為任意 series 如下
\[
t_n(x) := \sum_{m=1}^n \gamma_m \phi_m(x)
\]其中 $\gamma_n \in \mathbb{C}$ 則
\[
\int_a^b |f (x)- s_n(x)|^2 dx \le \int_a^b |f(x) - t_n(x)|^2 dx
\] 且 上式等式成立 若且為若 $\gamma_n = c_n$ 對任意 $n$。
==================

Proof:

\[
s_n (x):= \sum_{m=1}^n c_m \phi_m(x);\;\;\; t_n(x) := \sum_{m=1}^n \gamma_m \phi_m(x)
\]
我們首先證明下列不等式成立
\[
\int_a^b |f (x)- s_n(x)|^2 dx \le \int_a^b |f(x) - t_n(x)|^2 dx
\] 首先觀察
\[\begin{array}{l}
\int_a^b | f(x) - {t_n}(x){|^2}dx = \int_a^b {\left( {f(x) - {t_n}(x)} \right){{\left( {f(x) - {t_n}(x)} \right)}^*}} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {\left( {f(x){f^*}(x) - f(x){t_n}^*(x) - {t_n}(x){f^*}(x) + {t_n}(x){t_n}^*(x)} \right)} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \underbrace {\int_a^b {{{\left| {f(x)} \right|}^2}} dx}_{term1} - \underbrace {\int_a^b {f(x){t_n}^*(x)} dx}_{term2} - \underbrace {\int_a^b {{t_n}(x){f^*}(x)} dx}_{term3} + \underbrace {\int_a^b {{{\left| {{t_n}(x)} \right|}^2}} dx}_{term4} \ \ \ \ \ \ (*)
\end{array}\]接著對上式逐項觀察,首先檢驗 term 2:
\[\begin{array}{l}
\int_a^b {f(x){t_n}^*(x)} dx = {\int_a^b {f(x)\left[ {\sum\limits_{m = 1}^n {{\gamma _m}} {\phi _m}(x)} \right]} ^*}dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {f(x)\sum\limits_{m = 1}^n {{\gamma _m}^*} {\phi _m}^*(x)} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \sum\limits_{m = 1}^n {{\gamma _m}^*} \underbrace {\int_a^b {f(x){\phi _m}^*(x)} dx}_{ = {c_m}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \sum\limits_{m = 1}^n {{\gamma _m}^*} {c_m}
\end{array}\]
接著我們檢驗 term 3:
\[\begin{array}{l}
\int_a^b {{t_n}(x){f^*}(x)} dx = \int_a^b {\sum\limits_{m = 1}^n {{\gamma _m}} {\phi _m}(x){f^*}(x)} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \sum\limits_{m = 1}^n {{\gamma _m}} \underbrace {\int_a^b {{f^*}(x){\phi _m}(x)} dx}_{ = c_m^*}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \sum\limits_{m = 1}^n {{\gamma _m}} c_m^*
\end{array}\]
最後檢驗 term 4:
\[\begin{array}{l}
\int_a^b {{{\left| {{t_n}(x)} \right|}^2}} dx = \int_a^b {{t_n}(x)t_n^*(x)} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = {\int_a^b {\sum\limits_{m = 1}^n {{\gamma _m}} {\phi _m}(x)\left[ {\sum\limits_{k = 1}^n {{\gamma _k}} {\phi _k}(x)} \right]} ^*}dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {\sum\limits_{m = 1}^n {{\gamma _m}} {\phi _m}(x)\sum\limits_{k = 1}^n {{\gamma _k}^*} {\phi _k}^*(x)} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \sum\limits_{m = 1}^n {{\gamma _m}} \sum\limits_{k = 1}^n {{\gamma _k}^*} \underbrace {\int_a^b {{\phi _m}(x){\phi _k}^*(x)} dx}_{ = 1\begin{array}{*{20}{c}}
{}
\end{array}if\begin{array}{*{20}{c}}
{}
\end{array}m = k}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \sum\limits_{m= 1}^n {{\gamma _m}{\gamma _m}^*}  = \sum\limits_{m = 1}^n {{{\left| {{\gamma _m}} \right|}^2}}
\end{array}\]
故現在將上述結果 帶回 $(*)$ 可得
\[\begin{array}{l}
\int_a^b | f(x) - {t_n}(x){|^2}dx = \underbrace {\int_a^b {{{\left| {f(x)} \right|}^2}} dx}_{term1} - \underbrace {\int_a^b {f(x){t_n}^*(x)} dx}_{term2} - \underbrace {\int_a^b {{t_n}(x){f^*}(x)} dx}_{term3} + \underbrace {\int_a^b {{{\left| {{t_n}(x)} \right|}^2}} dx}_{term4}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {{{\left| {f(x)} \right|}^2}} dx - \sum\limits_{m = 1}^n {\gamma _m^*c_m^{}}  - \sum\limits_{m = 1}^n {{\gamma _m}c_m^*}  + \sum\limits_{m = 1}^n {{{\left| {{\gamma _m}} \right|}^2}}  \ \ \ \ (\star)
\end{array}\]
注意到下列 FACT:
\[\begin{array}{l}
\sum\limits_{m = 1}^n {{{\left| {{c_n} - {\gamma _m}} \right|}^2}}  = \sum\limits_{m = 1}^n {\left( {{c_n} - {\gamma _m}} \right){{\left( {{c_n} - {\gamma _m}} \right)}^*}}  = \sum\limits_{m = 1}^n {\left( {{c_n}{c_n}^* - {c_n}{\gamma _m}^* - {\gamma _m}{c_n}^* + {\gamma _m}{\gamma _m}^*} \right)} \\
 \Rightarrow \sum\limits_{m = 1}^n {{{\left| {{c_n} - {\gamma _m}} \right|}^2}}  = \sum\limits_{m = 1}^n {{c_n}{c_n}^*}  - \sum\limits_{m = 1}^n {{c_n}{\gamma _m}^*}  - \sum\limits_{m = 1}^n {{\gamma _m}{c_n}^*}  + \sum\limits_{m = 1}^n {{\gamma _m}{\gamma _m}^*} \\
 \Rightarrow \sum\limits_{m = 1}^n {{{\left| {{c_n} - {\gamma _m}} \right|}^2}}  - \sum\limits_{m = 1}^n {{{\left| {{c_n}} \right|}^2}}  =  - \sum\limits_{m = 1}^n {{c_n}{\gamma _m}^*}  - \sum\limits_{m = 1}^n {{\gamma _m}{c_n}^*}  + \sum\limits_{m = 1}^n {{{\left| {{\gamma _m}} \right|}^2}}
\end{array}\]與
\[\begin{array}{l}
\int_a^b | f(x) - {s_n}(x){|^2}dx = \int_a^b {\left( {f(x) - {s_n}(x)} \right){{\left( {f(x) - {s_n}(x)} \right)}^*}} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {\left( {f(x){f^*}(x) - f(x){s_n}^*(x) - {s_n}(x){f^*}(x) + {s_n}(x){s_n}^*(x)} \right)} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {f(x){f^*}(x)} dx - \int_a^b {f(x){s_n}^*(x)} dx - \int_a^b {{s_n}(x){f^*}(x)} dx + \int_a^b {{s_n}(x){s_n}^*(x)} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {{{\left| {f(x)} \right|}^2}} dx - \int_a^b {\left( {f(x)\sum\limits_{m = 1}^n {{c_m}^*{\phi _m}^*\left( x \right)} } \right)} dx - \int_a^b {\left( {\sum\limits_{m = 1}^n {{c_m}{\phi _m}\left( x \right)} {f^*}(x)} \right)} dx + \int_a^b {\left( {\sum\limits_{m = 1}^n {{c_m}{\phi _m}\left( x \right)} \sum\limits_{k = 1}^n {{c_k}^*{\phi _k}^*\left( x \right)} } \right)} dx\\
{\rm{since}}\begin{array}{*{20}{c}}
{}
\end{array}{s_n}(x): = \sum\limits_{m = 1}^n {{c_m}{\phi _m}\left( x \right)}  \Rightarrow s_n^*(x): = {\left[ {\sum\limits_{m = 1}^n {{c_m}{\phi _m}\left( x \right)} } \right]^*} = \sum\limits_{m = 1}^n {{c_m}^*{\phi _m}^*\left( x \right)} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {{{\left| {f(x)} \right|}^2}} dx - \sum\limits_{m = 1}^n {{c_m}^*} \int_a^b {\left( {f(x){\phi _m}^*\left( x \right)} \right)} dx - \sum\limits_{m = 1}^n {{c_m}} \int_a^b {{f^*}(x){\phi _m}\left( x \right)} dx + \sum\limits_{m = 1}^n {{c_m}} \sum\limits_{k = 1}^n {{c_k}^*} \int_a^b {{\phi _m}\left( x \right){\phi _k}^*\left( x \right)} dx\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {{{\left| {f(x)} \right|}^2}} dx - \sum\limits_{m = 1}^n {{c_m}^*} {c_m} - \sum\limits_{m = 1}^n {{c_m}} c_m^* + \sum\limits_{m = 1}^n {{c_m}{c_m}^*} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {{{\left| {f(x)} \right|}^2}} dx - \sum\limits_{m = 1}^n {{c_m}^*} {c_m}\\
 \Rightarrow \int_a^b | f(x) - {s_n}(x){|^2}dx = \int_a^b {{{\left| {f(x)} \right|}^2}} dx - \sum\limits_{m = 1}^n {{{\left| {{c_m}} \right|}^2}}
\end{array}\]

故 $\star$ 可進一步改寫
\[\begin{array}{l}
\int_a^b | f(x) - {t_n}(x){|^2}dx = \int_a^b {{{\left| {f(x)} \right|}^2}} dx - \sum\limits_{m = 1}^n {\gamma _m^*c_m^{}}  - \sum\limits_{m = 1}^n {{\gamma _m}c_m^*}  + \sum\limits_{m = 1}^n {{{\left| {{\gamma _m}} \right|}^2}} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b {{{\left| {f(x)} \right|}^2}} dx + \sum\limits_{m = 1}^n {{{\left| {{c_n} - {\gamma _m}} \right|}^2}}  - \sum\limits_{m = 1}^n {{{\left| {{c_n}} \right|}^2}} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \underbrace {\int_a^b {{{\left| {f(x)} \right|}^2}} dx - \sum\limits_{m = 1}^n {{{\left| {{c_n}} \right|}^2}} }_{ = \int_a^b | f(x) - {s_n}(x){|^2}dx} + \sum\limits_{m = 1}^n {{{\left| {{c_n} - {\gamma _m}} \right|}^2}} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \int_a^b | f(x) - {s_n}(x){|^2}dx + \underbrace {\sum\limits_{m = 1}^n {{{\left| {{c_n} - {\gamma _m}} \right|}^2}} }_{ \ge 0}\\
 \Rightarrow \int_a^b | f(x) - {t_n}(x){|^2}dx \ge \int_a^b | f(x) - {s_n}(x){|^2}dx\\

\end{array}\]
且若 $c_m = \gamma_m$ 則等式成立。 $\square$

[數學分析] 內積空間的不等式 Cauchy-Schwarz Inequality 與 Triangular Inequality

==============================
Theorem: (Cauchy-Schwarz Inequality) 
令 $V$ 為實數內積空間,且  ${\bf u}, {\bf v} \in V$ 則\[
|({\bf u}, {\bf v})| \le ||{\bf u}|| \; ||{\bf v}||
\]==============================


先看幾個例子
Example 1: 歐幾里德平面空間對應的 柯西不等式 
$V:=\mathbb{R}^2$ 且配備標準內積 $({\bf u}, {\bf v}) := {\bf u}^T {\bf v}$,現令 ${\bf u}:=[u_1\;\;u_2]^T; \; {\bf v}:=[v_1\;\;v_2]^T$ 則上述的 Cauchy-Schwarz Inequality 可表為
\[\begin{array}{l}
\left| {\left( {{\bf{u}},{\bf{v}}} \right)} \right| \le \left\| {\bf{u}} \right\|\left\| {\bf{v}} \right\|\\
 \Rightarrow {\left| {{{\bf{u}}^T}{\bf{v}}} \right|^2} \le \left( {{{\bf{u}}^T}{\bf{u}}} \right)\left( {{{\bf{v}}^T}{\bf{v}}} \right)\\
 \Rightarrow {\left| {{u_1}{v_1} + {u_2}{v_2}} \right|^2} \le \left( {u_1^2 + u_2^2} \right)\left( {v_1^2 + v_2^2} \right)
\end{array}\]

Example 2: 有限維歐幾里德空間對應的 柯西不等式
$V:=\mathbb{R}^n$ 且配備標準內積 $({\bf u}, {\bf v}) := {\bf u}^T {\bf v}$,現令 ${\bf u}:=[u_1,...,\;\;u_n]^T; \; {\bf v}:=[v_1,...,\;\;v_n]^T$ 則上述的 Cauchy-Schwarz Inequality 可表為
\[\begin{array}{*{20}{l}}
{\left| {\left( {{\bf{u}},{\bf{v}}} \right)} \right| \le \left\| {\bf{u}} \right\|\left\| {\bf{v}} \right\|}\\
{ \Rightarrow {{\left| {{{\bf{u}}^T}{\bf{v}}} \right|}^2} \le \left( {{{\bf{u}}^T}{\bf{u}}} \right)\left( {{{\bf{v}}^T}{\bf{v}}} \right)}\\
{ \Rightarrow {{\left| {{u_1}{v_1} + {u_2}{v_2} + ... + {u_n}{v_n}} \right|}^2} \le \left( {u_1^2 + u_2^2 + ... + u_n^2} \right)\left( {v_1^2 + v_2^2 + ... + v_n^n} \right)}
\end{array}\]

Example 3: 無窮維 實數連續函數空間 對應的 柯西不等式
$V:=C[0,1]$ 且配備內積 $(f(t), g(t)) := \int_0^1 f(t) g(t) dt$,現令 ${\bf u}:=f(t); \; {\bf v}:=g(t)$ 則上述的 Cauchy-Schwarz Inequality 可表為
\[\begin{array}{l}
\left| {\left( {f\left( t \right),g\left( t \right)} \right)} \right| \le \left\| {f\left( t \right)} \right\|\left\| {g\left( t \right)} \right\|\\
 \Rightarrow {\left| {\int_0^1 {f\left( t \right)g\left( t \right)dt} } \right|^2} \le \left( {\int_0^1 {{f^2}\left( t \right)dt} } \right)\left( {\int_0^1 {{g^2}\left( t \right)dt} } \right)
\end{array}\]

Example 4: 實數矩陣空間對應的柯西不等式
令 $V:= M_{n \times n}$ 且配備內積 $(A, B) := tr(B^T A)$ 現令 ${\bf u}:=A; \; {\bf v}:=B$ 為 $n \times n$ 矩陣,則上述的 Cauchy-Schwarz Inequality 可表為
\[\begin{array}{*{20}{l}}
{\left| {\left( {{\bf{u}},{\bf{v}}} \right)} \right| \le \left\| {\bf{u}} \right\|\left\| {\bf{v}} \right\|}\\
{ \Rightarrow {{\left| {tr\left( {{B^T}A} \right)} \right|}^2} \le tr\left( {{A^T}A} \right)tr\left( {{B^T}B} \right)}
\end{array}\]

Example 5: 隨機變數所成的 $L^2$ 空間之柯西不等式:
令 $V:= L^p :=\{X: E[|X|^2] < \infty\}$ 且配備內積 $(X,Y) := E[XY]$,其中 $X,Y$ 為隨機變數,$E[\cdot]$ 表期望值。現令 ${\bf u} := X$ 且 ${\bf v} := Y$ 則上述的 Cauchy-Schwarz Inequality 可表為
\begin{align*}
  & \left| {\left( {{\mathbf{u}},{\mathbf{v}}} \right)} \right| \leq \left\| {\mathbf{u}} \right\|\left\| {\mathbf{v}} \right\| \hfill \\
 &  \Rightarrow \left| {E\left[ {XY} \right]} \right| \leq \left\| X \right\|\left\| Y \right\| \hfill \\
  & \Rightarrow \left| {E\left[ {XY} \right]} \right| \leq \sqrt {E\left[ {{X^2}} \right]} \sqrt {E\left[ {{Y^2}} \right]}  \hfill \\
\end{align*}



Comments:
1.上述幾個例子展示了儘管所表現的樣式非常不同,但從抽象化觀點而言是同一件事情。
2. 柯西等式何時成立?

以下我們給出 Cauchy-Schwarz Inequality 的證明,此證明頗具巧思有興趣的讀者可細細品味。

Proof of Cauchy-Schwarz Inequality
令 $c \in \mathbb{R}^1$ 現在觀察
\[\begin{array}{l}
\underbrace {\left( {{\bf{u}} - c{\bf{v}},{\bf{u}} - c{\bf{v}}} \right)}_{ = {{\left\| {{\bf{u}} - c{\bf{v}}} \right\|}^2}} = \left( {{\bf{u}},{\bf{u}}} \right) + \left( { - c{\bf{v}},{\bf{u}}} \right) + \left( {{\bf{u}}, - c{\bf{v}}} \right) + \left( { - c{\bf{v}}, - c{\bf{v}}} \right)\\
 = \left( {{\bf{u}},{\bf{u}}} \right) - c\left( {{\bf{v}},{\bf{u}}} \right) - c\left( {{\bf{u}},{\bf{v}}} \right) + {c^2}\left( {{\bf{v}},{\bf{v}}} \right)\\
 = \left( {{\bf{u}},{\bf{u}}} \right) - 2c\left( {{\bf{u}},{\bf{v}}} \right) + {c^2}\left( {{\bf{v}},{\bf{v}}} \right) \;\;\;\; (*)
\end{array}\]
若 ${\bf{v}} \ne 0$ 則 $({\bf v},{\bf v})>0$ 我們可取 \[c: = \frac{{\left( {{\bf{u}},{\bf{v}}} \right)}}{{\left( {{\bf{v}},{\bf{v}}} \right)}}\]將此 $c$ 帶入 $(*)$ 可得
\[\begin{array}{l}
{\left\| {{\bf{u}} - c{\bf{v}}} \right\|^2} = \left( {{\bf{u}},{\bf{u}}} \right) - 2c\left( {{\bf{u}},{\bf{v}}} \right) + {c^2}\left( {{\bf{v}},{\bf{v}}} \right)\\
 = \left( {{\bf{u}},{\bf{u}}} \right) - 2\frac{{\left( {{\bf{u}},{\bf{v}}} \right)}}{{\left( {{\bf{v}},{\bf{v}}} \right)}}\left( {{\bf{u}},{\bf{v}}} \right) + {\left( {\frac{{\left( {{\bf{u}},{\bf{v}}} \right)}}{{\left( {{\bf{v}},{\bf{v}}} \right)}}} \right)^2}\left( {{\bf{v}},{\bf{v}}} \right)\\
 = \left( {{\bf{u}},{\bf{u}}} \right) - \frac{{{{\left( {{\bf{u}},{\bf{v}}} \right)}^2}}}{{\left( {{\bf{v}},{\bf{v}}} \right)}}
\end{array}\]但由於 ${\left\| {{\bf{u}} - c{\bf{v}}} \right\|^2} \ge 0$ 故
\[\left( {{\bf{u}},{\bf{u}}} \right) - \frac{{{{\left( {{\bf{u}},{\bf{v}}} \right)}^2}}}{{\left( {{\bf{v}},{\bf{v}}} \right)}} \ge 0 \Rightarrow \left( {{\bf{u}},{\bf{u}}} \right)\left( {{\bf{v}},{\bf{v}}} \right) \ge {\left( {{\bf{u}},{\bf{v}}} \right)^2}\]
上式結果說明在 ${\bf v} \neq 0$ 時 Cauchy-Schwarz Inequality 成立。另外我們回頭檢驗 ${\bf v} = 0$ 的情況,則此時 $\left( {{\bf{u}},{\bf{u}}} \right)\left( {{\bf{v}},{\bf{v}}} \right) \ge {\left( {{\bf{u}},{\bf{v}}} \right)^2}$ 自動滿足。故不論如何我們都有
\[{\left( {{\bf{u}},{\bf{v}}} \right)^2} \le \left( {{\bf{u}},{\bf{u}}} \right)\left( {{\bf{v}},{\bf{v}}} \right)\]至此證畢。$\square$

Comments:
1. 注意到若 ${\bf u} = c {\bf v} $ 則 Cauchy-Schwarz 等式成立。此結果背後蘊含最小平方的最佳化觀點但我們在此不作贅述。
2. 上述 Cauchy-Schwarz Inequality 可引出 Triangular Inequality

Corollary:  Triangular Inequality
令 $V$ 為實數內積空間,若 ${\bf u}, {\bf v} \in V $ 則
\[
||{\bf u} + {\bf v}|| \le ||{\bf u}|| + ||{\bf v}||
\]
Proof:
觀察
\[\begin{array}{l}
||{\bf{u}} + {\bf{v}}|{|^2} = \left( {{\bf{u}} + {\bf{v}},{\bf{u}} + {\bf{v}}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \left( {{\bf{u}},{\bf{u}}} \right) + \left( {{\bf{v}},{\bf{u}}} \right) + \left( {{\bf{u}},{\bf{v}}} \right) + \left( {{\bf{v}},{\bf{v}}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \left( {{\bf{u}},{\bf{u}}} \right) + 2\left( {{\bf{v}},{\bf{u}}} \right) + \left( {{\bf{v}},{\bf{v}}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {\left\| {\bf{u}} \right\|^2} + 2\left( {{\bf{v}},{\bf{u}}} \right) + {\left\| {\bf{v}} \right\|^2}\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le {\left\| {\bf{u}} \right\|^2} + 2\left| {\left( {{\bf{v}},{\bf{u}}} \right)} \right| + {\left\| {\bf{v}} \right\|^2}
\end{array}\]由 Cauchy-Schwarz Inequality 我們有 $
|({\bf u}, {\bf v})| \le ||{\bf u}|| \; ||{\bf v}||$ 故
\[\begin{array}{l}
||{\bf{u}} + {\bf{v}}|{|^2} \le {\left\| {\bf{u}} \right\|^2} + 2\left| {\left( {{\bf{v}},{\bf{u}}} \right)} \right| + {\left\| {\bf{v}} \right\|^2}\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le {\left\| {\bf{u}} \right\|^2} + 2||{\bf{u}}||\;||{\bf{v}}|| + {\left\| {\bf{v}} \right\|^2}\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le {\left( {\left\| {\bf{u}} \right\| + \left\| {\bf{v}} \right\|} \right)^2}
\end{array}\]對兩邊同開根號我們得到
\[
||{\bf u} + {\bf v}|| \le ||{\bf u}|| + ||{\bf v}||
\]即為所求 $\square$

Comment:
若 ${\bf u}, {\bf v}$ 互為正交,亦即 $({\bf u},{\bf v}) = 0$ 則我們有
\[
||{\bf u} + {\bf v}||^2 = ||{\bf u}||^2 + ||{\bf v}||^2
\]上述等式 可視為 畢氏定理 在向量空間中的推廣。

7/12/2015

[基礎數學] 數學歸納法應用例

以下我們簡介證明手段中一個重要的工具:數學歸納法 (Mathematical Induction) 以及一些 應用例子,以下我們給出定義

Theorem: (Mathematical Induction)
給定 $n, n_0 \in \mathbb{N}$ 滿足  $n \ge n_0$,則命題句  $P(n)$ 對任意 $n \ge n_0$ 為真若下列兩個條件成立:

  1. $P(n_0)$ 為真
  2. 對任意 $k \ge n_0$,若 $P(k)$ 為真,則 $P(k+1)$ 為真。


Comments:
1. 對於條件 1,我們稱其為 base case, 對於條件 2,我們稱其為 induction step
2. 想法:關於數學歸納法可以想成推倒骨牌的遊戲,條件一可以想像成推倒第一片骨牌,然後條件二假設如果第 $n$ 片骨牌被推倒,則 $n+1$ 片骨牌必定要倒。


以下我們看幾個例子:

================
Claim: 對任意 $p > -1$ 與 $n \in \mathbb{N}$,下列結果恆成立:
\[
(1+p)^n \ge 1+np
\]===============
Proof:
利用歸納法證明,先使用 $(*)$
考慮 $n=1$ 與 $p = 0$,該結果可簡化為
\[
1 \ge 1
\]故可馬上得知 $n=1$ 時候上述命題成立。接著我們使用 $(**)$,故現在假設
\[
(1+p)^n \ge 1+np
\]我們要證明
\[
(1+p)^{n+1} \ge 1+(n+1)p
\]
觀察
\[
(1+p)^{n+1} = (1+p)^n (1+p) \ge (1+np) (1+p) = 1+n p + p + n p^2
\]
注意到 $np^2 \ge 0$ 故我們有
\[
(1+p)^{n+1} \ge 1 + (n + 1)p\;\;\;\;\;\; \square
\]

Claim:
\[A = \left[ {\begin{array}{*{20}{c}}
1&b\\
0&1
\end{array}} \right]\]試證明
\[{A^n} = \left[ {\begin{array}{*{20}{c}}
1&{nb}\\
0&1
\end{array}} \right]\]
Proof: 首先觀察 $n=1$,原式成立
\[{A^1} = \left[ {\begin{array}{*{20}{c}}
1&b\\
0&1
\end{array}} \right]\]現在利用歸納法,假設
\[{A^n} = \left[ {\begin{array}{*{20}{c}}
1&{nb}\\
0&1
\end{array}} \right]\]我們要證明 $n+1$ 成立,亦即我們要證明
\[{A^{n + 1}} = \left[ {\begin{array}{*{20}{c}}
1&{\left( {n + 1} \right)b}\\
0&1
\end{array}} \right]\]現在觀察上式左方,
\[\begin{array}{l}
{A^{n + 1}} = {A^n}A\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
1&{nb}\\
0&1
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
1&b\\
0&1
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \left[ {\begin{array}{*{20}{c}}
1&{b + nb}\\
0&1
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
1&{\left( {1 + n} \right)b}\\
0&1
\end{array}} \right]
\end{array}\]即為所求。$\square$


讀者不妨練習幾題:
Exercise 1: Show that $1+2+...+n = \frac{n(n+1)}{2}$ for all $n \in \mathbb{N}$
Exercise 2: Show that $n < 2^n$ for all $n \in \mathbb{N}$
Exercise 3: Show that $2^n<n!$ for all $n\geq 4$

Claim: 最小整數原理:
對任意非空集合 $S \neq \emptyset$ 且 $S \subset \mathbb{N}$,則 $S$ 必有最小元素
Proof:
給定任意非空集合 $S := \{n: n \in \mathbb{N}\} $, 首先觀察若 $n=1$,我們有 $S = \{1\}$,且有最小值 $1$ 為其最小元素。

現在用歸納法,假設非空集合 $S_n = \{i: i \le n, i \in \mathbb{N}\} $有最小元素。我們證明 $S_{n+1} := \{i: i \le n+1, i \in \mathbb{N} \}$ 有最小元素。

注意到
$S_{n+1} = S_n \cup \{i: i= n+1\}$ 又因為 $S_n$ 有最小元素,故 $S_{n+1}$ 亦存在最小元素。$\square$

Comment:
上述最小整數原理不適用於任意實數 或者 有理數,舉例而言,若觀察 $E :=\{1, 1/2, 1/3, 1/4, ...\}$ 則此集合不存在最小元素。因為若  $x \in E$ 為最小值 則 必存在 $y \in E$ 使得 $y \leq x$,此時 $y$ 成為新的最小值。

3/28/2015

[系統理論] Picard Iteration

考慮狀態空間
\[{\bf{\dot x}}\left( t \right) = f\left( {t,{\bf{x}}\left( t \right)} \right),{\bf{x}}\left( 0 \right) = {{\bf{x}}^0}\]則 Picard Iteration 給定
1. Initial guess
\[
x(t) = x^0
\]2.. Update Step
\[{{\bf{x}}^{k + 1}}\left( t \right) = {{\bf{x}}^0} + \int_0^t {f\left( {\tau ,{{\bf{x}}^k}\left( \tau  \right)} \right)d\tau } \]
注意到上述迭代式為 sequence of $\{{\bf x}^k\}$


Example 1:
考慮下列非線性系統
\[{\bf{\dot x}}\left( t \right) = \left[ \begin{array}{l}
{{\dot x}_1}\\
{{\dot x}_2}
\end{array} \right] = \left[ \begin{array}{l}
\cos {x_1}\\
t{x_1} + {e^{ - t}}{x_2}
\end{array} \right]
\]且 $x_1(0) = 2$ 與 $x_2(0) = -1$。
試透過 Picard iteration 求取 ${\bf x }^1(t)$

Solution:
\[\begin{array}{l}
{{\bf{x}}^{k + 1}}\left( t \right) = {{\bf{x}}^0} + \int_0^t {f\left( {\tau ,{{\bf{x}}^k}\left( \tau  \right)} \right)d\tau } \\
{{\bf{x}}^1}(t) = {{\bf{x}}^0}(t) + \int_0^t {\left[ \begin{array}{l}
\cos {x_1}\left( \tau  \right)\\
\tau {x_1} + {e^{ - \tau }}{x_2}\left( \tau  \right)
\end{array} \right]} d\tau \\
 \Rightarrow {{\bf{x}}^1}(t) = \left[ \begin{array}{l}
2\\
 - 1
\end{array} \right] + \int_0^t {\left[ \begin{array}{l}
\cos 2\\
\tau 2 + {e^{ - \tau }}\left( { - 1} \right)
\end{array} \right]} d\tau \\
 \Rightarrow {{\bf{x}}^1}(t) = \left[ \begin{array}{l}
2\\
 - 1
\end{array} \right] + \left[ \begin{array}{l}
t\cos 2\\
{t^2} + \left( {{e^{ - t}} - 1} \right)
\end{array} \right] = \left[ \begin{array}{l}
2 + t\cos 2\\
{t^2} + {e^{ - t}} - 2
\end{array} \right]

\end{array}\]

Exercise: 讀者可自行嘗試透過 Picard Iteration 求解 $x^2(t)$ 與 $x^3(t)$


Example 2: Saturation 
考慮非線性系統 $\dot{x} = f(x)$ 且 $x(0) =1$ 其中
\[f\left( x \right) = \left\{ \begin{array}{l}
1,\begin{array}{*{20}{c}}
{}&{}
\end{array}x > 2\\
\frac{1}{2}x,\begin{array}{*{20}{c}}
{}&{}
\end{array}\left| x \right| \le 2\\
 - 1,\begin{array}{*{20}{c}}
{}&{}
\end{array}x <  - 2
\end{array} \right.\]試透過 Picard iteration 求取 $ x^1(t)$ 與 $x^2(t)$
Solution:
首先計算 $x^1(t)$:
\[\begin{array}{l}
{x^1}\left( t \right) = {x^0}\left( t \right) + \int_0^t {f\left( {{x^0}\left( \tau  \right)} \right)d\tau } \\
 \Rightarrow {x^1}\left( t \right) = 1 + \int_0^t {f\left( 1 \right)d\tau } \\
 \Rightarrow {x^1}\left( t \right) = 1 + \frac{1}{2}t
\end{array}\]
接著我們計算 $x^2(t)$:
\[\begin{array}{l}
{x^2}\left( t \right) = {x^0}\left( t \right) + \int_0^t {f\left( {{x^1}\left( \tau  \right)} \right)d\tau } \\
 \Rightarrow {x^2}\left( t \right) = 1 + \left\{ \begin{array}{l}
\int_0^t {\frac{1}{2}\left( {1 + \frac{1}{2}\tau } \right)d\tau ,\begin{array}{*{20}{c}}
{}&{}
\end{array}0 \le t \le 2} \\
\frac{1}{2}\int_0^t {1d\tau } ,\begin{array}{*{20}{c}}
{}&{}
\end{array}t > 2
\end{array} \right.\\
 \Rightarrow {x^2}\left( t \right) = 1 + \left\{ \begin{array}{l}
\frac{1}{2}\left( {t + \frac{1}{4}{t^2}} \right),\begin{array}{*{20}{c}}
{}&{}
\end{array}0 \le t \le 2\\
\frac{1}{2}t,\begin{array}{*{20}{c}}
{}&{}
\end{array}t > 2
\end{array} \right.\\
 \Rightarrow {x^2}\left( t \right) = \left\{ \begin{array}{l}
1 + \frac{t}{2} + \frac{1}{8}{t^2},\begin{array}{*{20}{c}}
{}&{}
\end{array}0 \le t \le 2\\
1 + \frac{t}{2},\begin{array}{*{20}{c}}
{}&{}
\end{array}t > 2
\end{array} \right.
\end{array}\]

12/17/2014

[數學分析] Inverse Function Theorem

想法:
這次要介紹數學分析理論中一個重要的定理,稱作 反函數定理 (Inverse Function Theorem),簡而言之,反函數定理指出 一個 連續可微函數 $f$,若我們考慮點 $x$ 可使其 Linear transformation $f'$ 為 invertibale,則該點 $x$ 附近的 $f'$ 都為 invertible。

Comments:
1. 上述我們所提及的 invertible 我們指 一個 Linear transformation 為 invertible,嚴格來說定義如下:若  linear transformation $A: X \to Y$ 為 invertible,若下列條件滿足:
    (a.) $A$ 為 one-to-one: (i.e., $A x = Ay \Rightarrow x =y$)
    (b.) $A(X) = Y$ (i.e., $A$ maps $X$ onto $Y$ or 對任意 $y \in Y$, 存在 $x \in X$ 使得 $Ax = y$ )

2. 以下討論我們皆以 多變數向量函數 為主,亦即
若 $A \subset \mathbb{R}^n$ 且 $B \subset \mathbb{R}^m$,$n,m \in \mathbb{N}$ 則我們稱 $\bf f$ $: A \to B$ 為多變項量函數 (vector function of several variables.)


接著我們介紹何謂 $C^1$ 函數:
================
Definition: $C^1$ Continuously differentiable
我們稱一個可導的 mapping ${\bf f}: E \subset \mathbb{R}^n \to \mathbb{R}^m$ 為 continuously differentiable in $E$ (記做 ${\bf f} \in C^1(E)$) 若下列條件成立:
${\bf f}':E \to L(\mathbb{R}^n, \mathbb{R}^m)$ 為 continuous mapping ;亦即 對任意 ${\bf x} \in E$ 且 任意 $\varepsilon >0$,存在 $\delta >0$ 使得 對任意 ${\bf y} \in E$,
\[||{\bf{x}} - {\bf{y}}|| < \delta  \Rightarrow ||{\bf{f}}'\left( {\bf{x}} \right) - {\bf{f}}'\left( {\bf{y}} \right)|| < \varepsilon \]================


現在我們可以介紹 反函數定理:
Inverse Function Theorem 的基本想法:
考慮 連續函數 $f: \mathbb{R} \to \mathbb{R}$ 若 $f'>0$ 則我們知道 $f$ 為 monotonic (嚴格來說 $f$ 為 strictly increasing)。我們可推知 $f$ 必為 one-to-one 與 onto (讀者可自行驗證);故 $f$ 為 invertible。

故如果我們觀察以上結果,可發現若 $f' \neq 0$ 且 連續,則 $f$ 必為 invertible。那麼將此結果推廣到多變數向量函數的情況便會得到 Inverse Function Theorem。


======================
Theorem: Inverse Function Theorem
令 ${\bf f} \in C^1(E)$,$E $ 為 open set 且 ${\bf f}: E \subset \mathbb{R}^n \to \mathbb{R}^n$;
假設存在 點 ${\bf a} \in E$ 使得  ${\bf f}'({\bf a})$ 為 invertible linear operator 且 ${\bf{b}} = {\bf{f}}\left( {\bf{a}} \right)$ 則
  1. 存在兩 open sets $U,V \subset \mathbb{R}^n$ 使得 ${\bf{a}} \in U$, ${\bf b} \in V$; 且 $\bf f$ 為 one-to-one on $U$ 且 ${\bf f}(U) = V$。
  2. 若 $\bf g$ 為 inverse of $\bf f$ (定義在 $V$ 上) 且滿足對任意 ${\bf x} \in U$ 我們有 ${\bf{g}}\left( {{\bf{f}}\left( {\bf{x}} \right)} \right) = {\bf{x}}$  則 ${\bf g} \in C^1(V)$
======================

Comment:
Inverse Function Theorem 要求 $\bf f'$$({\bf a})$ 需要為連續 (因為 $C^1$)。此假設是必要的! (若無此假設,反函數不存在。) 我們看下面的例子:

Example
考慮 $n=1$,且考慮
\[f\left( t \right): = \left\{ \begin{array}{l}
t + 2{t^2}\sin \left( {1/t} \right),\begin{array}{*{20}{c}}
{}&{}
\end{array}t \ne 0\\
0\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}
\end{array},\begin{array}{*{20}{c}}
{}&{}
\end{array}t = 0
\end{array} \right.\]則 $f'(0) =1$,$f'$ 在 $(-1,1)$ 上有界,但在 $0$ 點附近任意鄰域 $f$ 並非 one-to-one 。

Proof:
我們首先證明 $f'(0) =1$,由導數定義可知
\[\small
f'\left( 0 \right): = \mathop {\lim }\limits_{h \to 0} \frac{{f\left( {0 + h} \right) - f\left( 0 \right)}}{h} = \mathop {\lim }\limits_{h \to 0} \frac{{h + 2{h^2}\sin \left( {1/h} \right) - 0}}{h} = 1 + 2\mathop {\lim }\limits_{h \to 0} \sin \left( {1/h} \right)h = 1
\]接著我們證明 $f'$ 在 $(-1,1)$ 上有界;亦即 對任意 $x \in (-1,1)$ 要證明 存在 $M$ 使得 $|f'(t)| \le M$。觀察
\[\left| {f'\left( x \right)} \right| = \left| {1 + 4t\sin \left( {1/t} \right) - 2\cos \left( {1/t} \right)} \right| \le 1 + 4 + 2 = 7\]此處暗示了 $f'(0)$ 不為連續函數。 因為
\[\begin{array}{l}
|f'\left( t \right) - f'\left( 0 \right)| = |\left[ {1 + 4t\sin \left( {1/t} \right) - 2\cos \left( {1/t} \right)} \right] - 1|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = |4t\sin \left( {1/t} \right) - 2\cos \left( {1/t} \right)| \le 4|t| + 2 < 4\delta  + 2
\end{array}\]故不管 $\varepsilon$ 選多小都沒辦法使上述誤差項 $|f(t) - f(0)|$ 逼近任意小。

最後我們證明 $0$ 點附近任意鄰域 $f$ 並非 one-to-one:故給定任意 $r>0$ 使得任意$0$ 點附近  鄰域 $B_r(0)$,存在相異點 $x,y \in B_r(0)$ 滿足 $x = -y$ 使得在此鄰域中 $f(x) =f(y)$。注意到 $|x-y| = |x- (-x)| < r \Rightarrow |x| < r/2$ 且
\[\begin{array}{l}
f\left( x \right) - f\left( { - x} \right) = 2x\left[ {x + 2{x^2}\sin \left( {1/x} \right) - \left( { - x - 2{x^2}\sin \left( {1/x} \right)} \right)} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = {\left( {2x} \right)^2}\left[ {1 + 2x\sin \left( {1/x} \right)} \right] < {r^2}\left[ {1 + 2r} \right]
\end{array}\]由於 $r$ 為任意正數,故 $f\left( x \right) = f\left( { - x} \right)$




Proof: Inverse Function Theorem
先證 (1): 亦即要證 存在 open sets $U,V \subset \mathbb{R}^n$ 使得 ${\bf{a}} \in U$, ${\bf b} \in V$; 且 $\bf f$ 為 one-to-one on $U$ 且 ${\bf f}(U) = V$。

想法如下:要證明 one-to-one 除了利用定義之外,我們亦可透過建構輔助函數 利用 contraction principle 的幫助來得到我們所需的結果。


首先令 ${\bf{f}}'\left( {\bf{a}} \right): = A$ 且 選擇 $\lambda \in \mathbb{R}$ 使得 $2 \lambda ||A^{-1}||_L=1 $ $(*)$
(在此 $||\cdot||_L$ 表 operator norm)

由於 $\bf f$ 在 $\bf a$處可導,故可知 $\bf f'$ 為 continuous at 點 $\bf a$;亦即 對任意 $\varepsilon>0$,存在 $\delta >0$ 使得 對任意 ${\bf x} \in E$,
\[
||{\bf{x}} - {\bf{a}}|| < \delta  \Rightarrow ||{{\bf{f}}^\prime }\left( {\bf{x}} \right) - \underbrace {{{\bf{f}}^\prime }\left( {\bf{a}} \right)}_{ = A}|| < \varepsilon
\] 現在取 $\varepsilon:= \lambda$ 可推知:存在 球心為 $\bf a$ 半徑為 $\delta$ 的 open ball $U \subset E$  (表 $||{\bf x} - {\bf a}|| < \delta$) 使得 對任意 $\bf x$ $\in U$,我們有
\[
||{{\bf{f}}^\prime }\left( {\bf{x}} \right) - A|| < \lambda \ \ \ \ \ (\star)
\]現在,對任意 ${\bf y} \in \mathbb{R}^n$,定義輔助函數 $\varphi$ 如下:對任意 $\bf x$ $\in E$
\[
\varphi ({\bf{x}}): = {\bf{x}} + {A^{ - 1}}\left( {{\bf{y}} - {\bf{f}}\left( {\bf{x}} \right)} \right)
\]觀察上式,注意到 ${\bf{f}}\left( {\bf{x}} \right) = {\bf{y}}$ 若且唯若 ${\bf{x}}$ 為 fixed point of $\varphi$。 $(**)$

故我們接著計算 $\varphi'$,首先我們觀察 \[\varphi ({\bf{x}} + {\bf{h}}) - \varphi ({\bf{x}}) = {\bf{h}} - {A^{ - 1}}\left[ {{\bf{f}}\left( {{\bf{x}} + {\bf{h}}} \right) - {\bf{f}}\left( {\bf{x}} \right)} \right]\]故可推知
\[\begin{array}{l}
\varphi '({\bf{x}}) = I + {A^{ - 1}}{\bf{f}}'\left( {\bf{x}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {A^{ - 1}}\left[ {A + {\bf{f}}'\left( {\bf{x}} \right)} \right]
\end{array}\]現在對上式取 norm,並 利用 $(*)$ 與 $(\star)$ 可推知
\[\begin{array}{l}
{\left\| {\varphi '({\bf{x}})} \right\|_L} = {\left\| {{A^{ - 1}}\left[ {A + {\bf{f}}'\left( {\bf{x}} \right)} \right]} \right\|_L}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le {\left\| {{A^{ - 1}}} \right\|_L}{\left\| {A + {\bf{f}}'\left( {\bf{x}} \right)} \right\|_L}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \frac{\lambda }{2} \cdot \lambda  = \frac{1}{2}
\end{array}
\] 上式對任意 $\bf x$ $\in U$ 成立。現在利用 Mean Value Theorem 可知對任意 ${\bf x}_1$, ${\bf x}_2$ $\in U$
\[{\left\| {\varphi ({\bf{x}}_1) - \varphi ({\bf{x}}_2)} \right\|_L} \le \frac{1}{2}{\left\| {{\bf{x}}_1 - {\bf{x}}_2} \right\|_L}\]故由 Contraction principle 可知 $\varphi$ 有唯一固定點 $\bf x$ $\in U$;由 $(**)$可知存在唯一固定點  $\bf x$ 使得 ${\bf{f}}\left( {\bf{x}} \right) = {\bf{y}}$ 因此 $\bf f$ 為 one-to-one in $U$

接著我們證 ${\bf f}(U) = V$ 為 open 。
亦即要證給定任意 ${\bf y}_0 \in V$ 存在 $R>0$ 使得 開球 $B_R({\bf y}_0) \subset V$

令 $V:= {\bf f} (U)$ 則若我們取 ${{\bf{y}}_0} \in V$ 則 存在 ${\bf x}_0$ 使得 ${{\bf{y}}_0} = {\bf{f}}\left( {{{\bf{x}}_0}} \right)$ 。現在取 開球 $B_r({\bf x}_0)$ ,並且讓 $B_r({\bf x}_0)$ 的半徑 $r>0$ 足夠小 使得 開球的 closure $\bar B_r({\bf x}_0) \subset U$。

現在選 $R:= \lambda r$ 我們要證明 開球 $B_R({\bf y}_0) \subset V$,此等價證明以下 Claim:

Claim:   $\left\| {{\bf{y}} - {{\bf{y}}_0}} \right\| < \lambda r \Rightarrow {\bf{y}} \in V$
(此陳述等價對任意 $R:=\lambda r>0$ 存在 open ball $B_{\lambda r} ({\bf y}_0) \subset V$)

固定任意 $\bf y$ 滿足 $||{\bf y} - {\bf y}_0|| < \lambda r$,回憶我們先前定義的 contraction 函數 $\varphi$
\[
\varphi ({\bf{x}}): = {\bf{x}} + {A^{ - 1}}\left( {{\bf{y}} - {\bf{f}}\left( {\bf{x}} \right)} \right)
\]觀察
\[\begin{array}{l}
\left\| {\varphi ({{\bf{x}}_0}) - {{\bf{x}}_0}} \right\| = \left\| {{{\bf{x}}_0} + {A^{ - 1}}\left( {{\bf{y}} - {\bf{f}}\left( {{{\bf{x}}_0}} \right)} \right) - {{\bf{x}}_0}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \left\| {{A^{ - 1}}\left( {{\bf{y}} - {\bf{f}}\left( {{{\bf{x}}_0}} \right)} \right)} \right\| = \left\| {{A^{ - 1}}\left( {{\bf{y}} - {{\bf{y}}_0}} \right)} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} \le \left\| {{A^{ - 1}}} \right\|\left\| {{\bf{y}} - {{\bf{y}}_0}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} < \frac{1}{{2\lambda }}\lambda r = \frac{1}{2}r
\end{array}
\]若 $\bf x$ $\in \bar B_r({\bf x}_0)$ 則 $\left\| {{\bf{x}} - {{\bf{x}}_0}} \right\| \le r$ 且我們有
\[\begin{array}{l}
\left\| {\varphi ({\bf{x}}) - {{\bf{x}}_0}} \right\| = \left\| {\varphi ({\bf{x}}) - \varphi ({{\bf{x}}_0}) + \varphi ({{\bf{x}}_0}) - {{\bf{x}}_0}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} \le \left\| {\varphi ({\bf{x}}) - \varphi ({{\bf{x}}_0})} \right\| + \left\| {\varphi ({{\bf{x}}_0}) - {{\bf{x}}_0}} \right\|
\end{array}
\]由於 $\left\| {\varphi ({{\bf{x}}_1}) - \varphi ({{\bf{x}}_2})} \right\| \le \frac{1}{2}\left\| {{{\bf{x}}_1} - {{\bf{x}}_2}} \right\|$ (注意到此式成立 ${\bf x}_1, {\bf x}_2$ $\in \bar B_r({\bf x}_0)$)故可知
\[\begin{array}{l}
\left\| {\varphi ({\bf{x}}) - {{\bf{x}}_0}} \right\| \le \left\| {\varphi ({\bf{x}}) - \varphi ({{\bf{x}}_0})} \right\| + \left\| {\varphi ({{\bf{x}}_0}) - {{\bf{x}}_0}} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \frac{1}{2}\left\| {{\bf{x}} - {{\bf{x}}_0}} \right\| + \frac{r}{2}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \frac{1}{2}r + \frac{r}{2} = r
\end{array}\]因此 $\varphi({\bf x}) \in B_r({\bf x}_0)$ 故 $\varphi$ 確實為 contraction on $\bar B_r({\bf x}_0)$ ;且由於 $\bar B_r$ 為 closed subset in $\mathbb{R}^n$ 故 $\bar B_r$ 為 complete ,利用 Contraction principle 可知具有唯一固定點 ${\bf x}^*$ $\in \bar B_r({\bf x}_0)$,對此 ${\bf x}^*$ 而言,我們有
\[{\bf{f}}\left( {\bf{x}^*} \right) = {\bf{y}} \in {\bf{f}}\left( {{{\bar B}_r}\left( {{{\bf{x}}_0}} \right)} \right) \subset {\bf{f}}\left( U \right) = V\]因此  ${\bf{y}} \in V$


Corollary: (f is a open mapping of E to R^n)
若 $\bf f$ $\in C^1(E)$,且 ${\bf f}: E \subset \mathbb{R}^n \to \mathbb{R}^n$ 且 若 對任意 $\bf x$,${\bf f}'({\bf x})$ 為 invertible,則 對任意 open set $W \subset E$,${\bf f}(W)$ 為 open subset of $\mathbb{R}^n$  



以下我們看個 Inverse Function Theorem 的應用:

Example
Let $L:\mathbb{R}^n \to \mathbb{R}^n$ be a bounded linear operator such that $||L(\vec x)|| = ||\vec x||$ for all $\vec x \in \mathbb{R}^n$. Define $f(\vec x):=L(\vec x) + g(\vec x)$ where $||g(\vec x)|| \le M ||\vec x||^2$ and $f \in C^1$. Show that $f$ is invertible in a neighborhood of $\vec 0 \in \mathbb{R}^n$.

Proof: First show that $f'(\vec0) = L$. Observe that
\[\begin{array}{l}
\mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{\left\| {f(\vec h) - f\left( {\vec 0} \right) - L\vec h} \right\|}}{{\left\| {\vec h} \right\|}} = \mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{\left\| {L\vec h + g(\vec h) - g(\vec 0) - L\vec h} \right\|}}{{\left\| {\vec h} \right\|}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{\left\| {g(\vec h) - g(\vec 0)} \right\|}}{{\left\| h \right\|}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \le \mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{M{{\left\| {\vec h} \right\|}^2}}}{{\left\| {\vec h} \right\|}} = \mathop {\lim }\limits_{\vec h \to \vec 0} M\left\| {\vec h} \right\| = 0\\
\Rightarrow \mathop {\lim }\limits_{\vec h \to \vec 0} \frac{{\left\| {f(\vec h) - f\left( {\vec 0} \right) - L\vec h} \right\|}}{{\left\| {\vec h} \right\|}} = 0
\end{array}\]Hence, $f'(\vec 0) =L.$ Next, we show $L$ is invertible. Observe that for two vectors $\vec x, \vec y$ $\in \mathbb{R}^n$, suppose $L\vec x = L\vec y$, we have by linearity,

$L\left( {\vec x - \vec y} \right) = 0$. This shows $\vec x = \vec y$; i.e., $L$ is invertible. Now, by inverse function theorem, we know that $f$ is invertible in a neighborhood of $\vec 0$ $\in \mathbb{R}^n$. $\square$

10/25/2014

[數學分析] Compactness 與 Totally Boundedness

令 $X$ 為 metric space 且 metric 為 $d$;亦即 $(X,d)$ 為 metric space。

==========================
Definition: Compact Metric Space
(a) 由 open subsets 所形成的集合  $\{G_\alpha\}_{\alpha \in A} $ 被稱為 open cover 若 下列條件成立:
對任意 $x \in X$ 存在 $\alpha \in A$ 使得 $x \in G_\alpha$。

若 index set $A$ 為 finite 則 $\{G_\alpha\}$ 為 finite open cover。

(b) 我們說 metric space $(X,d)$ 為 compact 若下列條件成立:
對任意 open cover of $X$,存在 有限個 subcover of $X$。
==========================

Comment
注意到上述定義在 metric space $(X,d)$ 之上,若我們現在考慮其上的子集合:
\[
A \subset X
\]則 $A$ 仍為一個 metric space 且 metric 為 $d$;亦即 $(A,d)$ 仍為一個 metric space。


==========================
Definition: Compact Set
集合 $A \subset X$ 為 compact 若下列條件成立:
metric space $(A,d)$ 為 compact (亦即:對任意 open cover 存在 有限 subcover of $A$。)
==========================



==========================
Definition: Relatively Compact
集合 $A \subset X$ 稱為 relatively compact 若下列條件成立
\[
\bar A \subset X \text{ is compact}
\]上述 $\bar{A}$ 表示 closure of $A$
==========================

==========================
Theorem: Heine-Borel Theorem
若 $A \subset \mathbb{R}^n$ (或者 $\mathbb{C}^n$) 為 closed + bounded 則 $A$ 為 compact。
==========================

==========================
Definition: Sequentially Compact
我們說一個 metric space $(X,d)$ 為 sequentially compact 若下列條件成立
對任意 sequence in $X$ 存在 收斂 subsequence 。
==========================

==========================
Definition: Totally Bounded
一個 metric space $(X,d)$ 稱為 totally bounded 若下列條件成立:
對任意 $\varepsilon>0$,存在有限個 以半徑為 $\varepsilon$ 的 open Ball $\mathcal{B}_\varepsilon$ 所組成的集合 並且 covers $X$。
==========================


Example
考慮 $l^p$ space $:= \{\{a_n\}_n: \sum_{n}^\infty |a_n|^p < \infty, 0 <p <\infty\}$;且定義 metric 如下
\[d\left( {{a_n},{b_n}} \right): = {\left( {\sum\limits_{n = 1}^\infty  {|{a_n} - {b_n}{|^p}} } \right)^{\frac{1}{p}}}\]

Question: 試定義 半徑為1 且球心為 $\{0,0,0,...\}$ 的 open ball $\mathcal{B} \in l^p$:
ANS:\[
\mathcal{B}: = \left\{ {{{\left\{ {{a_n}} \right\}}_{n \in \mathbb{N}}}:\sum\limits_{n = 0}^\infty  {{{\left| {{a_n}} \right|}^p} < 1} } \right\}
\]
現在定義 example element in $l^p$
\[\left\{ {{e_n}^{\left( k \right)}} \right\}: = \left\{ \begin{array}{l}
0,\begin{array}{*{20}{c}}
{}
\end{array}n \ne k\\
1,\begin{array}{*{20}{c}}
{}
\end{array}n = k
\end{array} \right.
\]舉例而言,若 $k=1$ 則 上述定義表示 $e_n^{(1)} = \{1, 0, 0, 0,...\}$ 若 $k=2$ 則上述定義表示 $e_n^{(2)} = \{0, 1, 0, 0,...\}$

注意到
1. $\{e_n^{(k)}\} \in  \mathcal{\bar{B}}$
2. 且 example element 的 距離 (metric, $d$) 為 \[d({e^{(k)}},{e^{(m)}}) = {\left( {\sum\limits_{n = 0}^\infty  {{{\left| {e_n^{(k)} - e_n^{\left( m \right)}} \right|}^p}} } \right)^{\frac{1}{p}}} = {2^{\frac{1}{p}}}\]

Question: 試問 $ \mathcal{\bar{B}}$ 是否為 totally bounded?
NO! 亦即 存在 $\varepsilon>0$,使得 沒有 有限的 collection of open balls covers $X$

取 $\varepsilon < 1/2^p$ 則可證明 沒有有限的 collection of open balls covers $X$。


以下我們看個 totally bounded 的結果

=============
FACT: 若 $X$ 為 totally bounded metric space,則 $X$ 具有 countable 且 dense 的子集合 (亦即 $X$ 中存在 separable 的子集合)。
=============
Proof:
此為存在性的定理,我們要找出 一個 $X$ 的子集合 滿足 countable 與 dense。

首先由於 $X$ 為 totally bounded metric space,由定義可知 對任意 $\varepsilon >0$, 存在有限個 由半徑為 $\varepsilon>0$ 的 open ball $\mathcal{B}$ 所組成 的  cover of $X$。故對任意 $n \in \mathbb{N}$ 我們選 $\varepsilon_n:=1/n$,並且令有限個點 $x_1,...x_n \in X$,則由 toally boundedness of $X$ 我們可建構集合
\[
A_n := \{x_1, x_2,...,x_n\}
\] 使得 $X \subset \cup_i^n \mathcal{B}(x_i) $。那麼若我們現在令
\[
A:= \cup_n A_n
\] 則此集合 $A \subset X$ 且為 countable。

接著我們證集合 $A$ 為 dense。亦即要證明 :
對任意 $z \in X$,存在一組 sequence $\{z_n\} \in A$ 使得 $z_n \rightarrow z$。

現在給定任意 $z \in X$ ,則由 totally boundedness 我們可知必定存在 一個 點 $z_n \in A$ 使得 $d(z_n, z) < 1/n$ ,故對任意 $n \in \mathbb{N}$ 我們可建構一組 sequence $\{z_n\}$ 滿足
\[
\lim_{n \rightarrow \infty} d(z_n,z) =0
\]亦即 $z_n \rightarrow z$。

===================
Lemma 1: 任意 closed subset $F$ of compact metric space $X$ 必為 compact。
Proof: omitted.
===================

===================
Lemma 2: 任意 在 $X$ 中的無窮集合 必有 accumulation point 若且為若 $X$ 為 sequentially compact。
===================

Proof: $(\Rightarrow)$ 假設 在 $X$ 中的無窮集合 必有 accumulation point,我們要證明  $X$ 為 sequentially compact;亦即給定任意 sequence in $X$ ,要證明 存在 有收斂 subsequence 。

現在取 $\{p_n\}$ 為 $X$ 中任意 sequence。 將此 $\{p_n\} $ 中的元素形成集合 $A \subset X$ 且考慮以下兩種情況:
1.若 集合 $A$ 中元素為有限個,則 $\{p_n\}$ sequence 中 必定存在一點為重複出現無限次,則我們可取此點為形成 constant subsequence。
2. 若 集合 $A$ 中元素為無限個,亦即 $\{p_n\}$ 為無限個相異元素;由 假設可知
"任意 在 $X$ 中的無窮集合 必有 accumulation point "
$A$ 為 $X$ 中的無窮集合,必有  accumulation point ,此等價為 $\{p_n\}$ 具有收斂子數列。

$(\Leftarrow)$ 假設 $X$ 為 sequentially compact,要證明 任意 在 $X$ 中的無窮集合 必有 accumulation point。

令 $A \subset X$ 為無窮集合,我們要證 $A$ 必有 accumulation point。
我們取 $\{a_n\} \subset A$ 為 sequence,則由於  $X$ 為 sequentially compact,故可知給定任意sequence in $X$,必有收斂子數列。此等價為 $A$ 必有 accumulation point。

===================
Lemma 3: 若 $X$ 為 compact,則 $X$ 為 sequentially compact。
===================
Proof:
要證 $X$ 為 sequentially compact;可由 Lemma 2 我們證 任意 在 $X$ 中的無窮集合 必有 accumulation point 。

利用歸謬法(Proof by contradiction):假設 $X$ 為 compact,且存在一個 $X$ 中的無窮集合,但此集合並沒有 accumulation point 。我們要證矛盾。

故現在令 $Y \subset X$ 為此 無窮集合 (沒有 accumulation point)。則由於 $Y$ 並沒有 accumulation point ,我們可推知 對任意 $y \in Y$,存在適當的半徑 $r>0$ 使得開球 $B_r(y)$ 與 $Y$ 的交集
 \[B_r(y) \cap Y = \{y\}
\] 且由於  $Y$ 無 accumulation point,我們亦另外推知 $Y$ 為 closed。 ($Y$ is closed iff its contains all its accumulation point,但由於 $Y$ 並無 accumulation point,故 $Y$ 為 closed。)

由於 $X$ 為 compact,且 $Y \subset X$ 為 closed,由 Lemma 1 可知 $Y$ 亦為 compact。

對任意 $y$,我們確實可透過 $B_r(y)$ 來 cover $Y$ (透過 $ B_r(y) \cap Y = \{y\}$ ) 故由 compactness of $Y$ 可知必定存在有限個 subcover 來蓋住 $Y$。但此與 $Y$ 為無窮集合 矛盾。 $\square$

現在我們回憶 totally bounded
==========================
Definition: Totally Bounded
一個 metric space $(X,d)$ 稱為 totally bounded 若下列條件成立:
對任意 $\varepsilon>0$,存在有限個 以半徑為 $\varepsilon$ 的 open Ball $\mathcal{B}_\varepsilon$ 所組成的集合 並且 covers $X$。
==========================

Definition: 一個集合 $A$ 為 $\varepsilon$-net for space $X$ 若下列條件成立:
$A$ 為 finite set 且對 $x \in A$,開球 $B_\varepsilon(x)$ 建構一個 open cover of $X$。

現在我們給出等價定義: 我們說 $A$ is totally bounded 若 對任意 $\varepsilon>0$ 而言,我們有 $\varepsilon$-net。

Claim: 若 $X$ 為 sequentially compact,則 集合 $A \subset X$ 滿足 $p,q \in A, p \neq q$ 且 $d(p,q) \ge \varepsilon$ 為 有限集。
proof:


Lemma 4: 一個 sequentially compact 的 metric space $X$ 為 totally bounded + complete。

Proof:
先證 totally bounded。給定 $\varepsilon$,要建構 一個 $\varepsilon$-net。

現在令 $A \subset X$ 為一集合 滿足其中的元素之間互相之距離大於 $\varepsilon$,由 Claim 可知此集合 $A$ 為 有限集合,故對任意點 $p_i \in A$ 則我們可對每一個 $i$,建構一開球 $B_\varepsilon(p_i)$ 且此開球確實 蓋住 $X$。
亦即我們確實建構出 $\varepsilon$-net for $X$ 故  $X$ 為 totally bounded。$\square$

接著我們證  $X$ 為  complete:亦即給定任意 Cauchy sequence $\{x_n\} \subset X$ 要證明 此 $\{x_n\}$ 收斂在 $X$ 上。

由於 $X$ 為 sequentially compact ,故此 $\{x_n\}$ 具有收斂子數列 $\{x_{n_k}\}$在 $X$ 上。稱其極限為 $l$ 現在觀察 對足夠大的 $N$ 使得當 $n,n_k \ge N$ 我們有
\[\begin{array}{l}
\left| {{x_n} - l} \right| = \left| {{x_n} - {x_{{n_k}}} + {x_{{n_k}}} - l} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} \le \left| {{x_n} - {x_{{n_k}}}} \right| + \left| {{x_{{n_k}}} - l} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} < \varepsilon /2 + \varepsilon /2 < \varepsilon
\end{array}\]故$X$ 為  complete。 $\square$

10/01/2014

[數學分析] Weierstrass Theorem (1) - 先備概念

回憶在數學分析的內容中,我們試圖利用 $\mathbb{Q}$ 在 $\mathbb{R}$ 中 dense的想法,指出 任意在 $\mathbb{R}$ 上的實數 $r$,皆可透過 一組 sequence $\{q_n\} \in \mathbb{Q}$ 逼近 。也就是說 $q_n \rightarrow r$ 當 $n \rightarrow \infty$。那麼我們想問在函數上是否也有類似的概念? Weierstrass Approximation Theorem 便是試圖回答這個問題。

Weierstrass  Approximation Theorem 主要想法: 利用多項式 均勻收斂 連續函數!!

不過在介紹之前,我們需要一些先備知識。
首先看個 算子 (operator) 的概念:
定義 $A: \text{one function} \rightarrow \text{different function}$ 為一個算子(operator)

我們看個例子:

------------
Example
Fourier transform of 函數 $f$ 為一個算子 (將函數 $f$ 映射到另一個函數 $F$)
\[F(j\omega ) = \int_{ - \infty }^\infty  f (t){e^{ - j\omega }}dt
\]-----------

那麼算子何其多? 哪一種算子適合我們?? 以下我們介紹一個即為有用的特殊算子:摺積(Convolution)

===================
Definition: Convolution (Integral)
給定兩可積函數 $f,g$ on $\mathbb{R}$,則其折積(convolution) 定義為
\[(f*g)\left( x \right): = \int f (x - y)g(y)dy = \int g (x - y)f(y)dy
\]===================

Example
$f,g$ 為在 $[-1,1]$ 上的週期函數,且 $|\delta| <1$ \[f\left( x \right): = \left\{ \begin{array}{l} 1/2\delta ,\begin{array}{*{20}{c}} {}&{} \end{array}x \in \left[ { - \delta ,\delta } \right]\\ 0,\begin{array}{*{20}{c}} {}&{}&{} \end{array}o.w \end{array} \right.
\]試求其 convolution $(f * g)(x)=?$
Proof:
\[\begin{array}{l}
f*g: = \int_{ - 1}^1 {f\left( y \right)g\left( {x - y} \right)dy}  = \int_{ - \delta }^\delta  {\frac{\delta }{2}g\left( {x - y} \right)dy} \\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \frac{\delta }{2}\int_{ - \delta }^\delta  {g\left( {x - y} \right)dy}. \ \ \ \ \square
\end{array}
\]

Convolution 的好處:可以保留原函數的本身的優點!!

===================
FACT: 令 $K$ 為 compact interval,若 $f \in \mathcal{C}^{\infty}(\mathbb{R})$ (smooth function) 且 $g$ 為 可積函數,則
\[
(f * g)(x) = \int_K f(y)g(x-y)dy
\]亦為在 $K$ 上 smooth function
==================
Proof: omitted.

現在我們看個函數
===================
Definition: A Specific Smooth Function
令 $\phi(x)$ 為 $\mathbb{R}$ 上的 smooth function 且滿足下列條件
在 $(-1,1)$, $\phi>0$ ;且在 $(-1,1)^c$, $\phi=0$ ;另外我們限定此函數  $\phi$ 必須滿足下列積分
\[
\int_{-1}^{1} \phi(t) dt =1
\]===================

有了上述函數,我們可以定義算子 Operator $A$ 如下:
對 $s>0$,定義 $\phi_s$ 為\[{\phi _s}(t): = \frac{1}{s}\phi (\frac{t}{s});\;\;\;\int_{-1}^1 \phi  dt = 1\]且
\[
A_s f(t) :=( \phi_s * f)(t) = \int \phi_s(t) f(x-t) dt
\]其中 $\phi \ge 0$ on $[-1,1]$ 且 $\phi =0$ on $[-1,1]^c$ 。
============
Theorem: Preliminary Lemma for Weierstrass Approximation Theorem
令 $f$ 為 有界 連續 函數 on $\mathbb{R}$ ($f \in \mathcal{C}(\mathbb{R})$) 且 令 $J$ 為任意 compact interval in $\mathbb{R}$。則 當 $s \rightarrow 0$,我們有 $A_s f \rightarrow f$ 均勻收斂 on $J$。
============

Proof:
令 $\varepsilon>0$ ,我們要證明 $A_s f \rightarrow f$ 均勻收斂;(注意到上述定理陳述是當 $s \rightarrow 0$,故令 $n := 1/s$) 故要證 存在 $N>0$ 使得 $n > N$ 我們有
\[
|A_sf(x) - f(x) | < \varepsilon
\]對任意 $x \in J$ 。

觀察
\[\small
\begin{array}{l}
|{A_s}f(x) - f(x)| = \left| {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)f\left( {x - t} \right)dt}  - f\left( x \right)} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \left| {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)f\left( {x - t} \right)dt}  - f\left( x \right)\underbrace {\int_{ - \infty }^\infty  {{\phi _s}\left( t \right)dt} }_{ = 1}} \right|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \left| {\int_{ - \infty }^\infty  {\left[ {f\left( {x - t} \right) - f\left( x \right)} \right]{\phi _s}\left( t \right)dt} } \right| \le \int_{ - \infty }^\infty  {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon
\end{array}\]注意到上式中當 $|t| >s$時, $\phi_s =0$故上式積分範圍為
\[|{A_s}f(x) - f(x)| \le \int_{ - s}^s {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon \]
故如果可以讓上式 $|f(x-t) - f(x)|$ 對任意 $x \in J$ 都可使其任意小便完成證明。故現在透過 $J$ 為任意 compact interval on $\mathbb{R}$,我們可推知 $f$ 在 $J$ 上為 uniform continuous。亦即我們可選 $\delta >0$ 使得對任意 $u,v \in J$,
\[
|u-v| < \delta \Rightarrow |f(u) - f(v)| < \varepsilon
\]取 $u :=x, v := x+t \in J$ 則我們可知
\[
|u-v| = |x - (x+t)| < \delta \Rightarrow  |f(x) - f(x-t)| < \varepsilon
\]也就是說只要能找到 $N$ 使得 $n >N$ 且滿足 $|t| < \delta$ 則 我們便會有
\[|{A_s}f(x) - f(x)| \le \int_{ - s}^s {\left| {f\left( {x - t} \right) - f\left( x \right)} \right|{\phi _s}\left( t \right)dt}  < \varepsilon \]由於 $n =1/s; \; n >N \Rightarrow s < 1/N$ 且又由 $\phi_s(t)$ 定義可知 $t \in [-s,s]$故取 $N = 1/\delta$ 則上述自動滿足。$\square$

9/20/2013

[集合論] 基礎集合論的數學語言 (3)- Monotone Sequence of Sets

延續前篇  [集合論] 基礎集合論的數學語言 (2)- Limits of Sets

Definition: 單調集合的數列 (Monotone Sequence of Sets)
令 $\{A_n \}$ 為 一組 sequence of sets,我們說 $\{A_n \}$ 為 montone non-decreasing 若 $A_1 \subset A_2 \subset ... $,我們用 $A_n \uparrow$ 表示  $\{A_n \}$ 為 monotone non-decreasing sets。

另一方面,我們說 $\{A_n \}$ 為 montone non-increasing 若 $A_1 \supset A_2 \supset ... $。我們用 $A_n \downarrow$ 表示  $\{A_n \}$ 為 monotone non-increasing sets。

FACT: 對 Monotone Sequence of Sets 其極限存在。


現在我們看個結果

Theorem:
令 $\{A_n \}$ 為 monotone sequence of sets,我們有
  1. 若 $A_n  \uparrow $ ( 亦即 $\{A_n\} $ 為 monotone non-decreasing) 則 \[\lim_{n \rightarrow \infty}A_n = \bigcup_{n=1}^\infty A_n\]
  2. 若 $A_n  \downarrow $ (亦即 $\{A_n\} $ 為 monotone non-increasing) 則 \[\lim_{n \rightarrow \infty}A_n = \bigcap_{n=1}^\infty A_n\]
Proof
先證 (1):令 $\{A_n \}$ 為 monotone sequence of sets  且  $A_n \uparrow $ ,我們要證\[\mathop {\lim }\limits_{n \to \infty } {A_n} = \bigcup\limits_{n = 1}^\infty  {{A_n}} \]注意到若 集合數列的極限存在等價為
\[\mathop {\lim \sup }\limits_{n \to \infty } {A_n} = \mathop {\lim \inf }\limits_{n \to \infty } {A_n} = \mathop {\lim }\limits_{n \to \infty } {A_n}
\]現在由  $A_n  \uparrow $ 我們知道 $A_j \subset A_{j+1}$ 故
\[\bigcap\limits_{k \ge n}^{} {{A_k}}  = {A_n}
\]現在觀察 $\lim \inf$
\[\mathop {\lim \inf }\limits_{n \to \infty } {A_n}: = \bigcup\limits_{n = 1}^\infty  {\left( {\bigcap\limits_{k \ge n}^{} {{A_k}} } \right)}  = \bigcup\limits_{n = 1}^\infty  {{A_n}}
\]接著我們在觀察 $\lim \sup$  可得
\[\mathop {\lim \sup }\limits_{n \to \infty } {A_n}: = \bigcap\limits_{n = 1}^\infty  {\left( {\bigcup\limits_{k \ge n}^{} {{A_k}} } \right)}  \subset \bigcup\limits_{k \ge 1}^{} {{A_k}}  = \mathop {\lim \inf }\limits_{n \to \infty } {A_n}\]又我們知道
\[\mathop {\lim \inf }\limits_{n \to \infty } {A_n} \subset \mathop {\lim \sup }\limits_{n \to \infty } {A_n}
\]故總合以上可推知
\[\left\{ \begin{array}{l}
\mathop {\lim \sup }\limits_{n \to \infty } {A_n} \subset \mathop {\lim \inf }\limits_{n \to \infty } {A_n}\\
\mathop {\lim \inf }\limits_{n \to \infty } {A_n} \subset \mathop {\lim \sup }\limits_{n \to \infty } {A_n}
\end{array} \right. \Rightarrow \mathop {\lim \sup }\limits_{n \to \infty } {A_n} = \mathop {\lim \inf }\limits_{n \to \infty } {A_n}\]且
\[\mathop {\lim \sup }\limits_{n \to \infty } {A_n} \subset \bigcup\limits_{n = 1}^\infty  {{A_n}}  \subset \mathop {\lim \sup }\limits_{n \to \infty } {A_n} \Rightarrow \bigcup\limits_{n = 1}^\infty  {{A_n}}  = \mathop {\lim \sup }\limits_{n \to \infty } {A_n}\]

接著我們證 (2):令 $\{A_n \}$ 為 monotone sequence of sets  且  $A_n \downarrow $ ,我們要證\[\mathop {\lim }\limits_{n \to \infty } {A_n} = \bigcap\limits_{n = 1}^\infty  {{A_n}} \]

同之前證明(1)的手法,若 集合數列的極限存在等價為
\[\mathop {\lim \sup }\limits_{n \to \infty } {A_n} = \mathop {\lim \inf }\limits_{n \to \infty } {A_n} = \mathop {\lim }\limits_{n \to \infty } {A_n}
\] 故現在由定義 $\lim \sup$ 與 $\lim \inf$可知
\[\left\{ \begin{array}{l}
\mathop {\lim \inf }\limits_{n \to \infty } {A_n}: = \bigcup\limits_{n = 1}^\infty  {\left( {\bigcap\limits_{k \ge n}^{} {{A_k}} } \right)} \\
\mathop {\lim \sup }\limits_{n \to \infty } {A_n}: = \bigcap\limits_{n = 1}^\infty  {\left( {\bigcup\limits_{k \ge n}^{} {{A_k}} } \right)}
\end{array} \right.\]由於 $\{A_n \} \downarrow$,亦即 $A_{n+1} \subset A_n$ 故上述  $\lim \sup$ 與 $\lim \inf$ 有如下關係
\[\begin{array}{l}
\left\{ \begin{array}{l}
\mathop {\lim \inf }\limits_{n \to \infty } {A_n}: = \bigcup\limits_{n = 1}^\infty  {\left( {\bigcap\limits_{k \ge n}^{} {{A_k}} } \right)} \\
\mathop {\lim \sup }\limits_{n \to \infty } {A_n}: = \bigcap\limits_{n = 1}^\infty  {\left( {\bigcup\limits_{k \ge n}^{} {{A_k}} } \right) = \bigcap\limits_{n = 1}^\infty  {{A_n}} }
\end{array} \right.\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} \Rightarrow \left\{ \begin{array}{l}
\mathop {\lim \inf }\limits_{n \to \infty } {A_n} \subset \mathop {\lim \sup }\limits_{n \to \infty } {A_n}\\
\mathop {\lim \sup }\limits_{n \to \infty } {A_n} = \bigcap\limits_{n = 1}^\infty  {{A_n}}  \subset \bigcup\limits_{n = 1}^\infty  {\left( {\bigcap\limits_{k \ge n}^{} {{A_k}} } \right) = \mathop {\lim \inf }\limits_{n \to \infty } {A_n}}
\end{array} \right.\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} \Rightarrow \mathop {\lim }\limits_{n \to \infty } {A_n} = \mathop {\lim \inf }\limits_{n \to \infty } {A_n} = \mathop {\lim \sup }\limits_{n \to \infty } {A_n} = \bigcap\limits_{n = 1}^\infty  {{A_n}} \ \ \ \ \ \square
\end{array}\]


上述定理有個重要的結果值得紀錄。
若現在我們取 $B_n$ 為任意 sequence of sets,則
\[\left\{ \begin{array}{l}
\mathop {\inf }\limits_{k \ge n} {B_n}: = \bigcap\limits_{k \ge n}^{} {{B_k}}  \uparrow \\
\mathop {\sup }\limits_{k \ge n} {B_n}: = \bigcup\limits_{k \ge n}^{} {{B_k}}  \downarrow
\end{array} \right.\]利用上述定理可得
\[\left\{ \begin{array}{l}
\mathop {\inf }\limits_{k \ge n} {B_n}: = \bigcap\limits_{k \ge n}^{} {{B_k}}  \uparrow \begin{array}{*{20}{c}}
{}
\end{array} \Rightarrow \begin{array}{*{20}{c}}
{}
\end{array}\mathop {\lim }\limits_{n \to \infty } \left( {\bigcap\limits_{k \ge n}^{} {{B_k}} } \right) = \bigcup\limits_{n = 1}^\infty  {\left( {\bigcap\limits_{k \ge n}^{} {{B_k}} } \right) = \mathop {\lim \inf }\limits_{n \to \infty } {B_n}} \\
\mathop {\sup }\limits_{k \ge n} {B_n}: = \bigcup\limits_{k \ge n}^{} {{B_k}}  \downarrow \begin{array}{*{20}{c}}
{}
\end{array} \Rightarrow \begin{array}{*{20}{c}}
{}
\end{array}\mathop {\lim }\limits_{n \to \infty } \left( {\bigcup\limits_{k \ge n}^{} {{B_k}} } \right) = \bigcap\limits_{n = 1}^\infty  {\left( {\bigcup\limits_{k \ge n}^{} {{B_k}} } \right) = \mathop {\lim \sup }\limits_{n \to \infty } {B_n}}
\end{array} \right.\]

讀者可嘗試以下幾個例子看看是否能正確使用上述定理

Exercise:
\[\begin{array}{l}
\mathop {\lim }\limits_{n \to \infty } \left[ {0,1 - \frac{1}{n}} \right] = [0,1)\\
\mathop {\lim }\limits_{n \to \infty } \left[ {0,1 - \frac{1}{n}} \right) = [0,1)\\
\mathop {\lim }\limits_{n \to \infty } \left[ {0,1 + \frac{1}{n}} \right] = [0,1]\\
\mathop {\lim }\limits_{n \to \infty } \left[ {0,1 + \frac{1}{n}} \right) = [0,1]
\end{array}\]

8/12/2013

[數學分析] 函數的極限

這次要介紹函數極限( Limit of Function)。我們首先給出定義如下

===========================
Definition: Limit of Function
令 $X$ 與 $Y$ 為 metric spaces,設 $E \subset X$ 且 考慮函數 $f : E \rightarrow Y$ 與點 $p$ 為 limit point of $E$,則我們將函數的極限 記作 $f(x) \rightarrow p$ 當 $x \rightarrow p$ 或者
\[
\lim_{x \rightarrow p} f(x) =q
\]若 存在一點 $q \in Y$ 滿足下列條件:
對任意 $\varepsilon >0$ 存在 $\delta >0$ 使得 對所有的 $x \in E$,若 $ 0 < d_X(x,p) < \delta$,則
\[
d_Y(f(x),q) < \varepsilon
\]===========================

上述 $d_X$ 與 $d_Y$ 表示 metric in $X$ 與 metric in $Y$

Comment:
1. 上述定義從直覺上可以看出想表達我們可以透過讓 $x$ 足夠的接近 $p$ 來使得 $f(x)$ 可以被任意接近 $q$。
2. 關於上述定義提及的 Metric Space 可直接簡單視為 $\mathbb{R}^n$ Euclidean 空間,若對 Metric Space 定義有興趣讀者請參考
[數學分析] 淺談 Metric Space and Topology
3. 上述定義可等價用 limits of sequences 表示,我們將其記做下面重要的定理

===========================
Theorem:  Equivalence of Limit of Functions and Limit of Sequences 
令 $X,Y,E,f,p$ 同上述定義,則
\[
\lim_{x \rightarrow p} f(x) =q
\]若且唯若 對任意 sequence $\{p_n \}$ in $E$ 滿足 $p_n \neq q$ 且使得
\[
\lim_{n \rightarrow \infty} p_n =p
\Rightarrow \lim_{n \rightarrow \infty} f(p_n) =q
\]===========================
Proof
先證 $(\Rightarrow)$
已知 $\lim_{x \rightarrow p} f(x) =q$,我們有:對任意 $\varepsilon >0$ 存在 $\delta >0$ 使得對所有的 $x \in E$ ,若 $ 0 < d_X(x,p) < \delta$ 則
\[
d_Y(f(x),q) < \varepsilon \ \ \  \ (*)
\]
我們要證明
對任意 sequence $\{p_n \}$ in $E$ 滿足 $p_n \neq q$ 且
\[
\lim_{n \rightarrow \infty} p_n =p \Rightarrow
\lim_{n \rightarrow \infty} f(p_n) =q
\] 故首先令 sequence $\{p_n \}$ in $E$ 滿足 $p_n \neq q$ 且 $\lim_{n \rightarrow \infty} p_n =p$.   $(**)$
則我們僅需證明下式成立即可
\[
\lim_{n \rightarrow \infty} f(p_n) =q
\] 由定義拆解上式,亦即我們需要證 對任意 $\varepsilon >0$ 存在 $N >0$ 使得 $n \ge N$ 讓 $d_Y(f(p_n),q) < \varepsilon $

故取 $\delta$ 如前所定,則由 sequence $\{p_n\}$ 的假設 $(**)$ 我們可知存在 $N$ 使得 $n \ge N$ 讓
\[
0 < d(p_n,p) < \delta
\]由 $(*)$ 我們可得 對 $n \ge N$,
\[
d(f(p_n),q) < \varepsilon
\]亦即
\[
\lim_{n \rightarrow \infty} f(p_n) =q
\]

接著我們證明 $(\Leftarrow)$
利用歸謬法 (Suppose toward to Contradiction),也就是說我們 假設
(1) 對任意 sequence $\{p_n \}$ in $E$ 滿足 $p_n \neq q$ 且使得
\[
\lim_{n \rightarrow \infty} p_n =p
\Rightarrow \lim_{n \rightarrow \infty} f(p_n) =q
\] 另外 假設 (2) $\lim_{x \rightarrow p} f(x) =q$ 不成立,亦即對原本陳述取非
存在一 $\varepsilon >0$ 使得 對任意 $\delta >0$,存在 $x \in E$,使得 $ 0 < d_X(x,p) < \delta$,但是
\[
d_Y(f(x),q) \ge \varepsilon
\] 現在我們的目標是結合假設 (1) 與 (2) 試圖尋找矛盾點。

現在觀察 (2),給定 $\varepsilon_n >0$, 且定義 $\delta :=1/n >0 \; \text{for}\; n \in \mathbb{N}$ 則存在一組 sequence $\{ x_n\} \in E$ 使得  $ 0 < d_X(x_n,p) < \delta$,但是
\[
d_Y(f(x_n),q) \ge \varepsilon
\] 上述結果與假設 (1) 矛盾。故得證。 $\square$

Reference:
[1] W. Rudin, Principles of Mathematical Analysis
[2] T. M. Apostol, Mathematical Analysis

7/19/2013

[基礎數學] 函數的像 與 像原 (Image and Preimage)

這是要介紹的概念是關於函數的 image 與 preimage (又稱 inverse image)

現在給定一個函數 $f: X \rightarrow Y$,則我們說 $f(x)$ 為 $f$ 的值。$X$ 為 domain (有時候我們稱 $f$ 定義在 $X$ 上),$Y$ 為 co-domain。下圖可以很清楚的說明這個概念


ref: http://en.wikipedia.org/wiki/Image_(mathematics)

在介紹 preimage之前,我們先說說什麼是 image (像)
讓 $E \subset X$,則我們稱 image of $E$ under $f$ 為 $f(E)$ 定義如下
\[f(E): = \{ f(x):x \in E\}
\]現在我們看幾個 image 的例子

Example 1
令 $f:\{1,2,3\} \rightarrow \{a,b,c,d \}$ 且定義
\[f\left( x \right): = \left\{ \begin{array}{l}
a,\begin{array}{*{20}{c}}
{}
\end{array}x = 1\\
a,\begin{array}{*{20}{c}}
{}
\end{array}x = 2\\
c,\begin{array}{*{20}{c}}
{}
\end{array}x = 3
\end{array} \right.\]試求 image $f(\{2,3 \})=?$
Solution
由定義 
\[\begin{array}{l}
f(E): = \{ f(x):x \in E\} \\
 \Rightarrow f(\left\{ {2,3} \right\}) = \{ f(x):x \in \left\{ {2,3} \right\}\}  = \left\{ {a,c} \right\} \ \ \ \ \square
\end{array}
\]

Example 2
令 $f: \mathbb{R} \rightarrow \mathbb{R}$ 且定義 $f\left( x \right): =x ^2 $ 試求 image $f(\{-2,3 \})=?$
Solution
由定義 
\[\begin{array}{l}
f(E): = \{ f(x):x \in E\} \\
 \Rightarrow f(\left\{ { - 2,3} \right\}) = \{ f(x):x \in \left\{ { - 2,3} \right\}\}  = \left\{ {4,9} \right\}
\end{array}\]


有了 image之後我們便可以來定義甚麼是 preimage,定義如下:

===========================
Definition: (Preimage or Inverse Image)
考慮函數 $f: X \rightarrow Y$,且令集合 $B \subset Y$,則我們定義  preimage of B under $f$ 為 $f^{-1} (B)$ 滿足
\[
f^{-1}(B) := \{ x \in X : f(x) \in B \}
\]===========================

這定義有甚麼用呢? 我們用幾個例子來說明:

Example 1:
令 $f: X \to Y$,若取集合 $B = Y$ 則由定義可知
\[
f^{-1}(B) = f^{-1}(Y) = \{x \in X: f(x) \in T \} = X
\]

Example 2 :
現給定 $f: (-\infty, \infty) \rightarrow (-\infty, \infty) $ 且 $f(x) = x^2$,試找出 $f^{-1}([4,9])=?$

Sol:
首先我們可以比對 此例 與 定義,便可發現

$ f^{-1}([4,9]) = \{x \in (-\infty, \infty) : f(x) \in [4,9]\}$

$ = \{x \in (-\infty, \infty) :4 \leq  f(x) \leq 9 \}$

$ = \{x \in (-\infty, \infty) : 4 \leq  x^2 \leq 9 \}$

$ = \{x \in (-\infty, \infty) : 2 \leq  x \leq 3 \ or  -3 \leq  x \leq -2 \}$

$ = [-3,-2] \bigcup [2,3]$ $\square$

由上例可以看出, $f^{-1}([4,9]) = [-3,-2] \bigcup[2,3]$ ;這表示了 所謂的 preimage 是原本定義域(domain) 的子集合。也就是在問說 在  $x \in (-\infty, \infty)$ 之下, 甚麼樣的 $x$ 可以使 $f(x)$ 的值域落在 $[4,9]$之中。

好,那麼如果現在我們把前例中的 函數的定義域 domain 改成如下:

$f : [0, \infty) \rightarrow (-\infty, \infty)$ 則 此時 preimage變成

$f^{-1}([4,9]) = [2,3]$

,因為此函數的定義域已經被更改成 $[0, \infty)$ (也就是說 $x$ 已經被限制不能為負值) 所以 由preimage定義可知

$f^{-1}([4,9]) =  \{x \in [0, \infty) : f(x) \in [4,9]\}$ 也就是再問說 在  $x \in [0, \infty)$ 之下, 甚麼樣的 $x$ 可以使 $f(x)$ 的值域落在 $[4,9]$之中。

這便是preimage。


以下我們介紹幾個 Preimage 的性質:
令 $\Omega, \Omega'$為任意集合,現考慮函數 $f: \Omega \rightarrow \Omega'$ 則我們有以下 preimage 性質

(1) $f^{-1}(\emptyset) = \emptyset$
(2) $f^{-1}(\Omega') = \Omega$
(3) 對 $A' \subset \Omega'$,$f^{-1}(A'^C) = (f^{-1}(A'))^C$
(4) Preimage 對 set operation 成立
\[\begin{array}{l}
{f^{ - 1}}\left( {\bigcup\limits_i^{} {{A_i}'} } \right) = \bigcup\limits_i^{} {{f^{ - 1}}\left( {{A_i}'} \right)} \\
{f^{ - 1}}\left( {\bigcap\limits_i^{} {{A_i}'} } \right) = \bigcap\limits_i^{} {{f^{ - 1}}\left( {{A_i}'} \right)}
\end{array}\]

7/10/2013

[分享] 關於數學證明的一點點思路 (III)

關於數學證明的一點點思路(III)-Forward-backward method。

這次想跟大家分享一個一般數學證明常用的方法,稱作Forward-backward method。
此法本質上就是 [分享] 關於數學證明的一點點思路 (I)-基本思路 的詳細說明版本。

現在讓我們考慮一個標準命題:
If A then B

如之前我們討論過的, 陳述 A 稱為 假設(hypothesis), 陳述 B 稱為 結論(conclusion)或稱待證目標,

如果我們想要證明 if A then B,則我們可以假設A為真,然後需要證明B為真。
這時有兩種途徑可以著手進行,

首先是先觀察 待證目標B,看看是否有方法可以得到 結論B 或者 得到接近B的陳述,或者有與待證目標B相關的已知結果(如定理、引理)可以使用,這種方法稱為 Backward process (從觀察結論下手)

再者,回頭觀察 已知假設A,看看是否可以透過藏在A中的蛛絲馬跡讓我們來一步一步逼近結論B,這種方法稱為Foward process (從假設出發)

最後是試圖把上述兩者連結起來,就構成整個Forward-Backward process,這很像是在走迷宮
Professor Daniel Solow給了一張非常生動的圖闡述這個想法



看是要從迷宮的中心往外走還是要從迷宮的入口往內走,只要能把整個路徑連起來,證明就完成了。以下是一個非常簡單的例子,來說明如何使用Forward-Backward process


==========================================
EXAMPLE
If the right triangle $XYZ$ with sides of lengths $x$ and $y$, and hypotenuse of length $z$, has an area of $z^2/4$, then the triangle $XYZ$ is isosceles.
------------------------------------------
(譯:若直角三角形 $XYZ$ 兩股長為 $x$ 與 $y$,且斜邊長為 $z$,其面積為 $z^2/4$,則 三角形 $XYZ$ 為等腰三角形)

==========================================

觀察上述陳述,我們可以馬上判斷
已知假設 "A" 為:
 the right triangle $XYZ$ with sides of lengths $x$ and $y$, and hypotenuse of length $z$, has an area of $z^2/4$,

待證目標 "B" 為:
the triangle $XYZ$ is isosceles.
-------------------------------------------

BACKWARD PROCESS
現在讓我們首先觀察結論B,看看是否有方法可以得到結論B或者得到接近B的陳述,比如上例而言,我們應先觀察 "the triangle $XYZ$ is isosceles",

接著我們可能會問自己該如何才能證明一個三角形是等腰呢? 這時很明顯的我們要先知道"什麼是等腰三角形(isosceles)",如果你不清楚定義,那麼到這邊遊戲就結束,因為我們很難再不清楚定義的情況試圖證明某個命題的真假。所以現在需要用上 等腰三角形 的定義!

Def: 一個三角形,若具備 (至少)任兩邊等長 之性質,則此三角形稱為等腰三角形

由上述定義的提示,我們很清楚地發現只要能夠找到兩邊等長就可以證明$XYZ$是等腰三角形了!!,故馬上轉變目標變成證明 $x=y$,
因為如果能夠證明 $x=y$,則由定義可知, $XYZ$ 即為等腰三角形。(Note: 不是證明 $x=z \quad or \quad y=z$,因為此題已經給出$XYZ$為直角三角形,且斜邊為$z$)

故我們說透過Backward process,得到新的待證目標B1: (亦即若B1為真 => B為真)

B1: $x=y$

所以現在問題變成,如何證明$x=y?$,注意到此時我們若想再進一步用 $x=y$ 作進一步推論,便會發覺似乎不太容易

註:
  • 也許你可能回憶起 等腰三角形 還具備一個性質:兩股對應的角度相等,故你可能會試圖將待證目標 B1 改寫成 待證目標B2: 證明x與y對應的角度相等,但一般而言,我們不太容易思考到這個步驟,且注意到 已知假設A 中只有提及 邊長 與 面積 的訊息,故若採用角度作推論,很容易陷入困難之中。
  • 也許你可能會想到 $x=y \implies x\leq{y} \quad \& \quad x\geq{y}$,但是這依然難以繼續。

很明顯的,現在我們對於backward-process似乎已經束手無策,故我們便可暫時停止Backward-process,然後回頭開始採用 已知假設A 所提供的資訊 來幫助我們,亦即開始採用Foward-process進攻目標

B1: $x=y$
------------------------------------------
FORWARD PROCESS
回顧我們的 已知假設A: "the right triangle $XYZ$ with sides of lengths $x$ and $y$, and hypotenuse of length $z$, has an area of $z^2/4$ "

現在仔細看看上A提供的線索,我們可以發現 $XYZ$ 的面積給定為 $z^2/4$,且又給出兩股 $x$ and $y$ 與斜邊 $z$,從這裡我們可以推論

A1: $z^2/4=xy/2$

另外由已知假設可知 $XYZ$ 為直角三角形,故我們可馬上由畢氏定理得到另外一個線索

A2: $(x^2+y^2)=z^2$

故我們可以把A1與A2合併
(用$(x^2+y^2)$換掉A1中的$z^2$),得到

 A3: $(x^2+y^2)/4=xy/2$

注意到我們的目標是要把已知假設A與剛剛用Backward process找出的新待證目標B1作連結。
只要連結起來證明便完畢

故現在對A3同乘 $4$,可得

A4: $(x^2+y^2)=2xy \implies (x^2-2xy+y^2)=0$

進一步再整理一下A4
A5: $(x-y)^2=0$

仔細再看一下剛剛得到的A,這時候我們發現

$(x-y)^2=0 \implies (x-y)=0 \implies x=y$

此時A5結結實實的連上了待證目標B1: $x=y$,故我們的證明至此完畢。
=============================================

文章至此可能會發現這個簡單的例子怎麼需要搞這麼複雜,其實上面的討論是單純的證明思路,但真正把證明寫下來的時候,是不需要這樣的,以下是一個寫下來的證明

Proof:
由題目(EXAMPLE)可知,我們需要證明三角形 ${\color{red}XYZ}$ is isosceles,亦即須證明其兩股相等,
i.e.,${\color{red} x=y}$
由假設可知三角形 ${\color{red}XYZ}$ 面積為 ${\color{red}z^2/4}$ 故可推知 ${\color{red}z^2/4=xy/2}$ (因為三角形面積:1/2*底*高=1/2*x*y)
另外由已知假設又可知 ${\color{red}XYZ}$ 為直角三角形,故由畢氏定理可知
${\color{red} {(x^2+y^2)=z^2}}$
整理上式可得
${\color{red} {(x^2+y^2)/4=xy/2 \implies(x^2-2xy+y^2)=0}}$

$ {\color{red} {(x-y)^2=0 \implies(x-y)=0 \implies x=y}}$
Q.E.D
------------------------------------------------------------------------
Ref: Daniel Solow, How to Read and Do Proofs: An Introduction to Mathematical Thought Processes 2e, 2001

相關閱讀

7/03/2013

[數學分析] 什麼是若且唯若 "if and only if"

數學上的 if and only if
 (此文不討論邏輯學中的 if and only if,只討論數學上的 if and only if。)

中文翻譯叫做 若且唯若 (or 當且僅當)記得當初剛接觸這個詞彙的時候,我是完全不明白到底是甚麼意思,查了翻譯也是愛莫能助,畢竟有翻跟沒翻一樣,都是有看沒有懂。

在數學上如果看到 if and only if  這類的句子,其實是表示一種雙條件句,通常可以直接將其視為"定義(Definition)"待之,今天要分享的是這樣的一個句子如何用比較直觀的方法去看他

假設我們現在有 兩個邏輯陳述句 A 與  B.
注意到,在此我們不必考慮這兩個陳述句到底是什麼,想表達什麼,或者到底是否為真(true),這些都不重要。只要知道是兩個陳述即可。

現在,考慮新的陳述:  "A if and only if B"
好了,現在主角登場,我們可以怎麼看待這個句子呢?
事實上我們可以很直覺的把這句子拆成兩部分看待,也就是
"( A if B ) and ( A only if B )"

那麼先針對第一個部分 A if B 來看,
其實這句就是說 if B then A,
更直白一點就是 "if B is true, then A is also true". 
在數學上等價可以寫為 "B implies A"
或者更常用一個箭頭符號來表示 "B $\Rightarrow$  A" 

現在針對第二個部分 A only if B
此句意指 "If B is not true, then A is also not true".
所以如果已知 A is true, 那麼按照上句不難推得 B is also true
也就是說 A only if B 等價為 "If A is true then B is also true".
同樣,也可以寫作 "A implies B" 
或者用箭頭表示 "A  $\Rightarrow$   B".

所以現在總結如下,下列七個 if and only if 陳述完全等價:

  1. "A if and only if B" 
  2. "A iff B" 
  3. "A is equivalent to B" 
  4. "A is a necessary and sufficient condition for B" 
  5. "( A implies B ) and ( B implies A )" 
  6. "( A  $\Rightarrow$   B ) and ( B  $\Rightarrow$   A )" 
  7. "A $\Leftrightarrow$ B" 


Comments: 
(1) A iff B 當中的 iff 只是 if and only if 的英文縮寫。
(2) A is equivalent to B 表A與B等價,若有興趣深究什麼是數學上的等價關係,可以參閱 數學上的等價關係 一文
(3) A is a necessary and sufficient condition for B 提及 必要條件 (necessary condition) 與 充分條件 (sufficient condition),但為了不造成混淆,原則上以前述的說明為主。有興趣請再參考附註
.
附註
If A then B (我們稱B為A的 必要條件; A為B的充分條件)

用上述的說法,A if and only if B
即可說 A為B的充分且必要條件 而且  B也為A的充分且必要條件

你可能會發現這種充/要條件的說法很饒舌,個人其實沒有非常喜歡這種用法,最直白還是使用箭頭表述,會發現一切都變得簡單又清

6/22/2013

[集合論] 基礎集合論的數學語言 (2)- Limits of Sets

回憶在數學分析中我們定義了實數 sequence 的 limit 以及 函數 sequence 的 limt,那麼對於一組 集合 sequence 是否也能定義其極限?。 答案是肯定的。我們將仿照 實數 or 函數sequence 的 limit 來定義 集合 sequence 的極限 如下

令集合 $ A_n \subset \Omega$,我們定義
\[\mathop {\inf }\limits_{k \ge n} {A_k}: = \bigcap\limits_{k = n}^\infty  {{A_k}} ;\begin{array}{*{20}{c}}
{}&{}
\end{array}\mathop {\sup }\limits_{k \ge n} {A_k}: = \bigcup\limits_{k = n}^\infty  {{A_k}} ;
\] 有了上述定義後我們可以進一步定義 $\lim\inf$ 與 $\lim \sup$
\[\mathop {\lim \inf }\limits_{n \to \infty } {A_n} = \bigcup\limits_{n = 1}^\infty  {\bigcap\limits_{k = n}^\infty  {{A_k}} } ;\begin{array}{*{20}{c}}
{}&{}
\end{array}\mathop {\lim \sup }\limits_{n \to \infty } {A_n}: = \bigcap\limits_{n = 1}^\infty  {\bigcup\limits_{k = n}^\infty  {{A_k}} } ;
\] 有了$\lim\inf$ 與 $\lim \sup$,我們便可定義 集合 sequence 的 極限如下:

若存在一組集合 sequence $\{B_n\}$ 且 $B_n \subset \Omega, \; \forall n$ ,則我們說 $B_n$ 的極限存在若下列條件成立
\[\mathop {\lim \inf }\limits_{n \to \infty } {B_n} = \mathop {\lim \sup }\limits_{n \to \infty } {B_n} = B\]且 我們稱 $B$ 為 $B_n$ 的極限,並記做
\[
\lim_{n \rightarrow \infty} B_n = B\; \text{ or $B_n \rightarrow B$}
\]

以下我們看個例子確保我們確實了解上述定義

Example 
試證
\[\mathop {\lim \sup }\limits_{n \to \infty } \left[ {0,\frac{n}{{n + 1}}} \right) = \mathop {\lim \inf }\limits_{n \to \infty } \left[ {0,\frac{n}{{n + 1}}} \right) = \left[ {0,1} \right)\]
Proof
首先觀察
\[\mathop {\lim \inf }\limits_{n \to \infty } \left[ {0,\frac{n}{{n + 1}}} \right) = \bigcup\limits_{n = 1}^\infty  {\left( {\bigcap\limits_{k = n}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)} } \right)}
 \]注意到
\[\bigcap\limits_{k = n}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)}  = \left\{ \begin{array}{l}
k = 1:\bigcap\limits_{k = 1}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)}  = \left[ {0,\frac{1}{2}} \right)\\
k = 2:\bigcup\limits_{k = 2}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)}  = \left[ {0,\frac{2}{3}} \right)\\
...\\
k = n:\bigcup\limits_{k = n}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)}  = \left[ {0,\frac{n}{{n + 1}}} \right)
\end{array} \right.
\] 故
\[ \Rightarrow \bigcup\limits_{n = 1}^\infty  {\left( {\bigcap\limits_{k = n}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)} } \right) = \bigcup\limits_{n = 1}^\infty  {\left[ {0,\frac{n}{{n + 1}}} \right) = \left[ {0,1} \right)} } \]接著觀察
\[\mathop {\lim \sup }\limits_{n \to \infty } \left[ {0,\frac{n}{{n + 1}}} \right) = \bigcap\limits_{n = 1}^\infty  {\left( {\bigcup\limits_{k = n}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)} } \right)}
\]注意到
\[\bigcup\limits_{k = n}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)}  = \left\{ \begin{array}{l}
k = 1:\bigcup\limits_{k = 1}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)}  = \left[ {0,1} \right)\\
k = 2:\bigcup\limits_{k = 2}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)}  = \left[ {0,1} \right)\\
...\\
k = n:\bigcup\limits_{k = n}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)}  = \left[ {0,1} \right)
\end{array} \right.\]故可得
\[\bigcap\limits_{n = 1}^\infty  {\left( {\bigcup\limits_{k = n}^\infty  {\left[ {0,\frac{k}{{k + 1}}} \right)} } \right)}  = \bigcap\limits_{n = 1}^\infty  {\left[ {0,1} \right) = \left[ {0,1} \right)}
\]故兩者相等即為所求。$\square$

不過事實上我們可以將 集合的 sequence 的 $\lim \sup$ 與 Indicator function 連結起來。(關於 Indicator function 請參閱BLOG文章)

Lemma: The relationship between limsup and indicator function
令 $A_n \in \Omega$,我們讓 $\{ A_n \}$ 為 一組 集合 sequence。則
對於 $\lim \sup$ 我們有如下等價描述:
存在 subsequence $n_k$ 且 $n_k$ 與 $\omega$ 有關 使得
\[\begin{array}{l}
\mathop {\lim \sup }\limits_{n \to \infty } {A_n} = \left\{ {\omega  \in \Omega :\sum\limits_{n = 1}^\infty  {{1_{{A_n}}}\left( \omega  \right) = \infty } } \right\}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \left\{ {\omega  \in \Omega :\omega  \in {A_{{n_k}}},k = 1,2,3,...} \right\}
\end{array}
\]亦即我們可寫
\[\mathop {\lim \sup }\limits_{n \to \infty } {A_n} = \left\{ {{A_n}\begin{array}{*{20}{c}}
{}
\end{array}i.o.} \right\}\]其中 $i.o.$ 表 infinitely often.
Proof: omitted.


[Claude] 國小數學加減乘除法計算小遊戲:數學怪獸大亂鬥

心血來潮用 Anthropic Claude Opus 4.6 做的簡單國小數學乘除法計算小遊戲,感嘆AI工具之強大與便利。原本可能要耗時幾天的工作轉眼就完成,時代的巨輪確實在飛速轉動。  數學怪獸大亂鬥(Math Monster Brawl)對戰的國小數學 加減乘除 小遊戲連結...