\documentclass[%
version=last,%
a5paper,
10pt,%
headings=small,%
bibliography=totoc,%
index=totoc,%
twoside,%
reqno,%
cleardoublepage=empty,%
%open=any,%
parskip=half,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=true,%
pagesize]%{scrreprt}
{scrartcl}

%\usepackage[notref,notcite]{showkeys}
\renewcommand{\theequation}{\fnsymbol{equation}}

\usepackage[headsepline]{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ohead{\pagemark}
\ihead{\headmark}

\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{url}

\usepackage{amsmath,amsthm,amssymb,bm,upgreek,mathrsfs}
\usepackage[all]{xy}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\conc}{\mathbin{\hat{\ }}}
\newcommand{\sig}{\mathscr S}
\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\size}[1]{\lvert#1\rvert}
\DeclareMathOperator{\setMod}{Mod}
\newcommand{\sMod}[1]{\setMod(#1)}
\newcommand{\Mod}[2][]{\mathbf{Mod}_{#1}(#2)}
\newcommand{\Moda}[1]{\mathbf{Mod}^*(#1)}
\newcommand{\Str}{\mathbf{Str}}
\DeclareMathOperator{\sentences}{Sen}
\newcommand{\Sen}{\sentences}
\newcommand{\modsim}{/\mathord{\sim}}
\newcommand{\pow}[1]{\mathscr P(#1)}
\newcommand{\inv}{{}^{-1}}

\newcommand{\Cat}[1]{\bm{\mathsf{#1}}}
\newcommand{\Top}{\Cat{Top}}
\newcommand{\Frm}{\Cat{Frm}}
\newcommand{\Loc}{\Cat{Loc}}
\newcommand{\Grp}{\Cat{Grp}}
\newcommand{\Set}{\Cat{Set}}
\DeclareMathOperator{\domain}{dom}
\newcommand{\dom}[1]{\domain(#1)}
\DeclareMathOperator{\points}{pt}
\newcommand{\pt}[1]{\points(#1)}
\DeclareMathOperator{\homoms}{Hom}
\newcommand{\Hom}[1]{\homoms(#1)}
\newcommand{\bel}[1]{\left[#1\right]}

\newcommand{\Sn}[1][\sig]{\sentences_{\sig}}
\newcommand{\Sna}[1][\sig]{\sentences^*_{\sig}}
\DeclareMathOperator{\formulas}{Fm}
\newcommand{\Fm}[1][\sig]{\formulas_{#1}}
\DeclareMathOperator{\freevariables}{fv}
\newcommand{\fv}[1]{\freevariables(#1)}
\DeclareMathOperator{\variables}{v}
\newcommand{\vr}[1]{\variables(#1)}
\DeclareMathOperator{\theory}{Th}
\newcommand{\Th}[1]{\theory(#1)}
\newcommand{\Tha}[1]{\theory^*(#1)}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\setminus}{\smallsetminus}
\renewcommand{\leq}{\leqslant}
\renewcommand{\nleq}{\nleqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\phi}{\varphi}
%\newcommand{\Or}{\;\lor\;}
\newcommand{\Or}{\;\mathrel{\text{\textsc{or}}}\;}
\renewcommand{\models}{\vDash}
\newcommand{\nmodels}{\nvDash}
\newcommand{\included}{\subseteq}
\newcommand{\includes}{\supseteq}
\newcommand{\pincluded}{\subset}
\newcommand{\liff}{\Leftrightarrow}
\newcommand{\lto}{\Rightarrow}


\swapnumbers
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}{Lemma}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{document}

\title{Notes on compactness}
\author{David Pierce}
\date{\today}
\publishers{Mimar Sinan Fine Arts University\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}
\maketitle

I made these notes while preparing my talk ``Compactness'' 
at the Caucasian Mathematics Conference, Tbilisi, Georgia, 
September 5 \&\ 6, 2014.
I did not actually print out the notes for use during the talk;
but I spoke of some points from memory.
I am likely to use these notes 
in preparing for the tutorial at the School mentioned below.
Documents that I have been able to consult directly (if only in electronic form)
are in the References at the end;
footnotes contain other documents.

\begin{asparaenum}
\item
The Compactness Theorem is that 
if every finite subset of a set of sentences has a model, 
then the whole set has a model.
\item 
I shall give a tutorial on compactness 
at the
\begin{center}
5th World Congress and School on Universal Logic\\
June 20--30, 2015, Istanbul\\
\url{http://www.uni-log.org/}
\end{center}
\item
John Dawson \cite{MR1212899} reports that Vaught,\footnote{%%%%%
Vaught, R. L.
Model theory before 1945. 
\emph{Proceedings of the Tarski Symposium 
(Proc.\ Sympos.\ Pure Math., Vol. XXV, 
Univ.\ California, Berkeley, Calif., 1971),} 
pp.\ 153--172. Amer.\ Math.\ Soc., Providence, R.I., 1974.}
as well as van Heijenoort and Dreben,\footnote{%%%%%
In the introduction to the \emph{Collected Works, vol.~1} of G\"odel, 1986.}
finds the Compactness Theorem [for countable sets of sentences]
to be implicit in Skolem's 1922 paper \cite{Skolem-some-remarks} 
(Dawson writes 1923).
Looking at the paper, I find this plausible.
(It would be desirable to work out the details\dots)
\item
But the Compactness Theorem (for countable sets) was not made explicit
until G\"odel's 1930 article \cite{Goedel-compl} 
based on his doctoral dissertation.
\item
Mal$'$cev stated the Compactness Theorem 
(calling it, according to the translator, the ``general local theorem''), 
in 1941,\footnote{%%%%%
Mal$'$cev, A.
On a general method for obtaining local theorems in group theory. (Russian.)
\emph{Ivanov.\ Gos.\ Ped.\ Inst.\ U\v c.\ Zap.\ Fiz.-Mat.\ Fak.\ 1} 
(1941), no.\ 1, 3--9.}
but for a proof referred to his 1936 paper,%%%%%
\footnote{Maltsev, A . I. 1936 
`Untersuchungen aus dem Gebiete der mathematischen Logik', 
\emph{Matematicheskii Sbornik, n.s.,} \textbf 1, 323-336.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
which had been found dubious in a 1937 review by Rosser.\footnote{%%%%%
Mal$'$cev's 1936 paper is earlier than the earliest of his on MathSciNet;
so I have not seen Rosser's review.}
\item
But Mal$'$cev obtained interesting algebraic results, 
as:
\begin{quote}
  A locally soluble group of class $k$ is soluble of class $k$.

``Locally special groups are direct products of their Sylow subgroups.''
\end{quote}
In general, the review by I. Kaplansky of the 1941 paper says,
\begin{quote}
  Let $E_1$, \dots, $E_k$ be ``elementary'' properties of a group. 
Say that a group $G$ has type $[E_1,\dots,E_k]$ 
if it possesses a normal series $G\supset G_1\supset\dots\supset G_k$ 
such that each $G_i/G_{i+1}$ has property $E_{i+1}$. 
Theorem: $G$ is of type $[E_1,\dots,E_k]$ 
if and only if this is true for each finitely generated subgroup. 
An interesting application is the case where $k=2$ and $E_2$ is ``abelian'', 
$E_1$ is ``order $\leq m$ for a certain fixed $m$''. 
In this way we can pass from Jordan's theorem 
that any finite group of complex $n$-by-$n$ matrices 
has an abelian subgroup of index $\leq$ a number $m$ depending only on $n$, 
to Schur's theorem that the same is true 
for any (possibly infinite) torsion group of matrices. 
Further applications are given to a theorem of \v Cernikov 
[ibid.\ \textbf{8(50)} (1940), 377--394; MR0003422 (2,217a)] 
on Sylow series and a theorem attributed to Baer 
on lattice isomorphisms of groups. 
\end{quote}
\item
As the Prime Ideal Theorem for \emph{countable} rings 
requires no choice principle
(\emph{i.e.}\ follows from ZF alone)
so too the Compactness Theorem for \emph{countable} signatures.
This is observed, in effect, by Skolem \cite{Skolem-some-remarks},
who needs to prove the L\"owenheim--Skolem Theorem
(and in effect proves countable Compactness)
without using AC,
so that the Skolem Paradox results more plausibly.
\item
Four bits of evidence that the contents of my talk 
are not well known or well appreciated:
\begin{enumerate}
\item
Some model-theoretic sources suggest that the Compactness Theorem
is \emph{immediately} equivalent to the compactness of Stone spaces.
(The two theorems are equivalent, but not immediately equivalent.)
My examples are:
\begin{enumerate}
\item 
Keisler \cite{Keisler-fund} lets $S$ be the set of all $\Th{\str A}$
(``in a first order language L'').
Given a sentence $\phi$ [\emph{sic}%
\footnote{I think an arbitrary \emph{sentence} ought to be denoted by $\sigma$,
while $\phi$ can be an arbitrary \emph{formula.}}%%%%
] of L, he defines
\begin{equation*}
  [\phi]=\{p\in S\colon\phi\in p\},
\end{equation*}
and he notes that such sets are a basis of closed sets for a topology on $S$.
He calls $S$ thus topologized the \textbf{Stone space} of L.
He notes that, by the compactness theorem [\emph{sic}%
\footnote{Keisler does not capitalize the name of the theorem.}%
],
every set of basic closed sets with the finite intersection property
has nonempty intersection.
\begin{quote}
  In other words, the compactness theorem states that
the Stone space $S$ of L is compact.
\end{quote}
This is not literally wrong, 
but it uses a nonstandard \emph{definition} of a Stone space,
and so it obscures the significance of the Compactness Theorem.
\item
Tent and Ziegler \cite{MR2908005} say at the head of their Section 2.2,
just before proving the Compactness Theorem,
\begin{quote}
  Its name is motivated by the results in Section 4.2
which associate to each theory a certain compact topological space.
\end{quote}
Section 4.2 begins:
\begin{quote}
  We now endow the set of types of a given theory with a topology. 
The Compactness Theorem 2.2.1 then translates into the statement 
that this topology is compact, whence its name.

Fix a theory $T$. 
An $n$-type is a maximal set of formulas $p(x_1,\dots,x_n)$
consistent with $T$. 
We denote by $\mathrm S_n(T)$ the set of all $n$-types of $T$. 
We also write $\mathrm S(T)$ for $\mathrm S_1(T)$\dots

\textsc{Remark.} The Stone duality theorem asserts that the map
\begin{equation*}
X\mapsto\{C\mid C \text{ clopen subset of } X\}
\end{equation*}
yields an equivalence between the category of $0$-dimen\-sional compact spaces
and the category of Boole\-an algebras. 
The inverse map assigns to every Boole\-an algebra $B$ 
its Stone space $\mathrm S(B)$, 
the set of all ultrafilters (see Exercise 1.2.4) of $B$. 
\end{quote}
Here ``consistent'' means satisfiable.
Exercise 1.2.4 defines filters, ultrafilters, and ultraproducts
and asks for a proof of \L o\'s's Theorem.
Again nothing is literally wrong here.
But the notation suggests 
that type spaces are \emph{by definition} Stone spaces,
so that one might think the Compactness Theorem
was a special case of the compactness of Stone spaces.
\end{enumerate}
\item
The same sources and others prove Compactness
using the full force of the Axiom of Choice
(Keisler uses transfinite recursion; Tent \&\ Ziegler, Zorn's Lemma).
Poizat \cite{MR2001a:03072} spends 7 pages
discussing AC and mentions that the Prime Ideal Theorem
is strictly weaker,
but does \emph{not} point out
that this is sufficient for the Compactness Theorem; 
rather, he calls AC indispensible for this and other theorems.
(Rothmaler \cite{MR1800596} does refer the reader 
to Hodges \cite[\S6.2]{MR94e:03002},
where matters are made explicit.)
\item
The basic Compactness Theorem
is not always distinguished from stronger statements.
Rubin \&\ Rubin \cite{MR798475}
give almost literally the result of Vaught \cite{Vaught-1956}
given in the abstract quoted in its entirety below;
but they do not give Vaught's parenthesis:
\begin{quote}
Consider the following three known theorems 
concerning the existence of models of sentences 
(of the first-order predicate logic) : 
(1) a sentence having a model of power $\mathfrak b$ 
has also a model of every power $\mathfrak a$ 
such that $\aleph_0\leqq\mathfrak a\leqq\mathfrak b$; 
(2) a sentence having a model of power $\aleph_0$ 
has also a model of every power $\mathfrak c\geqq\aleph_0$; 
(3) if $Q$ is a set of sentences, 
in which the set of individual constants involved 
may have an arbitrary power $\mathfrak d$, 
and every finite subset of $Q$ has a model, 
then $Q$ has a model, 
whose power is not greater than $\mathfrak d+\aleph_0$. 
Theorem: 
\emph{Each of} (1), (2), \emph{and} (3) 
\emph{implies the Axiom of Choice in its general form.} 
As regards (3), this answers a question, raised by Henkin 
(Trans.\ Amer.\ Math. Soc.\ vol. 74 (1953) p.\ 420), 
as explicitly formulated. 
(On the other hand, the statement, 
obtained from (3) by dropping the final phrase (``whose\dots'') 
has been shown by Henkin and \L o\'s 
to be equivalent to the existence of prime ideals in Boolean algebras, 
and its exact relationship to the Axiom of Choice is still not determined.) 
The Theorem is derived from the known result (of Tarski) 
that the Axiom of Choice is implied by the statement: 
if $\aleph_0\leqq\mathfrak b$, then $\mathfrak b^2=\mathfrak b$. 
(Received January 13, 1956.)
\end{quote}
Rubin and Rubin list 8 equivalent formulations 
of the \emph{Boolean} Prime Ideal Theorem; 
but none of them is the (arbitrary) Prime Ideal Theorem
or the Compactness Theorem.

Rubin and Rubin refer to Vaught's three statements as
a downward L\"owenheim--Skolem theorem,
an upward L\"owenheim--Skolem theorem,
and a compactness theorem,
designating them as 
\texttt{LOG 1}, \texttt{LOG 2}, and \texttt{LOG 3} respectively.
Some sort of correction to \texttt{LOG 3} as indicated is needed
(otherwise $\Gamma$ could use singulary predicates, for example,
to say that all models are strictly larger than $\kappa$).

By the method of constants, \texttt{LOG 3} $\Rightarrow$ \texttt{LOG 2}.
By the original L\"owenheim--Skolem Theorem, 
\texttt{LOG 2} $\Rightarrow$ \texttt{LOG 1}.
Now suppose
\begin{align*}
  \aleph_0&\leq\kappa,&
\mu&=2^{\kappa\cdot\aleph_0}.
\end{align*}
Then
\begin{gather*}
  \mu^2=\left(2^{\kappa\cdot\aleph_0}\right)^2
=2^{\kappa\cdot\aleph_0\cdot2}
=2^{\kappa\cdot\aleph_0}
=\mu,\\
\aleph_0\leq\kappa\leq\mu.
\end{gather*}
In a signature $\{F\}$, where $F$ is a binary operation symbol,
let $\sigma$ say $F$ is surjective and injective.
Then $\sigma$ has a model of cardinality $\mu$.
If \texttt{LOG 1} holds, then $\sigma$ has a model of cardinality $\kappa$,
so
\begin{equation}\label{eqn:k}
  \kappa^2=\kappa.
\end{equation}
This in turn implies the Well Ordering Theorem.
For, let $\kappa^*$ be the least aleph that is not less than $\kappa$:
\begin{equation*}
  \kappa^*=\{\xi\colon\xi\in\mathbf{ON}\And\xi\leq\kappa\}.
\end{equation*}
By \eqref{eqn:k} (for all $\kappa$),
\begin{equation*}
  \kappa+\kappa^*=(\kappa+\kappa^*)^2\geq\kappa\cdot\kappa^*=\kappa^*\cdot\kappa.
\end{equation*}
This implies (by a result of Tarski)
that $\kappa$ and $\kappa^*$ are comparable.
Therefore $\kappa=\kappa^*$.

Under the supplied correction to \texttt{LOG 1},
without assuming the Axiom of Choice (but with the Prime Ideal Theorem),
all we know is that the model of $\Gamma$ is bounded in cardinality
by $\bigcup_{n\in\upomega}\kappa^n+\aleph_0$.
Assuming this bound is equal to $\kappa+\aleph_0$
is already equivalent to AC, as we have just seen.
\end{enumerate}
\item
The Maximal Ideal Theorem can be proved with Zorn's Lemma;
but the method of constructing the maximal ideal by transfinite recursion 
is useful to know.
The method is available automatically (without AC)
in the countable case.
\item
It is worthwhile to prove the Prime Ideal Theorem without AC,
to emphasize that primeness (unlike maximality) is local,
hence amenable to Compactness.
\item
According to Dawson, in topology, \emph{bicompact} was first defined
(``every open covering possesses a finite subcovering'')
``in a paper submitted in 1923 but not published until 1929''
by Alexandroff and Urysohn.
\item
The current \emph{name} of the Compactness Theorem 
(again according to Dawson)
first appeared in Tarski's 1950 address to the ICM 
in Cambridge, Massachusetts (published in 1952).
One of his versions of the theorem is that $\Str$ is compact;
but the formulation (as his Theorem 17) is basically as follows.
For every \emph{formula} $\phi$ of $\sig$,
let $\Mod{\phi}$ be the class of structures $\str A$ of $\sig$
such that every tuple of $A$ satisfies $\phi$ in $\str A$.
Thus $\Mod{\phi}=\Mod{\Forall{\bm x}\phi}$,
if $\phi\in\Fm(\bm x)$.
If a set of such classes has empty intersection,
then so does some finite subset.
Tarski's notation is more complicated,
involving first the function $\mathfrak F$ associated with $\phi$
that sends each $\str A$ to the subset of $A^{\upomega}$
whose elements satisfy $\phi$ in $\str A$.
Then our $\Mod{\phi}$ is his $\mathfrak{EL}(\mathfrak F)$,
which he calls an \textbf{arithmetical class.}
$\mathfrak F$ itself is an \textbf{arithmetical function,}
and there is a compactness theorem (Theorem 13) for these as well.
\item
Dawson notes, 
``few logic texts bother to explain the topological context 
of the compactness theorem at all.''
His example of an exception is Monk \cite{MR0465767}.
Monk derives the Compactness Theorem from the Completeness Theorem
(proved by Henkin's method).
He immediately says,
\begin{quote}
  The compactness theorem lies at the start of model theory,
and it will play a very important role in Part IV.
For some motivation for the name compactness theorem,
see Exercise 11.59.
\end{quote}
The exercise, quoted by Dawson, is
\begin{quote}
  Let $\mathbf K$ be a nonempty set of $\mathscr L$-structures. 
For each $\mathbf L\subseteq\mathbf K$ 
let $C\mathbf L=\{\mathfrak A\in\mathbf K:\mathfrak A
\text{ is a model of every sentence which}$
$\text{holds in all members of }\mathbf L\}$.
Show that with respect to $C$ as a closure operator, 
$\mathbf K$ is a compact topological space.
\end{quote}
Dawson shows that this is false as stated,
because there is a counterexample in which $\mathbf K$ consists of
the finite substructures of $\langle\mathbb N,<\rangle$:
look at the sentences saying there are at least $n$ elements.
Dawson \emph{could} just have noted that,
while the given closure operator makes $\Str$ a compact space,
not every subclass of this is compact.
Dawson does note that presumably Monk intended $\mathbf K$
to be ``elementary, or perhaps $\mathrm{AC}_{\delta}$''---%
but here $\mathrm{AC}_{\delta}$ means closed,
that is, elementary.
\end{asparaenum}

%\bibliographystyle{plain}
%\bibliography{../references}

\def\rasp{\leavevmode\raise.45ex\hbox{$\rhook$}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\begin{thebibliography}{10}

\bibitem{MR1212899}
John~W. Dawson, Jr.
\newblock The compactness of first-order logic: from {G}\"odel to
  {L}indstr\"om.
\newblock {\em Hist. Philos. Logic}, 14(1):15--37, 1993.

\bibitem{Goedel-compl}
Kurt G{\"o}del.
\newblock The completeness of the axioms of the functional calculus of logic.
\newblock In van Heijenoort \cite{MR1890980}, pages 582--91.
\newblock First published 1930.

\bibitem{MR94e:03002}
Wilfrid Hodges.
\newblock {\em Model theory}, volume~42 of {\em Encyclopedia of Mathematics and
  its Applications}.
\newblock Cambridge University Press, Cambridge, 1993.

\bibitem{Keisler-fund}
H.~Jerome Keisler.
\newblock Fundamentals of model theory.
\newblock In {\em Handbook of mathematical logic}, pages 47--103. North-Holland
  Publishing Co., Amsterdam-New York-Oxford, 1977.
\newblock Edited by Jon Barwise, With the cooperation of H. J. Keisler, K.
  Kunen, Y. N. Moschovakis and A. S. Troelstra, Studies in Logic and the
  Foundations of Mathematics, Vol. 90.

\bibitem{MR0465767}
J.~Donald Monk.
\newblock {\em Mathematical logic}.
\newblock Springer-Verlag, New York-Heidelberg, 1976.
\newblock Graduate Texts in Mathematics, No. 37.

\bibitem{MR2001a:03072}
Bruno Poizat.
\newblock {\em A course in model theory}.
\newblock Universitext. Springer-Verlag, New York, 2000.
\newblock An introduction to contemporary mathematical logic, Translated from
  the French by Moses Klein and revised by the author.

\bibitem{MR1800596}
Philipp Rothmaler.
\newblock {\em Introduction to model theory}, volume~15 of {\em Algebra, Logic
  and Applications}.
\newblock Gordon and Breach Science Publishers, Amsterdam, 2000.
\newblock prepared by Frank Reitmaier, translated and revised from the 1995
  German original by the author.

\bibitem{MR798475}
Herman Rubin and Jean~E. Rubin.
\newblock {\em Equivalents of the axiom of choice. {II}}, volume 116 of {\em
  Studies in Logic and the Foundations of Mathematics}.
\newblock North-Holland Publishing Co., Amsterdam, 1985.

\bibitem{Skolem-some-remarks}
Thoralf Skolem.
\newblock Some remarks on axiomatized set theory.
\newblock In van Heijenoort \cite{MR1890980}, pages 290--301.
\newblock First published 1922.

\bibitem{MR2908005}
Katrin Tent and Martin Ziegler.
\newblock {\em A course in model theory}, volume~40 of {\em Lecture Notes in
  Logic}.
\newblock Association for Symbolic Logic, La Jolla, CA, 2012.

\bibitem{MR1890980}
Jean van Heijenoort, editor.
\newblock {\em From {F}rege to {G}\"odel: {A} source book in mathematical
  logic, 1879--1931}.
\newblock Harvard University Press, Cambridge, MA, 2002.

\bibitem{Vaught-1956}
R.~L. Vaught.
\newblock On the axiom of choice and some metamathematical theorems.
\newblock {\em Bulletin of the American Mathematical Society}, 62(3), 1956.
\newblock Abstract of paper read by title at the 522nd meeting of the American
  Mathematical Society, New York, February, 1956.

\end{thebibliography}


\end{document}