Difference between revisions of "Relation"
m |
m |
||
| Line 2: | Line 2: | ||
[[Function|Functions]], [[Equivalence relation|equivalence relations]] and [[Ordering|orderings]] are special kinds of relation | [[Function|Functions]], [[Equivalence relation|equivalence relations]] and [[Ordering|orderings]] are special kinds of relation | ||
| + | {{Refactor notice}} | ||
| + | ==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: | ||
| + | * {{M|\mathcal{R}\subseteq X\times Y}} | ||
| + | We say that {{M|\mathcal{R} }} is a ''relation in {{M|X}}''<ref name="Analysis"/> if: | ||
| + | * {{M|\mathcal{R}\subseteq X\times X}} (note that {{M|\mathcal{R} }} is sometimes<ref name="Analysis"/> called a ''graph'') | ||
| + | ** For example {{M|<}} is a relation in the set of {{M|\mathbb{Z} }} (the integers) | ||
| + | |||
| + | If {{M|(x,y)\in\mathcal{R} }} then we: | ||
| + | * Say: ''{{M|x}} is in relation {{M|\mathcal{R} }} with {{M|y}}'' | ||
| + | * Write: {{M|x\mathcal{R}y}} for short. | ||
| + | ==Operations== | ||
| + | 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}} | ||
| + | {| class="wikitable" border="1" | ||
| + | |- | ||
| + | ! Name | ||
| + | ! Notation | ||
| + | ! Definition | ||
| + | |- | ||
| + | | NO IDEA | ||
| + | | {{M|1=P_X\mathcal{R} }}<ref name="Analysis"/> | ||
| + | | {{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="Analysis"/> | ||
| + | | {{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="Analysis"/> | ||
| + | | {{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== | ||
| + | # The ''empty relation''<ref name="Analysis"/>, {{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 ''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\} }} | ||
| + | #* This is also known as<ref name="Analysis"/> ''the diagonal of the square {{M|X\times X}}'' | ||
| + | |||
| + | ==Types of relation== | ||
| + | Here {{M|\mathcal{R}\subseteq X\times X}} | ||
| + | {| class="wikitable" border="1" | ||
| + | |- | ||
| + | ! Name | ||
| + | ! Set relation | ||
| + | ! Statement | ||
| + | ! Notes | ||
| + | |- | ||
| + | ! Reflexive<ref name="Analysis"/> | ||
| + | | {{M|\text{id}_X\subset\mathcal{R} }} | ||
| + | | {{M|\forall x\in X[x\mathcal{R}x]}} | ||
| + | | Every element is related to itself (example, equality) | ||
| + | |- | ||
| + | ! Symmetric<ref name="Analysis"/> | ||
| + | | {{M|\mathcal{R}\subset\mathcal{R}^{-1} }} | ||
| + | | {{M|\forall x\in X\forall y\in X[x\mathcal{R}y\implies y\mathcal{R}x]}} | ||
| + | | (example, equality) | ||
| + | |- | ||
| + | ! Transitive<ref name="Analysis"/> | ||
| + | | {{M|\mathcal{R}\circ\mathcal{R}\subset\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|<}}) | ||
| + | |- | ||
| + | ! Identitive<ref name="Analysis"/> | ||
| + | | {{M|\mathcal{R}\cap\mathcal{R}^{-1}\subset\text{id}_X}} | ||
| + | |} | ||
| + | {{Todo|See<ref name="Analysis"/> page 8}} | ||
| + | |||
| + | ==References== | ||
| + | <references/> | ||
| + | |||
| + | =OLD PAGE= | ||
==Notation== | ==Notation== | ||
Rather than writing {{M|(x,y)\in R}} to say {{M|x}} and {{M|y}} are related we can instead say {{M|xRy}} | Rather than writing {{M|(x,y)\in R}} to say {{M|x}} and {{M|y}} are related we can instead say {{M|xRy}} | ||
Revision as of 21:36, 21 June 2015
A set [ilmath]R[/ilmath] is a binary relation if all elements of [ilmath]R[/ilmath] are ordered pairs. That is for any [ilmath]z\in R\ \exists x\text{ and }y:(x,y)[/ilmath]
Functions, equivalence relations and orderings are special kinds of relation
Contents
Definition
A relation [ilmath]\mathcal{R} [/ilmath] between two sets is a subset of the Cartesian product of two sets[1], 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\subset\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}\subset\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}\subset\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]) |
| Identitive[1] | [ilmath]\mathcal{R}\cap\mathcal{R}^{-1}\subset\text{id}_X[/ilmath] |
TODO: See[1] page 8
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 Analysis - Part I: Elements - Krzysztof Maurin
OLD PAGE
Notation
Rather than writing [ilmath](x,y)\in R[/ilmath] to say [ilmath]x[/ilmath] and [ilmath]y[/ilmath] are related we can instead say [ilmath]xRy[/ilmath]
Basic terms
Proof that domain, range and field exist may be found here
Domain
The set of all [ilmath]x[/ilmath] which are related by [ilmath]R[/ilmath] to some [ilmath]y[/ilmath] is the domain.
[math]\text{Dom}(R)=\{x|\exists\ y: xRy\}[/math]
Range
The set of all [ilmath]y[/ilmath] which are a relation of some [ilmath]x[/ilmath] by [ilmath]R[/ilmath] 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 [ilmath]X[/ilmath] 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 [ilmath]R[/ilmath] in [ilmath]A[/ilmath] is symmetric if for all [ilmath]a,b\in A[/ilmath] we have that [ilmath]aRb\implies bRa[/ilmath] - a property of equivalence relations
Antisymmetric
A binary relation [ilmath]R[/ilmath] in [ilmath]A[/ilmath] is antisymmetric if for all [ilmath]a,b\in A[/ilmath] we have [math]aRb\text{ and }bRA\implies a=b[/math]
Symmetric implies elements are related to each other, antisymmetric implies only the same things are related to each other.
Reflexive
For a relation [ilmath]R[/ilmath] and for all [ilmath]a\in A[/ilmath] we have [ilmath]aRa[/ilmath] - [ilmath]a[/ilmath] is related to itself.
Transitive
A relation [ilmath]R[/ilmath] in [ilmath]A[/ilmath] is transitive if for all [ilmath]a,b,c\in A[/ilmath] we have [math][aRb\text{ and }bRc\implies aRc][/math]
Asymmetric
A relation [ilmath]S[/ilmath] in [ilmath]A[/ilmath] is asymmetric if [ilmath]aSb\implies(b,a)\notin S[/ilmath], for example [ilmath]<[/ilmath] has this property, we can have [ilmath]a<b[/ilmath] or [ilmath]b<a[/ilmath] but not both.
