Relation

Definition

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

• [ilmath]\mathcal{R}\subseteq X\times Y[/ilmath]

We say that [ilmath]\mathcal{R} [/ilmath] is a relation in [ilmath]X[/ilmath] if:

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

If [ilmath](x,y)\in\mathcal{R} [/ilmath] then we:

• Say: [ilmath]x[/ilmath] is in relation [ilmath]\mathcal{R} [/ilmath] with [ilmath]y[/ilmath]
• Write: [ilmath]x\mathcal{R}y[/ilmath] for short.

Operations

Here [ilmath]\mathcal{R} [/ilmath] is a relation between [ilmath]X[/ilmath] and [ilmath]Y[/ilmath], that is [ilmath]\mathcal{R}\subseteq X\times Y[/ilmath], and [ilmath]\mathcal{S}\subseteq Y\times Z[/ilmath]

Name	Notation	Definition
NO IDEA	[ilmath]P_X\mathcal{R}[/ilmath]	[ilmath]P_X\mathcal{R}=\{x\in X\vert\ \exists y:\ x\mathcal{R}y\}[/ilmath] - a function is (among other things) a case where [ilmath]P_Xf=X[/ilmath]
Inverse relation	[ilmath]\mathcal{R}^{-1} [/ilmath]	[ilmath]\mathcal{R}^{-1}:=\{(y,x)\in Y\times X\vert\ x\mathcal{R}y\}[/ilmath]
Composing relations	[ilmath]\mathcal{R}\circ\mathcal{S} [/ilmath]	[ilmath]\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]\}[/ilmath]

Simple examples of relations

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

Types of relation

Here [ilmath]\mathcal{R}\subseteq X\times X[/ilmath]

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

Examples of binary relations

• Functions / mappings
• Equivalence relations
• Orderings
• Preorderings