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

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

\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ofoot{\pagemark}
%\ihead{\headmark}
\refoot{The Compactness Theorem}
\lofoot{\leftmark}


\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{url}
\usepackage{relsize,moredefs,lips}

\usepackage{amsmath,amsthm,amssymb,bm,upgreek,mathrsfs}
\usepackage[all]{xy}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\proves}{\vdash}
\renewcommand{\models}{\vDash}
\newcommand{\included}{\subseteq}
\newcommand{\includes}{\supseteq}
\newcommand{\nincluded}{\nsubseteq}
\newcommand{\pincluded}{\subset}
\newcommand{\Mod}[2][]{\mathbf{Mod}_{#1}(#2)}

\newcommand{\liff}{\leftrightarrow}
\newcommand{\lto}{\rightarrow}

\DeclareMathOperator{\diagram}{diag}
\newcommand{\diag}[1]{\diagram(#1)}

\newcommand{\sig}{\mathscr S}
\newcommand{\str}[1]{\mathfrak{#1}}

\DeclareMathOperator{\sentences}{Sen}
\newcommand{\Sen}[1][\sig]{\sentences_{#1}}
\newcommand{\Str}[1][\sig]{\mathbf{Str}_{#1}}



\newcommand{\simec}{^{\sim}}
\newcommand{\Sto}[1]{\operatorname{Sto}(#1)}
\newcommand{\bv}[1]{\lVert#1\rVert}

\newcommand{\modsim}{/\mathord{\sim}}
\newcommand{\pow}[1]{\mathscr P(#1)}
\newcommand{\powf}[1]{\mathscr P_{\upomega}(#1)}


\DeclareMathOperator{\formulas}{Fm}
\newcommand{\Fm}[1][\sig]{\formulas_{#1}}
\DeclareMathOperator{\theory}{Th}
\newcommand{\Th}[1]{\theory(#1)}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\setminus}{\smallsetminus}
\renewcommand{\leq}{\leqslant}
\renewcommand{\nleq}{\nleqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\phi}{\varphi}
\newcommand{\Or}{\;\mathrel{\text{\textsc{or}}}\;}


%\swapnumbers
\theoremstyle{definition}
\newtheorem*{theorem}{Theorem}
\newtheorem*{corollary}{Corollary}
\newtheorem*{compactness}{Compactness Theorem}
\newtheorem*{cantor}{Cantor Intersection Theorem}
\newtheorem*{heine}{Heine--Borel Theorem}
\newtheorem*{los}{\L o\'s's Theorem}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\begin{document}

\title{The Compactness Theorem}
\subtitle{A course of three lectures\\
one hour each\\
June 20--1, 2015\\
5th World Congress and School\\
on Universal Logic\\
June 20--30, 2015\\
Istanbul University}
\author{David Pierce}
\date{June 24, 2015\\
Edited September 4, 2016}
\publishers{Mathematics Department\\
Mimar Sinan Fine Arts University\\
Istanbul\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}
%\uppertitleback{\tableofcontents}

\maketitle\thispagestyle{empty}
\tableofcontents
\addchap{Preface}

This document consists of transcriptions 
of the three hour lectures of my course
on the Compactness Theorem
in the 5th World Congress and School on Universal Logic, June, 2015.

\begin{sloppypar}
I submitted the abstract (also included here) 
some nine months in advance of the School.
I have added the footnotes, and the year (1908) of Zermelo's axioms;
otherwise the abstract is unchanged,
though the references are now incorporated with others at the end of the present document.
Every work mentioned with a year has a citation in the references.
The submitted abstract was placed in a frame (\url{t5-compactness.html})
on the website (\url{http://www.uni-log.org/}) of the School and Congress: 
apparently this frame represented a conversion from the \url{pdf} version of my submitted abstract,
since hyphens were retained, though they no longer marked the ends of lines.
The use of frames means it is not possible 
to give a single link to the abstract as it was meant to be seen;
one must say rather, ``go to \url{http://www.uni-log.org/start5.html},
click on `Tutorials,'
and then click on `Compactness Theorem.'$\;$''
\end{sloppypar}

Mostly in the summer of 2014, I composed several collections of notes 
relevant to the Compactness Theorem.
These notes concerned, respectively,
\begin{compactenum}[(1)]
\item
the L\"owenheim--Skolem Theorem,
\item
G\"odel's Completeness Theorem,
\item
Tarski's 1950 ICM address (giving the Compactness Theorem its current name),
\item
Lindstr\"om's Theorem,
\item
logics in general, and
\item
the Compactness Theorem itself.
\end{compactenum}
In July, I gave a two-week course on nonstandard analysis at the Nesin Mathematics Village, \c Sirince;
and in this course I considered the logical relations between
the Compactness Theorem, \L o\'s's Theorem, and the Prime and Maximal Ideal Theorems.
I typed up and edited my lectures in this course.
I then gave a half-hour talk on the Compactness Theorem at the Caucasian Mathematics Conference,
Tbilisi, September 5 \&\ 6, 2014.
I used slides for that talk,  
and the course that is the subject of the present document is basically an expanded version of those slides.
All of these documents are among my webpages.

I started typing notes for the lectures of my course before giving them;
but then a fortuitous computer malfunction inhibited me from continuing.
Notes written at the computer are easier to edit and save and share,
which is why I am creating the present document.
However,
notes 
to be used in delivering a \emph{lecture}
are better written out by hand.
Hand writing provides muscle memory as well as, I think, 
a better visual memory of one's own words.
It also forces one to think about just how much writing one will want to do at the board.

Prepared \emph{after} the course, 
the notes below are a typeset version of my handwritten notes,
with changes and footnotes based on my memory of what actually happened in the lectures.
Paragraphs labelled as Remarks were only spoken out loud.
Other parts \emph{may} only have been spoken aloud;
it is hard to be precise on these matters.

The three hours of the course were distinct,
the respective themes being the Compactness Theorem
\begin{inparaenum}[(1)]
\item
in action,
\item
as a topological theorem, and
\item
proved.
\end{inparaenum}
Looking at notes from regular university courses that I had recently taught,
I had the idea that I could cover three or four of my handwritten pages (size A4) in a one-hour lecture.
This turned out to be nearly correct.
I tried to be prepared to curtail or jettison material at the end of my notes for each lecture.

Speakers in the other lectures that I attended used slides, 
unless technical problems prevented it.
I think the use of slides is usually a mistake,
especially for a \emph{course} of lectures.
Slides allow a speaker to pass too quickly through his or her material,
and they inhibit the listener from taking notes.
Speakers who use slides may also want to write on the board;
but since the room will have been darkened for the slides,
the speaker's writing will be hard to read.

For my convenience, I typed up the schedule of the two days
on which my course would meet.
The School of Universal Logic was to have an afternoon session on Saturday,
and morning and afternoon sessions on Sunday.
Then the schedule was changed,
because of the Turkish national university entrance examinations.
The Saturday afternoon session was delayed, 
and the Sunday morning session was shifted to Monday.
When the School actually began on Saturday, there was a further delay.
I believe the schedule given on the next page represents what actually happened.
\newpage
\mbox{}
\vfill
  \begin{center}\relscale{0.9}
\renewcommand{\arraystretch}{2}
  \begin{tabular}{|c|ccc|}\hline
    &Room I&Room II&Room III\\\hline
\multicolumn{4}{c}{Saturday, June 20, 2015}\\\hline
14:30&\multicolumn{3}{l|}{Opening: why studying [\emph{sic}] logic}\\\hline
15:00&Husserl \&\ Frege&Lindstr\"om&Completeness\\
16:00&Jain&L\"owenheim--Skolem&Nonsense\\\hline
17:00&\multicolumn{3}{c|}{coffee}\\\hline
17:30&Music&Politics&Relativity\\
18:30&COMPACTNESS&Category&Quantum\\\hline
\multicolumn{4}{c}{Sunday, June 21, 2015}\\\hline
14:00&COMPACTNESS&Politics&Relativity\\
15:00&Music&Category&Quantum\\\hline
16:00&\multicolumn{3}{c|}{coffee}\\\hline
16:30&COMPACTNESS&Kant&Nonsense\\
17:30&Husserl \&\ Frege&Lindstr\"om&Dugundji\\\hline
  \end{tabular}
\end{center}
\vfill  
  


\addchap{Abstract}

A logic has \emph{a compactness theorem}
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 a compactness theorem.
This theorem is fundamental to model theory.
One may however note that Hodges's encyclopedic twelve-chapter
1993 volume \emph{Model Theory}\nocite{MR94e:03002}
finds no need to 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 (first-order) 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 [1908] 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%%%%%
\footnote{I believe this name is the innovation of the translator, 
but Mal$'$tsev used no particular name.} 
%%%%%%%%%%%%%%%%%%%%%%%%
in 1941\nocite{Maltsev-1941},
having proved it implicitly in 1936\nocite{Maltsev-1936};
he used it to prove algebraic results
in the way we proved the Prime Ideal Theorem above.

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 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 \emph{Stone space}
consisting of \emph{all} ultrafilters of the Lindenbaum algebra 
is easily shown to be compact.
Or one could look instead at the \emph{spectrum,}
consisting of the prime ideals of the corresponding Boolean ring.
Spectra are always 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 propositional logic
can be seen as a version of the theorem,
known by the name of Tychonoff,
that the product of two-element discrete spaces 
(or indeed any compact spaces) is compact.
\emph{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.%%%%%
\footnote{My understanding of the history of the Compactness Theorem
depends on John Dawson's 1993 article\nocite{MR1212899}.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Compactness in Action}

\begin{remark}
I have lived in Istanbul for four years (and Turkey for fifteen).
Since I moved here with my spouse,
the subway station called Vezneciler near Istanbul University has opened.
When you come out of that station, you see a mosque, namely
\begin{center}
\textsc{Kalenderhane Camii.}
\end{center}
Perhaps many people hardly notice it, assuming it is just another mosque.
But it is not just another mosque, and it deserves further notice.  It is perhaps 800 years old,
and it was a church before the Ottoman Turkish conquest of Istanbul in 1453.
Similarly, in some model-theory texts at least,
the name of the Compactness Theorem is explained in passing
as being due to the compactness of a certain Stone space.
This casual reader accepts the explanation,
because the Stone space in question \emph{is} compact.%%%%%
\footnote{For example, Hodges \cite[\S6.2, p.\ 274]{MR94e:03002}
defines a Stone space as a non-empty compact Hausdorff space
with a basis of clopen sets.
He then states the theorem that the space of ultrafilters of a Boolean algebra is a Stone space.
In the next section, he defines a \textbf{complete type} as the complete type of some tuple
over a given set $X$ of parameters, in an elementary extension of a given structure $A$.
Using the Compactness Theorem, he shows that such a complete type
is precisely a set of formulas that is maximal among the sets of formulas 
with parameters from $X$
that are finitely realized in $A$.
If $X=\emptyset$ and $T=\Th A$, one then speaks of \emph{complete types of} $T$.
The set of complete types of $T$ in $n$ variables is denoted by $S_n(T)$ and called the $n$th \textbf{Stone space} of $T$,
``for reasons that will appear in a moment,'' namely, that the space
``is in fact the Stone space of a boolean algebra generally known as the $n$th \textbf{Lindenbaum algebra} of $T$\dots
The name `compactness theorem' originally came from the fact that $S_n(T)$ is a compact space.''
Strictly, Hodges has not formally defined the Stone space \emph{of} a Boolean algebra;
presumably it is to be understood as the space of ultrafilters of the algebra,
which space is a Stone space, as noted.
If $S_n(T)$ is the Stone space, in this sense, of the $n$th Lindenbaum algebra of $T$,
then it is automatically compact, regardless of the Compactness Theorem.
But if $S_n(T)$ is a space of complete types in the original sense of complete types \emph{of tuples,}
then the Compactness Theorem can be understood as the theorem that $S_n(T)$ is compact.}
%%%%%%%%%%%%%%%%%%%%%%%%%
But \emph{every} Stone space is compact,
and every logic gives rise to a Stone space,
namely the Stone space
consisting of the prime filters
of the distributive lattice of logical equivalence-classes of sentences.%%%%%
\footnote{This is spelled out in the second lecture.}
%%%%%%%%%%%%%%%%%%%%%%
The Compactness Theorem is that,
in first-order logic, each of those prime filters actually has a model.
\end{remark}

We shall use the notation
\begin{align*}
  \N&=\{1,2,3,\dots\},&\upomega&=\{0\}\cup\N.
\end{align*}
Consider $(\N,1,x\mapsto x+1)$ as a \emph{structure} in the \emph{signature}
$(1,S)$.
It satisfies the \textbf{Peano Axioms} (1889\nocite{Peano}):
\begin{gather*}
  \Forall x\Forall y(Sx=Sy\lto x=y),\\
\Forall xSx\neq1,\\
\Forall X\bigl(1\in X\land\Forall y(y\in X\lto Sy\in X)
\lto\Forall yy\in X\bigr).
\end{gather*}

\begin{theorem}[Dedekind, 1888\nocite{MR0159773}]
  For all models $\str A$ of the Peano Axioms,
for all structures $\str B$ in the signature $\{1,S\}$,
there is a unique homomorphism from $\str A$ to $\str B$.
\end{theorem}

\begin{remark}
We know the axioms by Peano's name,
apparently because he wrote them out formally;
but Dedekind recognized them earlier and understood them better.
In particular, Dedekind understood that all three of the axioms were needed
to ensure existence of the homomorphism of the theorem.%%%%%
\footnote{I elaborated at the beginning of the second lecture.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{remark}

\begin{corollary}
  All models of the Peano Axioms are isomorphic to
the structure $(\N,1,x\mapsto x+1)$.
Hence if $c$ is a new constant symbol, then%%%%%
\footnote{\label{correction}%
Apparently I wrote $S^{(n)}c\neq1$ rather than $c\neq S^{(n)}1$;
I made the correction at the beginning of the second lecture.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation*}
  \{\text{Peano Axioms}\}\cup\{c\neq S^{(n)}1\colon n\in\upomega\}
\end{equation*}
has no model, although every finite subset has.
\end{corollary}

\begin{sloppypar}
\begin{compactness}[Skolem, 1922\nocite{Skolem-some-remarks};
G\"odel, 1930\nocite{Goedel-compl};
Mal${}'$cev, 1936\nocite{Maltsev-1936}, 1941\nocite{Maltsev-1941}] 
In a \emph{first-order} logic,
there is a model of a set of sentences,
if there is of every finite subset.
\end{compactness}
\end{sloppypar}

\textbf{First-order} means:
\begin{compactenum}[1)]
  \item
variables stand for individuals, not sets;
\item
formulas are finite.
\end{compactenum}
By Compactness,
the Peano Axioms have no first-order formulation.
Neither do the axioms of \textbf{torsion groups,}
which are the abelian-group axioms,
along with\footnote{There was a question about what $nx$ means.
It means $\underbrace{x+\dots+x}_n$.}
\begin{equation*}
\Forall x\bigvee_{n\in\N}nx=0.
\end{equation*}

\begin{theorem}[Tarski, 1954; \L o\'s, 1955]
  In a signature $\sig$,
suppose $T$ is a (first-order) theory,
and $\sigma$ is a (first-order) sentence
that is \textbf{preserved in substructures} in $\Mod T$, that is,
\begin{equation*}
  \text{if $\str A,\str B\models T$, $\str A\included\str B$, and $\str B\models\sigma$, then $\str A\models\sigma$.}
\end{equation*}
Then for some \emph{universal} sentence $\tau$ of $\sig$,
\begin{equation*}
  T\proves\sigma\liff\tau.
\end{equation*}
\end{theorem}

\begin{remark}
The converse is easy 
and was alluded to in Nate Ackerman's talk on the L\"owenheim--Skolem Theorem.
\end{remark}

\begin{proof}
  By Compactness,
  \begin{compactenum}[1)]
    \item
$T\proves\sigma\liff\bigwedge\Gamma$, where
      \begin{equation*}
        \Gamma=\{\tau\in\Sen\colon\tau\text{ is universal and }
T\proves\sigma\lto\tau\};
      \end{equation*}
\item
$T\proves\sigma\liff\bigwedge\Gamma_0$ 
for some finite subset $\Gamma_0$ of $\Gamma$.
  \end{compactenum}
Details:
\begin{asparaenum}
  \item
We show $T\cup\Gamma\proves\sigma$.
Say $\str A\models T\cup\Gamma$; we show $\str A\models\sigma$.
By hypothesis, it is enough to find $\str B$ such that
\begin{align*}
  \str B&\models T,&
\str A&\included\str B,&
\str B&\models\sigma.
\end{align*}
This means finding a model of
\begin{equation*}
  T\cup\diag{\str A}\cup\{\sigma\},
\end{equation*}
where $\diag{\str A}$ is the \textbf{diagram} of $\str A$,
namely the quantifier-free theory of $\str A_A$
(the obvious expansion of $\str A$ to $\sig(A)$,
which has a new constant symbol 
for each element of the universe $A$ of $\str A$).%%%%%
\footnote{The parenthetical remark is in my notes,
but I must not have written it all down;
for somebody asked me what the Roman $A$ was.
Apparently she was unfamiliar with my convention,
which comes from Chang and Keisler\nocite{Chang--Keisler}.
I did not mention that Hodges\nocite{MR94e:03002}
traces diagrams to Wittgenstein's 
\emph{Tractatus} 4.26\nocite{WittgensteinTLP}.}
If there is no model,
then by Compactness, for some%%%%%
\footnote{Out loud I observed that logic is concerned with correct expression,
but it is difficult to explain expressions in detail.
We should understand that $\phi$ is a quantifier-free formula of $\sig$,
and $\vec a$ is a tuple of elements of $A$.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$\phi(\vec a)$ in $\diag{\str A}$,
\begin{gather*}
  T\proves\sigma\lto\lnot\phi(\vec a),\\
T\proves\sigma\lto\Forall{\vec x}\lnot\phi,\\
\Forall{\vec x}\lnot\phi\in\Gamma,\\
\str A\models\Forall{\vec x}\lnot\phi,\\
\str A\models\lnot\phi(\vec a),\\
\lnot\phi(\vec a)\in\Gamma,
\end{gather*}
which is absurd.
\item
Now $T\cup\Gamma\cup\{\lnot\sigma\}$ has no model,
so by Compactness, neither has $T\cup\Gamma_0\cup\{\lnot\sigma\}$.%%%%%
\footnote{I may not have written out even this much.
However, in Peter Arndt's earlier talk on Lindstr\"om's Theorem,
somebody had been confused
about applying Compactness to the characteristic of fields.
Arndt observed that a theorem about fields of characteristic $0$
would be true in fields of large-enough characteristic;
the questioner apparently thought that only the converse was the case.}
%%%%%%%%%%%%%%%%%%%%%
\qedhere
\end{asparaenum}
\end{proof}

\begin{remark}
Hodges gives the following as an application of a generalization of the theorem.
\end{remark}

\begin{sloppypar}
\begin{theorem}[Mal${}'$cev, 1940]
A group has a faithful $n$-dimensional representation
(that is, an embedding in $\mathrm{GL}_n(K)$ for some field $K$)
if every finitely generated subgroup does.%%%%%
\footnote{Somebody asked what $\mathrm{GL}_n(K)$ was.}
%%%%%%%%%%%%%%%%%%%
\end{theorem}
\end{sloppypar}

The \L o\'s--Tarski Preservation Theorem yields:
\begin{equation*}
  \Th{\{\text{substructures of models of $T$}\}}\included T_{\forall}
\end{equation*}
(and the converse is easy).
From algebra,
\begin{equation*}
  \{\text{substructures of fields}\}=\{\text{integral domains}\},
\end{equation*}
an \textbf{elementary class}
(that is, $\Mod T$ for some theory $T$).

\begin{theorem}
For all theories $T$,
the class of substructures of models of $T$ is an elementary class:
If $\str A\models T_{\forall}$, then $\str A$ embeds in an element of $\Mod T$.
\end{theorem}

\begin{proof}
  $T\cup\diag{\str A}$ has a model, by Compactness,
as in the proof of the \L o\'s--Tarski Theorem.
\end{proof}

What are the semigroups that embed in groups?
They are precisely the models of some universal theory.%%%%%
\footnote{It turns out that it was Mal${}'$cev 
who first found this theory,
at least implicitly;
but there are infinitely many axioms.
See \cite{MR3248511}.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Compactness as a Topological Theorem}

%It is the set
As we saw, the set%%%%%
\footnote{This assumes the correction in note \ref{correction} on page \pageref{correction}.
In my handwritten notes, and in the original June 24, 2015,
version of the present document,
instead of ``As we saw, the set\lips has no model,'' 
I wrote ``It is the set\lips that has no model.''}
%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{gather*}
  \{  \Forall x\Forall y(Sx=Sy\lto x=y),\\
\Forall xSx\neq1,\\
\Forall X\bigl(1\in X\land\Forall y(y\in X\lto Sy\in X)
\lto\Forall yy\in X\bigr),\\
c\neq1,c\neq S1,c\neq SS1,c\neq SSS1,\dots\}
\end{gather*}
%that 
has no model, although every finite subset does
(just let $c$ be large enough).

\begin{sloppypar}
On $\N$, addition is the unique operation $+$ such that
\begin{align*}
  n+1&=Sn,&n+Sx&=S(n+x).
\end{align*}
That is, $x\mapsto n+x$ is the unique homomorphism
from $(\N,1,x\mapsto x+1)$ to $(\N,n+1,x\mapsto x+1)$
guaranteed by Dedekind's theorem.
The existence of such homomorphisms 
usually requires all three of the Peano Axioms.
In fact, the definitions of addition and multiplication
require only the induction axiom
(as Landau shows implicitly
in \emph{Foundations of Analysis}\nocite{MR12:397m}).
This is why \emph{modular} addition and multiplication are possible:
these are operations in $\Z/n\Z$, which allows proofs by induction.
\end{sloppypar}

But exponentiation needs more than induction.
For example, \emph{modulo} $3$, we have
\begin{align*}
  2^1&\equiv2,&
2^2&\equiv2\cdot 2\equiv1,&
2^3&\equiv2,&
2^4&\equiv2\cdot 2\equiv1\not\equiv 2^1,
\end{align*}
although $4\equiv1$.

\begin{sloppypar}
\begin{cantor}
Provided $F_0$ is also bounded,%%%%%
\footnote{Originally I said each $F_k$ was bounded;
but then that might seem to imply that all closed sets are bounded.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
a decreasing chain
\begin{equation*}
  F_0\includes F_1\includes F_2\includes\cdots
\end{equation*}
of closed intervals of $\R$ has nonempty intersection:
for this intersection contains
\begin{equation*}
  \inf\{\sup F_k\colon k\in\upomega\}.
\end{equation*}
This fails for other intervals:
\begin{align*}
\bigcap_{k\in\upomega}[k,\infty)&=\emptyset,&
\bigcap_{k\in\N}\left(0,\textstyle\frac1k\right)&=\emptyset.
\end{align*}
But it still holds if each $F_k$ is
\begin{compactenum}[1)]
  \item
the union of finitely many closed bounded intervals;
\item
the intersection of any number of such unions.
\end{compactenum}
\end{cantor}
\end{sloppypar}

Such intersections are the \textbf{closed} subsets of $\R$.
Let $\tau$ be the set of these.  Then%%%%%
\footnote{Somebody asked me after the lecture
why the second condition was true.
It is true by the distributivity of taking unions over taking intersections:
\begin{equation*}
 \bigcap A\cup\bigcap B=\bigcap_{a\in A}\bigcap_{b\in B}a\cup b.
\end{equation*}}
\begin{compactenum}[1)]
  \item
$\emptyset\in\tau$,
\item
$X\in\tau\And Y\in\tau\implies X\cup Y\in\tau$,
\item
$\mathscr X\included\tau\implies\bigcap\mathscr X\in\tau$.
\item
$\R\in\tau$ (here $\R$ can be understood as $\bigcap\emptyset$).
\end{compactenum}

\begin{heine}
A collection $\mathscr X$ of bounded closed subsets of $\R$
has non-empty intersection
if each finite subcollection does.  
\end{heine}

\begin{proof}
  We may assume $\mathscr X$ is countable,
since each closed interval 
is the intersection of the larger closed intervals with rational endpoints:%%
\footnote{I just made the explanation out loud,
until somebody asked for clarification.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation*}
  [\alpha,\beta]=\bigcap_{\substack{a\leq\alpha<\beta\leq b\\a,b\in\Q}}[a,b].
\end{equation*}
Then $\mathscr X$ has the form $\{F_k\colon k\in\upomega\}$,
and we can apply the Cantor Intersection Theorem to
\begin{equation*}
  F_0\included F_0\cap F_1\included F_0\cap F_1\cap F_2\included\cdots
\qedhere
\end{equation*}
\end{proof}

The theorem is that bounded closed subsets of $\R$ are \textbf{compact.}
In his address to the 1950 ICM\nocite{MR0045068},
Tarski called the Compactness Theorem by this name
and noted that it did establish compactness of certain topological spaces.
We can understand these spaces as $\Str$,
the spaces of structures in the signature $\sig$ for various $\sig$.

Let
\begin{align*}
\bm A&=\Str,\\
B&=\Sen=\{\text{first-order sentences of $\sig$}\}.
\end{align*}
There are
\begin{compactitem}
\item
a relation $\models$ from $\bm A$ to $B$,
\item
a binary operation $\lor$ on $B$.
\end{compactitem}
If $\sigma\in B$, we define
\begin{equation*}
\Mod{\sigma}=\{a\in\bm A\colon a\models\sigma\}.
\end{equation*}
Then%%%%%
\footnote{At some point I was asked what the operation ``vee'' was.
My explanation that it was logical disjunction was immediately satisfactory to the questioner.
I believe I did point that, more generally, it would be any operation making \eqref{eqn:Mod} true.}
%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation}\label{eqn:Mod}
\Mod{\sigma}\cup\Mod{\tau}=\Mod{\sigma\lor\tau}.
\end{equation}
Thus the classes $\Mod{\sigma}$ are a basis for a topology on $\bm A$
where every closed subclass is, for some subset $\Gamma$ of $B$,
\begin{align*}
&\Mod{\Gamma},&
&\text{that is,}&
&\bigcap_{\sigma\in\Gamma}\Mod{\sigma}.
\end{align*}
Every topology on a set or class $\bm A$ can be seen as arising in this way
from a structure $(B,\lor)$ and a relation $\models$ from $\bm A$ to $B$ such that \eqref{eqn:Mod} holds.
This topology is \textbf{compact,} provided that
\begin{equation*}
\Mod{\Gamma}\neq\emptyset
\end{equation*}
whenever $\Gamma\included B$ and, for every finite subset $\Gamma_0$ of $\Gamma$,
\begin{equation*}
\Mod{\Gamma_0}\neq\emptyset.
\end{equation*}
Thus the Compactness Theorem is that $\Str$ is compact.

\begin{sloppypar}
In the general case, we can produce a structure $(C,\lor,\land,\bot,\top)$ or $\str C$
such that
\begin{compactitem}
\item
$(B,\lor)\included(C,\lor)$,
\item
$\Mod{\bot}=\emptyset$ and $\Mod{\top}=\bm A$,
\item
for all $\sigma$ and $\tau$ in $C$,
\begin{compactitem}
\item
\eqref{eqn:Mod} holds,
\item
$\Mod{\sigma\land\tau}=\Mod{\{\sigma,\tau\}}$,
\item
$\Mod{\sigma}=\Mod{\Gamma}$ for some subset%%%%%
\footnote{Normally $\Gamma$ will be finite;
but we may allow it to be infinite if we wish.}
%%%%%%%%%%%%%%%%%%%%
 $\Gamma$ of $B$.
\end{compactitem}
\end{compactitem}
Now let
\begin{equation*}
\sigma\sim\tau\iff\Mod{\sigma}=\Mod{\tau}.
\end{equation*}
Then $\str C\modsim$ is a well-defined distributive lattice.
If $a\in\bm A$, define
\begin{equation*}
\Th a=\{\sigma\in C\colon a\models\sigma\}.
\end{equation*}
Then
\begin{multline*}
\Th a=\Th b\iff\\
\text{$a$ and $b$ are topologically indistinguishable.}	
\end{multline*}
Thus $\{\Th a\colon a\in\bm A\}$ is a \textbf{Kolmogorov} (or $T_0$) quotient of $\bm A$.%%%%%
\footnote{I think I did not actually express this this last sentence,
since several students in the audience had indicated that they did not know anything about topology.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation*}
 \xymatrix{
\bm X\ar@{>>}[d]_{x\mapsto\Th x}\ar@{~>}[r]^{\models}
&C\ar@{>>}[d]^{\sigma\mapsto\sigma\simec}\\
\{\Th x\colon x\in\bm X\}%\rule[-1.7ex]{0ex}{2ex}
\ar@{~>}[r]
&
C\modsim%\rule[-1.7ex]{0ex}{2ex}
}
\end{equation*}
Moreover,
\begin{align*}
\bot&\notin\Th a,&
\top&\in\Th a,
\end{align*}
and
\begin{equation*}
\sigma\lor\tau\in\Th a\iff\sigma\in\Th a\Or\tau\in\Th a.
\end{equation*}
Therefore, by definition, $\Th a\modsim$ is a \textbf{prime filter} of $\str C\modsim$.
But possibly not every prime filter of $\str C\modsim$ is of this form.
Let
\begin{gather*}
\Sto{\str C\modsim}=\{\text{prime filters of $\str C\modsim$}\},\\
[\sigma]=\{F\in\Sto{\str C\modsim}\colon\sigma\simec\in F\}.
\end{gather*}
Then
\begin{equation*}
[\sigma]\cup[\tau]=[\sigma\lor\tau],
\end{equation*}
so the $[\sigma]$ induce a topology on $\Sto{\str C\modsim}$ by the relation $\in$
(that is, the $[\sigma]$ themselves are basic closed sets).
\begin{equation*}
 \xymatrix{
\bm X
\ar@{>>}[d]_{a\mapsto\Th a}
\ar@{~>}[r]^{\models}
&C
\ar@{>>}[d]^{\sigma\mapsto\sigma\simec}\\
%%%%%%%%%%%%%%%%
\{\Th x\colon x\in\bm X\}\rule[-1.7ex]{0ex}{2ex}
\ar@{~>}[r]
\ar@{>->}[d]_{\Th a\mapsto\Th a\modsim}
&
C\modsim\rule[-1.7ex]{0ex}{2ex}
\ar@{>->>}[d]^{\sigma\simec\mapsto[\sigma]}\\
%%%%%%%%%%%%%%%%%%
\Sto{\str C\modsim}
\ar@{~>}[r]^{\in}
&\{[\sigma]\colon\sigma\in C\}
}
\end{equation*}
The map $\Th a\mapsto\Th a\modsim$ is a dense topological embedding 
of the space $\{\Th a\colon a\in\bm A\}$ in $\Sto{\str C\modsim}$
since if $[\sigma]\neq\emptyset$, then $\sigma\nsim\bot$, so $\Mod{\sigma}\neq\emptyset$.
\end{sloppypar}

By the Prime Ideal Theorem,
$\Sto{\str C\modsim}$ is compact,
since if 
\begin{equation*}
\bigcap_{\sigma\in\Gamma_0}[\sigma]\neq\emptyset
\end{equation*}
for all finite subsets $\Gamma_0$ of $\Gamma$,
that is, all $\Gamma_0$ in $\powf{\Gamma}$,
then $\Gamma\modsim$ generates a proper filter of $\str C\modsim$,
and so $\Gamma\modsim$ is included in a prime filter $F$, and then
\begin{equation*}
F\in\bigcap_{\sigma\in\Gamma}[\sigma].
\end{equation*}
Thus
(except it may not be Hausdorff)
$\Sto{\str C\modsim}$ is a compactification of $\{\Th a\colon a\in\bm A\}$.
But the latter space can be any Kolmogorov space.
In particular, it need not be compact.

\chapter{Compactness Proved}

Suppose $\Gamma\included\Sen$ and is \textbf{consistent,} that is, every finite subset has a model.
Why has $\Gamma$ a model?

Skolem's approach (1922\nocite{Skolem-some-remarks}),
developed by G\"odel (1930\nocite{Goedel-compl}),
and then by Mal${}'$cev (1936\nocite{Maltsev-1936}, 1941\nocite{Maltsev-1941})
for the uncountable case, is first to show that,
by adjusting $\sig$, we may assume
\begin{compactitem}
\item
the sentences of $\Gamma$ are in \textbf{Skolem normal form,}
that is, prenex $\forall\exists$ form;
\item
$\sig$ contains no operation symbols.
\end{compactitem}
If a sentence
\begin{equation*}
\Forall{x_0}\cdots\;\Forall{x_{m-1}}\Exists{y_0}\cdots\;\Exists{y_{n-1}}\phi
\end{equation*}
has a model, then
\begin{compactitem}
\item
some structures with universe $n+1$, that is, $\{0,\dots,n\}$, are models of
\begin{equation*}
\Exists{\vec y}\phi(0,\dots,0,\vec y);
\end{equation*}
\item
some of these embed in structures with universe $2n+1$ that are also models of
\begin{equation*}
\Exists{\vec y}\phi(1,0,\dots,0,\vec y);
\end{equation*}
\item
some of these embed in structures with universe $3n+1$ that are also models of
\begin{equation*}
\Exists{\vec y}\phi(1,1,0,\dots,0,\vec y);
\end{equation*}
\item
and so on.
\end{compactitem}
Thus we obtain an infinite, finitely branching tree of structures.
By K\"onig's Lemma (1926),
this tree has an infinite branch, whose union has universe $\upomega$
and is a model of each sentence
\begin{equation*}
\Exists{\vec y}\phi(a_0,\dots,a_{m-1},\vec y);
\end{equation*}
therefore it is a model of $\Forall{\vec x}\Exists{\vec y}\phi$.
Similarly we obtain a model of any consistent set of sentences,
though the uncountable case will use the Axiom of Choice.

But suppose we do not want to change $\sig$.
We say that $\Gamma$
\begin{compactitem}
\item
is \textbf{complete} if it is consistent and, for all $\sigma$ in $\Sen$, contains $\sigma$ or $\lnot\sigma$;
\item
\textbf{has witnesses} if for every $\phi$ in $\Fm(x)$ (the set of formulas of $\sig$ whose only free variable is $x$),
for some constant symbol $c$ of $\sig$,
\begin{equation*}
\Gamma\proves\Exists x\phi\lto\phi(c).
\end{equation*}
\end{compactitem}
If it exists, a \textbf{canonical model} of $\Gamma$ has universe consisting of the interpretations of the constant symbols of $\sig$.

\begin{theorem}[Henkin 1949\protect{\nocite{MR0033781}}]
A complete subset of $\Sen$ with witnesses has a canonical model.
\end{theorem}

\begin{corollary}[Mal${}'$cev 1941]
The Compactness Theorem
follows is a consequence of the Prime Ideal Theorem.%%%%%
\footnote{I cite Mal${}'$cev as being the first to state the Compactness Theorem in full generality.
I don't know that he referred to the Prime Ideal specifically; probably he did not.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{corollary}

\begin{proof}[Proof (Henkin).]
Given the consistent subset $\Gamma$ of $\Sen$,
we can obtain a set $C$ of new constant symbols
and a bijection
\begin{equation*}
\phi\mapsto c_{\phi}
\end{equation*}
from $\Fm[\sig(C)](x)$ to $C$.%%%%%
\footnote{I originally had the bijection from $\Fm(x)$ to $C$,
but then recognized out loud that this was not quite right.
One will obtain $C$ as a disjoint union $\bigcup_{n\in\upomega}C_n$, 
with bijections from
 $\Fm(x)$ to $C_0$,
and  $\Fm[\sig(C_0)](x)\setminus\Fm(x)$ to $C_1$,
and
$\Fm[\sig(C_{n+1})](x)\setminus\Fm[\sig(C_n)](x)$ to $C_{n+2}$.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Now let
\begin{equation*}
\Gamma^*=\Gamma\cup\{\Exists x\phi\lto\phi(c_{\phi})\colon\phi\in\Fm[\sig(C)](x)\}.
\end{equation*}
This is consistent and has witnesses,
and the same is true of any complete subset of $\Sen[\sig(C)]$ that includes $\Gamma^*$.
Such complete sets exist, by Lindenbaum's Theorem (on which there will be a tutorial);
this theorem follows from the Prime Ideal Theorem.
\end{proof}

The converse is true by Henkin (1954\nocite{MR0063325}).

Another corollary of the Canonical Model Theorem is

\begin{los}[1955\nocite{MR0075156}]
Given a signature $\sig$ and an index set $I$, suppose
\begin{compactitem}
\item
$(\str A_i\colon i\in I)\in\Str{}^I$;
\item
$A=\prod_{i\in I}A_i$;
\item
for each $i$ in $I$, $\str A_i{}^*$ is the expansion of $\str A_i$ to $\sig(A)$ such that
\begin{equation*}
a=(a_j\colon j\in I)\implies a^{\str A_i{}^*}=a_i;
\end{equation*}
\item
$\mathscr U$ is a prime filter, or \textbf{ultrafilter,} of $\pow I$, that is,
\begin{align*}
\emptyset&\notin\mathscr U,&
I&\in\mathscr U,&
X\cup Y\in\mathscr U&\iff X\in\mathscr U\Or Y\in\mathscr U;
\end{align*}
\item
for each $\sigma$ in $\Sen[\sig(A)]$,
\begin{equation*}
\bv{\sigma}=\{i\in I\colon\str A_i{}^*\models\sigma\};
\end{equation*}
\item
$T=\{\sigma\in\Sen[\sig(A)]\colon\bv{\sigma}\in\mathscr U\}$.
\end{compactitem}
By the Axiom of Choice,
$T$ has a canonical model,
which is called the \textbf{ultraproduct} of $(\str A_i\colon i\in I)$ with respect to $\mathscr U$.
\end{los}

\begin{proof}
$T$ is consistent because%%%%%
\footnote{Running out of time,
I did not write down arguments for consistency and completeness.}
%%%%%%%%%%%%%%%%%%%%%
\begin{gather*}
\sigma\in T\implies\bv{\sigma}\in\mathscr U\implies\bv{\sigma}\neq\emptyset,\\
X\in\mathscr U\And Y\in\mathscr U\implies X\cap Y\in\mathscr U,\\
\bv{\sigma}\cap\bv{\tau}=\bv{\sigma\land\tau}.
\end{gather*}
Then $T$ is complete because
\begin{gather*}
X\notin\mathscr U\iff I\setminus X\in\mathscr U,\\
I\setminus\bv{\sigma}=\bv{\lnot\sigma}.
\end{gather*}
Finally, $T$ has witnesses because if $\phi\in\Fm[\sig(A)](x)$,
then by the Axiom of Choice
there is $a$, namely $(a_i\colon i\in I)$, in $A$ such that
\begin{equation*}
\str A_i{}^*\models\Exists x\phi\iff\str A_i{}^*\models\phi(a_i)\iff\str A_i{}^*\models\phi(a),
\end{equation*}
and thus
\begin{gather*}
\bv{\Exists x\phi}=\bv{\phi(a)},\\
\bv{\Exists x\phi\lto\phi(a)}=I,\\
T\models\Exists x\phi\lto\phi(a).\qedhere
\end{gather*}
\end{proof}

\begin{theorem}[Halpern \&\ Levy, 1971\nocite{MR0284328}]
The Prime Ideal Theorem does not imply the Maximal Ideal Theorem.
\end{theorem}

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

Thus \L o\'s's Theorem is stronger than the Compactness Theorem.
To prove the latter from the former,
suppose every finite subset $\Delta$ of $\Gamma$ has a model $\str A_{\Delta}$
(here we use the Axiom of Choice).
Then there is an ultraproduct of $(\str A_{\Delta}\colon\Delta\in\powf{\Gamma})$ 
that is a model of $\Gamma$.
Indeed,%%%%% 
\footnote{I did not have time to write down the details.}
%%%%%%%%%%%%%
if we let
\begin{equation*}
[\Delta]=\{\Theta\in\powf{\Gamma}\colon\Delta\included\Theta\},
\end{equation*}
then
\begin{equation*}
[\Delta]\cap[\Theta]=[\Delta\cup\Theta],
\end{equation*}
so the $[\Delta]$ generate a proper filter of $\pow{\powf{\Gamma}}$.
This filter is therefore included in an ultrafilter,
which yields the desired ultraproduct.

In case $\Gamma=\{\sigma_k\colon k\in\upomega\}$, we get
\begin{equation*}
\Mod{\sigma_0}\includes\Mod{\sigma_0\land\sigma_1}\includes\Mod{\sigma_0\land\sigma_1\land\sigma_2}\includes\cdots
\end{equation*}
as in the Cantor Intersection Theorem.

\AfterBibliographyPreamble{\relscale{0.9}}

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

\def\cprime{$'$}
\begin{thebibliography}{10}

\bibitem{Chang--Keisler}
C.~C. Chang and H.~J. Keisler.
\newblock {\em Model theory}.
\newblock North-Holland Publishing Co., Amsterdam, third edition, 1990.
\newblock First edition 1973.

\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{MR0159773}
Richard Dedekind.
\newblock {\em Essays on the Theory of Numbers. {I}: {C}ontinuity and
  Irrational Numbers. {II}: {T}he Nature and Meaning of Numbers}.
\newblock authorized translation by Wooster Woodruff Beman. Dover Publications
  Inc., New York, 1963.

\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{MR0063325}
L.~Henkin.
\newblock Boolean representation through propositional calculus.
\newblock {\em Fund. Math.}, 41:89--96, 1954.

\bibitem{MR0033781}
Leon Henkin.
\newblock The completeness of the first-order functional calculus.
\newblock {\em J. Symbolic Logic}, 14:159--166, 1949.

\bibitem{MR533327}
Wilfrid Hodges.
\newblock Krull implies {Z}orn.
\newblock {\em J. London Math. Soc. (2)}, 19(2):285--287, 1979.

\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{MR3248511}
Christopher Hollings.
\newblock Embedding semigroups in groups: not as simple as it might seem.
\newblock {\em Arch. Hist. Exact Sci.}, 68(5):641--692, 2014.

\bibitem{MR12:397m}
Edmund Landau.
\newblock {\em Foundations of Analysis. {T}he Arithmetic of Whole, Rational,
  Irrational and Complex Numbers}.
\newblock Chelsea Publishing Company, New York, N.Y., third edition, 1966.
\newblock Translated by F. Steinhardt; first edition 1951; first German
  publication, 1929.

\bibitem{MR0075156}
Jerzy {\L}o{\'s}.
\newblock Quelques remarques, th\'eor\`emes et probl\`emes sur les classes
  d\'efinissables d'alg\`ebres.
\newblock In {\em Mathematical interpretation of formal systems}, pages
  98--113. North-Holland Publishing Co., Amsterdam, 1955.

\bibitem{Maltsev-1941}
Anatoli{\u\i}~Ivanovi{\v{c}} Mal{\cprime}cev.
\newblock A general method for obtaining local theorems in group theory.
\newblock In {\em The metamathematics of algebraic systems. {C}ollected papers:
  1936--1967\/} \cite{MR0349383}, chapter~2, pages 15--21.
\newblock First published in Russian in 1941.

\bibitem{Maltsev-1936}
Anatoli{\u\i}~Ivanovi{\v{c}} Mal{\cprime}cev.
\newblock Investigations in the realm of mathematical logic.
\newblock In {\em The metamathematics of algebraic systems. {C}ollected papers:
  1936--1967\/} \cite{MR0349383}, chapter~1, pages 1--14.
\newblock First published in German in 1936.

\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{Peano}
Giuseppe Peano.
\newblock The principles of arithmetic, presented by a new method.
\newblock In van Heijenoort \cite{MR1890980}, pages 83--97.
\newblock First published 1889.

\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 Lawrence~M. Graves et~al., editors, {\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.
\newblock Held at Harvard University, Cambridge, Massachusetts.

\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{WittgensteinTLP}
Ludwig Wittgenstein.
\newblock {\em Tractatus Logico-Philosophicus}.
\newblock Routledge, London, 1922.

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




