% \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}