Difference between revisions of "Relation"

From Maths
Jump to: navigation, search
m (Removing old page (have never used it in 7 months, safe to say it is obsolete), fixed references)
(Types of relation: Added anchor tags to table.)
Line 46: Line 46:
 
! Notes
 
! Notes
 
|-
 
|-
! Reflexive<ref name="APIKM"/>
+
! {{Anchor|Type_reflexive}}Reflexive<ref name="APIKM"/>
 
| {{M|\text{id}_X\subseteq\mathcal{R} }}
 
| {{M|\text{id}_X\subseteq\mathcal{R} }}
 
| {{M|\forall x\in X[x\mathcal{R}x]}}
 
| {{M|\forall x\in X[x\mathcal{R}x]}}
 
| Every element is related to itself (example, equality)
 
| Every element is related to itself (example, equality)
 
|-
 
|-
! Symmetric<ref name="APIKM"/>
+
! {{Anchor|Type_symmetricc}}Symmetric<ref name="APIKM"/>
 
| {{M|\mathcal{R}\subseteq\mathcal{R}^{-1} }}
 
| {{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]}}
 
| {{M|\forall x\in X\forall y\in X[x\mathcal{R}y\implies y\mathcal{R}x]}}
 
| (example, equality)
 
| (example, equality)
 
|-
 
|-
! Transitive<ref name="APIKM"/>
+
! {{Anchor|Type_transitive}}Transitive<ref name="APIKM"/>
 
| {{M|\mathcal{R}\circ\mathcal{R}\subseteq\mathcal{R} }}
 
| {{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]}}
 
| {{M|\forall x,y,z\in X[(x\mathcal{R}y\wedge y\mathcal{R}z)\implies x\mathcal{R}z]}}
 
| (example, equality, {{M|<}})
 
| (example, equality, {{M|<}})
 
|-
 
|-
! Antisymmetric<ref name="RAAA">Real and Abstract Analysis - Edwin Hewitt and Karl Stromberg</ref><br/>({{AKA}} Identitive<ref name="APIKM"/>)
+
! {{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|\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]}}
 
| {{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}}
 
| {{Todo|What about a relation like 1r2 1r1 2r1 and 2r2}}
 
|-
 
|-
! Connected<ref name="APIKM"/>
+
! {{Anchor|Type_connected}}Connected<ref name="APIKM"/>
 
| {{M|1=\mathcal{R}\cup\mathcal{R}^{-1}=X\times X}}
 
| {{M|1=\mathcal{R}\cup\mathcal{R}^{-1}=X\times X}}
 
|
 
|
 
| {{Todo|Work out what this means}}
 
| {{Todo|Work out what this means}}
 
|-
 
|-
! Asymmetric<ref name="APIKM"/>
+
! {{Anchor|Type_asymmetric}}Asymmetric<ref name="APIKM"/>
 
| {{M|1=\mathcal{R}\subseteq\complement(\mathcal{R}^{-1})}}
 
| {{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}]}}
 
| {{M|1=\forall x\in X\forall y\in X[x\mathcal{R}y\implies (y,x)\notin\mathcal{R}]}}
 
| Like {{M|<}} (see: [[Contrapositive]])
 
| Like {{M|<}} (see: [[Contrapositive]])
 
|-
 
|-
! Right-unique<ref name="APIKM"/>
+
! {{Anchor|Type_right-unique}}Right-unique<ref name="APIKM"/>
 
| {{M|1=\mathcal{R}^{-1}\circ\mathcal{R}\subseteq\text{id}_X}}
 
| {{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]}}
 
| {{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]]
 
| This is the definition of a [[function]]
 
|-
 
|-
! Left-unique<ref name="APIKM"/>
+
! {{Anchor|Type_left-unique}}Left-unique<ref name="APIKM"/>
 
| {{M|1=\mathcal{R}\circ\mathcal{R}^{-1}\subseteq\text{id}_X}}
 
| {{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]}}
 
| {{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"/>
+
! {{Anchor|Type_mutually-unique}}Mutually unique<ref name="APIKM"/>
 
| Both right and left unique
 
| Both right and left unique
 
|
 
|
 
| {{Todo|Investigate}}
 
| {{Todo|Investigate}}
 
|}
 
|}
 +
 
==Examples of binary relations==
 
==Examples of binary relations==
 
* [[Function|Functions / mappings]]
 
* [[Function|Functions / mappings]]

Revision as of 20:02, 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