View source for Relation

==Definition==
A ''binary relation'' {{M|\mathcal{R} }} (or just a ''relation'' {{M|R}}<ref group="Note">A binary relation should be assumed if just relation is specified</ref>) between two sets is a subset of the [[Cartesian product]] of two sets{{rAPIKM}}<ref name="TAPL">Types and Programming Languages - Benjamin C. Peirce</ref>, that is:
* {{M|\mathcal{R}\subseteq X\times Y}}
We say that {{M|\mathcal{R} }} is a ''relation in {{M|X}}''<ref name="APIKM"/> if:
* {{M|\mathcal{R}\subseteq X\times X}} (note that {{M|\mathcal{R} }} is sometimes<ref name="APIKM"/> called a ''graph'')
** For example {{M|<}} is a relation in the set of {{M|\mathbb{Z} }} (the integers)


If {{M|(x,y)\in\mathcal{R} }} then we:
* Say: ''{{M|x}} is in relation {{M|\mathcal{R} }} with {{M|y}}''
* Write: {{M|x\mathcal{R}y}} for short.
==Operations==
Here {{M|\mathcal{R} }} is a relation between {{M|X}} and {{M|Y}}, that is {{M|\mathcal{R}\subseteq X\times Y}}, and {{M|\mathcal{S}\subseteq Y\times Z}}
{| class="wikitable" border="1"
|-
! Name
! Notation
! Definition
|-
| NO IDEA
| {{M|1=P_X\mathcal{R} }}<ref name="APIKM"/>
| {{M|1=P_X\mathcal{R}=\{x\in X\vert\ \exists y:\ x\mathcal{R}y\} }} - a [[Function|function]] is (among other things) a case where {{M|1=P_Xf=X}}
|-
! Inverse relation
| {{M|\mathcal{R}^{-1} }}<ref name="APIKM"/>
| {{M|1=\mathcal{R}^{-1}:=\{(y,x)\in Y\times X\vert\ x\mathcal{R}y\} }}
|-
! Composing relations
| {{M|\mathcal{R}\circ\mathcal{S} }}<ref name="APIKM"/>
| {{M|1=\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==
# The ''empty relation''<ref name="APIKM"/>, {{M|\emptyset\subset X\times X}} is of course a relation
# The ''total relation''<ref name="APIKM"/>, {{M|1=\mathcal{R}=X\times X}} that relates everything to everything
# The ''identity relation''<ref name="APIKM"/>, {{M|1=\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<ref name="APIKM"/> ''the diagonal of the square {{M|X\times X}}''

==Types of relation==
Here {{M|\mathcal{R}\subseteq X\times X}}
{| class="wikitable" border="1"
|-
! Name
! Set relation
! Statement
! Notes
|-
! Reflexive<ref name="APIKM"/>
| {{M|\text{id}_X\subseteq\mathcal{R} }}
| {{M|\forall x\in X[x\mathcal{R}x]}}
| Every element is related to itself (example, equality)
|-
! Symmetric<ref name="APIKM"/>
| {{M|\mathcal{R}\subseteq\mathcal{R}^{-1} }}
| {{M|\forall x\in X\forall y\in X[x\mathcal{R}y\implies y\mathcal{R}x]}}
| (example, equality)
|-
! Transitive<ref name="APIKM"/>
| {{M|\mathcal{R}\circ\mathcal{R}\subseteq\mathcal{R} }}
| {{M|\forall x,y,z\in X[(x\mathcal{R}y\wedge y\mathcal{R}z)\implies x\mathcal{R}z]}}
| (example, equality, {{M|<}})
|-
! Antisymmetric<ref name="RAAA">Real and Abstract Analysis - Edwin Hewitt and Karl Stromberg</ref><br/>({{AKA}} Identitive<ref name="APIKM"/>)
| {{M|\mathcal{R}\cap\mathcal{R}^{-1}\subseteq\text{id}_X}}
| {{M|1=\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<ref name="APIKM"/>
| {{M|1=\mathcal{R}\cup\mathcal{R}^{-1}=X\times X}}
|
| {{Todo|Work out what this means}}
|-
! Asymmetric<ref name="APIKM"/>
| {{M|1=\mathcal{R}\subseteq\complement(\mathcal{R}^{-1})}}
| {{M|1=\forall x\in X\forall y\in X[x\mathcal{R}y\implies (y,x)\notin\mathcal{R}]}}
| Like {{M|<}} (see: [[Contrapositive]])
|-
! Right-unique<ref name="APIKM"/>
| {{M|1=\mathcal{R}^{-1}\circ\mathcal{R}\subseteq\text{id}_X}}
| {{M|1=\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<ref name="APIKM"/>
| {{M|1=\mathcal{R}\circ\mathcal{R}^{-1}\subseteq\text{id}_X}}
| {{M|1=\forall x,y,z\in X[(x\mathcal{R}y\wedge z\mathcal{R}y)\implies x=z]}}
|
|-
! Mutually unique<ref name="APIKM"/>
| Both right and left unique
|
| {{Todo|Investigate}}
|}
==Examples of binary relations==
* [[Function|Functions / mappings]]
* [[Equivalence relation|Equivalence relations]]
* [[Ordering|Orderings]]
* [[Preordering|Preorderings]]
==Notes==
<references group="Note"/>
==References==
<references/>
{{Relations navbox|plain}}
{{Definition|Set Theory}}