Difference between revisions of "Relation"

Revision as of 22:21, 4 March 2015 (view source) Alec (Talk | contribs) m ← Older edit		Revision as of 16:40, 5 March 2015 (view source) Alec (Talk | contribs) m Newer edit →
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 $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.