Relation

From Maths
Revision as of 16:40, 5 March 2015 by Alec (Talk | contribs)

Jump to: navigation, search

A set R is a binary relation if all elements of R are ordered pairs. That is for any z\in R\ \exists x\text{ and }y:(x,y)


Notation

Rather than writing (x,y)\in R to say x and y are related we can instead say xRy

Basic terms

Proof that domain, range and field exist may be found here

Domain

The set of all x which are related by R to some y is the domain.

\text{Dom}(R)=\{x|\exists\ y: xRy\}

Range

The set of all y which are a relation of some x by R is the range.

\text{Ran}(R)=\{y|\exists\ x: xRy\}

Field

The set \text{Dom}(R)\cup\text{Ran}(R)=\text{Field}(R)

Relation in X

To be a relation in a set X we must have \text{Field}(R)\subset X

Images of sets

Image of A under R

This is just the set of things that are related to things in A, denoted R[A]

R[A]=\{y\in\text{Ran}(R)|\exists x\in A:xRa\}

Inverse image of B under R

As you'd expect this is the things that are related to things in B, denoted R^{-1}[B]

R^{-1}[B]=\{x\in\text{Dom}(R)|\exists y\in B:xRy\}

Important lemma

It is very important to know that the inverse image of B under R is the same as the image under R^{-1}


Properties of relations

Symmetric

A relation R in A is symmetric if for all a,b\in A we have that aRb\implies bRa - a property of equivalence relations

Antisymmetric

A binary relation R in A is antisymmetric if for all a,b\in A we have aRb\text{ and }bRA\implies a=b
Symmetric implies elements are related to each other, antisymmetric implies only the same things are related to each other.

Reflexive

For a relation R and for all a\in A we have aRa - a is related to itself.

Transitive

A relation R in A is transitive if for all a,b,c\in A we have [aRb\text{ and }bRc\implies aRc]

Asymmetric

A relation S in A is asymmetric if aSb\implies(b,a)\notin S, for example < has this property, we can have a<b or b<a but not both.