Partial Order Relations (Mappings on Ordered Sets)

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.

Related Articles

Follow Me
Latest posts by David A. Smith (see all)