2013年7月19日 星期五

[基礎數學] 函數的像 與 像原 (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}\]

2013年7月10日 星期三

[分享] 關於數學證明的一點點思路 (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

相關閱讀

2013年7月3日 星期三

[數學分析] 什麼是若且唯若 "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的充分且必要條件

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