# 2020-03-13 Intro. & Math Background
###### tags: `圖論`
[TOC]

{%youtube WtyiVHoixpk%}

### Set Definition
* $$ S = \{ x\in A:condition(x) \} $$

* X is **proper subset** of A (X是A的subset，但不等於A)
$$ X \subsetneq A $$

* **Partition** 定義:
$$ A_i \cap A_j = \emptyset\ \ \forall i \neq j \ \ , \ \bigcup_i A_i =A$$

* **symetric difference** of A and B : **AΔB**
* Note: A xor B $$ A \Delta B =(A \cup B) - (A \cap B) $$


* k-tuple $$ A^k = \{ (x_1,...,x_k): x_i \in A \} $$
$$When A=\{0,1\},A^k \ is \ the \ set \ of \ binary \ k-tuples. $$

### Quantifiers & Proofs

* **Universal** quantifier ∀ (For all ...)
$$ (\forall x \in S) P(x) $$

* **Existential** quantifier ∃ (For some ...)
$$(\exists x \in S) P(x)$$

* 英文對照參考

* **Negation** of quantified statements:
- $$\neg[(\forall x \in S) P(x)] \ same \ as \ (\exists x \in S) (\neg P(x)) $$
- $$\neg[(\exists x \in S) P(x)] \ same \ as \ (\forall x \in S) (\neg P(x)) $$

* Note: Quantifier 的順序會影響語句
* ∀x ∃y P: 無論x是哪一種，都存在「相對應的y」，使P為真
* ∃y ∀x P: 存在一個y，使得「任何x」都能使P為真

* logical definition

* $$ P \Rightarrow Q \ is \ (\neg P) \lor Q$$
* Note： 真值表

| | P | ¬P |
| :-----: |:--: |:--: |
| **Q** | 1 | 1 |
| **¬Q** | 0 | 1 |

* **Sufficient V.S. Necessary**
>[color=#ff0000]
>
>Sufficient:
>如果給定句子的真偽，要讓 Q 的 value 可以被評估的話
>至少 P 要是 true
>(P 是 true 時，「足以」近一步判斷 Q 值 與句子的真偽)
>
>Necessary:
>如果知道 P 是 true，那麼 Q 必須是 true，
>否則句子是 false
>
>[name=MathematiKai ] :+1: :100: :smile: :satisfied: :cry: :laughing:
>

* **Contrapositive**: 證明右邊成立，左邊自然而然也就成立
$$P \Rightarrow Q \ is \ \neg Q \Rightarrow \neg P$$

* **Contradiction**:

$$ \text{ Assume }Q\text{ is false. When } P\text{ is true, }Contradiction \text{(false) occurs}$$
$$ P \Rightarrow \neg Q (\Rightarrow\! \Leftarrow), \text{ thus, } P \Rightarrow Q \text{ must be true.}$$

### Induction


### Function
* **Injective**: one-to-one
* if x is different, then y is different
* **Surjective**: onto
* every y has at least 1 correspondent x
* **Bijective**: one-to-one & onto
* one-to-one correspondent

### Equivalence Relation

### Pigeonhole Principle
#### Lemma:
**kn objects is partintioned into n classes,
then some classes receive more than k objects**