How About One-To-Many Function

本文探討數學語言三大基礎概念之一 (邏輯，集合，函數) 的函數 !!
並推廣函數觀念至"一對多"，並定義共同集(common set) 等概念與例子 

[回顧函數定義]
函數是一種對應，給定兩個集合 $X$ , $Y$
$f : X \longrightarrow Y$ ，稱 $X$ 為定義域(domain)，$Y$ 為對應域(codomain)
英文定義 :
$(E1)$ For each $x \in X$  there exists "unique" $y \in Y$ such that  $y = f(x)$
符號寫法:
$\forall x \in X \exists ! y \in Y , \text{ s.t } y = f(x)$
資工術語:
key-value ，資料結構裡面的 map data structure

注意: 這邊的 $y$ 是隨著 $x$ 值不同而可能不同($y$ is depend on $x$)，必須要跟下面的意思做區分:
$(E2)$ For all $x \in X$ , there exists "unique common" $y \in Y$ such that  $y = f(x)$，這代表對應到的 "y" 都是一模一樣的。
$(E1)$ 是函數的意思，$(E2)$ 是常數(Constant)函數的意思。

函數也可以想成一條條 if - then 構成(邏輯式展開)
--------------------------------------------------------------------
[Example: 如果令 $X= \{1,2,3\} , Y= \{4,5,6\}$]
$f(1) = 4$    代表  if $X=1$ then $Y=4$
$f(2) = 5$    代表  if $X=2$ then $Y=5$
$f(3) = 5$    代表  if $X=3$ then $Y=5$

而(E2)大概是長這樣
$f(1) = 4$    代表  if $X=1$ then $Y=4$
$f(2) = 4$    代表  if $X=2$ then $Y=4$
$f(3) = 4$    代表  if $X=3$ then $Y=4$
--------------------------------------------------------------------

[可以說的事]
可以定義函數的值域 $Range(f) := \{y\in Y : \exists x \in X \text{ s.t } f(x) = y\}$或寫成 $f(X) \text{ or } Image(f)$ ，很明顯，$f(X)\subseteq Y$
可以定義反映射 Preimage , 給定 $y \in f(X) , f^{-1}(y) := \{x\in X : f(x) = y \}$

注意: 定義域裡面的每一個 $x$ 都要對應一個 $y$，不能一對無，可以多對一，即 $\forall y \in f(X) ,  |f^{-1}(y)| \geq 1$

注意: 函數$f$ 可以視為把定義域 $X$ 做切割成一塊塊互斥的集合(partitions) ，即 $$\bigcup^{\text{disjoint}}_{y\in f(X)} f^{-1}(y)  = X$$ ，這在機率論"隨機變數"上是重要的概念!!


如果 $\forall y \in f(X) ,  |f^{-1}(y)| = 1$ 則我們稱函數為 1-1 函數 !!

如果 $f(X) = Y$ 則我們稱函數為 onto 函數 !!

如果一個函數 1-1 又 onto 則我們可以定義反函數，$f^{-1} : Y \rightarrow X$ ，$f^{-1}(y) = x$ ，而且 $f^{-1}(f(x)) = x$

函數我們有時候會簡記成 $y = y(x)$ (在微分方程領域常用) ，$y$ 代表值 ，$y(\cdot)$代表函數，不過簡記容易會有意義上混淆。

如果 $X$ 是一個有限集，我們有時候會寫成下標 $f_x = y$
例如: 實數矩陣 $A = (A_{ij})$  可看成 $A : I \times J \rightarrow \mathbb{R}$
$I = \{1,2,3,....m\} , J = \{1,2,3,....n\}$

[簡單的假想實驗]
如果你有個黑板上可以畫 $xy$ 平面，畫一條條水平線(跟$x$軸平行)，垂直線(跟$y$軸平行)，隨便在畫一條曲線代表 $f$，如果每一條垂直線都跟曲線$f$ 恰有一交點則我們稱 $f$ 是一個 $x$ 的函數，而此時如果每一條水平線又跟曲線 $f$ 也是恰有一個交點，則我們稱此函數為 1-1 (one-one)

[推廣至一對多]
而在現實生活中，一對多的概念也是非常常見，所以筆者決定定義它
(p.s)在資工資料結構類似 Linked List 的概念或是 C++ 實作的結構 map<T,set<T>>，其中 T 是型別(datatype)，而數學上可以想成圖論(Graph Theory) 的 Directed Bipartite Graph
給定兩個集合 $X$ , $Y$ ，定義函數 $f : X \longrightarrow 2^{Y}$ ，其中 $2^{Y}:= \{S: S \subset Y\}$ 是 PowerSet of $Y$ ，也就是 $f(x)$ 是一個集合 !! ，我們把 $y = f(x)$ 寫成 $y \in f(x)$ !! (點對應到一個集合)，而如果 $\forall x\in X  \quad  |f(x)| = 1$ 就是傳統函數的概念。
而當 $|f(x)| = 1$ 時 $f(x) = \{ y \}$ (單一元素的集合，因為沒得選)，我們可以簡記寫成 $y = f(x)$
註: 是否要允許一對無， $f(x) = \emptyset$，視情況而決定
英文定義 :
For each $x \in X$  there exists  $y \in Y$ such that $y \in f(x)$
[可以說的事]
很自然的我們可以定義 Range $f$
$$f(X):= \bigcup_{x\in X}f(x) \subseteq Y$$
自然如果 $f(X) = Y$ 我們可以說是 $f$ 是 onto
也可以定義 Preimage ，給定 $y \in f(X) , f^{-1}(y) := \{x\in X : y\in f(x) \}$
我們可以定義一個集合 $G := \{(x,y) :  x \in X ,  y \in f(x)  \} \subseteq X \times Y$
然後可發現 $G$ 也可以用 Preimage 定義，即 $G = \{(x,y) :  y \in f(X) ,  x \in f^{-1}(y)  \}$
代表 $G$ 集合可以有兩種方式描述 !!
-----------------------------------------------------------------
[Example1] 二重積分交換順序的例子  $X = [0,1]$，$Y = [0,1]$，考慮實數函數 $g(x,y)$，然後積分範圍 $G$ 為$x$軸(y=0)跟 $y = x$，$x=1$之間的三角形區域，則 $y \in f(x) = [0,x]$ ，$x\in f^{-1}(y) = [y,1]$ ，註 : $f(X) = Y$
根據微積分 Fubini 定理，我們可以寫成

$$\iint_{G} g(x,y) dA = \underbrace{\int^{1}_{0}\int^{x}_{0} g(x,y) dydx}_{x\in X , y\in f(x)} = \underbrace{\int^{1}_{0}\int^{1}_{y} g(x,y) dxdy}_{y\in Y , x\in f^{-1}(y)}$$
-------------------------------------------------------------------
[Example2]  程式碼掃上三角矩陣(upper triangular matrix)，考慮 $I = \{1,2,3,....n\}， J = \{1,2,3,.....n\}$ 的 $n \times n$ 矩陣 $A_{ij}$ ，則我們只需要印出  $i \leq j$ 的部分，而且 $f(i) = [i,n]_{\mathbb{N}}$，$f^{-1}(j) = [1,j]_{\mathbb{N}}$ $f(I) = J$

為了更方便理解，寫成 $J_i = f(i)$，$I_j = f^{-1}(j)$
則掃矩陣我們可以用以下三種方式
++++++++++++++++++++++++++++++++++++
$(C1)$ 全掃型 $I \times J$
For  $i \in I$
$\qquad$ For $j \in J$
$\qquad$$\qquad$ if $(i\leq j)$ Print $A_{ij}$
$\qquad$ EndFor
EndFor
++++++++++++++++++++++++++++++++++++
$(C2)$ 先掃 $I$
For  $i \in I$
$\qquad$ For $j \in J_i$
$\qquad$$\qquad$ Print $A_{ij}$
$\qquad$ EndFor
EndFor
++++++++++++++++++++++++++++++++++++
$(C3)$ 先掃 $J$
For  $j \in J$
$\qquad$ For $i \in I_j$
$\qquad$$\qquad$ Print $A_{ij}$
$\qquad$ EndFor
EndFor
++++++++++++++++++++++++++++++++++++
其中 $(C2),(C3)$ 比 $(C1)$ 省了一半時間左右
註:則符號上可以記做 $G = I \times J_i = I_j \times  J$ (這是筆者的寫法)
註:也可以寫成這兩個等式  :
$\left\{\begin{array}{c} \bigcup_{i\in I} J_i  = J \\  \bigcup_{j\in J}I_j =I \\ \end{array}\right.$
-------------------------------------------------------------------
令 $S \subset X$  我們可以定義
[sub-image] $$f(S) := \bigcup_{x\in S} f(x)$$
[common set]   $$Com(f) := \bigcap_{x\in X} f(x)$$
[sub-common set] $$Com(f,S) := \bigcap_{x\in S} f(x)$$

如果$Com(f) \neq \emptyset$，common set 是重要的集合，因為$y$ 與 $x$ 無關
英文定義是 $\forall y \in Com(f) , y \text{ is  constant respect to } x$

----------------------------------------------------------------------------------
[Example]  ${\displaystyle{\lim_{n \rightarrow \infty }g_n(t)} = g(t)}$ ,  $t \in \mathbb{R}$
逐點收斂(pointwise-convergence) and 均勻收斂(uniform convergence)
詳細定義可參考高等微積分(advanced calculus) 或是實分析(real analysis)相關領域
我們可以定義 $f : \mathbb{R}^{+}\times \mathbb{R} \longrightarrow 2^{\mathbb{N}}$
$$N \in f(\epsilon,t) \Longleftrightarrow  \text{if } n > N \text{ then }  |g_n(t) - g(t)| < \epsilon$$
或是以下的定義
$$f(\epsilon,t) := \{N \in \mathbb{N}:  n > N \Rightarrow |g_n(t) - g(t)| < \epsilon  \}$$
(D1) 則 pointwise convergence 代表 $$\forall (\epsilon,t) \in  \mathbb{R}^{+}\times \mathbb{R}  , f(\epsilon,t) \neq \emptyset$$
(D2) 則 uniform convergence 代表 $$\forall \epsilon \in  \mathbb{R}^{+}  , \bigcap_{t\in \mathbb{R}}f(\epsilon,t) \neq \emptyset$$
註: uniform convergence 即為 common set 的概念 !!
註: 相似的概念還有均勻連續(uniform continuity)
-----------------------------------------------------------------------------------

[小結]
定義一對多函數是筆者在大學時代自創研究的符號與概念，雖然數學上都有類似的概念，但正式的符號定義並不多見，希望能藉由集合的交集聯集來描述複雜的邏輯概念，能對讀者有另一個角度的了解，關於一對多函數"合成"，還有其他可以做的事或許日後會再寫一篇 !!

[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 

by Plus & Minus 2017.08