Relations

Instructor

Li Hui

The concept of relations is universally present in the real world.

e.g., brother relations, classmate relations, colleague relations, ordering relations among numbers, inclusion relations among sets, etc.

Set theory provides a mathematical model for characterizing such relations: Relations.

A relation is also a set, with pairs of objects having the corresponding relation as its elements.

Ordered Pairs and Cartesian Products

Definition: A sequence consisting of two elements $x$ and $y$ with a given order is called an ordered pair, denoted ${\langle}x, y\rangle$. Here, $x$ is called the 1st element (component), and $y$ is called the 2nd element (component).

Example: In a Cartesian coordinate system, the coordinates $\langle x, y\rangle$ of a point on a 2D plane form an ordered pair.

The order is particularly emphasized here:

When $x\neq y$, $\langle x, y\rangle\neq\langle y, x\rangle$
The necessary and sufficient condition for $\langle x, y\rangle=\langle u, v\rangle$ is: $x=u, y=v$

Definition: A sequence consisting of 412$ elements , a_2, , a_n$ with a given order is called an ordered 412$-tuple. Denoted: $\langle a_1, a_2, \cdots, a_n\rangle$.

where $a_i$ is called the $i$-th component.

\[\langle a_1, a_2, \cdots, a_n\rangle=\langle b_1, b_2, \cdots, b_n\rangle\]

if and only if

\[a_i=b_i\, (i=1, 2, \cdots, n).\]

Definition: Let $A, B$ be any two sets. Ordered pairs are formed with elements of $A$ as the 1st component and elements of $B$ as the 2nd component.

The set of all such ordered pairs is called the Cartesian product of $A$ and $B$.

Formally: $A\times B=\{\langle x, y\rangle |x\in A, y\in B\}.$

Example: Let $A=\{a, b\}, B=\{0, 1, 2\}, C=\Phi$, then

\[A\times B=\{\langle a, 0\rangle, \langle a, 1\rangle, \langle a, 2\rangle, \langle b, 0\rangle, \langle b, 1\rangle, \langle b, 2\rangle\}\] \[B\times A=\{\langle 0, a\rangle, \langle 0, b\rangle, \langle 1, a\rangle, \langle 1, b\rangle, \langle 2, a\rangle, \langle 2, b\rangle\}\] \[A\times A=\{\langle a, a\rangle, \langle a, b\rangle, \langle b, a\rangle, \langle b, b\rangle\}\] \[B\times B=\{\langle 0, 0\rangle, \langle 0, 1\rangle, \langle 0, 2\rangle, \langle 1, 0\rangle, \langle 1, 1\rangle, \langle 1, 2\rangle, \langle 2, 0\rangle, \langle 2, 1\rangle, \langle 2, 2\rangle\}\] \[A\times C=\Phi\] \[C\times A=\Phi\]

Clearly, $A\times B\neq B\times A$, so the Cartesian product does not satisfy the commutative law.

Example: Suit $\times$ Rank:

\[\{(\spadesuit, A), (\spadesuit, K), (\spadesuit, Q), (\spadesuit, J), (\spadesuit, 10), \cdots, (\diamondsuit, 6), (\diamondsuit, 5), (\diamondsuit, 4), (\diamondsuit, 3), (\diamondsuit, 2)\}.\]

From combinatorics: If $|A|=m$, $|B|=n$, then $|A\times B|=mn$.

Definition: Let , A_2, , A_n$ be any given 412$ sets. If the 1st element of an ordered 412$-tuple $\langle a_1, a_2, \cdots, a_n\rangle$ is taken from $, the 2nd from $, $\cdots$, and the 412$-th from $, then the set of all such ordered 412$-tuples is called the Cartesian product of , A_2, , A_n$, denoted \times A_2\times\cdots\times A_n$. i.e., \[A_1\times A_2\times\cdots\times A_n=\{\langle a_1, a_2, \cdots, a_n\rangle |a_i\in A_i, i=1, 2, \cdots, n\}\]

Example: Let $A=\{1\}, B=\{a, b\}, C=\{x, y\}$, then:

\[A\times B=\{\langle 1, a\rangle, \langle 1, b\rangle\}\] \[B\times C=\{\langle a, x\rangle, \langle b, x\rangle, \langle a, y\rangle, \langle b, y\rangle\}\] \[(A\times B)\times C =\{\langle\langle 1, a\rangle, x\rangle, \langle\langle 1, a\rangle, y\rangle, \langle\langle 1, b\rangle, x\rangle, \langle\langle 1, b\rangle, y\rangle\} \] \[A\times (B\times C) =\{\langle 1, \langle a, x\rangle\rangle, \langle 1, \langle a, y\rangle\rangle, \langle 1, \langle b, x\rangle\rangle, \langle 1, \langle b, y\rangle\rangle\}\]

Clearly, the Cartesian product does not satisfy the associative law.

The following distributive laws hold:

$A\times (B\cup C)=(A\times B)\cup (A\times C)$
$A\times (B\cap C)=(A\times B)\cap (A\times C)$
$(A\cup B)\times C=(A\times C)\cup (B\times C)$
$(A\cap B)\times C=(A\times C)\cap (B\times C)$
$A\times (B-C)=(A\times B)-(A\times C)$
$(A-B)\times C=(A\times C)-(B\times C)$

If $C\neq\Phi$, then \[A\subseteq B\Leftrightarrow (A\times C\subseteq B\times C)\Leftrightarrow (C\times A\subseteq C\times B)\]

Let $A, B, C, D$ be four non-empty sets, then \[A\times B\subseteq C\times D\] if and only if \[A\subseteq C \wedge B\subseteq D.\]

Proof of distributive law: $A\times (B\cup C)=(A\times B)\cup (A\times C)$.

Proof: For any $\langle x, y\rangle$, if $\langle x, y\rangle\in A\times (B\cup C)$, then: \[x\in A\wedge y\in (B\cup C)\] \[x\in A\wedge (y\in B\vee y\in C)\] \[(x\in A\wedge y\in B)\vee (x\in A\wedge y\in C)\] \[\langle x, y\rangle\in A\times B\vee \langle x, y\rangle\in A\times C\] \[\langle x, y\rangle\in (A\times B)\cup (A\times C)\] Therefore $A\times (B\cup C)\subseteq(A\times B)\cup (A\times C)$

For any $\langle x, y\rangle$, if $\langle x, y\rangle\in (A\times B)\cup (A\times C)$, \[\langle x, y\rangle\in A\times B\vee \langle x, y\rangle\in A\times C\] \[(x\in A\wedge y\in B)\vee (x\in A\wedge y\in C)\] \[x\in A\wedge (y\in B\vee y\in C)\] \[x\in A\wedge y\in (B\cup C)\] \[\langle x, y\rangle\in A\times (B\cup C)\] Therefore $(A\times B)\cup (A\times C) \subseteq A\times (B\cup C)$

Combining both directions: \[A\times (B\cup C)=(A\times B)\cup (A\times C).\]

Example: Let $A, B, C$ be any three sets with $C\neq\Phi$, then $A\subseteq B$if and only if$A\times C\subseteq B\times C$.

Proof: (Necessity) Let $A\subseteq B$. For any $x\in A$, we have $x\in B$.

For any $\langle x, y\rangle$, if $\langle x, y\rangle\in A\times C$, then: \[x\in A\wedge y\in C\] \[x\in B\wedge y\in C\] \[\langle x, y\rangle\in B\times C\] Therefore \[A\times C\subseteq B\times C.\]

(Sufficiency) Let $A\times C\subseteq B\times C$.

Since $C\neq\Phi$, there exists $y\in C$. For any $x\in A$, we have \[x\in A\wedge y\in C\] \[\langle x, y\rangle\in A\times C\] \[\langle x, y\rangle\in B\times C\] \[x\in B\wedge y\in C\] \[x\in B\] Therefore $A\subseteq B$.

Therefore $A\subseteq B$if and only if$A\times C\subseteq B\times C$.

Relations and Their Representations

Definition of Relations

Definition: If all elements of a set are ordered pairs, the set is called a binary relation, denoted $R$.

Example: Let $A=\{2, 3, 4\}$, define: \[R_1=\{\langle x, y\rangle |x, y\in A \wedge x> y\}\] \[R_2=\{\langle x, y\rangle |x, y\in A \wedge x\geq y\}\] i.e.,: \[R_1=\{\langle 4, 3\rangle, \langle 4, 2\rangle, \langle 3, 2\rangle\}\] which represents the greater-than relation on $A$. \[R_2=\{\langle 4, 4\rangle, \langle 4, 3\rangle, \langle 4, 2\rangle, \langle 3, 3\rangle, \langle 3, 2\rangle, \langle 2, 2\rangle\}\] which represents the greater-than-or-equal-to relation on $A$.

Definition: Let $A, B$ be any two sets. Any subset of $A\times B$ defines a binary relation $R$ called a binary relation from $A$ to $B$.

When $A=B$, $R$ is called a binary relation on $A$.

Example: Let $A=\{1, 2, 3\}, B=\{a, b\}$, then \[A\times B=\{\langle 1, a\rangle, \langle 1, b\rangle, \langle 2, a\rangle, \langle 2, b\rangle, \langle 3, a\rangle, \langle 3, b\rangle \}\] Any subset of $A\times B$ is a relation. Such as: \[R_1=\{\langle 1, a\rangle, \langle 1, b\rangle \}\] \[R_2=\{\langle 1, a\rangle, \langle 2, a\rangle, \langle 3, b\rangle \}\] are all binary relations from $A$ to $B$.

In general, an $n$-ary relation can be defined on $n$ sets.

Definition: Let $A_1, A_2, \cdots, A_n$ be any given sets. Any subset $R$ of the Cartesian product $A_1\times A_2\times\cdots\times A_n$ is called an $n$-ary relation on $A_1, A_2, \cdots, A_n$.

When $A_1=A_2=\cdots=A_n=A$, $R$ is called an $n$-ary relation on $A$.

Example: Let $A, B$ be any two sets with $|A|=m, |B|=n$. How many distinct binary relations are there from $A$ to $B$?

Solution: Since any subset of the Cartesian product $A\times B$ is a binary relation from $A$ to $B$, and \[|A\times B|=m\times n\] \[|P(A\times B)|=2^{m\times n}\] there are $2^{m\times n}$ distinct binary relations from $A$ to $B$.

Example: Let $A=\{0, 1\}, B=\{2\}$ be two sets, then

\[A\times B=\{\langle 0, 2\rangle, \langle 1, 2\rangle\}\]

So $|A\times B|=2\times 1=2, |P(A\times B)|=2^2=4.$

There are 4 distinct binary relations from $A$ to $B$. Including: \[R_1=\Phi,\,\,R_2=\{\langle 0, 2\rangle\},\,\,R_3=\{\langle 1, 2\rangle\},\,\,R_4=\{\langle 0, 2\rangle, \langle 1, 2\rangle\}.\]

Example: Let $A=\{a, b, c\}$. How many binary relations can be defined on $A$?

512 binary relations can be defined on $A$.

Definition: Let $R$ be a binary relation from set $A$ to set $B$.

The set of all first components of ordered pairs in $R$ is called the domain of $R$, denoted $\text{dom}(R)$ (or $D(R)$).

The set of all second components of ordered pairs in $R$ is called the range of $R$, denoted $\text{ran}(R)$ (or $V(R)$). i.e.,: \[D(R)=\{x|x\in A\wedge\langle x, y\rangle\in R\}\] \[V(R)=\{y|y\in B\wedge\langle x, y\rangle\in R\}\] Clearly, $D(R)\subseteq A, V(R)\subseteq B$.

Example: Let $A=\{1, 2, 3, 4\}$. Find the less-than relation on $A$ and its domain and range.

Solution: The less-than relation: \[R=\{\langle 1, 2\rangle, \langle 1, 3\rangle, \langle 1, 4\rangle, \langle 2, 3\rangle, \langle 2, 4\rangle, \langle 3, 4\rangle\}, \]

\[D(R)=\{1, 2, 3\}, V(R)=\{2, 3, 4\}.\]

Example: Let $X=\{a, b, c, d, e, f\}$, with binary relation: \[R=\{\langle a, b\rangle, \langle c, d\rangle, \langle e, f\rangle\}, \] Find the domain and range of $R$.

Solution: $D(R)=\{a, c, e\}$, $V(R)=\{b, d, f\}.$

Some common binary relations: Let $A$ be any set, then:

$R_A=\Phi$, called the empty relation on $A$
$E_A=\{\langle x, y\rangle |x, y\in A\}$, called the universal relation on $A$
$I_A=\{\langle x, x\rangle |x\in A\}$, called the identity relation on $A$
$D_A=\{\langle x, y\rangle |x, y\in A\wedge x|y\}$, called the divisibility relation on $A$
$L_A=\{\langle x, y\rangle |x, y\in A\wedge x\leq y\}$, called the less-than-or-equal-to relation on $A$
$L_{A^\prime}=\{\langle x, y\rangle |x, y\in A\wedge x<y\}$, called the less-than relation on $A$

Example: Let $X=\{1, 2, 3\}$, $E_X=\{\langle 1, 1\rangle, \langle 1, 2\rangle, \langle 1, 3\rangle, \langle 2, 1\rangle, \langle 2, 2\rangle, \langle 2, 3\rangle, \langle 3, 1\rangle, \langle 3, 2\rangle, \langle 3, 3\rangle\}$ \[I_X=\{\langle 1, 1\rangle, \langle 2, 2\rangle, \langle 3, 3\rangle\},\,\,D_X=\{\langle 1, 1\rangle, \langle 1, 2\rangle, \langle 1, 3\rangle, \langle 2, 2\rangle, \langle 3, 3\rangle\}\] \[L_X=\{\langle 1, 1\rangle, \langle 1, 2\rangle, \langle 1, 3\rangle, \langle 2, 2\rangle, \langle 2, 3\rangle, \langle 3, 3\rangle\},\,\,L_{X^\prime}=\{\langle 1, 2\rangle, \langle 1, 3\rangle, \langle 2, 3\rangle\}\]

Relation Matrix

Definition: Let $X, Y$ be two finite sets, and let $R$ be a binary relation from $X$ to $Y$, where $X=\{x_1, x_2, \cdots, x_m\}, Y=\{y_1, y_2, \cdots, y_n\}$, then the relation matrix $M_R$ (or $M(R)$) of $R$ is an $m\times n$ matrix whose entries $m_{ij}$ are defined as: \[ m_{ij}= \begin{cases} 0 &\langle x_i, y_j\rangle\notin R\\ 1 &\langle x_i, y_j\rangle\in R \end{cases}\,\,\,\,\,1\le i\le m, 1\le j\le n\]

Example: Let $A=\{x_1, x_2, x_3, x_4\}$, $B=\{y_1, y_2, y_3\}$, with binary relation from $A$ to $B$: $R=\{\langle x_1, y_1\rangle, \langle x_1, y_3\rangle, \langle x_2, y_2\rangle, \langle x_2, y_3\rangle, \langle x_3, y_1\rangle, \langle x_4, y_1\rangle, \langle x_4, y_2\rangle\}$. Find the relation matrix $M_R$ of $R$.

\[M_R=\left( \begin{matrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 1 & 0 \end{matrix} \right) \]

Example: Let $A=\{x_1, x_1, x_3, x_4\}$, with binary relation on $A$: \[R=\{\langle x_1, x_1\rangle, \langle x_1, x_3\rangle, \langle x_2, x_3\rangle, \langle x_2, x_4\rangle, \langle x_3, x_1\rangle, \langle x_3, x_2\rangle, \langle x_4, x_4\rangle\}, \] Find the relation matrix $M_R$ of $R$.

\[M_R=\left( \begin{matrix} 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{matrix}\right) \]

Relation Digraph

Let $X=\{x_1, x_2, \cdots, x_m\}$, $Y=\{y_1, y_2, \cdots, y_n\}$ be two finite sets, and $R$ be a binary relation from $X$ to $Y$.

The relation digraph $G_R$ (or $G(R)$) of $R$ is a directed graph constructed as follows:

For each element $x_i$ in $X$, draw a small circle; for each element $y_j$ in $Y$, draw a small circle. Each small circle is called a node (vertex).
If $\langle x_i, y_j\rangle\in R$, draw a directed edge from node $x_i$ to node $y_j$. The node the arrow points to is called the terminal node, and the other endpoint is the initial node.

Example: Let $A=\{x_1, x_2, x_3, x_4\}$, $B=\{y_1, y_2, y_3\}$,

with binary relation from $A$ to $B$: \[R=\{\langle x_1, y_1\rangle, \langle x_1, y_3\rangle, \langle x_2, y_2\rangle, \langle x_2, y_3\rangle, \] \[\langle x_3, y_1\rangle, \langle x_4, y_1\rangle, \langle x_4, y_2\rangle\}, \] Find the relation digraph $G_R$ of $R$.

\[M_R=\left( \begin{matrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 1 & 0 \end{matrix}\right) \]

Example: Let $A=\{x_1, x_2, x_3, x_4\}$, with binary relation on $A$: \[R=\{\langle x_1, x_1\rangle, \langle x_1, x_3\rangle, \langle x_2, x_3\rangle, \langle x_2, x_4\rangle, \] \[\langle x_3, x_1\rangle, \langle x_3, x_2\rangle, \langle x_4, x_4\rangle\}, \] Find the relation digraph $G_R$ of $R$.

\[M_R=\left( \begin{matrix} 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{matrix}\right) \]

\[R=\{\langle x_1, x_1\rangle, \langle x_1, x_3\rangle, \langle x_2, x_3\rangle,\] \[\langle x_2, x_4\rangle, \langle x_3, x_1\rangle, \langle x_3, x_2\rangle, \langle x_4, x_4\rangle\}\]

Since $A=B$, the digraph can also be drawn using only the elements of $A$.

Example: Let $X=\{1, 2, 3\}$, $Y=\{a, b, c\}$, \[R=\{\langle 1, a\rangle, \langle 1, b\rangle, \langle 2, b\rangle, \langle 2, c\rangle, \]

\[\langle 3, a\rangle, \langle 3, c\rangle \}\]

Find the relation matrix and digraph of $R$.

Solution: The relation matrix of $R$ is:

\[M_R=\left( \begin{matrix} 1 & 1 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{matrix}\right) \]

Example: Let $A=B=\{a, b, c\}$, the binary relation from $A$ to $B$ is:

\[R=\{\langle a, b\rangle, \langle b, c\rangle, \langle a, c\rangle\}, \]

Draw the relation digraph of $R$.

Relations Operations

Inverse Relation

Definition: Let $R$ be a binary relation from set $X$ to set $Y$, $R=\{\langle a, b\rangle |a\in X\wedge b\in Y\},$

then

$R^{-1}=\{\langle b, a\rangle |\langle a, b\rangle\in R\}$

is called the inverse relation of $R$.

Clearly, $R^{-1}$ is a binary relation from $Y$ to $X$.

Example: Let $X=\{1, 2, 3, 4\}, Y=\{a, b, c\}$, $R$ is a binary relation from $X$ to $Y$, with $R=\{\langle 1, a\rangle, \langle 2, b\rangle, \langle 3, c\rangle, \langle 4, c\rangle\}$, Find $R^{-1}$

Solution: \[R^{-1}=\{\langle a, 1\rangle, \langle b, 2\rangle, \langle c, 3\rangle, \langle c, 4\rangle\}\]

Theorem: Let $R$ and $S$ be binary relations from set $X$ to set $Y$; $D(R)$ and $V(R)$ denote the domain and range of $R$; $\sim R=(X\times Y)-R$. The following identities hold:

$D(R^{-1})=V(R)$
$V(R^{-1})=D(R)$
$(R^{-1})^{-1}=R$
$(R\cup S)^{-1}=R^{-1}\cup S^{-1}$

$(R\cap S)^{-1}=R^{-1}\cap S^{-1}$
$(X\times Y)^{-1}=Y\times X$
$(\Phi)^{-1}=\Phi$
$R=S\Leftrightarrow R^{-1}=S^{-1}$
$R\subseteq S\Leftrightarrow R^{-1}\subseteq S^{-1}$
$(\sim R)^{-1}=\sim(R^{-1})$
$(R-S)^{-1}=R^{-1}-S^{-1}$

Prove: $(R\cap S)^{-1}=R^{-1}\cap S^{-1}$

Proof: For any $\langle y, x\rangle$,

if $\langle y, x\rangle\in (R\cap S)^{-1}$, then:

\[\langle x, y\rangle\in R\cap S\] \[\langle x, y\rangle\in R\wedge\langle x, y\rangle\in S\] \[\langle y, x\rangle\in R^{-1}\wedge\langle y, x\rangle\in S^{-1}\] \[\langle y, x\rangle\in R^{-1}\cap S^{-1}\] Therefore \[(R\cap S)^{-1} \subseteq R^{-1}\cap S^{-1}.\]

For any $\langle y, x\rangle$, if $\langle y, x\rangle\in R^{-1}\cap S^{-1}$, then:

\[\langle y, x\rangle\in R^{-1}\wedge\langle y, x\rangle\in S^{-1}\] \[\langle x, y\rangle\in R\wedge\langle x, y\rangle\in S\] \[\langle x, y\rangle\in R\cap S\] \[\langle y, x\rangle\in (R\cap S)^{-1}\]

Therefore \[R^{-1}\cap S^{-1}\subseteq (R\cap S)^{-1}\]

Hence \[(R\cap S)^{-1}=R^{-1}\cap S^{-1}.\]

Prove: \[(R-S)^{-1}=R^{-1}-S^{-1}.\]

Proof:

\[(R-S)^{-1}=(R\cap \sim S)^{-1}\] \[=R^{-1}\cap (\sim S)^{-1}\] \[=R^{-1}\cap \sim (S^{-1})\] \[=R^{-1} – S^{-1}\]

Therefore \[(R-S)^{-1}=R^{-1}–S^{-1}.\]

Let \[A=\{x_1, x_2, \cdots , x_m\}, \] \[B=\{y_1, y_2, \cdots , y_n\}, \]

$R$ is a binary relation from $A$ to $B$.

Then $R^{-1}$ is a binary relation from $B$ to $A$, and their relation matrices satisfy:

\[ M_R= \left( \begin{array}{rrrr} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array} \right) \] \[ M_{R^{-1}}= \left( \begin{array}{rrrr} a_{11} & a_{21} & \cdots & a_{m1} \\ a_{12} & a_{22} & \cdots & a_{m2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{mn} \end{array} \right) \] \[M_{R^{-1}}=(M_R)^T\]

Let \[A=\{x_1, x_2, \cdots , x_m\}, \] \[B=\{y_1, y_2, \cdots , y_n\}, \]

$R$ is a binary relation from $A$ to $B$, then $R^{-1}$ is a binary relation from $B$ to $A$, and their relation digraphs have the following relationship:

Example: Let $X=\{1, 2, 3\}$, $Y=\{a, b, c, d\}$, \[R=\{{\langle}1, a{\rangle}, {\langle}1, b{\rangle}, {\langle}2, c{\rangle}, {\langle}3, d{\rangle} \}\] Find the relation matrices and digraphs of $R$ and $R^{-1}$.

Solution: $R^{-1} =\{{\langle}a, 1{\rangle}, {\langle}b, 1{\rangle}, {\langle}c, 2{\rangle}, {\langle}d, 3{\rangle}\}$,

So the relation matrices and digraphs of $R$ and $R^{-1}$ are:

\[ M_R= \left( \begin{array}{rrrr} 1&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ \end{array} \right) \] \[ M_{R^{-1}}= \left( \begin{array}{rrr} 1&0&0\\ 1&0&0\\ 0&1&0\\ 0&0&1 \end{array} \right) \]

Composite Relation (Composition of Relations)

Definition: Let $R$ be a binary relation from set $X$ to set $Y$, and $S$ be a binary relation from set $Y$ to set $Z$.

The composite relation (composition) $R{\cdot}S$ of $R$ and $S$ is a binary relation from $X$ to $Z$, defined as: \[R{\cdot}S=\{{\langle}x, z{\rangle}|x{\in}X, z{\in}Z, \exists y{\in}Y, {\langle}x, y{\rangle}{\in}R∧{\langle}y, z{\rangle}{\in}S)\}\]

Example: Let $X=\{1, 2, 3\}$, $Y=\{a, b, c\}$, $Z=\{\alpha, \beta, \gamma\}$,

$R$ is a relation from $X$ to $Y$, $S$ is a relation from $Y$ to $Z$: \[R=\{{\langle}1, a{\rangle}, {\langle}2, b{\rangle}, {\langle}2, c{\rangle}\}\]

\[S=\{{\langle}a, \beta{\rangle}, {\langle}b, \alpha{\rangle}, {\langle}c, \gamma{\rangle}, {\langle}c, \beta{\rangle}\}\]

Find $R{\cdot}S$.

Solution: \[R{\cdot}S=\{{\langle}1, \beta{\rangle}, {\langle}2, \alpha{\rangle}, {\langle}2, \gamma{\rangle}, {\langle}2, \beta{\rangle}\}.\]

Example: Let $X=\{0, 1, 2, 3\}$, with binary relations on $X$: \[R=\{{\langle}i, j{\rangle}|j=i+1\, or\, i=2j\}, \] \[T=\{{\langle}i, j{\rangle}|i=j+2\}, \] Find $R{\cdot}T$ and $T{\cdot}R$.

Solution: \[R=\{{\langle}0, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}0, 0{\rangle}, {\langle}2, 1{\rangle}\}\] \[T=\{{\langle}2, 0{\rangle}, {\langle}3, 1{\rangle}\}\] \[R{\cdot}T=\{{\langle}1, 0{\rangle}, {\langle}2, 1{\rangle}\}\] \[T{\cdot}R=\{{\langle}2, 1{\rangle}, {\langle}2, 0{\rangle}, {\langle}3, 2{\rangle}\} \]

Example: Let $X=\{1, 2, 3, 4, 5\}$, $R$, $S$, $T$ are binary relations on $X$:

$R=\{{\langle}1, 2{\rangle}, {\langle}3, 4{\rangle}, {\langle}2, 2{\rangle}\},\,\,S=\{{\langle}4, 2{\rangle}, {\langle}2, 5{\rangle}, {\langle}3, 1{\rangle}, {\langle}1, 3{\rangle}\},\,\,T=\{{\langle}2, 3{\rangle}, {\langle}4, 1{\rangle}\}$

Find $R{\cdot}S$, $S{\cdot}R$, $(R{\cdot}S){\cdot}T$, $R{\cdot}(S{\cdot}T)$

Solution: \[R{\cdot}S=\{{\langle}1, 5{\rangle}, {\langle}3, 2{\rangle}, {\langle}2, 5{\rangle}\}\] \[S{\cdot}R=\{{\langle}4, 2{\rangle}, {\langle}3, 2{\rangle}, {\langle}1, 4{\rangle}\}\] \[(R{\cdot}S){\cdot}T =\{ {\langle}3, 3{\rangle} \}\] \[S{\cdot}T=\{ {\langle}4, 3{\rangle} \},\] \[R{\cdot}(S{\cdot}T)=\{ {\langle}3, 3{\rangle} \}\] \[R{\cdot}S {\neq} S{\cdot}R,\] \[(R{\cdot}S){\cdot}T =R{\cdot}(S{\cdot}T)\]

Relation digraph of composite relations:

Let:

$A=\{x_1, x_2, \cdots , x_m\}$,

$B=\{y_1, y_2, \cdots , y_n\}$,

$C=\{z_1, z_2, \cdots , z_p\}$,

$R$ is a binary relation from $A$ to $B$,

$S$ is a binary relation from $B$ to $C$,

then the relation digraph of $R\cdot S$ is constructed as follows:

For each element $x_i$ ($i=1, 2, \cdots , m$) in $A$, draw a node. Similarly, for each element $z_k$ ($k=1, 2, \cdots , p$) in $C$, draw a node. These form all nodes of the digraph $G_{R{\cdot}S}$.

In $G_{R{\cdot}S}$, draw a directed edge for each pair satisfying: if there is a directed edge from $x_i$ to $y_j$ in $G_{R}$, and a directed edge from $y_j$ to $z_k$ in $G_{S}$, then draw a directed edge from $x_i$ to $z_k$ in $G_{R{\cdot}S}$.

Example: Let $X=\{1, 2, 3\}$, $Y=\{a, b, c\}$, $Z=\{\alpha, \beta, \gamma\}$,

$R$ is a relation from $X$ to $Y$. $S$ is a relation from $Y$ to $Z$. \[R=\{{\langle}1, a{\rangle}, {\langle}2, b{\rangle}, {\langle}2, c{\rangle}\}\] \[S=\{{\langle}a, \beta{\rangle}, {\langle}b, \alpha{\rangle}, {\langle}c, \beta{\rangle}\}, {\langle}c, \gamma{\rangle}\] Find $G_{R{\cdot}S}$.

Solution: \[R{\cdot}S =\{{\langle}1, \beta{\rangle}, {\langle}2, \alpha{\rangle}, {\langle}2, \beta{\rangle}, {\langle}2, \gamma{\rangle}\}\] The relation digraph of composition $R{\cdot}S$:

Example: Let $X=\{1, 2, 3, 4\}$, and let $R$, $T$ be binary relations on $X$: \[R=\{{\langle}1, 2{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 4{\rangle}\}\] \[T=\{{\langle}1, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}3, 1{\rangle}, {\langle}4, 2{\rangle}\}\]

Find $G_{R{\cdot}T}$ and $G_{T{\cdot}R}$.

\[R{\cdot}T =\{{\langle}1, 4{\rangle}, {\langle}2, 4{\rangle}, {\langle}3, 2{\rangle}\}\]

\[T{\cdot}R =\{{\langle}1, 4{\rangle}, {\langle}3, 2{\rangle}, {\langle}4, 2{\rangle}\}\]

\[T\cdot R \neq R\cdot T\]

The relation matrix of a composition can also be computed via logical matrix multiplication.

Theorem: The relation matrix of a composite relation equals the logical product of the individual relation matrices.

Let: $A=\{x_1, x_2, \cdots , x_m\}$, $B=\{y_1, y_2, \cdots , y_n\}$, $C=\{z_1, z_2, \cdots , z_p\}$,

where $R$ is a binary relation from $A$ to $B$, and $S$ is a binary relation from $B$ to $C$. Then

$M_{R{\cdot}S}= M_R{\times}M_S$

\[ \left( \begin{array}{rrr} 0&1&1\\ 0&0&1\\ 1&0&1 \end{array} \right) \left( \begin{array}{rrr} 0&1&1\\ 1&0&1\\ 0&0&1 \end{array} \right) = \left( \begin{array}{rrr} 1&0&1\\ 0&0&1\\ 0&1&1 \end{array} \right) \]

Let $A$ be an $m{\times}n$ matrix:

\[\qquad\qquad A= \left( \begin{array}{rrrr} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array} \right) \] Let $B$ be an $n{\times}p$ matrix:

\[\qquad\qquad B= \left( \begin{array}{rrrr} a_{11} & a_{12} & \cdots & a_{1p} \\ a_{21} & a_{22} & \cdots & a_{2p} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{np} \end{array} \right) \]

Then the logical product $C=A{\times}B$ is defined as:

\[ C=A\times B= \left( \begin{array}{rrrr} a_{11} & a_{12} & \cdots & a_{1p} \\ a_{21} & a_{22} & \cdots & a_{2p} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mp} \end{array} \right) \] where \[ c_{ik}=\vee_{j=1}^n(a_{ij}\wedge b_{jk}) \] and $a_{ij}$, $b_{jk}$ take only values 0 or 1; the operations are logical operations.

Example: Let $X=\{1, 2, 3, 4, 5\}$, with relations on $X$: \[R=\{{\langle}1, 2{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 4{\rangle}\}, \] \[T=\{{\langle}1, 3{\rangle}, {\langle}2, 5{\rangle}, {\langle}3, 1{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 2{\rangle}\}, \] Find $M_{R{\cdot}T}$ and $M_{T{\cdot}R}$.

\[ M_R=\left( \begin{array}{rrrrr} 0&1&0&0&0\\ 0&1&0&0&0\\ 0&0&0&1&0\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{array} \right) \,\,\, M_T=\left( \begin{array}{rrrrr} 0&0&1&0&0\\ 0&0&0&0&1\\ 1&0&0&1&0\\ 0&1&0&0&0\\ 0&0&0&0&0 \end{array} \right) \]

\[ M_{R\cdot T}=\left( \begin{array}{rrrrr} 0&0&0&0&1\\ 0&0&0&0&1\\ 0&1&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{array} \right) \] \[ M_{T\cdot R}=\left( \begin{array}{rrrrr} 0&0&0&1&0\\ 0&0&0&0&0\\ 0&1&0&0&0\\ 0&1&0&0&0\\ 0&0&0&0&0 \end{array} \right) \]

From $M_{R{\cdot}T}$ and $M_{T{\cdot}R}$ we obtain

\[R{\cdot}T=\{{\langle}1, 5{\rangle}, {\langle}2, 5{\rangle}, {\langle}3, 2{\rangle}\}\]

\[T{\cdot}R=\{{\langle}1, 4{\rangle}, {\langle}3, 2{\rangle}, {\langle}4, 2{\rangle}\}\]

Properties of Composite Operations

Satisfies the associative law:

\[(R{\cdot}S){\cdot}P=R{\cdot}(S{\cdot}P)\]

Does not satisfy the commutative law:

\[R{\cdot}S\neq S{\cdot}R\]

Composition distributes over union:

\[R{\cdot}(S{\cup}P)=(R{\cdot}S){\cup}(R{\cdot}P),\,\,(S{\cup}P){\cdot}R =(S{\cdot}R){\cup}(P{\cdot}R)\]

Composition satisfies the following inclusion relation with respect to intersection:

\[R{\cdot}(S{\cap}P)\subseteq(R{\cdot}S){\cap}(R{\cdot}P),\,\,(S{\cap}P){\cdot}R\subseteq(S{\cdot}R){\cap}(P{\cdot}R)\]

Let $R$ be a relation from $X$ to $Y$, $I_x$ the identity relation on $X$, and $I_y$ the identity relation on $Y$. Then

\[I_x{\cdot}R=R{\cdot}I_y=R.\]

Proof of associativity: $(R{\cdot}S){\cdot}P=R{\cdot}(S{\cdot}P)$

Proof: For any ${\langle}x, w{\rangle}{\in}(R{\cdot}S){\cdot}P$, there exists $z{\in}Z$ such that ${\langle}x, z{\rangle}{\in}R{\cdot}S$ and ${\langle}z, w{\rangle}{\in}P$.

There also exists $y{\in}Y$ such that ${\langle}x, y{\rangle}{\in}R$ and ${\langle}y, z{\rangle}{\in}S$.

Since ${\langle}y, z{\rangle}{\in}S$ and ${\langle}z, w{\rangle}{\in}P$, we get ${\langle}y, w{\rangle}{\in}S{\cdot}P$.

Since ${\langle}x, y{\rangle}{\in}R$ and ${\langle}y, w{\rangle}{\in}S{\cdot}P$, we get ${\langle}x, w{\rangle}{\in}R{\cdot}(S{\cdot}P)$.

Hence $R{\cdot}(S{\cdot}P) \subseteq (R{\cdot}S){\cdot}P$.

Similarly, $(R{\cdot}S){\cdot}P \subseteq R{\cdot}(S{\cdot}P)$.

Therefore $(R{\cdot}S){\cdot}P = R{\cdot}(S{\cdot}P).$

Theorem: Let $R$ be a binary relation from $X$ to $Y$, and $S$ a binary relation from $Y$ to $Z$. Then \[(R{\cdot}S)^{-1}=S^{-1}{\cdot}R^{-1}\]

Proof: For any ${\langle}z, x{\rangle}$, if ${\langle}z, x{\rangle}{\in}(R{\cdot}S)^{-1}$,

then ${\langle}x, z{\rangle}{\in}(R{\cdot}S)$,

so there exists $y{\in}Y$ such that \[{\langle}x, y{\rangle}{\in}R{\wedge}{\langle}y, z{\rangle}{\in}S\] Thus:

\[{\langle}y, x{\rangle}{\in}R^{-1} {\wedge} {\langle}z, y{\rangle}{\in}S^{-1}.\]

We have ${\langle}z, y{\rangle}{\in}S^{-1}{\wedge}{\langle}y, x{\rangle}{\in}R^{-1}$,

so ${\langle}z, x{\rangle}{\in}S^{-1}{\cdot}R^{-1}$.

Therefore $(R{\cdot}S)^{-1} \subseteq S^{-1}{\cdot}R^{-1}$.

Similarly, $S^{-1}{\cdot}R^{-1} \subseteq (R{\cdot}S)^{-1}$.

Hence $(R{\cdot}S)^{-1}=S^{-1}{\cdot}R^{-1}.$

Power Operations

Definition: Let $R$ be a binary relation on set $A$, and let $n$ be a natural number. The $n$-th power of $R$, denoted $R^n$, is defined by

$R^0=I_A, \,\,R^{n+1}= R^n{\cdot}R$

From the definition, for any relation $R$ on set $A$, we have $R^0=I_A$ and $R^1=R$.

Example: Let $X=\{1, 2, 3\}$, with binary relation $R=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}$ on $X$. Find all powers of $R$.

Solution: \[R^0=I_x=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\] \[R^1=R=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}\] \[R^2=R{\cdot}R=\{{\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\] \[R^3=R^2{\cdot}R=\{{\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}{\cdot}\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle} \} =\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\} =R\]

\[R^4=R^3{\cdot}R=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}{\cdot}\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle} \}=\{{\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\} =R^2\]

\[R = R^3 =\cdots = R^{2n+1} = \{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}\] \[R^2 = R^4 =\cdots = R^{2n+2} = \{{\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

Example: Let $A=\{a, b, c, d\}$, with binary relation $R=\{{\langle}a, b{\rangle}, {\langle}b, a{\rangle}, {\langle}b, c{\rangle}, {\langle}c, d{\rangle}\}$ on $A$. Find all powers of $R$.

Solution: \[R^0=I_A=\{{\langle}a, a{\rangle}, {\langle}b, b{\rangle}, {\langle}c, c{\rangle}, {\langle}d, d{\rangle}\}\] \[R^1=R =\{{\langle}a, b{\rangle}, {\langle}b, a{\rangle}, {\langle}b, c{\rangle}, {\langle}c, d{\rangle}\}\] \[R^2=R{\cdot}R =\{{\langle}a, a{\rangle}, {\langle}a, c{\rangle}, {\langle}b, b{\rangle}, {\langle}b, d{\rangle}\}\] \[R^3=R^2{\cdot}R =\{{\langle}a, b{\rangle}, {\langle}a, d{\rangle}, {\langle}b, a{\rangle}, {\langle}b, c{\rangle}\}\]

\[R^4=R^3{\cdot}R =\{{\langle}a, a{\rangle}, {\langle}a, c{\rangle}, {\langle}b, b{\rangle}, {\langle}b, d{\rangle}\} =R^2\]

\[R^5=R^4{\cdot}R =\{{\langle}a, b{\rangle}, {\langle}a, d{\rangle}, {\langle}b, a{\rangle}, {\langle}b, c{\rangle}\} =R^3\]

\[ R^2 = R^{2n+2} = \{{\langle}a, b{\rangle}, {\langle}a, d{\rangle}, {\langle}b, a{\rangle}, {\langle}b, c{\rangle}\} \]

\[R^3 = R^{2n+1}= \{{\langle}a, b{\rangle}, {\langle}a, d{\rangle}, {\langle}b, a{\rangle}, {\langle}b, c{\rangle}\}\]

Theorem: Let $R$ be a binary relation on set $X$, and let $m, n{\in}N$. Then $R^m{\cdot}R^n = R^{m+n}$ and $(R^m)^n = R^{m\times n}$.

Properties of Relations

Definition: Let $R$ be a binary relation on set $X$. If for all $x{\in}X$ we have ${\langle}x, x{\rangle}{\in}R$, then $R$ is called a reflexive relation (reflexive).

Example: The inclusion relation “$\subseteq$” between sets, the less-than-or-equal relation “$\leq$” between numbers, and the “parallel” relation between lines are all reflexive relations.

Definition: Let $R$ be a binary relation on set $X$. If for all $x{\in}X$ we have ${\langle}x, x{\rangle}{\notin}R$, then $R$ is called an irreflexive relation (irreflexive).

Example: The proper inclusion relation “$\subset$” between sets and the strict less-than relation “$<$” between numbers.

Example: Let $X=\{1, 2, 3\}$. Determine whether each of the following binary relations on $X$ is reflexive or irreflexive: $E_x, I_x, D_x, L_x, L_ {x^\prime}, R=\{{\langle}1, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}.$

Solution: \[E_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 2{\rangle}, \] \[{\langle}2, 3{\rangle}, {\langle}3, 1{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

\[I_x=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

\[D_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

\[L_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}\}\]

\[L_{X^\prime}=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\]

\[R=\{{\langle}1, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\]

Reflection of reflexive/irreflexive relations in the relation digraph:

If $R$ is reflexive, every vertex in its digraph has a self-loop;
If $R$ is irreflexive, no vertex in its digraph has a self-loop;
If $R$ is neither reflexive nor irreflexive, some vertices have self-loops and some do not.

Example: Let $X=\{1, 2, 3\}$. Draw the relation digraph for each binary relation on $X$ below.

\[L_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}\}\]

\[L_X^\prime=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\]

\[R=\{{\langle}1, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\]

Reflection of reflexive/irreflexive relations in the relation matrix:

If $R$ is reflexive, all main diagonal entries of its relation matrix are 1;
If $R$ is irreflexive, all main diagonal entries of its relation matrix are 0;
If $R$ is neither reflexive nor irreflexive, the main diagonal contains both 0s and 1s.

Example: Let $X=\{1, 2, 3\}$. Find the relation matrix for each binary relation on $X$ below.

\[L_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}\},\,\,L_X^\prime=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\]

\[R=\{{\langle}1, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\] \[ L_x= \left( \begin{array}{ccc} 1&1&1\\ 0&1&1\\ 0&0&1 \end{array} \right) , \,\, L_{x^\prime}= \left( \begin{array}{ccc} 0&1&1\\ 0&0&1\\ 0&0&0 \end{array} \right) ,\,\, R= \left( \begin{array}{ccc} 1&0&1\\ 0&0&1\\ 0&0&0 \end{array} \right) \]

Theorem: Let $R$ be a binary relation on set $A$. Then:

$R$ is reflexive if and only if $I_A{\subset}R$.
$R$ is irreflexive if and only if $R{\cap}I_A={\Phi}$.

Theorem: Let $R_1$ and $R_2$ be binary relations on $A$. If $R_1$ and $R_2$ are reflexive, then:

$R_1^{-1}$, $R_1{\cup}R_2$, and $R_1{\cap}R_2$ are also reflexive.

Proof: Let $R_1$ be a reflexive relation on $A$. For any $x{\in}A$, ${\langle}x, x{\rangle}{\in}R_1$, so ${\langle}x, x{\rangle}{\in} R_1^{-1}$. Hence $R_1^{-1}$ is reflexive.

Let $R_1$ and $R_2$ be reflexive relations on $A$. For any $x{\in}A$, ${\langle}x, x{\rangle}{\in}R_1$ and ${\langle}x, x{\rangle}{\in}R_2$, so ${\langle}x, x{\rangle}{\in}R_1{\cup}R_2$; hence $R_1{\cup}R_2$ is reflexive.

Definition: Let $R$ be a binary relation on set $X$. If for all $x, y{\in}X$, whenever ${\langle}x, y{\rangle}{\in}R$ implies ${\langle}y, x{\rangle}{\in}R$, then $R$ is called a symmetric relation.

E.g., the equality relation “$=$” on numbers and the “similarity” relation on triangles.

Definition: Let $R$ be a binary relation on set $X$. If for all $x, y{\in}X$, whenever ${\langle}x, y{\rangle}{\in}R$ and ${\langle}y, x{\rangle}{\in}R$, it follows that $x=y$, then $R$ is called an antisymmetric relation.

E.g., the inclusion relation “${\subseteq}$” between sets and the less-than-or-equal relation “${\leq}$” between numbers.

Example: Let $X=\{1, 2, 3\}$, $R=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}$. Determine whether $R$ and the following binary relations on $X$ are symmetric or antisymmetric: $E_x, I_x, D_x, L_x, L_{x^\prime}, {\Phi}$.

\[D_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

\[L_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}\}\]

\[L_X^\prime=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\} \]

\[ {\Phi} =\{\}\]

\[R =\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}\] $R$ is neither symmetric nor antisymmetric.

Example: Let $X=\{1, 2, 3\}$. Give examples of symmetric and antisymmetric relations on $X$.

Solution: \[R_1=\{{\langle}1, 1{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\},\,\, R_2=\{{\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}3, 1{\rangle}\}\] are all symmetric relations on $X$. \[R_3=\{{\langle}1, 1{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 2{\rangle}\},\,\,R_4=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\},\,\,R_5=\{{\langle}3, 2{\rangle}\}\] are all antisymmetric relations.

\[R_6=\{{\langle}3, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\] This relation is neither symmetric nor antisymmetric. However, \[R_7=\{{\langle}2, 2{\rangle}\}\] is both symmetric and antisymmetric.

Reflection of symmetric/antisymmetric relations in the relation digraph:

If $R$ is symmetric: whenever there is a directed edge from $x_i$ to $x_j$, there is also one from $x_j$ to $x_i$;
If $R$ is antisymmetric: whenever there is a directed edge from $x_i$ to $x_j$, there is none from $x_j$ to $x_i$;
If $R$ is neither symmetric nor antisymmetric: some pairs have edges in both directions and some have only one edge, with both cases present simultaneously.

Example: Let $X=\{1, 2, 3\}$. Draw the relation digraph for each binary relation on $X$ below.

Binary relations: \[E_X, D_X , R=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}1, 3{\rangle}\}\]

Reflection of symmetric/antisymmetric relations in the relation matrix:

If $R$ is symmetric, its relation matrix is symmetric;
If $R$ is antisymmetric, its relation matrix is antisymmetric, i.e., in $M_R$: if $m_{ij}=1$ (with $i {\neq} j$), then $m_{ji}=0$.

Example: Let $X=\{1, 2, 3\}$ with the binary relations below. Give the relation matrices.

Binary relations: \[E_X, D_X , R=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}1, 3{\rangle}\}\] \[ E_x= \left( \begin{array}{ccc} 1&1&1\\ 1&1&1\\ 1&1&1 \end{array} \right) , \, \, D_{x}= \left( \begin{array}{ccc} 1&1&1\\ 0&1&0\\ 0&0&1 \end{array} \right) ,\,\, R= \left( \begin{array}{ccc} 1&1&1\\ 1&0&0\\ 0&0&0 \end{array} \right). \]

Theorem: Let $R$ be a binary relation on $A$. Then:

$R$ is symmetric if and only if $R=R^{-1}$.
$R$ is antisymmetric if and only if $R{\cap}R^{-1}{\subseteq}I_A$.

Theorem: Let $R_1$ and $R_2$ be binary relations on $A$. If $R_1$ and $R_2$ are symmetric, then $R_1^{-1}$, $R_1{\cup}R_2$, and $R_1{\cap}R_2$ are also symmetric.

Proof: Let $R_1$ be a symmetric relation on $A$. For any ${\langle}x, y{\rangle}$, if ${\langle}x, y{\rangle}{\in}R_1^{-1}$, then ${\langle}y, x{\rangle}{\in}R_1$.

Since $R_1$ is symmetric, ${\langle}x, y{\rangle}{\in}R_1$. Hence ${\langle}y, x{\rangle}{\in}R_1^{-1}$, so $R_1^{-1}$ is also symmetric.

Let $R_1$ and $R_2$ be symmetric relations on $A$.

For any ${\langle}x, y{\rangle}$, if ${\langle}x, y{\rangle}{\in}R_1{\cup}R_2$, then:

${\langle}x, y{\rangle}{\in}R_1$ or ${\langle}x, y{\rangle}{\in}R_2$.

Since $R_1$ and $R_2$ are symmetric:

${\langle}y, x{\rangle}{\in} R_1$ or ${\langle}y, x{\rangle}{\in}R_2$.

Hence ${\langle}y, x{\rangle}{\in} R_1 {\cup}R_2$.

Therefore $R_1{\cup}R_2$ is symmetric.

Let $R_1$ and $R_2$ be symmetric relations on $A$.

For any ${\langle}x, y{\rangle}$, if ${\langle}x, y{\rangle} {\in} R_1 {\cap} R_2$, then:

${\langle}x, y{\rangle}{\in} R_1$ and ${\langle}x, y{\rangle}{\in}R_2$.

Since $R_1$ and $R_2$ are symmetric:

${\langle}y, x{\rangle}{\in} R_1$ and ${\langle}y, x{\rangle}{\in}R_2$.

Hence ${\langle}y, x{\rangle}{\in} R_1 {\cap} R_2$.

Therefore $R_1 {\cap} R_2$ is symmetric.

Definition: Let $R$ be a binary relation on set $X$. If for any $x, y, z{\in}X$, whenever ${\langle}x, y{\rangle}{\in}R$ and ${\langle}y, z{\rangle}{\in}R$ we have ${\langle}x, z{\rangle}{\in}R$, then $R$ is called a transitive relation on $X$.

Examples:

The set inclusion relation “${\subseteq}$”
The strict less-than relation “$<$” on numbers
The “similarity” relation on triangles in geometry

Theorem: Let $R$ be a binary relation on $A$. Then $R$ is transitive if and only if $R{\cdot}R{\subseteq}R$.

Example: $E_x, I_x, D_x, L_x, L_{x^\prime}$ are all transitive relations.

Proof: \[E_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 1{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

We have $E_X{\cdot} E_X = E_X$ and $E_X{\cdot} E_X {\subseteq} E_X$, so $E_x$ is transitive.

\[I_x=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

We have $I_x{\cdot} I_x = I_x$ and $I_x{\cdot} I_x {\subseteq} I_x$, so $I_x$ is transitive.

\[D_x=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

\[D_x{\cdot} D_x=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

We have $D_x{\cdot} D_x = D_x$ and $D_x{\cdot} D_x {\subseteq} D_x$, so $D_x$ is transitive.

\[L_X=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}\}\] \[L_X{\cdot}L_X = \{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}\}\] We have $L_X{\cdot} L_X = L_X$ and $L_X{\cdot} L_X {\subseteq} L_X$, so $L_X$ is transitive.

\[L_{X^\prime}=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\]

\[ L_{X^\prime}{\cdot} L_{X^\prime}=\{{\langle}1, 3{\rangle}\}\] We have $L_{X^\prime}{\cdot} L_{X^\prime}{\subseteq} L_{X^\prime}$, so $L_{X^\prime}$ is transitive.

Example: $R_1=\{{\langle}2, 3{\rangle}, {\langle}1, 3{\rangle}\}$ is a transitive relation.

Because \[R_1 {\cdot} R_1 = \{{\langle}2, 3{\rangle}, {\langle}1, 3{\rangle}\} {\cdot} \{{\langle}2, 3{\rangle}, {\langle}1, 3{\rangle}\} = {\Phi}\]

Clearly $R_1 {\cdot} R_1 {\subseteq} R_1$, so $R_1$ is transitive.

$R_2=\{{\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}, {\langle}1, 3{\rangle}\}$ is NOT transitive.

Because: ${\langle}2, 3{\rangle}{\in}R_2$ and ${\langle}3, 2{\rangle}{\in}R_2$, but ${\langle}2, 2{\rangle}{\notin} R_2$,

i.e., $R_2{\cdot} R_2 {\nsubseteq} R_2$.

Example: Let $X=\{1, 2, 3\}$. Give some transitive relations on $X$.

Solution: \[R_1=\{{\langle}1, 1{\rangle}\}\] \[R_2=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}1, 3{\rangle}\}\] \[R_3=\{{\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}\}\] are all transitive relations on $X$.

While \[R_4=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}\}\] \[R_5=\{{\langle}1, 3{\rangle}, {\langle}3, 1{\rangle}\}\] are not transitive.

Reflection of the transitive relation in the relation digraph:

If $R$ is transitive, whenever there is a directed edge from $x_i$ to $x_k$ and from $x_k$ to $x_j$,

there is also a directed edge from $x_i$ to $x_j$.

Reflection of the transitive relation in the relation matrix:

If $R$ is transitive, then in the matrices $M_R= (m_{ij})_{n{\times}n}$ and $M_R{\cdot}M_R=(b_{ij})_{n{\times}n}$, whenever \[b_{ij} =1\] we have \[m_{ij} =1\] for $i, j=1, 2, {\cdots}, n$.

Example: Let $R_1$ and $R_2$ be binary relations on $X=\{a, b, c\}$ with the digraphs shown below. Determine whether each is transitive.

Solution: $R_1$ is NOT transitive: there are edges $a{\rightarrow}b$ and $b{\rightarrow}a$, but no edge $a{\rightarrow}a$.

$R_2$ is transitive: there are edges $a{\rightarrow}b$ and $b{\rightarrow}c$ and also $a{\rightarrow}c$, so $R_2$ is transitive.

Formally, \[R_2 =\{{\langle}a, b{\rangle}, {\langle}b, c{\rangle}, {\langle}a, c{\rangle}\}, \] \[R_2 {\cdot} R_2 =\{{\langle}a, c{\rangle}\} {\subseteq} R_2.\]

We can also determine transitivity via the relation matrix.

\[ M_{R_1}= \left( \begin{array}{ccc} \boxed{0}&1&0\\ 1&0&0\\ 1&1&0 \end{array} \right) \] \[ M_{R_1\cdot R_1}= \left( \begin{array}{ccc} \boxed{1}&0&0\\ 0&1&0\\ 1&1&0 \end{array} \right) \]

We see $b_{11}=1$ but $m_{11}=0$, so transitivity fails.

\[ M_{R_2}= \left( \begin{array}{ccc} 0&1&\boxed{1}\\ 0&0&1\\ 0&0&0 \end{array} \right) \] \[ M_{R_2\cdot R_2}= \left( \begin{array}{ccc} 0&0&\boxed{1}\\ 0&0&0\\ 0&0&0 \end{array} \right) \]

$b_{13}=1$ and $m_{13}=1$, so the relation is transitive.

Theorem: Let $R_1$ and $R_2$ be binary relations on $A$. If $R_1$ and $R_2$ are transitive, then $R_1^{-1}$ and $R_1{\cap}R_2$ are also transitive, but $R_1{\cup}R_2$ is not necessarily transitive.

Proof: Let $R_1$ be a transitive relation on $A$.

For any $x, y, z{\in}A$, if ${\langle}x, y{\rangle}, {\langle}y, z{\rangle}{\in} R_1^{-1}$, then

${\langle}y, x{\rangle}, {\langle}z, y{\rangle}{\in}R_1$, i.e., ${\langle}z, y{\rangle},{\langle}y, x{\rangle}{\in}R_1$.

By transitivity, ${\langle}z, x{\rangle}{\in} R_1$, so ${\langle}x, z{\rangle}{\in} R_1^{-1}$.

Therefore $R_1^{-1}$ is transitive.

Let $R_1$ and $R_2$ be transitive relations on $A$.

For any $x, y, z{\in}A$, if ${\langle}x, y{\rangle}, {\langle}y, z{\rangle}{\in} R_1{\cap}R_2$, then

\[{\langle}x, y{\rangle}, {\langle}y, z{\rangle}{\in}R_1 \text{ and } {\langle}x, y{\rangle}, {\langle}y, z{\rangle}{\in}R_2.\]

Since $R_1$ and $R_2$ are transitive: \[{\langle}x, z{\rangle}{\in} R_1 \text{ and } {\langle}x, z{\rangle}{\in} R_2.\] Hence: ${\langle}x, z{\rangle}{\in}R_1{\cap}R_2$.

Therefore $R_1{\cap}R_2$ is transitive.

Example: Let $A=\{a, b, c\}$ with transitive relations: \[R_1=\{{\langle}a, b{\rangle}, {\langle}b, c{\rangle}, {\langle}a, c{\rangle}\}\] \[R_2=\{{\langle}b, c{\rangle}, {\langle}c, a{\rangle}, {\langle}b, a{\rangle}\}\] Clearly: \[R_1{\cup}R_2 =\{{\langle}a, b{\rangle}, {\langle}b, c{\rangle}, {\langle}a, c{\rangle}, {\langle}b, c{\rangle}, {\langle}c, a{\rangle}, {\langle}b, a{\rangle}\}\] is NOT transitive,

because ${\langle}a, b{\rangle}{\in}R_1{\cup}R_2$ and ${\langle}b, a{\rangle}{\in}R_1{\cup}R_2$, but ${\langle}a, a{\rangle}{\notin} R_1{\cup}R_2$.

Example: Let $A=\{1, 2, 3, 4\}$ with binary relation: \[R=\{{\langle}1, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 1{\rangle}, \] \[{\langle}3, 3{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 3{\rangle}, {\langle}4, 4{\rangle}\}\] Discuss the properties of $R$ (reflexivity, symmetry, and transitivity).

Solution: The relation matrix of $R$: \[ M_{R}= \left( \begin{array}{cccc} 1&0&1&0\\ 0&1&0&0\\ 1&0&1&1\\ 0&0&1&1 \end{array} \right) \]

The diagonal of $M_R$ is all 1s, so $R$ is reflexive;

$M_R$ is a symmetric matrix, so $R$ is symmetric.

\[ M_{R}=(m_{ij})_{4\times 4}= \left( \begin{array}{cccc} 1&0&1&\boxed{0}\\ 0&1&0&0\\ 1&0&1&1\\ 0&0&1&1 \end{array} \right) \] \[ M_{R\cdot R}=(b_{ij})_{4\times 4}= \left( \begin{array}{cccc} 1&0&1&\boxed{1}\\ 0&1&0&0\\ 1&0&1&1\\ 1&0&1&1 \end{array} \right) \]

$b_{14}=1$ but $m_{14}=0$, so $R$ is NOT transitive.

Relation Closures

Definition: Let $R$ be a binary relation on $X$. If another binary relation ${R^\prime}$ satisfies:

${R^\prime}$ is reflexive (symmetric, transitive)
$R {\subseteq} {R^\prime}$
For any reflexive (symmetric, transitive) binary relation $R^{\prime\prime}$, if $R{\subseteq}R^{\prime\prime}$, then ${R^\prime}{\subseteq}R^{\prime\prime}$,

then ${R^\prime}$ is called the reflexive closure (symmetric closure, transitive closure) of $R$, denoted $r(R)$ ($s(R)$, $t(R)$).

Theorem: Let $R$ be a binary relation on $X$, $I_x$ the identity relation on $X$, and $R^{-1}$ the inverse of $R$. Then:

$r(R)=R{\cup}I_x$
$s(R)=R{\cup}R^{-1}$
$t(R)=R{\cup}R^2{\cup}R^3{\cup} \cdots =\cup_{i=1}^\infty R^i$

Example: Let $X=\{1, 2, 3, 4\}$ with $R=\{{\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 4{\rangle}\}$. Find the reflexive, symmetric, and transitive closures of $R$.

Solution: Reflexive closure: \[r(R)=R{\cup}I_x =\{{\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 4{\rangle}\}{\cup} \{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}4, 4{\rangle}\}\] \[=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 4{\rangle}\}\]

Symmetric closure: \[s(R)=R{\cup}R^{-1} = \{{\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 4{\rangle}\} {\cup} \{{\langle}2, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}3, 2{\rangle}, {\langle}4, 3{\rangle}\}\] \[= \{{\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 3{\rangle}\}\]

Transitive closure: \[t(R)=R{\cup}R_2{\cup}R_3{\cup}R_4{\cup}\cdots\] Because \[R^2=R{\cdot}R=\{{\langle}1, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 4{\rangle}\}\] \[R^3=R^2{\cdot}R=\{{\langle}1, 2{\rangle}, {\langle}1, 4{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 3{\rangle}\}\] \[R^4=R^3{\cdot}R=\{{\langle}1, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 4{\rangle}\}\] Therefore \[t(R)=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}1, 4{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}3, 4{\rangle}\}\]

Theorem: Let $R$ be a binary relation on $X$. Then:

$R=r(R)$ if and only if $R$ is reflexive;
$R=s(R)$ if and only if $R$ is symmetric;
$R=t(R)$ if and only if $R$ is transitive.

Lemma: If $R$ and $S$ are both symmetric, then $R{\cup}S$ is also symmetric.

Lemma: If $R$ is symmetric, then $R^n$ is also symmetric for any positive integer $n$.

Theorem: Let $R$ be a binary relation on $X$. Then

If $R$ is reflexive, then $s(R)$ and $t(R)$ are also reflexive;
If $R$ is symmetric, then $r(R)$ and $t(R)$ are also symmetric;
If $R$ is transitive, then $r(R)$ is also transitive.

Theorem: Let $R$ and $S$ be binary relations on $X$ with $R{\subseteq}S$. Then:

$r(R) {\subseteq} r(S)$;
$s(R) {\subseteq} s(S)$;
$t(R) {\subseteq} t(S)$.

Equivalence Relations

Definition: Let $R$ be a binary relation on set $X$. If $R$ is reflexive, symmetric, and transitive, then $R$ is called an equivalence relation (Equivalence Relation).

Example: Let $X=\{1, 2, 3, 4\}$ with relation:

Prove that $R$ is an equivalence relation on $X$.

Proof: The relation matrix of $R$:

\[ M_R= \left( \begin{array}{cccc} 1&0&0&1\\ 0&1&1&0\\ 0&1&1&0\\ 1&0&0&1 \end{array} \right) \]

Clearly, the main diagonal of $M_R$ is all 1s, so $R$ is reflexive. $M_R$ is a symmetric matrix, so $R$ is symmetric.

\[ M_{R\cdot R}= \left( \begin{array}{cccc} 1&0&0&1\\ 0&1&1&0\\ 0&1&1&0\\ 1&0&0&1 \end{array} \right) =M_R \]

Hence $R$ is transitive. Therefore $R$ is an equivalence relation.

Example: Let $X=\{1, 2, 3\}$. The relation $R=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}$ is an equivalence relation.

Example: Let $X=\{1, 2, 3\}$. $E_X$ and $I_x$ are equivalence relations on $X$.

Definition: Let $Z$ be the set of integers, $R$ a binary relation on $Z$, and $m$ a positive integer. If \[R=\{{\langle}x, y{\rangle}|x, y{\in}Z{\, \wedge\, }m|(x-y)\}\] then $R$ is called a congruence relation modulo $m$ (Congruence Relation), written: \[x{\equiv}y(\bmod\, m).\] Every congruence relation is an equivalence relation, but not every equivalence relation is a congruence relation.

Example: Let $X=\{1, 2, 3, 4, 5, 6, 7\}$ and let $R$ be the congruence-mod-3 relation on $X$: $R=\{{\langle}x, y{\rangle}\mid x, y{\in}X{\,\wedge\,}3|(x-y)\}$. Verify that $R$ is an equivalence relation.

Solution: For any $x{\in}X$, $3|(x-x)$, so ${\langle}x, x{\rangle}{\in} R$; $R$ is reflexive.

For any $x, y{\in}X$, if ${\langle}x, y{\rangle}{\in}R$ (i.e., $3|(x-y)$), then $3|(y-x)$, so ${\langle}y, x{\rangle}{\in}R$; $R$ is symmetric.

For any $x, y, z{\in}X$, if ${\langle}x, y{\rangle}{\in}R$ and ${\langle}y, z{\rangle}{\in}R$ (i.e., $3|(x-y)$ and $3|(y-z)$), then $3|(x-z)$, so ${\langle}x, z{\rangle}{\in}R$; $R$ is transitive.

Therefore $R$ is an equivalence relation.

Definition: Let $R$ be an equivalence relation on $X$. For any $x{\in}X$, \[[x]_R=\{y\mid y{\in}X{\wedge}{\langle}x, y{\rangle}{\in}R\}\] is called the equivalence class of $x$ generated by $R$.

$x$ is called a representative of $[x]_R$.

Example: Let $X=\{1, 2, 3, 4\}$ with equivalence relation:

\[R=\{{\langle}1, 1{\rangle}, {\langle}1, 4{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}4, 1{\rangle}, {\langle}4, 4{\rangle}\}\] The equivalence classes of elements of $X$: \[[1]_R=\{1, 4\}, [2]_R=\{2, 3\}, [3]_R=\{2, 3\}, [4]_R=\{1, 4\}.\]

Example: Let $X=\{1, 2, 3\}$ with equivalence relation $R=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}$. Find the equivalence class of each element.

Solution: $[1]_R=\{1\}$, $[2]_R=\{2, 3\}$, $[3]_R=\{2, 3\}$

Theorem: Let $R$ be an equivalence relation on nonempty set $X$. For any $a, b{\in}X$:

$[a]_R{\neq} {\Phi}$ and $[a]_R {\subseteq} X$
${\langle}a, b{\rangle}{\in}R$ if and only if $[a]_R=[b]_R$
${\langle}a, b{\rangle}{\notin}R$ if and only if $[a]_R{\cap}[b]_R={\Phi}$
$\cup_{x\in X}^{}[x]_R=X$

Definition: Let $R$ be an equivalence relation on nonempty set $X$. The set of all equivalence classes of $R$ is called the quotient set of $X$ by $R$, denoted $X/R$: \[X/R=\{ [a]_R|a{\in}X\}\] The cardinality of $X/R$ is called the rank of $R$.

Example: Let $X=\{a, b, c, d\}$ with equivalence relation \[R=\{{\langle}a, a{\rangle}, {\langle}a, b{\rangle}, {\langle}b, a{\rangle}, {\langle}b, b{\rangle}, {\langle}c, c{\rangle}, {\langle}c, d{\rangle}, {\langle}d, c{\rangle}, {\langle}d, d{\rangle}\}\]

Find the quotient set $X/R$ and the rank of $R$.

Solution: Since $[a]_R=\{a, b\}=[b]_R$ and $[c]_R=\{c, d\}=[d]_R$, we have $X/R=\{\{a, b\}, \{c, d\}\}$. The rank of $R$ = 2.

Example: Let $N$ be the set of natural numbers and $R$ the congruence-mod-3 relation on $N$: $R=\{{\langle}x, y{\rangle}\mid x, y{\in}N{\,\wedge\,}3|(x-y)\}$. Find $N/R$ and the rank of $R$.

Solution: \[[0]_R=\{0, 3, 6, 9, \cdots \} =[3]_R=[6]_R=[9]_R= \cdots\]

\[[1]_R=\{1, 4, 7, 10, \cdots \} =[4]_R=[7]_R=[10]_R= \cdots\]

\[[2]_R=\{2, 5, 8, 11, \cdots \} =[5]_R=[8]_R=[11]_R= \cdots\]

Therefore $N/R=\{[0]_R, [1]_R, [2]_R\}$ and the rank of $R$ = 3.

Example: The universal relation $E_A$ on nonempty set $A$ is an equivalence relation. Find the equivalence class of any element $x{\in}A$.

Solution: For any $x{\in}A$, $[x]_R=\{y\mid y{\in}A{\wedge}{\langle}x, y{\rangle}{\in}E_A\}=A$, so $A/E_A= \{A\}$.

Example: The identity relation $I_A$ on nonempty set $A$ is an equivalence relation. Find the equivalence class of any element $x{\in}A$.

Solution: For any $x{\in}A$, $[x]_R=\{y\mid y{\in}A{\wedge}{\langle}x, y{\rangle}{\in}I_A\}=\{x\}$, so $A/I_A= \{\{x\}\mid x{\in}A \}$.

Definition: For a nonempty set $S$, if a family ${\pi}=\{S_1, S_2, \cdots , S_n\}$ satisfies:

$S_i {\neq} {\Phi}$ for $i=1, 2, \cdots , n$;
$S_i {\subseteq} S$ for $i=1, 2, \cdots , n$;
$S_i {\cap} S_j={\Phi}$ for $i, j=1, 2, \cdots , n$, $i\neq j$;
$S_1{\cup}S_2{\cup} \cdots{\cup}S_n=S$;

then ${\pi}$ is called a partition of $S$, and each $S_i$ is called a block of the partition.

Example: Let $S=\{a, b, c\}$. Consider the following collections: \[{\pi}_1=\{\{a, b\}, \{b, c\}\}\] \[{\pi}_2=\{\{a\}, \{b, c\}\}\] \[{\pi}_3=\{\{a\}, \{a, b\}\}\] \[{\pi}_4=\{\{a\}, \{b\}, \{c\}\}\] \[{\pi}_5=\{\{a, b, c\}\}\]

Clearly, ${\pi}_2$, ${\pi}_4$, and ${\pi}_5$ are all partitions of $S$, while ${\pi}_1$ and ${\pi}_3$ are not.

Definition: Let $S$ be a nonempty set and ${\pi}=\{S_1, S_2, \cdots , S_n\}$ a partition of $S$.

If $n=|S|$, then ${\pi}$ is called the finest partition of $S$.

If $n=1$, then ${\pi}$ is called the coarsest partition of $S$.

Example: For the three partitions of $S=\{a, b, c\}$: \[{\pi}_2=\{\{a\}, \{b, c\}\}\] \[{\pi}_4=\{\{a\}, \{b\}, \{c\}\}\] \[{\pi}_5=\{\{a, b, c\}\}\] ${\pi}_4$ is the finest partition and ${\pi}_5$ is the coarsest partition of $S$.

Definition: Let $A=\{A_1, A_2, \cdots , A_m\}$ and $B=\{B_1, B_2, \cdots , B_n\}$ be two partitions of a nonempty set $S$:

If for every $B_i{\in}B$ there exists $A_j{\in}A$ with $B_i{\subseteq}A_j$, then $B$ is called a refinement of $A$;
If $B$ is a refinement of $A$ and $B{\neq}A$, then $B$ is a proper refinement of $A$.

Example: For the three partitions of $S=\{a, b, c\}$:

${\pi}_2=\{\{a\}, \{b, c\}\}$, ${\pi}_4=\{\{a\}, \{b\}, \{c\}\}$, ${\pi}_5=\{\{a, b, c\}\}$

${\pi}_4$ is a proper refinement of ${\pi}_2$, and ${\pi}_2$ is a proper refinement of ${\pi}_5$.

Theorem: If $R$ is an equivalence relation on a nonempty set $X$, then the quotient set $X/R$ is a partition of $X$.

We call this partition the partition induced by the equivalence relation $R$, denoted $X_R$.

Example: Let $X=\{1, 2, 3, 4, 5, 6, 7, 8\}$, and let $R$ be the congruence-mod-3 relation on $X$, i.e.,: \[R=\{{\langle}x, y{\rangle}｜x, y{\in}X{\wedge}3|(x-y)\}\] Find:

The equivalence class of each element of $X$;
The quotient set $X/R$;
The partition $X_R$ induced by the equivalence relation $R$.

Solution: Equivalence classes:

\[[1]_R=\{1, 4, 7\} =[4]_R=[7]_R\] \[[2]_R=\{2, 5, 8\} =[5]_R=[8]_R\] \[[3]_R=\{3, 6\} =[6]_R\]

Quotient set:

\[X/R = \{ [1]_R, [2]_R , [3]_R \} =\{ \{1, 4, 7\}, \{2, 5, 8\}, \{3, 6\} \}\]

Partition induced by equivalence relation $R$:

\[X_R = \{ [1]_R, [2]_R , [3]_R \} =\{ \{1, 4, 7\}, \{2, 5, 8\}, \{3, 6\} \}\]

Theorem: A partition ${\pi}$ of set $A$ determines an equivalence relation on $A$, called the equivalence relation induced by partition ${\pi}$, denoted $R_{\pi}$.

The equivalence relation induced by ${\pi}=\{A_1, A_2, \cdots , A_n\}$ is:

\[R_{\pi}=A_1{\times}A_1{\cup}A_2{\times}A_2{\cup}\cdots {\cup}A_n{\times}A_n\] Example: Let $A=\{1, 2, 3, 4, 5, 6, 7\}$, and let $C=\{\{1, 4, 7\}, \{2, 5\}, \{3, 6\}\}$ be a partition of $A$. Find the equivalence relation $R_C$ induced by $C$.

Solution: \[R_C=\{1, 4, 7\}\times \{1, 4, 7\}\cup\{2, 5\}\times \{2, 5\}\cup\{3, 6\}\times\{3, 6\}\] \[=\{{\langle}1, 1{\rangle}, {\langle}1, 4{\rangle}, {\langle}1, 7{\rangle}, {\langle}4, 1{\rangle}, {\langle}4, 4{\rangle}, {\langle}4, 7{\rangle}, {\langle}7, 1{\rangle}, \] \[ {\langle}7, 4{\rangle}, {\langle}7, 7{\rangle}{\langle}2, 2{\rangle}, {\langle}2, 5{\rangle}, {\langle}5, 2{\rangle}, {\langle}5, 5{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 6{\rangle}, {\langle}6, 3{\rangle}, {\langle}6, 6{\rangle}\}\] $R_C$ is the equivalence relation induced by the partition $C$.

Equivalence relations and partitions are in one-to-one correspondence.

Different equivalence relations $R$ on $A$ determine different quotient sets $A/R$, hence different partitions $A_R$.

Conversely, any partition ${\pi}$ of $A$ determines an equivalence relation $R_{\pi}$ on $A$.

Different partitions determine different equivalence relations.

These partitions biject with the equivalence relations on $A$. All equivalence relations on $A$ are:

\[R_1=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 1{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}\}\] \[R_2=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}\}\] \[R_3=\{{\langle}1, 1{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 1{\rangle}, {\langle}3, 3{\rangle}\}\] \[R_4=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\] \[R_5=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\]

Theorem: If $R_1$ and $R_2$ are equivalence relations, then $R_1 {\cap} R_2$ is also an equivalence relation.

Proof: Since $R_1$ and $R_2$ are equivalence relations, they are reflexive, symmetric, and transitive.

Therefore $R_1 {\cap} R_2$ is also reflexive, symmetric, and transitive, so $R_1 {\cap} R_2$ is an equivalence relation.

Compatibility Relations

Definition: Let $R$ be a binary relation on $X$. If $R$ is reflexive and symmetric, then $R$ is called a compatibility relation (Tolerance Relation, or Dependency Relation).

If ${\langle}x, y{\rangle}{\in}R$, we say $x$ and $y$ are compatible.

Example: Let $X=\{1, 2, 3, 4\}$ with binary relation $R$ on $X$:

\[R=\{{\langle}1, 1{\rangle}, {\langle}1, 4{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 1{\rangle}, {\langle}4, 2{\rangle}, {\langle}4, 3{\rangle}, {\langle}4, 4{\rangle}\}\]

It is easy to verify that $R$ is reflexive and symmetric, so $R$ is a compatibility relation.

\[ M_R= \left( \begin{array}{cccc} 1&0&0&1\\ 0&1&1&1\\ 0&1&1&1\\ 1&1&1&1 \end{array} \right) \]

Definition: Let $R$ be a compatibility relation on $X$ and $A{\subseteq}X$. If every two elements of $A$ are compatible, then $A$ is called a compatibility class generated by $R$.

Furthermore, if no element of $(X-A)$ is compatible with all elements of $A$, then $A$ is called a maximal compatibility class.

In the previous example, $\{1, 4\}$, $\{2, 3, 4\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1\}$, etc. are compatibility classes.

Among them, $\{1, 4\}$ and $\{2, 3, 4\}$ are maximal compatibility classes.

For a compatibility relation $R$ on $X$, the maximal compatibility classes of $R$ can be identified from its relation graph.

Simplified relation graph of a compatibility relation:

Remove all self-loops.
Replace each pair of directed edges between two vertices with a single undirected edge.

In the simplified graph, every vertex of a maximal compatibility class with $n$ elements is connected to all other $n-1$ vertices in that class.

No vertex outside the class can be connected to all vertices of the class. We call the subgraph formed by these $n$ vertices and their incident edges a maximal complete subgraph of $G$.

Maximal complete subgraphs for n=2, 3, 4, 5

The maximal compatibility classes can be found conveniently from the simplified relation graph.

In the simplified graph:

The vertex set of a maximal complete subgraph is a maximal compatibility class.
An isolated vertex is a maximal compatibility class;
For any edge not contained in a maximal complete subgraph, the set of its two endpoints is also a maximal compatibility class.

Example: Given a compatibility relation, find all maximal compatibility classes.

From {b}, {a, c}, {c, e, f}, {c, d, f, g} To {a, d, c}, {e, d}, {b, e}, {b, c}

Let $R$ be a compatibility relation on set $X$. The maximal compatibility classes of $X$ with respect to $R$ have the following properties:

Every maximal compatibility class is a nonempty subset of $X$;
Different maximal compatibility classes may intersect;
The union of all maximal compatibility classes equals $X$.

Definition: For a nonempty set $S$, if a family ${\pi}=\{S_1, S_2, \cdots , S_n\}$ satisfies:

$S_i{\neq} {\Phi}$ for $i=1, 2, \cdots , n$;
$S_i{\subseteq}S$ for $i=1, 2, \cdots , n$;
$S_1{\cup}S_2{\cup} {\cdots}{\cup}S_n=S$;

then ${\pi}$ is called a covering of $S$, and each $S_i$ is called a covering block.

(Compare with partitions and partition blocks.)

Definition: For a nonempty set $S$, if a family ${\pi}=\{S_1, S_2, \cdots , S_n\}$ satisfies:

$S_i {\neq} {\Phi}$;
$S_i {\subseteq} S$;
$S_i {\cap} S_j={\Phi}$ for $i\neq j$;
$S_1{\cup}S_2{\cup} {\cdots}{\cup}S_n=S$;

then ${\pi}$ is called a partition of $S$, and each $S_i$ is called a block.

Example: Let $S=\{a, b, c\}$. If \[{\pi}_1=\{\{a\}, \{a, b\}, \{b, c\}\}\] \[{\pi}_2=\{\{a, c\}, \{b, c\}\}\] \[{\pi}_3=\{\{a, b, c\}\}\] \[{\pi}_4=\{\{a\}, \{a, b\}, \{b\}\}\] then ${\pi}_1$, ${\pi}_2$, and ${\pi}_3$ are coverings of $S$, while ${\pi}_4$ is not.

Definition: Let $S=\{S_1, S_2, \cdots, S_n\}$ be a covering of $A$. If for every $S_i{\in}S$ there is no other $S_j{\in}S$ with $S_i{\subseteq}S_j$, then $S$ is called a complete covering of $A$.

Example: Let $S=\{a, b, c\}$. If \[{\pi}_1=\{\{a\}, \{a, b\}, \{b, c\}\}\] \[{\pi}_2=\{\{a, c\}, \{b, c\}\}\] \[{\pi}_3=\{\{a, b, c\}\}\] then ${\pi}_1$, ${\pi}_2$, and ${\pi}_3$ are coverings of $S$. ${\pi}_2$ and ${\pi}_3$ are both complete coverings of $S$.

Theorem: If $R$ is a compatibility relation on set $X$, then the collection of all maximal compatibility classes of $X$ with respect to $R$ is a covering (complete covering) of $X$, called the covering (complete covering) induced by compatibility relation $R$, denoted $X_R$.

Theorem: Given a covering ${\pi}=\{A_1, A_2, \cdots , A_n\}$ of $A$, the relation determined by the covering ${\pi}$, namely $R=A_1{\times}A_1{\cup}A_2{\times}A_2{\cup}\cdots {\cup}A_n{\times}A_n$, is a compatibility relation.

Example: Let $X=\{1, 2, 3, 4\}$, and let $X_1$ and $X_2$ be two different coverings of $X$:

\[X_1=\{ \{1\}, \{2, 3, 4\} \}\] \[X_2=\{ \{1\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \}\]

Find the compatibility relation determined by each of $X_1$ and $X_2$.

Solution: The compatibility relations determined by $X_1$ and $X_2$ respectively are:

\[R_1=\{1\}{\times}\{1\}{\cup}\{2, 3, 4\}{\times}\{2, 3, 4\}\] \[=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 2{\rangle}, {\langle}4, 3{\rangle}, {\langle}4, 4{\rangle}\}\]

\[X_2=\{ \{1\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \}\] \[R_2=\{1\}{\times}\{1\}{\cup}\{2, 3\}{\times}\{2, 3\}{\cup}\{2, 4\}{\times}\{2, 4\}{\cup}\{3, 4\}{\times}\{3, 4\}\] \[=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 2{\rangle}, {\langle}4, 3{\rangle}, {\langle}4, 4{\rangle}\}\] \[R_1=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}3, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 2{\rangle}, {\langle}4, 3{\rangle}, {\langle}4, 4{\rangle}\}\] This example shows that different coverings may determine the same compatibility relation.

Example: Let $X=\{216, 243, 375, 455, 648\}$ with compatibility relation

$R=\{{\langle}x, y{\rangle}|x, y{\in}X{\wedge}x, y$ share a common digit$\}$.

Find all maximal compatibility classes and the resulting complete covering of $X$.

Solution: Using $x_1, x_2, x_3, x_4, x_5$ to represent 216, 243, 375, 455, 648 respectively, we have

\[X=\{x_1, x_2, x_3, x_4, x_5\}\]

\[R=\{{\langle}x_1, x_1{\rangle}, {\langle}x_1, x_2{\rangle}, {\langle}x_1, x_5{\rangle}, \] \[{\langle}x_2, x_1{\rangle}, {\langle}x_2, x_2{\rangle}, {\langle}x_2, x_3{\rangle}, {\langle}x_2, x_4{\rangle}, \] \[{\langle}x_2, x_5{\rangle}, {\langle}x_3, x_2{\rangle}, {\langle}x_3, x_3{\rangle}, {\langle}x_3, x_4{\rangle}, \] \[{\langle}x_4, x_2{\rangle}, {\langle}x_4, x_3{\rangle}, {\langle}x_4, x_4{\rangle}, {\langle}x_4, x_5{\rangle}, \] \[{\langle}x_5, x_1{\rangle}, {\langle}x_5, x_2{\rangle}, {\langle}x_5, x_4{\rangle}, {\langle}x_5, x_5{\rangle}\}\]

The maximal compatibility classes are: \[A_1=\{x_1, x_2, x_5\}, A_2=\{x_2, x_3, x_4\}, A_3=\{x_2, x_4, x_5\}.\] A complete covering of $X$: \[{\pi}=\{A_1, A_2, A_3\}=\{\{x_1, x_2, x_5\}, \{x_2, x_3, x_4\}, \{x_2, x_4, x_5\}\}.\]

Partial Order Relations

Definition: Let $R$ be a binary relation on set $X$. If $R$ is reflexive, antisymmetric, and transitive, then $R$ is called a partial order relation.

We usually denote a partial order by “${\leq}$” and call ${\langle}X, {\leq}{\rangle}$ a partially ordered set (poset).

If ${\langle}x, y{\rangle}{\in}R$, we write $x{\leq}y$ (read “$x$ is less than or equal to $y$”).

Examples:

The less-than-or-equal relation on real numbers.
The divisibility relation on integers.
The inclusion relation between sets.

Example: The less-than-or-equal relation $R$ on $N$ is a partial order.

Proof: \[R=\{{\langle}a, b{\rangle}|a, b{\in}N\wedge a{\leq}b\}\]

For any $a{\in}N$, $a{\leq}a$, so ${\langle}a, a{\rangle}{\in}R$; $R$ is reflexive;
For any $a, b{\in}N$, if ${\langle}a, b{\rangle}{\in}R$ and ${\langle}b, a{\rangle}{\in}R$, i.e., $a{\leq}b$ and $b{\leq}a$, then $a=b$; $R$ is antisymmetric;
For any $a, b, c{\in}N$, if ${\langle}a, b{\rangle}{\in}R$ and ${\langle}b, c{\rangle}{\in}R$, i.e., $a{\leq}b$ and $b{\leq}c$, then $a {\leq} c$; $R$ is transitive.

Therefore $R$ is a partial order relation.

Example: \[{\leq}::=R=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, \cdots , {\langle}2, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}2, 4{\rangle}, \cdots , {\langle}3, 3{\rangle}, {\langle}3, 4{\rangle}, {\langle}3, 5{\rangle}, \cdots\}\]

Example: Let $A=\{2, 3, 6, 8\}$ with $R=\{{\langle}a, b{\rangle}|a, b{\in}A\wedge a|b\}$. Is $R$ a partial order relation?

Solution: \[R=\{{\langle}2, 2{\rangle}, {\langle}2, 6{\rangle}, {\langle}2, 8{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 6{\rangle}, {\langle}6, 6{\rangle}, {\langle}8, 8{\rangle}\}\]

\[ M_R= \left( \begin{array}{cccc} 1&0&1&1\\ 0&1&1&0\\ 0&0&1&0\\ 0&0&0&1 \end{array} \right),\,\, M_{R\cdot R}= \left( \begin{array}{cccc} 1&0&1&1\\ 0&1&1&0\\ 0&0&1&0\\ 0&0&0&1 \end{array} \right) \]

Clearly $R$ is reflexive, antisymmetric, and transitive, so $R$ is a partial order relation.

Definition: Let $R$ be a binary relation on set $X$. If $R$ is irreflexive and transitive, then $R$ is called a strict partial order relation (quasi-order relation).

We usually denote it by “$<$” and call ${\langle}X, <{\rangle}$ a strict poset.

If ${\langle}x, y{\rangle}{\in}R$ we write $x<y$ (“$x$ is less than $y$”).

Example: The “less-than” relation on the reals is a strict partial order (irreflexive and transitive).

Example: The less-than relation $R$ on $N$ is a strict partial order.

Proof: $R=\{{\langle}a, b{\rangle}|a, b{\in}N \wedge a<b\}$

For any $a{\in}N$, $a\nless a$, so ${\langle}a, a{\rangle}{\notin}R$; $R$ is irreflexive. For any $a, b, c{\in}N$, if ${\langle}a, b{\rangle}{\in}R$ and ${\langle}b, c{\rangle}{\in}R$, i.e., $a<b$ and $b<c$, then $a<c$; $R$ is transitive. Therefore $R$ is a strict partial order relation.

\[<::=R=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}1, 4{\rangle}, \cdots , {\langle}2, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}2, 5{\rangle}, \cdots , {\langle}3, 4{\rangle}, {\langle}3, 5{\rangle}, {\langle}3, 6{\rangle}, \cdots , \}\]

Theorem: If $R$ is a strict partial order on $A$, then $R$ is antisymmetric.

Proof: By contradiction. Assume $R$ is not antisymmetric, i.e., there exist $x, y{\in}A$ with ${\langle}x, y{\rangle}{\in}R$, ${\langle}y, x{\rangle}{\in}R$, and $x{\neq}y$. By transitivity, ${\langle}x, x{\rangle}{\in}R$, contradicting the irreflexivity of $R$. Hence $R$ is antisymmetric.

Partial order: reflexive, antisymmetric, transitive

Strict partial order: irreflexive, antisymmetric, transitive

Definition: Let ${\langle}A, {\leq}{\rangle}$ be a poset. For any $x, y{\in}A$, if $x{\leq}y$ or $y{\leq}x$, then $x$ and $y$ are comparable.

Definition: In poset ${\langle}A, {\leq}{\rangle}$, for any $x, y{\in}A$, if $x{\leq}y$, $x{\neq}y$, and there is no $z{\in}A$ with $x{\leq}z$ and $z{\leq}y$, then $y$ covers $x$.

The cover relation is: $COV_A=\{{\langle}x, y{\rangle}|x, y{\in}A{\wedge}y$ covers $x\}$.

Example: Let ${\langle}A, {\leq}{\rangle}$ be a poset where $A$ is the set of positive divisors of 12 and “${\leq}$” is divisibility. Find $COV_A$.

Solution: $A=\{1, 2, 3, 4, 6, 12\}$. \[{\leq}::=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}1, 4{\rangle}, {\langle}1, 6{\rangle}, {\langle}1, 12{\rangle}, {\langle}2, 4{\rangle}, {\langle}2, 6{\rangle}, {\langle}2, 12{\rangle}, {\langle}3, 6{\rangle}, \]

\[{\langle}3, 12{\rangle}, {\langle}4, 12{\rangle}, {\langle}6, 12{\rangle},{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}4, 4{\rangle}, {\langle}6, 6{\rangle}, {\langle}12, 12{\rangle}\}\]

The cover relation is: \[COV_A=\{{\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}2, 6{\rangle}, {\langle}3, 6{\rangle}, {\langle}4, 12{\rangle}, {\langle}6, 12{\rangle}\}\]

We describe a partial order using a Hasse diagram (simplified relation graph).

Method 1: For poset ${\langle}A, {\leq}{\rangle}$, first compute $COV_A$, then build the Hasse diagram:

Represent each element of $A$ with a dot;
If ${\langle}x, y{\rangle}{\in}COV_A$ ($y$ covers $x$), draw $y$ above $x$ and connect with a line;
If $x$ and $y$ are incomparable, place them on the same level.

Note: If $x{\leq}y$ and $x{\neq}y$ but $y$ does not cover $x$, do NOT connect $x$ and $y$ directly.

Example: Let ${\langle}A, {\leq}{\rangle}$ be a poset with $A=\{1, 2, 3, 4\}$ and “${\leq}$” the usual less-than-or-equal relation. Find its Hasse diagram.

Solution: \[{\leq}::=\{{\langle}1, 1{\rangle}, {\langle}1, 2{\rangle}, {\langle}1, 3{\rangle}, {\langle}1, 4{\rangle}, {\langle}2, 2{\rangle}, \] \[{\langle}2, 3{\rangle}, {\langle}2, 4{\rangle}, {\langle}3, 3{\rangle}, {\langle}3, 4{\rangle}, {\langle}4, 4{\rangle}\}\]

\[COV_A=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 4{\rangle}\}\]

Example: Let $X=\{2, 3, 4, 6, 8, 12, 16, 24\}$ with divisibility relation $R=\{{\langle}x, y{\rangle}\mid x, y{\in}X${}$x|y{\in}X\}$. Then \[COV_X=\{{\langle}2, 4{\rangle}, {\langle}2, 6{\rangle}, {\langle}4, 8{\rangle}, {\langle}4, 12{\rangle}, {\langle}8, 16{\rangle}, \] \[ {\langle}8, 24{\rangle}, {\langle}3, 6{\rangle}, {\langle}6, 12{\rangle}, {\langle}12, 24{\rangle}\}\]

Method 2: Obtain the Hasse diagram by simplifying the relation digraph.

Example: Let $A=\{a, b, c\}$. Find the Hasse diagram of ${\langle}{P}(A), {\subseteq}{\rangle}$.

Solution: Since \[{P}(A)=\{ {\Phi}, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\} \}\] \[COV_{P}(A)=\{{\langle}{\Phi}, \{a\}{\rangle}, {\langle}{\Phi}, \{b\}{\rangle}, {\langle}{\Phi}, \{c\}{\rangle}, {\langle}\{a\}, \{a, b\}{\rangle},\]

\[{\langle}\{a\}, \{a, c\}{\rangle}, {\langle}\{b\}, \{a, b\}{\rangle}, {\langle}\{b\}, \{b, c\}{\rangle},\] \[{\langle}\{c\}, \{a, c\}{\rangle}, {\langle}\{c\}, \{b, c\}{\rangle}, {\langle}\{a, b\}, \{a, b, c\}{\rangle},\] \[{\langle}\{a, c\}, \{a, b, c\}{\rangle}, {\langle}\{b, c\}, \{a, b, c\}{\rangle}\}\]

Definition: Let ${\langle}A, {\leq}{\rangle}$ be a poset and $Q{\subseteq}A$.

If there exists $a{\in}Q$ such that:

$a{\leq}x$ for all $x{\in}Q$, then $a$ is called the minimum element of $Q$.
$x{\leq}a$ for all $x{\in}Q$, then $a$ is called the maximum element of $Q$.

Definition: Let ${\langle}A, {\leq}{\rangle}$ be a poset and $Q{\subseteq}A$. If there exists $a{\in}Q$ such that:

No other $x{\in}Q$ satisfies $x{\leq}a$, then $a$ is a minimal element of $Q$.
No other $x{\in}Q$ satisfies $a{\leq}x$, then $a$ is a maximal element of $Q$.

Example: Let $A=\{a, b\}$. In the poset ${\langle}{P}(A), {\subseteq}{\rangle}$, find the maximum and minimum elements of $\{{\Phi}, \{a\}\}$, $\{\{a\}, \{b\}\}$, and $P(A)$.

Solution: $P(A)=\{{\Phi}, \{a\}, \{b\}, \{a, b\}\}$. Draw the Hasse diagram of ${\subseteq}$.

From the Hasse diagram:

The maximum element of $\{\Phi, \{a\}\}$ is $\{a\}$ and the minimum element is $\Phi$.
$\{\{a\}, \{b\}\}$ has neither a maximum nor a minimum element.
The maximum element of $P(A)$ is $\{a, b\}$ and the minimum element is $\Phi$.

Example: Let $A=\{2, 3, 5, 7, 14, 15, 21\}$ with partial order \[R=\{{\langle}2, 14{\rangle}, {\langle}3, 15{\rangle}, {\langle}3, 21{\rangle}, {\langle}5, 15{\rangle}, {\langle}7, 14{\rangle},\] \[{\langle}7, 21{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}, {\langle}5, 5{\rangle}, {\langle}7, 7{\rangle}, \] \[{\langle}14, 14{\rangle}, {\langle}15, 15{\rangle}, {\langle}21, 21{\rangle}\}\]

Find the maximal, minimal, maximum, and minimum elements of $B=\{2, 7, 3, 21, 14\}$.

In $B=\{2, 7, 3, 21, 14\}$:

Minimal elements: $\{2, 7, 3\}$
Maximal elements: $\{14, 21\}$
No minimum or maximum element exists.

Example: Let $A=\{a, b, c\}$. In poset ${\langle}{P}(A), {\subseteq}{\rangle}$, \[P(A)=\{{\Phi}, \{a\}, \{b\}, \{c\}, \] \[\{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}, \] \[Q_1=\{{\Phi}, \{a\}, \{a, b\}, \{a, b, c\}\}, \] \[Q_2=\{\{a\}, \{b\}, \{a, b\}\}, \] \[Q_3=\{\{b\}, \{a, b\}, \{b, c\}\}, \] \[Q_4=\{\{c\}, \{a, b\}\}. \] Find the maximal and minimal elements of $Q_1$, $Q_2$, $Q_3$, and $Q_4$.

\[Q_1=\{{\Phi}, \{a\}, \{a, b\}, \{a, b, c\}\}\] \[Q_2=\{\{a\}, \{b\}, \{a, b\}\}\]

\[Q_3=\{\{b\}, \{a, b\}, \{b, c\}\}\]

\[Q_4=\{\{c\}, \{a, b\}\}\] The maximal element of $Q_1$ is $\{a, b, c\}$, and its minimal element is $\Phi$.

The maximal element of $Q_2$ is $\{a, b\}$, and its minimal elements are $\{a\}$ and $\{b\}$.

The maximal elements of $Q_3$ are $\{a, b\}$ and $\{b, c\}$, and its minimal element is $\{b\}$.

The maximal elements of $Q_4$ are $\{a, b\}$ and $\{c\}$, and its minimal elements are $\{a, b\}$ and $\{c\}$.

Theorem: Let ${\langle}A, {\leq}{\rangle}$ be a poset and $Q\subseteq A$. Then:

If $Q$ has a minimum element, it is unique.
If $Q$ has a maximum element, it is unique.

Definition: Let ${\langle}A, {\leq}{\rangle}$ be a poset and $Q{\subseteq}A$. If there exists $a{\in}A$ such that:

$x{\leq}a$ for all $x{\in}Q$, then $a$ is an upper bound of $Q$, denoted $U_B$;
$a{\leq}x$ for all $x{\in}Q$, then $a$ is a lower bound of $Q$, denoted $L_B$.

Definition: Let ${\langle}A, {\leq}{\rangle}$ be a poset and $Q{\subseteq}A$. If there exists $a{\in}A$ such that:

$a$ is an upper bound of $Q$ and $a{\leq}a^\prime$ for every upper bound $a^\prime$ of $Q$, then $a$ is the least upper bound (supremum) of $Q$, denoted $LU_B$;
$a$ is a lower bound of $Q$ and $a^\prime{\leq}a$ for every lower bound $a^\prime$ of $Q$, then $a$ is the greatest lower bound (infimum) of $Q$, denoted $GL_B$.

Example: Let $A=\{2, 3, 6, 12, 24, 36\}$, with the Hasse diagram of the partial order $R$ on $A$ as shown.

Find the upper bounds, lower bounds, supremum, and infimum of the subsets $\{2, 3, 6\}$ and $\{6, 12\}$.

Solution:

For $\{2, 3, 6\}$: upper bounds: 6, 12, 24, 36; supremum: 6; lower bounds: none; infimum: none.

For $\{6, 12\}$: upper bounds: 12, 24, 36; supremum: 12; lower bounds: 2, 3, 6; infimum: 6.

Example: Let $A=\{a, b, c, d, e\}$, with the Hasse diagram of the partial order $R$ on $A$ shown below.

Find the maximal, minimal, maximum, minimum elements, and the upper bounds, lower bounds, supremum, and infimum of $A$.

Solution:

Maximal element: $e$; Minimal element: $a$; Maximum element: $e$; Minimum element: $a$;

Upper bounds: $e$; Lower bounds: $a$; Supremum: $e$; Infimum: $a$.

Theorem: Let ${\langle}A, {\leq}{\rangle}$ be a poset and $Q{\subseteq}A$.

If $Q$ has a supremum, it is unique.
If $Q$ has an infimum, it is unique.

From the above we conclude:

The maximum (minimum) element need not exist; if it does, it is unique.
Maximal (minimal) elements always exist but need not be unique.

A maximum (minimum) element is necessarily a maximal (minimal) element.
Upper (lower) bounds need not exist; if they do, they need not be unique.
Supremum (infimum) need not exist; if it does, it is unique.
Existence of a supremum (infimum) implies existence of upper (lower) bounds.
If $a$ is the maximum (minimum) of $Q$, then $a$ is the supremum (infimum) of $Q$. Conversely, if $a$ is the supremum (infimum) of $Q$ and $a{\in}Q$, then $a$ is the maximum (minimum) of $Q$.

Definition: Let ${\langle}X, {\leq}{\rangle}$ be a poset. If every two elements of $X$ are comparable, then ${\leq}$ is called a total order (linear order), and ${\langle}X, {\leq}{\rangle}$ is called a totally ordered set (chain).

Example: The relation ${\leq}$ (less-than-or-equal) on $N$ makes ${\langle}N, {\leq}{\rangle}$ a totally ordered set.

It is reflexive, antisymmetric, transitive, and for any $x, y{\in}N$, either $x{\leq}y$ or $y{\leq}x$. Therefore ${\langle}N, {\leq}{\rangle}$ is a totally ordered set.

Example: Let $A=\{a, b, c\}$. Define $\subseteq$ as the inclusion relation on $P(A)$. Then $\langle P(A), \subseteq\rangle$ is NOT a totally ordered set.

Because: \[P(A)=\{\Phi, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}\] and $\{a\}$ and $\{b, c\}$ are incomparable (neither contains the other). Therefore $\langle P(A), \subseteq\rangle$ is not a totally ordered set.

Definition: In a poset ${\langle}X, {\leq}{\rangle}$, if every nonempty subset of $X$ has a minimum element, then ${\leq}$ is called a well-order, and ${\langle}X, {\leq}{\rangle}$ is called a well-ordered set.

Example: Let $Z_n=\{1, 2, 3, \cdots , n\}$ with the usual ${\leq}$. Then ${\langle}Z_n, {\leq}{\rangle}$ is a well-ordered set, and so is ${\langle}Z_+, {\leq}{\rangle}$.

However, ${\langle}Z, {\leq}{\rangle}$ is NOT a well-ordered set, because the subset $Z_- {\subseteq}Z$ has no minimum element.

Theorem: Every well-ordered set is a totally ordered set.

Theorem: Every finite totally ordered set is a well-ordered set.