
% Subject: lattice.tex
% Date: Mon, 25 Apr 1994 18:30:28 +0200 (MET DST)



\documentclass[12pt]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}

\newcommand{\newmytheorem}{\theoremstyle{plain}\newtheorem}
\newcommand{\newmyremark}{\theoremstyle{remark}\newtheorem}

\makeatletter
\long\outer\def\thm#1 #2:#3\sof{%
\@ifundefined{#2}{%
	\newmytheorem{#2}[thxx]{#2}%
}{}%
\begin{#2}\label{#1}%
\mrginpar{$<${#1}}%
#3
\end{#2}}

\long\outer\def\rem#1 #2:#3\sof{%
\@ifundefined{#2}{%
	\newmyremark{#2}[thxx]{#2}%
}{}%
\begin{#2}\label{#1}%
\mrginpar{$<${#1}}%
#3
\end{#2}}

\newif\ifproofmode
\def\mrginpar#1{\ifproofmode\marginpar{#1}\else\fi}

\newtheorem{thxx}{BLA}[section]

\renewcommand{\baselinestretch}{1.1}
%\proofmodetrue

\def\<#1>{\langle #1 \rangle}


\let\cut\cap
\let\bigcut\bigcap
\def\logand{\wedge}
\def\Limpl{\Rightarrow}
\def\Liff{\Leftrightarrow}
\def\itm#1 {\item[({#1})]}
\def\ls{\lesssim}
\def\dom{{\rm dom}}
\def\ran{{\rm ran}}
\def\on{{\restriction}}
\def\x{{\tt x}}
\def\qed#1 {~~\null\hfil\null~~\smiley$\,_{\ref{#1}}$~~\break
	\bigbreak}
\def\QED#1 {~~\null\hfil\null~~\SMILEY$\,_{\ref{#1}}$~~\break
	\bigbreak}
\def\A{{\cal A}}

\font\circle=lcircle10
\setbox0=\hbox{~~~~~}
\setbox1=\hbox to \wd0{\hfill$\scriptstyle\smile$\hfill} % mouth
\setbox2=\hbox to \wd0{\hfill$\cdot\,\cdot$\hfill} % eye 
\setbox3=\hbox to \wd0{\hfill\hskip4.8pt\circle i\hskip-4.8pt\hfill} % head
%\setbox4=\hbox to \wd0{\hfil\vrule width 0.2pt 
%                       height 3.5pt depth -1pt\hfil}% nose
\setbox5=\hbox to  \wd0{\hfill--\hfill}
\setbox6=\hbox to \wd0{\hfill$\scriptstyle\frown$\hfill}

\wd1=0cm
\wd2=0cm
\wd3=0cm
\wd4=0cm
\wd5=0cm
\wd6=0cm
\newbox\SMILEBOX
\setbox\SMILEBOX \hbox {\lower 0.4ex\copy1
		 \raise 0.3ex\copy2
		 \raise 0.5ex\copy3
		\copy4
		\copy0{}}
\def\SMILEY{\leavevmode\copy\SMILEBOX}

\newbox\frownbox
\setbox\frownbox \hbox {\lower 0.2ex\copy6
		 \raise 0.3ex\copy2
		 \raise 0.5ex\copy3
		\copy4
		\copy0{}}
\def\frowny{\leavevmode\copy\frownbox}

\newbox\smilebox
\setbox\smilebox \hbox {\lower 0.4ex\box5
		 \raise 0.3ex\box2
		 \raise 0.5ex\box3
		\box4
		\box0{}}
\def\smiley{\leavevmode\copy\smilebox}






\newdimen\eightpt
\newdimen\sixpt
\newdimen\sevenpt
\newdimen\onept
\eightpt=8pt
\onept=0.1pt
\sevenpt=\eightpt \advance\sevenpt-\onept
\sixpt=\eightpt \advance\sixpt-2\onept


\newbox\squarebox
\setbox0=\hbox{\vrule height \eightpt depth -\sevenpt width \eightpt}
\wd0 0cm
\setbox1=\hbox{\vrule height\eightpt depth 0pt width \onept
	\vrule height \onept depth 0pt width \sixpt 
	 \vrule height \eightpt depth 0pt width \onept}
\setbox\squarebox\hbox{\box0\box1 }
\def\square{\copy\squarebox}

\def\proof{\par\noindent{\bf Proof:} \ignorespaces}

%\textheight=8in
%\textwidth=6.5in


\begin{document}
\title{Interpolation of monotone functions in lattices}

\author{Martin Goldstern, TU Wien}

%\address{Institut f\"ur Algebra und Diskrete Mathematik\\TU Wien}
\date{April 17, 1994}

\maketitle



\begin{abstract}
We show that for every  lattice $L_0$ and for 
every cardinal $\kappa$ there is a lattice 
$L \supseteq L_0 $ on  which
every monotone function can be interpolated by a polynomial
on any set of size $\kappa$.  
\end{abstract}



%\def\Pol{{\bf Pol}}
\def\P{{\bf P}}

\section*{Introduction}






Let $(L, {\logand}, {\vee})$ be a lattice.  The  {\bf polynomials}
over $L$ are the well-formed expressions involving constants
from $L$ and/or   formal variables $\x_1$, $\x_2$, \dots\
 together with parentheses and
the formal symbols $\logand$, $\vee$.  The set of
$n$-ary {\bf  polynomial functions}
is the smallest set of functions from $L^n$ to $L$ which
contains all the constant functions  as well as  the projection functions
and is closed under (pointwise) meet and join. Every polynomial in
which at most the variables $\x_1$, \dots, $\x_n$ occur 
defines in an obvious way an $n$-ary polynomial function. Clearly every
polynomial function $f$  is monotone. 

We call a lattice $L$ {\bf $n$-order polynomially complete}  if
\begin{quote}
$(*)$ \qquad  every monotone $n$-ary function is a polynomial function 
\end{quote}
and we say that $L$ is order polynomially complete if $L$ is $n$-order
polynomially complete for every $n$. 

The finite order polynomially complete  lattices were investigated and 
classified by
Schwei\-gert \cite{Schweigert},  Wille \cite{Wille77}, Kindermann 
\cite{Kindermann} and others. 
   The question 
whether infinite order polynomially complete  lattices exist is still open. 
 In \cite{KaiserSauer}, Kaiser
and Sauer showed 
\begin{description}
\itm a Every order polynomially complete  lattice is bounded (i.e.,
	has a largest and a     smallest element)
\itm b Every infinite lattice contains an infinite chain or an
	infinite antichain
\itm c If $L$ contains an antichain of size $\kappa$ or a chain of
	order type $\kappa+1$ or $(\kappa+1)^*$, then $L$ admits at
	least $2^\kappa$ many monotone unary functions,
\end{description}
and concluded that an infinite $1$-order polynomially complete 
 lattice (if one exists at all) cannot be countable, but
must have size at least continuum.  Note that (b) and (c) above are
true not only for lattices but for arbitrary partial orders, so the
theorem is only partially of an ``algebraic'' nature. 
The search for a algebraic proof of the conjecture ``there is no order
polynomially complete infinite lattice'' naturally leads to the
following problem: 
\begin{quote}
 Find a ``structural''  property of polynomial
functions and show that in every infinite lattice there is a monotone
function not satisfying this property.
\end{quote}
In this paper we show that
there are no ``local'' properties of polynomial functions which are
not shared by all monotone functions.  Formally, we prove:

\thm thma Theorem A: Let $L_0$ be a lattice, $n$ a natural number, 
 $f_0:L_0^n \to L_0$ a monotone
partial function.  Then there is a lattice $L$ which contains $L_0$
as a sublattice and a polynomial function $f$ on $L$ which extends
$f_0$.  
\sof

Thus, any monotone function on a lattice
 can be realized as the behaviour of a
polynomial on a suitable extension lattice.   Is it then possible to 
represent ALL monotone functions by polynomials?  We can give  a
``local''  answer to this question in the next theorem. 
Noticing that the lattice $L $ in theorem A can be chosen to
be of the same   
cardinality as $L_0$, we can iterate  theorem A to obtain:

\thm thmb Theorem B:  Let $\lambda $ and $ \kappa$ be infinite
cardinals, and let $L_0$ be a lattice of size $\le \lambda^{\kappa}$.
  Then
there is a lattice $L$ of size $\lambda^{\kappa}$, $L_0 \subseteq L$
such that for every $n$, for every  
partial monotone  function $f:L^n\to L$ with domain of size ${\le}\kappa$ 
there is a polynomial function $f'$ on $L$ which extends $f$, i.e.,
$L$ is ``$\kappa$-locally order polynomially complete.''   
\sof
In particular, for any lattice $L_0$ we can (choosing $\kappa =
\lambda = |L_0|$) get a 
lattice $L \supseteq L_0$ of size $2^{|L_0|}$  such
that every monotone function $f:L_0\to L_0$ is induced by a polynomial
over $L$.  (In the terminology of \cite{KaiserLidl} we could phrase this as follows:  Every lattice is
``extension order polynomially complete.'')


For example, letting $\lambda = \kappa = {\aleph_0}$, we get a lattice
of size continuum on which every monotone function can be interpolated
by a polynomial on every countable set.   



\rem notat Notation: Lattices are denoted by $L$, $L'$, $L_1$, etc.
When we consider several lattices, we use the self-explanatory
notation $ \logand _1$, $\le_2$, etc. for the operations/relation in
$L_1$, $L_2$, etc.   We read lattice operations from left to right:
$a\vee b \logand c = (a \vee b) \logand c$, 
$a \logand  b \vee c = (a \logand  b) \vee c$.   For $a\in L$ we let
$(a]:= \{b\in L: b \le a\}$. 

$L_1 \subseteq L_2$ or $L_2 \supseteq L_1$ always means that $L_1$ is
a sublattice of $L_2$. 

We use $\alpha$, ${\beta}$, ${\gamma}$ to range over ordinals,
$\kappa$, $\lambda$, $ \mu$ for cardinals. The set of natural numbers
is denoted by $\omega$.  $|A|$ is the cardinality of
the set $A$. $\lambda^\kappa$ (cardinal exponentiation) is the
cardinality of $\{f: \ f:\kappa \to \lambda\}$.

$f,g,h$ are always unary functions, $\dom(f)$ is the domain of $f$ and
$\ran(f)$ is the range of $f$. $f:L_1 \to L_2$ means $\dom(f) = L_1$,
$\ran(f) \subseteq L_2$, unless we explicitly call $f$ ``partial'', in
which case we only have $\dom(f) \subseteq L_1$. 

$f\on A$ is the restriction of $f$ to $A$. ``$f$ extends $g$'' or ``$
g \subseteq f$'' means $g = f \on \dom(g)$.   $f[A]=\ran(f\on A)$. 

We write $\SMILEY_x$ to denote the end of the proof of theorem (lemma,
etc.)~$x$, and we write $\smiley_y$ if (most of) a proof is left to
the reader.  $\frowny$ marks the end of a wrong proof.
\sof

\bigskip


\rem ack Acknowledgements:
I am grateful to Hans Kaiser for providing the initial motivation, and to
Gerhard Dorfer for simplifying the original proof in section 2. 
\sof

\section{Continuous join-homomorphisms}

First we remark that it is enough  to prove theorem A for the case
$n=1$.  This follows easily from fact~\ref{n=1fact} below:

\rem deltadef Definition and Fact:  Let $L$ be a lattice, $n>0$.  Define
$\delta_n: L \to L^n$ by $\delta_n(x)= \<x, \ldots, x>$.  Then
$\delta_n $ is an embedding of lattices. 
\sof

\rem n=1fact Fact: Let $L$ be a bounded lattice, $n>0$. Then there is a
polynomial $\pi_n$ over  $L^n$ such that
the induced function from $(L^n)^n \to L^n$ (which we again call
$\pi_n$) satisfies 
$$ \pi_n(\delta_n(a_1), \ldots, \delta_n(a_n)) = 
	\<a_1, \ldots, a_n> $$
for all $a_1$, \dots, $a_n\in L$. 
\sof
\proof Let $a=\inf L$, $b=\sup L$. Let $e_1:= \<b, a,\ldots, a>$,
\dots, 
$e_n:= \<a, \ldots, a, b>$.   Let $\pi_n$ be 
the polynomial 
$(\x_1 \logand b_1) \vee \cdots \vee (\x_n \logand b_n)$. \QED n=1fact

\rem n=1conc Conclusion: It is enough to prove theorem A for the case
$n=1$. 
\sof
\proof Without loss of generality assume that $L_0$ is bounded. 
Let $f_0$ be an $n$-ary function on $L_0$. 
So $\delta_n \circ f_0$ is a unary function on $L_0^n$. 
Find a lattice
$L \supseteq L_0^n$ and a polynomial function $f':L \to L$ extending
$\delta_n \circ f_0$.
Now let
$f:L^n\to L$ be defined by 
$f(x_1, \ldots, x_n) = f'(\pi_n(x_1, \ldots, x_n))$. It is clear that
(identifying
 $L_0$ with $\delta_n[L_0] \subseteq L_0^n \subseteq L$) 
$f$ is a polynomial function extending $f_0$. 
\QED n=1conc

So from now on we will only on concentrate on unary functions. 


\rem cdef Definition:  A lattice $L$ is {\bf complete}, if every subset $A$ of
$L$ has a greatest lower bound, called $\inf A$.  In a complete
lattice, also every set has a least upper bound, $\sup A$. In
particular, $L$ must be bounded: $0 = \inf L = \sup\emptyset$,
$1=\inf\emptyset = \sup L$. 
\sof

\rem cfact Fact: For every lattice $L$ there is a complete lattice
$\bar L$ such that $L \subseteq \bar L$.
\sof

\proof Well known (see, e.g., \cite{Graetzer}). Let $\bar L$ be the
set of ideals of $L$, i.e., the 
set of downward closed upward directed subsets of $L$ (including the
empty set), and embed $L$ via $x\mapsto \{y: y\le x\}$. 
\qed cfact


\rem extendfact Fact: (a) 
If $f:L_1 \to L_2$ is a partial monotone function, and if
$L_2$ is a complete lattice, then $f$ can be extended to a total
monotone function.\\
(b)  If $f$ is a partial monotone function
from $L$ to $L$ then there is a lattice $\bar L$ of the same cardinality
as $ L$ and a total monotone function $\bar f:\bar L\to \bar L$
extending $f$.
\sof

\proof (a): Let $\bar f(x) = \sup\{ f(y): y\le x, y\in \dom(f)\}$. \\
(b):  Let $L' \supseteq L$ be a complete lattice, and let $f':L'\to
L'$ be a total function extending $f$.  Now let $\bar L \subseteq L'$
be the structure generated from $L$ by the binary operations $\logand
$ and $\vee$ and the unary function $f'$.  
\QED extendfact

To explain the motivation for the following definition, consider a
complete lattice $L$ and the polynomial  $p(\x) =  \x\vee a$
for some fixed $a\in L$. Clearly $p(x\vee y) = p(x) \vee p(y)$ and
moreover $p(\sup A) = (\sup A )\vee a = \sup (A\cup \{a\}) 
= \sup \{x\vee a: x\in A\} = \sup  p[A]$ for any nonempty $A \subseteq L$. 



\rem jhdef Definition: $f:L_1 \to L_2$ is called {\bf join-homomorphism} if for
all $x,y\in L_1$ we have $f(x) \vee f(y) = f(x\vee y)$. 
\newline 
We call $f: L_1 \to L_2$ a {\bf continuous join-homomorphism} if 
\begin{description}
\itm a $f$ is monotone
\end{description}
{\bf and}  there
is a function $f^*:L_2\to L_1$ such that
\begin{description}
\itm b $\forall y \in L_2\ f(f^*(y))\le y$
\itm c $\forall x \in L_1\, \forall y \in L_2 \ f(x)\le b \Limpl a \le
	f^*(y)$. 
\end{description}
We define ``meet-homomorphism'' and ``continuous meet-homomorphism''
dually.
\sof

\rem chrem Remark:
 \begin{enumerate}
\item Every join  homomorphism is monotone. 
\item Every continuous join-homomorphism is a join-homomorphism.
\item If $f$ is a continuous join-homomorphism, then $f^*$ is unique,
namely, $f^*(y)$ must be the greatest element of 
$$ \{ x\in L_1: \ f(x) \le y\}$$
\item (a)\&(b)\&(c) above can be replaced by (a)\&(bc), where
\begin{description}
\itm bc  $\forall a \in L_1\, \forall b \in L_2 \ f(a)\le b \Liff a \le
	f^*(b)$. 
\end{description}
\item If $L_1$ is a complete lattice, then $f:L_1 \to L_2$ is a
	continuous join-homomorphism iff $f(\sup A)= \sup f[A]$ for
	all $A \subseteq L_1$. 
 \end{enumerate}
\sof 

\proof (1), (3) and (4) are clear.

 (2): Since $f$ is monotone, $f(x\vee y) \ge f(x)\vee f(y)$.
Conversely, let $z:=f(x) \vee f(y)$.  Then $f(x)\le z$, so $x \le
f^*(z)$, and similarly $y\le f^*(z)$. Hence $x\vee y \le f^ *(z)$, so
$f(x\vee y) \le f f^*(z) \le z = f(x) \vee f(y)$ and we are done.

(5): If $f(\sup A)= \sup f[A]$, then $f$ is clearly a join 
homomorphism, hence monotone. Let $f^*(y):= \sup\{x: f(x)\le y \}$.
It is  clear that $f f^ *(y) \le y$, and that $f(x)\le y$ implies
$x\le f^*(y)$. 

Conversely, assume that $f$ is a continuous join-homomorphism.  Let $A
\subseteq L_1$, and let $a = \sup A$.
 The monotonicity of $f$ shows that $f(a)$ is an upper bound for
$f[A]$. Now let $b$ be any upper bound for $f[A]$.  We have $\forall
x\in A \ f(x) \le b$, hence $\forall x\in A\ x\le f^*(b)$, so $a=\sup
A \le f^*(b)$, hence $f(a)\le f(f^*(b))\le b$. So $f(a)$ is indeed the
least upper bound of $f[A]$. 
\QED chrem


The next lemma shows that the property isolated in
definition \ref{jhdef} more or  
less characterizes the possible behaviours of 
the polynomial function $x\mapsto x\vee a$, at
least for complete lattices. 


\rem twodef Definition: Let $L_1$ and $L_2$ be disjoint lattices,  $f:L_1 \to
	L_2$.  We define $L_1 +_f L_2 = (L_1 \cup L_2, \le) $ as
	follows: 

\begin{tabular}{rl} $x \le y$ iff: & either $x,y \in L_1$, $x \le_1 y$\\
& or $x,y \in L_2$, $x \le_2 y$\\
& or $x \in L_1$, $y\in L_2$, $f(x)\le_2 y$
\end{tabular}

\sof 
%\picskip 4cm
\vbox{
\unitlength=1mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(81.00,129.00)
\put(30.50,82.00){\oval(21.00,28.00)[]}
\put(70.50,115.00){\oval(21.00,28.00)[]}
\put(44.00,93.00){\vector(1,1){13.00}}
\put(46.00,103.00){\makebox(0,0)[cc]{$f$}}
\put(28.00,81.00){\makebox(0,0)[cc]{$x$}}
\put(65.00,111.00){\makebox(0,0)[cc]{$f(x)$}}
\end{picture}
\vskip-60mm
 }

\thm  twolem  Lemma:  Assume that 
 $f:L_1 \to L_2$ is a continuous join-homomorphism.
 Let  $L:=      L_1 +_f L_2 $. Then 
\begin{description}
\itm a $L$ is a lattice.
\itm b $L_1, L_2 \subseteq L$. 
\itm c If $L_2$ has a smallest element $a_2$, then for all $x\in L_1$
	we have $f(x)= x\vee a_2$. 
\end{description}
\sof
\proof  Transitivity of $\le$ follows from the monotonicity of $f$:
Let $x\le y \le z$.  The only nontrivial case is when $x\le_1 y$ and
$f(y) \le_2 z$.   But then also $f(x)\le_2 f(y) \le_2 z$.

Now let $f^*:L_2\to L_1$ be such that $f^*(y)$ is always the greatest 
element of $\{x\in L_1: f(x)\le y\}$.   We claim that for $x\in L_1$,
$y\in L_2$ we have $\inf\{x,y\}=x \logand _1 f^*(y)$.   For a proof,
note  that $z$
is a lower bound for $\{x,y\}$ iff $z\le_1 x$ and $f(z)\le_2 y$, which
is equivalent to  $z\le_1 x$ and $z\le_1 f^*(y)$, i.e., 
$z \le x \logand_1 f^*(y)$.

 We leave it to the reader to
check the other cases of the following table: 
$$
\inf\{x,y\} = \cases{ x \logand_1 y & if $x,y\in L_1$\cr
		x \logand_2 y & if  $x,y\in L_2$\cr
		x \logand_1 f^*(y) & if $x\in L_1$, $y\in L_2$\cr}
$$ 
$$
\sup\{x,y\} = \cases{ x \vee_1 y & if $x,y\in L_1$\cr
		x \vee_2 y & if  $x,y\in L_2$\cr
		f(x) \vee_2 y & if $x\in L_1$, $y\in L_2$\cr}
$$

(b) and (c) are now clear. 
\QED twolem


Conversely, it is easy to check 
the following:  If $f:L_1 \to L_2$, and
$L_1$ has a largest element $b_1$, then we also have: 
\begin{quote}
If $L_1+_f L_2$ is a lattice, then $f$ is a continuous
join-homomorphism, witnessed by $f^*(y)=y \logand b_1$. 
\end{quote}

The  construction in lemma \ref{twolem} deals with the situation where
the  function 
which we want to  represent by a polynomial has disjoint domain and
range.  Below we give a slight extension of the previous lemma
that  deals with the case $f:L\to L$.  (The following lemma is also a
generalization of a construction considered in \cite{FriedLakser}.) 

\thm six Lemma: Let $L_0$, $L_1$, \ldots, $L_5$ be disjoint
lattices, and let 
$f_i:L_i\to L_{i+1}$, $i=0, \ldots, 5$ be monotone functions.  Assume
that each $f_{i}$ is a continuous meet-homomorphism for $i=0,2,4$ and a
continuous join-homomorphism for $i=1,3,5$. Then the following
structure $L$ is a lattice: 



\vbox{ 
\unitlength=1mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(134.00,134.00)
\put(13.00,117.00){\makebox(0,0)[cc]{$L_4$}}
\put(28.00,94.00){\makebox(0,0)[cc]{$L_5$}}
\put(47.00,118.00){\makebox(0,0)[cc]{$L_0$}}
\put(70.00,94.00){\makebox(0,0)[cc]{$L_1$}}
\put(94.00,118.00){\makebox(0,0)[cc]{$L_2$}}
\put(119.00,93.00){\makebox(0,0)[cc]{$L_3$}}
\put(17.00,109.00){\vector(3,-4){6.67}}
\put(36.00,99.00){\vector(2,3){7.33}}
\put(56.00,110.00){\vector(1,-1){10.00}}
\put(78.00,100.00){\vector(1,1){10.00}}
\put(103.00,110.00){\vector(4,-3){11.00}}
\put(124.00,101.00){\vector(1,1){10.00}}
\put(2.00,100.00){\vector(3,4){6.67}}
\put(66.00,134.00){\makebox(0,0)[cc]{$1$}}
\put(66.00,69.00){\makebox(0,0)[cc]{$0$}}
\put(54.00,101.00){\makebox(0,0)[cc]{$f_0$}}
\put(77.00,106.00){\makebox(0,0)[cc]{$f_1$}}
\put(101.00,103.00){\makebox(0,0)[cc]{$f_2$}}
\put(123.00,106.00){\makebox(0,0)[cc]{$f_3$}}
\put(15.00,101.00){\makebox(0,0)[cc]{$f_4$}}
\put(33.00,105.00){\makebox(0,0)[cc]{$f_5$}}
\end{picture}
\vskip-63mm
}

The universe of $L$ is the disjoint union $L_0 \cup L_1 \cup \cdots
\cup L_5 \cup \{0,1\}$.  The partial order on $L$ is defined as
follows:

\begin{tabular}{rl}
$x\le y $ iff & $x=0$ or $y=1$  \\
& or for some $i\in\{0,\ldots, 5\}$, $x,y\in L_i$ and  $x \le_i y$ \\
& or  for some $i\in \{1,3,5\}$, $x\in L_i$, $y\in L_{i+1}$ and
$f_i(x)\le_{i+1} y$\\
& or for some $i\in\{0,2,4\}$, $x\in L_{i+1}$, $y\in L_i$ and
$x\le_{i+1} f_{i}(y)$. 
\end{tabular}

Moreover, if $a_i=\inf L_i$, $b_i=\sup L=i$, then for all $x\in L_0$
we have 
$$  f_5\, f_4\, f_3 \, f_2 \, f_1 \, f_0 (x) = 
x \logand b_1 \vee a_2 \logand b_3 \vee a_4 \logand b_5 \vee a_0.$$

(It is understood that addition of indices is performed modulo 6, i.e.\ 
$L_6 = L_0$, $L_7=L_1$, etc.)
\sof 
\proof We leave it to the reader to check that join and meet can be
computed accoding to the following rules:
\begin{itemize}
\item $\inf\{x,0 \} = 0$, $ \sup \{x,0\}= \inf\{x,1\}=x$, 
	$\sup\{x,1\} = 1$.
\item If $x,y\in L_i$, then $\inf\{x,y\}= x \logand_i y$,
	$\sup\{x,y\}=x\vee_i y$.
\item If $x\in L_i$, $y\in L_{i+1}$, $i $ even, 
	then $\inf\{x,y\} = f_i(x) \logand_{i+1}  y $, 
	 $\sup\{x,y\} = x \vee_i f_i^*( y) $. 
\item If $x\in L_i$, $y\in L_{i+1}$, $i$ odd, 
	then $\inf\{x,y\} = x \logand_i f_i^*(y) $, 
	 $\sup\{x,y\} = f_{i}(x) \vee_{i+1}  y $. 
\item If $x\in L_i$, $y \in L_{i+2}$, $i $ odd, 
	then $\inf\{x,y\} = 0$,
	 $\sup\{x,y\} = f_i(x) \vee_{i+1}  f_{i+1}^*(y) $. 
\item If $x\in L_i$, $y \in L_{i+2}$, $i $ even, 
	then $\inf\{x,y\} = f_i(x) \logand_{i+1}  f_{i+1}^*(y) $, 
	 $\sup\{x,y\} = 1 $. 
\item If $x \in L_i$, $y\in L_{i+3}$, 
	then $\inf\{x,y\} = 0$,
	 $\sup\{x,y\} = 1 $. 
\end{itemize}
\qed six



\section{Factoring monotone functions}


By what we have seen so far, theorem A is true if we change
the condition ``$f$  monotone'' to ``$f$ a continuous join-homomorphism''.
The dual is of course also true.  Our next aim is to show that every
monotone function can be written as a  composition of a continuous
join-homomorphism and a continuous meet-homomorphism. 

\rem stardef Definition: For any lattice $L$ let $\hat L$ be the set
of all downward closed subsets of $L$: 
$$ \hat L = \{A \subseteq L : \forall a\in A\, \forall b \le a\,\,
b\in A\}.$$ 
\sof

% \rem stardef Definition:  For any lattice $L$ define a binary relation
% $\ls $ on  
% $\P(L)$, the power set of $L$ as follows: 
% $$ A \ls B \ \ \Liff \ \ \forall x\in A\,\, \exists y\in B \ x \le y$$
% (in particular $\emptyset \ls A$ for all $A \subseteq L$, and more
% generally $A \subseteq B $ implies $A \ls B$.)
% \sof
\rem starfact Fact: For any lattice $L$ the partial order $(\hat L,
\subseteq ) $ is a complete lattice, with operations 
%
% \rem starfact Fact and Definition: For $A, B \subseteq L$ let $A \sim
% B$ iff $A \ls 
% B $ and $B \ls A$.  Then $\sim $ is an equivalence relation on
% $\P(L)$.  Let $A_\sim$ be the equivalence class of $A$, and let
% $\P(L)/{\sim} = \{A_\sim: A \subseteq L \}$ be the set of equivalence
% classes.  Then  there is a partial order $\le$ on $\P(L)$ which
% satisfies 
% $$ A_\sim \le B_\sim \ \Liff A \ls B. $$
% \sof 
% 
% \proof Clear. \qed starfact
% 
% 
% 
% 
% \rem starisL Fact: $\P(L)/{\sim}$ as defined above is a lattice, with
 \begin{eqnarray*}
 A \vee B & =& A \cup B\ \ 
\hbox{(more generally, $\sup \A = \bigcup \A$ for any $\A \subseteq
\hat L$)}
 \\
 A\logand  B & =& \{z: \exists  x\in A\, \exists  y\in B\ z\le
x\logand y\}\\ 
 \end{eqnarray*}
 \sof
 \proof Straightforward.
 \qed starfact
 
 \thm isch Lemma: Assume that $L$ is a complete lattice.  Then the map 
 $g:L \to \hat L$, defined by $g(x)= (x] := \{y\in L: y\le x\}$, is a
continuous  meet-homomorphism. 
 \sof
 \proof We will use the dual of remark~\ref{chrem}(5). 
$x\le y$ implies $(x] \subseteq (y]$, hence $g$ is monotone. 
\\
Let $A \subseteq L$, $a= \inf A$.  We have to show $g(a)=\inf g[A]$.
It is clear that $g(a)$ is a lower bound for $g[A]$, since
$g$ is monotone.  So let $B\in \hat L$ be any lower bound for $g[A]$.
Then $B \subseteq (x]$ for all $x\in A$, hence each $b\in B$ is a lower
bound for $A$. So each $b\in B$ is $\le a$, so $B \subseteq (a] =
g(a)$. 
%  Let
% $g^*(A_\sim) := \sup A$.  Note that $g^*$ is well-defined, because $A
% \ls B$ implies $\forall x\in A\,\, x\le \sup B$ and hence $\sup A \le
% \sup B$. 
% \\Next we have to check $g g^*(y)\ge y$ for all $y\in \P(L)/{\sim }$
% (remember that we deal with a continuous {\bf meet}-homomorphism here,
% so we have to use the dual of definition \ref{jhdef}). 
% Let $A\in \P(L)$. Then for all $x\in A$ we have $x\le \sup A =
% g^*(A_\sim) $, so $A \ls \{g^*(A_\sim)\}$, hence 
% $A_\sim \le \{g^*(A_\sim)\}_\sim = g g^ *(A_\sim)$. 
% \\
% Finally we have to check $g(x) \ge y \Limpl x \ge g^*(y)$.  Let
% $y=A_\sim$. If $g(x) \ge A_\sim$, then $A \ls \{x\}$, so 
% $\forall a\in A\, a\le x$, hence $x\ge \sup A = g^*(A_\sim)$. 
 \QED isch
 



\thm factorize Factor Lemma: Assume that $f:L_0 \to L_2$ is monotone,
and 
$L_2$ is complete. 
Then there is a function $h:\hat L_0 \to L_2$ satisfying
\begin{itemize}
\item $h$ is a continuous join-homomorphism 
\item $h\circ g = f$ (where $g$ is the continuous meet-homomorphism
	from the previous lemma)
\end{itemize}
%%\picskip 5cm
%\vbox{ \input three.pic
%\vskip-57mm
%} 
$$\vcenter{ \ialign{&\hfil$#$\hfil\cr
L_0 & \multispan3{\hfil
 $\mathop{\longrightarrow}\limits^{\textstyle  f}$\hfil}&L_2\cr
 &\lower2pt\llap{$g$}\searrow & &\nearrow\lower3pt\rlap{$h$} \cr
 &&\hat L_0\cr  }
}$$
\sof
\proof  Let $h(A)= \sup f[A]$. Clearly $h$ is monotone. Also, since
$f$ is monotone we get $$
h(g(x))= \sup f[\{y: y\le x \}] = f(x)$$
For any $\A \subseteq \hat L$ we have $\sup \A
= \bigcup \A$ and 
$$\sup h[\A] = 
\sup\{\sup\{f(x): x\in A\}:A\in \A\} = 
\sup \{f(x): x\in \bigcup \A\} = h(\sup\A).$$
% 
% 
% 
% \proof Let $h':\P(L_0) \to L_2$ be defined by $h'(A) = \sup f[A]$. 
% We claim that 
% $$ (*) \qquad \forall A,B \subseteq L_0: 
% A \ls B \ \Limpl \  h'(A) \le h'(B)$$
% Proof of the claim: Let $s:A \to B$ be such that $\forall x\in A \,
% x\le s(x)$. Then 
% $$ h'(A) = \sup \{f(x): x\in A \} 
% \le \sup \{f(s(x)): x\in A \} 
% \le \sup \{f(y): y\in B \} = h'(B).$$
% 
% By $(*)$ there is a monotone function $h: \P(L_0)/{\sim} \to L_2$
% satisfying 
% $$ (**) \qquad \forall A \subseteq L_0 :   h(A_\sim) = \sup \{f(x):
% x\in A\}$$
% For $a\in L_0$ we have $h g(a) = h(\{a\}_\sim) = \sup \{f(x):
% x\in \{a\}\} = f(a)$. 
% 
% 
% For $y\in L_2$, let $h^*(y) := \{ x\in L_0: f(x)\le y\}_\sim$.  
% We claim that $h^*$ witnesses  that $h$ is a continuous
% join-homomorphism: 
% First we check $h h^*(y) \le y$.  We have $h h^*(y) = 
% h(\{x\in L_0: f(x) \le y \}_\sim) = 
% \sup \{ f(x): f(x) \le y \} \le y$. 
% \\
% Now we have to check that $h(A_\sim) \le y$ implies $A_\sim \le
% h^*(y)$:  If $h(A_\sim) \le y$, then
% $\sup\{ f(x): x\in A\} \le y$,  so $\forall x\in A \, f(x)\le y$,
% hence $A \subseteq \{x\in L_0: f(x) \le y\}$ which implies 
%  $A_\sim \le   \{x\in L_0: f(x) \le y\}_\sim = h^*(y)$. 
% 
\QED factorize
  






Now we can put the pieces together:

\noindent{\bf Proof of theorem A:}
By conclusion \ref{n=1conc} we only have to consider the case of a
unary function. 
Let $L_0$ be a lattice, $f:L_0 \to L_0$ a partial monotone function.
By facts \ref{cfact} and \ref{extendfact} we may assume that $L_0$ is
complete, and that $f$ is a total function. Let $L_1:= \hat L_0$
as in definition \ref{stardef}, and let $f_0 : L_0\to L_1$ be the continuous
meet-homomorphism defined in lemma \ref{isch}, $f_0(x)= (x]$.  Let
$L_2$ be an isomorphic copy of $L_0$, $i:L_0 \to L_2$ an isomorphism.
The map $i\circ f:L_0 \to L_2$ is monotone, so we can find a
continuous join-homomorphism $f_1:L_1\to L_2$ such that $f_1\circ f_0
= i \circ f$. 
$$\vcenter{ \ialign{&\hfil$#$\hfil\cr
L_0 & \multispan3{\hfil
 $\mathop{\longrightarrow}\limits^{\textstyle i\circ f}$\hfil}&L_2\cr
 &\lower2pt\llap{$f_0$}\searrow & &\nearrow\lower3pt\rlap{$f_1$} \cr
 &&L_1\cr  }
}$$

Let $L_3$, $L_4$, $L_5$ be disjoint  isomorphic copies of $L_2$ with
isomorphisms 
%$$L_2\mathop{\to}\limits^{f_2}
%L_3 \mathop{\to}\limits^{f_3}
%L_4 \mathop{\to}\limits^{f_4}
%L_5 \mathop{\to}\limits^{f_5}
%L_0
%$$
$$\begin{array}{cccccccccc}
L_2&         &   &        &L_4&         &   &        &L_0&\\
   &\lower3pt\llap{$f_2\!\!$}
    \searrow &   &\raise1pt\llap{$f_3\!\!$} 
		  \nearrow&   &\lower3pt\llap{$f_4\!\!$}
			       \searrow &   &\raise1pt\llap{$f_5\!\!$}
					     \nearrow&\\
   &         &L_3&        &   &         &L_5\\
\end{array}
$$
such that
$f_5 \circ f_4  \circ f_3  \circ f_2  \circ i :L_0\to L_0$ is the
identity map on $L_0$.  Then 
$f_5  \circ f_4  \circ f_3  \circ f_2  \circ f_1  \circ f_0 = f:L_0
\to L_0$. 

Letting $L:= L_0 \cup \cdots \cup L_5 \cup \{0,1\}$ as in lemma
\ref{six}, we get a lattice $L$.  Letting $a_i:= \inf(L_i)$, $b_i:=
\sup (L_i)$ we get 
$$ \forall x\in L_0\ f(x) = x \logand b_1 \vee a_2 \logand 
b_3 \vee a_4 \logand b_5 \vee a_0$$ 
\QED thma

\rem 1rem Remark:  We may assume that the lattice $L$ is of the same
cardinality as  $L_0$. (Assuming, of course,  that $L_0$ is infinite.
If $L_0$ is finite the $L$ will also be finite of size 
$\le 2^{|L_0|}+5|L_0|+2$.)
\sof
\proof  Let $L'$ be the sublattice of $L$ generated by the elements of
the original (possibly non-complete) $L_0$ plus the coefficients of
the polynomial $p$. 
\QED 1rem 

\section{Proof of theorem B} 

Let $\mu:= \lambda ^{\kappa}$.  Let ${\Gamma} : \mu \times \mu \times
\omega \to \mu$
be a bijection with the property 
$$ (**)\forall {\beta}, {\gamma} < \mu\,\, \forall n: 
\ {\Gamma}({\beta},{\gamma},n) \ge {\gamma}$$
Start with an arbitrary infinite lattice $L_0$ of cardinality $\le
\mu$.  We will construct a continuous increasing sequence $(L_\alpha:
\alpha \le \mu)$  
of lattices and a sequence $(p_\alpha: \alpha < \mu) $ of polynomials,
where $p_\alpha$ has coefficients in $L_{\alpha+1}$, and
$|L_\alpha|\le \max(|\alpha|, |L_0|)$. 

First we deal with successor steps:  $L_\alpha$ has size $\le \mu$ so
for any $n$ the set of partial 
functions from $L_\alpha^n$ to $L_\alpha$ whose domain has size $\le
\kappa$ has cardinality at most $\mu^\kappa = \mu$.  Let 
$(f^{\beta}_{\alpha,n}: {\beta} < \mu) $ be an enumeration of these
functions. 
\\
We can find ${\beta}_\alpha, {\gamma}_\alpha\in \mu$, $n_\alpha\in
\omega$  such that
${\Gamma}({\beta}_\alpha, {\gamma}_\alpha, n_\alpha ) = \alpha$.  As
${\gamma}_\alpha \le \alpha$, we already know what
$f^{{\beta}_\alpha}_{{\gamma}_\alpha, n_\alpha}$ is, namely, a partial
function 
from $L^{n_\alpha}_{{\gamma}_\alpha}$ to $L_{{\gamma}_\alpha}$, hence
also a 
partial function from $L^{n_\alpha}_\alpha$ to $L_\alpha$.   
% By fact~\ref{extendfact}
% we can find a lattice
% $L_\alpha ' \supseteq L_\alpha$ of the same cardinality as $L_\alpha$
% and a total monotone function $f_\alpha: L_\alpha ' \to L_\alpha ' $
% which extends $f^{{\beta}_\alpha}_{{\gamma}_\alpha}$. 
% Let $L_\alpha '' \supseteq L_\alpha '$ be an arbitrary lattice of size
% $\le \mu$.  


By theorem A we can find a lattice $L_{\alpha+1}
\supseteq L_\alpha  $ of again the same size and a polynomial
$p_\alpha$ with coefficients in $L_{\alpha+1}$ such that the
polynomial function induced by $p_\alpha$ (which we again call
$p_\alpha$) extends $f_\alpha$ and hence also
$f^{{\beta}_\alpha}_{{\gamma}_\alpha,n_\alpha }$. 

This concludes the construction of $L_{\alpha+1}$ and $p_\alpha$. 

If $\alpha$ is a limit ordinal, we let $L_\alpha:= \bigcup_{{\beta} <
\alpha} L_{\beta}$. 



Finally, let $L:= L_\mu = \bigcup_{\alpha < \mu} L_\alpha$.  $L$ is of
size $\mu$. Let $f$ be an arbitrary partial monotone function from $L^n$
to $L$ with domain of cardinality $ \le   \kappa$.  We have to find
 a polynomial which extends  $f$.   Since $\mu^{\kappa}
= \mu$ we have $\kappa < cf(\mu)$, so there is a ${\gamma} $ such that
$\dom(f) \cup \ran(f) \subseteq L_{\gamma}^n$. Let $f=
f^{\beta}_{\gamma,n}$.  Letting $\alpha:= \Gamma({\beta}, {\gamma},n )
\ge {\gamma}$ we get a polynomial $p_\alpha$ with coefficients in
$L_{\alpha+1}$ such that the induced polynomial function (in
$L_{\alpha+1}$ as well as in $L$) extends $f$.  \QED thmb 


\nocite{KaiserSauer}
\nocite{FriedLakser}
\nocite{Schweigert}
\nocite{ErneSchweigert}

\nocite{Wille77}
% \nocite{BakerPixley}
%\nocite{Kindermann}
\nocite{Graetzer}
%\nocite{Schmidt87}



\begin{thebibliography}{1}

\bibitem{ErneSchweigert}
Marcel Ern\'e and Dietmar Schweigert.
\newblock Pre-fixed points of polynomial functions on lattices.
\newblock {\em Algebra Universalis}, 31:298--300, 1994.

\bibitem{FriedLakser}
Ervin Fried and Harry Lakser.
\newblock Polynomial automorphism of lattices.
\newblock {\em Algebra Universalis}, 27:371--384, 1990.

\bibitem{Graetzer}
G.~Gr{\"a}tzer.
\newblock {\em General Lattice Theory}.
\newblock Series on Pure and Applied Mathematics. Academic Press, New York,
  1978.

\bibitem{KaiserLidl}
H.~Kaiser and R.~Lidl.
\newblock {Erweiterungs- und R\'edei\-polynom\-voll\-st\"andig\-keit
  universaler Algebren}.
\newblock {\em Acta Mathematica Scientiarum Hungaricae}, 30:171--176, 1993.

\bibitem{KaiserSauer}
Hans Kaiser and Norbert Sauer.
\newblock {On order polynomially complete lattices}.
\newblock {\em Algebra Universalis}, 30:171--176, 1993.

\bibitem{Kindermann}
M.~Kindermann.
\newblock {\"Uber die \"Aquivalenz von
  Ord\-nungs\-poly\-nom\-voll\-st\"andig\-keit und Toleranz\-ein\-fach\-heit
  endlicher Ver\-b\"ande}.
\newblock In {\em Contributions to General Algebra}, pages 145--149, 1978.

\bibitem{Schweigert}
Dietmar Schweigert.
\newblock {\"Uber endliche, ord\-nungs\-poly\-nom\-voll\-st\"andige
  Ver\-b\"an\-de}.
\newblock {\em Monatshefte f\"ur Mathematik}, 78:68--76, 1974.

\bibitem{Wille77}
R.~Wille.
\newblock {Eine Charakterisierung endlicher,
  ord\-nungs\-poly\-nom\-voll\-st\"an\-diger Ver\-b\"ande}.
\newblock {\em Archiv der Mathematik}, 28:557--560, 1977.

\end{thebibliography}
\bigskip

\noindent
Martin Goldstern\\
Institut f\"ur Algebra und Diskrete Mathematik\\
Technische Universit\"at                        \\
Wiedner Hauptstra\ss e 8--10/118.2                \\
A 1040 Wien
\smallskip


{\tt Martin.Goldstern@tuwien.ac.at}



\end{document}



