Relation & Function
1. Relation
1-1. Partition and Covering of a set
$\pi = \{A_1, A_2, ... , A_m\}$ 일 때,
$A_i (1 \le i \le m)$이 S의 non-empty subset이고,
$\bigcup_{i=1}^m A_i = S$이면
set $\pi$를 covering of S라고 부른다. $A_1, A_2, ... , A_m$을 S를 cover라고 부른다.
만약 $\pi$의 element들이 서로 disjoint라면 $\pi$를 S의 partition이라고 부른다. $A_1, A_2, ... , A_m$을 S를 the blocks of the partition이라고 부른다.
1-2. Quotient Set
R이 equivalence relation on a set A이라면,
A/R = $\{[x]_R | x \in A\}$ 을 a quotient set of A modulo R이라고 부른다.
ex)
R을 {$(a, b) \ AND \ a, b \in \mathbb{Z} $| a mod 3 = b mod 3}이라고 할 때
$Z/R = {Z_0, Z_1, Z_2}$이다. 각각의 $Z_i$는 {3k+i | k $\in \mathbb{Z}$} 로 정의할 수 있다.
Z/R은 Z를 covering하고, 각각의 원소들은 disjoint이기 때문에 partition of Z이다.
Theorem 9
R이 equivalence relation일 때, A/R은 a patition of A이다.
1-3. Relation induced by the Partition
$\pi = \{A_1, A_2, ... , A_m\}$가 partition이라면,
$R_\pi$를 relation induced by the partition이라 부르고 아래를 만족한다.
$R_\pi = \{<x, y> | (x \in A_i) \land (y \in A_i)$ for some i $\}$
$<a, b> \in R_\pi$인 경우는 a, b가 같은 subset(block)에 있을 때만 성립한다.
Theorem 10
$\pi = \{A_1, A_2, ... , A_m\}$이 A의 partition이면 relation induced by the partition $R_\pi$는 A의 equivalence relation이다.
1-4. refinement
$\pi_1$과 $\pi_2$를 set A의 partition이라고 할 때,
Every Block $B_i$ in $\pi_2$, some $A_j$ in $\pi_1$에 대해 $B_j \subseteq A_i$일 때 $\pi_2$는 $\pi_1$의 refinement다.
Theorem 11
$\pi$ $\pi'$이 A의 비어있지 않은 두 partition일 때, $R_\pi' \subseteq R_\pi \Leftrightarrow \pi'$가 $\pi$의 refinement이다.
2. Partial Ordering
2-1. Definition
A relation R이 partial ordering이려면(iff) reflexive, antisymmetric, transitive해야 한다.
A set S가 partial ordering R가 함께 있는 것을 poset이라고 부르고 (S, R)으로 표기한다.
ex) $(\mathbb{Z}, \ge)$
2-2. Partially Ordered Sets
$\preceq$ 는 poset을 의미하는 notation으로 주로 쓰인다.
- notation $a \preceq b$는 $(a, b) \in \preceq$을 의미한다.
- poset $(S, \preceq)$의 element a, b는 $a \preceq b$ 또는 $b \preceq a$가 아닐 수도 있다.
2번의 케이스에서 무조건 $a \preceq b$ 또는 $b \preceq a$ 중 하나 이상을 만족하는 경우를 comparable,
$a \preceq b$ 또는 $b \preceq a$가 둘다 아닐 때 incomparable이라고 부른다.
Definition 17
만약 $(S, \preceq)$ 이 poset이고, 모든 pair에 대해 comparable하다면 $(S, \preceq)$을 totally ordered 또는 linearly ordered set, chain으로 부르고 $\preceq$을 a total order 또는 linear order라고 부른다.
2-3. Hasse Diagram
만약 G가 $(A, \preceq)$을 표시하는 digraph(a directed graph)이라고 한다면,
Hasse diagram of $(A, \preceq)$은,
1) G의 모든 loop가 사라지고
2) transitivity로 이어지는 arc들을 지우고
3) 모든 arrow를 위로 향하게 한 뒤 방향을 지우면
Hasse Diagram이 된다!
Definition 18
$x \preceq y$이지만 $x \preceq z \preceq y$를 만족시키는 z가 없는 (x, y)를 poset $(A, \preceq)$의 covering relation이라고 한다.
=> Hasse diagram은 이러한 covering relation을 이은 것
=> 전체 partial ordering에 대한 충분한 정보를 전해준다.
2-4. Greatest Elements and Least Elements
Definition 19
$(A, \preceq)$이 poset이고 $B \subseteq A$일 때,
1) $a \in B$는 greatest element of B $\Leftrightarrow$ $\forall a' \in B, a' \preceq a$
2) $a \in B$는 least element of B $\Leftrightarrow$ $\forall a' \in B, a \preceq a'$
Theorem 12
$(A, \preceq)$이 poset이고, $B \subseteq A$일 때, a와 b가 모두 greatest element of B일 때 a = b이다. greatest element는 unique하다.
2-5. lub(Least Upper Bound) and glb(Greatest Least Bound)
Definition 20
$(A, \preceq)$이 poset이고 $B \subseteq A$일 때,
1) $a \in A$는 upper bound for B $\Leftrightarrow$ $\forall a' \in B, a' \preceq a$
2) $a \in A$는 least upper bound of B $\Leftrightarrow$ a = upper bound and 모든 다른 upper bound a'에 대해 $a \preceq a'$일 때
Definition 21
$(A, \preceq)$이 poset이고 $B \subseteq A$일 때,
1) $a \in A$는 lower bound for B $\Leftrightarrow$ $\forall a' \in B, a \preceq a'$
2) $a \in A$는 greatest lower bound of B $\Leftrightarrow$ a = lower bound and 모든 다른 lower bound a'에 대해 $a' \preceq a$일 때
Theorem 13
$(A, \preceq)$이 poset이고 $B \subseteq A$일 때,
1) b가 B의 greatest element일 때, b는 B의 lub이다.
2) b가 B의 upper bound이고 $b \in B$이면, b는 B의 greatest element이다.
Theorem 14
$(A, \preceq)$이 poset이고 $B \subseteq A$일 때, 만약 B에 대한 lub 또는 glb가 존재한다면 이것은 unique하다.
(proof by contradiction)
만약 두개의 서로 다른 lub x, y가 존재한다고 한다면 정의에 의해 $x \preceq y$, $y \preceq x$ 이다.
하지만 antisymmetric의 정의에 의해
$x \neq y \Rightarrow \lnot(x \preceq y \land y \preceq x)$ 이다.
2-6. Lattice
Definition 22
모든 pair에 대해 lub와 glb를 가지고 있는 poset $<A, \preceq>$를 lattice라고 부른다.
이후 수업에서 자세히 다룰 예정!!