Review of Relation

Relation and Closure

$R$ is a relation on set $A$. If there exists a relation $S$ with property $P$ that includes $R$, and $S$ being a subset of all relations that has property $P$ and includes $R$, then $S$ is a closure of $R$ with respect to $P$.

Reflexive Closure

for set $A$.

$\Delta=\{(a,a)|a\in A\}$.

For any $R$ on $A$, its reflexive closure is $R\cup\Delta$

Symmetric Closure

for set $A$.

$R^{-1}=\{(b,a)|(a,b)\in R\}$.

For any $R$ on $A$, its symmetric closure is $R\cup R^{-1}$

Transitive Closure

Connectivity Relation: $R$ is a relation on $A$. A connectivity relation $R^*=\bigcup_{n=1}^{\infty}R^n$.

Let $R’$ be the transitive closure of R, then $R’=R^*$.

Hence, to get the transitive closure of $R$, we need to calculate $M_{R^*}=\vee_{i=1}^nM_R^{[i]}$. $M_R$ is a 0-1 Matrix of $R$, which defined on n elements.

Warshell Algorithm

Let $W_0=M_R$. $\forall k \in \{1,2,\cdots,n\}, W_k=[w_{ij}^{[k]}]$, $w_{ij}^{[k]}=w_{ij}^{[k-1]}\vee(w_{ik}^{[k-1]}\land w_{kj}^{[k-1]})$. $W_n=M_{R^*}$.

Partial Order

$(S,\preccurlyeq)$ is a linear order(total order) set $\iff$ $\forall a,b\in S$,$a\preccurlyeq b$ or $b\preccurlyeq a$. A total order set is also called a chain.

For partial order set $(S,\preccurlyeq)$, if $\preccurlyeq$ is a linear order, and every non-empty subset of $S$ has a minimum element, we call it a well ordered set.

Well-ordered Induction

$S$ is a well ordered set. $\forall y\in S$, if $P(x)$ is true for all $x\in S$ $\land$ $x\prec y$ leading to $P(y)$ is true, then $\forall x\in S, P(x)$ is true.


A relation $R$ on a set $A$ is called quasiorder if it is transitive and irreflexive.