Partial Order Relations

Partial Order Relations (Mappings on Ordered Sets)


Master of Science in Mathematics
Lecture Notes. Accessed on: 2019-10-21 18:28:50

We discuss many properties of ordered sets including Noetherian ordered sets and order ideals. We also detail monotone mappings and isomorphisms between ordered sets.

Ordered Sets

Throughout we assume $(X,\geq)$ is an ordered set.  By this we mean that $X$ is a set and that $\geq$ is binary relation on $X$ that is reflexive, antisymmetric, and transitive

Definition. A subset $U$ of $X$ is called an up-set if  \begin{equation} (x\in U, \, y\in X, \text{ and } y\geq x) \implies y\in U.  \end{equation} A subset $D$ of $X$ is called a down-set if \begin{equation} (x\in D, \, y\in X, \text{ and } x\geq y) \implies y\in D.  \end{equation}

Theorem. Let $(X,\geq)$ be an ordered set. The union or intersection of any family of up-sets is an up-set. The complement of an up-set is a down-set.

Proof. Let $\{U_i : i \in I\}$ be a family of up-sets.  Let  $$ U=\bigcup_{i\in I} U_i \quad \text{and} \quad  F=\bigcap_{i\in I} U_i. $$  We will show that $U$ is an up-set.  Let $x\in U,$ $y\in X$ and assume $y\geq x.$  Since $x\in U,$ it follows $x\in U_i$ for some $i.$  Since $U_i$ is an up-set, it follows $y\in U_i.$  Hence $y\in U.$   Next we will show $F$ is an up-set.  Let $x\in F$ and $y\in X$ and assume $y\geq x.$  Since $x\in F,$ it follows $x\in U_i$ for all $i\in I.$  Since $U_i$ are all up-sets, it follows $y \in U_i$ for all $i\in I.$  Let $U$ be an up-set and let $D$ be the complement of $U.$  Let $x\in D,$ $y\in X,$ and assume $x\geq y.$ Assume $y\in U.$  Since $U$ is an up-set and $x\geq y,$ if follows $x\in U.$  However, $x\in U$ and $x\in D$ is a contradiction.  Thus, $y\in D$ as needed. 

Theorem. The union or intersection of any family of down-sets is a down-set. The complement of a down-set is an up-set.

Proof. Let $\{D_i : i \in I\}$ be a family of down-sets. Let  $$ D=\bigcup_{i\in I} D_i \quad \text{and} \quad  E=\bigcap_{i\in I} D_i. $$  We will show that both $D$ and $E$ are down-sets.  Let $x\in D,$ $y\in X$ and assume $x\geq y.$  Since $x\in D,$ it follows $x\in D_i$ for some $i.$ Since $D_i$ is a down-set, it follows $y\in D_i.$ Hence $y\in D.$ Next we will show $E$ is a down-set.  Let $x\in E$ and $y\in X$ and assume $x\geq y.$ Since $x\in E,$ it follows $x\in D_i$ for all $i\in I.$ Since $D_i$ are all down-sets, it follows $y \in D_i$ for all $i\in I.$   Hence $y\in E.$   Let $D$ be a down-set and let $U$ be the complement of $D.$ Let $x\in U,$ $y\in X,$ and assume $y\geq x.$ Assume $y\in D.$ Since $D$ is a down-set and $y\geq x,$ if follows $x\in D.$ However, $x\in D$ and $x\in U$ is a contradiction. Thus, $y\in U$ as needed.

Definition. If $A$ is an arbitrary subset of $X$ and $x\in X,$ then we define $$\uparrow{A}=\{y\in X : \exists\, x\in A,\, y\geq x\}\quad \text{and} \quad  \uparrow{x}=\{y\in X :  y\geq x\}. $$ $$\downarrow{A}=\{y\in X : \exists\, x\in A,\, x\geq y\} \quad \text{and} \quad  \downarrow{x}=\{y\in X : x\geq y\}, $$ to be the up-closure of $A$, up-closure of $x$, down-closure of $A$, and the down-closure of $x$, respectively. Up-sets of the form $\uparrow{x}$ are called principal up-sets and dually, down-sets of the form $\downarrow{x}$ are called principal down-sets.

Important special cases are $\uparrow{X}=X,$ $\downarrow{X}=X,$ $\downarrow{\emptyset}=\emptyset$ and $\uparrow{\emptyset}=\emptyset.$   Clearly,\begin{equation}\label{isoequiv1}\forall \ x,y\in X, \quad x\geq y \, \Longleftrightarrow \,\uparrow{x}\subseteq \uparrow{y}\, \Longleftrightarrow \,\downarrow{x}\supseteq \downarrow{y}.\end{equation}To see this, suppose $x\geq y,$ and assume $z\in \uparrow{x}$ and $w\in \downarrow{y}.$ Then by transitivity of $\geq$ we have $z\in \uparrow{y}$ and $w\in \downarrow{x}.$Conversely, both $\uparrow{x}\subseteq \uparrow{y}$ and $\downarrow{x}\supseteq \downarrow{y}$ imply that $x\geq y$ which follows by the reflexive property.  

Theorem. Assume $A\subseteq X$ and $x\in X.$ Then 

$\quad (1)$ $\downarrow{A}$ is the smallest down-set containing $A,$ 

$\quad (1)$ $A$ is an down-set if and only if $A=\, \downarrow{A},$ and 

$\quad (1)$ $\downarrow{\{x\}}=\, \downarrow{x}.$

Proof. Let $x\in \downarrow{A},$ $y\in X.$  Assume $x\geq y.$ Since $x\in \downarrow{A},$ there exists $z\in A$ such that $z\geq x.$  By transitivity $z\geq y.$  Thus it follows $y\in \downarrow{A}.$  Therefore, $\downarrow{A}$ is an down-set.  Let $D$ be an down-set that contains $A.$  We will show $\downarrow{A}\subseteq D.$  Let $x\in \downarrow{A}.$  Then there exists $z\in A$ such that $z\geq x.$  Since $z\in A,$ it follows $z\in D.$  Since $D$ is an down-set, it follows that $x\in D,$ as a needed.  Suppose $A=\downarrow{A},$ then it follows $A$ is an down-set.  Conversely, assume $A$ is an down-set.  Thus $\downarrow{A}$ is the smallest down-set that contains $A,$ so it follows $\downarrow{A}\subseteq A$ since $A$ is an down-set and $A\subseteq A.$  Let $x\in A.$  By the reflexive property of $\geq,$ it follows $x\geq x,$ and thus $x\in \downarrow{A}.$  Hence $\downarrow{A}=A.$  Immediately, $y\in \downarrow{\{x\}} \Longleftrightarrow x\geq y  \Longleftrightarrow y\in \downarrow{x}.$

Theorem. Let $(X,\geq)$ be an ordered set with $A\subseteq X$ and $x\in X.$ 

$\quad (1)$ $\uparrow{A}$ is the smallest up-set containing $A.$

$\quad (1)$ $A$ is an up-set if and only if $A=\, \uparrow{A}.$ 

$\quad (1)$ $\uparrow{\{x\}}=\, \uparrow{x}.$

Proof. Let $x\in \uparrow{A},$ $y\in X.$  Assume $y\geq x.$  Since $x\in \uparrow{A},$ there exists $z\in A$ such that $x\geq z.$  By transitivity $y\geq z.$  Thus it follows $y\in \uparrow{A}.$  Therefore, $\uparrow{A}$ is an up-set.  Let $U$ be an up-set that contains $A.$  We will show $\uparrow{A}\subseteq U.$  Let $x\in \uparrow{A}.$  Then there exists $z\in A$ such that $x\geq z.$  Since $z\in A,$ it follows $z\in U.$  Since $U$ is an up-set, it follows that $x\in U,$ as a needed.  Suppose $A=\uparrow{A},$ then it follows $A$ is an up-set.  Conversely, assume $A$ is an up-set.  Thus $\uparrow{A}$ is the smallest up-set that contains $A,$ so it follows $\uparrow{A}\subseteq A$ since $A$ is an up-set and $A\subseteq A.$  Let $x\in A.$  By the reflexive property of $\geq,$ it follows $x\geq x,$ and thus $x\in \uparrow{A}.$  Immediately, $y\in \uparrow{\{x\}} \Longleftrightarrow y\geq x  \Longleftrightarrow y\in \uparrow{x}.$

Theorem. For all $x,y\in X,$  \begin{equation} \label{isoequiv} x\geq y  \, \Longleftrightarrow \,\downarrow{x}\supseteq \downarrow{y}\, \Longleftrightarrow \,\uparrow{x}\subseteq \uparrow{y}.\end{equation}

Proof. Suppose $x\geq y.$  Let $z\in \downarrow{y}$ then $y\geq z.$  By transitivity of $\geq$ we have $x\geq z$ and thus $z\in \downarrow{x}.$ Therefore we have shown, if $x\geq y$ then $\downarrow{x}\supseteq \downarrow{y}.$Conversely, assume $\downarrow{x}\supseteq \downarrow{y}.$ By reflexivity of $\geq$ we have $y\in \uparrow{y}$ and so $y\in \downarrow{x},$ and thus $x\geq y.$ Now suppose $x\geq y.$  Let $z\in \uparrow{x}.$ Then $z\geq x$ and so by transitivity of $\geq$ we have $z\geq y,$ and therefore $z\in \uparrow{y}.$ Conversely, assume $\uparrow{x}\subseteq \uparrow{y}.$ Then $x\in \uparrow{y}$ and thus $x\geq y.$

Theorem. Let $(X,\geq)$ be an ordered set with $A,B\subseteq X.$ 

$\quad (1)$ $\uparrow{A}=\uparrow{\uparrow{A}}$

$\quad (2)$ $\uparrow{(A\cup B)}=\uparrow{A}\ \cup \uparrow{B}$

$\quad (3)$ $\uparrow{(A\cap B)}\subseteq \uparrow{A}\ \cap \uparrow{B}$

$\quad (4)$ $\uparrow{A}=\bigcup_{x\in A} \uparrow{x}$

$\quad (5)$ $B\supseteq A\Rightarrow \uparrow{B}\supseteq \uparrow{A}$

Proof. Immediately we have $\uparrow{A}\subseteq \uparrow{\uparrow{A}}.$ Let $x\in \downarrow{\downarrow{A}}.$  Then there exists $y\in\downarrow{A}$ such that $y\geq x$ and there exists $a\in A$ such that $a\geq y\geq x.$  Hence $x\in \downarrow{A}.$ Let $x\in \uparrow{(A\cup B)}.$ Then there exists $y\in A\cup B$ such that $x\geq y.$ If $y\in A,$ then $x\in \uparrow{A}.$ If $y\in B,$ then $x\in \uparrow{B}.$ Hence, $x\in \uparrow{A}\ \cup \uparrow{B}.$  Conversely, assume $x\in \uparrow{A} \ \cup \uparrow{B}.$ If $x\in \uparrow{A},$ then there exists $a\in A$ such that $x \geq a.$  Hence $a\in A\cup B$ with $x\geq a$ which yields $x\in \uparrow{(A\ \cup B)}.$ If $x\in \uparrow{B},$ then there exists $b\in B$ such that $x \geq b.$  Hence $b\in A\cup B$ with $x\geq b$ which yields $x\in \uparrow{(A\ \cup B)}.$ Let $x\in \uparrow{(A\cap B)}.$  Then there exists $y\in A\cap B$ such that $x\geq y.$ Hence $y\in A$ with $x\geq y$ and $y\in B$ with $x\geq y.$  Thus $x\in \uparrow{A}$ and $x\in \uparrow{B},$ and so $x\in \uparrow{A}\ \cap \uparrow{B}.$  Let $z\in \uparrow{A}.$ Then there exists $a\in A$ such that $z\geq a.$  Hence it follows that $z\in \uparrow{a}\subseteq \bigcup_{x\in A} \uparrow{x}.$ Conversely, assume $z\in \bigcup_{x\in A} \uparrow{x}.$ Then there exists $x\in A$ such that $z\in \uparrow{x}.$  Hence we have $x\in A$ with $z\geq x.$ Thus it follows that $z\in \uparrow{A}$ as needed. 

Theorem. Let $(X,\geq)$ be an ordered set with $A,B\subseteq X.$ 

$\quad (1)$ $\downarrow{A}=\downarrow{\downarrow{A}}$

$\quad (2)$ $\downarrow{(A\cup B)}=\downarrow{A}\ \cup \downarrow{B}$

$\quad (3)$ $\downarrow{(A\cap B)}\subseteq \downarrow{A}\ \cap \downarrow{B}$

$\quad (4)$ $\downarrow{A}=\bigcup_{x\in A} \downarrow{x}$

$\quad (5)$ $B\supseteq A\Rightarrow \downarrow{B}\supseteq \downarrow{A}$

Spanning Sets, Independence, and Bases

Definition. Let $(X,\geq)$ be an ordered set. If $U$ is an up-set and $U=\uparrow{A},$ then we say $A$ is a spanning set for $U.$

Theorem. If $U=\uparrow{A}$ and $B$ is a subset of $U,$ then $A \cup B$ is also a spanning set for $U.$

Proof. We immediately we have that $\uparrow{(A\cup B)}\subseteq U$ since $U$ is an up-set and $A \cup B\subseteq U.$  Conversely, let $u\in U=\uparrow{A}.$  Thus there exists $a\in A\subseteq A\cup B$ such that $u\geq a,$ and so $a\in \uparrow{(A\cup B)}.$

Definition. Let $(X,\geq)$ be an ordered set. We say $A$ is an up-independent subset of $X$ if for all $a,b\in A,$ $a\in \uparrow{b}$ implies $a=b.$

Theorem. A subset $A$ of $X$ is up-independent if and only if every element in $A$ is an $A$-minimal element.

Proof. Assume $A$ is up-independent and that $a$ is not minimal in $A.$ Hence there exists $b\in A$ such that $a\neq b\in A$ and $a\geq b,$ and so $b\in \uparrow{a},$ contrary to hypothesis.  Conversely, suppose every element in $A$ is $A$-minimal and let $a,b\in A.$ If $a\in \uparrow{b},$ then $a\geq b$ and so $a=b$ since $b$ is minimal in $A.$ Therefore, $A$ is up-independent.

Theorem. If $A$ is an up-independent subset of $X,$ then any subset of $A$ is also an up-independent subset of $X.$

Proof. Assume that $A$ is an up-independent subset and let $B\subseteq A.$  If $B$ is not an up-independent subset, then there exists $a,b\in B$ with $a\in \uparrow{b}$ and $a\neq b.$ Thus, $A$ is not an up-independent subset, contrary to hypothesis.  Thus, $B$ must be up-independent subset of $X.$ To prove the dual statement, assume that $A$ is a down-independent subset and let $B\subseteq A.$  If $B$ is not a down-independent subset, then there exists $a,b\in B$ with $a\in \downarrow{b}$ and $a\neq b.$  Thus, $A$ is not a down-independent subset, contrary to hypothesis. Thus, $B$ must be a down-independent subset.

Definition. A subset $B$ is called a basis for an up-set $U$ if $B$ is up-independent and spans $U.$

Theorem. Any basis for an up-set is a minimal spanning set and a maximal up-independent subset.

Proof. Assume $B$ is a basis for an up-set $U.$ Suppose a proper subset $B’$ of $B$ is also a spanning set for $U$ and let $a\in B\setminus B’.$ Since $U=\uparrow{B’},$ there exists $b\in B’$ such that $a\geq b,$ but this contradicts the hypothesis that $B$ is up-independent.  Now if $B$ were not maximal, there would be an element in $a\in U\setminus B$ for which the set $B\cup\{a\}$ is up-independent.  But then $a$ is not in the span of $B,$ contradicting the fact that $B$ is a spanning set for $U.$ Hence $B$ is a maximal up-independent subset of $U.$

Theorem. If $U$ is an up-set, then either there exists a chain in $U$ with no lower bound or $U$ contains a basis.

Proof. Suppose every chain in $U$ has a lower bound in $U.$ Then by Zorn’s Lemma, $U$ contains a nonempty set of minimal elements $B.$ If $x\in U,$ let $M$ be a maximal chain in $U$ which contains $x.$ By our assumption, $M$ has a lower bound $a$ in $U.$ Then $x\geq a$ and $a\in B$ (by maximality of $M$), and so $U=\uparrow{B}.$ Since $B$ consists only of minimal elements, for all $b_1,b_2\in B$ with $b_1\in \uparrow{b_2}$ it follows immediately that $b_1=b_2,$ and thus $B$ is an up-independent subset of $U.$ Hence $B$ is a basis for $U.$

Theorem. Assume $U$ is an up-set of $X.$ If $A$ is an up-independent subset of $U$ consisting only of minimal elements in $U$ and if $S$ is a spanning set for $U$ containing $A$ in which every infinite chain in $S$ contains a minimal element of $U,$ then there exists a basis $B$ for $U$ for which $A\subseteq B\subseteq S.$

Proof. Let $\mathcal{A}$ be the collection of all up-independent subsets of $U$ that contain $A,$ are contained in $S,$ and consist only of minimal elements in $U.$   By hypothesis $A\in\mathcal{A}.$ Let $\mathcal{C}=\{C_k:k\in K\}$ be a chain in $\mathcal{A}.$ We claim that $C=\bigcup_{k\in K}C_k$ is an up-independent subset of $U.$ To prove this claim, let $a,b\in C$ and suppose $a\in \uparrow{b}.$  Then there exists $k_1,k_2\in K$ such that $a\in C_{k_1}$ and $b\in C_{k_2}.$  If $C_{k_1}\subseteq C_{k_2},$ then $a,b\in C_{k_2}$ and thus $a=b,$ since $C_{k_2}$ is up-independent.   The case for $C_{k_2}\subseteq C_{k_1}$ is similar.  Hence $C$ is an up-independent subset of $U.$  Since $A\subseteq C_k \subseteq S,$ for all $k\in K,$ it follows $A\subseteq C \subseteq S.$ Further, $C$ consists only of minimal elements in $U,$ and thus $C\in \mathcal{A}.$  By Zorn’s Lemma, there exists a maximal up-independent subset $B$ of $U$ with $A\subseteq B \subseteq S$ and which consists only of minimal elements in $U.$ Assume that $B$ is not a spanning set for $U.$  Then $\uparrow{B}\neq U=\uparrow{S}$ and so there exists $x\in \uparrow{S}$ with $x\notin\uparrow{B}.$ Then there exists $s_1\in S$ such that $x\geq s_1.$ Notice that $s_1\notin B$ since if not, then $x\in \uparrow{B}$ would occur.  If there exists $b\in B$ with $s_1\geq b,$ then $x\in \uparrow{B}$ follows by $x\geq s_1\geq b.$ If there exists $b\in B$ with $b\geq s_1,$ then $b=s_1$ since $B$ consists only of minimal elements.  Whence it follows that $B\,\cup\{s_1\}$ is up-independent.  Assume $s_1$ is not minimal in $U.$   Then there exists $y\in U$ such that $s_1\geq y.$ Since $S$ is a spanning set, there exists $s_2\in S$ such that $x\geq s_1\geq y\geq s_2.$  Notice that $s_2\notin B$ since if not, then $x\in \uparrow{B}$ would occur.  If there exists $b\in B$ with $s_2\geq b,$ then $x\in \uparrow{B}$ follows by $x\geq s_2\geq b.$ If there exists $b\in B$ with $b\geq s_2,$ then $b=s_2$ since $B$ consists only of minimal elements.  Whence it follows that $B\,\cup\{s_2\}$ is up-independent.  Let $C$ be the chain of elements in $S$ obtained by repeating this process. Let $s$ be the least element of $C$ guaranteed by hypothesis.  Whence, $B\,\cup\{s\}$ is up-independent and consists only of minimal elements in $U.$  Since $B\subset B\,\cup\{s\}\subseteq S,$ it follows that $U=\uparrow{B},$ and so $B$ is a basis for $U.$

Theorem. All bases for an up-set have the same cardinality.

Proof. First we will prove that if an up-set $U$ has a finite basis, then all bases for $U$ are finite.  Suppose $A=\{a_1,\ldots,a_n\}$ is a finite basis for $U$ and $B$ is another basis for $U.$ For each element $a_i\in A,$ there exists $b_i\in B$ such that $a_i\geq b_i.$  Let $C=\{b_1,\ldots, b_m\}\subseteq B$ with $m\leq n.$ Notice that $C$ is up-independent since $B$ is. Assume there exists $b\in B\setminus C.$  Then, since $U=\uparrow{A},$ there exists $a\in A$ such that $b\geq a.$  Then there exists $b_j\in C$ such that $b\geq a\geq b_j,$ which can not happen since $B$ is up-independent.  Hence $B=C$ and so $|B|\leq |A|.$  Reversing the roles of $A$ and $B$ in the above argument it follows that $|A|\leq |B|$; and so $|A|=|B|$ Next we will prove that if an up-set has an infinite basis, then all bases for $U$ have the same cardinality.  Suppose $A$ is a basis for $U$ with $|A|\geq \aleph_0,$ the smallest infinite cardinal, and that $B$ is another basis for $U.$ We want to show $|A|=|B|.$ First notice that $|B|\geq \aleph_0$ by the above argument.  For each $a\in A,$ let $B_a=\{b\in B:a\geq b\}.$ Notice that each $B_a$ is nonempty since $B$ is a basis.  From each $B_a$ choose $b_a$ and let $B’$ be the collection of these choices.  We claim that $\uparrow{B’}=U.$ Clearly, $\uparrow{B’}\subseteq U.$ Let $x\in U.$ Since $\uparrow{A}=U,$ there exists $a\in A$ such that $x\geq a.$ Then $x\geq a \geq b_a$ and so $x\in\uparrow{B’}.$ Suppose $b\in B\setminus B’.$ Since $\uparrow{B’}=U,$ there exists $b’\in B$ such that $b’\geq b,$ contrary to the assumption that $B$ is up-independent. Hence $B’=B.$ Now we have $|B|=|B’|\leq |A|.$ Reversing the roles of $A$ and $B$ in the above argument we have $|B|\leq |A|$; and so $|A|=|B|$ follows by the Cantor-Bernstein-Schroeder theorem.

Definition. The cardinality of any basis of an up-set $U$ is called the dimension of $U$ and is written $\dim U.$

Chain Conditions

Definition. Let $(X,\geq)$ be an ordered set. For any $c_0\in X$ form a chain in the following way  $$ c_0 > c_1 >\cdots >c_{k-1}>c_k > \cdots. $$ If each chain so formed is finite, then $X$ is said to satisfy the minimum condition.

Definition. Let $(X,\geq)$ be an ordered set. Then $X$ satisfies the descending chain condition, if given any sequence $x_1\geq x_2 \geq \cdots \geq x_n \geq \cdots$ of elements of $X,$ there exists $k\in \mathbb{N}$ such that $x_k=x_{k+1}=\cdots.$

Theorem. If $(X,\geq)$ is an ordered set that satisfies the minimum condition, then for any $x\in X,$ there exists at least one minimal element $m$ of $X$ such that $x\geq m.$

Theorem. Every chain of an ordered set $(X,\geq)$ satisfying the minimum condition has a least element. 

Theorem. An ordered set $(X,\geq)$ satisfies the descending chain condition if and only if $\geq$ is well-founded on $X.$

Theorem. Let $(X,\geq)$ be an ordered set.

$\quad (1)$ Then $\geq$ is well-founded  if and only if there exists a linear extension of $\geq$ which is a well-ordering. 

$\quad (2)$ If $\geq$ is well-founded and does have an infinite anitchain, then there exists a linear extension of $\geq$ which is not a well-ordering.

Definition. An ordered set $(X,\geq)$ that is well-founded and every antichain is finite is called Noetherian

Theorem. For any ordered set $(X,\geq),$ the following are equivalent.

$\quad (1)$ $\geq$ is Noetherian. 

$\quad (2)$ $\geq$ is well-founded and every subset has only finitely many minimal elements. 

$\quad (3)$ Every linear extension of $\geq$ is a well-ordering of $X.$

$\quad (4)$ Every up-set has a finite basis. 

$\quad (5)$ The ascending chain condition holds for up-sets.

$\quad (6)$ $(\mathcal{X},\supseteq)$ is well-founded.

Proof. Since $\geq$ is well-founded, every chain in $U$ has a lower bound in $U.$ Then by Zorn’s Lemma, $U$ contains a nonempty set of minimal elements $B.$ If $x\in U,$ let $M$ be a maximal chain in $U$ which contains $x.$ By our assumption, $M$ has a lower bound $a$ in $U.$ Then $x\geq a$ and $a\in B$ (by maximality of $M$), and so $U=\uparrow{B}.$ Since $B$ consists only of minimal elements, it follows immediately that $B$ is up-independent.

The primes $\{2,3,5,7,11,\ldots\}$ form an infinite antichain in the ordered set $(\mathbb{N},|).$

Order Ideals

Assume that $(X,\geq)$ is an ordered set and that $A$ is a subset of $X.$ Let $L(A)$ be the set of all lower bounds of $A$ and $U(A)$ be the set of all upper bounds of a set $A.$  Exactly,  $$ L(A)=\{x\in X: \forall a\in A, a \geq x\}, \quad  U(A)=\{x\in X: \forall a\in A, x \geq a\}. $$ Clearly, $L(\emptyset)=X,$ $U(\emptyset)=X,$  $L(X)$ is either empty or consists only of the least element of $X,$ and $U(X)$ is either empty or consists only of the greatest element of $X.$

Theorem. Let $(X,\geq)$ be an ordered set.

$\quad (1)$ If $A\subseteq B\subseteq X,$ then $L(B)\subseteq L(A)$ and $U(B)\subseteq U(A).$

$\quad (2)$ If $A, B\subseteq X,$ then $L(A\cup B)\subseteq L(A)\cap L(B).$ 

$\quad (3)$ If $A, B\subseteq X,$ then $U(A\cup B)\subseteq U(A)\cap U(B).$

Proof. Assume $A\subseteq B$ and let $x\in L(B).$ Then $b\geq x,$ for all $b\in B.$ Hence $b\geq x,$ for all $b\in A.$ Thus $x\in L(A).$  Similarly, let $y\in U(B).$  The $y\geq b,$ for all $b\in B.$ Hence $y\geq b,$ for all $b\in A.$ Thus $y\in U(A).$ Assume $A,B\subseteq X.$  Let $x\in L(A\cup B).$  Then $a\geq x,$ for all $a\in A\cup B.$ Thus, $a\geq x,$ for all $a\in A$ and  $a\geq x,$ for all $a\in B.$ Hence $x\in L(A)\cap L(B).$ Assume $A,B\subseteq X.$  Let $y\in U(A\cup B).$  Then $y\geq b,$ for all $b\in A\cup B.$ Thus, $y\geq b,$ for all $b\in A$ and  $y\geq b,$ for all $b\in B.$ Hence $y\in U(A)\cap U(B).$

Theorem. Let $(X,\geq)$ be an ordered set.

$\quad (1)$ If $A\subseteq B \subseteq X,$ then $UL(A)\subseteq UL(B).$

$\quad (2)$ If $A\subseteq X,$ then $A\subseteq UL(A).$

$\quad (3)$ If $A\subseteq X,$ then $UL(UL(A))=UL(A).$

Proof. We have $A\subseteq B\Rightarrow L(B)\subseteq L(A)\Rightarrow UL(A)\subseteq UL(B)$ as needed. Assume $A\subseteq X$ and let $x\in A.$ Assume $y\in L(A).$ Then $b\geq y$ for all $b\in A.$ Thus $x\geq y$ and so we have $x\in UL(A).$ Assume $A\subseteq X.$ Thus we have $A\subseteq UL(A)$ and so $UL(A)\subseteq UL(UL(A))$ as needed. Let $x\in L(A).$ Let $z\in UL(A).$ Then $z\geq b,$ for all $b\in L(A).$ Then $z\geq x$ and so $L(A)\subseteq LUL(A).$ Therefore, $UL(UL(A))\subseteq UL(A)$ as needed.

Theorem. Let $(X,\geq)$ be an ordered set.

$\quad (1)$ If $x\in X,$ then $UL(x)=\uparrow{x}.$

$\quad (2)$ If $A\subseteq X,$ then $UL(A)=\bigcap\{\uparrow{x}:A\subseteq \uparrow{x}\}.$

Proof. Let $y\in UL(x).$ Then $y\geq z,$ for all $z\in L(x).$ Hence $y\geq x$ since $x\in L(x),$ and so $y\in \uparrow{x}.$ Conversely, assume $y\in \uparrow{x}.$ Then $y\geq x.$ Let $z\in L(x).$ Then $y\geq x\geq z,$ and so by transitivity, $y\in UL(x).$ Assume $y\in UL(A).$ Then $y\geq z,$ for all $z\in L(A).$ Let $A\subseteq \uparrow{x}.$ Then $L(\uparrow{x})\subseteq L(A).$ Hence, $y\geq z,$ for all $z\in \uparrow{x}$ so that $x$ with $A\subseteq \uparrow{x}.$ Therefore, $y\in \bigcap\{\uparrow{x}:A\subseteq \uparrow{x}\}.$ Conversely, assume $y\in \bigcap\{\uparrow{x}:A\subseteq \uparrow{x}\}.$  Let $z\in \uparrow{x}.$  To show that $A\subseteq \uparrow{z},$ let $a\in A.$ Then $a\geq z$ and so $a\in \uparrow{z}.$ Therefore, $y\in \uparrow{z}.$  Hence $y\geq z$ and so $y\in UL(A).$

Definition. We say a subset $I$ of $X$ is an ideal if for every finite subset $A$ of $X,$ $A\subseteq I$ implies that $UL(A)\subseteq I.$ 

Theorem. The following hold in any ordered set. 

$\quad (1)$ Every ideal is a up-set.

$\quad (2)$ Principal up-sets are ideals.

$\quad (3)$ The intersection of any number of ideals is an ideal.

Proof. Let $I$ be an ideal of $X$ and assume $x\in I,$ $y\in X,$ and that $y\geq x.$ Clearly, $\{x\}\subseteq I,$ and so $UL(x)\subseteq I.$  If $z$ is an lower bound of $x,$ then $y\geq x\geq z,$ and so $y\in UL(x)\subseteq I.$  Therefore, $I$ is a up-set.  We will prove that $\uparrow{x}$ is an ideal. Assume $A$ is a finite subset of $X$ and that $A\subseteq \uparrow{x}.$ To prove that $UL(A)\subseteq \uparrow{x},$ assume $y\in UL(A).$ Then $y\geq b,$ for all $b\in L(A).$ Since $A\subseteq \uparrow{x},$ we have $a\geq x,$ for all $a\in A.$  Hence $x\in L(A).$ Thus, $y\geq x$ and so $y\in \uparrow{x}$ as needed.  Suppose $\{I_{\alpha}:\alpha\in \Omega\}$ is a collection of ideals of $X.$ We will prove that $I:=\bigcap_{\alpha\in\Omega} I_{\alpha}$ is an ideal of $X.$ Let $A$ be a finite subset of $X$ and assume $A\subseteq I.$ Thus, $A\subseteq I_{\alpha},$ for all $\alpha\in \Omega.$  Immediately, we have $UL(A)\subseteq I_{\alpha},$ for all $\alpha\in \Omega,$ since each $I_{\alpha}$ is an ideal.  Thus $UL(A)\subseteq I$ as needed.

Theorem. The following hold in any ordered set. 

$\quad (1)$ Every ideal is a down-set.

$\quad (2)$ Principal up-sets are ideals.

$\quad (3)$ The intersection of any number of ideals is an ideal.

Proof. Let $I$ be an ideal of $X$ and assume $x\in I,$ $y\in X,$ and that $x\geq y.$ Clearly, $\{x\}\subseteq I,$ and so $(f^*\circ f_*)(\{x\})\subseteq I.$  If $z$ is an lower bound of $x,$ then $y\geq x\geq z,$ and so $y\in (f^*\circ f_*)(\{x\})\subseteq I.$  We will prove that $\uparrow{x}$ is an ideal. Assume $A$ is a finite subset of $X$ and that $A\subseteq \uparrow{x}.$ To prove that $UL(A)\subseteq \uparrow{x},$ assume $y\in UL(A).$ Then $y\geq b,$ for all $b\in L(A).$ Since $A\subseteq \uparrow{x},$ we have $a\geq x,$ for all $a\in A.$  Hence $x\in L(A).$ Thus, $y\geq x$ and so $y\in \uparrow{x}$ as needed.  Suppose $\{I_{\alpha}:\alpha\in \Omega\}$ is a collection of ideals of $X.$ We will prove that $I:=\bigcap_{\alpha\in\Omega} I_{\alpha}$ is an ideal of $X.$ Let $A$ be a finite subset of $X$ and assume $A\subseteq I.$ Thus, $A\subseteq I_{\alpha},$ for all $\alpha\in \Omega.$  Immediately, we have $UL(A)\subseteq I_{\alpha},$ for all $\alpha\in \Omega,$ since each $I_{\alpha}$ is an ideal.  Thus $UL(A)\subseteq I$ as needed.

Definition. Let $(X,\geq)$ be an ordered set with $A\subseteq X.$ The set  $$ \langle A\rangle := \bigcup \ \{UL(B) : B \text{ is a finite subset of } A\}  $$ is called the ideal generated by $A$.

Theorem. The following hold in any ordered set. 

$\quad (1)$ $\langle A \rangle$ is the smallest ideal containing $A.$

$\quad (2)$ For all $x\in X,$ $UL(x)=\langle x\rangle =\uparrow{x}.$

$\quad (3)$ For all $A, B\subseteq X,$ if $A\subseteq B,$ then $\langle A\rangle\subseteq\langle B\rangle .$

$\quad (4)$ If $I$ is an ideal, then $\langle I \rangle =I.$

Proof. First we prove that $\langle A \rangle$ is an ideal of $X.$ Let $F=\{x_1,\ldots,x_n\}$ be a finite subset of $X$ and assume $F\subseteq \langle A \rangle .$ For each $x_i\in F,$ there exists a finite subset $B_i$ of $A$ such that $x_i\in UL(B_i).$ Let $B=B_1\cup \cdots \cup B_n.$ Then $B$ is a finite subset of $A$ and we claim that $F\subseteq UL(B).$ If $x\in F,$ then $x\in UL(B_i)\subseteq UL(B)$ for some $i.$  Therefore, $UL(F)\subseteq UL(UL(B))=UL(B)\subseteq \langle A\rangle$ as needed.  Let $J$ be an ideal containing $A.$ To prove that $\langle A \rangle \subseteq J,$ assume $y\in \langle A\rangle.$ Thus there exists a finite subset $B$ of $A$ such that $y\in UL(B).$ Since $B\subseteq A\subseteq J,$ we see that $B$ is a finite subset of $J.$ Whence, $UL(B)\subseteq J,$ and so $y\in J$ as desired.  Let $a\in \langle x \rangle .$ Then there exists a finite subset $F$ of $\{x\},$ such that $a\in UL(F).$ In case $F=\{x\},$ then $a\geq b,$ for all $b\in L(x).$ In particular, $x\geq x$ implies $x\in L(x).$ Thus $a\in \uparrow{x}.$ In case $F=\emptyset,$ then $a\in UL(\emptyset)=U(X)$ and so $a$ must be the greatest element of $X.$  Hence $a\in \uparrow{x}.$ Conversely, assume $a\in\uparrow{x}.$ Hence $a\geq x.$ Let $u$ be an lower bound of $x,$ then $a\geq x\geq u$ and so $a\in UL(x).$ Hence $a\in\langle x \rangle.$ Assume $A\subseteq B.$  Suppose $x\in \langle A \rangle.$ Then there exists a finite subset $F$ of $A$ such that $x\in UL(F).$ Since $F\subseteq A\subseteq B,$ we have a finite subset $F$ of $B$ with $x\in UL(F).$ Hence, $x\in \langle B \rangle.$  Assume $I$ is an ideal of $X.$ Since $I\supseteq I$ and $\langle I \rangle $ is the smallest ideal containing $I,$ we have $\langle I \rangle \subseteq I.$ Conversely, assume $x\in I.$ Of course $\{x\}$ is a finite subset of $I,$ and  now $x\geq x$ implies that $x\in UL(x).$  Therefore, $x\in \langle I \rangle .$

Theorem. If $\langle A \rangle =I$ and $B$ is a finite subset of $I,$ then $A \cup B$ is also a generating set for $I.$

Proof. Since $A\cup B\subseteq I,$ we immediately have $\langle A\cup B \rangle \subseteq I.$  To prove conversely, let $x\in I=\langle A \rangle .$ Then there exists a finite subset $F$ of $A$ such that $x\in UL(F).$ Thus, $F\cup B$ is a finite subset of $A\cup B$ and $x\in UL(F)\subseteq UL(F\cup B).$ Hence, $x\in \langle A\cup B \rangle .$

Recall, an ordered set $(X,\geq)$ that is well-founded and every antichain is finite is called Noetherian

Theorem. For any ordered set $(X,\geq),$ the following are equivalent.

$\quad (1)$ $\geq$ is Noetherian. 

$\quad (2)$ Every ideal has a finite generating set. 

$\quad (3)$ The ascending chain condition holds for ideals.

Proof. Assume every ideal is finitely generated and let $I_1 \subseteq \cdots \subseteq I_n \subseteq \cdots$ be an ascending chain of ideals. To see that $I=\bigcup_{n\geq 1}I_n$ is an ideal, let $F$ be a finite subset of $I.$  Since $F$ is finite there exists $N$ such that $F\subseteq I_N,$ and so $UL(F)\subseteq I_N.$ Hence, $UL(F)\subseteq I,$ and so $I$ is an ideal.  By hypothesis there exists a finite subset $G=\{g_1,\ldots,g_s\}$ such that $\langle G \rangle =I.$ Since $g_i\in I,$ for $1\leq i\leq s,$ there exists $n_i$ such that $g_i\in I_{n_i}.$Let $M=\max\{n_i:1\leq i \leq s\},$ then $g_i\in I_M$ for all $1\leq i \leq s.$  Since $I$ is the smallest ideal containing $G,$ it follows that $I\subseteq I_M$ and thus $I=I_M.$ Assume there exists an ideal $I$ that is not finitely generated. Let $f_1\in I.$ Then $I\neq \langle f_1 \rangle $ since $I$ is not finitely generated and so there exists $f_2\in I$ such that $f_2\notin \langle f_1 \rangle .$ Then $I\neq \langle f_1, f_2 \rangle $ since $I$ is not finitely generated and $\langle f_1 \rangle \subset \langle f_1, f_2 \rangle .$  If $X$ is finite, then the result holds. Otherwise we continue in this fashion, and we obtain a strictly ascending chain of ideals. 

Monotone Mappings

If $(X,\leq_1)$ and $(Y,\leq_2)$ are ordered sets then the mapping $f: X \to Y$ is said to be isotone (isotone) if $$(\forall \, x,y\in X) \quad x \leq_1 y \implies f(x) \leq_2 f(y) $$ or is said to be order-reversing (antitone) if  $$ (\forall \, x,y\in X) \quad x \leq_1 y \implies f(x) \geq_2 f(y). $$ Furthermore, $f$ is called monotone if $f$ is either isotone or antitone.

Theorem. For every function $f$ on an ordered set $(X,\geq),$ we denote it to be $\uparrow,$ $\downarrow,$ or $\updownarrow$ according to whether it is isotone, antitone, or both.  The following are some easy consequences:

$\quad (1)$ $\uparrow \circ \downarrow \, \, = \,  \,  \downarrow \circ \uparrow \, \, = \,  \, \downarrow$ (meaning that the composition of an isotone and an antitone maps is antitone), 

$\quad (2)$ $\uparrow \circ \uparrow \,\, = \,\,  \downarrow \circ \downarrow \, \, = \,  \,  \uparrow$ (meaning that the composition of two isotone or two antitone maps is isotone),

$\quad (3)$ $f$ is $\updownarrow$ if and only if it is a constant on any chain in $A,$ and if this is the case, for every $a\in A,$ $f^{-1}(a)$ is a maximal chain in $A.$

Theorem. A mapping $f:X\to Y$ is isotone if and only if the inverse image of every principal down-set of $Y$ is a down-set of $X.$

Proof. First notice that \begin{equation} \label{inverseprinds} \forall y\in Y, \quad x\in f^{-1}(\downarrow{y}) \Longleftrightarrow y\geq f(x). \end{equation} Suppose that $f$ is isotone.  Let $\downarrow{y}$ be an arbitrary principal down-set of $Y$ and let $A=f^{-1}(\downarrow{y}).$  Assume $x\in A,$ $z\in X,$ and $x\geq z.$ Since $f$ is isotone, we have $f(x)\geq f(z).$  Since $x\in A$ it follows by \eqref{inverseprinds} that $y\geq f(x)$; and so we have $y\geq f(z)$ by transitivity of $\geq.$ Thus $z\in A$ as needed.  For conversely, notice that by reflexivity of $\geq$ and \eqref{inverseprinds} it follows that  for every $x\in X$ we have $x\in f^{-1}(\downarrow{f(x)}).$  By hypothesis, $f^{-1}(\downarrow{f(x))}$ is a down-set of $X$; so if $y\in X$ is such that $x\geq y$ we have $y\in f^{-1}(\downarrow{f(x)}).$ By \eqref{inverseprinds}, it follows that $f(x)\geq f(y)$ and therefore $f$ is isotone.

Theorem. If $X, Y$ are ordered sets and if $f:X\to Y$ is any mapping then the following statements are equivalent. 

$\quad (1)$ $f$ is isotone;

$\quad (2)$ the inverse image of every principal down-set of $Y$ is a down-set of $X$;

$\quad (3)$ the inverse image of every principal up-set of $Y$ is an up-set of $X.$

Proof. Suppose that $f$ is isotone.  Let $y\in Y$ and let $A=f^{\leftarrow}(y^{\downarrow}).$  If $A\neq\emptyset$ assume $x\in A.$  Then for every $z\in X$ with $z\leq x$ we have $f(z)\leq f(x)\leq y$ whence $z\in A.$ Thus $A$ is a down-set of $X.$  Conversely, notice that for every $x\in X$ we have $x\in f^{\leftarrow}[f(x)^{\downarrow}].$ By (2) this is a down-set of $X$; so if $y\in X$ is such that $y\leq x$ we have $y\in f^{\leftarrow}[f(x)^{\downarrow}].$  If follows that $f(y)\leq f(x)$ and therefore $f$ is isotone.  Assume $f$ is order preserving.  Let $y\in Y$ and let $A=f^{\leftarrow}(y^{\uparrow})$ be the inverse image of a principal down-set of $Y.$  To show $A$ is an up-set of $X,$ assume $x\in A.$  If $z\in X$ with $z\geq x$ we have $f(z)\geq f(x) \geq y$ whence $z\in A$ as needed.   Conversely assume $x\leq y$.  Notice $x\in f^{\leftarrow}(f(x)^{\uparrow})$ holds for all $x\in X.$  By assumption, $f^{\leftarrow} (f(x)^{\uparrow})$ is an up-set of $X,$ and so it follows $y\in f^{\leftarrow}(f(x)^{\uparrow}).$  Whence $f(y)\geq f(x)$ as needed.

Theorem. A mapping $f: X \to Y$ is an order-isomorphism if and only if $f$ is bijective and both $f$ and $f^{-1}$ are isotone.

Proof. Assume $f:X\to Y$ is a order-isomorphism.  By definition $f$ is surjective.  Using the reflexive and antisymmetric properties we have \begin{align*} f(x)=f(y) & \Longleftrightarrow f(x)\geq f(y)\text{ and } f(y)\geq f(x)  \\ &  \Longleftrightarrow x\geq y \text{ and } y\geq x \\ &   \Longleftrightarrow x=y \end{align*} Thus $f$ is injective and so bijective. Since $$ \forall x,y\in X, \quad x=f^{-1}(f(x))=f^{-1}(f(y))=y \Longleftrightarrow f(x)\geq_2 f(y) $$ it follows both $f$ and $f^{-1}$ are isotone.   Conversely, assume $f$ is bijective and both $f$ and $f^{-1}$ are isotone.  Obviously, $f$ is surjective.  Let $x,y\in X.$ Assume $x\geq y.$ Then $f(x)\geq f(y)$ since $f$ is isotone.  Now assume $f(x)\geq f(y).$  Since $f^{-1}$ is isotone and $f^{-1}$ is the inverse of $f,$ we have $x=f^{-1}(f(x))\geq y=f^{-1}(f(y))$ as needed.

Theorem. The mapping $\phi: X\to \mathcal{X}$ defined by  $$ \phi(x)= \downarrow{x}. $$ is a order-isomorphism onto the set of all principal down-sets of $X.$

Proof. First notice that $\phi$ is a bijection to the principal down-sets:  $$ \phi(x)=\phi(y)  \Longleftrightarrow \downarrow{x} = \downarrow{y}  \Longleftrightarrow y\geq x \text{ and } x\geq y \Longleftrightarrow x=y. $$ To show that $\phi$ is a order-isomorphism, observe \eqref{isoequiv} yields $x\geq y$ if and only if $\phi(y) \subseteq \phi(x),$ and the claim follows.

5/5 (1 Review)

Leave a Comment

Scroll to Top