{%hackmd @RintarouTW/About %}

# Relation

## Cartesian Product

:::info
$$
A,B\in sets, R\in relation,\\
A\times B\iff\{(a,b)\in R\mid a\in A, b\in B\}\\
(a,b)\in R\iff aRb
$$
:::

## Composition of Relations

:::info
$$
A,B,C\in sets, r,s\in relation\\
\cases{
r= \{(a,b)\mid a\in A, b\in B\}\\
s= \{(b,c)\mid b\in B, c\in c\}\\
}\\
\implies rs=\{(a,c)\mid \exists a\in A,b\in B, c\in C, (a,b)\in r\land (b,c)\in s \}\\
\iff rs=\{(a,c)\in A\times C\}
$$
:::

## Digraph

:::info
Ordered set of Relation(arrow)
$$
aRb\neq bRa
$$

digraph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
a->b
}

digraph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=BT;
b->a
}

:::

**Embedding of a graph**
:::info
The position of the vertices
:::

## Relations

$A$ is a set, $r$ is the relation on $A$,
**Reflexive Relation**
$$
\forall a\in A, ara
$$
**Symmetric Relation**
$$
\forall a,b\in A,a\neq b, arb\iff bra
$$
**Antisymmetric Relation**
$$
\forall a,b\in A,a\neq b, arb\implies b\not{r}a
$$
**Transitive Relation**
$$
\forall a,b,c\in A, arb\land brc\iff arc
$$

## Hasse(ordering) Diagram

graph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=BT;
0--"{1}","{2}"--"{1,2}"
}

- Reflexive : ex: $\{1\}\subset\{1\}$
- Antisymmetric : ex : $\{1\}\subset\{1,2\}\implies\{1,2\}\not\subset\{1\}$
- Transitive : ex: $(0\subset\{1\})\land(\{1\}\subset\{1,2\})\implies 0\subset\{1,2\}$

In Hasse digram, the order (level: bottom to top) matters.

## Partical Ordering Relation (Poset)

- Reflexive : $a\leq a$
- Antisymmetric : $a\leq b\implies b\nleq a$
- Transitive : $(a\leq b)\land (b\leq c)\implies a\leq c$

## Equivalence Relation

- Reflexive : $a=a$
- Symmetric : $a=b\implies b=a$
- Transitive : $(a=b)\land (b=c)\implies a=c$

:::info
Equivalence Class
$$
a,b\in A, r\in relation\ on\ A,c(a)=\{b\mid (a,b)\in r\}
$$
:::

Proof of Equivalenct Relation
$$
(a\leq b)\land(b\leq a)\iff a=b
$$

## Matrix of Relation

### Adjacency Matrix

digraph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=LR
1->1,2
2->3
3->3
}

$$
\cases{
A=\{1,2,3\}\\
r=\{(1,1),(1,2),(2,3),(3,3)\}
}\iff
R=\pmatrix{
1&1&0\\
0&0&1\\
0&0&1
}
$$

### Composition as Matrix Multiplication

$$r^2=r\times r=\{(1,1),(1,2),(1,3),(2,3),(3,3)\}\\
\Updownarrow\\
R^2=\pmatrix{1&1&0\\
0&0&1\\
0&0&1}\pmatrix{1&1&0\\
0&0&1\\
0&0&1}=\pmatrix{1&1&1\\
0&0&1\\
0&0&1}$$

digraph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=LR
1->1,2,3
2->3
3->3
}

## Closure Opeartion on Relation

### Transitive Closure

:::info
$r^+$ is a transitive closure of $r$ relation on $A$ that contains $r$ and is the smallest relation with all transitive relation of $r$.

$$
\cases{
|A|=n\\
r\in relation\ on\ A\\
}\\
\begin{array}l
r^+ &= r\cup r^2\cup \cdots\cup r^n\\
&= \bigcup_\limits{i=1}^n r^i
\end{array}
$$
:::

### Matrix of Transitive Closure

:::info
Let $R$ be the adjacency matrix of relation $r$ on a finite set $A$ where $|A|=n$,

$$
\begin{array}l
R^+ &= R+R^2+\cdots+R^n\\
&= R(I+R(I+R(\cdots)))
\end{array}
$$

$$
\begin{array}l
S_1&=R\\
S_1(I+S_1)&=R(I+R)\\
&=R+R^2=S_2\\
S_2(I+S_2)&=(R+R^2)(I+R+R^2)\\
&=(R+R^2)+(R^2+R^3)+(R^3+R^4)\\
&\because R^2+R^2=R^2\text{ while using boolean algebra in the adjacency matrix}\\
&=R+R^2+R^3+R^4\\
&=S_3\\
&\vdots
\end{array}\\
\therefore S_{k}=S_{k-1}(I+S_{k-1})=\bigcup_\limits{i=1}^{k^2} R^i
$$

When $|A|=n$, we only need $\lceil log_2 n\rceil$ matrix multiplication to calculate the $R^+$.
:::

###### tags: `math`