
\documentclass{slides}
% \usepackage{slides}
% \usepackage{color}
\usepackage{amsfonts}
\usepackage{mathrsfs}


\def\xx#1:{\medskip\noindent{\bf #1:} }
\parskip0pt

\begin{document}


\newcommand{\3}{\ss}

\newcommand{\C}{{\mathscr C}}
\newcommand{\complex}{{\mathbb C}}
% \definecolor{halfgreen}{rgb}{0,0.5,0}
% \definecolor{halfblue}{rgb}{0.9,0.9,1}
\newcommand{\dark}{\textcolor{halfgreen}}
\newcommand{\lightblue}{\textcolor{blue}}
\newcommand{\A}{{\mathfrak A}}
\newcommand{\B}{{\mathfrak B}}
\newcommand{\Z}{{\Bbb Z}}
\newcommand{\R}{{\Bbb R}}
\newcommand{\N}{{\Bbb N}}
\newcommand{\K}{{\cal K}}
\newcommand{\I}{{\rm I}}
\newcommand{\II}{{\rm II}}
\renewcommand{\P}{{\mathscr P}}
\newcommand{\Q}{{\Bbb Q}}
\def\itm#1 {\par\vskip-9mm\hangindent 0.9cm \hangafter1
\noindent\hbox to 0.9cm{\hss#1 }\ignorespaces}
\def\itn{\itm{--} }

\title{Set theory and Lattice Theory}

\raggedright \advance\rightskip -1cm plus -0.5cm 


% \begin{center}
% \lightblue{ \tt Martin.Goldstern@tuwien.ac.at }
% \bigskip\bigskip
% \hrule %\vrule width 0.5\hsize height 0.5pt
% \end{center}



\begin{itemize}
\item The role of set theory in general
\item As an application: \\
Proof sketch that there are no infinite opc lattices. 

\end{itemize}







\newpage

\begin{center} Size  and counting 
\end{center}

\begin{tabular}{lll}
Pre-math:        &  singular & plural \\
\end{tabular}
\begin{tabular}{rrll}
ancient math:&  &1, 2, 3, 4, 5, \dots\\
or even:   &   &1, 2, 3, 4, 5, \dots,&$\infty$\\
or sometimes:&   &1, 2,   3, 4, 5, \dots,&verboten \\
India?       & 0,&1, 2, 3, 4, 5, \dots\\
\end{tabular}

20th century naive mathematics: 0,1,2,3,4,5,\dots, 
                                                 countable,  uncountable  

Cantor, 19th century: there is much more than that. Not only two
infinite cardinalities,  but really infinitely many. 
In fact, uncountably many.

\newpage



$A \sim B$ iff there is a bijection $f: A\to B$   [``equipotent'', ``equinumerous'', ``gleichm\"achtig'']\\
$A \le B $ iff there is a 1-1 map $f:A \to B$\\
$A < B$ iff  $A \le B$ but $A \not\sim B$\\

\xx Theorem:   If $A \le B$ and $B \le A$ then $A \sim B$. 
\xx Theorem:  For all $A$, $B$:  $A \ge B$ or $A \le B$. 

\xx Definition:  A ``cardinality'' is an equivalence class of equipotent sets. 

\bigskip
 \centerline{\vrule width 4cm height 0.5 pt }
\bigskip


% \begin{center} \bf Life starts at $\aleph_0$!  \end{center}
\xx Approximative Definition:   Set theory is the classification of 
sets up to equipotency. 



\xx Second approximation:  Set theory is the theory of well-orders 
(and of well-foundedness), and hence of ``transfinite induction''. 

% \xx Claim:  I will not give a correct definition of "set theory" in this talk. 



\newpage


INDUCTION on $\N$ --- an example.


\xx Theorem:  If $L$ is a countable lattice then there is a 
cofinal chain $C \subset L$.  \\ \relax
[cofinal = $\forall l\in L \,\exists c\in C: l \le c$]


Proof:   Let $L = \{l_0,l_1,l_2, ... \}$, let $c_0$ be arbitrary, 
$c_{n+1} = c_n \vee l_n$. 

In other words:   Well-order $L$ in a  NICE way
\\ \relax
[ $L$ is infinite, but each element has only finitely many predecessors]\\
and then construct $C$ ``by induction''. 

\bigskip
\hrule

\bigskip
Does this work for uncountable lattices? 

\newpage 

 TRANSFINITE  INDUCTION: \begin{center}  {\sl To infinity and beyond! }
\end{center}
\bigskip
\bigskip

\xx Theorem:  If $L$ is of cardinality $\aleph_1$,  \\
and 
\\  \ 
\\ 
then 
there is  a
cofinal chain $C \subset L$.  


Proof:  Well-order $L$ in a NICE way 
\\ \relax
[ $L$ is uncountable, but each element has only countably many 
 many predecessors]\\
and then proceed by induction: 

$c_0= $ arbitrary, $c_1 \ c_0 \vee l_1$, etc. 

In ``limit stages''  ? 

Use $\sigma$-completeness!

\newpage



\xx Question:  Is there an uncountable  Boolean algebra $B$ such that 
\itn All chains in $B$ are countable
\itn All (Boolean) antichains are countable ?


Note that $\P(\Q)$ has no uncountable antichains, but there is an uncountable 
chain: 
$$ \{ A_r: r \in \R \}$$
where $A_r = \{q: q<r\}$. 



\xx Answer:  perhaps no. 

\xx Answer: perhaps yes.   Well-order $\P(\N)$ and construct 
an uncountable increasing sequence of countable subalgebras with 
nice properties. [Baumgartner+Komjath]


\newpage


Notation: 
\\
$|A| $ = cardinality of $A$ 

   $2^A$ = set of all characteristic functions on $A$
\\
(isomorphic to $\P(A)$)


If $\kappa $ is a cardinal, say $\kappa = |A|$, we write 
$2^\kappa$ for  $ |2^A| = |\P(A)|$. 

To simplify the exposition we will use the [not true] assumption
$$ 2^{\aleph_0} = \aleph_1, \ 
   2^{\aleph_1} = \aleph_2, \ 
   2^{\aleph_2} = \aleph_3, \dots $$


$A^A  $  = set of all functions from $A$ to $A$. 


Cantor's theorem:   $|2^A| > |A|$.  \\

For infinite sets $A$ we have $|2^A | =  |A^A|$, so 
$$ |A| < |A^A|$$





\newpage 

From now on all lattices will be bounded: $(L, \vee, \wedge, 0,1)$. 

\xx Definition:  A lattice is called opc iff: \\
For all $n$: Every monotone function $f:L^n \to L$ is represented 
by a polynomial.  


\xx Note:  If $L$ is countable, then there are only contably many polynomials. 
More generally, if $|L| = \kappa$, then there are only 
$\kappa$ many polynomials, but there are $2^\kappa> \kappa $ many 
functions from $L$ to $L$. 

From now on all functions will be {\em monotone}.

\xx Example:   There are $2^{\aleph_0}$ many monotone  functions from
$\Q$ to $\Q$. 
\\ 
But there are also only $2^{\aleph_0}$ many monotone  functions from
$\R$ to $\R$  (and not $2^{2^{\aleph_0}}$). 

\newpage


\xx Fact:  Let $P$ be a partial order (with 0 and 1).
 If $P^n$ contains an antichain
[or a well-ordered chain]  $A$ 
of size $\kappa$, then there are $2^\kappa$ many 
\hskip 6cm 
monotone functions from $ A$ to $A$ (trivial), and 
 they can all be extended to monotone functions from $P^n$ to $P$ (easy).


Proof:   There are $2^\kappa$ many functions from $A$ to $A$.
We can extend them to functions from $L$ to $A \cup \{0,1\}$. 


\xx Strategy:  Let $L$ be an infinite lattice, say of size $\kappa$.
 We will try to find an antichain of size $\kappa$.  [Hence $L$ will 
not be opc]
\\  If we do not succeed, then our failure will give us another reason why 
$L$ is not opc. 



\newpage 

\xx Definition:   $ \kappa \to (\lambda)_3$ means:  
\\
Whenever you color the unordered pairs of a $\kappa$-element set with 3 
colors, then there is a $\lambda$-element ``homogeneous'' subset. 

\xx Theorem:   $\aleph_0 \to (\aleph_0)_3$. 



\xx Fact:    If   $ \kappa \to (\lambda)_3$, then: 
\\
Every partialorder with  $\kappa$ many elements 
contains a ``uniform set'' of size at least $\lambda$.
\\
(``Uniform'' means:  antichain, or well-ordered chain, or
dually well-ordered chain.)

\xx Theorem:    $\aleph_1 \not\to  (\aleph_1)_3$.   In fact, the relation
$\kappa \to (\kappa)_3$ is quite rare. 

However:   $\aleph_{n+1} \to  ( \aleph_n)_3$. 

\newpage

First step:   If $L$ is countable, then $L$ contains an antichain
[or chain -- we will ignore this case for simplicity]  of size 
$\aleph_0$, so there are unctbly many monotone functions from $L$ , 
not all of them can be polynomials. 


Next step:  $\aleph_1$. \\
Unfortunately, $\aleph_1 \to (\aleph_1)_3$ does not hold.   


However:  If $L$ contains an antichain of size $\aleph_0$, then there 
are $\aleph_1$ many functions  $f_i$ from $L$ to $L$. 
They can be chosen to be pairwise incomparable. 
Now since the lattice is opc, this gives us an antichain of
pw incomparable polynomials.
Wlog they are all of the same type, i.e. there is  some $k$ and a 
$k+1$-ary term $t =  t(x,y_1,...y_k)$ , and for all $i$: 
\\
$f_i(x)  =  t(x, \bar  c_i) $, where    $\bar  c_i \in   L^k$ are
the ``coefficients''. 

So the $c_i$ form an antichain of size $\aleph_1$ in some $L^k$, this gives us 
$\aleph_2 $ many functions from $L^k$ to $L$, etc. 
[Haviar and  Ploscica]. 


What about $\aleph_\omega$?  

We know $\aleph_{n+1} \to (\aleph_n)_3$, so for each $n$ we have an antichain
$A_n$ in $L$ of size $\aleph_n$.   

Together they have size $\aleph_\omega$,
but  are there $2^{\aleph_\omega}$ many 
monotone functions? 

Yes.  This uses the ``canonisations theorem'' and again $\aleph_0 
\to(\aleph_0)_3$. 

\bigskip
\vrule width 5cm height 0.5pt 
\bigskip


For $\aleph_{\omega+1}$ use  the same argument as for $\aleph_1$. \\
\dots 

For $\aleph_{\omega+\omega}$ use the same argument as for $\aleph_\omega$.


For $\aleph_{\omega_1}$ we use a new argument:
\\ Let $L$ be opc,
$|L| = \aleph_{\omega_1}$. 

Let $\Omega$ be a NICE well-order of size $\aleph_{\omega_1}$.  (so all 
initials segments of this wellorder have fewer than $\aleph_{\omega_1}$
many elements. 
\newpage

By transfinite induction on $j\in \omega$, construct an increasing
 sequence  $L_j: j \in  \Omega$ 
such that: 

% \begin{itemize}
\itn for all $j$: $|L_j| $ is smaller than $\aleph_{\omega_1}$. 
\itn there are $a_j$, $b_j \in L \setminus L_j$ which have the same 
``type'' over $L_j$ , i.e., $L_j$ cannot distinguish between them. 
\\
(This exists, because there are only $2^{|L_i|}< \aleph_{\omega_1}$ many
possible ``types'' = sets of equations)
\itn  There is a monotone function that maps $a_j$ to $0$ and $b_j$ 
  to $1$.   This functions is realized by a polynomial 
$t(x, \bar c_j)$: 
      $$ t(a_j,\bar c_j) = 0, \ \ t(b_j, \bar c_j) = 1$$
$\bar c_j \in L^n$ are the $n$ ``coefficients'' of the polynomial: 
\itn $a_j,b_j,\bar c_j \in L_{j'} $ for all $j'>j$. 
% \end{itemize}

\newpage

Now check that the $n+2$-tuples 
$(a_j, b_j, \bar c_j)$ form an antichain in $L^{n+2}$: 


If  $j<j'$ and 
$(a_j, b_j, \bar c_j)  \le  (a_{j'}, b_{j'}, \bar c_{j'})$ , then 
$$
 \begin{array}{ccc}
0= t(a_{j'},\bar c_{j'}) && t(b_{j'},\bar c_{j'}) = 1 \\
  |                      &&      | \\ 
 t(a_{j'},\bar c_{j}) & \sim & t(b_{j'},\bar c_{j})  \\
  |                      &&      | \\ 
0= t(a_j,\bar c_j) && t(b_j,\bar c_j) = 1 \\
 \end{array}
$$


But the equations 
 $t(a_{j'},\bar c_{j})=0$ 
$ t(b_{j'},\bar c_{j})  =1$ distiguish between $a_{j'}$ and
$b_{j'}$, using only coefficients from $L_{j'}$, contradiction.




\end{document}

How many nonisomorphic structures are there of the same cardinality with the
same theory?    At most $2^\kappa$, and we expect that this upper bound 
is obtained.    This umber is called $I(T,\kappa)$. 

Morley's theorem:    If $I(T,\aleph_1)=1$ then $I(T,\lambda)=1$ for all 
uncountable $\lambda$. \\
   Proof: develop a ``structure theory'' (such as ``vector
space is characterized by its dimension'') for structures satsifying $T$. 

Morley's conjecture:   If $\kappa<\lambda$, then $I(T,\kappa)\le I(T,\lambda)$. 
\\
Shelah's proof:  If $I(T,\lambda)< 2^\lambda$ then we can develop 
``structure theory''. 

