函數基本概念

This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.

Main idea

Let \(S\) and \(T\) be two sets.
A function \(f\) from \(S\) to \(T\) is an assignment of each element \(s\in S\) with an element \(f(s)\in T\).
We usually write
\[\begin{aligned} f : S &\rightarrow T \\ s &\mapsto f(s) \end{aligned} \] to descriibe a function.
We call \(S\) and \(T\) the domain and the codomain of \(f\).

A function \(f:S\rightarrow T\) is injective if

• for any distinct elements \(s_1,s_2\in S\), i.e., \(s_1\neq s_2\), their values under the function \(f(s_1), f(s_1)\) are also distinct, i.e., \(f(s_1)\neq f(s_2)\).

Equivalently, \(f\) is injective if \(f(s_1) = f(s_2)\) implies \(s_1 = s_2\).
The term "injective" is also known as "one-to-one".
An injection is an injective function.

A function \(f : S \rightarrow T\) is surjective if

• for any element \(t\in T\), there is an element \(s\in S\) such that \(f(s) = t\).

The range of a function \(f\) is
\[\operatorname{range}(f) = \{f(s) : s\in S\}. \]
Therefore, \(f\) is surjective if and only if \(\operatorname{range}(f) = T\).
The term "surjective" is also known as "onto".
A surjection is a surjective function.

If a function \(f\) is both injective and surjective, then it is bijective.
A bijection is a bijective function.

If \(f\) is a bijection, then one may define its inverse as
\[\begin{aligned} f^{-1} : T &\rightarrow S \\ t &\mapsto f^{-1}(t), \end{aligned} \] where \(f^{-1}(t)\) is defined as the unique element \(s\in S\) such that \(f(s) = t\).
(Here the existence of \(s\) is because \(f\) is surjective, and the uniqueness of \(s\) is because \(f\) is injective.)

The function
\[\begin{aligned} \operatorname{id}_S : S &\rightarrow S \\ s &\mapsto s \end{aligned} \] is called the identity map on \(S\), denoted as \(\operatorname{id}_S\).

Let \(f : S \rightarrow T\) be a function.
If \(S'\subseteq S\), then the image of \(S'\) is \[f(S') = \{ f(s) : s\in S'\}. \] If \(T'\subseteq T\), then the preimage of \(T'\) is \[f^{-1}(T') = \{ s\in S : f(s) \in T'\}. \]
Therefore, \(\operatorname{range}(f) = f(S)\).

Note that although both the inverse and the preimage use the notation \(f^{-1}\), the inverse is a function of elements in \(T\) while the preimage is a function of subsets in \(T\), so they should be distinguishable.

When the domain \(S\), the codomain \(T\), and a formula \(f\) are given, we say \(f\) is well-defined if \(f\) is indeed a function.
Here are some examples.

1. The value \(f(s)\) should exist in \(T\): Let \(S = T = \mathbb{R}\) and \(f(x) = \frac{1}{x}\). Then \(f\) is not well-defined since \(f(0)\) is not a real number.
2. The value of an element under different representation should have the same value: This happens when an element has several equivalent representation, e.g., \(\frac{1}{2} = \frac{2}{4}\). Let \(S = \mathbb{Q} \times \mathbb{Q}\), \(T = \mathbb{Q}\), and \(f(\frac{a}{b}, \frac{c}{d}) = \frac{a+c}{b+d}\). Thus, we have \((\frac{1}{2}, \frac{3}{3}) = (\frac{2}{4}, \frac{3}{3})\) but \(f(\frac{1}{2}, \frac{3}{3}) = \frac{4}{5} \neq f(\frac{2}{4}, \frac{3}{3}) = \frac{5}{8}\).

Side stories

• countable

Experiments

Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = False
inj = choice([True, False])
sur = choice([True, False])
S = list(range(1,5))
if inj and sur:
    T = list(range(1,5))
if inj and not sur:
    T = list(range(1,6))
if not inj and sur:
    T = list(range(1,4))
if not inj and not sur:
    T = list(range(1,5))
while True:
    f = {s: choice(T) for s in S}
    ran = list(set(f.values()))
    if inj == (len(ran) == len(S)) and sur == (len(ran) == len(T)):
        break
    
print("S =", S)
print("T =", T)
print("f : S --> T")
for s in S:
    print("f(%s) ="%s, f[s])


if print_ans:
    print("Injective?", inj)
    print("Surjective?", sur)
    print("range(f) =", ran)

\(S = [1, 2, 3, 4]\)

\(T = [1, 2, 3, 4]\)

\(f : S \rightarrow T\)

\(f(1) = 2\)

\(f(2) = 4\)

\(f(3) = 1\)

\(f(4) = 3\)

Exercise 1(a)

判斷 \(f\) 是否為嵌射函數。

\(Ans:\) 每一個元素對應的函數值都相異， \(f\) 為嵌射函數

Exercise 1(b)

判斷 \(f\) 是否為映射函數。

\(Ans:\) 每一個對應元素都有一個對應值，\(f\) 為映射函數

Exercise 1©

寫出 \(f\) 的值域。

\(Ans:\)
值域為 \(T = \{1, 2, 3, 4\}\)。

Exercises

Exercise 2

找出符合各條件的函數。

Exercise 2(a)

給兩個函數的例子﹐一個是嵌射、一個不是。

令 \(S = \{1,2,3,4\}\)、
\(T = \{1,2,3,4\}\)、且
\[\begin{aligned} f : S &\rightarrow T \\ f(1) &= 1 \\ f(2) &= 2 \\ f(3) &= 3 \\ f(4) &= 4 \end{aligned}. \] 函數 \(f\) 為一嵌射的函數。

令 \(S = \{1,2,3,4\}\)、
\(T = \{1,2,3,4\}\)、且
\[\begin{aligned} g : S &\rightarrow T \\ g(1) &= 1 \\ g(2) &= 1 \\ g(3) &= 1 \\ g(4) &= 1 \end{aligned}. \] 函數 \(g\) 不為一嵌射的函數。

Exercise 2(b)

給兩個函數的例子﹐一個是映射、一個不是。

令 \(S = \{1,2,3,4\}\)、
\(T = \{1,2,3,4\}\)、且
\[\begin{aligned} f : S &\rightarrow T \\ f(1) &= 1 \\ f(2) &= 2 \\ f(3) &= 3 \\ f(4) &= 4 \end{aligned}. \] 函數 \(f\) 為一映射的函數。

令 \(S = \{1,2,3,4\}\)、
\(T = \{1,2,3,4\}\)、且
\[\begin{aligned} g : S &\rightarrow T \\ g(1) &= 1 \\ g(2) &= 1 \\ g(3) &= 1 \\ g(4) &= 1 \end{aligned}. \] 函數 \(g\) 不為一映射的函數。

Exercise 3

令 \(S = \{1,2,3,4\}\)、
\(T = \{1,2,3,4\}\)、且
\[\begin{aligned} f : S &\rightarrow T \\ f(1) &= 2 \\ f(2) &= 3 \\ f(3) &= 4 \\ f(4) &= 1 \end{aligned}. \]

Exercise 3(a)

求 \(f(\{1,3\})\)。

由上述可知， \(f(\{1,3\})=\{2,4\}\) 。

Exercise 3(b)

求 \(f^{-1}(\{1,3\})\)。

由上述可知， \(f^{-1}(\{1,3\})=\{2,4\}\) 。

Exercise 3©

寫出 \(f\) 的反函數。

令 \(S = \{1,2,3,4\}\)、
\(T = \{1,2,3,4\}\)、且
\[\begin{aligned} f^{-1} : T &\rightarrow S \\ f^{-1}(1) &= 4 \\ f^{-1}(2) &= 1 \\ f^{-1}(3) &= 2 \\ f^{-1}(4) &= 3 \end{aligned}. \]

Exercise 3(d)

求 \(f^{-1}(\{1\})\)。

由上述可知， \(f^{-1}(\{1\})=\{4\}\) 。

Exercise 3(e)

求 \(f^{-1}(1)\)。

由上述可知， \(f^{-1}(1)=4\) 。

Exercise 4

令 \(f:S\rightarrow T\) 為一函數。
證明以下關於投影區和送影區的性質。

Exercise 4(a)

證明對任何子集 \(S'\subseteq S\) 都有 \(S'\subseteq f^{-1}(f(S'))\)。
找一個例子讓 \(S'\subsetneq f^{-1}(f(S'))\)。

(1)
Let \(a\in S'\).
Then, we have \(f(\{a\})\subseteq f(S')\).
Similarly, \(f^{-1}(f(\{a\}))\subseteq f^{-1}(f(S'))\).
Because \(a\in f^{-1}(f(\{a\}))\subseteq f^{-1}(f(S'))\), we can conclude \(S'\subseteq f^{-1}(f(S'))\).

(2)
Define \(f(x)=0\), for all \(x\in S\).
Let \(S'\subsetneq S\).
Then \(f^{-1}(f(S'))=f^{-1}(\{0\})=S\).
So, \(S'\subsetneq f^{-1}(f(S'))\).

Exercise 4(b)

證明對任何子集 \(T'\subseteq T\) 都有 \(T'\supseteq f(f^{-1}(T'))\)。
找一個例子讓 \(T'\supsetneq f(f^{-1}(T'))\)。

(1)
Let \(y\in f(f^{-1}(T'))\).
Then there is \(x\in f^{-1}(T')\) such that \(f(x) = y\)
Since \(x\in f^{-1}(T')\), \(y = f(x) \in T'\).
So, \(T'\supseteq f(f^{-1}(T'))\).

(2)
Let \(f\) be a function mapping \(S\) to \(T\) and \(T=\mathbb{R}\).
Define \(f(x)=0\), for all \(x\in S\), and \(T'=\{0,1\}\).
Then \(\{0\}=f(f^{-1}(T'))\subsetneq T'\).

Exercise 4©

證明若 \(f\) 是嵌射﹐
則對任何子集 \(S'\subseteq S\) 都有 \(S'= f^{-1}(f(S'))\)。

We suffer to show that \(f^{-1}\) is also an injective function.
Let \(f\) be a function mapping \(S\) to \(T\).
Because \(f\) is an injective function, \(f\) has an inverse function \(f^{-1}\) mapping \(T\) to \(S\).
Pick \(a,b\in T\) such that \(f^{-1}(a)=f^{-1}(b)=x\in S\).
So, \(f(x)=a=b\). Then, we prove \(f^{-1}\) is injective.

Exercise 4(d)

證明若 \(f\) 是映射﹐
則對任何子集 \(T'\subseteq T\) 都有 \(T'= f(f^{-1}(T'))\)。

Let \(T'=f(S')\).
By ©, we have \(f(f^{-1}(T'))=f(f^{-1}(f(S')))=f(S')=T'\).

Exercise 5

在以下集合中找到一個對射。
（兩個集合間如果存在一個對射﹐則它們的數量級就被視為是一樣的。
這個現象在個數有限的時候很自然﹐
但當個數無限多的時候會出現一個集合和它的子集個數一樣多的狀況﹐有些違反直覺﹐
但其實這現象就類似於 \(\infty + 1 = \infty\) 這種概念﹐在無限大的時候是可接受的。
所有和自然數 同樣數量級的集合﹐我們就說這樣的集合大小是無窮可數多個。
所以在當代的數學定義裡 \(|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}|\)﹐
但 \(|\mathbb{R}| \neq |\mathbb{N}|\)。）

Exercise 5(a)

令 \(S = \{1,2,3\}\) 且 \(T = \{x,y,z\}\)。
找一個 \(S\) 到 \(T\) 的對射。

\[\begin{aligned} f : S &\rightarrow T \\ f(1) &= x, \\ f(2) &= y, \\ f(3) &= z. \end{aligned} \]

Exercise 5(b)

令 \(S = \mathbb{Z}\) 且 \(T = 2\mathbb{Z} = \{2z: z\in\mathbb{Z}\}\)。
找一個 \(S\) 到 \(T\) 的對射。

\[\begin{aligned} f : S &\rightarrow T \\ f(x) &= 2x. \end{aligned} \]

Exercise 5©

令 \(S = 2\mathbb{Z} = \{2z : z\in\mathbb{Z}\}\) 且 \(T = 2\mathbb{Z} + 1 = \{2z+1 : z\in\mathbb{Z}\}\)。
找一個 \(S\) 到 \(T\) 的對射。

\[\begin{aligned} f : S &\rightarrow T \\ f(x) &= x+1. \end{aligned} \]

Exercise 5(d)

令 \(S = \mathbb{N} = \{1,2,3,\ldots\}\) 且 \(T = \mathbb{Z}\)。
找一個 \(S\) 到 \(T\) 的對射。
\[\begin{aligned} f : S &\rightarrow T \end{aligned}. \] \[f(x) = \begin{cases} 0 & \text{if }x=1, \\ (-1)^x[\frac{x}{2}] & \text{if }x\in\mathbb{N}\setminus\{1\}. \end{cases} \]