Mathematics-Online course: Basic Mathematics-Sets-Properties of Relations

	[home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff]
	Mathematics-Online course: Basic Mathematics - Sets
	Properties of Relations

[previous page] [next page]

[table of contents][page overview]

A (binary) relation $R\subseteq A^2$ on a set

is called

reflexive, if each element is related to itself: $\forall a\in A: (a,a) \in R$
symmetric, if the order of the elements is irrelevant: $(a,b) \in R \Rightarrow (b,a) \in R$
asymmetric, if symmetry implies the identity of the respective elements: $(a,b) \in R \land (b,a) \in R \Rightarrow a=b$
transitive, if the middle element of a chain can be removed: $(a,b) \in R \land (b,c) \in R \Rightarrow (a,c)\in R$
complete, if any two distinct elements are related to each other in at least one direction: $\forall a,b\in A: (a,b) \in R \lor (b,a) \in R$

A reflexive, symmetric and transitive relation is called an equivalence relation, usually symbolized by $a\sim b$ instead of $a \operatorname{R}b$ . An equivalence relation divides a set in disjoint subsets (equivalence classes), with any two elements of a particular subset being related (equivalent) to each other, while two elements of distinct subsets are not related to one another.

A reflexive, asymmetric and transitive relation is called a partial order, symbolized as $a \leq b$ instead of $a \operatorname{R}b$ . If a partial order is complete, it is called a (total) order; is then ordered by $\leq$ .

(Authors: Hörner/Abele)

The inclusion of sets $\subseteq$ is a partial order in the power set ${\cal P}(M)$ of a set

since it is

reflexive ( $A\subseteq A$ ),

asymmetric ( $A\subseteq B \land B \subseteq A \Rightarrow A=B$ ),

and

transitive ( $A\subseteq B\subseteq C\Rightarrow A\subseteq C$ ).

However, if contains more than one element, then the inclusion is not an order:

$\displaystyle a,b \in M, a\neq b: \{a\} \not\subseteq \{b\} \land \{b\} \not\subseteq \{a\} \,,$

i.e. it is not complete.

The relation ,,has an equal number of elements `` is an equivalence relation in the power set ${\cal P}(M)$ of a finite set since it is

reflexive ( $\vert A\vert=\vert A\vert$ ),

symmetric ( $\vert A\vert=\vert B\vert \Rightarrow \vert B\vert=\vert A\vert$ ),

and

transitive ( $\vert A\vert=\vert B\vert=\vert C\vert \Rightarrow \vert A\vert =\vert C\vert$ ).

(Authors: Hörner/Abele)

[previous page] [next page]

[table of contents][page overview]

automatically generated 10/31/2008