Difference between revisions of "Relation"

From Maths
Jump to: navigation, search
m (Types of relation)
m (Types of relation: fixing typo)
 
(2 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)}}
 
 
[[Function|Functions]], [[Equivalence relation|equivalence relations]] and [[Ordering|orderings]] are special kinds of relation
 
{{Refactor notice}}
 
 
==Definition==
 
==Definition==
A relation {{M|\mathcal{R} }} between two sets is a subset of the [[Cartesian product]] of two sets<ref name="Analysis">Analysis - Part I: Elements - Krzysztof Maurin</ref>, that is:
+
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}}
 
* {{M|\mathcal{R}\subseteq X\times Y}}
We say that {{M|\mathcal{R} }} is a ''relation in {{M|X}}''<ref name="Analysis"/> if:
+
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="Analysis"/> called a ''graph'')
+
* {{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)
 
** For example {{M|<}} is a relation in the set of {{M|\mathbb{Z} }} (the integers)
  
Line 23: Line 19:
 
|-
 
|-
 
| NO IDEA
 
| NO IDEA
| {{M|1=P_X\mathcal{R} }}<ref name="Analysis"/>
+
| {{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}}
 
| {{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
 
! Inverse relation
| {{M|\mathcal{R}^{-1} }}<ref name="Analysis"/>
+
| {{M|\mathcal{R}^{-1} }}<ref name="APIKM"/>
 
| {{M|1=\mathcal{R}^{-1}:=\{(y,x)\in Y\times X\vert\ x\mathcal{R}y\} }}
 
| {{M|1=\mathcal{R}^{-1}:=\{(y,x)\in Y\times X\vert\ x\mathcal{R}y\} }}
 
|-
 
|-
 
! Composing relations
 
! Composing relations
| {{M|\mathcal{R}\circ\mathcal{S} }}<ref name="Analysis"/>
+
| {{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]\} }}
 
| {{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==
 
==Simple examples of relations==
# The ''empty relation''<ref name="Analysis"/>, {{M|\emptyset\subset X\times X}} is of course a relation
+
# The ''empty relation''<ref name="APIKM"/>, {{M|\emptyset\subset X\times X}} is of course a relation
# The ''total relation''<ref name="Analysis"/>, {{M|1=\mathcal{R}=X\times X}} that relates everything to everything
+
# The ''total relation''<ref name="APIKM"/>, {{M|1=\mathcal{R}=X\times X}} that relates everything to everything
# The ''identity relation''<ref name="Analysis"/>, {{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\} }}
+
# 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="Analysis"/> ''the diagonal of the square {{M|X\times X}}''
+
#* This is also known as<ref name="APIKM"/> ''the diagonal of the square {{M|X\times X}}''
  
 
==Types of relation==
 
==Types of relation==
Line 50: Line 46:
 
! Notes
 
! Notes
 
|-
 
|-
! Reflexive<ref name="Analysis"/>
+
! {{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="Analysis"/>
+
! {{Anchor|Type_symmetric}}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="Analysis"/>
+
! {{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="Analysis"/>)
+
! {{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="Analysis"/>
+
! {{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="Analysis"/>
+
! {{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="Analysis"/>
+
! {{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="Analysis"/>
+
! {{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="Analysis"/>
+
! {{Anchor|Type_mutually-unique}}Mutually unique<ref name="APIKM"/>
 
| Both right and left unique
 
| Both right and left unique
 
|
 
|
Line 96: Line 92:
 
|}
 
|}
  
 +
==Examples of binary relations==
 +
* [[Function|Functions / mappings]]
 +
* [[Equivalence relation|Equivalence relations]]
 +
* [[Ordering|Orderings]]
 +
* [[Preordering|Preorderings]]
 +
==Notes==
 +
<references group="Note"/>
 
==References==
 
==References==
 
<references/>
 
<references/>
 
+
{{Relations navbox|plain}}
=OLD PAGE=
+
==Notation==
+
Rather than writing {{M|(x,y)\in R}} to say {{M|x}} and {{M|y}} are related we can instead say {{M|xRy}}
+
==Basic terms==
+
Proof that domain, range and field exist may be found [[The domain, range and field of a relation exist|here]]
+
===Domain===
+
The set of all {{M|x}} which are related by {{M|R}} to some {{M|y}} is the domain.
+
 
+
<math>\text{Dom}(R)=\{x|\exists\ y: xRy\}</math>
+
 
+
===Range===
+
The set of all {{M|y}} which are a relation of some {{M|x}} by {{M|R}} is the range.
+
 
+
<math>\text{Ran}(R)=\{y|\exists\ x: xRy\}</math>
+
 
+
===Field===
+
The set <math>\text{Dom}(R)\cup\text{Ran}(R)=\text{Field}(R)</math>
+
 
+
===Relation in X===
+
To be a relation in a set {{M|X}} we must have <math>\text{Field}(R)\subset X</math>
+
 
+
==Images of sets==
+
===Image of A under R===
+
This is just the set of things that are related to things in A, denoted <math>R[A]</math>
+
 
+
<math>R[A]=\{y\in\text{Ran}(R)|\exists x\in A:xRa\}</math>
+
 
+
===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>
+
 
+
<math>R^{-1}[B]=\{x\in\text{Dom}(R)|\exists y\in B:xRy\}</math>
+
 
+
===Important lemma===
+
It is very important to know that the inverse image of B under R is the same as the image under <math>R^{-1}</math>
+
 
+
 
+
==Properties of relations==
+
===Symmetric===
+
A relation {{M|R}} in {{M|A}} is symmetric if for all {{M|a,b\in A}} we have that {{M|aRb\implies bRa}} - a property of [[Equivalence relation|equivalence relations]]
+
===Antisymmetric===
+
A binary relation {{M|R}} in {{M|A}} is antisymmetric if for all {{M|a,b\in A}} we have <math>aRb\text{ and }bRA\implies a=b</math><br/>
+
Symmetric implies elements are related to each other, antisymmetric implies only the same things are related to each other.
+
===Reflexive===
+
For a relation {{M|R}} and for all {{M|a\in A}} we have {{M|aRa}} - {{M|a}} is related to itself.
+
===Transitive===
+
A relation {{M|R}} in {{M|A}} is transitive if for all {{M|a,b,c\in A}} we have <math>[aRb\text{ and }bRc\implies aRc]</math>
+
===Asymmetric===
+
A relation {{M|S}} in {{M|A}} is asymmetric if {{M|aSb\implies(b,a)\notin S}}, for example {{M|<}} has this property, we can have {{M|a<b}} or {{M|b<a}} but not both.
+
 
{{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