Difference between revisions of "Relation"
From Maths
(→Types of relation: Added anchor tags to table.) |
m (→Types of relation: fixing typo) |
||
| Line 51: | Line 51: | ||
| Every element is related to itself (example, equality) | | Every element is related to itself (example, equality) | ||
|- | |- | ||
| − | ! {{Anchor| | + | ! {{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]}} | ||
Latest revision as of 20:07, 20 April 2016
Contents
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
- The empty relation[1], [ilmath]\emptyset\subset X\times X[/ilmath] is of course a relation
- The total relation[1], [ilmath]\mathcal{R}=X\times X[/ilmath] that relates everything to everything
- 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
- ↑ A binary relation should be assumed if just relation is specified
References
- ↑ 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
- ↑ Types and Programming Languages - Benjamin C. Peirce
- ↑ Real and Abstract Analysis - Edwin Hewitt and Karl Stromberg
| |||||||||||
