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