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

\usepackage[headsepline]{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ohead{\pagemark}
\ihead{The Compactness Theorem (abstract)}

\usepackage{hfoldsty}
\usepackage{url}

\begin{document}

\title{The Compactness Theorem}
\subtitle{Abstract of a course to be given at the\\
5th World Congress and School on Universal Logic\\
June 20--30, 2015, Istanbul}
\author{David Pierce}
\date{September 18, 2014}
\publishers{Mimar Sinan Fine Arts University\\
Istanbul\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}
\maketitle

Let us say that a logic has the \emph{compactness property}
if a set of sentences of the logic has a model
whenever every finite subset of the set has a model.
For present purposes, \textbf{the Compactness Theorem}
is that first-order logic has the compactness property.
This theorem is fundamental to model theory.
However, Hodges's comprehensive twelve-chapter
1993 volume \emph{Model Theory}\nocite{MR94e:03002}
finds no need to state and prove the theorem until Chapter 6.
It is worthwhile to think about what needs Compactness and what does not.

One consequence of the Compactness Theorem
is that a set of sentences with arbitrarily large finite models
must have an infinite model.
A more purely mathematical consequence
is the \textbf{Prime Ideal Theorem:} 
\emph{every nontrivial commutative ring has a prime ideal.}
One can prove this by noting first
that every \emph{maximal} ideal is prime.
Moreover, every \emph{countable} ring has a maximal ideal;
for we can obtain a generating set of such an ideal
by considering the elements of the ring one by one.
In particular then, every finitely generated subring of a given ring
has a maximal ideal, because every finitely generated ring is countable.
By the Compactness Theorem then, 
the original ring must have an ideal that is at least prime,
although it might not be maximal.
The point here is that primeness is a ``local'' property,
while maximality is not.

It is usually understood that every nontrivial commutative ring has, 
not just a prime ideal, but a maximal ideal.
To make it easy to prove such results,
Zorn\nocite{MR1563165} stated in 1935 the result now known by his name.
However, Zorn's Lemma relies on the Axiom of Choice.
The Compactness Theorem is strictly weaker than this,
with respect to ZF (Zermelo--Fraenkel set theory
without Choice).
For, Compactness is also a \emph{consequence} 
of the Prime Ideal Theorem,
even the Boolean Prime Ideal Theorem;
and \emph{this} is strictly weaker than the Axiom of Choice
(as shown by Halpern and L\'evy in 1971).\nocite{MR0284328}

The Compactness Theorem for \emph{countable} sets of sentences
needs nothing beyond ZF.
Skolem showed this implicitly in 1922\nocite{Skolem-some-remarks}
when he established the paradox
that Zermelo's axioms for set theory\nocite{Zermelo-invest}
must have a countable model,
if they have a model at all.
In 1930, G\"odel\nocite{Goedel-compl} proved countable Compactness explicitly,
though not by that name.
Mal$'$tsev stated the full Compactness Theorem
as the General Local Theorem in 1941,
having proved it implicitly in 1936;
he used it to prove algebraic results
in the way we proved the Prime Ideal Theorem above.%
\nocite{MR0349383}%\nocite{Maltsev-1941}\nocite{Maltsev-1936}

In his 1950 address to the International Congress of Mathematicians,
Tarski\nocite{MR0045068} gave the Compactness Theorem its current name
and noted its topological meaning.
But this meaning is not generally well expressed
in today's textbooks of model theory.

The class of structures having a given signature
can be given a topology,
although the closed ``sets'' in this topology are not sets,
but proper classes
(except for the empty set):
they are the classes of models of sets of sentences.
The space of all structures has a Kolmogorov ($T_0$) quotient
that is a set:
it is the space of complete theories of structures.
If one replaces sentences with their logical equivalence classes,
then the set of sentences becomes a Boolean algebra,
called a Lindenbaum algebra;
and the complete theories of structures become ultrafilters 
of the Lindenbaum algebra.
By means of the Boolean Prime Ideal Theorem, 
the Stone space
consisting of \emph{all} ultrafilters of the Lindenbaum algebra 
is easily shown to be compact.
Or one could look instead at the spectrum,
consisting of the prime ideals of the corresponding Boolean ring;
the spectrum of every ring is compact.
The Compactness Theorem says more:
every ultrafilter of the Lindenbaum algebra
is derived from the complete theory of a structure.

The compactness theorem for \emph{propositional} logic
can be seen as a version of the theorem
that the product of two-element discrete spaces 
(or indeed any compact Hausdorff spaces) is compact.
The Compactness Theorem for first-order logic
does not follow so readily,
though it can be seen to result from a kind of reduction of first-order logic
to propositional logic.
Then Lindstr\"om's Theorem is roughly that
there is no such reduction for certain more expressive logics---but 
see that tutorial for more.
Sometimes the Compactness Theorem
is derived from the Completeness Theorem:
see \emph{that} tutorial for more.
Meanwhile, the present tutorial 
is intended to fill out the foregoing sketch
of the Compactness Theorem as such.\nocite{MR1212899}

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

\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{MR0284328}
J.~D. Halpern and A.~L{\'e}vy.
\newblock The {B}oolean prime ideal theorem does not imply the axiom of choice.
\newblock In {\em Axiomatic {S}et {T}heory ({P}roc. {S}ympos. {P}ure {M}ath.,
  {V}ol. {XIII}, {P}art {I}, {U}niv. {C}alifornia, {L}os {A}ngeles, {C}alif.,
  1967)}, pages 83--134. Amer. Math. Soc., Providence, R.I., 1971.

\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{MR0349383}
Anatoli{\u\i}~Ivanovi{\v{c}} Mal{\cprime}cev.
\newblock {\em The metamathematics of algebraic systems. {C}ollected papers:
  1936--1967}.
\newblock North-Holland Publishing Co., Amsterdam-London, 1971.
\newblock Translated, edited, and provided with supplementary notes by Benjamin
  Franklin Wells, III, Studies in Logic and the Foundations of Mathematics,
  Vol. 66.

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

\bibitem{MR0045068}
Alfred Tarski.
\newblock Some notions and methods on the borderline of algebra and
  metamathematics.
\newblock In {\em Proceedings of the {I}nternational {C}ongress of
  {M}athematicians, {C}ambridge, {M}ass., 1950, vol. 1}, pages 705--720. Amer.
  Math. Soc., Providence, R. I., 1952.

\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{Zermelo-invest}
Ernst Zermelo.
\newblock Investigations in the foundations of set theory {I}.
\newblock In van Heijenoort \cite{MR1890980}, pages 199--215.
\newblock First published 1908.

\bibitem{MR1563165}
Max Zorn.
\newblock A remark on method in transfinite algebra.
\newblock {\em Bull. Amer. Math. Soc.}, 41(10):667--670, 1935.

\end{thebibliography}


\end{document}