[Discrete Mathmatic cheat sheet] — From Set and Relation to Function

1. Set
2. Relation
3. Binary Relation
4. Eguvalence relation
5. Closure
6. Partial order、Total order、Well order
7. Function

Relation

令A、B:Set，則定義 R ⊆ A×B ，其中R:為relation 、×: 為卡式積。

Example

表示法

• Graph
• Relation matrix

Binary relation

若將上述Relation的定義改成，自己與自己作卡式積也就是 R ⊆ A×A，則稱
R為A上之一 binary relation。

Example

Note.
可以看出A上的Binary relation的個數 = 2^(n²)

以下介紹幾種重要的基本關係及其相關的關係

1. Reflexive (反身性): ∀ a ∈ A , a R a
2. Irreflexive (非反身性):∀ a ∈ A , a !R a
3. Symmetric(對稱性):∀ a,b ∈ A , a R b ⇒ b R a
4. Asymmetric (非對稱性):∀ a,b ∈ A , a R b ⇒ b !R a
5. Anit-symmetric (反對稱性):∀ a,b ∈ A , a R b且b R A⇒ a=b
6. Transitive (遞移性):∀ a,b,c ∈ A , a R b 且 b R c ⇒ a R c

Reflexive

是指具有反身性的基本關係。

所有在集合的元素都和自己有關係，∀ a ∈ A , a R a。反之，只要有一個元素和自己沒有關係便不滿足反身性。

可以透過使用矩陣表示法時，其對角線上的元素來思考是否具有反身性 :

如左圖所示，如果binary relation要滿足反身性，
則對角線的元素必須皆為1。

而其他元素則無限制，
0、1皆可。

Note.

Irreflexive

非反身性，是指所有在集合的元素都和自己沒關係，∀ a ∈ A , a !R a。反之，如果出現一個和自己有關係的元素，便不滿足非反身性。

以矩陣表示法思考，是指對角線上的元素皆為0，

Note.

Symmetric

指∀ a,b ∈ A , a R b ⇒ b R a。

考慮其個數，以矩陣表示法思考，分為兩個部分 :

1. 因為對角線的元素若要滿足對稱性，勢必得要滿足反身性 → 對角皆1
   (i.e反身性是對稱性的子集合)
2. 只有1+2+…+(n-1)對pair可以決定，而每對pair若要滿足對稱性，則有(0,0)、(1,1)兩種選擇 → 2^(n*(n-1))/2

Asymmetric 、Anti-symmetric

這兩個基本關係非常相似，所以一起說明。

先看定義:

Example

A={1,2,3},R={(1,2),(2,3)} …滿足asymmetic

A={1,2,3},R={(1,1),(1,2),(2,3)} …滿足anti-symmetic

所以最大的差別為對角線上的元素能不能為1，也就是反身性能不能存在?

再來，討論其個數，以矩陣表示法思考 :

Asymmetric
— 分為兩部分思考: 1.對角線、2.非對角線

1. 對角線元素在Asymmetric關係中是不能存在的，因此皆為0
2. 非對角線元素有1+2+…+(n-1)對pair可以決定，要滿足Asymmetric關係，只能是(0,0)、(0,1)、(1,0)

Anti-symmetric
— 將其視為"允許反身性的asymmetric關係"。

所以其個數為

Summarize Table

Eguvalence relation

滿足Reflexive、Symmetric、Transitive 這些關係者，我們稱為等價關係。

定義 [a] = {x |x R a}，a ∈ A 稱為a的等價類equvalence class。(同堆)

Closure

使其完成某一性質(reflexive、transitive…)的最小關係。

warshall algorithm & transitive closure

Partial order

若S:set ,S≠∅ ,R⊆SxS，而且S滿足Reflexive、Anti-symmetric、Rransitive。
則稱 S 為 Partial order relation ，以(S,R) 或是POSET、POS稱之。

常見Poset

1. (Z+,≤)
2. (Z+,|)
3. (P(x),⊆)

表示法 — Hasse diagram

先從Reflexive、Anti-symmetric、Rransitive這些關係中的圖形表示法思考 :

1. Reflexive : 自己到自己的loop
2. Anti-symmetric : 若有edge,只能單向,可有loop
3. Transitive : a →b,b →c就有a →c

Hasse diagram(漢斯圖)

是表達POSET的表示法，其步驟如下 :

1. 去掉reflesive的邊(loop)
2. 去掉transitive的邊
3. 假設有A →B，把A點置下、B點置上並把箭頭去掉。

Example.

S={1,2,3,4}、R={(1,1),(2,2),(3,3),(4,4),(1,2),(1,4),(1,3),(2,4),(3,4)}
畫出其Hasse diagram。

Total order

建立在Partial order的基礎下，若 ∀a≠b∈S,aRb且bRa 成立。白話一點來說就是"任意兩點皆可比較"的情況下。即稱為Total order relation、TOS
也以 "(S, ≤)" 記之。

TOS’s Hasse diagram

全序關係的漢斯圖表示法會是一條直線，稱為Chain。

也就是Topological order

Lattice

以下考慮一組POSET:(S,≤)

我們定義以下關係 :

• upper bound — a≤u、b≤u，則u為a,b之upper bound(上面)
• lower bound — a≥u、b≥u，則u為a,b之lower bound(下面)
• least upper bound — a,b最小的upper bound(a,b往上走第一次碰面的點)
• greaset lower bound — a,b最大的lower bound(a,b往下走第一次碰面點)
• greatest — 全域最大值(存在必唯一)、也就是山頂
• least — 全域最小值(存在必唯一)、也就是山谷
• maximal — 局部最大值
• least — 局部最小值

由以上定義，若是 ∀a,b∈S 其 lub(a,b)、glb(a,b)皆存在的話，即稱為lattice

常見Lattice

1. (Z+,≤) →(Z+,max,min)
2. (Z+,|)→(Z+,lcm,gcd)
3. (P(x),⊆)→(P(x), ∪,∩)

Function

定義 f ⊆ A×B ，滿足∀ a ∈ A , ∃! (唯一存在)b ∈ B , s.t. , a f b
稱 f 為 A 到 B之 function。

以 f : A → B 記之。
其中 a R b 表示 f(a)=b 。

example of function

白話文來說就是函數是一種滿足每一個在A集合的元素(a)都唯一存在一個
b (b ∈ B)，使得 a R b ，也就是 (a,b) ∈ f。

Note.

不可一對多
A要全部對出去

domain、codomain、range(image)

上述 f : A → B，稱A為 domain(定義域)、B 為codomain(對應域)。

我們將 所有A的元素所對應到B的元素蒐集起來，也就是
f(A)={f(a)| a ∈ A}，則稱f(A)為range(值域)、image of f

one-to-one、onto

1. one-to-one function
   若 a≠b ⇒ f(a) ≠ f(b) ，或是 f(a)=f(b) ⇒ a = b
   稱 f 為 1–1 function、injective function
2. onto function
   若 f(A) = B //把codomain全部元素對完
   i.e. ∀b∈ B , ∃ a ∈ A ,s.t. f(a) = b
   稱f 為 onto function、surjective function
3. bijective function (1–1 且 onto)
   若f滿足1–1且onto，稱f為bijective
   而且f為 "invertible"。

Example

• 嚴格遞增、嚴格遞減函數

inverse function

f : A → B，而且f:1-1且onto
則 f的"反關係"仍為function稱為inverse function，以 f^-1 記之

composed function

合成函數 ，若有f : A →B，g : B →C，我們可以合成f和g，如下 :

Theorem

Note.

Function 的計數

假設f :A →B ,|A|=m,|B|=n

我們有以下事實 :

1. 若f:1–1，m≤n (i.e. 大 →小,不1-1)
2. 若f:onto，m≥n(i.e. 小→大,不ono)
3. 若f:1–1且onto，m=n

Note.(f :A →B ,|A|=m,|B|=n)

1. f :為function的個數 : m^n
2. f :1–1 的個數 : P(m,n)
3. f :onto的個數 :

Finite 、Countable Set

若A、B:sets，我們想要去計算A、B的可數性以及有限性，因此我們定義

若存在一個function f : A →B ，而且f : 1–1 且onto ，則稱A和B有相同cardinality (基數) ，記做A~B。

Example.

[0,1]~[10,100]

可取f=90*x+10，f:1–1且onto，故其基數相同。

Finite set

A:set,若A=∅ 或是 ∃n ∈ Z+ 使得 A~{1,2,…,n}，稱A為finite set。
否則稱為infinite set。

Countable set

A:set,若A為finite set或是A~Z+，稱A為countable set。