Hi all, This Blog is an English archive of my PhD experience in Imperial College London, mainly logging my research and working process, as well as some visual records.

Wednesday, 29 August 2007

Basic Concepts: Preorder, Partial Order, Total Order, Supremum

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 ab and ba then a = b (antisymmetry)

if ab and bc then ac (transitivity)

ab or ba (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 \lesssimis a preorder, or quasiorder, if it is reflexive and transitive, i.e., for all a, b and c in P, we have that:

a \lesssima (reflexivity)

if a \lesssimb and b \lesssimc then a \lesssimc (transitivity)

A set that is equipped with a preorder is called a preordered set.

If a preorder is also antisymmetric, that is, a \lesssimb and b \lesssima implies a = b, then it is a partial order. In that case there is no need for the special symbol \lesssimand we can just write ≤.

On the other hand, if it is symmetric, that is, if a \lesssimb implies b \lesssima, 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: