Revision as of 21:36, 21 June 2015 (view source) Alec (Talk | contribs) m ← Older edit		Revision as of 17:25, 28 August 2015 (view source) Alec (Talk | contribs) m (→‎Types of relation) Newer edit →
Line 51:		Line 51:
	|-		|-
	! Reflexive<ref name="Analysis"/>		! Reflexive<ref name="Analysis"/>
−	| {{M|\text{id}_X\subset\mathcal{R} }}	+	| {{M|\text{id}_X\subseteq\mathcal{R} }}
	| {{M|\forall x\in X[x\mathcal{R}x]}}		| {{M|\forall x\in X[x\mathcal{R}x]}}
	| Every element is related to itself (example, equality)		| Every element is related to itself (example, equality)
	|-		|-
	! Symmetric<ref name="Analysis"/>		! Symmetric<ref name="Analysis"/>
−	| {{M|\mathcal{R}\subset\mathcal{R}^{-1} }}	+	| {{M|\mathcal{R}\subseteq\mathcal{R}^{-1} }}
	| {{M|\forall x\in X\forall y\in X[x\mathcal{R}y\implies y\mathcal{R}x]}}		| {{M|\forall x\in X\forall y\in X[x\mathcal{R}y\implies y\mathcal{R}x]}}
	| (example, equality)		| (example, equality)
	|-		|-
	! Transitive<ref name="Analysis"/>		! Transitive<ref name="Analysis"/>
−	| {{M|\mathcal{R}\circ\mathcal{R}\subset\mathcal{R} }}	+	| {{M|\mathcal{R}\circ\mathcal{R}\subseteq\mathcal{R} }}
	| {{M|\forall x,y,z\in X[(x\mathcal{R}y\wedge y\mathcal{R}z)\implies x\mathcal{R}z]}}		| {{M|\forall x,y,z\in X[(x\mathcal{R}y\wedge y\mathcal{R}z)\implies x\mathcal{R}z]}}
	| (example, equality, {{M|<}})		| (example, equality, {{M|<}})
	|-		|-
	! Identitive<ref name="Analysis"/>		! Identitive<ref name="Analysis"/>
−	| {{M|\mathcal{R}\cap\mathcal{R}^{-1}\subset\text{id}_X}}	+	| {{M|\mathcal{R}\cap\mathcal{R}^{-1}\subseteq\text{id}_X}}
		+	| {{M|1=\forall x\in X\forall y\in X[(x\mathcal{R}y\wedge y\mathcal{R}x)\implies x=y]}}
		+	| {{Todo|What about a relation like 1r2 1r1 2r1 and 2r2}}
		+	|-
		+	! Connected<ref name="Analysis"/>
		+	| {{M|1=\mathcal{R}\cup\mathcal{R}^{-1}=X\times X}}
		+	|
		+	| {{Todo|Work out what this means}}
		+	|-
		+	! Asymmetric<ref name="Analysis"/>
		+	| {{M|1=\mathcal{R}\subseteq\complement(\mathcal{R}^{-1})}}
		+	| {{M|1=\forall x\in X\forall y\in X[x\mathcal{R}y\implies (y,x)\notin\mathcal{R}]}}
		+	| Like {{M|<}} (see: [[Contrapositive]])
		+	|-
		+	! Right-unique<ref name="Analysis"/>
		+	| {{M|1=\mathcal{R}^{-1}\circ\mathcal{R}\subseteq\text{id}_X}}
		+	| {{M|1=\forall x,y,z\in X[(x\mathcal{R}y\wedge x\mathcal{R}z)\implies y=z]}}
		+	| This is the definition of a [[function]]
		+	|-
		+	! Left-unique<ref name="Analysis"/>
		+	| {{M|1=\mathcal{R}\circ\mathcal{R}^{-1}\subseteq\text{id}_X}}
		+	| {{M|1=\forall x,y,z\in X[(x\mathcal{R}y\wedge z\mathcal{R}y)\implies x=z]}}
		+	|
		+	|-
		+	! Mutually unique<ref name="Analysis"/>
		+	| Both right and left unique
		+	|
		+	| {{Todo|Investigate}}
	|}		|}
−	{{Todo|See<ref name="Analysis"/> page 8}}
	==References==		==References==

---

Revision as of 17:25, 28 August 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)$

Functions, equivalence relations and orderings are special kinds of relation

Definition

A relation $\mathcal{R}$ between two sets is a subset of the Cartesian product of two sets^[1], that is:

• $\mathcal{R}\subseteq X\times Y$

We say that $\mathcal{R}$ is a relation in $X$^[1] if:

• $\mathcal{R}\subseteq X\times X$ (note that $\mathcal{R}$ is sometimes^[1] called a graph)
  • For example $<$ is a relation in the set of $\mathbb{Z}$ (the integers)

If $(x,y)\in\mathcal{R}$ then we:

• Say: $x$ is in relation $\mathcal{R}$ with $y$
• Write: $x\mathcal{R}y$ for short.

Operations

Here $\mathcal{R}$ is a relation between $X$ and $Y$, that is $\mathcal{R}\subseteq X\times Y$, and $\mathcal{S}\subseteq Y\times Z$

Name	Notation	Definition
NO IDEA	$P_X\mathcal{R}$[1]	$P_X\mathcal{R}=\{x\in X\vert\ \exists y:\ x\mathcal{R}y\}$ - a function is (among other things) a case where $P_Xf=X$
Inverse relation	$\mathcal{R}^{-1}$[1]	$\mathcal{R}^{-1}:=\{(y,x)\in Y\times X\vert\ x\mathcal{R}y\}$
Composing relations	$\mathcal{R}\circ\mathcal{S}$[1]	$\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]\}$

Simple examples of relations

1. The empty relation^[1], $\emptyset\subset X\times X$ is of course a relation
2. The total relation^[1], $\mathcal{R}=X\times X$ that relates everything to everything
3. The identity relation^[1], $\text{id}_X:=\text{id}:=\{(x,y)\in X\times X\vert x=y\}=\{(x,x)\in X\times X\vert x\in X\}$
   • This is also known as^[1] the diagonal of the square $X\times X$

Types of relation

Here $\mathcal{R}\subseteq X\times X$

Name	Set relation	Statement	Notes
Reflexive[1]	$\text{id}_X\subseteq\mathcal{R}$	$\forall x\in X[x\mathcal{R}x]$	Every element is related to itself (example, equality)
Symmetric[1]	$\mathcal{R}\subseteq\mathcal{R}^{-1}$	$\forall x\in X\forall y\in X[x\mathcal{R}y\implies y\mathcal{R}x]$	(example, equality)
Transitive[1]	$\mathcal{R}\circ\mathcal{R}\subseteq\mathcal{R}$	$\forall x,y,z\in X[(x\mathcal{R}y\wedge y\mathcal{R}z)\implies x\mathcal{R}z]$	(example, equality, $<$)
Identitive[1]	$\mathcal{R}\cap\mathcal{R}^{-1}\subseteq\text{id}_X$	$\forall x\in X\forall y\in X[(x\mathcal{R}y\wedge y\mathcal{R}x)\implies x=y]$	TODO: What about a relation like 1r2 1r1 2r1 and 2r2
Connected[1]	$\mathcal{R}\cup\mathcal{R}^{-1}=X\times X$		TODO: Work out what this means
Asymmetric[1]	$\mathcal{R}\subseteq\complement(\mathcal{R}^{-1})$	$\forall x\in X\forall y\in X[x\mathcal{R}y\implies (y,x)\notin\mathcal{R}]$	Like $<$ (see: Contrapositive)
Right-unique[1]	$\mathcal{R}^{-1}\circ\mathcal{R}\subseteq\text{id}_X$	$\forall x,y,z\in X[(x\mathcal{R}y\wedge x\mathcal{R}z)\implies y=z]$	This is the definition of a function
Left-unique[1]	$\mathcal{R}\circ\mathcal{R}^{-1}\subseteq\text{id}_X$	$\forall x,y,z\in X[(x\mathcal{R}y\wedge z\mathcal{R}y)\implies x=z]$
Mutually unique[1]	Both right and left unique		TODO: Investigate

References

1. ↑ ^{Jump up to: 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

OLD PAGE

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.