## 2. 基礎結構: 集合、函數、序列、總和、與矩陣

### 2.1 集合

#### Definition - 集合

集合是一個不需按照順序排列，且集合內部所有元素均不相等的物件。

$a \in A$, $a$ 是集合 $A$ 的元素之一。

$a \not \in A$, $a$ 不是集合 $A$ 的元素之一。

##### Example

$\{a, b\} = \{b, a\}$

$\text{{a, a, b}} = \text{{a, b}}$

$(a, b) \neq (b, a)$
<br>
<br>

---

#### Introduce - 窮舉法

如果窮舉出集合內的所有物件是可能的，我們可以窮舉出集合內的所有物件。

##### Example 1

所有母音的集合。

$V = \{a, e, i, o, u\}$

<br>

##### Example 2

所有小於100的正整數的集合。

$O = \text{{1, 2, 3, ... 99, 100}}$

<br><br>

---

#### Introduce - 集合建構式符號

$\text{{x | x has property P}}$，念作「所有符合條件$P$元素$x$的集合」。
<br>

##### Example 1

所有小於10的正整數奇數集合。

$O = \{1, 3, 5, 7, 9...\}$

$O = \text{{x | x is an odd positive integers less than 10}}$
x 是小於 10 的奇數正整數

$O = \{{2x+1\ |\ 0 \le x \le 4}\}$

<br>

##### Example 2

所有正的有理數，且為整數的集合$\mathbb{Q}^+$。

$\mathbb{Q}^+ = \{{x\in\mathbb{R}\ |\ x = \dfrac{a}{b}\text{ for some positive integers p and q.}}\}$

<br>
##### Example 3

所有自然數的整數集合。

$\mathbb{N} = \{0, 1, 2, 3, ...\}$

<br>

##### Example 4

所有整數的集合。

$\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$

<br>
##### Example 5

所有正整數的集合。

$\mathbb{Z}^+ = \{0, 1, 2, ...\}$

<br>

##### Example 6

所有有理數的集合。

$\mathbb{Q} = \{\dfrac{p}{q}\ |\ p \in \mathbb{Z}, q \in \mathbb{Z}, q \neq 0\}$

---

#### Definition - 集合相等

若兩個集合的所有元素相等，則我們說這兩個集合相等。

$A = B \iff (x \in A \rightarrow x \in B)$

##### Example

$\{1, 3, 5\} = \{3, 5, 1\}$

$\{1, 3, 3, 3, 5, 5, 5, 5\} = \{1, 3, 5\}$

#### Definition - 空集合

空集合沒有任何元素，寫作 $\varnothing$。

#### Definition - 單元素集合

單元素集合只有一個元素。

##### Example

$\{\varnothing\}$ 是一個單元素集合。

---

#### Introduce - 文氏圖

我們可以用文氏圖來表示一個集合。

##### Example


$U = \text{{a, b, c, d, e, f, g ...}}$

$V = \text{{a, e, i, o, u}}$

---

#### Definition - 子集合

若且唯若集合$A$的每個元素都為集合$B$的元素，則我們說$A$是$B$的子集合，且$B$為$A$的父集合。

可以表示成$(A \subseteq B \land B \supseteq A) \iff \forall x(x \in A \rightarrow x \in B)$

#### Theorem - 1

對於每一個集合 $S$, $\varnothing \subseteq S$, $S \subseteq S$

$\{\} \subseteq \{\}$

$\{\} \subseteq \{a\}$

$\{a\} \subseteq \{a\}$

$\{\} \subseteq \{a, b\}$

$\{a\} \subseteq \{a, b\}$

$\{b\} \subseteq \{a, b\}$

$\{a, b\} \subseteq \{a, b\}$

如果一個集合有$n$個元素，則他會有$n!$種不同的子集合。

---

#### Introduce - 真子集

若$A$是$B$的真子集，則對於所有在集合$A$的$x$也都在集合$B$，且$B$存在一個元素不在集合$A$。

可以寫作，$A \subset B \iff \forall x(x \in A \rightarrow x \in B) \land \exists x(x \in B \land x \not \in A)$。

---

#### Definition - 有限集合與無限集合

如果一個集合有剛好$n$個元素，且$n$存在，則我們說這個集合是有限的，否則這個集合是無限的。

---

#### Definition - 集合的勢

若有一個集合$A$，我們定義「集合的勢」為==集合內部的元素數量==，寫作$|A|$。

##### Example 1

$|\varnothing| = 0$

<br>

##### Example 2

令集合$S$為擁有所有字母的集合，則$|S| = 26$
<br>

##### Example 3

$|\{1, 2, 3\}| = 3$

<br>

##### Example 4

$|\{\varnothing\}|= 1$

<br>

##### Example 5

若$S$為所有整數的集合，則$|S|$為無限。

---

#### Introduce - 冪集

若存在一個集合 ==有集合$A$的所有子集==，我們寫作$\wp(A)$。

如果集合$A$有$N$個元素，則$|\wp(A)| = 2^N$。

##### Example

若$A=\{a, b\}$，則$\wp(A) = \{\{\varnothing\}, \{a\}, \{b\}, \{a, b\}\}$

---

#### Introduce - 多元組

- 一個有序且長度為$n$的多元組包含了元素$(a_1, a_2, a_3, ... a_n)$，且$a_1$是第一個元素，$a_n$是最後一個元素。

- 兩個長度為$n$的多元組$A, B$，我們先用$A_i$表示多元組$A$的第$i$個元素。

若兩個多元組的每一項都相同，也就是$A_1 = B_1, A_2 = B_2, ... ,A_n = B_n$，則兩個多元組就是相同的。

- 長度為$2$的多元組我們稱作有序對。
- 若有兩個有序對$(a, b)$與$(c, d)$，則若$a = c$且$b = d$，則兩個有序對才相同。

##### Example

若有兩個長度為$n$的多元組$A, B$。

$A = (1, 2, 3, 4, 5)$，$B = (5, 4, 3, 2, 1)$，則$A \neq B$

$A = (1, 2, 3, 4, 5)$，$B = (1, 2 ,3, 4)$，則$A \neq B$

$A = (1, 2, 3, 4, 5)$，$B = (1, 2 ,3, 4, 5)$，則$A = B$

---

#### Introduce - 笛卡兒積

兩個==集合$A, B$相乘==，我們稱作==笛卡爾積==，寫作$A \times B$。

$A \times B$是一個集合，包含了所有不同的有序對$(a, b)$，其中$a \in A$，$b \in B$

我們可以寫成這樣：$A \times B = \{(a, b) | a \in A \land b \in B\}$

<br>

##### Example

若集合$A = \{a, b\}$，集合$B = \{1, 2\}$

則$A \times B = \{(a, 1), (a, 2), (b, 1), (b, 2)\}$

---

#### Introduce - 笛卡兒積的子集合

在笛卡爾積的子集合$R$，我們可以說與集合$A$和集合$B$都有關係。

---

#### Introduce - 多個集合的笛卡兒積

若我們有$m$個集合$A_1, A_2, A_3, ..., A_M$，則笛卡爾積寫作$A_1 \times A_2 \times ...\times A_M$。

則$A_1 \times A_2 \times ...\times A_M = (a_1, a_2, ... ,a_n)$，為一個有序多元組的集合，其中$a_i \in A_i, i = 1, 2, ..., n$。

##### Example

若$A = \{0, 1\}$，$B = \{1, 2\}$，$C = \{0, 1, 2\}$，求$A \times B \times C$

$A × B × C = \{(0,1,0), (0,1,1), (0,1,2),(0,2,0), (0,2,1), (0,2,2),(1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2)\}$

---

==#### Introduce - 量詞的真值集==

給定一個量詞$P$與定義域$D$，我們定義量詞$P$的真值集為所有使得$P$為true且在定義域$D$的元素。

我們可以把真值集寫作$\{x \in D | P(x)\}$。

##### Example

給定定義域$D$為所有整數與$P(x)$為$|x| = 1$，找出$P(x)$的真值集。

則$P(x)$的真值集為$\{-1, 1\}$。

---

### 2.2 集合運算子

#### Introduce - 聯集

$A$與$B$為集合，若$A$與$B$取聯集，則我們可以表示成$A \cup B = \{x | x \in A \lor x \in B\}$。


##### Example

若$A = \{1, 2, 3\}$，且$B = \{3, 4, 5\}$，則$A \cup B = \{1, 2, 3, 4, 5\}$

---

#### Introduce - 交集

$A$與$B$為集合，若$A$與$B$取交集，則我們可以表示成$A \cap B = \{x | x \in A \land x \in B\}$


如果$A \cap B = \varnothing$，則$A$與$B$的關係為互斥的。

<br>

##### Example 1

若$A = \{1, 2, 3\}$，且$B = \{3, 4, 5\}$，則$A \cap B = \{3\}$

<br>

##### Example 2

若$A = \{1, 2, 3\}$，且$B = \{4, 5, 6\}$，則$A \cap B = \varnothing$

---

#### Introduce - 補集

令$A$是一個集合，則$A$的補集(通常叫做宇集$U$)，==寫作$\overline{A}$==，為$U - \overline{A}$的集合。

定義為$\overline{A} = \{x \in U | x \not \in A\}$

$A$的補集有時表示成$A^c$。

##### Example

如果宇集$U$代表小於$100$的正整數，則求$\{x | x > 70\}$的補集。

$\{x | x \le 70\}$


---

####

#### Introduce - 差集

令$A$與$B$為一個集合。

$A$與$B$的差集，可以表示成$A - B$，代表==集合$A$不包含集合$B$的東西==。

可以被定義為$A - B = \{x | x \in A \land x \not \in B\} = A \cap \overline{B}$

##### Example

令$A = \{1, 2, 3\}$，$B = \{3, 4, 5\}$，求$A - B$

$A - B = \{1, 2\}$

---

#### Introduce - 兩個集合交集的勢

利用排容原理。

$|A \cup B| = |A| + |B| - |A \cap B|$

##### Example

令$A = \{1, 2, 3\}$，$B = \{3, 4, 5\}$，求$|A \cup B|$

$|A \cup B| = |A| + |B| - |A \cap B| = |3| + |3| - |5| = 1$

---

#### Introduce - 對稱差

若有兩個集合$A$與$B$，則$A$與$B$的對稱差寫作$A \oplus B$。

定義為$A \oplus B = (A-B) \cup (B-A)$

##### Example

若$U = \{0, 1 ,2, 3, 4, 5, 6, 7, 8, 9\}$，$A = \{1, 2, 3, 4, 5\}$，$B = \{3, 4, 5, 6, 7\}$，求$A \oplus B$

$A \oplus B = (A - B) \cup (B - A) = \{1, 2\} \cup \{6, 7\} = \{1, 2, 6, 7\}$

---

#### Introduce - 集合特徵

- 恆等律
- $A \cup \varnothing = A$，$A \cap U = A$
- 支配律
- $A \cup U = U$，$A \cap \varnothing = \varnothing$
- 冪等律
- $A \cup A = A$，$A \cap A = A$
- 補餘律
- $\overline{(\overline{A})} = A$
- 交換律
- $A \cup B = B \cup A$，$A \cap B = B \cap A$
- 連鎖律
- $A \cup (B \cup C) = (A \cup B) \cup C$
- $A \cap (B \cap C) = (A \cap B) \cap C$
- 分配律
- $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
- $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
- 德摩根定律
- $\overline{A \cup B} = \overline{A} \cap \overline{B}$，$\overline{A \cap B} = \overline{A} \cup \overline{B}$
- 吸收律
- $A \cap (A \cup B) = A$，$A \cap (A \cup B) = A$
- ==Complement laws補充法律==
- $A \cup \overline{A} = U$，$A \cap \overline{A} = \varnothing$

---

### 2.3 函數

#### Definition - 函數

令$A$與$B$為一個非空集合，一個函數從$A$映射$B$，寫作$A \rightarrow B$。

代表==每一個集合$A$的元素都剛好指向一個集合$B$的元素==，寫作$f(a) = b$。

其中$b$為集合$B$的相異元素，被集合$A$的元素所映射。

---

==#### Introduce - 笛卡耳積的函數==

一個 $A \rightarrow B$ 可以用來表示 $A \times B$ 的子集合，這個子集合是一個函數 $f$，其數學表達為：

$$
\forall x \in A, \exists y \in B \, ((x, y) \in f)
$$

這表示對於所有來自集合 $A$ 的元素 $x$，存在至少一個來自集合 $B$ 的元素 $y$，使得有序對 $(x, y)$ 屬於集合 $f$。

此外，為了確保函數的唯一性：

$$
\forall x \in A, \forall y_1, y_2 \in B \, ([(x, y_1) \in f \land (x, y_2) \in f] \rightarrow y_1 = y_2)
$$

這表示如果某個元素 $x$ 透過函數 $f$ 同時與 $B$ 中的兩個元素 $y_1$ 和 $y_2$ 相關聯，則這兩個元素 $y_1$ 和 $y_2$ 必須相等，確保每個 $x$ 只對應一個 $y$。

---

#### Introduce - 映射、像與原像

給你一個集合$A$與集合$B$，我們說$f$是由$A$映射$B$所組成，則

$A$被稱為$f$的定義域

$B$被稱為$f$的值域

如果$f(a) = b$，==則$b$被稱為$f$在$a$的像==，==$a$被稱為$b$的像原==

當兩個函數有相同的定義域，相同的域值，還有兩個函數的像與像原映射相同，則兩個函數相同。

---

#### Introduce - 單射

函數$f$被稱做==一對一函數==，或者稱做==單射==，也就是對於所有在定義域的$a, b$，若且唯若$f(a) = f(b)$，則$a = b$。

函數$f$如果是一對一函數，則這個函數是個單射函數。

---

#### Introduce - 滿射

若有兩集合$A, B$，若且唯若所有元素$b \in B$，存在一個$a \in A$，使得$f(a) = b$，則稱做這個函數為滿射函數。


---

#### Introduce - 對射

若一個函數是一對一函數，且函數滿射，則我們稱作這個函數是一對一對應函數或叫做對射函數。

---

#### Introduce - 反函數

令$f$是一個集合$A$對集合$B$的對射函數，$f$的反函數寫作$f^{-1}$。

反函數$f^{-1}$代表集合$B$對集合$A$的函數，定義為若且唯若$f^{-1}(y) = x$則$f(x) = y$。

---

#### Introduce - 複合函數

令$f$為集合$B$對集合$C$的函數，且$g$為集合$A$對集合$B$的函數，$f$與$g$的複合函數，寫作$f \circ g$，代表一個集合$A$對集合$C$的函數，定義為$(f \circ g)(x) = f(g(x))$。

---

#### Introduce - 函數的圖形

令$f$為一個集合$A$對集合$B$函數，函數$f$的圖形即為每一對的$(a, b)$，即為

$\{(a, b) | a \in A \land f(a) = b\}$

---

#### Introduce - 一些重要的函數

==底函數代表將小於等於$x$之最大整數指派給實數$x$，記為$\lfloor x \rfloor$==

頂函數代表將大於等於$x$之最小整數指派給實數$x$，記為$\lfloor x \rfloor$

階乘函數$f: \mathbb{N} \rightarrow \mathbb{Z}^+$，記為$f(n) = n! = 1 \times 2 \times .... \times n$，其中$n \in \mathbb{Z}^+$。

##### Table - 頂函數與升函數


#### Introduce - 部分函數

令$f$為一個集合$A$對集合$B$函數。

若$f$的定義域$D(f) \subseteq A$，且$f$的值域$R(f) \subseteq B$，則我們稱$f$為一部分函數。

---

### 2.4 數列與總和

#### Definition - 序列

- 序列是有序的表列，例如$1, 3, 5, 7, 9$，或者$1, 4, 9, 16, 25$。
- 序列是一個整數子集的函數。
- 我們使用符號$\{a_n\}$來描述序列。

##### Example

考慮序列$a_n$，其中$a_n = \dfrac{1}{n}$

由$a_1$開始，可記為$a_1, a_2, a_3, a_4, ...$

前幾項為$1, \dfrac{1}{2}, \dfrac{1}{3}, \dfrac{1}{4}...$

---

#### Introduce - 幾何數列

一個幾何數列可以表示成：$a, ar, ar^2, ar^3, ... ,ar^n$，其中$a$為首項，$r$為公比。

##### Example

若有一序列$a_n = (-1)^n$，則我們說這==是一個幾何數列==，因為$a_n$的前幾項為$1, -1, 1, -1 ...$，即為$a=1$，$r = -1$。

---

#### Introduce - 算術數列

一個算術數列可以表示成：$a, a+d, a+2d, a+3d, ..., a+nd$，其中$a$為首項，$d$為公差

##### Example

若有一序列$a_n = 1 + 3n$，則我們說這是一個算術數列，因為$a_n$的前幾項為$1, 4, 7, 10...$，即為$a = 1$，$r = 3$。

---

#### Definition - 字串

- 字串為有限字元數所組成的序列。
- 一個不含任何項的字串稱作空字串。

---

#### Introduce - 遞迴關係式

遞迴關係，也就是差分方程式，是一種遞推地定義一個序列的方程式：序列的每一項目是定義為前一項的函數。

##### Example - 斐波納契數列

一個Fibonacci Sequence可以由以下的性質定義

$F_0 = 0$

$F_1 = 1$

$F_n = F_{n-2} + F_{n-1}$

因此，斐波納契數列的序列為

$\{0, 1, 1, 2, 3, 5, 8, 13, 21 ...\}$

---

### 2.5 集合的勢

#### Definition - 勢

- 令A與B為兩個集合，若且唯若A與B對射，則集合A與集合B的勢是相同的，寫作$|A| = |B|$。

- 令A與B為兩個集合，若且唯若A與B==單射==，則集合A的勢小於等於集合B的勢，寫作$|A| \le |B|$。

如果集合A的勢與集合B的勢不同，則$|A| < |B|$。

- 一個==集合==如果是==有限的==，或者==與正整數集合的勢相同==，則我們說這個==集合是可數的==，否則就是不可數的。

例如一個實數集合是個不可數的集合。

- 如果一個無限的集合是可數的，他的勢為$ℵ_0$，寫作$|S| = ℵ_0$，且唸做"aleph null"。

- 一個無限集合的勢，若且唯若可以將所有的元素列成一個數列，則我們說這個無限集合的勢是可數的。

原因是一個無限集合的勢，可以寫作一個對射函數，且函數的index是正整數，故我們可以寫成這樣的形式：

$f(1) = a_1, f(2) = a_2, ... f(n) = a_n$

故根據「一個集合如果是有限的，或者與正整數集合的勢相同，則我們說這個集合是可數的」，我們可以知道無限集合的勢，若且唯若可以將所有的元素列成一個數列，則我們說這個集合是無限的。

---

#### Introduce - 希爾伯特旅館悖論

一個有無限間房間的旅館，每一個房間均住滿人，我們要怎麼樣能夠再容納一個旅客？

假設我們有無限多個客人，我們將每個客人$j$編號成$a_j$，新的客人我們表示成$a_0$，則我們可以寫成這樣的形式

$f(1) = a_1, f(2) = a_2, f(3) = a_3, f(4) = a_4, ..., f(n) = a_n, ...$

我們可以將第$i$房的人，請他移駕至第$i+1$房，這樣就會使第一間房間空出來。

$g(1) = a_0, g(2) = a_1, g(3) = a_2, g(4) = a_3,..., g(n) = a_{n-1}, ...$

可以顯而易見的知道這樣分配不會使房間編號撞號。

---

##### Example - 證明集合是可數的(1)

證明正偶數整數集合$E$是可數的。

令$f(x) = 2x$，則我們可以將其列成序列，也就是

$f(1) = 2, f(2) = 4, f(3) = 6, f(4) = 8, ..., f(n) = 2n$

我們可以證明這個函數是對射，假設$t$為偶正整數，則它可以寫成$2k$的形式，故每一個$t$存在唯一一個$k$，使得$f(k) = t$

我們可以證明這個函數是一對一函數，假設存在$f(n) = f(m)$，必定存在$2n = 2m$，也就是存在$n = m$

故若$n = m$，才能使得$f(n) = f(m)$

根據勢的定義，「一個無限集合的勢，若且唯若可以將所有的元素列成一個數列，則我們說這個無限集合的勢是可數的。」

因此$f(x) = 2x$是可數的。

##### Example - 證明集合是可數的(2)

證明整數集合$Z$是可數的。

將集合$Z$列成：$0, 1, -1, 2, -2, 3, -3 ... $

我們可以寫成以下的部分函數：$f(x) = \left\{ \begin{array}\ f(x) = -(x-1)/2 & x \in \text{odd} \\ f(x) = x/2 & x \in \text{even} \end{array}\right.$