Difference between revisions of "Relation"
From Maths
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
Contents
[hide]Definition
A binary relation R (or just a relation R[Note 1]) between two sets is a subset of the Cartesian product of two sets[1][2], that is:
- R⊆X×Y
We say that R is a relation in X[1] if:
- R⊆X×X (note that R is sometimes[1] called a graph)
- For example < is a relation in the set of Z (the integers)
If (x,y)∈R then we:
- Say: x is in relation R with y
- Write: xRy for short.
Operations
Here R is a relation between X and Y, that is R⊆X×Y, and S⊆Y×Z
| Name | Notation | Definition |
|---|---|---|
| NO IDEA | PXR[1] | PXR={x∈X| ∃y: xRy} - a function is (among other things) a case where PXf=X |
| Inverse relation | R−1[1] | R−1:={(y,x)∈Y×X| xRy} |
| Composing relations | R∘S[1] | R∘S:={(x,z)∈X×Z| ∃y∈Y[xRy∧ySz]} |
Simple examples of relations
- The empty relation[1], ∅⊂X×X is of course a relation
- The total relation[1], R=X×X that relates everything to everything
- The identity relation[1], idX:=id:={(x,y)∈X×X|x=y}={(x,x)∈X×X|x∈X}
- This is also known as[1] the diagonal of the square X×X
Types of relation
Here R⊆X×X
| Name | Set relation | Statement | Notes |
|---|---|---|---|
| Reflexive[1] | idX⊆R | ∀x∈X[xRx] | Every element is related to itself (example, equality) |
| Symmetric[1] | R⊆R−1 | ∀x∈X∀y∈X[xRy⟹yRx] | (example, equality) |
| Transitive[1] | R∘R⊆R | ∀x,y,z∈X[(xRy∧yRz)⟹xRz] | (example, equality, <) |
| Antisymmetric[3] (AKA Identitive[1]) |
R∩R−1⊆idX | ∀x∈X∀y∈X[(xRy∧yRx)⟹x=y] |
TODO: What about a relation like 1r2 1r1 2r1 and 2r2 |
| Connected[1] | R∪R−1=X×X |
TODO: Work out what this means | |
| Asymmetric[1] | R⊆∁(R−1) | ∀x∈X∀y∈X[xRy⟹(y,x)∉R] | Like < (see: Contrapositive) |
| Right-unique[1] | R−1∘R⊆idX | ∀x,y,z∈X[(xRy∧xRz)⟹y=z] | This is the definition of a function |
| Left-unique[1] | R∘R−1⊆idX | ∀x,y,z∈X[(xRy∧zRy)⟹x=z] | |
| Mutually unique[1] | Both right and left unique |
TODO: Investigate |
Examples of binary relations
Notes
- Jump up ↑ A binary relation should be assumed if just relation is specified
References
- ↑ Jump up to: 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
- Jump up ↑ Types and Programming Languages - Benjamin C. Peirce
- Jump up ↑ Real and Abstract Analysis - Edwin Hewitt and Karl Stromberg
| |||||||||||
