Relations and Functions

중간고사 이전 부분은 Set/Propositions, Permutation/Combination/Discrete probability이나 pass함

Relations and Funcitons

---

Intruduction

Cartesian product of A and set B, A x B : set of all ordered pairs (a,b) where $a \in A$ and $b \in B$

ex) {a, b} x {a, c, d} = {(a,a), (a,c), (a,d), (b,a), (b,c), (b,d)}

 

Binary relation from set A to set B :

- subset of A x B

- R is binary relation from A to B and if (a,b) $\in$ R, we say a is related to b

 

Representation of binary relatoin : set of ordered pair, tabluar form, graphical form

 

Let $R_1 and R_2$ be two binary relation from A to B, followings are also binary relation from A to B

- $R_1 \cap R_2$

- $R_1 \cup R_2$

- $R_1 \bigoplus R_2$

- $R_1 - R_2$

 

binary relation : relationship between pairs of objects

ternary relation : relationship among triples of objects

quaternary relation : relationship among quadruples of objects

n-ary relation : a subset of $((A_1\times A_2)\times A_3)\cdots\times A_n$

---

Relational Model for Data Bases

Let $A_1, A_2, \cdots , A_n$ be n sets

- a table : an n-ary relation among $A_1, A_2, \cdots , A_n$

- domains of table : $A_1, A_2, \cdots , A_n$

- degree of table : n

 

key : a uniquely identified domain for ordered n-tuple

composite key : use key as a combination of two or more domains

 

projection : Let R be a table of degree n. projection of R is m-ary relation($m<=n$)

- obtained from R by deleting n-m of components in each ordered n-tuple in R

- notation : $\pi_{i}, \pi_{i2}, \cdots , \pi_m$

join : combine two tables into one.

- Let R be a table of degree n and S be a table of degree m, $\tau_p (R\times S)$ of degree p($\leq n+m$)

- notation : $\tau_p(R\times S)$

---

Properties of Binary Relations

a binary relation on A : binary relation from A to A

Reflxive relation : $(a,a) \in R$ for every element a$\in$A

Symmetric relation : $(a,b) \in R$ implies that $(b,a) \in R$

Antisymmetric relation : $(a,b) \in R$ implies that $(b,a) \notin R$ except $a=b$

Transitive relation : $(a,b),(b,c) \in R$ implies that $(a,c) \in R$

 

$R_1$ : the transitive extension of R

$R^*$ : the transitive closure of R ( = $R_\infty$ )

---

Equivalence Relations and Partitions

Equivalence relation : reflexive, symmetric, transitive binary relation

partition of set A : nonempty subsets of A. ${A_1 ,A_2 ,\cdots ,A_k}$ whose intersection is $\phi$ and union is A

 

Equivalence classes : partitions induced by equivalence relation

 

Let two partitions of set $\pi_1 ,\pi_2$ and corresponding equivalence relations $R_1, R_2$

- $\pi_1$ is refinement of $\pi_2$ denoted $\pi_1\leq\pi_2$ if $R_1\subseteq R_2$

- product of $\pi_1$ and $\pi_2$, ($\pi_1 \cdot\pi_2$) : partition corresponding to equivalence relation $R_1\cap R_2$

- sum of $\pi_1$ and $\pi_2$, ($\pi_1 +\pi_2$) : partition corresponding to equivalence relation $(R_1\cup R_2)^*$

---

Partial Ordering Relations and Lattices

Partial ordering relation : reflexive, antisymmetric, transitive binary relation

- representation : tabluar, graphical, Hasse diagram(all edges represents to be pointing upward)

Partially ordered set(poset) : set A together with partial ordering relation R on A

- notation : $(A,R)$ or $(A,\leq )$

- For each ordered pair $(a,b)$ in R, we write $a\leq b$ instead of $(a,b)\in R$

Chain : Let $(A,\leq )$ be a poset. chain is subset of A if every two elements in subset are related

- ex) for chain ${a_1,a_2,\cdots ,a_k}$ have relation $a_{i_1}\leq a_{i_2} \leq \cdots \leq a_{i_k}$

Antichain : a subset of A if no two distinct elements in subset are related

Totally ordered set : a partially ordered set $(A,\leq )$ if A is a chain. In this case, $\leq$ is called total ordering relation

 

Let $(A,\leq )$ be a partially ordered set

- maximal element : element $a\in A$ if for no $b\in A$, $a\neq b$, $a\leq b$ e.g. j, k

- minimal element : element $a\in A$ if for no $b\in A$, $a\neq b$, $b\leq a$ e.g. a, b, e

- cover : element a is cover b if $b\leq a$ and no other element c, $b\leq c\leq a$ i.e. a is just above b e.g. f covers b and c

- upper bound : element c is an upper bound if $a\leq c$ and $b\leq c$

- least upper bound : element c is an least upper bound if there is no upper bound d of a and b, $d\leq c$

- lower bound : element c is an lower bound if $c\leq a$ and $c\leq a$

- greatest lower bound : element c is a greatest lower bound if there is no lower bound d of a and b, $c\leq d$

Lattice : a poset if every two elements in set have unique least upper bound and unique greatest lower bound

 

Let $(A,R_1)$ and $(B,R_2)$ be two posets. Define $R_3$ over the set $A\times B$

- For $a_1$, $a_2$ $\in A$ and $b_1$, $b_2$ $\in B$, $((a_1,b_1),(a_2,b_2))\in R_3$ if and only if $(a_1,a_2)\in R_1$ and $(b_1,b_2)\in R_2$

---

Chains and Antichains

Theorme 4.1

Let $(P,\leq )$ be a poset. Suppose the length of longest chains in P is n. The, the elements in P can be partitioned into n disjoint antichains

proof) by induction

i) induction basis : for n =1, no two elemebts in p are related.

ii) induction step : assume that theorem holds when the length of longest chains in poset is n-1

iii) Let P be a poset with length of logest chains being n. Let M denote the set of maximal element P

- consider now the poset $(P-M, \leq)$. M cannot contain two or more elements that are in the same chain.

  Consequently, the length of longest chain in P-M is n-1

 

Collary 4.1.1

- Let $(P,\leq )$ be a poset consisting of nm+1 elements. either there is an antichain consisting of m+1 elements or chain of length n+1 in P

proof) Suppose the length of longest chains in P is n. According to theorem 4.1, P can be partitioned into n disjoint antichains. If each antichains consists of m or fewer elements, total number of elements in P is at most nm, which are contradiction to assumption.

---

Functions and the Pigeonhole Principle

Function

- binary relation R from A to B if for every element $a\in A$, there is unique element $b\in B$ so that $(a,b)\in R$

- notation : $R(a)=b$ instead of $(a,b)\in R$

- A = domain, B = range

 

onto function (surjection) : every $b\in B$ is image of one or more elements of A

one-to-one function (injection) : no two elements of A have same image

one-to-one onto function (bijection) : both onto and one-to-one function

 

Pigeonhole Principle : Let D and R be finite sets. if |D|>|R|, then any function f from D to R, there exist $d_1,d_2\in D$ such that $f(d_1)=f(d_2)$

---

학교 강의를 토대로 개인 공부 목적으로 작성되어 오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.