Relation

From Maths
Revision as of 17:32, 28 August 2015 by Alec (Talk | contribs) (Types of relation)

Jump to: navigation, search

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

This page is currently being refactored (along with many others)
Please note that this does not mean the content is unreliable. It just means the page doesn't conform to the style of the site (usually due to age) or a better way of presenting the information has been discovered.

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

  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[2]
(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


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 I: Elements - Krzysztof Maurin
  2. Real and Abstract Analysis - Edwin Hewitt and Karl Stromberg

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.