Difference between revisions of "Relation"

From Maths
Jump to: navigation, search
m
m (Types of relation: fixing typo)
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
A set {{M|R}} is a binary relation if all elements of {{M|R}} are [[Ordered pair|ordered pairs]]. That is for any {{M|z\in R\ \exists x\text{ and }y:(x,y)}}
+
==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)
  
  
==Notation==
+
If {{M|(x,y)\in\mathcal{R} }} then we:
Rather than writing {{M|(x,y)\in R}} to say {{M|x}} and {{M|y}} are related we can instead say {{M|xRy}}
+
* 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]\} }}
 +
|}
  
==Domain==
+
==Simple examples of relations==
The set of all {{M|x}} which are related by {{M|R}} to some {{M|y}} is the domain.
+
# 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}}''
  
<math>\text{Dom}(R)=\{x|\exists\ y: xRy\}</math>
+
==Types of relation==
 
+
Here {{M|\mathcal{R}\subseteq X\times X}}
==Range==
+
{| class="wikitable" border="1"
The set of all {{M|y}} which are a relation of some {{M|x}} by {{M|R}} is the range.
+
|-
 
+
! Name
<math>\text{Ran}(R)=\{y|\exists\ x: xRy\}</math>
+
! Set relation
 
+
! Statement
==Field==
+
! Notes
The set <math>\text{Dom}(R)\cup\text{Ran}(R)=\text{Field}(R)</math>
+
|-
 
+
! {{Anchor|Type_reflexive}}Reflexive<ref name="APIKM"/>
==Relation in X==
+
| {{M|\text{id}_X\subseteq\mathcal{R} }}
To be a relation in a set {{M|X}} we must have <math>\text{Field}(R)\subset X</math>
+
| {{M|\forall x\in X[x\mathcal{R}x]}}
 
+
| Every element is related to itself (example, equality)
==Image of A under R==
+
|-
This is just the set of things that are related to things in A, denoted <math>R[A]</math>
+
! {{Anchor|Type_symmetric}}Symmetric<ref name="APIKM"/>
 
+
| {{M|\mathcal{R}\subseteq\mathcal{R}^{-1} }}
<math>R[A]=\{y\in\text{Ran}(R)|\exists x\in A:xRa\}</math>
+
| {{M|\forall x\in X\forall y\in X[x\mathcal{R}y\implies y\mathcal{R}x]}}
 
+
| (example, equality)
==Inverse image of B under R==
+
|-
As you'd expect this is the things that are related to things in B, denoted <math>R^{-1}[B]</math>
+
! {{Anchor|Type_transitive}}Transitive<ref name="APIKM"/>
 
+
| {{M|\mathcal{R}\circ\mathcal{R}\subseteq\mathcal{R} }}
<math>R^{-1}[B]=\{x\in\text{Dom}(R)|\exists y\in B:xRy\}</math>
+
| {{M|\forall x,y,z\in X[(x\mathcal{R}y\wedge y\mathcal{R}z)\implies x\mathcal{R}z]}}
 +
| (example, equality, {{M|<}})
 +
|-
 +
! {{Anchor|Type_antisymmetric|Type_identitive}}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}}
 +
|-
 +
! {{Anchor|Type_connected}}Connected<ref name="APIKM"/>
 +
| {{M|1=\mathcal{R}\cup\mathcal{R}^{-1}=X\times X}}
 +
|
 +
| {{Todo|Work out what this means}}
 +
|-
 +
! {{Anchor|Type_asymmetric}}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]])
 +
|-
 +
! {{Anchor|Type_right-unique}}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]]
 +
|-
 +
! {{Anchor|Type_left-unique}}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]}}
 +
|
 +
|-
 +
! {{Anchor|Type_mutually-unique}}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}}
 
{{Definition|Set Theory}}

Latest revision as of 20:07, 20 April 2016

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


Examples of binary relations

Notes

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

References

  1. 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 Analysis - Part 1: Elements - Krzysztof Maurin
  2. Types and Programming Languages - Benjamin C. Peirce
  3. Real and Abstract Analysis - Edwin Hewitt and Karl Stromberg