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.
Quasiorder
A relation $R$ on a set $A$ is called quasiorder if it is transitive and irreflexive.