% \author{Martin Goldstern}
% \title{Interpolation in ortholattices}
\documentclass% [12pt]
{amsart}
\usepackage{eepic}
\newcommand{\dashlinestretch}{10}
\date{August 14, 2000}
\usepackage{a4wide}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathrsfs}
% \usepackage{epic}\usepackage{eepic}
\swapnumbers
\newcommand{\<}{\langle}
\renewcommand{\>}{\rangle}
\newcommand{\oo}{\text{\it ortho}}
%\renewcommand{\baselinestretch}{1.5}
%\textwidth150mm
%\textheight220mm
%\parindent5mm
%\advance\hoffset-2cm
\makeatletter
\newcommand{\KNUTHcases}[1]% the one and only!
{\left \{\,\vcenter {\normalbaselines \m@th
\ialign {$##\hfil $&\quad ##\hfil \crcr #1\crcr }}\right .%}
} % I don't like the ams \cases
\makeatother
\def\newthm#1 {\newtheorem{#1}[thm]{#1}}
\newtheorem{thm}{Theorem}[section]
\def\itm#1 {\item[{(#1)}]}
\theoremstyle{definition}
\newthm Notation
\newthm {Abuse of Notation}
\newthm {Definition and Fact}
\newthm Definition
\newthm Fact
\newthm {More Notation}
\newthm {Even More Notation}
\newthm Construction
\theoremstyle{plain}
\newthm Theorem
\newthm Conclusion
\newthm Lemma
\newthm {Main Lemma}
\newthm Corollary
\newthm Claim
\theoremstyle{remark}
\newthm Observation
\newthm Remark
\newthm Question
\newcommand{\pp}{\perp}
\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}}
\newcommand{\y}{{\tt y}}
\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}
\newcommand{\xx}{\trianglelefteq}
\newcommand{\dd}{{\it dual}}
\newcommand{\logand}{\wedge}
\newcommand{\F}{{\mathscr F}}
\begin{document}
\author{Martin Goldstern}
\thanks{This research was
supported by the Austrian Science Foundation (FWF), grant P13325-MAT}
\address{Technische Universit\"at Wien\\
Wiedner Hauptstra\3e 8--10/118.2
\\
A-1040 Wien
}
\email{Martin.Goldstern@tuwien.ac.at}
\urladdr{http://info.tuwien.ac.at/goldstern/}
\title{Interpolation in ortholattices}
\thanks{This paper is available from {\tt www.arXiv.org}, and also from
my home page}
% 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}
If $(L,\vee,\wedge,0,1, {^\pp})$ is a complete ortholattice, $f:L^n\to L$
{\em any} partial function, then there is
a complete
ortholattice $L^*$ containing $L$ as a subortholattice, and an
ortholattice 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$.
Iterating this construction long enough
yields a complete ortholattice in which every function can be
interpolated by a polynomial on any set of small
enough cardinality.
\end{abstract}
\maketitle
% \begin{center}
% \newcommand{\vr}{\vrule depth -3pt height 3.4pt width 0.5 \hsize}
% \newcommand{\vvr}{\vr\\[-9pt]\vr}
% \vvr\\ DRAFT --- WORK IN PROGRESS \\ \vvr
% \end{center}
\setcounter{section}{-1}
\section{Introduction}
In \cite{mfl} and \cite{l01} we showed the following: Let $L$ be any
[bounded] lattice, then there is a lattice $\bar L$ extending $L$
[with the same least and greatest element] such that every {\it
monotone} function from $L^n$ to $L$ is represented by a polynomial
with coefficients in $\bar L$.
It is clear that as long as we restrict ourselves to lattice polynomials we
can only interpolate monotone functions. Here we consider the
problem of interpolation on {\it ortholattices}, i.e., bounded
lattices equipped with an ``orthocomplement''. Since the
orthocomplement reverses order, there is no obvious monotonicity
property that all orthopolynomials in an ortholattice will share.
The main theorem of this paper shows
that indeed there are no restrictions on the
behavior of orthopolynomials; more precisely: If $L$ is an
ortholattice, then {\it any} function $f:L^n \to
L$ can be represented by a polynomial with coefficients in some
suitable orthoextension $\bar L$.
By iterating the construction from the theorem we get, for every
cardinal number $\kappa$, a lattice $\hat
L$ with the property that every function from $\hat L^n$ to $\hat L$
can be
interpolated on any set of size $\le \kappa$.
We also show that we can construct $\hat L$ such that $\hat L$ will
be complete (as a partial order). Moreover, assuming
that the original ortholattice $L$ is complete,
we construct $\hat L$ such that $L$ is a ``convex''
sublattice of $\hat L$.
\section{Basic definitions}
\begin{Notation}
Lattices are denoted by $L$, $L'$, $L_1$, etc.
When we consider several lattices, we use the self-explanatory
notation $ \logand_{L_1}$ or $\logand_1$, $\le_2$, etc. for the
operations/relation in
$L_1$, $L_2$, etc.
We agree that the symbol $\wedge$ binds more tightly than $\vee$,
i.e., $a\vee b \logand c = a \vee ( b \logand c)$.
% 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 any lattice $L$ we let $L^\dd$ be the dual lattice (with the same
underlying set): $x \le^{L^\dd} y $ iff $x \ge^L y$.
An ortholattice is a bounded lattice $(L,\vee,\wedge,0,1) $ with an
additional unary operation $x \mapsto x^\pp$ which satisfies
$x \le y \Rightarrow x^\pp \ge y^\pp$, $(x^\pp)^\pp = x$,
$x \vee x^\pp = 1$, $x \wedge x^\pp=0$ for all $x,y$
(and hence also the de Morgan
laws $(x \vee y)^\pp = x^\pp\wedge y^\pp$, etc.).
\end{Notation}
\begin{Abuse of Notation}
If $(L,\vee,\wedge, 0,1)$ is a bounded lattice, $A \subseteq L$, then
we say that $A$ is ``convex'' in $L$ iff
\begin{quote}
whenever $a,a'\in A$, $x\in L$, $0) = f(x)$ for all $x\in L_0$.
\item $g_1(x) = \$, $g_2(x) = \<0,x\>$,
for all $x\in L_0$.
\end{itemize}
The following easy observation is the crucial step in this proof:
\begin{quote}
The elements of the set $\{ \ : x \in L_0\}$ are
pairwise incomparable, so the function $\bar f$ is trivially monotone.
\end{quote}
By theorem~\ref{Told} we can find a lattice $L_1$, $L_0' \xx L_1$ in
which the functions $\bar f$, $g_1$ and $g_2$ are restrictions of polynomials
$p$, $q_1$ and $q_2$, respectively.
Now let $L = \oo(L_1, L_0)$, so $L$ is
an orthoextension of $L_0$.
Now $h({\x}) = p(q_1(\x) \vee q_2(\x^\pp)) $ is an orthopolynomial
with coefficients in $L$, and clearly $h(x) = p (
\ \vee \<0,x^\pp\>) =
p(\) =
\bar f(\) = f(x)$ for all $x\in L_0$.
\end{proof}
\begin{Remark}
For every orthopolynomial $p(\x)$ there is a lattice polynomial
$p'(\x,\y)$ such that (by de Morgan's laws) $p(\x)$ is equivalent to
$p'(\x,\x^\perp) $.
\end{Remark}
\begin{Definition} \label{power}
Let $\F$ a family of lattices. We say that
$\F$ is square closed if:
\begin{quote}
For every $S\in \F$ there is some $S'\in \F$ which is isomorphic to
$S\times S$.
\end{quote}
We say that $L$ is $\kappa$-square closed if the family of sublattices
of size $\le \kappa $ is square closed.
\end{Definition}
\begin{Fact}
If $\F$ is square closed and closed under the formation of sublattices,
then:
For every $S\in \F$ and every $n>1$ there is some $S'\in \F$ which
is isomorphic to $S^n$.
\end{Fact}
\begin{Theorem}
Let $L$ be a complete ortholattice, and let $\kappa$ be any cardinal.
Then:
\begin{enumerate}
\item
There is a complete ortholattice
$\bar L$ extending $L$ such that
every function
$f:L \to L$ is represented by an orthopolynomial of $\bar L$.
\\
Moreover, $\bar L$ can be chosen to be of the form $\oo
(L_1,L)$ with $L \xx L_1$. In particular, $L$ will be convex in $\bar
L$.
\\
Moreover, $\bar L$ can be chosen to be $\kappa$-square closed.
\item There is a complete
ortholattice $\hat L$ extending $L$ such that:
\begin{quote}
For every natural number $n$, for every function
$f: \hat L^n \to \hat L$ and for every set $A \subseteq \hat L^n$ of
cardinality $\le \kappa$ there is an orthopolynomial $p({\tt x}_1,
\ldots , {\tt x}_n)$ with coefficients in $\hat L$ that interpolates
$f$ on every point in $A$.
\end{quote}
\end{enumerate}
\end{Theorem}
\begin{proof}
Choose a cardinal $\lambda$ of cofinality $>\kappa $ such that
there is a transfinite enumeration (not necessarily 1-1)
$\{f_i: 0 \le i < \lambda\}$ of all
functions $f:L \to L$.
Define an increasing
transfinite sequence $(L_i: i \le \lambda)$ of $\{0,1\}$-lattices
satisfying
\begin{enumerate}
\item $L_0 = L$.
\item If $i< j\le \lambda$, then $L_i \xx L_j$
\item For every $i< \lambda$ there is a lattice polynomial $p_i$ with
coefficients in $L_{i+1}$ such that for all $z\in L$: $f_i(z) = p_i(z,
z^{\pp_L})$.
\item For every $i< \lambda$, $L_{i+1}$ contains an isomorphic copy
of $L_i^2$.
\item If $i$ is a limit stage, then $L_i$ is the direct limit of
$(L_j:j