Mathematics-Online lexicon: Properties of Relations

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

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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)

[Examples] [Links]

automatically generated 6/19/2007