[Discrete Mathematics] lecture 3 - Relations

Overview

This lecture presents a comprehensive introduction to relations in discrete mathematics, covering foundational definitions, properties, and theorems. It begins by defining binary relations and their operations (complement, inverse, composition, and power), followed by a detailed look at key relational properties such as reflexivity, symmetry, and transitivity. The text explores the graphical interpretation of relations using directed graphs and explains how relational properties map to graph structures.

Further, the concepts of closures (reflexive, symmetric, transitive) are introduced, followed by equivalence relations, equivalence classes, and the resulting partitions and quotient sets. The discussion extends to induced relations, refinement of partitions, and the formal connection between partitions and equivalence.

In the final sections, the focus shifts to partial orders and posets, introducing tools such as Hasse diagrams, covering, greatest/least elements, bounds, and lattices—highlighting how structured orderings arise from specific relational properties. The section closes with a preview of lattice theory, a topic central to further studies in order theory.

Introduction to Relations

Basic Definitions of Relations

The following are basic definitions of relations in discrete mathematics.

Definition 1 (binary relation)
Let $A$ and $B$ be two sets. A binary relation from $A$ to $B$ is a subset of the Cartesian product $A \times B$.

Definition 2 (complement)
Let $R \in A \times B$ be a binary relation. The complement of $R$ is defined as
$\bar{R} ={(a,b)| (a,b) \notin R}= (A \times B) - R$.

Definition 3 (inverse)
An inverse (or converse) of a binary relation $R \in A \times B$ is defined as
$R^{-1} = {(b,a)| (a,b) \in R}$.

Definition 4
‣ A relation from a set $A$ to itself is called a relation on $A$.
‣ The identity relation $I_A$ on a set $A$ is defined as $I_A = {(a,a)| a \in A}$.

Definition 5 (composite)
Let $R \in A \times B$ and $S \in B \times C$ be two binary relations. The composite of $R$ and $S$ is defined as
$R \circ S = {(a,c)| (a,b) \in R \wedge (b,c) \in S ;\text{for some} ; b \in B}$.

Definition 6 (power of a relation)
The n-th power of a relation $R$ is defined as
$R^n = R \circ R^{n-1}$ for $n \geq 1$ and $R^0 = I_A$.

Properties of Relations

A relation $R$ on $A$ is said to be...

property	definition
reflexive	$\forall a \in A, : (a,a) \in R$
irreflexive	$\forall a \in A, : (a,a) \notin R$
symmetric	$\forall a, b \in A, : (a,b) \in R \rightarrow (b,a) \in R$
antisymmetric	$\forall a, b \in A, : (a,b) \in R \wedge (b,a) \in R \rightarrow a = b$
asymmetric	$\forall a, b \in A, : (a,b) \in R \rightarrow (b,a) \notin R$
transitive	$\forall a, b, c \in A, : (a,b) \in R \wedge (b,c) \in R \rightarrow (a,c) \in R$

• irreflexive $\neq$ reflexive
• if $R$ is asymmetric, then it is antisymmetric, but not vice versa.

Example
Let $R = { (1,1), (1,2), (2,1), (2,2), (3,3), (4,4) }$ on $A={1,2,3, 4}$.
Then $R$ is reflexive, symmetric, and transitive.

From the definitions and properties above, we can derive some theorems.

Basic Theorems of Relations

Theorem 1
Let $\R_1$ and $\R_2$ be two binary relations on $A$
‣ $(R_1 \cup R_2)^{-1} = R_1 ^{-1} \cup R_2^{-1}$
‣ $(R_1 \cap R_2)^{-1} = R_1^{-1} \cap R_2^{-1}$

Theorem 2 (associativity in composite)
Let $R \in A \times B$, $S \in B \times C$, and $T \in C \times D$ be three binary relations. Then
$(R \circ S) \circ T = R \circ (S \circ T)$

Theorem 3
Let $R$ be a relation. For any pair of natural numbers $m$ and $n$,
$R^n \circ R^m = R^{n+m}$
$ (R^n)^m = R^{n m}$

Theorem 4
Let $R_1$, $R_2$, and $R_3$ be relations on a set $A$.
‣ $R_1 \circ (R_2 \cap R_3) \subseteq (R_1 \circ R_2) \cap (R_1 \circ R_3)$
‣ $R_1 \circ (R_2 \cup R_3) = (R_1 \circ R_2) \cup (R_1 \circ R_3)$

Theorem 5
Let $R$ be a binary relation on $A$, and $I_A$ be the identity relation on $A$.
$R$ is reflexive iif $I_A \subseteq R$
$R$ is irreflexive iif $I_A \cap R = \empty$
$R$ is symmetric iif $R^{-1} = R$
$R$ is asymmetric iif $R^{-1} \cap R = \empty$
$R$ is antisymmetric iif $R^{-1} \cap R \subseteq I_A$
$R$ is transitive iif $R \circ R \subseteq R$

Short Disscussion on Graphs

Definition 7
Consider a directed graph $G = \left<V, E\right>$ where $V$ is a set of vertices and $E$ is a set of edges.
‣ A walk is a sequence of edges of $G$
‣ A length of a walk is the number of edges in the walk.
‣ A trail is a walk in which all edges are distinct
‣ A path is a trail in which all vertices are distinct
‣ A cycle is a walk that begins and ends at the same vertex.
‣ A loop is a cycle of length 1.
‣ A sling is a cycle of length 2.

Theorem 6
Let $G=\left<V,E\right>$ where $V$ is a set of vertices and $E$ is a set of edges.
‣ $E$ is reflexive iif $G$ has a loop at every vertex
‣ $E$ is irreflexive iif G has no loop at any vertex
‣ $E$ is symmetric iif if G has a walk of length one between two distinct vertices then it has a sling between them
‣ $E$ is asymmetric iif (1) if G has a walk of length one between two distinct vertices then it has no slign between them and (2) no vertex has a loop
‣ $E$ is antisymmetric iif if G has a walk of length one between two distinct vertices then it has no slign between them
‣ $E$ is transitive iif if G has a walk of length two between two distinct vertices then it has a walk of length one between

Example :

Closure of Relations

Definition 8
For any property $X$, the $X$ closure of a relation $R$ is the smallest relation that contains $R$ and has property $X$.

Example: The reflexive closure of $R={(1,2),(2,3)}$ on $A={1,2,3}$ is
$R'={(1,1),(2,2),(3,3),(1,2),(2,3)}$.

Theorem 7
The reflextive closure of a relation $R$ is $R \cup I_A$
The symmetric closure of a relation $R$ is $R \cup R^{-1}$
The transitive closure of a relation $R$ is $\bigcup_{n\in \N }R^n$ .

Equivalence

Definition 9 (equivalence relation)
A relation $R$ on a set $A$ is called an equivalence relation if it is reflexive, symmetric, and transitive.

Definition 10 (equivalence class)
Let $R$ be an equivalence relation on a set $A$. The equivalence class of a with respect to $R$ is defined as
$\left[ a \right]_R = \left\{ x \in A | (a,x) \in R\right \}$.

Think of the modulo operation.
The equivalent element in modulo 3 is the same as the remainder of the division by 3.
The equivalence class would be the set of all elements that have the same remainder.

In short, the equivalence class is a set of elements that are equivalent to each other.

Theorem 8
Let $R$ be an equivalence relation on a set $A$.
‣ $\forall x \in A, x \in \left[x\right]_R$
‣ If $\left<x,y\right> \in R$, then $\left[x\right]_R = \left[y\right]_R$
‣ If $\left<x,y\right> \not\in R$, then $\left[x\right]_R \cap \left[y\right]_R = \empty$

Partition of a Set

Definition 11 (covering, partition)
Let $S$ be a given set and $\pi = \left\{A_1, A_2, ... A_m\right\}$, where each $A_i$ is a non-empty subset of $S$ and $\bigcup_{i=1}^{m}A_i = S$
‣ $\pi$ is a covering of $S$ and $A_1, A_2, ... A_m$ are said to cover $S$.
‣ $\pi$ is a partition of $S$ if $A_i \cap A_j = \empty$ for all $i \neq j$. $A_1, A_2, ... A_m$ are called the blocks of the partition

Definition 12 (quotient set)
Let $R$ be an equivalence relation on a set $A$. Then the quotient set of $A$ modulo $R$ is defined as
$A/R = \left\{\left[x\right]_R | x \in A\right\}$.

Theorem 9
Let $R$ be an equivalence relation on a set $A$. Then the quotient set $A/R$ is a partition of $A$.

Induced Relation

Definition 13 (induced relation)
Let $\pi = \left\{A_1, A_2, ... A_m\right\}$ be a partition of a set $S$. The induced relation on $S$ is defined as
$R = \left\{(x,y) | x \in A_i \wedge y \in A_i, : \text{for some} : i\right\}$.

Theorem 10
Let $\pi = \left\{A_1, A_2, ... A_m\right\}$ be a partition of a set $S$. Then the induced relation on $S$ is an equivalence relation.

If you think about it, the induced relation generates all the possible combinations of elements in the same block of the partition. Thus, it must be reflexive, symmetric, and transitive i.e. an equivalence relation.

Refinement of a Partition

Definition 14 (refinement of a partition)

Let $\pi_1$ and $\pi_2$ be two partitions of a set $S$. Then $\pi_2$ is said to be a refinement of $\pi_1$ if every block of $\pi_2$ is a subset of some block of $\pi_1$.

Example:

Let $\pi_1 = \left\{\left\{1,2\right\}, \left\{3,4\right\}\right\}$ and $\pi_2 = \left\{\left\{1\right\}, \left{2\right\}, \left\{3,4\right\}\right\}$.

Then $\pi_2$ is a refinement of $\pi_1$ because every block of $\pi_2$ is a subset of some block of $\pi_1$.

In short, refinement is a process of breaking down a partition into smaller partitions.

Theorem 11
Let $\pi_1$ and $\pi_2$ be two partitions of a set $S$ and let $R_{\pi_1}$ and $R_{\pi_2}$ be the induced relations on $S$ with respect to $\pi_1$ and $\pi_2$, respectively. Then
$\pi_2$ is a refinement of $\pi_1$ iif $R_{\pi_2} \subseteq R_{\pi_1}$

Intuitively speaking, if $\pi_2$ is a refinement of $\pi_1$, then the $\pi_2$ must have smaller blocks than $\pi_1$. Thus, the induced relation of $\pi_2$ must be a subset of the induced relation of $\pi_1$.

Partial Order

Definition 15 (partial order)
A relation $R$ on a set $S$ is called a partial order if it is reflexive, antisymmetric, and transitive.
A set $S$ with a partial order is called a partially ordered set (or poset).

The symbol $\preceq$ is used to denote a relation in any poset.

Definition 16
‣ The elements $a$ and $b$ are said to be comparable if $a \preceq b$ or $b \preceq a$.
‣ The elements $a$ and $b$ are said to be incomparable if neither $a \preceq b$ nor $b \preceq a$.

Definition 17 (total order)
A relation $R$ on a set $S$ is called a total order if it is reflexive, antisymmetric, transitive, and every pair of elements in $S$ is comparable.
A set $S$ with a total order is called a totally ordered set (or chain).

Hasse Diagram

A Hasse diagram is a graphical representation of a poset.

It is obtained by drawing the elements of the poset as points in a plane and connecting them with lines to represent the relation.

• All the loops are omitted
• An arc is omitted if it can be inferred from the trasitivity.
• All arcs are drawn in the upward direction.

Covering in Poset

Definition 18

An element $a$ is said to cover an element $b$ in a poset if $a \preceq b$ and there is no element $c$ such that $a \preceq c \preceq b$.

So, in a Hasse diagram, if there is an arc from $a$ to $b$, then $a$ covers $b$.

GLB and LUB

Definition 19 (greatest element and least element)

Let $(A, \preceq)$ be a poset and $B \subseteq A$.
‣ An element $g \in B$ is said to be a greatest element of $B$ iif $b \preceq g$ for all $b \in B$.
‣ An element $l \in B$ is said to be a least element of $B$ iif $l \preceq b$ for all $b \in B$.

The greatest/least element does not necessarily exist in every cases.

Theorem 12
Let $(A, \preceq)$ be a poset and $B \subseteq A$.
If both $a$ and $b$ are greatest (or least) elements of $B$, then $a = b$.

Definition 20 (lower bound and greatest lower bound)
Let $(A, \preceq)$ be a poset and $B \subseteq A$.
‣ An element $a \in A$ is said to be a lower bound of $B$ iif $a \preceq b$ for all $b \in B$.
‣ An element $a \in A$ is said to be a greatest lower bound of $B$ iif $a$ is a lower bound of $B$ and $a' \preceq a$ for all lower bounds $a'$ of $B$.

Definition 21 (upper bound and least upper bound)
Let $(A, \preceq)$ be a poset and $B \subseteq A$.
‣ An element $a \in A$ is said to be an upper bound of $B$ iif $b \preceq a$ for all $b \in B$.
‣ An element $a \in A$ is said to be a least upper bound of $B$ iif $a$ is an upper bound of $B$ and $a \preceq a'$ for all upper bounds $a'$ of $B$.

This part is important because it is used in the definition of a lattice, which we will discuss in lecture 7.

Theorem 13
Let $(A, \preceq)$ be a poset and $B \subseteq A$.
‣ If $b$ is a greatest element of $B$, then $b$ is a lub of $B$.
‣ If $b$ is an upper bound of B and $b \in B$, then $b$ is the greatest element of $B$

Theorem 14
Let $(A, \preceq)$ be a poset and $B \subseteq A$. If lub or glb exists, then it is unique.

Sneak peek of Lattice

Definition 22 (lattice)
A poset $(A, \preceq)$ is called a lattice if every pair of elements in $A$ has a lub and a glb.

Theorem 15
Let $\left<L, \preceq \right>$ be a lattice. If $x+y$ denotes lub, $xy$ denotes glb, the following holds for $\forall a,b,c \in L$
$ab = a$ (idempotent)
$ab = b*a$ (commutative)
$a(bc) = (ab)c$ (associative)
$a(a+b) = a$ (absorbtion)
$a+b = a$ (idempotent)
$a+b = b+a$ (commutative)
$a+(b+c) = (a+b)+c$ (associative)
$a+(a*c) =a$ (absorbtion)

One important thing to note is that the distributive property does not hold in a lattice. More to be discussed in lecture 7.