Relations: Introduction

What is a Relation?

Definition

A binary relation $R$ from a set $A$ to a set $B$ is a subset $R \subseteq A \times B$.

We write:

• $R : A \nrightarrow B$ to indicate a relation from $A$ to $B$
• $aRb$ or $(a, b) \in R$ to indicate $R$ relates $a$ and $b$

Intuition

A relation describes how elements of $A$ are connected to elements of $B$. Unlike a function, a single $a \in A$ can be related to multiple $b \in B$, or to none at all.

Relational Extensionality

Two relations are equal iff they relate the same pairs:

$R = S \iff \forall a \in A. \forall b \in B. (aRb \Leftrightarrow aSb)$

Examples of Relations

The Empty Relation

For any sets $A, B$, the empty relation $\emptyset \subseteq A \times B$ relates nothing.

$a \emptyset\, b \text{ is never true}$

The Full Relation

The full relation $A \times B \subseteq A \times B$ relates everything.

$a (A \times B) b \text{ for all } a \in A, b \in B$

The Identity Relation

For a set $A$, the identity relation $\text{id}_A \subseteq A \times A$:

$a \,\text{id}_A\, a' \iff a = a'$

Examples from Computer Science

Program specification: The relation $\text{sq} : \mathbb{R}_{\geq 0} \nrightarrow \mathbb{R}$ given by $x \,\text{sq}\, y \iff x = y^2$.

Operational semantics: A transition relation $S : E \nrightarrow E$ on machine states where $eSe'$ means “state $e$ can transition to $e'$”.

Network connectivity: A relation $C : N \nrightarrow N$ on network nodes, where $aCb$ means “node $a$ is directly connected to node $b$”.

Database relations: A table relating Movies, Directors, Years, and People.

Special Relations on a Single Set

A relation $R \subseteq A \times A$ is called an endo-relation or relation on $A$.

Reflexivity

$R$ is reflexive if $\forall a \in A. aRa$.

Equivalently: $\text{id}_A \subseteq R$.

Symmetry

$R$ is symmetric if $\forall a, b \in A. (aRb \Rightarrow bRa)$.

Transitivity

$R$ is transitive if $\forall a, b, c \in A. (aRb \land bRc \Rightarrow aRc)$.

Antisymmetry

$R$ is antisymmetric if $\forall a, b \in A. (aRb \land bRa \Rightarrow a = b)$.

Examples

Relation	Reflexive	Symmetric	Transitive	Antisymmetric
$a = b$ on any set	Yes	Yes	Yes	Yes
$a \leq b$ on $\mathbb{R}$	Yes	No	Yes	Yes
$a < b$ on $\mathbb{R}$	No	No	Yes	Yes
$a \mid b$ on $\mathbb{Z}$	Yes	No	Yes	No
”is a sibling of” on people	No	Yes	No	No

Visualising Relations

Internal Diagrams

Draw elements of $A$ on the left, elements of $B$ on the right. Draw arrows from $a$ to $b$ whenever $aRb$.

Matrix Representation

For finite sets $A = \{a_1, \ldots, a_m\}$ and $B = \{b_1, \ldots, b_n\}$, represent $R$ as an $m \times n$ boolean matrix $M$:

$M_{ij} = 1 \iff a_i R b_j$

Graph Representation (for endo-relations)

Draw elements of $A$ as vertices. Draw a directed edge from $a$ to $b$ whenever $aRb$.

---

Summary

• A relation $R : A \nrightarrow B$ is a subset $R \subseteq A \times B$
• Special relations: empty, full, identity
• Key properties: reflexive, symmetric, transitive, antisymmetric
• Visualise with internal diagrams, matrices, or directed graphs