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

**if \begin{equation} (x\in D, \, y\in X, \text{ and } x\geq y) \implies y\in D. \end{equation}**

*down-set*** 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

**of $A$, up-closure of $x$,**

*up-closure***of $A$, and the down-closure of $x$, respectively. Up-sets of the form $\uparrow{x}$ are called**

*down-closure***and dually, down-sets of the form $\downarrow{x}$ are called**

*principal up-sets***.**

*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

**of $X$ if for all $a,b\in A,$ $a\in \uparrow{b}$ implies $a=b.$**

*up-independent subset*** 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

**for an up-set $U$ if $B$ is up-independent and spans $U.$**

*basis*** 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

**, 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.$**

*descending chain condition*** 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

**if for every finite subset $A$ of $X,$ $A\subseteq I$ implies that $UL(A)\subseteq I.$**

*ideal*** 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** (

**) 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**

*isotone***if $f$ is either isotone or antitone.**

*monotone*** 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

- Tonelli-Shanks Algorithm (by Example) - September 18, 2020
- Quadratic Congruences and Quadratic Residues - September 17, 2020
- Euler’s Totient Function and Euler’s Theorem - September 16, 2020