page1
Chapter 9 Formulas / Theorems sheet
Properties of relations:
A relation R on set A is reflexive if (a,a)  R for every a  A.
A relation R on set A is irreflexive if (a,a)  R for every a  A.
A relation R on set A is symmetric if (b,a)  R whenever (a,b)  R, for all a, b  A.
A relation R on set A is antisymmetric if whenever (b,a)  R and (a,b)  R, then a=b, for all a, b  A.
A relation R on set A is asymmetric if (a,b)  R implies that (b,a)  R.
A relation R on set A is transitive if whenever (a,b)  R and (b,c)  R, then (a,c)  R , for all a, b  A.
Some correlations:
If a relation is reflexive, then it is not asymmetric. Irreflexive is not opposite of reflexive.
Asymmetric is not opposite of symmetric. Antisymmetric is not opposite of symmetric.
Let R be a relation on set A. The powers Rn , n=1,2,3,...
are defined recursively by R1 = R
Rn+1 = Rn ◦ R
A relation on a set A is called an equivalence relation if it is reflexive, symmetric and transitive.
Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a. denotation: [a]R equivalence class of a , or [a]
If b Î [a]R , then b is called representative of this equivalence class.
A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. (S,R) is called a partially ordered set or poset.
The elements a and b of the poset (S,R) are called comparable if either aRb or bRa.
Otherwise they are called incomparable.
If (S,R) is a poset, and every two elements of S are comparable, then S is called a totally ordered or linearly ordered set, and R is called a total order or a linear order.
A totally ordered set is called a chain.
a is maximal in the poset (S, R) if there is no b Î S such that a R b.
a is minimal in the poset (S, R) if there is no b Î S such that b R a.
a is the greatest element of the poset (S, R) if b R a for all b Î S . The greatest element is unique if it exists.
a is the least element of the poset (S, R) if a R b for all b Î S . The least element is unique if it exists.
If u is an element of S such that a R u for all elements a Î A, then u is called the upper bound of A.
If l is an element of S such that l R a for all elements a Î A, then l is called the lower bound of A.