Partial Order Relation

On September 18, 2010, in Analysis, by ufukkaya

DEFINITION1: Let $X$ be a set and $R\subset{X\times{X}}$ . If the relation $R$ is reflexive, antisymmetric and transitive, then the relation $R$ is called a “partial order relation” and denoted by $R=\le$ in general. If “ $\le$ ” is a partial order relation over a set $X$ , then $(X,\le)$ is called “partially ordered set” or shortly “poset”.

DEFINITION2: Let $x$ and $y$ are elements of a partially ordered set $X$ . If it holds “ $x\le{y}\lor{y\le{x}}$ ”, then $x$ and $y$ are called “comparable”. Otherwise they are called “incomparable”.

DEFINITION3: If $x$ and $y$ are comparable for all $x,y$ in a partially ordered set $(X,\le)$ , then the relation $\le$ is called a “total order” and the set $X$ is called a “totally ordered set” or “linearly ordered set”.

DEFINITION4: Let $(X,\le)$ be a partially ordered set and $A\subset{X}$ . If $(A,\le)$ is a totally ordered set, then $A$ is called a “chain” in $X$ .

DEFINITION5: Let $(X,\le)$ be a partially ordered set and $A\subset{X}$ . If there exists an element $a^{*}\in{A}$ satisfying $a\le{a^{*}}$ for all $a\in{A}$ , then $a^{*}$ is called the maximum of $A$ , and if there exists an element $a_{*}\in{A}$ satisfying $a_{*}\le{a}$ for all $a\in{A}$ , then $a_{*}$ is called the minimum of $A$ . The minimum and the maximum of $A$ are denoted by $\min{A}$ and $\max{A}$ respectively.

DEFINITION6: If every non-empty subset of a partially ordered set $(X,\le)$ has a minimum, then $\le$ is called a “well order”, and $(X,\le)$ 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” ( $\le$ ) is totally ordered but not well ordered because non-empty subset $(0,1)$ 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 $E$ be a set and $X=\mathbf{P}(E)$ . Hence, the set $X$ with the inclusion relation “ $\subset$ ” is partially ordered set. The inclusion relation is, reflexive because every set is a subset of itself, antisymmetric because $A\subset{B}\land{B\subset{A}}\Rightarrow{A=B}$ and transitive because $A\subset{B}\land{B\subset{C}}\Rightarrow{A\subset{C}}$ ( $A,B,C\subset{E}$ ). Consequently, the inclusion is a partial order. Assume the set $E$ has two distinct elements such as $a$ , $b$ and choose $A=\{a\}$ , $B=\{b\}$ . Then, $(\mathbf{P}(E),\subset)$ isn’t totally ordered because $A\nsubseteq{B}$ and $B\nsubseteq{A}$ . I.e., if the set $E$ has more than one element, then $\mathbf{P}(E)$ has at least two incomparable elements. Besides, $(\mathbf{P}(E),\subset)$ is totally ordered if and only if $\arrowvert{E}\arrowvert\le{1}$ . Choose $E=\mathbb{N}$ . Since $\mathbb{N}$ has infinitely many elements, $\mathbf{P}(\mathbb{N})$ isn’t totally ordered. However, we can give an example of chain in $\mathbf{P}(\mathbb{N})$ : Choose $A_{0}=\varnothing$ , $A_{1}=\{1\}$ , $A_{2}=\{1,2\}$ , $A_{3}=\{1,2,3\}$ , $\dots$ , $A_{n}=\{1,2,\dots,n\}$ , $\dots$ . If we define $F=\{A_{n}\:|\:n\in{\mathbb{N}}\}$ , then $F$ is a chain of $\mathbf{P}(\mathbb{N})$ because $A_{n}\subset{A_{m}}\Leftrightarrow{n\le{m}}$ .

EXAMPLE4: For $n,m\in{\mathbb{N}}$ , define $nRm\Leftrightarrow{n\arrowvert{m}}$ . The relation $R$ is called “division”. ( $n\arrowvert{m}\Leftrightarrow$ $m$ can be divided by $n$ $\Leftrightarrow{\exists{k}\in{\mathbb{N}}: m=k.n}$ ). The division is, reflexive because every natural number can be divided by itself, antisymmetric because $n\arrowvert{m}\land{m\arrowvert{n}}\Rightarrow{m=n}$ and transitive because $n\arrowvert{m}\land{m\arrowvert{k}}\Rightarrow{n\arrowvert{k}}$ . Consequently, the division is a partial order. Since $2\nmid{3}$ and $3\nmid{2}$ , the numbers $2$ and $3$ are incomparable each other, i.e., $\mathbb{N}$ isn’t a totally ordered set with the division relation. If we want to define a chain in $\mathbb{N}$ , we can examine the subset $F=\{n^k\:|\:k\in{\mathbb{N}}\}$ for the arbitrary constant $n>1$ . It is clear that the subset $F$ is a chain of $\mathbb{N}$ .

DEFINITION7: Let $(X,\le)$ be a partially ordered set, $A\subset{X}$ and $x_{0}\in{X}$ . If $a\le{x_{0}}$ for all $a\in{A}$ , then the element $x_{0}$ is called an upper bound of the set $A$ and if $x_{0}\le{a}$ for all $a\in{A}$ , then the element $x_{0}$ is called a lower bound of the set $A$ . If a subset of $X$ has an upper bound and a lower bound, then this set is called a “bounded set”.

Note that $x_{0}$ don’t have to be chosen in $A$ . 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 $X=\mathbb{R}$ and $A=(0,1)$ . There isn’t the maximum of $(0,1)$ . However, $1$ is an upper bound of $(0,1)$ because $a\le{1}$ for all $a\in{(0,1)}$ . Similarly, $12$ is also an upper bound of $(0,1)$ because $a\le{12}$ for all $a\in{(0,1)}$ . Let $A^{*}$ denote the set of all the upper bounds of $(0,1)$ and $A_{*}$ also denote the set of all the lower bounds. It is clear that $A^{*}=[1,+\infty)$ and $A_{*}=(-\infty,0]$ . As is seen, $(0,1)$ has infinitely many upper bounds and lower bounds although there isn’t its minimum and maximum.

DEFINITION8: Let $(X,\le)$ be a partially ordered set and $A\subset{X}$ . $A^{*}=\{x\in{X}\:|\:\forall{a}\in{A}, a\le{x}\}$ is the set of all the upper bounds of $A$ and $A_{*}=\{x\in{X}\:|\:\forall{a}\in{A}, x\le{a}\}$ is the set of all the lower bounds of $A$ . If there is the minimum of $A^{*}$ , then this minimum is called the “supremum” of $A$ and if there is the maximum of $A_{*}$ , then this maximum is called the “infimum” of $A$ . If there is a supremum or infimum of $A$ , then it’s obviously unique. The supremum and the infimum of a set $A$ are denoted by $\sup{A}$ and $\inf{A}$ 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.

THE 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 $X=\mathbb{R}, \varnothing\ne{A}\subset{\mathbb{R}}$ and $l,L\in{\mathbb{R}}$ . Then,

(i) $\sup{A}=L$ $\iff$

a) $\forall{a}\in{A}, a\le{L}$ ,

b) $\forall{\varepsilon}>0, \exists{a_{\varepsilon}}\in{A}: L-\varepsilon<a_{\varepsilon}$ .

(ii) $\inf{A}=l$ $\iff$

a) $\forall{a}\in{A}, l\le{a}$ ,

b) $\forall{\varepsilon}>0, \exists{a_{\varepsilon}}\in{A}: a_{\varepsilon}<l+\varepsilon$ .

5) Let $X=\mathbb{R}, \varnothing\ne{A}\subset{\mathbb{R}}$ and $l,L\in{\mathbb{R}}$ . Then,

(i) $\sup{A}=L$ $\iff$

a) $\forall{a}\in{A}, a\le{L}$ ,

b) $\displaystyle{\exists{(x_{n})\subset{A}}: \lim_{n\to{\infty}}x_{n}=L}$

(ii) $\inf{A}=l$ $\iff$

a) $\forall{a}\in{A}, l\le{a}$ ,

b) $\displaystyle{\exists{(x_{n})\subset{A}}: \lim_{n\to{\infty}}x_{n}=l}$

6) Let $X=\mathbb{R}, \varnothing\ne{A}\subset{\mathbb{R}}$ and $l,L\in{\mathbb{R}}$ . We can give the following property for the people who know the topology:

(i) $\sup{A}=L$ $\iff$

a) $\forall{a}\in{A}, a\le{L}$ ,

b) $L\in{\overline{A}}$ .

(ii) $\inf{A}=l$ $\iff$

a) $\forall{a}\in{A}, l\le{a}$ ,

b) $l\in{\overline{A}}$ .

(Where $\overline{A}$ denotes the closure of $A$ ).

EXAMPLE6: It was mentioned that $(0,1)\subset{\mathbb{R}}$ has no minimum and maximum in example5. The set of all the upper bounds of $(0,1)$ is $A^{*}=[1,+\infty)$ . Hence, the equality $\sup{A}=\min{A}^{*}=\min{[1,+\infty)}=1$ is true. Similarly, the equality $\inf{A}=0$ is also true.

EXAMPLE7: Let $E$ be a set and $X=\mathbf{P}(E)$ . As it is well known, $(\mathbf{P}(E),\subset)$ is a partially ordered. $S,T\subset{E}$ , $A=\{S,T\}\subset{\mathbf{P}(E)}$ . Now, let’s analyse $\sup{A}=\sup\{S,T\}$ and $\inf{A}=\inf\{S,T\}$ . I.e., we will find the supremum and the infimum of two sets $S$ and $T$ . Since $S\subset{S\cup{T}}$ and $T\subset{S\cup{T}}$ , the set $S\cup{T}$ is an upper bound of the set $\{S,T\}$ . Assume that $U$ is another upper bound of $\{S,T\}$ . Then, $S\subset{U}$ and $T\subset{U}$ . So, $S\cup{T}\subset{U}$ is obtained. Consequently, the least upper bound of $\{S,T\}$ is the union of $S$ and $T$ i.e., $S\cup{T}$ . Similarly, one can easily prove the equality $\inf\{S,T\}=S\cap{T}$ . Let $I$ be an index set and $\{S_{i}\}_{i\in{I}}$ be a family of sets of $\mathbf{P}(E)$ . Hence, the following equalities are true:

$\displaystyle{\sup_{i\in{I}}S_{i}=\bigcup_{i\in{I}}S_{i}}$ and $\displaystyle{\inf_{i\in{I}}S_{i}=\bigcap_{i\in{I}}S_{i}}$ .

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

EXAMPLE8: We know that the natural numbers $\mathbb{N}$ is a partially ordered set with the division. Let’s show that $\sup\{n,m\}=\text{lcm}\{n,m\}=[n,m]$ and $\inf\{n,m\}=\text{gcd}\{n,m\}=(n,m)$ for $n,m\in{\mathbb{N}}$ (lcm: least common multiple, gcd: greatest common divisor). First, we will prove for the supremum: Since $n\mid{[n,m]}$ and $m\mid{[n,m]}$ , the number $[n,m]$ is an upper bound of the set $\{n,m\}$ . Assume that the natural number $k$ is another upper bound of $\{n,m\}$ . Then, $n\mid{k}$ and $m\mid{k}$ . So, $[n,m]\mid{k}$ . Consequently, the least upper bound of two natural numbers is their least common multiple. Now, we will prove for the infimum: Since $(n,m)\mid{n}$ and $(n,m)\mid{m}$ , the number $(n,m)$ is a lower bound of the set $\{n,m\}$ . Assume that the natural number $k$ is another lower bound of $\{n,m\}$ . Then, $k\mid{n}$ and $k\mid{m}$ . So, $k\mid{(m,n)}$ . Consequently, the greatest lower bound of two natural numbers is their greatest common divisor.

DEFINITION9: Let $(X,\le)$ a partially ordered set and $A\subset{X}$ .

(i) $M\in{A}$ is called a maximal element of $A$ if $A$ has no an element being greater than $M$ .

(ii) $m\in{A}$ is called a minimal element of $A$ if $A$ has no an element being lower than $m$ .

THE PROPERTIES OF MAXIMAL AND MINIMAL ELEMENTS:

1) Another expression for the maximal element: Let $M$ be a maximal element of $A$ and $a\in{A}$ . Hence, $M$ and $a$ are incomparable each other or $a\le{M}$ . Another expression for the minimal element: Let $m$ be a minimal element of $A$ and $a\in{A}$ . Hence, $m$ and $a$ are incomparable each other or $m\le{a}$ .

2) Any maximal or minimal element of $A$ is in $A$ .

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 $a^{*}$ is the maximum element of a set, then $a^{*}$ is also a maximal element of this set and this set has no another maximal element. Similarly, if $a_{*}$ is the minimum element of a set, then $a_{*}$ is also a minimal element of this set and this set has no another minimal element.

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

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