# 離散上-第一章 基本數學
<!-- ## 快速跳轉
- [Before we start...](#Before-we-start)
- [第一章: 基本數學](#第一章：基本數學)
- 第二章
- 第三張
-->
## Before we start...
### 引理，定理，系理以及命題
- 定理 Theorem: 最重要的結果
- 系理 Corollary: 接續該定理所衍生的立即應用
- 引理 Lemma: 用以證明上述定理的小結果，可以將引理視為 "引出" 定理的 前置結果

<!-- # 第一章：基本數學 -->
## 1.1 集合論

### 集合
- 常見數系
- $N = \{0, 1, 2, \dots \}$
- $Z = \{\dots, -2, -1, 0, 1, 2, \dots\}$
- $Z^+$ 正整數
- $Q$ 有理數
- $R$ 實數
- $C$ 複數
- 加 $^*$ 就是 「非零」
- 集合中的元素**無次序**之分，也**不計重複**。e.g. $\{0, 2, 1, 1\} = \{0, 1, 2\}$。

### 子集 & 真子集 (proper subset)
- **Def**: A, B 兩個 set，$\forall x (x \in A \Rightarrow x \in B)$，則 A is a subset of B ($A \subseteq B$).
- **Def**: $A \subseteq B \cap A \not= B$，則 $A$ 是 $B$ 的真子集，計做 $A \subset B$

#### *注意事項*
1. $\phi \not= \{\phi\}$: 前者 0 個元素，後者 1 個
2. $A = B \iff A \subseteq B \cap B \subseteq A$
3. $x \in A \iff \{x\} \subseteq A$
4. Universal set (宇集合) 指問題的所以元素所成之集合

> #### 本處常錯
> - $\phi \subseteq \phi$ -> O (空集合是任何集合的子集)
> - $\phi \in \phi$ -> X (空集合沒有任何元素，何來的 $\in$ ?)
> - $\{\phi\} \in \{\phi\}$ -> X (應改為 $\subseteq$)
> - **要先檢查給定的 set 裡面是否有重複的元素**

### 集合的運算
1. $A - B = \{x| x\in A \cap x\not\in B\}$ (差集 difference)
2. $\overline{A} = \{x| x \in U \cap x \not \in A\}$ (補集 complement)
3. **$A \oplus B = (A \cup B) - (A \cap B) = (A - B) \cup (B - A)$ 稱為 A 和 B 的對稱差 (symmetric difference)，又記做 $A \triangle B$。**

### 集合的性質
假設 $A, B, C \subseteq U$，以下性質成立(其他看課本 1-8)：
1. 分配律 (distributive laws):<br/>$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ <br/> $A \cap (B \cup C) = (A\cap B) \cup (A \cap C)$
2. 吸收率 (absorption laws):<br/> $A \cup (A \cap B) = A \cap (A \cup B) = A$
3. $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
4. $A \cap (B \oplus C) = (A \cap B) \oplus (A \cap C)$

### De Morgan's law
1. $\overline{A \cup B} = \overline{A} \cap \overline{B}$
2. $\overline{A \cap B} = \overline{A} \cup \overline{B}$

> 推廣：$\overline{\cup_{i \in I}A_i} = \cap_{i \in I}\overline{A_i}$、$\overline{\cap_{i \in I}A_i} = \cup_{i \in I}\overline{A_i}$

#### *注意事項*
1. $A \cap C = B \cap C$ 不代表 $A = B$。e.g. $A$ 可以是個超長的 set
2. $A \cup C = B \cup C$ 不代表 $A = B$。e.g. 和 $C$ 重疊的部分可以不同。
3. 遇到有同時有 $\oplus、-$ 和 $\cup、\cap$ 的題目可以**畫圖驗證**比較安全。

### 基數 (Cardinality)
一個集合 $A$ 中相異的元素個數，稱作 $|A|$。

#### *注意事項*
1. $|\{\phi , \{\phi, \{\phi \}\} \}| = 2$

### 冪集合 (power set)
- $P(A) = \{X|X \subseteq A\}$，也就是 A 的所有**子集合**所形成的集合。*注意：有時候也繼做 $2^A$*
- $|A| = n \Rightarrow |P(A)| = 2^n$ (因為每個元素都可以**出現**或**不出現**) (可能可以解釋第一點為何以 2 為底作表示？)

假設 $A_n = \{a_1, a_2, \dots, a_n\}$，則 $P(A_n)$ 可以

$$
\begin{aligned}
P(\phi) &= \{\phi\} \\
P(A_1) &= \{\phi, \{a_1\}\} \\
P(A_2) &= \{\phi, \{a_1\}, \{a_2\}, \{a_1, a_2\} \} \\
&= P(A_1) \cup \{ X \cup \{a_2\}| X \in P(A_1)\}\\
P(A_n) &= P(A_{n-1}) \cup \{ X \cup \{a_n\}| X \in P(A_{n-1})\}\\
\end{aligned}
$$

由上述可以看出 $A_n$ 含偶數個元素的子集數 $=$ 含奇數個元素的子集數。
> Why?
> - 情況一： $\{1, 2, 3, 4, 5\}$
>$\{1\} \rightarrow \{2, 3, 4, 5\}$ (一奇配一偶)
> - 情況二： $\{1, 2, 3, 4\}$
> $\{1, 2\} \rightarrow \{3, 4\}$ (偶配偶)
> $\{1\} \rightarrow \{2, 3, 4\}$ (奇對奇)

範例：$A = \{1, 3, 5\}$, then $P(A) = \{\phi, \{1\}, \{3\}, \{5\}, \{1, 3\}, \{1, 5\}, \{3,5\}, \{1, 3, 5\} \}$

#### *注意事項* $\newcommand{\qed}{■}\newcommand{floor}[1]{\lfloor#1\rfloor}\newcommand{ceil}[1]{\lceil#1\rceil}$
1. $P(A \cup B) \not= P(A) \cup P(B)$
Why? 假設 $|A| = 5, |B| = 3$，則 $P(A \cup B)$ 裡應該會有一個元素 $|a| = 8$。但 $P(A), P(B)$ 最大的元素也僅僅為基數 (cardinality) 5 的集合。
2. $P(A \cap B) = P(A) \cap P(B)$
$$
\begin{aligned}
s \in P(A \cap B) &\Leftrightarrow s \subseteq (A \cap B) \Leftrightarrow s \subseteq A \cap s \subseteq B \\
&\Leftrightarrow P(A) \cap P(B) \qed
\end{aligned}
$$

### 卡氏積 (Cartesian product)
$A, B$ 的卡氏積計作 $A \times B$，定義為
$$
A \times B = \{(a, b)|\ a \in A, b \in B \}
$$
$(a, b)$ 稱為有序對 (ordered pair)，**順序顛倒視為不同**

#### 卡氏積的一些性質
1. $|A| = m, |B| = n \Rightarrow |A \times B| = mn$
2. $A \times \phi = \phi = \phi \times A$
3. 可擴充至 $n$ 個集合的卡氏積
$$
A_1 \times A_2 \times \dots \times A_n = \{(a_1, a_2, \dots, a_n)|\ a_1\in A_1, a_2 \in A_2, \dots \}
$$
其中 $(a_1, \dots, a_n)$ 為 $n$-序對 ($n$-tuple)
4. 可計為 $A^n$

## 1.2 數學歸納法 (Mathematical induction)
### Before we start...
- Axiom (aka 公理/公設):
> *公理是沒有經過證明，但被當作不證自明的一個命題$\quad\quad$ --[維基百科](https://zh.wikipedia.org/zh-tw/%E5%85%AC%E7%90%86)*
- 在數學歸納法中，我們需要 The Well-Ordering Principle
$$
Z^+ \text{ 的每個非空子集必包含最小元素}
$$

### 數學歸納法原理
$P(n)$ 為性質函數 (值為 True/false)，若滿足以下
$$
\begin{aligned}
\text{Step 1} &: P(1)\text{為真}\\
\text{Step 2} &: \forall k \geq 1, \text{"$P(k) \rightarrow P(K+1)$" 為真}
\end{aligned}
$$
則 $\forall n \in Z^+, P(n)$ 為真。

### 強數學歸納法
$P(n)$ 為性質函數 (值為 True/false)，若滿足以下
$$
\begin{aligned}
\text{Step 1} &: P(n_0)\text{為真}\\
\text{Step 2} &: \forall n_0 \leq t \leq 1, \text{$P(t)為真保證 P(K+1)$ 為真}
\end{aligned}
$$
則 $\forall n > n_0, P(n)$ 為真。

### 兩者的差異
同樣的題目兩者皆解得出來，但運用**強數學歸納法**，要注意須證明幾項要看**歸納步驟而定**。

<!-- <h3 style="color:red;">這邊寫題目比較重要，整理待補</h3> -->

## 1.3 基礎數論
### Floor, Ceiling
1. $\exists! n \in Z$^[存在唯一] s.t. $n \leq x \leq n+1$，$n$ 即為 $x$ 的 floor (記作 $\floor{x}$)
2. $\exists! n \in Z$ s.t. $x \leq n \leq x+1$，$n$ 即為 $x$ 的 ceilng (記作 $\ceil{x}$)

^[存在唯一]$\exists!$ 是「存在唯一」的意思。

### 一些性質
1. $\floor{x} + \floor{y} \leq \floor{x+y} \leq \floor{x} + \floor{y} + 1$
2. $\floor{x} + \floor{-x} = \begin{cases}
0 & \text{if } x \in z\\
-1 & \text{otherwise}
\end{cases}$
3. $\floor{\sqrt{\floor{x}}} = \floor{\sqrt{x}}$
<!-- 4. <span style="color:red">證明待補</span> -->

### 因數、倍數 (factor & multiple)
$\exists k \in Z: n = m k$，則稱 $m$ 整除 $n$ ($m$ divide $n$)。記作 $m\mid n$，此時 $m$ 為 $n$ 的 factor，$n$ 為 $m$ 的 muliple；反之則為 $m \not\mid n$。

### 質數 (prime)
$p \in Z^+ \cap p \geq 2$，若只有 1 和自己這兩個正因數，反之為組合數 (composite)。
> *注意：1 不是質數也不是組合數*
> *注意：有時相關證明要把 2 分開討論，因他為唯一的偶數質數*

### Lemma
假設 $n \in Z^+$ 且 composite，$\exists p:p\mid n$，$p$ 為質數。

### Theorem
1. $Z^+$有無限多個質數
2. $n \in Z^+$ 且 $n$ 為組合數，則必有一個質因數 $p \leq \sqrt{n}$
3. 質因數分解唯一

> #### 本處常錯 / 不會
> 1. How many zeros are there at the end of the decimal representation of $400!$ ?
> *Sol:*
> $400!$ 可寫成唯一的 $2^a3^b5^c7^d\dots$，只需關心 2 和 5，因 $2 \times 5 = 10$。
> $\Rightarrow$ 換句話說，只要觀察有幾個 5 相乘 (5 的數量會比 2 少，*ps: 但不知道的話把 2 的也算一下再比較也行啦*)
> $\Rightarrow$ 1~400 中，包含一個5的(aka 上述的 $c \geq 1$)一共有 $\floor{\frac{400}{5}} = 80$，包含兩個5的(aka 上述的 $c \geq 2$)一共有 $\floor{\frac{400}{25}} = 16$，包含三個5的(aka 上述的 $c \geq 3$)一共有 $\floor{\frac{400}{125}} = 3$
> $\Rightarrow$ 一共有 $80+ 16+3 = 99$ 個五 (aka $c=99$)

### 除法
1. 除法演算法 : $m \in Z, n \in Z^+$ 存在唯一 $q, r \in Z$，s.t. $m = nq + r$ 其中 $0 \leq r < n$
2. 商數 Quotient、餘數 Remainder

### 同餘 (Congruence)
$a, b, n \in Z, n > 0$, if $n \mid (a - b)$, then $a \equiv b \mod n$
> *雖然很直覺，但有時證明要從定義下手*

#### 一些性質
1. $(a + b) \mod n = ((a \mod n) + (b \mod n))\mod n$
2. $ab\mod n = ((a \mod n)(b \mod n))\mod n$

### 最大公因數
$m, n \in Z$, at least one of them not 0. Then... the biggest $g: (g \mid m) \cap (g \mid n)$ is the **greatest common divisor**, $g= \text{gcd}(m, n)$

#### 互值 (Relatively prime)
gcd$(m, n) = 1$

### Theorem (Euclidean)
$$
m = nq+r
$$$$
\text{gcd}(m, n) = \text{gcd}(n, m \mod n)
$$
> #### Proof
> $(g \mid m) \cap (g \mid n) \Rightarrow g \mid (m-nq)$, where $m-nq=r$

### Euclidean algorithm
$$
\begin{cases}
\text{gcd}(n, 0)= n & n > 0\\
\text{gcd}(m, n)=\text{gcd}(n, m \mod n) & m > n
\end{cases}
$$
#### *注意事項*
1. $g$ 可以寫成 $m, n$ 的線性組合，$\exists s, t \in Z \mid g = sm + tn$ *(不唯一)*
2. 寫橫式在回推的時候千萬要細心

### Theorem
$ax + by = c$ 有整數解 $\iff$ $gcd(a, b) \mid c$
因為 $g = sx + ty$ ，若 $g \not\mid c$，則必不存在整數解。

### Multiplicative inverse
$ax \equiv 1 \mod n$，則 $x$ 為 $a$ 在 mod 2 下的乘法反元素。

- if gcd$(a, n) = 1$, multiplicative inverse $x$ of $a$ under mod $n$ exist.
- 方法? 用 Euclidean algorithm 找 gcd 並且回推出 $sx + ty = 1$

### Lemma
$a$ 在 mod $p$ 的乘法反元素是 $a$ $\iff a \equiv \pm 1 \mod p$

### Wilson's theorem
A prime $p$, then $(p-1)! \equiv -1 \mod p$

From lemma above, 只有 1, 和 p-1 的反元素是自己，剩下 $2$ ~ $p-2$ 會湊成一對一對
So... $(p-1)! \equiv (p-1) \equiv -1$

#### *注意事項*
1. 若某個 $n$ 滿足上面的式子，則可反推 $n$ 是質數。

### Fermat's Little Theorem
$m \in Z$, $p$ is prime s.t. gcd$(m, p) = 1$, then $m^{p-1} \equiv 1 \mod p$

### Euler's $\phi$ function
$\phi(n)$ 為 $\{1, 2, \dots, n\}$ 中與 $n$ 互質的元素個數。 *(aka Euler's totien function)*

#### 性質
1. $n = p_1^a p_2^b p_3^c$
$\Rightarrow \phi(n) = (p_1-1)p_1^{a-1} (p_2-1)p_2^{b-1} (p_3-1)p_3^{c-1}$
2. $\phi(n) = \phi(x)\phi(y)$ if $x$, $y$ relatively prime.
3. $\phi(p)=p-1 \iff p$ is prime

### Euler 對 Fermat 的推廣
gcd$(m, n) = 1$, 則 $m^{\phi(n)}\equiv 1 \mod n$
> 原本 Fermat 是說 $n$ 是質數，所以必然 gcd 為 1。

### Chinese Remainder Theorem (CRT)
$$
\begin{aligned}
x &\equiv r_1 \mod n_1\\
x &\equiv r_2 \mod n_2\\
&\quad\quad \vdots \\
x &\equiv r_k \mod n_k
\end{aligned}
$$
如果 $n_1, n_2, \dots, n_k$ 彼此互質，則有為一解
$$
x = \sum_{j=1}^k r_j M_i N_i \mod n_i
$$
where $N_j = \frac{n}{n_j} = \Pi_{i \not=j}n_i$ , $N_jM_j \equiv 1 \mod n_j$

#### *注意事項*
1. $n_1, \dots, n_k$ 互質，若不互質則需拆解。
假設有一條方程式 $x \equiv r_i \mod n_i$， 其中 $n_i$ 可以寫成 $n_i = pq$ 且 gcd$(p,q)=1$，可以拆解成
$$
x \equiv r_i \mod n_i \Leftrightarrow
\begin{cases}
x \equiv r_i \mod p\\
x \equiv r_i \mod q
\end{cases}
$$