# 函數基本概念

Function basics

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

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

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

$$
\range(f) = \{f(s) : s\in S\}.
$$

Therefore, $f$ is surjective if and only if $\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}
\idmap_S : S &\rightarrow S \\
s &\mapsto s
\end{aligned}
$$

is called the **identity map** on $S$, denoted as $\idmap_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, $\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

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

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

By setting `seed = 0` , we get
$S=\{1,2,3,4\},$
$T=\{1,2,3,4\},$
$$
\begin{aligned}
f : S &\rightarrow T \\
f(1) &= 2 \\
f(2) &= 4 \\
f(3) &= 1 \\
f(4) &= 3
\end{aligned}.
$$

---

##### Exercise 1(a)

判斷 $f$ 是否為嵌射函數。

<!-- eng start -->
Is $f$ injective?
<!-- eng end -->

:::warning
Good.

Grammar:

- [x] correspond --> correspond to
:::

##### <font color="#f00">**Answer:**</font>
It is injective since every elements in $S$ correspond to different elements of $T$.

---

##### Exercise 1(b)

判斷 $f$ 是否為映射函數。

<!-- eng start -->
Is $f$ surjective?
<!-- eng end -->

:::warning

"Value" usually means something in the codomain. For example, the value of $f(x)$ means the number in the codomain.

I think what you mean is every value in the codomain has a corresponding element in the domain.
:::

##### <font color="#f00">**Answer:**</font>
It is surjective since every value in the codomain has a corresponding element in the domain.

---

##### Exercise 1(c)

寫出 $f$ 的值域。

<!-- eng start -->
Find the range of $f$.
<!-- eng end -->

##### <font color="#f00">**Answer:**</font>
The range of $f$ is $\{1,2,3,4\}.$

---

## Exercises

##### Exercise 2

找出符合各條件的函數。

<!-- eng start -->
Find examples of functions satisfying the following conditions.
<!-- eng end -->

##### Exercise 2(a)

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

<!-- eng start -->
Give an example of an injective function and an example of a non-injective function.
<!-- eng end -->

:::warning
Nice! :+1:

Wording issue:
Then an injective function could be ... and a non-injective function could be ...
:::

##### <font color="#f00">**Answer:**</font>
Let $S = \{1,2\},$
and $T = \{3,4\}.$
Then an injective function could be

$$
\begin{aligned}
f : S &\rightarrow T \\
f(1) &= 3 \\
f(2) &= 4 \\
\end{aligned}
$$
and a non-injective function could be

$$
\begin{aligned}
g : S &\rightarrow T \\
g(1) &= 3 \\
g(2) &= 3 \\
\end{aligned}
$$

---

##### Exercise 2(b)

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

<!-- eng start -->
Give an example of a surjective function and an example of a non-surjective function.
<!-- eng end -->

##### 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}.
$$

<!-- eng start -->
Let $S = \{1,2,3,4\}$, $T = \{1,2,3,4\}$, and

$$
\begin{aligned}
f : S &\rightarrow T \\
f(1) &= 2 \\
f(2) &= 3 \\
f(3) &= 4 \\
f(4) &= 1
\end{aligned}.
$$
<!-- eng end -->

---

##### Exercise 3(a)

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

<!-- eng start -->
Find $f(\{1,3\})$.
<!-- eng end -->

:::success
Good.
:::

##### <font color="#f00">**Answer:**</font>
$f(\{1,3\})=\{2,4\}.$

---

##### Exercise 3(b)

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

<!-- eng start -->
Find $f^{-1}(\{1,3\})$.
<!-- eng end -->

:::success
Good.
:::

##### <font color="#f00">**Answer:**</font>

$f^{-1}(\{1, 3\})=\{4, 2\}.$

---
##### Exercise 3(c)

寫出 $f$ 的反函數。

<!-- eng start -->
Find the inverse function of $f$.
<!-- eng end -->

:::success
Beautiful.
:::

##### <font color="#f00">**Answer:**</font>
Let $S = \{1,2,3,4\}$, $T = \{1,2,3,4\}$, and
$$
\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\})$。

<!-- eng start -->
Find $f^{-1}(\{1\})$.
<!-- eng end -->

:::success
Exactly! Note that the parantheses are important, since $f^{-1}(1) = 4$ (value of the inverse functino) but $f^{-1}(\{1\}) = \{4\}$ (preimage).
:::

##### <font color="#f00">**Answer:**</font>
$f^{-1}(\{1\})=\{4\}.$

---

##### Exercise 3(e)

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

<!-- eng start -->
Find $f^{-1}(1)$.
<!-- eng end -->
##### <font color="#f00">**Answer:**</font>
$f^{-1}(1)=4.$

---

##### Exercise 4

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

<!-- eng start -->
Let $f: S\rightarrow T$ be a function. Prove the following properties about the domain and the codomain.
<!-- eng end -->

##### Exercise 4(a)

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

<!-- eng start -->
Prove that $S'\subseteq f^{-1}(f(S'))$ for any $S'\subseteq S$. Find an example where $S'\subsetneq f^{-1}(f(S'))$.
<!-- eng end -->

##### Exercise 4(b)

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

<!-- eng start -->
Prove that $T'\supseteq f(f^{-1}(T'))$ for any $T'\subseteq T$. Find an example where $T'\supsetneq f(f^{-1}(T'))$.
<!-- eng end -->

##### Exercise 4(c)

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

<!-- eng start -->
Suppose $f$ is injective. Prove that $S'= f^{-1}(f(S'))$ for any $S'\subseteq S$.
<!-- eng end -->

##### Exercise 4(d)

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

<!-- eng start -->
Suppose $f$ is surjective. Prove that $T'= f(f^{-1}(T'))$ for any $T'\subseteq T$.
<!-- eng end -->

##### Exercise 5

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

<!-- eng start -->
For the following pairs of sets, find a bijection between them.

When there is a bijection between two sets, then we believe the two sets have the same **cardinality** . This is natural for finite sets. However, it could be counter-intuitive for infinite sets since sometimes a infinite set has the same cardinality with its proper subset. Indeed, this is similar to the idea of $\infty + 1 = \infty$, which is acceptable. A set that has the same cardinality with the set of natural numbers is called **countable** , or **countably infinite** . Therefore, in modern mathematics, we have $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}|$, but $|\mathbb{R}| \neq |\mathbb{N}|$.
<!-- eng end -->

##### Exercise 5(a)

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

<!-- eng start -->
Let $S = \{1,2,3\}$ and $T = \{x,y,z\}$. Find a bijection between $S$ and $T$.
<!-- eng end -->

:::success
Nice.
:::

##### <font color="#f00">**Answer:**</font>
Let $f:S\rightarrow T,$
$f(1)=x,\,f(2)=y,\,f(3)=z.$

---
##### Exercise 5(b)

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

<!-- eng start -->
Let $S = \mathbb{Z}$ and $T = 2\mathbb{Z} = \{2z: z\in\mathbb{Z}\}$. Find a bijection between $S$ and $T$.
<!-- eng end -->

:::success
Nice.
:::

##### <font color="#f00">**Answer:**</font>
Let $f:S\rightarrow T,\,f(x)=2x.$

---
##### 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$ 的對射。

<!-- eng start -->
Let $S = 2\mathbb{Z} = \{2z : z\in\mathbb{Z}\}$ and $T = 2\mathbb{Z} + 1 = \{2z+1 : z\in\mathbb{Z}\}$. Find a bijection between $S$ and $T$.
<!-- eng end -->

:::warning

Oops... think agian...

Your function

| $x$ | 2 | 4 | 6 | 8 | 10 |
|---|---|---|---|---|---|
| $f(x)$ | 5 | 9 | 13 | 17 | 21 |

Is this what you want?
:::

##### <font color="#f00">**Answer:**</font>
Let $f:S\rightarrow T,\,f(x)=x+1.$

---
##### Exercise 5(d)

令 $S = \mathbb{N} = \{1,2,3,\ldots\}$ 且 $T = \mathbb{Z}$。
找一個 $S$ 到 $T$ 的對射。

<!-- eng start -->
Let $S = \mathbb{N} = \{1,2,3,\ldots\}$ and $T = \mathbb{Z}$. Find a bijection between $S$ and $T$.
<!-- eng end -->

:::success
:100: Wonderful!
:::

##### <font color="#f00">**Answer:**</font>
Let $f:S\rightarrow T,$
$$f(x) = \begin{cases}
\displaystyle \frac{x}{2} & \text{if $x$ is even} \\
\displaystyle -\frac{(x-1)}{2} & \text{if $x$ is odd}
\end{cases}.
$$

---

:::info

collaboration: 1
4 problems: 4
done: 2a, 2b, 3a, 3b

extra: 3.5
done: 3c, 3d, 3e, 5a, 5b, 5c, 5d

moderator: 2
quality control: 2
:::