Difference between revisions of "Relation"

From Maths
Jump to: navigation, search
m
m
Line 36: Line 36:
 
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>
 
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 {{M|R}} in {{M|A}} is symmetric if for all {{M|a,b\in A}} we have that {{M|aRb\implies bRa}} - a property of [[Equivalence relation|equivalence relations]]
 +
===Antisymmetric===
 +
A binary relation {{M|R}} in {{M|A}} is antisymmetric if for all {{M|a,b\in A}} we have <math>aRb\text{ and }bRA\implies a=b</math><br/>
 +
Symmetric implies elements are related to each other, antisymmetric implies only the same things are related to each other.
 +
===Reflexive===
 +
For a relation {{M|R}} and for all {{M|a\in A}} we have {{M|aRa}} - {{M|a}} is related to itself.
 +
===Transitive===
 +
A relation {{M|R}} in {{M|A}} is transitive if for all {{M|a,b,c\in A}} we have <math>[aRb\text{ and }bRc\implies aRc]</math>
 +
===Asymmetric===
 +
A relation {{M|S}} in {{M|A}} is asymmetric if {{M|aSb\implies(b,a)\notin S}}, for example {{M|<}} has this property, we can have {{M|a<b}} or {{M|b<a}} but not both.
 
{{Definition|Set Theory}}
 
{{Definition|Set Theory}}

Revision as of 16:40, 5 March 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]


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.