# Basis 基礎
tags: `sets` `functions`
簡單介紹一下之後會用到的語言以及一些符號與概念，也就是集合與函數們。
- Sets
- <a >set axiom</a>
- <a>numbers</a>
- Functions
- <a>Def: ordered-pair</a>
- <a>Def: relation</a>
- <a>Def: descartes product</a>
- <a>Def: function</a>
- <a>Def: inj. , surj. , bij.</a>
- Thm: bij. and inverses
- Def: function composition
## Set axiom 集合公設
集合論有很多種，我們在國中小、高中學習到的基本上都是所謂的ZFC集合論。
集合論是甚麼呢?簡單來說就是利用公理去限制、構造出一個範疇使得我們可以在裡面討論很多定理而不會互相矛盾(也就是自洽)
接下來就是ZFC的正式公設:
:::success
1.外延公理: 兩個集合相等，若它們有相同的元素。
$$\forall A \forall B[\forall x(x \in A \Leftrightarrow x \in B) \Rightarrow A=B]$$

2.正規公理: 每個非空集合A都包含一個x，使得A和x不相交。
$$\forall A \ne \phi, \exists x \in A [x \cap A = \phi]$$

3.分類公理: 有個集合A，存在一個描述A的P，則存在A的子集包含滿足P的x
$$\forall A, \exists P(A),\exists B, \forall x: x \in B \Leftrightarrow x \in A \land P(x)$$

4.配對公理: 任兩個集合有共同的父集
$$\forall A \forall B\exists \mathbb{C} [A\in \mathbb{C}\land B\in \mathbb{C}]$$

5.聯集公理: 對於任何集合A有一個集合B，B的元素正是A的元素的元素。
$$\forall A\exists B, \forall x[ x \in B \Leftrightarrow \exists y(x \in y \land y \in A)]$$

6.替代公理: 一個集合在一個映射（泛函謂詞）下的像也是一個集合
$$(\forall x, \exists! y:P(x,y)) \Rightarrow (\forall A, \exists B, \forall y:P(x,y) \Leftrightarrow \exists x \in A :P(x,y))$$

7.無窮公理: 存在集合使得若x在裡面則x跟{x}的併也會在原集內
$$\exists \mathbb{N} [\phi \in \mathbb{N} \land\forall x \in \mathbb{N}[x \cup \{x\}\in \mathbb{N}]]$$

8.冪集公理: 對所有集合都有一個他的冪集的父集
$$\forall A\exists Z[\forall X \in \wp(A)[X \in Z]]$$

9.良序公理: 一個集合一定有一個全序關係，且他的所有真子集都良序
$$\forall A\exists R[R \ well-orders \ X]$$
然後值得注意的點是良序公理等價於選擇公理，也就是ZFC中的"C"
:::
然後如何定義一個集合的大小呢?
### 定義:基數
:::info
**Def: cardinality**
一個集合$A$的基數就是他元素的個數，記作$|A|$
而基數也可以對無窮集定義，這邊就先不提，之後會詳述
:::
簡單吧! 接下來我們就能有系統的繼續我們在ZFC中的邏輯推演了。
## Numbers 數域
數學上我們有很多數字，比如最熟悉的正整數、實數之類的，這些數字構成一個個的集合稱之為數域，各個數域間有一些包含與關聯性，甚至還有演變

#### 1. Natural number 自然數 $\mathbb{N}$
自然數包含0,以及所有的正整數
建構過程請參考<a href="https://zh.wikipedia.org/wiki/皮亞諾公理">皮亞諾公理</a>
簡單來說就是$0之後是1, 1$之後有後繼，然後之後每個數都有唯一的後繼，然後就造出來了
#### 2. Integer 整數 $\mathbb{Z}$
在加法定義之後，
讓$\forall n \in \mathbb{N}, \exists -n[n +(-n) =0]$
然後把$n, \ -n, \ 0$丟在一起就得到整數了
#### 3. Rational number 有理數 $\mathbb{Q}$
以$\mathbb{Z} \times (\mathbb{Z}- \{0\}) / \cong$ 建構$( \frac{a}{b} \cong \frac{c}{d} \Leftrightarrow ad=bc)$
#### 4. Real number 實數 $\mathbb{R}$
在微積分或分析導論中，我們都會學到如何建構實數，也就是在有理數(全序集)的基礎下我們對他進行<a href="https://zh.wikipedia.org/wiki/戴德金分割">戴德金分割</a>
這邊簡單說就是把有理數的一些「洞」填滿，比如$\sqrt{2}$就用$\{x|x^2-2 \geq 0 \land x>0,x \in \mathbb{Q}\}和\{x|x^2-2 < 0 \land x>0,x \in \mathbb{Q}\}$來定義
## Relations and Functions 關係與函數
### 定義:有序對
:::info
**Def: ordered-pair**
$$(a,b):= \{\{a\},\{a,b\}\}$$
$$(a,b,c):=\{\{a\},\{a,b\},\{a,b,c\}\}$$
and so on
:::
上面的定義讓我們能夠很簡單的不依靠標號而能表現出元素間的順序，而很重要的一點是有序對是「**有序的**」，所以$(a,b) \ne (b,a)$除非$a=b$
#### 小練習:
$(a,b),(c,d)$是兩組有序對，證明$$(a,b)=(c,d) \Leftrightarrow a=c \land b=d$$
### 定義:關係
:::info
**Def: relation**
一個關係$R$是蒐集一些有序對的集合
關係的Domain是蒐集$R$內有序對的第一項:
$$DomR:=\{x|(x,y) \in R\}$$
Range則是蒐集第二項:
$$RangeR:=\{y|(x,y) \in R\}$$
而如果$(x,y) \in R$我們也會寫成$xRy$
:::
### 定義:笛卡兒積
:::info
**Def: descartes product**
兩個集合$A,B$的笛卡兒積:
$$A \times B := \{(a,b)|a \in A \land b \in B\}$$
:::
所以由上面的定義可以簡單地發現$R = DomR \times RangeR$

---
我們在國中有學過函數的概念，所謂「給一個x，都有一個唯一的y對應，則y是x的函數」，
現在我們要以更嚴謹的語言表示
### 定義:函數(映射)
:::info
**Def: function**
一個關係$F$如果滿足:
$$\forall a\forall b\forall c[(a,b) \in F \land (a,c) \in F \Rightarrow b=c]$$
則稱$F$是一個函數(映射)
且若 $$DomF=X,\ RangeF=Y$$
我們會寫成$$F: X \rightarrow Y$$
此時在$F$裡的元素我們會寫成$(x,F(x)), y=F(x)$
特別的如果$\forall x, F(x)=x$ 那我們叫$F$恆等映射($Id_X$)
:::
而利用函數這種特殊的關係，我們可以建構出一個完整的範疇。
範疇是由物件和態射組成的結構，在上面的定義完善後我們得到的其實就是一個由
集合(物件類)+函數(態射)組成的範疇。(詳情請參閱<a href="https://en.wikipedia.org/wiki/category_theory">範疇論</a>)

接下來關於函數我們有一些特殊的性質與定義
### 定義:單、滿、雙射
:::info
給定一個函數$F: X \rightarrow Y$
**Def: injectivity**
$F$是單射的若且唯若:
$$\forall a,b \in X[F(a)=F(b) \Rightarrow a=b]$$
**Def: surjectivity**
$F$是滿射的若且唯若:
$$\forall y \in Y,\exists x \in X[F(x)=y]$$
**Def: bijectivity**
$F$是雙射的若且唯若$F$是單射且滿射的
而且有$\exists F \ bij. \Leftrightarrow |X|=|Y|$
此即為==康托爾-施奈德-伯恩斯坦定理==
:::
所以由上面雙射的概念我們就能看出「<font color="red" backgroundcolor="yellow">哪些無窮是相等的</font>」
例如: 正整數集$\mathbb{N}$跟有理數集$\mathbb{Q}$的基數都是$\aleph_0$，所以有理數是可數的。
雖然我們都知道這兩個集合都是無窮的。
直觀上來說我們可以看成$F_{bij}$是$X,Y$之間的完美對應。
#### 小練習:
證明:
(1) $|[0,1]| = |\mathbb{R}|$ (Hint: tan)
(2) $|[a,b]| = |\mathbb{R}|, \forall a,b \in \mathbb{R}$
(3) $|\mathbb{Q}| = |\mathbb{N}|$
<font color="red">(4) $|\mathbb{R}| = |\mathbb{R}^2|$</font> (Hint: peano)

---
接下來我們有個小定義+定理
### 定義: 反函數
:::info
**Def: inverse function**
給定函數$F: X \rightarrow Y , \ x \mapsto f(x)$
他的反函數
$$F^{-1} := \{ (y,x)| y \in Y, x \in X\}$$
而$Id_X^{-1} = Id_Y$
:::
不難注意到 $$(x,y) \in F \Leftrightarrow (y,x) \in F^{-1}$$
然而你會發現，有些$F$甚至不能良好的使$F^{-1}$形成一個函數，所以就有以下定理:
### 定理1.1.1
:::danger
$$給定F: X \rightarrow Y, 則F^{-1}是個函數若且唯若F是個雙射$$
:::
**Proof:**
$F^{-1}$是函數則代表$Y$中的每個元素都有$X$中的對應元素，且是唯一的
也就是 $\forall y \in Y, \exists! x\in X, \ \ x=F^{-1}(y)$
$$\equiv \ (\forall y \in Y, \exists x\in X[(y,x) \in F^{-1}]) \land (\forall(y_1,x_1),(y_2, x_2) \in F^{-1}[y_1=y_2 \Rightarrow x_1=x_2])$$
第一個條件聲明了$F$是滿射，因為$(y,x) \in F^{-1} \Leftrightarrow (x,y) \in F$，同樣的第二句也就是聲明$F$是單射
注意到這邊的推導都是雙向的，所以此命題成立 ${\square}$
### 定義: 複合函數
:::info
**Def: function composition**
給定兩個函數$F: R \rightarrow S, G: S \rightarrow T$
則複合函數$$G \circ F: R \rightarrow T\\x \mapsto G(F(x))$$
:::
#### 重要練習
$f: S \rightarrow T,$ 證明:$f$是雙射 $\Leftrightarrow \exists g: T \rightarrow S[f \circ g = Id_T \land g \circ f = Id_S]$
這個性質給了我們另一個強一點的條件:直接把反函數找出來，就可以確定雙射了