

\documentstyle[11pt]{article}
\pretolerance=15000




\begin{document}
\pretolerance=15000
\tolerance=1500
\title{Monotone Functions from Posets onto $\omega$}
\author{K.A.Kale\\
Department of Pure Mathematics and Mathematical Statistics\\
16 Mill Lane\\
Cambridge\\
CB2 1SB}
\date{}
\maketitle

\begin{abstract}

We characterise a class of posets (which we call uniform posets) and deduce the following corollary:  Define a poset $P$ to have an $\omega$-ranking function if there exists a monotone increasing mapping from $P$ onto $\omega$.  Let $D$ and $E$ be posets with bottom elements.  Then $D \times E$ has an $\omega$-ranking function if and only if either $D$ or $E$ does.
\end{abstract}

\section{Preliminaries}

Let  $D$ be a poset.  We say that a non-empty subset $C$ of $D$ is a chain if for all $x,y \in C, x \leq y$ or $y \leq x$.
  
  When $D$ and $E$ are posets, a function $f:D \to E$ is defined to be monotone increasing if for all $x,y \in D$ with $x \leq y$, we have $f(x) \leq f(y)$.  A subset $C$ of $D$ is an upward $\omega$-chain if it is the image of some injective monotone increasing function from $\omega$ to $D$.

   If $D$ is a poset, a non-empty subset $R$ of $D$ is said to be directed if whenever $x$ and $y$ are members of $R$, there exists an element $z$ of $R$ which is an upper bound for both $x$ and $y$.  An element $x$ of $D$ is said to be confluent if the set 
$\{ y:  x \leq y \}$ is directed.

   Define the relation {\bf E} on the confluent elements of a poset $D$ by:  $a${\bf E}$b$ \iff \forall $x \geq a$ \forall $y \geq b \ x$ and $y$ have an upper bound in $D$.  Clearly this is an equivalence relation.  We call the equivalence classes ends of $D$.  Note that the ends of D are upward closed (i.e. if $E$ is an end, $x \in E$ and $x \leq y$, then $y \in E$).

   We say that a function $f:D \to \omega$ is an $\omega$-ranking function for $D$ if it is monotone increasing and onto $\omega$.

   Let $D$ be a poset with bottom element $0$.  We define a monotone function $f:D \to D$ to be pre-nilpotent if $\forall x \in D \ \exists n \in Z^+$ such that $f^n(x)=0$ and nilpotent if $\exists n \in Z^+$ such that $\forall x \in D f^n(x)=0$.  We say that $D$ is uniform if every pre-nilpotent f on D is nilpotent.

   Let $D$ and $E$ be posets.  We define the poset $D \times E$ to be the set $D \times E$ with the ordering defined by $<d_1,e_1> \leq <d_2,e_2>$ iff $d_1 \leq d_2$ and $e_1 \leq e_2$. This definition can be extended to arbitrary families of posets.

   If $D$ is a poset, the monotone function space $[D \stackrel{m}{\to} D]$ is defined to be the set of monotone increasing functions on D with the pointwise ordering.

   \section{The Results}

   \begin{theorem} \label{th:1}
   {\bf Theorem 1}:  Let $D$ be a poset with bottom element $0$.  Then the following are equivalent.

(a)  $D$ is a uniform poset.

(b)  $D$ does not have an $\omega$-ranking function.

(c)  Every element of $D$ is below a confluent element of $D$, and $D$ has only finitely many ends, and every end $E$ of $D$ has the property that every countably infinite subset of $E$ is bounded above.
\end{theorem}

\medskip

Proof:

\begin{sloppypar}
(b)$\Rightarrow$(a):  Suppose that $D$ is not uniform.  Then there exists a \linebreak monotone increasing   function $g:D \to D$ which is pre-nilpotent but not nilpotent.  Define $f:D \to \omega$ by $f(x)=min  \{ r \in Z^+ : g^r (x)=0 \}$.  Clearly $f$ is monotone  increasing, and the image of $f$ is $\omega$. 
\end{sloppypar}

(a)$\Rightarrow$(c):

Case 1:  Suppose that some $x \in D$ is not below a confluent element.  Then we can find a binary tree of height $\omega$ in $D$ with countably many elements and with the property that for every node, the two immediate successors of that node have no upper bound in $D$.  Label the tree by defining the element $a_n$ to be the element found by going  n steps up the right-most branch of the tree, and then taking the turning to the left and going one step up.

   Note that if $a_n$ and $a_m$ had a common upper bound in $D$,  this would also be an upper bound of $a_r$ (where $r=min\{m,n \}$) and the other son of the father of $a_r$.

Define $f:D \to D$ as follows:

\begin{eqnarray*}
f(x) & = & a_{n} \mbox{ if } x \geq  a_{n+1}
\mbox{  for some } x \in \omega \\
& & 0 \mbox{ otherwise }.
\end{eqnarray*}

    By the remark above, $f$ is well-defined on $D$.  Also, it is clearly pre-nilpotent but not nilpotent.  So $D$ is not uniform.

Case 2:

Suppose that $D$ has infinitely many ends.  Pick a countable subset, and call it $\{ E_i :  i \in \omega \}$.  For each $i \in \omega$, pick $x_i \in E_i$.

   Define $f:D \to D$ as follows:

\begin{eqnarray*}
f(x) & = & x_{n} \mbox{ if } x \in E_{n+1} \mbox{ for some } n \in \omega \\
& & 0 \mbox{ otherwise }.
\end{eqnarray*}
  
Then f is pre-nilpotent but not nilpotent.

Case 3:

Now suppose that some end $E$ has a countably infinite subset S which is unbounded.  Write $S=\{ a_i: i \in \omega \}$.  Define $x_0:=a_0$.  Suppose inductively that we have defined $x_0 \leq x_1 \leq x_2 \leq ... \leq x_n$ in $E$.  Now $x_n, a_n \in E$, so they have an upper bound $x_{n+1} \in D$, and clearly $x_{n+1} \in E$.  

   We assert that $\{ x_n : n \in \omega \}$ is infinite.  For if not, it would have a top element, $x$ say, and this would be an upper bound for $S$, contrary to our assumption.


   Thus $\{ x_n : n \in \omega \}$ contains an upward $\omega$-chain $x_{N_0} < x_{N_1} < x_{N_2) < ...$, which is unbounded in $D$.

   Define $f:D \to D$  as follows:

\begin{eqnarray*}
f(x) & = & x_{N_r} \mbox{ if } r=max\{  s: x_{N_{s+1}} \leq x \} \mbox{ exists } \\
& & 0 \mbox{ otherwise }.
\end{eqnarray*}

   Clearly f is pre-nilpotent but not nilpotent.

(c)$\Rightarrow$(b):  Suppose that there exists an $\omega$-ranking function $f:D \to \omega$.  Let the ends of $D$ be $E_1, E_2,..., E_m$.  Define $S_n:= f^{-1}(n)$ for each $n \in \omega$.  Then each $S_n$  is non-empty.  Some end (say without loss of generality $E_1$) must have non-empty intersection with infinitely many of the $S_n$. 

 (For otherwise we could find an $N$ such that $n \geq N$ implies that $S_n \cap E_i= \emptyset for i=1,..., m.$  Pick $x \in S_N$.  Then $x$ is below some confluent element $y$.  But $y$ is in some end, and also in some $S_n$, for $n \geq N$.  Contradiction.  ) 

 So say $T_r:= S_{N_r} \cap E_1 \not= \emptyset$ for some strictly increasing sequence $\{ N_r : r \in \omega \}$.  Pick $x_r \in T_r$.  Now $\{ x_r : r \in \omega \}$ is a countably infinite subset of $E_1$, so has a bound $x$.  But $f(x) \geq N_r$ for all $r \in \omega$, which is impossible.  $\Box$

   Note that the proofs (a)$\Rightarrow$(c) and (c)$\Rightarrow$(b) used the Axiom of Choice.

\medskip

\begin{corollary} \label{co:2}
{\bf Corollary 2}:  Let $D_i (1 \leq i \leq n )$ be posets with bottom elements.  Then $\times_{i=1}^n D_i$ has an $\omega$-ranking function if and only if some $D_i$ has an $\omega$-ranking function.
\end{corollary}

\medskip

Proof:

$\Leftarrow$:  Trivial.

$\Rightarrow$:  Assume that no $D_i$ has a characterisation function.  Let $x_i \in D_i \ (1 \leq i \leq n)$.  Then there exist  $y_i \in D_i$ such that $x_i \leq y_i$  and $\{ z: z \in D_i, z \geq y_i \}$ is directed in $D_i$.  Clearly $<y_i>$ is confluent in $\times_{i=1}^n D_i$, so every element of $\times_{i=1}^n D_i$ is below a confluent element.

   Let $D_i$ have ends $E_{1}^i, E_{2}^i,..., E_{N_i}^i$.  Pick $x_{j}^i \in E_{j}^i$ for $1 \leq j \leq N_i$.  Let $<x_i>$ be a confluent element of $\times_{i=1}^n D_i$.  Then clearly each $x_i$ is confluent in $D_i$.  So for some $1 \leq j_i \leq N_i, x_j E_i x_{j_i}^i$ (where $E_i$ is the equivalence relation on $D_i$ as defined in Section 1 of this paper).

   We assert that $< x_i > E <x_{j_i}^i$ (where $E$ is the equivalence relation on $\times_{i=1}^n D_i$ as defined in Section 1 of this paper).

   Let $<x_i > \leq <y_i >, \ <x_i > \leq <z_i >.$  Then for each $i$, there exists $w_i $ in $D_i $ such that $y_i \leq w_i $ and $z_i \leq w_i $.  So $<y_i > \leq <w_i >$ and $< z_i > \leq <w_i >$.  So $<x_i >E<x_{j_i}^i >$ as required.  Thus $\times_{i=0}^n D_i $ has only finitely many ends.

   We assert that every end of $\times_{i=0}^n D_i$ has the property that every countable subset of the end is bounded above.  Let $E$ be an end of $\times_{i=0}^n D_i $.  Let $<x_{i}^1 >,\ <x_{i}^2 >, \ <x_{i}^3 >, \ ...$ be a countable set in $E$.  Then for $1 \leq i \leq n$, there exists $x_i \in D_i$ such that $x_{i}^r \leq x_i $ for all $r \in \omega$.

  So $<x_{i}^r > \leq <x_i >$ for all $r \in \omega$.

   Combining the above, we see that $\times_{i=0}^n D_i$ is uniform, and so by Theorem 1, it can have no characterisation function. $\Box$

\medskip

\begin{corollary} \label{co:3}
{\bf Corollary 3}: Let $D$ be a poset with bottom element $0$.  Then $[D \stackrel{m}{\to} D]$ uniform implies $D$ uniform.
\end{corollary}

\medskip

Proof:  Suppose that $D$ is not uniform.  Then by Theorem 1, there exists an $\omega$-ranking function $f:D \to \omega$.

   Define $g:[D \stackrel{m}{\to} D] \to D$ by $g(h):=h(0)$.  Then $g$ is monotone increasing, and onto$D$.  So the composition $fg$ is an $\omega$-ranking function for $[D \stackrel{m}{\to} D]$.$\Box$

\section{Acknowledgements}
   I would like to thank my supervisor, Professor Wilfrid Hodges, for advice and guidance, and Dr Achim Jung for reading an earlier version of this paper.  I would also like to thank SERC for giving me a grant.

\end{document}

