% \author{Martin Goldstern}
% \title{Interpolation in $\{0,1\}$-lattices}

% latex2e needed, also epic and eepic


\documentclass  [12pt]{amsart}


\usepackage{amsthm}
\usepackage{epic}
\usepackage{eepic}
\swapnumbers

\renewcommand{\baselinestretch}{1.5}
\textwidth150mm
\textheight220mm
\parindent5mm
\advance\hoffset-2cm



\def\xx#1 {\newtheorem{#1}[thm]{#1}}
\newtheorem{thm}{Theorem}[section]
\def\itm#1 {\item[{(#1)}]}



\theoremstyle{definition}
\xx Notation
\xx {Abuse of Notation}

\xx {Definition and Fact}
\xx Definition 
\xx Fact
\xx {More Notation}
\xx {Even More Notation}

\theoremstyle{plain}
\xx Theorem
\xx Conclusion
\xx Lemma
\xx {Main Lemma}
\xx Corollary

\theoremstyle{remark}
\xx Observation
\xx Remark




\newtheorem{Conclusion2}{Conclusion$^2$}[section]
\newcommand{\Y}{{\mathsf{Y}}}
\newcommand{\M}{{\mathsf{M}}}
\newcommand{\dom}{{\rm dom}}   % change that. \operator??
\def\itm#1 {\item[({#1})]}
\def\o0{\mbox{$\{0,1\}$}}
\newcommand{\3}{\ss}

\newcommand{\x}{{\tt x}}
\newbox\happybox
\setbox1=\hbox{$\smile$}
\setbox0=\hbox to \wd1{\hfil$\cdot\cdot$\hfil}

\setbox\happybox=\hbox{\raise4pt\rlap{\box0}\lower1pt\box1}
\newcommand{\happy}{\copy\happybox}


   
\begin{document}
\author{Martin Goldstern}
\thanks{The author was  supported by the FWF through an Ernst
Schr\"odinger fellowship}
\address{Technische Universit\"at\\  Wiedner Hauptstra\3e
  8--10/118.2
\\
A-1040 Wien
}
\email{Martin.Goldstern@tuwien.ac.at}

\title{Interpolation in $\{0,1\}$-lattices}
\thanks{A more recent version of this paper may be
 available in the World-Wide Web
 at {\tt http://info.tuwien.ac.at/goldstern/}}
\begin{abstract}
The following theorem is known: 

Let~$L$ be a lattice, $f: L^n \to L$ monotone. 
Then there is a lattice $L^*$ containing $L$ as a sublattice, and a
lattice polynomial $p$ with coefficients in $L^*$ such that 
$p(a_1,\ldots, a_n) = f(a_1,\ldots, a_n)$ for all $a_1,\ldots , a_n \in
L$.

We show here that if $L$ is a bounded lattice with a least element 0 
and a  greatest element $1$, then we can choose $L^*$ as above  in which $0$
and $1$ are still minimal and maximal, respectively. 
  Iterating this construction long enough
yields a bounded lattice in which every monotone function can be
interpolated by a polynomial on any  set  of  small
enough cardinality.  

\end{abstract}

\maketitle

\setcounter{section}{-1}
\section{Introduction/Motivation}



In~\cite{mfl} the following was shown: 
\begin{Theorem}
\begin{itemize}
\itm a 
   Let $L$ be a lattice, $n$ a natural number,  $f:L^n \to L$ a
   monotone partial    function. 
 Then $L$ can be extended to a  lattice $L'$ such that for all 
$x_1, \ldots, x_n$ in $L$  we have
   $f( x_1, \ldots, x_n) = p(x_1, \ldots, x_n)$ 
   for some lattice polynomial $p$ with coefficients in~$L'$.
   Moreover, $p$ can be chosen to be of degree~1 in each 
   variable. 
\itm b Let $L$ be a lattice, $ \kappa $ a cardinal.   Then $L$ can be
   embedded into a lattice $\bar L$ which is ``$ \kappa
   $-order-polynomially complete'', i.e: 
   \begin{quote} For every natural number $n$, for every monotone
   partial function $f:\bar L^n \to \bar L$ with $|\dom(f) | \le \kappa $
   there is a polynomial $p $ with coefficients in $\bar L$, such that 
   $p(a_1,\ldots, a_n)=
	f(a_1, \ldots, a_n)$ for all $a \in \dom (f)$.
	(Again $p$ can be chosen to be of degree~$1$ in each variable.) 
   \end{quote}
\end{itemize}
\end{Theorem}



This theorem was motivated by the question of (non)existence of
order-polynomially complete lattices.  (See~\cite{Ka94} for a survey of      
some recent results in this area.) 
To show that no infinite
o.p.c.\ lattices exist it would be enough to show that on any
infinite lattice  there is
always a monotone function with a property that a polynomial cannot
have.   
The paper~\cite{mfl}
gave a (partial) negative answer to the question:  ``Is
there a property of polynomial functions that not all monotone
functions share?'' 

A distinguishing characteristic of the construction of an extension
lattice in~\cite{mfl} was that the bigger lattice $L'$ always had new
elements bounding all old elements.  However, \cite{KaSa93} showed that an
o.p.c.\ lattice is necessarily  bounded, so one could argue that only
constructions in the variety (or category) of \o0-lattices  (i.e., where
homomorphisms  by definition have to preserve 0 and 1) are relevant.
Since
the construction of~\cite{mfl} does not give a \o0-extension, the
question appeared whether the quoted theorem is still true for
\o0-lattices. 
   
The disadvantage of having to add  new bounds in the proof of part
   (a) becomes even more apparent in part (b):  Here we just iterate the
   construction  of part (a) a transfinite number of times, using a
   ``bookkeeping argument'' to eventually catch our own tail. 
   Since the construction in~\cite{mfl} adds new lower and upper
   bounds are added in each step (and since 
   there is no ``last'' step), the resulting lattice will not be
   bounded. 




We  show here that we can improve the construction from~\cite{mfl} 
to yield a
   \o0-extension for part (a), and to yield a \o0-lattice (hence in
   particular: a bounded lattice) in part (b). 
   We remark that it is
impossible to prove the same theorem for \o0-lattices if we only allow
polynomials of degree~1, and we show that we can choose our
interpolating   polynomials to be of degree~2. 



\bigskip

\begin{Notation}
\begin{enumerate}
\item
A {\em bounded lattice} is an algebra $(L, \vee, \wedge) $
of type (2,2) which (a) is a lattice 
and (b) happens to have a least and a greatest element. 
\item
A $\{0,1\}$-lattice is an algebra $(L, \vee, \wedge, 0,1)$ of
type (2,2,0,0) such that $(L, \vee, \wedge)$ is a bounded lattice, and
$0$ and $1$ are the least and the greatest element.  
\item When it is convenient we may also write a lattice (or a
\o0-lattice) as  $(L,\le)$, where $\le$ is the usual partial order on
$L$.  
\item
If $L$ is a \o0-lattice (or  a bounded lattice), $S \subseteq L$ a
sublattice, then we say that $S $ is a \o0-sublattice of $L$
 (or that $L$ is a \o0-extension of  $S$) iff $S$ contains
the greatest and the least element of~$L$.     
\item Operations are evaluated from lef to right.  E.g., 
$ \x \vee a\wedge b \vee c$ means 
$ [(\x \vee a)\wedge b] \vee c$.
\item
The ``degree'' of a polynomial  $p(\x_1,\ldots, \x_n) $ in the
variable $\x_k$  is the number of occurrences
of the variable $\x_k$ in~$p$.    (The degree of a polynomial function
$f$ is the smallest degree of a polynomial that induces~$f$.)
\end{enumerate}
\end{Notation}



\begin{Observation}
\begin{enumerate} 
\item If $(L,\vee,\wedge, 0,1)$  is a \o0-lattice with at least three
elements, then there is a monotone function $f:L\to L$ whose range
includes $\{0,1\}$, $f $ not equal to the identity function. 
\item If $f: L \to L $ is a polynomial function of degree~1, and $f$
is not the identity, then the range of $f$ cannot include $\{0,1\}$. 
\end{enumerate}
\end{Observation}
\begin{proof} (1) is clear, and for (2) notice that there must be a
  polynomial $p$ representing $f$ which is of the form $p(\x) = q(\x)
  \vee a$, $a > 0$,  or $p(\x)  = q(\x) \wedge b$, $b<1$. 
\end{proof}



\begin{Theorem}
Let $(L, \vee,\wedge, 0,1)$ be a \o0-lattice, $n$ a natural number, 
$f:L^n \to L$ a partial
monotone function.   Then there is a \o0-lattice 
$(L',   \vee,\wedge, 0,1)$ such that $L$ is a \o0-sublattice of $L'$
and a polynomial $p$ with coefficients in $L'$ (of degree~2 in each variable)
such that $p(x_1, \ldots, x_n)=f(x_1, \ldots, x_n)$ for all 
$x_1, \ldots, x_n \in L$. 
\end{Theorem}

\begin{Remark}

We may assume that $L$ is complete, as every \o0-lattice is a
\o0-sublattice of a complete \o0-lattice. 

Hence we may also assume that the monotone function $f$ is total. 

Moreover, as in~\cite{mfl} it is enough to prove the theorem for the
case $n=1$. 

\end{Remark}

\begin{Corollary}
For every \o0-lattice $ L$ and every cardinal $ \kappa $ there   is a
\o0-extension $\bar L$ of $L$ such that 
every monotone partial function from~$\bar L^n $ to~$\bar L$ whose
domain is at most of cardinality $ 
\kappa $ is the restriction of a polynomial. 
\end{Corollary}
\begin{proof} Iterate over all possible monotone  partial functions with small
domain, as in~\cite{mfl}. 
\end{proof}



\section{Preliminaries}

\begin{More Notation}

If $L$ is a \o0-lattice, $A$ and $B$ are nonempty  subsets of $L$,
then we say that $A$, $B$ are complementary 
% {\tt Is there a better or more customary name for this concept?
% ``orthogonal'' looks as if we care only about $a \wedge b$, not $a
% \vee b$\dots }
iff for all $a \in A\setminus \{0,1\}$,
 for all $b \in B\setminus\{0,1\}$ we have $a\vee b=1$, $a\wedge
b=0 $. 

Let $L$ be a \o0-lattice.  We write $[a,b]$ for the set $\{x\in L: a
   \le x \le b\}$.  We say that $S \subseteq L $ is a proper interval
   iff there are $0 < a < b < 1$ in $L$ such that  $S =[a,b]$.  

The letter $\iota$,  possibly with subscripts, always denotes 
a (partial) lattice isomorphism.  We usually use a superscript and a
   subscript to indicate domain and range of this isomorphism,
   respectively.     If $\iota^{m}_n$ is an isomorphism from~$S_m$ to
   $S_n$, then $\iota^n_m$ will always  denote its inverse.    

For polynomials  we use the letters $p$, $q$, \dots \
However, a polynomial that interpolates an isomorphism $\iota^m_n$ is
   sometimes written $i^m_n $. 

We often do not distinguish between a polynomial and the induced
   polynomial function, but to emphasize a point we may distinguish
   between an argument $x$ of a polynomial function and a formal
   variable (or ``indeterminate'') $\x$ by using different fonts. 

The set of unary  polynomials with coefficients in $L$ is    written
   as $L[\x]$. 

\end{More Notation}

\begin{Definition and Fact}  \label{pidef}
If $S = [a,b] \subseteq L$, we let $\pi^L_S: [0,b] \to S$ be the
 function that maps $x$  to~$x \vee a$.   Clearly $\pi^L_S(x)\in S$,
 $\pi^L_S(x) = \inf \{ s\in S: s \ge x\}$, and $\pi^L_S $ is
 idempotent, so we are justified in calling
 $\pi^L_S$ the ``projection'' from~$L$ to~$S$.  
\end{Definition and Fact}




\begin{Abuse of Notation}

If $L$ is a \o0-lattice, then 
% (in a slight abuse of terminology)
 we call a subset $A \subseteq L$ ``downward closed'' iff $(A\cup \{0\})
 \setminus \{1\}$ 
is downward closed in the traditional sense, or equivalently, if 
$A \setminus \{0,1\}$ is downward closed in $L \setminus \{0,1\}$.

Similarly we will ignore $0$ and $1$ 
when we speak of  an ``upward closed'' subset. 
\end{Abuse of Notation}






\section{A special case}

% \begin{Definition}
% Let $L$ be a bounded lattice, $S$ a sublattice.   We write $S \le_c L$ 
% iff for all $x \in L$ the set $\{s \in S: x \le s\}$ 
% is either empty or has a minimal (hence: least) element.  
% We let 
% $$ \pi^L_S(x):= \inf \{s \in S: x \le s\}$$
% (if it exists). 
% \end{Definition}
% 
% \begin{Remark}\label{trans}
% \begin{enumerate}
% \item If $S$ is a downward closed bounded sublattice of $L$, then 
% $S \le_c L$ is trivially true.
% \item $\le_c$ is transitive. 
% \end{enumerate}
% \end{Remark}

Our first observation proves the theorem in a special case which is 
trivial but important: 

\begin{Observation}\label{obs}
Let $L$ be a lattice, $T_1 = [a_1, b_1]$ and $T_5= [a_5, b_5]$
two proper intervals. % with $T_1 \le_c L$, $T_5 \le_c L$. 
Assume that $\iota^1_5:T_1 \to T_5$ is an isomorphism, and that $T_1$
and $T_5$ are complementary.

Then there is a \o0-extension $\bar L$ of $L$ such that the
isomorphism $\iota^1_5$ is induced by a polynomial (of degree~1) over
$\bar L$. Moreover, 
% we will still have $T_1\le_c \bar L$, $T_5\le_c \bar L$, and 
$T_1$ and $T_5$ will still be proper intervals in $\bar L$.
\end{Observation}



\begin{proof}
Let $T_2$, $T_3$, $T_4$ be isomorphic copies of $T_1$, pairwise
disjoint, and also disjoint from~$L$.   The following
diagram indicates how to make $L \cup T_2
\cup T_3\cup T_4$ a lattice such that 
$\iota^1_5(x) = x \vee \inf T_2 \wedge \sup T_3 \vee \inf T_4 \wedge \sup
T_5$.   (Recall that we evaluate operations from left to right.) 
\smallskip

$$
\begin{array}{ccccccccc}
     &      &  T_2 &       &        &       &  T_4 &             \\
     &\llap{$^{\iota^1_2}\!\!$}
     \nearrow&    & \nwarrow\rlap{$\!\!^{\iota^3_2}$}&    &
						\llap{$^{\iota^3_4}\!\!$}
						     \nearrow&      & 
							 \nwarrow
						 \rlap{$\!\!^{\iota^5_4}$}\\
 T_1 &      &      &       &   T_3 &        &        &       & T_5\\
\end{array}
$$


\smallskip

Formally, let $\iota^j_{j+1}: T_j \to T_{j+1}$ 
be an isomorphism from~$T_j$ to
$T_{j+1}$ for $j=1,2,3,4$ such that $\iota^1_5 = 
\iota_5^4\circ \iota_4^3\circ \iota_3^2\circ \iota_2^1$.
Let $\iota^{j+1}_j = (\iota^j_{j+1})^{-1}$. 
Define $\le$ on $\bar L$ as follows: 
$x \le y$ iff at least one of the following holds: 
\begin{enumerate}
\item $x =0$ or $y=1$
\item  $x,y\in L$, $x \le_L y$
\item $x,y\in T_j$, $x \le_{T_j} y$ for some $j$
\item $x\in T_j$, $y\in T_{j+1}$,
 $\iota_j(x) \le_{T_{j+1}} y$ for $j=1$ or $j=3$
\item $x\in T_{j+1}$, $y \in T_j$,  $\iota^{j+1}_j(x) \le_{T_j} y$ for
   $j=2$ or $j=4$
   % (here we write $\iota^{j+1}_j$ for the inverse of
   %$\iota^j_{j+1}$). 
\item $x \in L$, $y \in T_2$, $x \le_L \iota^2_1(y)$ 
  [or equivalently,
	$\iota^1_2(\pi^L_{T_1}(x)) \le_{T_2} y$]
\item Similarly for $x\in L$, $y\in T_4$. 
\end{enumerate}
Then it is easy to see that $\bar L$ will be a lattice extending the
lattice $L$ and also extending each $T_j$, 
with lattice operations satisfying furthermore the  following rules: 
\begin{enumerate}
\item[-] If $x\in T_j$, $y\in T_{j+1}$, then $x \vee y$ is either
   $\iota^j_{j+1} (x) \vee_{T_{j+1}}
	y$ or $x \vee_{T_j} \iota^{j+1}_j(y)$, depending on whether $j $ is
   odd or even.  
\item [-] Similarly, if $x\in T_j$, $y\in T_{j+1}$, then $x \wedge y$ is
	either $\iota^j_{j+1} (x) \wedge _{T_{j+1}}
	y$ or $x \wedge_{T_j} \iota^{j+1}_j(y)$, depending on whether $j $ is
	even or odd. 
\item[-] If $x\in T_j$, $y\in T_{j+2}$, then $x\vee y =
	\iota^j_{j+1}(x)\vee_{T_{j+1}}
	\iota^{j+2}_{j+1}(y)$  if $j$ is odd, and $x \vee y = 1$ if $j$
   is even.  
\item [-] If $x\in T_j$, $y\in T_{j+2}$, then $x\wedge y =
       \iota^j_{j+1}(x)\wedge_{T_{j+1}}
	\iota^{j+2}_{j+1}(y)$  if $j$ is even, and $x \wedge y = 0$ if $j$
	is odd. 
\item[-] If $x\in T_j$, $y \in T_{j+3}$, then $x \vee y = 1$, $x
	\wedge y=0$. 
\item[-] If $x \in L$, $y \in T_2$, then 
	$x \wedge y = x \wedge \iota^2_1(y)$, and 
	$x \vee y= \iota^1_2(\pi^L_{T_1}(x)) \vee_{T_1} y$ if 
			     $\pi^L_{T_1}(x) $ is defined, 
			     $x \vee y = 1$ otherwise.
\item[-] Similarly for $x\in L$, $y \in T_4$.
\item[-] If $x \in L$, $y \in T_3$, then $x \wedge y = 0$.   
For $x > 0$ 
at most one of $\pi^L_{T_1}(x)$, $\pi^L_{T_5}(x)$ (see~\ref{pidef}),
 since $T_1$ and
$T_5$ are complementary.  If neither exists, then $x \vee y = 1$, otherwise 
$x \vee y = \iota^1_2(\pi^L_{T_1}(x)) \vee_{T_2} \iota^3_2(y)$
or 
$x \vee y = \iota^5_4(\pi^L_{T_5}(x)) \vee_{T_4} \iota^3_4(y)$, 
respectively.
%\item[-] If $x\in T_4$,  $y \in L\setminus T_5$, then $x\vee y = 1$,
%        $x \wedge y = \iota^4_5(x) \wedge_L y$ (and similarly for $x\in T_2$,
%        $y\in L\setminus T_1)$). 
\end{enumerate}

It is now clear that (letting $a_j=\inf T_j$, $b_j=\sup T_j$) we have
$\iota^1_5(x)= x \vee a_2 \wedge b_3 \vee a_4 \wedge b_5$. 


\end{proof}
% 
% \bigskip
% {\small The assumptions in the previous lemma can be
% weakened.   It is sufficient for $T_1$, $T_5$ to be either intervals
% or downward closed, and essentially the same proof works. But since
% the lemma is only a special case of the main theorem, no attempt has
% been made to find the strongest possible version. }
% 
% \bigskip
% 
% 
% To reduce the general case to this special case, we have to accomplish
% three tasks: 
% \begin{itemize}
% \item  First, ``translate'' the domain $S$  of our 
% function $f$ to a downward closed interval $S_1$.   (i.e., find a
% lattice containing $S$ and an isomorphic copy $S_1$ of $S$, in which
% $S_1$ is a downward closed interval, and the isomorphism $\iota_1: S \to
% S_1$ is realized by a polynomial.)
% \item  Second, find a \o0-extension lattice
% with sublattices $S_3$ and $S_4$ isomorphic to~$S$ (via isomorphisms
% $\iota_3$ and $\iota_4$) such that the  map $f^* = \iota_4\circ  f \circ \iota_3^{-1}
% $ is realized by a polynomial.  This can be done using the method from
% \cite{mfl}.    We will ensure that $S_3$ is orthogonal to 
% $S_1$, so by \ref{obs}
% the isomorphism $\iota^1_3:= \iota_3 \circ \iota_1^{-1} $ can be realized by a
% polynomial. 
% \item  Finally, translate the result back from~$S_4$ to~$S$, i.e.,
% find (in some \o0-extension) a polynomial that realizes $\iota_4^{-1}$.
% This will be similar to the first step, but technically slightly more
% involved.  In particular, whereas all other steps can be carried out
% using only polynomials of degree~1, we have to use a polynomial of
% degree~2 here. 
% \end{itemize}
% Then the map $f =                          
% \iota_4^{-1}
% \circ
% f^*
% \circ
% \iota_{12}
%  \circ   \iota_1$ will be a polynomial.


\section{Two known  constructions}

 The following fact is easy: 

\begin{Fact}\label{fact}
  Let $(L_1, \le_1)$ and $(L_2, \le_2)$ be two
  \o0-lattices with $L_1 \cap L_2 = \{0,1\}$.  Then the ``horizontal
  sum'' of $L_1$ and $L_2$, i.e.,  
$$L:= ( L_1 \cup L_2, {\le _ 1} \cup {\le_2}),$$
is a \o0-lattice and $L_1$, $L_2$ are  \o0-sublattices of
$L$ which are complementary. 
\end{Fact}





\begin{Lemma}
\begin{enumerate}
\item Let $L$ be a complete lattice, $f:L \to L$ a monotone partial function.
  Then there is a bounded lattice $L' \supseteq L$ and a polynomial
  $p\in L'[\x]$  (of degree~1)
 such that $p(a)=f(a)$ for all $a \in
  L$.  Moreover, $L'$ can be chosen such that $L$ is downward (or,
  dually: upward) closed in~$L'$. 
\item 
 Let $S_3$, $S_4$ be complete lattices, disjoint, and let $f: S_3 \to
 S_4$ be monotone.   There there exists a \o0-lattice $L'$ containing
 $S_3$ and $S_4$ as proper intervals, % $S_3, S_4 \le_c L'$, 
 and a polynomial
   $r\in L'[\x]$ with coeffients in $L'$  such that  
   $f(x) = r(x)$ for all $x\in S_3$. $r$ can be chosen to be of degree
   1 (moreover:  even of the form $\x \vee a \wedge b$ for appropriate
   constants $a$ and $b$). 
\end{enumerate}
\end{Lemma}

\begin{proof}
Part (1): 
The existence of the extension $L'$   was shown in~\cite{mfl}.  
The construction in~\cite{mfl} yields a lattice $L'$ such that the
original lattice is upward closed in~$L'$. 

To prove part (2), let $L = S_3  \cup S_4 \mathbin{\dot\cup} 
\{\top,\bot\}$, as in~\ref{fact}, 
with $\top = \sup L$, $\bot=\inf L$,
$S_3$ and $S_4$ complementary in~$L$. 
$L$ is easily seen to be a complete
lattice, and $S_3$ and $S_4$ are downward closed in~$L$.  Now apply
part (1) to get an appropriate extension~$L'$.  
% From~\ref{trans} we conclude $S_3, S_4\le_c L'$.

(The ``moreover'' claim follows from the construction in~\cite{mfl}. 
As we will not need it, we leave this part of the proof to the reader.)
\end{proof}





\section{Extracting a closed set}

% The following definition will get us halfway towards 
%  accomplishing the first task in the above program.   


\begin{Definition}\label{star}
Let $L$ be a \o0-lattice, $S \subseteq L$ a downward closed
sublattice. 
\begin{itemize}
\itm a 
  We let $S^*$
   be an isomorphic copy of $(S \cup \{0\})\setminus \{1\}$ 
   (disjoint from~$L$).  
\itm b 
  We let $\iota= \iota^S_{S^*}$ be a bijection between  $S \cup
  \{0,1\}$ and $S^* \cup \{1\}$, with $\iota(1)=1$.     $\iota$ induces on
  $S^* \cup \{1\}$ a lattice structure $(\le_{S^*}, \vee_{S^*},
  \wedge_{S^*})$. 
\itm c
  Since we may consider several disjoint copies of $S$ at the
  same time, we may distinguish them by additional superscripts:
  $S^{*1}$, $S^{*2}$, etc. 
\itm d 
  We let $L + S^*$ be the structure $(L \cup S^*, \le^+)$, where
  the binary relation $\le^+$ is defined as follows:   $a \le^+ b$ iff one of
  the following holds: 
\begin{enumerate}
	\item $a=0$ or $b=1$ 
	\item $a\le_L b$ and $\{a,b\} \cap \{0,1\}=\emptyset$
	\item $a \le _{S^*} b$ and $\{a,b\} \cap \{0,1\}=\emptyset$
	\item $\iota(a) \le_{S^*} b$ and $\{a,b\} \cap \{0,1\}=\emptyset$
\end{enumerate}
(Note that these 4 cases are mutually exclusive.)
\end{itemize}
\end{Definition}

\begin{figure}
\label{fig}
% % \input{main.eepic}
\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(2945,2814)(0,-10)
\put(908,1400){\makebox(0,0)[lb]{\smash{$S$}}}
\put(2300,1700){\makebox(0,0)[lb]{\smash{$S^*$}}}
\put(65.955,56.318){\arc{1685.208}{5.0982}{6.2468}}
\put(1750.045,56.318){\arc{1685.208}{3.1780}{4.3266}}
\put(65.955,2817.682){\arc{1685.208}{0.0364}{1.1850}}
\put(1750.045,2817.682){\arc{1685.208}{1.9566}{3.1052}}
\put(1565.955,506.318){\arc{1685.208}{5.0982}{6.2468}}
\put(3250.045,506.318){\arc{1685.208}{3.1780}{4.3266}}
\put(908,1400){\ellipse{1800}{2774}}
\path(383,2037)(1433,2037)(1433,837)
	(383,837)(383,2037)
\path(1883,1287)(2933,1287)(2933,2262)
	(1883,2262)(1883,1287)
\drawline(1883,2262)(1883,2262)
\dottedline{45}(1883,2262)(908,2787)(2933,2262)
\dottedline{45}(908,12)(2408,462)
\dottedline{45}(1433,837)(2933,1287)
\dottedline{45}(383,837)(1883,1287)
\dottedline{45}(383,2037)(1883,2262)
\dottedline{45}(1433,2037)(2933,2262)
\end{picture}
}


\begin{center} Figure $\mathsf{>}$ \end{center}
\end{figure}

Figure $\mathsf{>}$ illustrates this definition.   The ellipse represents $L$,
the rectangle inside the ellipse is $S \setminus \{0,1\}$.  The
rectangle outside the ellipse is $S^* \setminus \{\inf S^*\}$.   Dotted lines
indicate the order relation. 


\begin{Main Lemma}\label{onestep}
Let $L$ be a \o0-lattice, $S \subseteq L$ a downward closed
sublattice.   Then:
\begin{itemize}
\itm a  $L + S^*$, as defined above, is a \o0-lattice.  We will write
the operations as $\vee^+$ and $\wedge^+$ or more explicitly 
as  $\vee^{L+S^*}$ and $\wedge^{L+S^*}$.
\itm b  $L$ is a \o0-sublattice of $L+S^*$. 
\itm c  $S$ is downward closed in $L+S^*$.
\itm d  $S^*\cup \{1\}$ is an upward closed sublattice of $L+S^*$
\itm e $\le_{S^*}$, $\vee_{S^*}$, $\wedge_{S^*}$ are the 
	restrictions of $\le^+$, $\vee^+$ and $\wedge^+$ 
	to~$S^* \cup \{1\}$. 
\itm f For $x\in S \cup \{0,1\}$, $\iota(x) = x \vee^+  \inf(S^*) $.
	$\iota$ is 
	a lattice isomorphism between $S \cup \{0,1\}$ and $S^*\cup
	\{1\}$. 
\itm g  Whenever $A \subseteq L \setminus S$ is upward closed in $L$,
	then $A$ is upward closed in $L+S^*$. 
\itm h  If $S \setminus \{1\}$ has a greatest element $s$, then 
	for all $x\in S^*$: $\iota^{-1}(x) = x \wedge^+ s$. 
\end{itemize}
\end{Main Lemma}



\begin{proof}
The  (easy) proof that $\le^+$ is indeed  a partial order is left to
the reader.  It is also easy to see that $0$ and $1$ will be the the
least and the greatest element of $L+S^*$.  

We will have proved most of the theorem once we have checked that the
following       table correctly computes $\inf_{\le^+}\{a,b\}$ and
$\sup_{\le^+}\{a,b\}$, depending on where $a$ and $b$ are.   Here,
$\vee_L$ and $\wedge_L$ are the lattice operations of $L$, and 
$\vee_{S^*}$ and $\wedge_{S^*}$ are the lattice operations of $S'$
(induced by the isomorphism $\iota$).     In this table we assume that 
$\{a, b\} \cap \{0,1\}=\emptyset$


$$
\begin{array}{lcc|c|c}
\vrule width 0pt depth 5pt
	 &      & &  \inf_{\le^+}\{a,b\} & \sup_{\le^+}\{a,b\} \\
\hline
\vrule width 0pt height 12pt
\mbox{(A)}      &
a\in L,  & b \in L &  a \wedge_L b        & a \vee_L b           \\ 
\mbox{(B)}      &       
a \in S, & b \in S^*& a \wedge_L \iota^{-1}(b)   & \iota(a) \vee_{S^*} b \\
\mbox{(C)}      &       
a \in L\setminus S,
	& b \in S^* & a \wedge_L \iota^{-1}(b)   &  1              \\
\mbox{(D)}      &
a \in S^*,& b \in S^* & a \wedge_{S^*} b        & a \vee_{S^*} b           \\ 
\end{array}
$$
\medskip



The proof is boring but straightforward. We first deal with greatest
lower bounds, i.e., the $\inf$ column. Fix $a,b$ both different
from~$0$ and $1$, and assume $y \le^+ a, b$.    We have to show  
``$ y \le^ +   a \wedge_L b        $'', 
``$ y \le^ +  a \wedge_L \iota^{-1}(b) $'', 
or ``$ y \le^ +  a \wedge_{S^*} b  $'',  respectively. 

This is trivial if $y=0$, so we may assume $y\not=0$ whenever that is
convenient.  We distinguish 4 cases: 

\begin{description}
  \itm A $a,b\in L$. So $y\in L$, $y \le_L a,b$, $y \le_L a\wedge_L b$,
  $y \le^ + a\wedge_L b$.
  \itm B,C $a\in L$, $b\in S^ *$.   Again $y \in L$ and $y\le_L a$.
  Also $\iota(y ) \le_{S^ *} b$, so
  $y \le_L \iota^ {-1} (b)$,
  $y \le_L a \wedge_ L  \iota^ {-1} (b)$,
  $y \le^ + a \wedge_ L  \iota^ {-1} (b)$. 
  \itm D1 $ a  , b \in S^ *$, $y \in S^ *$. 
  So $y\le_{S^ *} a,b $, 
   $y\le_{S^ *} a\wedge _{S^ *} b $, 
   $y\le^ + a\wedge _{S^ *} b $.
   \itm D2  
   $ a  , b \in S^ *$, $y \in L$. 
  So $\iota(y)\le_{S^ *} a,b $, 
   $\iota(y)\le_{S^ *} a\wedge _{S^ *} b $, 
   $y\le^ + a\wedge _{S^ *} b $.
 \end{description}
 
We now turn to the ``$\sup$'' column.   
Again fix $a,b$ both different from~$1$, 
and assume $z \ge^ + a,b$. If $z=1$ then we are again
immediately done, so assume  $z \not=1$.  We distinguish 5 cases:

\begin{description}
  \itm A1 $a,b\in L$,  $z\in L$.  So $z \ge_L a,b$, $z \ge_L a\vee_L b$,
  $z \ge^ + a\vee_L b$.
  \itm A2 $a,b\in L$,  $z\in S^ *$.  So $z \ge_S^ * \iota(a),\iota(b)$,
 $z \ge_{S^ *} \iota(a) \vee_{S^ *} \iota(b) = \iota(a \vee_L b) $, 
  $z \ge^ + a\vee_L b$.
  \itm B $a\in S$, $b\in S^ *$.   So $z \in S^ *$, $z \ge_{S^ *}b $,
  $z \ge_{S^ *} \iota(a)$,
  $z \ge^ + \iota(a) \vee_ {S^ *} b $.

  \itm C $a\in L \setminus S$, $b\in S^ *$.
  $z \ge^ + a$ implies $z \in L$ since $S$ is downward closed in $L$,
  but $z \ge^+b$ implies $z \in S^ *\cup \{1\}$, so $z=1$. 
  \itm D $ a  , b \in S^ *$.  So $z \in S^ *$. 
  $z\ge_{S^ *} a,b $, 
   $z\ge_{S^ *} a\vee _{S^ *} b $, 
   $z\ge^ + a\vee _{S^ *} b $.
 \end{description}


Thus we have shown that the table above is correct.  This proves in
	particular part (a) of our theorem. 

Part (b) follows from line (A) in our table. 

Part (c) follows immediately from the definition of $\le^+$.

Part (d):  The definition of $\le^+$ implies that $S^* \cup \{1\}$ is
upward closed, and line (D) of our table shows that $S^* \cup \{1\}$
is a sublattice. 

Part (e) follows from the definition and from line (D). 

Part (f): $\iota (x) = x \vee^+ \inf( S^*) $ follows from line (B), and
$\iota$ is a lattice isomorphism by the definition of $\le_{S^*}$. 

Part (g) follows from the definition of $\le^+$.

Part (h):  If $s = \sup(S\setminus \{1\})$, then for all
$ x \in S^*$ we have $\iota^{-1}(x) \in S\setminus \{1\}$, so 
$\iota^{-1}(x) = s \wedge_L \iota^{-1}(x)= s \wedge^+ \iota^{-1}(x)$. 

This concludes the proof of~\ref{onestep}.
\end{proof}




\begin{Conclusion}[The $\Y$-shaped extension]
\label{yyy}
 Let  $L$ be a \o0-lattice, $S$ a downward closed
sublattice.  Then there exists a \o0-extension $L^\Y$ of $L$
containing two isomorphic copies $S^{*1}$, $S^{*2}$ of
$S\cup\{0\}\setminus \{1\}$  such that
for $\ell=1,2$: 
\begin{enumerate}
\item  $S^{*\ell}$ is upward closed, and has a least  element
	 $a_\ell= \inf S^{*\ell}$. 
\item The map $\iota_\ell: S \cup \{0,1\} \to S^{*\ell} \cup \{1\}$,
defined by $\iota_\ell(x) = x \vee a_\ell $ is an isomorphism.
\item $x = \iota_1(x) \wedge \iota_2(x) $ for all $x\in S$.
\end{enumerate}
(See figure~$\Y$.)
\end{Conclusion}
\begin{figure}

% % \input{y.eepic}
\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(4074,2814)(0,-10)
%\put(908,1400){\makebox(0,0)[lb]{\smash{$1$}}}
%\put(2300,1700){\makebox(0,0)[lb]{\smash{$2$}}}
\put(2008,1400){\makebox(0,0)[lb]{\smash{$S$}}}
\put(3500,1700){\makebox(0,0)[lb]{\smash{$S^{*1}$}}}
\put(500,1700){\makebox(0,0)[lb]{\smash{$S^{*2}$}}}
\put(3500,300){\makebox(0,0)[lb]{\smash{$a_1$}}}
\put(500,300){\makebox(0,0)[lb]{\smash{$a_2$}}}


\put(1194.955,56.318){\arc{1685.208}{5.0982}{6.2468}}
\put(2879.045,56.318){\arc{1685.208}{3.1780}{4.3266}}
\put(1194.955,2817.682){\arc{1685.208}{0.0364}{1.1850}}
\put(2879.045,2817.682){\arc{1685.208}{1.9566}{3.1052}}
\put(2694.955,506.318){\arc{1685.208}{5.0982}{6.2468}}
\put(4379.045,506.318){\arc{1685.208}{3.1780}{4.3266}}
\put(1379.045,506.318){\arc{1685.208}{3.1780}{4.3266}}
\put(-305.045,506.318){\arc{1685.208}{5.0982}{6.2468}}
\put(2037,1400){\ellipse{1800}{2774}}
\path(1512,2037)(2562,2037)(2562,837)
	(1512,837)(1512,2037)
\drawline(3012,2262)(3012,2262)
\dottedline{45}(3012,2262)(2037,2787)(4062,2262)
\dottedline{45}(2037,12)(3537,462)
\dottedline{45}(2562,837)(4062,1287)
\dottedline{45}(1512,837)(3012,1287)
\dottedline{45}(1512,2037)(3012,2262)
\dottedline{45}(1512,837)(12,1287)
\dottedline{45}(2562,837)(1062,1287)
\dottedline{45}(2562,2037)(1062,2262)
\path(1062,1287)(12,1287)(12,2262)
	(1062,2262)(1062,1287)
\path(3012,1287)(4062,1287)(4062,2262)
	(3012,2262)(3012,1287)
\dottedline{45}(2037,12)(537,462)
\dottedline{45}(1062,2262)(2037,2787)(12,2262)
\dottedline{45}(1512,2037)(12,2262)
\dottedline{45}(2562,2037)(4062,2262)
\end{picture}
}


\begin{center} Figure $\Y$ \end{center}
\end{figure}



\begin{proof}   We use the construction from the main lemma twice:
First we extend $L$ to a lattice $L' = L+S^{*1}$, then we extend this
intermediate lattice again to~$L^\Y:= (L+S^{*1})+S^{*2}$.   This is
possible, as $S$ is still a downward closed sublattice of 
 $L+S^{*1}$ by~\ref{onestep}(c).

 $a_\ell = \inf S^{*\ell}$ exists by the main lemma. 
All that remains to prove is that 
$x = \iota_1(x) \wedge \iota_2(x) $ for all $x\in S$: 

So let $x\in S$ and let $y:= \iota_1(x) \wedge \iota_2(x) $.  Clearly
 $ y \ge x$, so in particular:  If $x=1$, then $y=1$.   



Now assume $x< 1$.   Since $\iota_1(x)\in S^{*1} \subseteq L'\setminus S$
and $\iota_2(x)\in S^{*2}$, we get 
$ \iota_1(x) \wedge \iota_2(x)  = \iota_1(x) \wedge
\iota_2^{-1}(\iota_2(x))$  by rule
\ref{onestep}(C),  
so $y = (x \vee a_1) \wedge x  = x$. 

\end{proof}





% 
% \begin{Conclusion} Let  $L$ be a \o0-lattice, $S$ a downward closed
% \o0-sublattice.  Then there exists a \o0-extension $L'$ of $L$
%  containing a downward closed proper interval $S_1$ isomorphic to
%  $S$ and a polynomial $p(x)$ over $L'$ (of degree~1) such that
%  $p$ induces a lattice isomorphism between $S$ and $S_1$. 
% 
% Moreover,  $S$ will still be downward closed in~$L'$. 
% \end{Conclusion}
% 


\begin{Conclusion}[The $\M$-shaped extension]
\label{mmm}
 Let  $L$ be a \o0-lattice, $S_0$ a downward closed
 \o0-sublattice.  Then there exist 
% (see figure 3)
%\begin{figure}
%$$
%\begin{array}{ccccccccc}
%  &                     & S^ {*2} &         &    &         & S^{*1}\\
%  & \llap{$p_2$}\nearrow&         & \nwarrow&    & \nearrow&         &
%                                       \nwarrow\rlap{$p_1$}\\  
%S_2&            & & & S & & & & S_1\\
%\end{array}
%$$
%\begin{center} 
%\rm Figure 3
%\end{center}
%\end{figure}
\begin{itemize}
\item [-]  a \o0-extension $L^ \M$ of $L$
\item [-] two sublattices $S_1 \subseteq L^\M$, $S_2 \subseteq L^ \M$ which
	are both downward closed proper intervals, and are isomorphic
	to~$S_0$---say, via isomorphisms $\iota^0_1:S_0 \to S_1$, $\iota^0_2:S_0 \to
	S_2$
\item[-] polynomials $i^0_1(x)$ and $i^0_2(x)$ of degree~1 whose
   restrictions to the set $S_0$ are the functions $\iota^0_1$, $\iota^0_2$,
   respectively 
\item[-] polynomials $p_1(x)$, $p_2(x)$ of degree~1 in $L^\M[\x]$
 satisfying 
  $$ (*) \qquad \qquad \qquad 
	a = p_1(\iota^0_1(a)) \wedge p_2(\iota^0_2(a))$$
for all $a \in S_0$. 
\end{itemize}
Again   $S_0$ will still be downward closed in $L^ \M$. 

Note that this  includes the case $S_0=L$. 
\end{Conclusion}




\begin{proof}
We will use the extension $L^\Y = L \cup S^{*1} \cup S^{*2}$ from~\ref{yyy}, and apply the dual of the  main lemma twice.  

First we note that $S^{*1}$ is upward closed in $L^\Y$, so we can
define an extension 
$$L':= L^\Y + (S^{*1})_*.$$
  Let $S_1 = (S^{*1})_*$.  (See figure $\mathsf{N}$.)

\begin{figure}

% % \input{n.eepic}
\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(5349,2956)(0,-10)
\put(2008,1400){\makebox(0,0)[lb]{\smash{$S$}}}

\put(500,1700){\makebox(0,0)[lb]{\smash{$S^{*2}$}}}
\put(500,350){\makebox(0,0)[lb]{\smash{$a_2$}}}

\put(3500,1700){\makebox(0,0)[lb]{\smash{$S^{*1}$}}}
\put(3500,350){\makebox(0,0)[lb]{\smash{$a_1$}}}
\put(4650,1500){\makebox(0,0)[lb]{\smash{$S_{1}$}}}
\put(4800,100){\makebox(0,0)[lb]{\smash{$b_1$}}}
\put(4800,2800){\makebox(0,0)[lb]{\smash{$c_1$}}}

\put(1194.955,127.318){\arc{1685.208}{5.0982}{6.2468}}
\put(2879.045,127.318){\arc{1685.208}{3.1780}{4.3266}}
\put(1194.955,2888.682){\arc{1685.208}{0.0364}{1.1850}}
\put(2879.045,2888.682){\arc{1685.208}{1.9566}{3.1052}}
\put(2694.955,577.318){\arc{1685.208}{5.0982}{6.2468}}
\put(4379.045,577.318){\arc{1685.208}{3.1780}{4.3266}}
\put(3969.955,277.318){\arc{1685.208}{5.0982}{6.2468}}
\put(5654.045,277.318){\arc{1685.208}{3.1780}{4.3266}}
\put(3969.955,2738.682){\arc{1685.208}{0.0364}{1.1850}}
\put(5654.045,2738.682){\arc{1685.208}{1.9566}{3.1052}}
\dottedline{45}(2037,83)(4812,308)(3537,533)
\dottedline{45}(2562,908)(4062,1358)(5337,1058)
\dottedline{45}(1512,908)(3012,1358)(4287,1058)
\dottedline{45}(1512,2108)(3012,2333)(4287,1958)
\dottedline{45}(2562,2108)(4062,2333)(5337,1958)
\put(1379.045,577.318){\arc{1685.208}{3.1780}{4.3266}}
\put(-305.045,577.318){\arc{1685.208}{5.0982}{6.2468}}
\put(2037,1471){\ellipse{1800}{2774}}
\put(2037,83){\blacken\ellipse{150}{150}}
\put(2037,83){\ellipse{150}{150}}
\put(2037,2858){\blacken\ellipse{150}{150}}
\put(2037,2858){\ellipse{150}{150}}
\path(1512,2108)(2562,2108)(2562,908)
	(1512,908)(1512,2108)
\path(4287,1058)(5337,1058)(5337,1958)
	(4287,1958)(4287,1058)
\path(3012,1358)(4062,1358)(4062,2333)
	(3012,2333)(3012,1358)
\dottedline{45}(4812,2708)(2037,2858)
\drawline(3012,2333)(3012,2333)
\dottedline{45}(3012,2333)(2037,2858)(4062,2333)
\path(1062,1358)(12,1358)(12,2333)
	(1062,2333)(1062,1358)
\dottedline{45}(1062,2333)(2037,2858)(12,2333)
\dottedline{45}(1512,908)(12,1358)
\dottedline{45}(2037,83)(537,533)
\dottedline{45}(1512,2108)(12,2333)
\drawline(2037,2858)(2037,2858)
\dottedline{45}(2562,2108)(1062,2333)
\dottedline{45}(2562,908)(1062,1358)
\end{picture}
}


\begin{center} Figure $\mathsf{N}$ \end{center}
\end{figure}






Let $a_1 = \inf S^{*1}$ (so $a_1>0$). So also  $S_1$ will have a least
element $b_1:= \inf S_1$.    By the (dualized version) of the  main
lemma~\ref{onestep},
 $S_1 \cup \{0\}$ is isomorphic to~$S^{*1} \cup \{0,1\}$, so 
$S_1$  will have a greatest element $c_1 = \sup S_1$.  Clearly
$S_1$ will be downward closed.   The map $x \mapsto  x\wedge c_1$ is
an isomorphism from~$S^{*1}\cup \{1\}$
to~$S_1$ with inverse $y \mapsto y \vee a_1$, by 
\ref{onestep}(f) and~\ref{onestep}(h). 

Now $S^{*2}$ is still upward closed in $L'$, so we can again apply the
dual of the main lemma and let 
$$L^\M = L' + (S^{*2})_*. $$ 
Let $S_2 =  (S^{*2})_*$,  $c_2:=\inf S_2$. 
Again the maps  $x \mapsto  x\wedge c_2$ and its inverse 
$y \mapsto y \vee a_2$ are isomorphisms between $S^{*2}\cup \{1\}$
and~$S_2$.
(See figure~$\M$.)

\begin{figure}

% % \input{m.eepic}
\setlength{\unitlength}{0.00059167in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(6624,2956)(0,-10)
\put(3207.2,1460){\makebox(0,0)[lb]{\smash{$S$}}}
\put(4750,1730){\makebox(0,0)[lb]{\smash{$S^{*1}$}}}
\put(1750,1730){\makebox(0,0)[lb]{\smash{$S^{*2}$}}}
\put(4750,315){\makebox(0,0)[lb]{\smash{$a_1$}}}
\put(1750,315){\makebox(0,0)[lb]{\smash{$a_2$}}}

\put(320,1550){\makebox(0,0)[lb]{\smash{$S_{2}$}}}
\put(420,90){\makebox(0,0)[lb]{\smash{$b_2$}}}
\put(520,2790){\makebox(0,0)[lb]{\smash{$c_2$}}}

\put(5920,1550){\makebox(0,0)[lb]{\smash{$S_{1}$}}}
\put(5920,90){\makebox(0,0)[lb]{\smash{$b_1$}}}
\put(5920,2790){\makebox(0,0)[lb]{\smash{$c_1$}}}


\put(2469.955,127.318){\arc{1685.208}{5.0982}{6.2468}}
\put(4154.045,127.318){\arc{1685.208}{3.1780}{4.3266}}
\put(2469.955,2888.682){\arc{1685.208}{0.0364}{1.1850}}
\put(4154.045,2888.682){\arc{1685.208}{1.9566}{3.1052}}
\put(3969.955,577.318){\arc{1685.208}{5.0982}{6.2468}}
\put(5654.045,577.318){\arc{1685.208}{3.1780}{4.3266}}
\put(5244.955,277.318){\arc{1685.208}{5.0982}{6.2468}}
\put(6929.045,277.318){\arc{1685.208}{3.1780}{4.3266}}
\put(5244.955,2738.682){\arc{1685.208}{0.0364}{1.1850}}
\put(6929.045,2738.682){\arc{1685.208}{1.9566}{3.1052}}
\dottedline{45}(3312,83)(6087,308)(4812,533)
\dottedline{45}(3837,908)(5337,1358)(6612,1058)
\dottedline{45}(2787,908)(4287,1358)(5562,1058)
\dottedline{45}(2787,2108)(4287,2333)(5562,1958)
\dottedline{45}(3837,2108)(5337,2333)(6612,1958)
\put(2654.045,577.318){\arc{1685.208}{3.1780}{4.3266}}
\put(969.955,577.318){\arc{1685.208}{5.0982}{6.2468}}
\put(1379.045,277.318){\arc{1685.208}{3.1780}{4.3266}}
\put(-305.045,277.318){\arc{1685.208}{5.0982}{6.2468}}
\put(1379.045,2738.682){\arc{1685.208}{1.9566}{3.1052}}
\put(-305.045,2738.682){\arc{1685.208}{0.0364}{1.1850}}
\dottedline{45}(3312,83)(537,308)(1812,533)
\dottedline{45}(2787,908)(1287,1358)(12,1058)
\dottedline{45}(3837,908)(2337,1358)(1062,1058)
\dottedline{45}(3837,2108)(2337,2333)(1062,1958)
\dottedline{45}(2787,2108)(1287,2333)(12,1958)
\put(3312,1471){\ellipse{1800}{2774}}
\put(3312,83){\blacken\ellipse{150}{150}}
\put(3312,83){\ellipse{150}{150}}
\put(3312,2858){\blacken\ellipse{150}{150}}
\put(3312,2858){\ellipse{150}{150}}
\path(2787,2108)(3837,2108)(3837,908)
	(2787,908)(2787,2108)
\path(5562,1058)(6612,1058)(6612,1958)
	(5562,1958)(5562,1058)
\path(4287,1358)(5337,1358)(5337,2333)
	(4287,2333)(4287,1358)
\dottedline{45}(6087,2708)(3312,2858)
\drawline(4287,2333)(4287,2333)
\dottedline{45}(4287,2333)(3312,2858)(5337,2333)
\path(1062,1058)(12,1058)(12,1958)
	(1062,1958)(1062,1058)
\path(2337,1358)(1287,1358)(1287,2333)
	(2337,2333)(2337,1358)
\dottedline{45}(537,2708)(3312,2858)
\dottedline{45}(2337,2333)(3312,2858)(1287,2333)
\end{picture}
}


\begin{center} Figure $\M$ \end{center}
\end{figure}





By~\ref{yyy}(3), we have for all $x\in S$: $x = ( x \vee a_1) \wedge
(x \vee a_2)$. 
Let $i^0_\ell(x) =  x \vee a_\ell \wedge c_\ell$ and  $p_\ell(x) = x \vee
 a_\ell$ for $\ell =1,2$.  Then $i^0_\ell(x ) = \iota^0_\ell(x)$ 

 and $x = p_1(\iota^0_1(x) ) \wedge p_2(\iota^0_2(x) )$
for all $x \in L$,
 as required. 

\end{proof}
\section{Proof of the theorem:}

Start with a complete lattice $L$ and a monotone function $f:L \to
L$. Let $S_0=L$ and construct $L^\M$ as in~\ref{mmm}: 
$L^\M = L \cup S^{*1} \cup S^{*2} \cup S_1 \cup S_2$.    Let
   $\iota^0_1$,    $\iota^0_2$,    $i^0_1$,    $i^0_2$ be as in~\ref{mmm}. 

Let $S_3$, $S_4$ be isomorphic copies of the lattice $L$ with
isomorphism $\iota^0_3: S_0 \to S_3$, $\iota^0_4: S_0 \to S_4$. 

 The function
$f^3_4: S_3 \to S_4$, defined by $f^3_4 = \iota^0_4 \circ f \circ
\iota^3_0$ is a monotone function from~$S_3$ to~$S_4$, so we can
find a 
\o0-lattice $\bar L$ containing  $S_3$ and  $S_4$ as 
proper intervals $ \le \bar L$ 
such that  for some $a,b\in \bar L$, for all $y\in
S_3$, $f^3_4(y)= r(y)$ for some polynomial $r(\x)\in \bar L[\x]$.  Hence:
$$ \forall x \in L: \ 
\iota^0_4(f(x)) = 
\iota^0_4(f(\iota^3_0(\, \iota^0_3(x)\, ))) = 
r(\iota^0_3(x))
$$
% so $\iota^0_4 \circ f$ is interpolated on $L$ by a polynomial of degree~1.    


We may assume that $\bar L \cap L^ \M = \{0,1\}$.  So we can find a
lattice $L' = L^ \M \cup \bar L$ as in~\ref{fact}.  Since $
S_1, S_2, S_3, S_4$ are all  proper intervals $\le L'$, 
and since $S_1$ and $S_2$ are both complementary from both $S_3$
and $S_4$, 
we can apply~\ref{obs} to extend the \o0-lattice $L'$ to a 
\o0-lattice $L''$ in which the isomorphisms 
\begin{itemize}
\item[] $\iota^1_3 : S_1 \to S_3$
\item[] $\iota^4_1 : S_4 \to S_1$
\item[] $\iota^4_2 : S_4 \to S_2$
\end{itemize}
are all realized by polynomials (of degree~1), which we call 
$i^1_3$, $i^4_1$, $i^4_2$, respectively. 

\begin{figure}
% % \input{allx.eepic}
\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(5611,2207)(0,-10)
\put(3870.500,2479.643){\arc{3440.104}{0.7678}{2.3738}}
\put(2757.805,2809.609){\arc{5602.804}{0.5755}{2.5339}}
\put(1470,1510){\ellipse{2924}{1350}}
\put(4545,1473){\ellipse{1724}{974}}
\path(3758,1585)(3833,1510)(2858,1510)(2783,1510)
\path(3833,1510)(3758,1435)
\path(383,1135)(383,1285)(533,1285)
\path(2558,1210)(2558,1360)(2708,1360)
\path(4283,1510)(4883,1510)(4808,1585)
\path(4883,1510)(4808,1435)
\path(383,1585)(628,1810)(533,1810)       % ne,  -/
\path(628,1810)(628,1735)
\path(2333,1585)(2108,1810)(2108,1735)    % nw |\
\path(2108,1810)(2183,1810)
\put(1283,1435){\makebox(0,0)[lb]{\smash{$S$}}}
\put(1808,1810){\makebox(0,0)[lb]{\smash{$S^{*1}$}}}
\put(708,1810){\makebox(0,0)[lb]{\smash{$S^{*2}$}}}
\put(233,1435){\makebox(0,0)[lb]{\smash{$S_2$}}}
\put(2408,1435){\makebox(0,0)[lb]{\smash{$S_1$}}}
\put(3908,1435){\makebox(0,0)[lb]{\smash{$S_3$}}}
\put(4958,1435){\makebox(0,0)[lb]{\smash{$S_4$}}}
\put(2633,2035){\makebox(0,0)[lb]{\smash{$L^{\M}$}}}
\put(5258,1885){\makebox(0,0)[lb]{\smash{$\bar L$}}}
\put(3158,1660){\makebox(0,0)[lb]{\smash{${i}^{1}_3$}}}
\put(2933,685){\makebox(0,0)[lb]{\smash{${i}^{4}_1$}}}
\put(1058,160){\makebox(0,0)[lb]{\smash{${i}^{4}_2$}}}
\put(4433,1585){\makebox(0,0)[lb]{\smash{$f^3_4$}}}
\put(608,1585){\makebox(0,0)[lb]{\smash{$p_2$}}}
\put(1983,1585){\makebox(0,0)[lb]{\smash{$p_1$}}}
\end{picture}
}

\begin{center} Figure \happy  \end{center}
\end{figure}




Now for all $x \in L$ we have by~\ref{mmm}$(*)$:
$$ f(x) = p_1(\iota^0_1(f(x))) \wedge p_2 (\iota^0_2(f(x)))$$
so it is enough to show that the function $x \mapsto \iota^0_\ell(f(x))$
can be interpolated by a polynomial on $S_0$ for $\ell=1,2$.    But by 
construction we have 
for $\ell=1,2$
$$\iota^0_\ell(f(x)) = 
\iota^4_\ell(\,\,  \iota^0_4 (f(x))\,\,) =
\iota^4_\ell(\,\,  r(\iota^0_3 (x))\,\,) =
 i^4_\ell \circ r \circ i^1_3 \circ i^0_1(x) $$
 hence $f$ is realized by a polynomial of degree~2.  (See figure \happy.)






\bibliographystyle{plain}
%\bibliography{goldstrn,others}

\bigskip\bigskip \def\nbibitem[#1]{\advance\bcount1 \bibitem[\number\bcount]}
  \newcount\bcount
\begin{thebibliography}{1}

\bibitem{mfl}
Martin Goldstern.
\newblock {Interpolation of Monotone Functions in Lattices}.
\newblock {\em Algebra Universalis}, 36:108--121, 1996.

\bibitem{Ka94}
Hans Kaiser.
\newblock Interpolation and order polynomially complete lattices.
\newblock In G.~Pilz, editor,
  {\em Contributions to General Algebra 9}, Wien, 1995.
  H{\"o}lder-Pichler-Tempsky.


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

\end{thebibliography}



\end{document}

