# 函數基本概念

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

## 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)

:::warning

- [x] $-->$ --> $\rightarrow$
:::

$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(c)

寫出 $f$ 的值域。

:::warning

- [x] 程式的時候才用 `[1,2,3,4]`，數學的時候寫 $\{1,2,3,4\}$
:::

$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(c)

寫出 $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'))$。

:::warning

- [x] 反函數 $f^{-1}$ 不一定存在，所以不能寫 $f^{-1}(y)$，所以 Then $f^{-1}(y)\in f^{-1}(T')$. --> Then there is $x\in f^{-1}(T')$ such that $f(x) = y$.
- [x] Finally, we have $y\in T'$. --> Since $x\in f^{-1}(T')$, $y = f(x) \in 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(c)

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

:::warning

- [ ] $f$ 不一定有反函數，因為有 4(a)，只要證明嵌射可以保證 $S' \supseteq 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'))$。

:::warning

- [ ] 題目有錯，我把原本的嵌射改成映射。
:::

Let $T'=f(S')$.
By (c), 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(c)

令 $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}
$$

:::info
目前分數 6.5
:::