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