# 離散第二章觀念整理

## 2-1關係
(1)關係之定義:
⇒A,B為一set,R⊆AxB,稱R為A至B之一relation<font color="red">(R為AxB之一子集)
</font>

(2)binary relation之定義:
⇒R⊆AxA

(3)R ⊆ AxB ⇔ R ∈ P(AxB)

(4)|A| = m ,|B| = n
R ∈ P(AxB) ⇒ |P(AxB)| = 2^mn^

(5)relation表示法分成兩種:
[1]圖形
[2]矩陣

(6)R的inverse之矩陣表示法 = R^T^

(7)
(R~1~ ∩ R~2~) ^-1^= R~1~^-1^ <font color="red">∩</font>R~2~^-1^
(R~1~ ∪ R~2~) ^-1^= R~1~^-1^ <font color="red">∪</font> R~2~^-1^

## 2-2基本關係
(1)R⊆AxA稱R為A上之binary relation
⇒R is relation on A

(2)reflexive
[1]具反身性⇔對角線全為1
[2]具非反身性⇔對角線全為0
<font color="red">可能存在不是非反身也不是非反身性之關係(兩者都不符合)</font>

(3)<font color="red">對稱性(symmetric)</font>

| | 對角線 | 若aRb是否bRa |定義|
| -------- | -------- | -------- |-------- |
|對稱性| 隨便 | 一端為1,另一端必為1 |∀a,b∈A 若aRb則bRa |
| 非對稱性| 整排一定是0 | 一端為1,另一端必為0 |∀a,b∈A 若aRb則b!Ra |
|反對稱性|隨便| 一端為1,另一端必為0|∀a,b∈A 若aRb且bRa則a=b並且∀a,b∈A 若a≠b則若aRb且b!Ra|

<font color="red">Ø具有三者symmetric性質</font>

(4)遞移性(transitive)
具遞移性 ⇔ ∀a,b,c∈A 若aRb ∩ bRa 則 aRc
R具transitive ⇔ R^2^ ⊆ R <font color="red">推廣⇒</font> R具transitive ⇔ R^n^ ⊆ R

(5)R,S ⊆ AxA
R∩S具reflexive,symmetric,transitive
R∪S具reflexive,symmetric,<font color="red">~~transitive~~</font>

## 2-3 等價關係 ⇒ 分割
(1)等價關係定義
⇒R⊆AxA 若R具有reflexive,symmetric,transitive稱R為A上之一equivalence relation

(2)關係包(equivalence class)之定義
⇒R⊆AxA為equivalence relation,a∈A
定義[a] = {x|xRa}稱為a之equivalance class<font color="red"> ⇒ 蒐集跟a有關的</font>

[lemma]
(3)R⊆AxA為equivalence relation,a,b∈A
若aRb ⇔ [a] = [b]

(4)分割(partition)定義
A~1~,...A~k~ ⊆ A滿足
[1]A~1~ ∪ A~2~ ∪...∪A~k~ = A
[2]A~i~ ∩ A~j~ = Ø ,∀i≠j
稱{A~1~,...,A~k~}形成A之一分割(partition)
也計做A~1~ ∪ A~2~ ∪...∪A~k~ <partition>
且稱A~1~ ~ A~k~為此種分割的k個block(可有多種分割法)

(5)<font color="red">一個equivalence relation就對應一種分割</font>

(6)<font color="red">等價關係就是分堆</font>

(7)在同一個block({})內為全關係(任兩者都有關係),而block及block間無關係(若有應當在同一block)

(8)求n個元素上之equivalance relation數量
⇒P~n~ = $\sum_{i=0}^{n-1}{n-1\choose i}
P~i~$
<font color="red">常考填空:P~0~ = 1,P~1~ = 1,P~2~ = 2,P~3~ = 5,P~4~ = 15,P~5~ = 52</font>

## 2-4關係之包
(1)XX closure(包)之定義
<font color="red">⇒包含R之最小XX關係 稱為XX closure</font>
r(*R*):包含R之最小反身關係,reflexive closure
s(*R*):包含R之最小對稱關係,symmetric closure
t(*R*):包含R之最小遞移關係,transitive closure
<font color="red">⇒t(s(r(*R*)))必為equivalence closure為包含R之最小等價關係</font>

(2)要解遞移包(transitive closure)⇒畫圖比較快

(3)relation越小,分得越細

(4)分的不細 ⇒ 一堆內element多 ⇒ ER為全關係⇒relation越大
等價包為包含R之「最小」等價關係 ⇒ 找分最細的

## 2-5函數
(1)函數之定義
f⊆AxB 滿足 ∀a∈A, ∃!b∈B使得afb
稱f為A到B之function
⇒代表定義域全對出去且單一對應的值唯一存在

(2)one-to-one定義
⇒若a~1~≠a~2~ ⇒ f(a~1~) ≠ f(a~2~)
⇒f(a~1~) = f(a~2~) ⇒ a~1~=a~2~
又稱<font color="red">injective</font>

(3)onto定義
⇒若f(A) = B⇒B的元素都被對完
又稱<font color="red">surjective</font>

(4)若1-1且onto
<font color="red">⇒稱invertible或bijection</font>

(5)f(A~1~∩A~2~) ⊆ f(A~1~)∩f(A~2~)
若f:1-1 ⇒ f(A~1~∩A~2~) = f(A~1~)∩f(A~2~)

(6)
f^-1^(B~1~∪B~2~) = f^-1^(B~1~)∪f^-1^(B~2~)
f^-1^(B~1~∩B~2~) = f^-1^(B~1~)∩f^-1^(B~2~)
<font color="red">⇒不會有B1,B2各一點送回相同點 這樣A->B是一對多</font>

(7)inverse function
f:1-1且onto ⇔ f之反關係仍為function 記作f^-1^

(8)合成
(gof)(a) = g(f(a))

(9)
(gof):1-1 ⇒<font color="red">只保證f 1-1</font>
(gof):onto ⇒<font color="red">只保證g onto</font>

## 2-6鴿籠原理
(1)定義
m隻鴿子,n個籠子,若m>n,則至少存在一個籠子含至少 ceiling($\dfrac{m}{n}$)隻鴿子 ⇒ 取比($\dfrac{m}{n}$)大之最小整數
<font color="red">⇒描述函式一對一,多對一且定義域(鴿子)都對出去</font>
<font color="green">*TIPS:Consider worst case</font>

## 2-7計數問題
(1)
f:A->B 1-1 ⇒ |A| < |B|
f:A->B onto ⇒ |A| > |B|
f:A->B 1-1,onto ⇒ |A| = |B|

(2)
f:A->B 1-1,onto ⇔ A~B ⇔ |A| = |B|

(3)證明A~B
[1]看如何數可以將B(對應域)全部都數到
[2]找對應的function可以1-1且onto

(4)**<font color="red"> finite set的定義:</font>**
[1]A是一集合
[2]A~{1,2,...,n}
⇔A可以被正整數所數完

(5)**<font color="red">countable set的定義:</font>**
[1]A是一集合
[2]A為finite set or A~Z^+^

(6)
f:A->Z^+^ 1-1 ⇒ A countable
pf⇒
利用(1)的定理可知
1-1 ⇒ |A| < |Z^+^| ⇒ A countable

(7)
A,B countable ⇒ AxB countable

(8)
(0,1) uncountable ⇒ 利用對角線論證法

(9)
uncountable - countable = uncountable

(10)
C ~ R^2^ ~ R

(11)
|Z^+^| = |Z| = |Q| < |U - Q (無理數)| = |R| = |C|

(12)
可數是同等級,不可數有等級之分
ex:|R| < |P(*R*)| > |P(P(*R*))|

(13)
當無限可數取powerset ⇒ 不可數

###### tags: `discrete math` `tips` `math` `chp2`