Difference between revisions of "Relation"

From Maths
Jump to: navigation, search
m
m (Types of relation: fixing typo)
 
(5 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)
  
[[Function|Functions]], [[Equivalence relation|equivalence relations]] and [[Ordering|orderings]] are special kinds of relation
 
  
==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}}''
==Basic terms==
+
* Write: {{M|x\mathcal{R}y}} for short.
Proof that domain, range and field exist may be found [[The domain, range and field of a relation exist|here]]
+
==Operations==
===Domain===
+
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}}
The set of all {{M|x}} which are related by {{M|R}} to some {{M|y}} is the domain.
+
{| 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]\} }}
 +
|}
  
<math>\text{Dom}(R)=\{x|\exists\ y: xRy\}</math>
+
==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}}''
  
===Range===
+
==Types of relation==
The set of all {{M|y}} which are a relation of some {{M|x}} by {{M|R}} is the range.
+
Here {{M|\mathcal{R}\subseteq X\times X}}
 +
{| class="wikitable" border="1"
 +
|-
 +
! Name
 +
! Set relation
 +
! Statement
 +
! Notes
 +
|-
 +
! {{Anchor|Type_reflexive}}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)
 +
|-
 +
! {{Anchor|Type_symmetric}}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)
 +
|-
 +
! {{Anchor|Type_transitive}}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|<}})
 +
|-
 +
! {{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}}
 +
|}
  
<math>\text{Ran}(R)=\{y|\exists\ x: xRy\}</math>
+
==Examples of binary relations==
 
+
* [[Function|Functions / mappings]]
===Field===
+
* [[Equivalence relation|Equivalence relations]]
The set <math>\text{Dom}(R)\cup\text{Ran}(R)=\text{Field}(R)</math>
+
* [[Ordering|Orderings]]
 
+
* [[Preordering|Preorderings]]
===Relation in X===
+
==Notes==
To be a relation in a set {{M|X}} we must have <math>\text{Field}(R)\subset X</math>
+
<references group="Note"/>
 
+
==References==
==Images of sets==
+
<references/>
===Image of A under R===
+
{{Relations navbox|plain}}
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