Relation

Definition

A binary relation $\mathcal{R}$ (or just a relation $R$) between two sets is a subset of the Cartesian product of two sets, that is:

• $\mathcal{R}\subseteq X\times Y$

We say that $\mathcal{R}$ is a relation in $X$ if:

• $\mathcal{R}\subseteq X\times X$ (note that $\mathcal{R}$ is sometimes called a graph)
  • For example $<$ is a relation in the set of $\mathbb{Z}$ (the integers)

If $(x,y)\in\mathcal{R}$ then we:

• Say: $x$ is in relation $\mathcal{R}$ with $y$
• Write: $x\mathcal{R}y$ for short.

Operations

Here $\mathcal{R}$ is a relation between $X$ and $Y$, that is $\mathcal{R}\subseteq X\times Y$, and $\mathcal{S}\subseteq Y\times Z$

Name	Notation	Definition
NO IDEA	$P_X\mathcal{R}$	$P_X\mathcal{R}=\{x\in X\vert\ \exists y:\ x\mathcal{R}y\}$ - a function is (among other things) a case where $P_Xf=X$
Inverse relation	$\mathcal{R}^{-1}$	$\mathcal{R}^{-1}:=\{(y,x)\in Y\times X\vert\ x\mathcal{R}y\}$
Composing relations	$\mathcal{R}\circ\mathcal{S}$	$\mathcal{R}\circ\mathcal{S}:=\{(x,z)\in X\times Z\vert\ \exists y\in Y[x\mathcal{R}y\wedge y\mathcal{S}z]\}$

Simple examples of relations

1. The empty relation, $\emptyset\subset X\times X$ is of course a relation
2. The total relation, $\mathcal{R}=X\times X$ that relates everything to everything
3. The identity relation, $\text{id}_X:=\text{id}:=\{(x,y)\in X\times X\vert x=y\}=\{(x,x)\in X\times X\vert x\in X\}$
   • This is also known as the diagonal of the square $X\times X$

Types of relation

Here $\mathcal{R}\subseteq X\times X$

Name	Set relation	Statement	Notes
Reflexive	$\text{id}_X\subseteq\mathcal{R}$	$\forall x\in X[x\mathcal{R}x]$	Every element is related to itself (example, equality)
Symmetric	$\mathcal{R}\subseteq\mathcal{R}^{-1}$	$\forall x\in X\forall y\in X[x\mathcal{R}y\implies y\mathcal{R}x]$	(example, equality)
Transitive	$\mathcal{R}\circ\mathcal{R}\subseteq\mathcal{R}$	$\forall x,y,z\in X[(x\mathcal{R}y\wedge y\mathcal{R}z)\implies x\mathcal{R}z]$	(example, equality, $<$)
Antisymmetric (AKA Identitive)	$\mathcal{R}\cap\mathcal{R}^{-1}\subseteq\text{id}_X$	$\forall x\in X\forall y\in X[(x\mathcal{R}y\wedge y\mathcal{R}x)\implies x=y]$	TODO: What about a relation like 1r2 1r1 2r1 and 2r2
Connected	$\mathcal{R}\cup\mathcal{R}^{-1}=X\times X$		TODO: Work out what this means
Asymmetric	$\mathcal{R}\subseteq\complement(\mathcal{R}^{-1})$	$\forall x\in X\forall y\in X[x\mathcal{R}y\implies (y,x)\notin\mathcal{R}]$	Like $<$ (see: Contrapositive)
Right-unique	$\mathcal{R}^{-1}\circ\mathcal{R}\subseteq\text{id}_X$	$\forall x,y,z\in X[(x\mathcal{R}y\wedge x\mathcal{R}z)\implies y=z]$	This is the definition of a function
Left-unique	$\mathcal{R}\circ\mathcal{R}^{-1}\subseteq\text{id}_X$	$\forall x,y,z\in X[(x\mathcal{R}y\wedge z\mathcal{R}y)\implies x=z]$
Mutually unique	Both right and left unique		TODO: Investigate

Examples of binary relations

• Functions / mappings
• Equivalence relations
• Orderings
• Preorderings