
\documentclass[portrait,notes]{seminar}
\usepackage{fancybox,amssymb}
\slideframe{oval}
\usepackage{eepic} 
\usepackage{epic} 
\usepackage{mathrsfs}
\usepackage{color}
\definecolor{brightred}{rgb}{1,0,0}
% \definecolor{halfred}{rgb}{1,0,0}



\newcommand{\brightred}{\textcolor{brightred}}

 
\def\xx#1:{\medskip\noindent{\bf #1:} } 
\def \yy#1\par{\centerline{\bf #1}}


\newcommand{\N}{{\mathbb N}}
\renewcommand{\P}{{\mathscr P}}
\newcommand{\Rel}{{\rm Rel}}
\newcommand{\rel}{{\rm Rel}}
\newcommand{\sinv}{{\rm sInv}}
\newcommand{\aut}{{\rm Aut}}
\newcommand{\Sym}{{\rm Sym}}
\newcommand{\sym}{{\rm Sym}}
\newcommand{\LL}{{\mathfrak L}} 
\newcommand{\M}{{\mathfrak M}} 
\newcommand{\ccup}{\mathbin{ \dot{\cup}}}
\def\indentandnextline{\\ \null~~~~}
 
\begin{document}
% \renewcommand{\theslide}{\arabic{slide}/11}



\begin{slide*}   % erste Folie

\
\bigskip\bigskip
\begin{center}
{
\Large\bf
 1-opc lattices
}
\vfill
\bigskip
\bigskip

 {\bf  
 Martin Goldstern\\
 TU Wien\\[9mm]
 {\tt\small http://www.tuwien.ac.at/goldstern/}
 }


\end{center}

\end{slide*}
\begin{slide*}
 

\yy opc lattices 


\xx Definition: A lattice $\LL = (L,{\vee},{\wedge}) $ is called
\brightred{ ``order-polynomially complete'' (opc)} iff
\begin{quote} For all $n$, every monotone function $f:\LL^n\to \LL$ is induced by a lattice polynomial.
\end{quote}

\bigskip
\bigskip

$\LL$ is called \brightred{$1$-opc} if 
\begin{quote} Every {\em unary}
 monotone function $f:\LL\to \LL$ is induced by a lattice polynomial.
\end{quote}

\end{slide*}
\begin{slide*}
 
\yy Finite opc lattices 

\xx \brightred{Theorem A}:  (Schweigert 1972) If $L$ is finite, then 
$$ \LL  \mbox{ is 1-opc}\    \Longleftrightarrow \ \LL  \mbox{ is opc} $$

Proof:  Lagrange interpolation. ({\small  Note:  this yields  a very 
{\it effective} or {\it explicit} proof})



\xx Example:  Let $A$ be any finite set with $\ge 3$ elements.  Then $\M_A $ is opc, where $\M_A = (M_A, \le)$, 
\brightred{
$M_A = A\ccup \{0,1\}$}, $A$ an antichain between $0$ and $1$. 

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0004in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(6024,4350)(0,-10)
\path(3012,3975)(12,2175)(3012,375)
	(6012,2175)(3012,3975)(612,2175)
	(3012,375)(5412,2175)(3012,3975)
	(1512,2175)(3012,375)(4512,2175)(3012,3975)
\put(2562,2025){\makebox(0,0)[lb]{$\cdots$}}
\put(3012,4200){\makebox(0,0)[lb]{1}}
\put(3012,0){\makebox(0,0)[lb]{0}}
\put(3087,2325){\makebox(0,0)[lb]{$A$}}
\put(4787,3325){\makebox(0,0)[lb]{$\M_A$}}
\end{picture}
}
\end{center}
\end{figure}




\end{slide*}
\begin{slide*}

\ \vskip 1cm 
\yy Infinite opc lattices

\vfil

\end{slide*}
\begin{slide*}
\xx \brightred{Theorem B}: (G$*$+Shelah, 1997-98)  There are 
\brightred{no infinite opc} lattices. 


The proof of theorem B analyzes the properties that the {\em 
cardinality} of an infinite opc lattice must have:  It cannot 
be countable, cannot be a successor cardinal {\small (Erd\H os-Rado used
here)}, cannot be a singular limit {\small (more infinite combinatorics 
used here)} and 
cannot be a limit of uncountable cofinality --- hence does not exist.

This approach made many people unhappy.

\bigskip
\xx Problem 1:
\indentandnextline
Find a \brightred{``purely algebraic''} proof of theorem B. 

\xx Meta-Problem: \indentandnextline
\brightred{What does ``purely algebraic'' mean?} 

\xx Problem 2:  
\indentandnextline
Show that there are 
\brightred{no infinite \textcolor{black}{1}-opc lattices}. 



\end{slide*}
\begin{slide*}
\yy What is ``purely algebraic''?  


\bigskip


An approximation to ``purely algebraic'': 
\begin{center}
\bf 
Let's use \brightred{less  set theory}! 
\end{center}

\bigskip

\xx Definition: We call a proof ``\brightred{explicit}'',
 if it does not use the
axiom of choice, i.e., if it can be carried out in ZF
(Zermelo-Fraenkel axioms of set theory 
\brightred{without the axiom of choice}.)


\xx Theorem \brightred{``-B''}: (G$*$+Shelah, 1998)\\
\indentandnextline
There is no ``explicit'' proof of theorem B. 

{\tiny (Proof sketch see slide \pageref{-B})}

\bigskip\bigskip We can interprete this as a hint that there is
\brightred{no~``purely algebraic''} proof of theorem B.


\bigskip\bigskip\bigskip\bigskip
\null


\end{slide*}
\begin{slide*}
\yy opc \ vs 1-opc


\xx Conjecture \brightred{C}: 
\indentandnextline
There are no infinite 1-opc lattices. 

% \medskip
\xx Conjecture \brightred{C'}: 
\indentandnextline
Every (infinite) 1-opc lattice is opc.   

\medskip


Recall that for finite lattices: C=false, C'=true.



\bigskip

By theorems A and B, we have:    C $\Leftrightarrow $ C'. 



\bigskip

Conjecture C trivially implies theorem B, so:

By theorem -B, there is \brightred{no explicit proof of C}. 


But perhaps it is easier to find a \brightred{proof of C'}?  


\bigskip


\xx Theorem \brightred{-C'}:  There is no explicit proof of C'. 




\end{slide*}
\begin{slide*}
\yy Proof of theorems \brightred{-B} and  \brightred{-C'} (sketch)


An infinite set $A$ is called \brightred{``amorphous''} if all subsets of $A$ are
either finite or cofinite; equivalently, if all subsets of $A$ are
definable with parameters from $A$ in predicate logic with no
predicates except equality. 

An infinite set $A$ is called \brightred{``strongly amorphous''} if: for all $n$,
 all subsets of $A^n$ are definable in predicate logic with equality,\\
 or equivalently, if all subsets of $A^n$ are in the Boolean algebra
 generated by the sets
\begin{enumerate}
\item[]  \brightred{$\{(x_1,\ldots, x_n): x_i=x_j\}$}: 
$i,j \in
 \{1,\ldots , n\}$ 
\item[]  \brightred{$\{ (x_1,\ldots, x_n): x_i=a\}$}: $i\in
 \{1,\ldots , n\}, a\in A$.
\end{enumerate}

\end{slide*}
\begin{slide*}




\xx Fact:
  If $A$ is strongly amorphous, then all maps $f:M_A^n\to M_A$
(so in particular: all monotone maps 
$f:\M_A ^n\to \M_A$) are definable in predicate logic with equality.  

This can be 
\label{-B}     
used to show
\begin{quote} 
\brightred{
If $A$ is strongly amorphous, then $\M_A$ is infinite and opc. 
}
\end{quote}

{\small
\xx Note:
The existence of strongly amorphous sets is consistent with ZF (i.e., 
cannot be ``explicitly'' refuted). 

}

\end{slide*}
\begin{slide*}

Similarly, the existence of a an infinite set $A$ with an equivalence 
relation $E$ satisfying {\sl
\begin{enumerate}
\item[(a)] All $E$-classes have exactly 3 elements
\item[(b)] All maps $f:A^n\to A$, and even all maps $f:M_A^n\to M_A$,
can be defined in predicate logic using the predicates ``$E$'' and
``$=$'' only
\end{enumerate}}
is consistent with ZF. 


Now check that for such a set $A$, all
\brightred{unary} monotone maps $f:\M_A \to \M_A$
are either almost constant or almost the identity, which in turn shows that they are represented by lattice polynomials.   
\brightred{$\Rightarrow \M_A$ is 1-opc}  

However, the \brightred{binary} map
$$ f(x,y) = 
\bigg\{ 
\begin{array}{ll}
  1 & \mbox{if }x=1\ \vee\  y=1\  \vee\  x\sim_E y\\
  x & \mbox{otherwise}
\end{array}
$$  
is monotone and {\bf not} represented by a lattice polynomial. 
\brightred{$\Rightarrow \M_A$ is not opc}  
\end{slide*}
\begin{slide*}

\yy Open Questions

\xx Question: 
Show that there are 
\brightred{no infinite 1-opc lattices}. 
\\
{\small (Equivalently, that 1-opc implies opc)}

{\sl [We know that there is no explicit proof.]}

\medskip
The proof of theorem -C' tells us that really 
there is no explicit proof 
of \brightred{$1$-opc $\Rightarrow$ $2$-opc}. 
\vskip-0.2cm
\xx Question: 
\indentandnextline
 Is there an explicit proof of 
\brightred{2-opc $\Rightarrow$ opc}?

\bigskip

The proof of theorem -B really showed (explicitly) that 
$\M_A$ is \brightred{definably opc}, i.e.: . 
\begin{quote}
Whenever $f:\M_A^n \to \M_A$ is a monotone function which is 
\brightred{first order definable} 
in the structure $(\M_A,{\le})$, \\
then $f$ is represented by a polynomial. 
\end{quote}


\xx Question:  Find a lattice which is 
\brightred{definably 1-opc} but not 
\brightred{definably opc}. 

\vfill
\


\end{slide*}


\end{document}
