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

v • d • e
 
Common relations in mathematics
Overview of the common relations encountered almost everywhere
Generic
Orderings
Retrieved from "https://www.maths.kisogo.com/index.php?title=Relation&oldid=2380"