# Relation

(Redirected from Symmetric relation)

## Definition

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

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

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

• [ilmath]\mathcal{R}\subseteq X\times X[/ilmath] (note that [ilmath]\mathcal{R} [/ilmath] is sometimes[1] 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][1] [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][1] [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][1] [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[1], [ilmath]\emptyset\subset X\times X[/ilmath] is of course a relation
2. The total relation[1], [ilmath]\mathcal{R}=X\times X[/ilmath] that relates everything to everything
3. The identity relation[1], [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[1] 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[1] [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[1] [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[1] [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[3]
(AKA Identitive[1])
[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[1] [ilmath]\mathcal{R}\cup\mathcal{R}^{-1}=X\times X[/ilmath]

TODO: Work out what this means

Asymmetric[1] [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[1] [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[1] [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[1] Both right and left unique

TODO: Investigate

## Notes

1. A binary relation should be assumed if just relation is specified

## References

1. Analysis - Part 1: Elements - Krzysztof Maurin
2. Types and Programming Languages - Benjamin C. Peirce
3. Real and Abstract Analysis - Edwin Hewitt and Karl Stromberg