1) Total Order: a total order, linear order, simple order, or (non-strict) ordering on a set X is any binary relation on X that is antisymmetric, transitive, and total. This means that if we denote one such relation by ≤ then the following statements hold for all a, b and c in X:
if a ≤ b and b ≤ a then a = b (antisymmetry)
if a ≤ b and b ≤ c then a ≤ c (transitivity)
a ≤ b or b ≤ a (totality or completeness)
A set paired with an associated total order on it is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain.
2) Partial Order: is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., for all a, b, and c in P, we have that:
- a ≤ a (reflexivity);
- if a ≤ b and b ≤ a then a = b (antisymmetry);
- if a ≤ b and b ≤ c then a ≤ c (transitivity).
In other words, a partial order is an antisymmetric preorder.
A set with a partial order is called a partially ordered set (also called a poset).
3) Preorder: Consider some set P and a binary relation on P. Then is a preorder, or quasiorder, if it is reflexive and transitive, i.e., for all a, b and c in P, we have that:
a a (reflexivity)
if a b and b c then a c (transitivity)
A set that is equipped with a preorder is called a preordered set.
If a preorder is also antisymmetric, that is, a b and b a implies a = b, then it is a partial order. In that case there is no need for the special symbol and we can just write ≤.
On the other hand, if it is symmetric, that is, if a b implies b a, then it is an equivalence relation.
4) Supremum: given a subset S of a partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to each element of S. Consequently, the supremum is also referred to as the least upper bound, lub or LUB. If the supremum exists, it may or may not belong to S. If the supremum exists, it is unique.
No comments:
Post a Comment