% 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)= \$. 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)) = \ $$ for all $a_1$, \dots, $a_n\in L$. \sof \proof Let $a=\inf L$, $b=\sup L$. Let $e_1:= \$, \dots, $e_n:= \$. 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}