# Partial Order Relation

**DEFINITION1:** Let be a set and . If the relation is reflexive, antisymmetric and transitive, then the relation is called a "partial order relation" and denoted by in general. If "" is a partial order relation over a set , then is called "partially ordered set" or shortly "poset".

**DEFINITION2:** Let and are elements of a partially ordered set . If it holds “”, then and are called “comparable”. Otherwise they are called “incomparable”.

**DEFINITION3:** If and are comparable for all in a partially ordered set , then the relation is called a “total order” and the set is called a “totally ordered set” or “linearly ordered set”.

**DEFINITION4:** Let be a partially ordered set and . If is a totally ordered set, then is called a “chain” in .

**DEFINITION5:** Let be a partially ordered set and . If there exists an element satisfying for all , then is called the maximum of , and if there exists an element satisfying for all , then is called the minimum of . The minimum and the maximum of are denoted by and respectively.

**DEFINITION6:** If every non-empty subset of a partially ordered set has a minimum, then is called a “well order”, and is called a “well ordered set”.

**PROPOSITION1:** Every well ordered set is a totally ordered set.

**EXAMPLE1:** The set of the real numbers with well-known “at-most relation” () is totally ordered but not well ordered because non-empty subset has no a minimum. Similarly, the set of the integers is totally ordered but not well ordered because this set has no a minimum.

**EXAMPLE2:** The set of natural numbers is well ordered. Note that any non-empty subset of a well ordered set is also well ordered.

**EXAMPLE3:** Let be a set and . Hence, the set with the inclusion relation “” is partially ordered set. The inclusion relation is, reflexive because every set is a subset of itself, antisymmetric because and transitive because (). Consequently, the inclusion is a partial order. Assume the set has two distinct elements such as , and choose , . Then, isn’t totally ordered because and . I.e., if the set has more than one element, then has at least two incomparable elements. Besides, is totally ordered if and only if . Choose . Since has infinitely many elements, isn’t totally ordered. However, we can give an example of chain in : Choose , , , , , , . If we define , then is a chain of because .

**EXAMPLE4:** For , define . The relation is called “division”. ( can be divided by ). The division is, reflexive because every natural number can be divided by itself, antisymmetric because and transitive because . Consequently, the division is a partial order. Since and , the numbers and are incomparable each other, i.e., isn’t a totally ordered set with the division relation. If we want to define a chain in , we can examine the subset for the arbitrary constant . It is clear that the subset is a chain of .

**DEFINITION7:** Let be a partially ordered set, and . If for all , then the element is called an upper bound of the set and if for all , then the element is called a lower bound of the set . If a subset of has an upper bound and a lower bound, then this set is called a "bounded set".

Note that don't have to be chosen in . An upper bound or a lower bound of a set don’t have to be included by this set. If an upper bound or a lower bound of a set were included by this set, then we would use the term “maximum” instead of the term “upper bound” and the term “minimum” instead of the term “lower bound”. This definitions shouldn’t be confused with the definitions of the maximum and the minimum. If there is a minimum or maximum of a set, then it’s unique. However, the number of all the lower bounds or all the upper bounds of a set may be more than one, even infinity. Besides, if there is the maximum of a set, then it’s already an upper bound of this set. However, there may be one or more upper bounds of a set although there isn’t the maximum of this set. The same of the last truth is also valid for the minimum. We will explain what we say above by the help of an example:

**EXAMPLE5:** Let and . There isn’t the maximum of . However, is an upper bound of because for all . Similarly, is also an upper bound of because for all . Let denote the set of all the upper bounds of and also denote the set of all the lower bounds. It is clear that and . As is seen, has infinitely many upper bounds and lower bounds although there isn’t its minimum and maximum.

**DEFINITION8:** Let be a partially ordered set and . is the set of all the upper bounds of and is the set of all the lower bounds of . If there is the minimum of , then this minimum is called the "supremum" of and if there is the maximum of , then this maximum is called the "infimum" of . If there is a supremum or infimum of , then it’s obviously unique. The supremum and the infimum of a set are denoted by and respectively. The supremum of a set is the least upper bound of this set and the infimum of a set is the greatest lower bound of this set.

**PROPERTIES OF SUPREMUM AND INFIMUM:**

**1)** If there is a supremum or infimum of a set, then it’s unique.

**2)** If there is the maximum of a set, then the maximum is also the supremum of this set. Similarly, if there is the minimum of a set, then the minimum is also the infimum of this set. However, the opposite of this isn’t true in general. I.e., there may not be the maximum of a set although there is the supremum of this set. Similarly, there may not be the minimum of a set although there is the infimum of this set. (See: example6)

**3)** Any subset of the real numbers has the infimum and the supremum.

**4)** Let and . Then,

**(i)**

a) ,

b) .

**(ii)**

a) ,

b) .

**5)** Let and . Then,

**(i)**

a) ,

b)

**(ii)**

a) ,

b)

**6)** Let and . We can give the following property for the people who know the topology:

**(i)**

a) ,

b) .

**(ii)**

a) ,

b) .

(Where denotes the closure of ).

**EXAMPLE6:** It was mentioned that has no minimum and maximum in example5. The set of all the upper bounds of is . Hence, the equality is true. Similarly, the equality is also true.

**EXAMPLE7:** Let be a set and . As it is well known, is a partially ordered. , . Now, let’s analyse and . I.e., we will find the supremum and the infimum of two sets and . Since and , the set is an upper bound of the set . Assume that is another upper bound of . Then, and . So, is obtained. Consequently, the least upper bound of is the union of and i.e., . Similarly, one can easily prove the equality . Let be an index set and be a family of sets of . Hence, the following equalities are true:

and .

The proof of above equalities is the same of the proof for two sets.

**EXAMPLE8:** We know that the natural numbers is a partially ordered set with the division. Let’s show that and for (lcm: least common multiple, gcd: greatest common divisor). First, we will prove for the supremum: Since and , the number is an upper bound of the set . Assume that the natural number is another upper bound of . Then, and . So, . Consequently, the least upper bound of two natural numbers is their least common multiple. Now, we will prove for the infimum: Since and , the number is a lower bound of the set . Assume that the natural number is another lower bound of . Then, and . So, . Consequently, the greatest lower bound of two natural numbers is their greatest common divisor.

**DEFINITION9:** Let a partially ordered set and .

**(i)** is called a maximal element of if has no an element being greater than .

**(ii)** is called a minimal element of if has no an element being lower than .

**PROPERTIES OF MAXIMAL AND MINIMAL ELEMENTS:**

**1)** Another expression for the maximal element: Let be a maximal element of and . Hence, and are incomparable each other or . Another expression for the minimal element: Let be a minimal element of and . Hence, and are incomparable each other or .

**2)** Any maximal or minimal element of is in .

**3)** Although a set has a maximal element, there may not be the maximum element of this set. Similarly, although a set has a minimal element, there may not be the minimum element of this set.

**4)** The number of minimal or maximal elements of a set may be more than one.

**5)** If is the maximum element of a set, then is also a maximal element of this set and this set has no another maximal element. Similarly, if is the minimum element of a set, then is also a minimal element of this set and this set has no another minimal element.

**6)** Let be a chain of a partially ordered set. If is a maximal element of , then is also the maximum element of and has no another maximal element. Similarly, if is a minimal element of , then is also the minimum element of and has no another minimal element.

**EXAMPLE9:** We know that the natural numbers is a partially ordered set with the division. Choose . Since has no element divided by 12 except for 12, the number 12 is a maximal element of . Similarly, the number 15 is also a maximal element of . Since has no element dividing 2 except for 2, the number 2 is a minimal element of . Similarly, the numbers 3 and 5 are also two minimal elements of . has no element being neither a maximal element nor a minimal element except for the number 4. See the following diagram:

Besides, since and , and .

**ZORN’S LEMMA:** Every partially ordered set in which every chain has an upper bound contains at least one maximal element.