Relation

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

(Unknown grade)

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, that is:

• [ilmath]\mathcal{R}\subseteq X\times Y[/ilmath]

We say that [ilmath]\mathcal{R} [/ilmath] is a relation in [ilmath]X[/ilmath] if:

• [ilmath]\mathcal{R}\subseteq X\times X[/ilmath] (note that [ilmath]\mathcal{R} [/ilmath] is sometimes 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]	[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]	[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]	[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, [ilmath]\emptyset\subset X\times X[/ilmath] is of course a relation
2. The total relation, [ilmath]\mathcal{R}=X\times X[/ilmath] that relates everything to everything
3. The identity relation, [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 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	[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	[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	[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	[ilmath]\mathcal{R}\cap\mathcal{R}^{-1}\subset\text{id}_X[/ilmath]

---

TODO: See page 8

---

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.