A relationship that is Reflexive, Symmetric and Transitive is called an equivalance relation. Two elements that are related by an equivalance relationship are said to be equivalent and form an equivalence class indicated by [a]. The set of equivalence classes is called a quotient set.
The following are then equivelent
a R b
[a] = [b] equivalence classes are either the same
[a] ^ [b] <> Ø or disjoint
Example 1 (congruence classes modulo m)
Let R ={(a,b) | a~b (mod n)} and let b=0 and n=5
This gives us a~0 (mod 5), the set of values of a divisible by 5.
Solving this, we get the equivelence class for [0] which is the set {..., -10, -5, 0, 5 , 10 ...}
Let b=1
This gives us a ~ 1 (mod 5), the set of values of a - 1 divisible by 5
Solving this, we get the equivelence class for [1] which is the set {..., -9, -4, 0, 6 , 11 ...}
Equivalance classes partition a set. In the example above, there are 5 equivalance classes: [0], [1], [2], [3], and [4]. They divide, in this case, the set of integers into 5 disjoint sets.
A relationship R on a set S that is Reflexive, Antisymmetric and Transitive is called an partial ordering. A set S with aprtial ordering R is called a partially ordered set or poset. Elements a and b are comparable if a=<b or b=<a. If every pairing is comparable, then the relation is a total ordering, linearly ordered or a chain.
a is maximal if there is no b where a<b. There may be more than 1 in a poset. (12, 20 and 25) a is minimal if there is no b where b<a. There may be more than 1 in a poset. ( 2 and 5) a is the greatest element if b=<a for all b's. There are none if there are several maximal elements. If it exists, it is unique. a is the least element if a=<b for all b's. There are none if there are several minimal elements. If it exists, it is unique. u is an upper bound if a=<u for all a's. The upper bounds of {b,d,g} are g and h. l is an lower bound if l=<a for all a's.The lower bounds of {b,g,d} are a and b x is the least upper bound if x is the upper bound element which is less than every other upper bound. The least upper bound of {b,d,g} is g. x is rthe greatest lower bound if x is the lower bound element that is greater than every other lower bound. The greatest lower bound of {b, d, g} is b