\documentclass[%
version=last,%
%%%%%%% For notes version %%%%%
%a5paper,%
%10pt,%
%%%%%%%%%% For slides version %%%%%
25pt,%
landscape,%
%titlepage,%
%%%%%%%%%%%%
%twoside,%
reqno,%
parskip=half,%
draft=true,%
DIV=12,%
headinclude=false,%
pagesize]
{scrartcl}

%\usepackage[turkish]{babel}
\usepackage[neverdecrease]{paralist}
\usepackage{relsize}
\usepackage{hfoldsty}
\setlength{\parindent}{0pt}
\raggedright
%\newenvironment{comment}{\hrulefill\par}{}
\usepackage{verbatim}

\usepackage{amsmath,amsthm,amssymb,url,upgreek,mathrsfs}
\usepackage{bm}
\usepackage[all]{xy}

\theoremstyle{definition}
\newtheorem*{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem*{example}{Example}
\newtheorem{corollary}{Corollary}
\numberwithin{corollary}{theorem}

\newcommand{\sig}{\mathscr S}

\newcommand{\Exists}[1]{\exists{#1}\;}
\newcommand{\Forall}[1]{\forall{#1}\;}
\newcommand{\liff}{\leftrightarrow}
\newcommand{\lto}{\rightarrow}
\newcommand{\diag}[1]{\operatorname{diag}(#1)}
\newcommand{\Str}[1][\sig]{\mathbf{Str}_{#1}}
\newcommand{\Mod}[1]{\mathbf{Mod}(#1)}
\newcommand{\Sen}[1][\sig]{\operatorname{Sen}_{#1}}
\newcommand{\Fm}[1][\sig]{\operatorname{Fm}_{#1}(x)}
\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\Th}[1]{\operatorname{Th}(#1)}
\newcommand{\Lin}[1][\sig]{\operatorname{Lin}_{#1}}
\newcommand{\modsim}{/\mathord{\sim}}
\newcommand{\simec}{^{\sim}}
\newcommand{\Sto}[1]{\operatorname{Sto}(#1)}
\newcommand{\card}[1]{\lvert#1\rvert}
\newcommand{\bv}[1]{\lVert#1\rVert}
\newcommand{\pow}[1]{\mathscr P(#1)}
\newcommand{\stnd}[1]{\mathbb{#1}}
\newcommand{\Z}{\stnd Z}
\newcommand{\Q}{\stnd Q}
\newcommand{\C}{\stnd C}
\newcommand{\R}{\stnd R}
\newcommand{\Or}{\;\mathrel{\textsc{or}}\;}

\renewcommand{\phi}{\varphi}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\setminus}{\smallsetminus}

\newcommand{\included}{\subseteq}
\newcommand{\nincluded}{\nsubseteq}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

\begin{document}
\title{Compactness}
\subtitle{Caucasian Mathematics Conference, Tbilisi}
\author{David Pierce}
\date{September 5 \&\ 6, 2014}
\publishers{Mimar Sinan Fine Arts University, Istanbul\\
\url{http://mat.msgsu.edu.tr/~dpierce/}
}

\maketitle

\newpage

In the background will be \textbf{Zermelo--Fraenkel set theory,}
in the first-order logic of signature $\{\in\}$:
\begin{description}
  \item[Equality:]\mbox{}
    \begin{compactenum}[$\bullet$]
\item
Equal sets are those having the same elements;
      \item
Equal sets are elements of the same sets.
    \end{compactenum}
\begin{comment}
  

    \begin{align*}
a=b&\liff\Forall x(x\in a\liff x\in b),\\
a=b\land a\in c&\lto b\in c.
    \end{align*}


\end{comment}
  \item[Comprehension:]
Every formula $\phi(x)$ defines the \textbf{class}
\begin{equation*}
  \{x\colon\phi(x)\}.
\end{equation*}
Certain classes are sets,
namely:
\begin{inparaitem}
\item 
the empty class,
\item
a pair of sets,
\item
the union of a set,
\item
the image of a set under a function,
\item
the power class of a set,
\item
$\upomega$.
\end{inparaitem}
\end{description}

We do not assume the
\textbf{Axiom of Choice (AC),} which is equivalent to the
\textbf{Well Ordering Theorem.}

\newpage

\mbox{}\hfill
\makebox[0pt][r]{
\begin{math}
  \xymatrix@!R=11mm
{
\makebox[6cm][l]{\text{L\"owenheim--Skolem Th.}}\ar@{<--}[dd]
&
&\parbox{6cm}{\centering compactness of\\Stone spaces}
\\
&
&
\\\parbox{6cm}{\centering Compactness for\\countable sets}
&\text{Compactness Th.}\ar[ddr]
&\parbox{6cm}{\centering Boolean\\Prime Ideal Th.}\ar@{<->}[uu]\ar@*{[|(4)]}[l]
\\
&
&
\\
&\text{Tarski--Vaught Test}\ar@{-->}[dd]
&\text{Prime Ideal Th.}\ar[uu]
\\\makebox[6cm][l]{\text{Henkin's Th.}}\ar@{-->}[uuur]\ar@{-->}[ur]\ar@{-->}%@(d,l)
                                                          [dddr]
&
&\text{Max.\ Ideal Th.}\ar@{<->}[dd]\ar[u]
\\
&\makebox[8cm][l]{\text{L\"owenheim--Skolem--Tarski Th.}}
&
\\
&
&\text{AC}\ar[ul]\ar[dl]
\\
&\text{\L o\'s's Theorem}
&
}
\end{math}
}

\newpage

\begin{theorem}[1930s?]\label{thm:wo-max}
The \textbf{Maximal Ideal Theorem} 
(for nontrivial, commutative, unital rings)
follows from AC.
\end{theorem}

\begin{proof}
A ring $\str R$ with $R=\{a_{\xi}\colon\xi<\kappa\}$ has maximal ideal
  \begin{equation*}
\bigcup_{\xi<\kappa}I_{\xi},\text{ where }
    I_{\xi}=
    \begin{cases}
    (a_{\xi})+\bigcup_{\eta<\xi}I_{\eta},&\text{ if this is proper,}\\
\bigcup_{\eta<\xi}I_{\eta},&\text{ otherwise.}
    \end{cases}
  \end{equation*}
This \emph{is} a proper ideal 
because the class of commutative $\str R$-algebras without identity 
is $\forall\exists$-axiomatizable, 
as by \emph{e.g.}
\begin{equation*}
  \Forall x\Exists yxy\neq y.\qedhere
\end{equation*}
\end{proof}

\begin{theorem}[Hodges, 1979]
The Maximal Ideal Theorem implies the Axiom of Choice.
\end{theorem}

\begin{theorem}[Halpern \&\ Levy, 1971]
The Maximal Ideal Theorem 
does not follow from the \textbf{Prime Ideal Theorem.}
\end{theorem}

\newpage

The \emph{signature} $\sig_{\text{ring}}$ of a ring $\str R$ 
is $\{0,1,-,+,\times\}$.
Let
\begin{equation*}
  \diag{\str R}
=\{\text{quantifier-free sentences of $\sig_{\text{ring}}(R)$ true in $\str R$}\};
\end{equation*}
its models are just the structures in which $\str R$ embeds.

\begin{theorem}[Henkin, 1954]
The \textbf{Prime Ideal Theorem}
follows from the
\textbf{Compactness Theorem} of first-order logic
(a \emph{theory} whose every finite subset has a \emph{model} has a model).
\end{theorem}

\begin{proof}
In the signature $\sig_{\text{ring}}\cup\{P\}$, let
\begin{align*}
   \bm K&=\{\text{rings with prime ideal $P$}\},&T&=\Th{\bm K}.
\end{align*}
Then 
$\Mod{T}=\bm K$: 
every model of the theory of $\bm K$ is in $\bm K$.

Every finitely generated sub-ring of a ring $\str R$ has a prime ideal,
by Theorem \ref{thm:wo-max}.

Hence
every finite subset of $T\cup\diag{\str R}$ has a model.
\end{proof}

\newpage

%Why ``Compactness''?
A proper class $\bm X$ can be topologized by
\begin{center}
a relation $\models$ (``turnstile'') from $\bm X$ to a set $B$.
\end{center}
If $x\in\bm X$ and $\sigma\in B$ and
$x\models\sigma$,
say $x$ is a \textbf{model} of $\sigma$.
So we define
\begin{equation*}
\Mod{\sigma}=\{x\in\bm X\colon x\models\sigma\}.  
\end{equation*}
If $\Gamma\included B$, we let
\begin{equation*}
  \Mod{\Gamma}=\bigcap_{\sigma\in\Gamma}\Mod{\sigma}.
\end{equation*}
These are the \textbf{closed classes} 
of a \textbf{topology} on $\bm X$,
assuming (as we do) that
for some $0$ in $B$ and binary operation $\lor$ on $B$,
\begin{align*}
\emptyset&=\Mod{0},&
\Mod{\sigma}\cup\Mod{\tau}&=\Mod{\sigma\lor\tau}.
\end{align*}

\newpage

Call a subset $\Gamma$ of $B$ \textbf{consistent} if
\begin{equation*}
\Mod{\Gamma_0}\neq\emptyset, 
\quad\text{ that is, }\quad
\bigcap_{\sigma\in\Gamma_0}\Mod{\sigma}\neq\emptyset,
\end{equation*}
for all finite subsets $\Gamma_0$ of $\Gamma$.
If it always follows that $\Mod{\Gamma}\neq\emptyset$,
then the topology on $\bm X$ is \textbf{compact.}

In any case, we may assume 
$B$ also has an element $1$ and a binary operation $\wedge$ such that
\begin{align*}
  \bm X&=\Mod1,&\Mod{\sigma}\cap\Mod{\tau}&=\Mod{\sigma\wedge\tau}.
\end{align*}
Now define \textbf{logical equivalence} in $B$ by
\begin{equation*}
  \sigma\sim\tau\iff\Mod{\sigma}=\Mod{\tau}.
\end{equation*}
Then $(B,0,1,\lor,\land)\modsim$ is a well-defined distributive lattice.

\newpage

If $x\in\bm X$, let
\begin{equation*}
  \Th x=\{\sigma\in B\colon x\models\sigma\},
\end{equation*}
\begin{minipage}{0.45\textwidth}
\mbox{}\hfill
\makebox[0pt][r]{
  \begin{math}
        \xymatrix@!0@R=4cm@C=6cm{
\bm X\ar@{>>}[d]^{x\mapsto\Th x}\ar@{~>}[r]^{\models}
&B\ar@{>>}[d]^{\sigma\mapsto\sigma\simec}\\
\{\Th x\colon x\in\bm X\}\rule[-1.7ex]{0ex}{2ex}
\ar@{~>}[r]
&
B\modsim\rule[-1.7ex]{0ex}{2ex}
}
  \end{math}
}
\end{minipage}
\hfill
\begin{minipage}{0.45\textwidth}
the \textbf{theory} of $x$.  
The set of these theories 
is naturally a \textbf{Kolmogorov} ($T_0$) \textbf{quotient} of $\bm X$.
Since
$0\notin\Th x$ and
$1\in\Th x$, while
\end{minipage}
\begin{equation*}
  \sigma\vee\tau\in\Th x\iff\sigma\in\Th x\Or\tau\in\Th x,
\end{equation*}
$\Th x\modsim$ is a \textbf{prime filter} of $B\modsim$.
Let
\begin{equation*}
  \Sto{B\modsim}=\{\text{prime filters of $B\modsim$}\},
\end{equation*}
and if $\sigma\in B$, let
$[\sigma]=\{F\in\Sto{B\modsim}\colon\sigma\simec\in F\}$.
Thus
\begin{equation*}
  x\in\Mod{\sigma}\iff\Th x\modsim\in[\sigma].
\end{equation*}

\newpage

\begin{minipage}{0.45\textwidth}
\mbox{}\hfill
\makebox[0pt][r]{
  \begin{math}
        \xymatrix@!0@R=6cm@C=7cm{
\bm X\ar@{>>}[d]^{x\mapsto\Th x}\ar@{~>}[r]^{\models}
&B\ar@{>>}[d]^{\sigma\mapsto\sigma\simec}\\
\{\Th x\colon x\in\bm X\}\rule[-1.7ex]{0ex}{2ex}
\ar@{>->}[d]^{\Th x\mapsto\Th x\modsim}
\ar@{~>}[r]
&
B\modsim\rule[-1.7ex]{0ex}{2ex}
\ar@{>->>}[d]^{\sigma\simec\mapsto[\sigma]}
\\
\Sto{B\modsim}\ar@{~>}[r]^(.45){\in}
&\{[\sigma]\colon\sigma\in B\}
}
  \end{math}
}
\end{minipage}
\hfill
\begin{minipage}{0.5\textwidth}
\begin{theorem}\mbox{}
  \begin{itemize}
  \item 
If the Prime Ideal Theorem holds,
then $\Sto{B\modsim}$ is compact and Kolmogorov ($T_0$)
when topologized by $\{[\sigma]\colon\sigma\in B\}$ under $\in$.
\item
The map
\begin{equation*}
x\mapsto\Th x\modsim
\end{equation*}
from $\bm X$ to $\Sto{B\modsim}$
is continuous,
and its image is dense and is a Kolmogorov quotient of $\bm X$.
  \end{itemize}
\end{theorem}
\end{minipage}




%\textbf{Logic} studies how algebras $(B,0,\lor)$ topologize classes.


\pagebreak

Given a signature $\sig$ (such as $\sig_{\text{ring}}$), we can let
\begin{itemize}
\item 
$\bm X$ be the class $\Str$ of \emph{structures} having signature $\sig$,
\item
$B$ be the set $\Sen$ of first-order \emph{sentences} in $\sig$,
\item
$\models$ be the relation of \emph{truth} from $\Str$ to $\Sen$.
\end{itemize}
In addition to $\lor$ and $\land$, $\Sen$ has the operation $\lnot$,
where
\begin{equation*}
\Str\setminus\Mod{\sigma}=\Mod{\lnot\sigma}.  
\end{equation*}
Then
$\Sen\modsim$ is a Boolean algebra, called a \textbf{Lindenbaum algebra}, so
\begin{itemize}
\item 
its prime filters are \emph{ultrafilters,}
\item
$\Sto{\Sen\modsim}$ is Hausdorff.
\end{itemize}
Is the image of $\Str$ in $\Sto{\Sen\modsim}$ compact?

\pagebreak

A subset $\Gamma$ of $\Sen$ is \textbf{complete} 
if it is consistent and always contains $\sigma$ or $\lnot\sigma$.

Equivalently,
$\Gamma=\bigcup\mathscr U$
for an ultrafilter $\mathscr U$ of $\Sen\modsim$.

Let $\Fm=\{\text{formulas of $\sig$ with free variable $x$}\}$.
%The key theorem is

\begin{theorem}[Henkin, 1949]
Suppose
\begin{itemize}
\item 
$T$ is a complete subset of $\Sen$, and
\item
$T$ has \textbf{witnesses:}
for every $\phi$ in $\Fm$,
for some constant $c$ in $\sig$,
\begin{equation*}
T\;\text{ contains }\;\Exists x\phi\lto\phi(c).
\end{equation*}
\end{itemize}
Then $T$ has a \textbf{canonical model,}
whose universe consists of its interpretations of the constants in $\sig$.
\end{theorem}

\pagebreak

\begin{corollary}[Mal'cev, 1941]
The Prime Ideal Theorem implies the Compactness Theorem.
\end{corollary}

\begin{proof}
Suppose $\Gamma$ is a consistent subset of $\Sen$.
We can find
\begin{itemize}
\item 
a set $A$ of constants not in $\sig$, together with
\item
a bijection $\phi\mapsto c_{\phi}$
from $\Fm[\sig(A)]$ to $A$.
\end{itemize}
Let
$\Gamma^*=  \Gamma\cup\{\Exists x\phi\lto\phi(c_{\phi})\colon
\phi\in\Fm[\sig(A)]\}$.
Then
\begin{itemize}
\item
  $\Gamma^*$ has witnesses and is consistent;
\item
the same is true of any complete subset of $\Sen[\sig(A)]$ 
that includes $\Gamma^*$;
\item
such complete sets exist, by \emph{Lindenbaum's Lemma}
(1930, following from the Prime Ideal Theorem).
\qedhere
\end{itemize}
\end{proof}

\pagebreak

\begin{corollary}[Tarski--Vaught Test, 1957]
  If $\str A\included\str B$,
that is, $\str B\models\diag{\str A}$,
and if for all $\phi$ in $\Fm$, for some $a$ in $A$,
\begin{equation*}
  \str B\models\Exists x\phi\lto\phi(a),
\end{equation*}
then 
\begin{equation*}
 \str A\preccurlyeq\str B 
\end{equation*}
($\str A$ is an \textbf{elementary substructure} of $\str B$),
that is,  $\str B\models\Th{\str A_A}$,
where $\str A_A$ is the obvious expansion of $\str A$ to $\sig(A)$.
\end{corollary}

\begin{proof}
  $\str A_A$ is a canonical model of $\Th{\str B_A}$.
\end{proof}

For example, 
\begin{align*}
(\{0,1\},+)&\nincluded(\Z,+),&
\Z&\included\Q,&
\Z&\not\preccurlyeq\Q,&
\Q^{\text{alg}}&\preccurlyeq\C.
\end{align*}

\pagebreak

\begin{corollary}[L\"owenheim--Skolem--Tarski Theorem]
Every structure of at least the (infinite) cardinality of its signature
has an elementary substructure of exactly that cardinality,
assuming AC.
\end{corollary}

\begin{proof}
There is a substructure of that size to which the Tarski--Vaught Test applies.
\end{proof}

The \textbf{L\"owenheim--Skolem Theorem} is the case of countable signatures
(this does not need AC).

Hence the \textbf{Skolem Paradox:}
It is a theorem of ZF that $\R$ is uncountable;
but if ZF has a well-ordered model,
it has a countable model.

(By G\"odel's Second Incompleteness Theorem,
it is not a theorem of ZF that ZF has a model at all.)

\pagebreak

\begin{corollary}[\L o\'s's Theorem, 1955]
Assume AC.  Suppose
\begin{itemize}
  \item
$(\str A_i\colon i\in\Omega)\in\Str{}^{\Omega}$, 
and $\mathscr U$ is an ultrafilter of $\pow{\Omega}$;
\item
$A=\prod_{i\in\Omega}A_i$, and
$\str A_i^*$ is the expansion of $\str A_i$ to $\sig(A)$ so that
  \begin{equation*}
a^{\str A_i^*}=a_i
  \end{equation*}
when $a$ is $(a_i\colon i\in\Omega)$ in $A$;
\item
$\bv{\sigma}=\{i\in\Omega\colon\str A_i^*\models\sigma\}$ 
when $\sigma\in\Sen[\sig(A)]$;
\item
$T=\bigl\{\sigma\in\Sen[\sig(A)]\colon
\bv{\sigma}
\in\mathscr U\bigr\}$ (which is consistent).
\end{itemize}
Then
$T$ has a \emph{canonical} model: an \textbf{ultraproduct} of the $\str A_i$.
\end{corollary}

\begin{proof}
  If $T$ contains $\Exists x\phi$, 
then it contains $\phi(a)$, where
  \begin{equation*}
    \str A_i^*\models\Exists x\phi\iff\str A_i^*\models\phi(a_i).\qedhere
  \end{equation*}
\end{proof}

\newpage

\begin{theorem}[Lindstr\"om, 1966]
There is no proper ``uniform'' compact refinement of the topology on $\Str$
that retains the L\"owenheim--Skolem Theorem.
\end{theorem}

The Compactness Theorem may be so called because:
\begin{enumerate}[1)]
\item\label1
$\{\Th{\str A}\modsim\colon\str A\in\Str\}$ is a Stone space, and
\item\label2
Stone spaces are compact.
\end{enumerate}
But the work lies in proving, not \eqref{2}, but \eqref{1}:
In some logics, \eqref1 fails.

Some formulations of the Compactness Theorem 
are equivalent to the Maximal Ideal Theorem;
but it is desirable to recognize the basic form above,
equivalent to the Prime Ideal Theorem.

Next June 20--30 in Istanbul: \url{http://www.uni-log.org/}

\end{document}