Binary Relations and Equivalence

In discrete mathematics, sets and functions establish the ground rules for structures, but binary relations provide the formal machinery needed to model and analyze connections between objects. This module explores how binary relations generalize functions, partitions domains, and establish order structures through equivalence relations and posets.

1. Mathematical Bedrock: Sets and Cartesian Products

A set is an unordered collection of distinct objects. We write $a \in S$ if $a$ is a member of the set $S$ , and $a \notin S$ otherwise.

Set Specification

Sets can be specified via:

Roster notation: Explicitly listing all elements, e.g., $A = \{1, 2, 3, 4, 5\}$ .
Set-builder notation: Specifying a defining predicate $P(x)$ , written as $D = \{x \in U \mid P(x)\}$ , where is the . This is governed by the , asserting that every predicate determines a subset of .

Subsets and Power Sets

Subset ( $\subseteq$ ): $A \subseteq B \iff \forall x (x \in A \implies x \in B)$ .
Proper Subset ( $\subset$ ): .

Cartesian Products

The Cartesian product of two sets $A$ and $B$ , denoted $A \times B$ , is the set of all ordered pairs: $A \times B = \{(a, b) \mid a \in A \land b \in B\}$

Two ordered pairs are equal if and only if their respective coordinates are equal: $\langle a_1, b_1 \rangle = \langle a_2, b_2 \rangle \iff a_1 = a_2 \land b_1 = b_2$

More generally, an ordered $n$ -tuple is an ordered list of $n$ elements, denoted $\langle a_1, a_2, \dots, a_n \rangle$ .

Bit-Vector Representation of Sets

For a finite universal set $U = \{u_1, u_2, \dots, u_m\}$ , a subset can be represented by a bit-vector of length , where the -th bit is if and if .

text

Universal Set U = {a, b, c, d, e}
Subset A        = {a,    c,    e}  --> Bit-Vector: [1, 0, 1, 0, 1]
Subset B        = {   b, c, d   }  --> Bit-Vector: [0, 1, 1, 1, 0]
 
Union (A U B)   = [1, 0, 1, 0, 1] OR  [0, 1, 1, 1, 0] = [1, 1, 1, 1, 1]
Inter. (A n B)  = [1, 0, 1, 0, 1] AND [0, 1, 1, 1, 0] = [0, 0, 1, 0, 0]

2. Foundations of Functions and Mappings

A function (or mapping) $f: X \to Y$ is a special type of relation that assigns to each element $x \in X$ exactly one element $y \in Y$ .

$\forall x \in X, \exists ! y \in Y \text{ such that } f(x) = y$

Formally, a relation $f \subseteq X \times Y$ is a function if and only if: $\forall x, y_1, y_2 \quad (\langle x, y_1 \rangle \in f \land \langle x, y_2 \rangle \in f \implies y_1 = y_2)$

$X$ is the domain ( $D_f$ ).
$Y$ is the codomain ( $C_f$ ).
The range () is the set of all actual images: .

Special Functions

Peano's Successor Function: $\sigma: \mathbb{P} \to \mathbb{P}$ where $\sigma(n) = n + 1$ .
Floor Function ( $\lfloor x \rfloor$ ): The largest integer $\le x$ .

For any $x \in \mathbb{R}$ : $\text{If } x \notin \mathbb{Z}, \quad \lfloor -x \rfloor \neq -\lfloor x \rfloor \quad \text{and} \quad \lceil -x \rceil \neq -\lceil x \rceil$

text

       Floor:  [-1.4] = -2      [1.6] = 1
       -----------------------------------> Real line
               -2       -1      0      1      2
       Ceiling:        [-1.4] = -1     [1.6] = 2

Classification of Mappings

One-to-One (Injective): Every element of the range has a unique pre-image. $\forall x_1, x_2 \in X \quad (f(x_1) = f(x_2) \implies x_1 = x_2)$

Function Composition

Given $f: A \to B$ and $g: B \to C$ , the composition $g \circ f: A \to C$ is defined by:

3. Binary Relations and Their Properties

A binary relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$ . We write $aRb$ to denote $\langle a, b \rangle \in R$ . If , we refer to as a .

Unlike functions, a single element $a \in A$ can be related to multiple elements in $B$ , or to none at all.

text

Function (Mapping)                   General Relation
  Domain        Codomain               Domain        Codomain
  [ a ] ------> [ 1 ]                  [ a ] ------> [ 1 ]
  [ b ] ---\                           [ b ] ---\---> [ 2 ]
            \--> [ 2 ]                           \---> [ 3 ]
  [ c ] ------> [ 3 ]                  [ c ] (unmapped)

Properties of Relations on a Set $A$

Reflexivity

$R$ is reflexive if every element is related to itself. $\forall a \in A \quad (aRa)$

Symmetry

$R$ is symmetric if relationship directions can be reversed. $\forall a, b \in A \quad (aRb \implies bRa)$

Antisymmetry

$R$ is antisymmetric if two distinct elements cannot be mutually related to each other. $\forall a, b \in A \quad (aRb \land bRa \implies a = b)$

Transitivity

$R$ is transitive if relationships cascade through intermediate elements. $\forall a, b, c \in A \quad (aRb \land bRc \implies aRc)$

Closures of Relations

If a relation $R$ lacks a property, we construct its closure by adding the minimum number of ordered pairs to satisfy that property:

Reflexive Closure: $R \cup \Delta$ , where $\Delta = \{(a, a) \mid a \in A\}$ .
Symmetric Closure: $R \cup R^{-1}$ , where .

4. Equivalence Relations and Partitions

An equivalence relation is a binary relation on a set $A$ that is simultaneously reflexive, symmetric, and transitive.

Equivalence Classes

Let $R$ be an equivalence relation on $A$ . For any $a \in A$ , the equivalence class of $a$ , denoted $[a]_R$ , is the set of all elements related to :

Any element $b \in [a]_R$ is called a representative of the equivalence class.

Quotient Sets and Partitions

The collection of all equivalence classes of elements in $A$ is the quotient set, denoted $A/R$ : $A/R = \{[a]_R \mid a \in A\}$

A key theorem of set theory states that the quotient set $A/R$ forms a partition of $A$ . A partition of a set $A$ is a collection of non-empty, pairwise disjoint subsets $A_i$ whose union is $A$ :

$\forall i, A_i \neq \emptyset$
$A_i \cap A_j = \emptyset \quad \forall i \neq j$

Concrete Example: Congruence Modulo $n$

Let $A = \mathbb{Z}$ , and $n \ge 2$ be a fixed positive integer. The relation congruence modulo $n$ , written $a \equiv b \pmod n$ , is defined by:

Proof that Congruence Modulo $n$ is an Equivalence Relation:

Reflexivity: For any $a \in \mathbb{Z}$ , $a - a = 0$ . Since $n \mid 0$ , we have $a \equiv a \pmod n$ .

For $n = 3$ , the quotient set $\mathbb{Z}/\equiv_3$ consists of exactly three equivalence classes: $[0] = \{\dots, -6, -3, 0, 3, 6, \dots\}$

5. Partially Ordered Sets (Posets) and Hasse Diagrams

A relation $R$ on a set $S$ is a partial ordering if it is reflexive, antisymmetric, and transitive. A set $S$ together with a partial ordering $R$ is called a partially ordered set, or poset, and is written as $\langle S, R \rangle$ (or $\langle S, \le \rangle$ ).

Comparability and Total Orders

Two elements $a$ and $b$ of a poset $\langle S, \le \rangle$ are comparable if $a \le b$ or $b \le a$ .
If every pair of elements in a poset is comparable, the set is called a totally ordered set (or a ).

Hasse Diagrams

A Hasse diagram is a graphical representation of a finite poset. It is constructed by omitting:

All loops $(a, a)$ due to reflexivity.
All transitive edges $(a, c)$ when $a \le b$ and $b \le c$ .
Directional arrows, by placing the larger element higher than the smaller element.

We say $y$ covers $x$ if $x < y$ and there is no element $z$ such that $x < z < y$ . In a Hasse diagram, we draw an edge from up to if and only if covers .

Example: Divisibility on $\{1, 2, 3, 6\}$

Let $X = \{1, 2, 3, 6\}$ under the relation $x | y$ ( $x$ divides $y$ ).

text

Example: Power Set of $\{a, b, c\}$ under Subset Inclusion ( $\subseteq$ )

Let $S = \{a, b, c\}$ . The poset is $\langle \mathcal{P}(S), \subseteq \rangle$ .

text

              {a, b, c}
             /    |    \
       {a, b}   {a, c}  {b, c}
         |  \   /   \   /  |
       {a}   {b}     {c}
         \    |    /
              {}

Extremal Elements in a Poset

Let $\langle P, \le \rangle$ be a poset:

Maximal element: An element $x \in P$ is maximal if there is no $y \in P$ such that $x < y$ . (Located at the top level of the Hasse diagram).
Minimal element: An element $x \in P$ is minimal if there is no such that . (Located at the bottom level of the Hasse diagram).

Bounds, LUB, and GLB

Let $A \subseteq P$ be a subset of a poset $\langle P, \le \rangle$ :

Upper Bound: An element $u \in P$ is an upper bound of $A$ if $a \le u$ for all $a \in A$ .
Lower Bound: An element $l \in P$ is a lower bound of if for all .

Summary

Binary Relations generalize mappings, mapping elements from a domain to multiple codomain targets as subsets of $A \times B$ .
Equivalence Relations partition their underlying sets into disjoint equivalence classes, structuring quotient sets $A/R$ .
Functions are specialized, restricted binary relations where every domain element maps to a unique codomain element.
Posets ( $\langle P, \le \rangle$ ) establish order relations through reflexivity, antisymmetry, and transitivity.
Hasse Diagrams represent finite posets by stripping away redundant reflexive and transitive links, rendering hierarchically ordered chains and lattices.

Assessed progress

Binary Relations and Equivalence

Key Concepts

Binary Relation

Equivalence Relation

Quotient Set

Partial Ordering (Poset)

Hasse Diagram

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures