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