\documentclass[twoside,a4paper,12pt,draft]{article} %\documentclass[draft]{amsart} \usepackage{amssymb,amsmath,amsthm} \usepackage{amscd} % commutative diagram %\usepackage{fullpage} %\setlength{\parindent}{0pt} %\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex} \title{Model-Theory to Compactness} \author{David Pierce} %\address{Department of Mathematics \\ %Middle East Technical University\\Ankara, Turkey} %\email{pierced@member.ams.org} %\subjclass{} \date{\today} \pagestyle{myheadings} \markboth{Model-Theory to Compactness}{David Pierce, \today} \newcommand{\Z}{\mathbf Z} % the integers \newcommand{\Q}{\mathbf Q} % the rationals %\newcommand{\A}{\mathbf A} % affine space \newcommand{\R}{\mathbf R} % the reals \newcommand{\N}{\mathbf{N}} % the naturals %I don't like the standard loose inequalities \renewcommand{\leq}{\leqslant} \renewcommand{\nleq}{\nleqslant} \renewcommand{\geq}{\geqslant} %I don't much like the standard here either: \renewcommand{\setminus}{-} %I don't want epsilon to look like `is an element of' \renewcommand{\epsilon}{\varepsilon} \newcommand{\To}{\longrightarrow} \newcommand{\mapset}[2]{#2^{#1}} \newcommand{\Mod}{\mathfrak{Mod}} \DeclareMathOperator{\Th}{Th} \newcommand{\pow}{\mathcal{P}} \newcommand{\K}{\mathcal{K}} \newcommand{\arity}[1]{\textrm{arity}(#1)} \newcommand{\proj}{\pi} \newcommand{\inv}{^{-1}} \newcommand{\Fm}[1]{\textrm{Fm}^{#1}} \newcommand{\Fmo}[1]{\textrm{Fm}^{#1}_0} \newcommand{\2}{\mathbf{F}_2} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\elsub}{\preccurlyeq} \newcommand{\Ba}{\mathcal{M}^\mathrm{a}} % a Boolean algebra \newcommand{\Br}{\mathcal{M}^\mathrm{r}} % a Boolean ring \DeclareMathOperator{\diag}{diag} % Robinson diagram of a structure \DeclareMathOperator{\sgn}{sgn} % signum of a permutation \newcommand{\included}{\subseteq} % the name suggests the meaning here \newcommand{\lang}{\mathcal L} % a language \newcommand{\SL}{\mathrm{PL}} % Propositional (was sentential) logic \newcommand{\pairing}[1]{\langle#1\rangle} % pairing \newtheorem*{theorem}{Theorem} \newtheorem*{lemma}{Lemma} \newtheorem*{corollary}{Corollary} \theoremstyle{remark} \newtheorem*{remark}{Remark} \newtheorem*{example}{Example} \newtheorem*{examples}{Examples} % For distinguishing claims made and proved within proofs %\newtheoremstyle{subclaim}{0pt}{0pt}{\itshape}{}{\bfseries}{}{0em}{} %\theoremstyle{subclaim} %\newtheorem*{claim}{} \newcommand{\tuple}{\mathbf} \newcommand{\reduct}{\overline} % Should the word `modulo' be italicized? \newcommand{\modulo}{\emph{modulo}\ } % To distinguish terms being defined \newcommand{\defn}[1]{{\bf#1}} \begin{document} %\begin{abstract} %Some notes on the basics of model theory. %\end{abstract} \maketitle \tableofcontents \newpage \setcounter{section}{-1} \section{Introduction} These notes are an attempt to develop model theory, as economically as possible, on a foundation of some familiarity with algebraic structures. References include \cite{Chang--Keisler}, \cite{Hodges} and \cite{Poizat}. \section{The natural numbers} By one standard definition, the set $\omega$ of \defn{natural numbers} is the smallest set that contains the empty set and that contains $x\cup\{x\}$ whenever it contains $x$. The empty set will be denoted $0$ here, and $x\cup\{x\}$, the \defn{successor} of $x$, can be denoted $x'$. The triple $(\omega,{}',0)$ will turn out to be an example of a \emph{structure}. Throughout these notes, $n$ will be a natural number, understood as the set $\{0,1,2,\dots,n-1\}$, possibly empty; and $i$ will range over the elements of this set. Also $m$ will be a natural number. \section{Cartesian powers} Let $M$ be a set. The \defn{Cartesian power} $M^n$ is the set of functions from $n$ to $M$. Such a function will be denoted by a boldface letter, as $\tuple a$, but then its value $\tuple a(i)$ at $i$ will be denoted $a_i$. The function $\tuple a$ can be identified with the \defn{$n$-tuple} $(a_0,\dots,a_{n-1})$ of its values. In particular, the power $M^0$ has but a single member, $0$; hence $M^0=1$. This is so, even if $M=0$; however, $0^n=0$ when $n$ is \emph{positive} (different from $0$). The set $M$ itself can be identified with the power $M^1$. Any function $f:m\to n$ determines the map \begin{equation*} \tuple a\mapsto(a_{f(0)},\dots,a_{f(m-1)}):M^n\to M^m, \end{equation*} no matter what set $M$ is. In case $m=1$, we have the \defn{coordinate projections} $\tuple a\mapsto a_i$. The \defn{Cartesian product} $A\times B$ of sets $A$ and $B$ is identified with the set of (ordered) pairs $(a,b)$ such that $a\in A$ and $b\in B$. There is a map \begin{align*} M^n\times M^m & \To M^{n+m} \\ (\tuple a,\tuple b) & \longmapsto(a_0,\dots,a_{n-1},b_0,\dots,b_{m-1}), \end{align*} often considered an identification. \section{Structures and signatures} A \defn{function on} the set $M$ is a map $M^n\to M$; the function then is \defn{$n$-ary}---its \defn{arity} is $n$. A nullary (that is, $0$-ary) function is a \defn{constant} and can be identified with an element of $M$. An \defn{$n$-ary relation on} $M$ is a subset of $M^n$. There are two nullary relations, namely $0$ and $1$. The relation of \emph{equality} is binary ($2$-ary). A \defn{structure} is a set equipped with some distinguished constants and with some functions and relations of various positive arities. The set then is the \defn{universe} of the structure. If the universe is $M$, then the structure might be denoted $\mathcal M$ or just $M$ again. However, the structure $(\omega,{}',0)$ is denoted $\N$. (This structure is often considered to contain the binary functions of addition and multiplication as well, but these are uniquely determined by the successor-function.) \begin{examples} A set with no distinguished relations, functions or constants is trivially a structure. Groups, rings and partially ordered sets are structures. A vector space is a structure whose unary functions are the multiplications by the scalars. A valued field can be understood as a structure when the valuation ring is distinguished as a unary relation. \end{examples} The \defn{signature} of a structure contains a \defn{symbol} for each function, relation and constant in the structure; the function, relation or constant is then the \defn{interpretation} of the symbol. Notationally, the symbols are primary; their interpretations can be distinguished, if need be, by superscripts indicating the structure. \begin{examples} The complete ordered field $\R$ has the signature $\{+, -, \cdot, \leq, 0, 1\}$. The ordered field $\Q$ of rational numbers has the same signature. The binary function-symbol $+$ is interpreted in $\R$ by addition of real numbers; the interpretation is also denoted by $+$, or by $+^{\R}$ if it should be distinguished from addition $+^{\Q}$ of rational numbers. To make its signature explicit, we can write $\R$ as the tuple $(\R, +, -, \cdot, \leq, 0, 1)$. \end{examples} Throughout these notes, $\lang$ will be a signature, and $f$, $R$ and $c$ will range respectively over the function-, relation- and constant-symbols in $\lang$. The structures with signature $\lang$ compose the class $\Mod(\lang)$. \section{Homomorphisms and embeddings} Suppose $M$ and $N$ are in $\Mod(\lang)$, and $h$ is a map $M\to N$. (So, $N$ must be nonempty, unless $M$ is empty.) Then $h$ induces maps $M^n\to N^n$ in the obvious way, even when $n=0$; so, $h(\tuple a)(i)=h(a_i)$, and $h(0)=0$. The map $h$ is a \defn{homomorphism} if it \emph{preserves} the functions, relations and constants symbolized in $\lang$, that is, \begin{itemize} \item $h(f^M(\tuple a))=f^N(h(\tuple a))$; \item $h(\tuple a)\in R^N$ when $\tuple a\in R^M$; \item $h(c^M)=c^N$. \end{itemize} Any map preserves \emph{equality}. A homomorphism is an \defn{embedding} if it preserves both inequality and the complements of the relations symbolized in $\lang$. \begin{examples} A group-homomorphism is a homomorphism of groups; a group-mono\-morphism is an embedding of groups. The zero-map on the ordered field $\R$ can be seen as a homomorphism, but not an embedding. (It would not even be a homomorphism if the signature of an ordered ring contained $<$ instead of $\leq$.) \end{examples} \section{Boolean algebras} An essential and notationally exceptional example is the \emph{Boolean algebra} of subsets of a nonempty set $\Omega$; this structure is the tuple \begin{equation*} (\pow(\Omega),\cap,\cup,{}^c,\emptyset,\Omega), \end{equation*} but we shall consider the signature of Boolean algebras to be the set \begin{equation*} \{\land,\lor,\lnot,0,1\}. \end{equation*} A \defn{Boolean ring} is a (unital) ring in which every element is idempotent, that is, satisfies \begin{equation*} x^2=x. \end{equation*} In particular, in such a ring we have $(x+y)^2=x+y$, whence \begin{equation*} xy+yx=0; \end{equation*} replacing $y$ with $x$, we get $2x=0$, so every element is its additive inverse; hence also $xy=yx$, so the ring is commutative. We have $x(1+x)=0$, so if $x$ is a unit, then $1+x=0$, so $x=1$. Thus also every nonzero nonunit of a Boolean ring is a zero-divisor. Hence the only Boolean integral domain is the two-element ring $\{0,1\}$ or $\2$, and this is a field. Therefore prime ideals of Boolean rings are maximal, since the quotient of a Boolean ring by an ideal is Boolean. A structure $(M,\land,\lor,\lnot,0,1)$---call it $\Ba$---in the signature of Boolean algebras determines a structure $\Br$ with the same universe in the signature of rings: This structure $\Br$---that is, $(M,+,\cdot,0,1)$---is given by the rules \begin{align*} x+y & =(x\land\lnot y)\lor(y\land\lnot x), \\ x y & =x\land y \end{align*} and the rule that $0$ and $1$ have the same interpretation in each structure. The structure $\Ba$ is a \defn{Boolean algebra} just in case $\Br$ is a Boolean ring. Any Boolean ring $(M,+,\cdot,0,1)$ is determined in this way by the Boolean algebra $(M,\land,\lor,\lnot,0,1)$ such that \begin{align*} x\land y & = x y, \\ x\lor y & =x+y+xy, \\ \lnot x & =1+ x. \end{align*} A Boolean algebra has a partial order $\leq$ such that \begin{equation*} x\leq y\iff x\land y=x. \end{equation*} An \defn{ideal} of a Boolean algebra is just an ideal of the corresponding ring. A \defn{filter} of a Boolean algebra is \emph{dual} to an ideal, so $F$ is a filter just in case $\{\lnot x:x\in F\}$ is an ideal. An \defn{ultrafilter} is dual to a maximal ideal. So, $F$ is a filter just in case \begin{align*} & 1\in F,\\ & x,y\in F\implies x\land y\in F, \\ & x\in F \text{ and } x\leq y\implies y\in F, \\ & 0\notin F; \end{align*} also, a filter $F$ is an ultrafilter just in case \begin{equation*} x\lor y\in F \implies x\in F\text{ or } y\in F, \end{equation*} equivalently, $x\notin F\implies \lnot x\in F$. The set of ultrafilters of a Boolean algebra is the \defn{Stone-space} of the algebra. For every element $x$ of a Boolean algebra, the corresponding Stone-space has a subset $[x]$ comprising the ultrafilters containing $x$. Then \begin{equation*} [x]\cap[y]=[x\land y] \end{equation*} since the elements of these sets are filters; since they are ultrafilters, we have also \begin{align*} [x]\cup[y] & =[x\lor y], \\ [x]^c & =[\lnot x]. \end{align*} Finally, $[1]$ is the whole Stone-space, and $[0]$ is empty. Therefore the map \begin{equation*} x\longmapsto[x] \end{equation*} is a homomorphism of Boolean algebras; it is an embedding, since $[x]$ is nonempty when $x\neq0$. Since the collection of sets $[x]$ contains the whole Stone-space and the empty set and is closed under finite unions, it is a \defn{basis} for the \defn{closed} sets of a \defn{topology} for the Stone-space. By definition then, every closed subset is an intersection of some closed sets $[x]$. These basic closed sets are also open---they are \defn{clopen}. The topology is \defn{Hausdorff}, since distinct points are respectively contained in some disjoint sets $[x]$ and $[\lnot x]$. Suppose $B$ is a subset of a Boolean algebra. Then the following are equivalent: \begin{itemize} \item the collection $\{[x]:x\in B\}$ has the \defn{finite-intersection property}, meaning any finite sub-collection has nonempty intersection; \item the set $B$ generates a filter of the algebra; \item $B$ included in an ultrafilter of this algebra; \item $\{[x]:x\in B\}$ has nonempty intersection. \end{itemize} That the first condition implies the last means that the topology of the Stone-space is \defn{compact}. Consequently, every clopen set is one of the sets $[x]$. Of the nonempty set $\Omega$, we can see the Boolean ring $\pow(\Omega)$ of its subsets as a compact \defn{topological ring}. For, we can identify any subset $A$ of $\Omega$ with its \defn{characteristic function}, the map from $\Omega$ to $\2$ taking $x$ to $1$ just in case $x\in A$. The set of such maps can be denoted $\mapset{\Omega}{\2}$. With the \defn{discrete} topology, in which every subset is closed, $\2$ is a compact topological ring. Therefore on $\mapset{\Omega}{\2}$ is induced a ring-structure and a compatible topology---the \defn{product}-topology or topology of \defn{pointwise convergence}, compact in this case since $\2$ is compact. The induced ring-structure makes the bijection from $\pow(\Omega)$ to $\mapset{\Omega}{\2}$ a homomorphism. In the induced topology, every finite subset of $\Omega$ determines for the zero-map on $\Omega$ an open neighborhood, comprising those maps into $\2$ that are zero on that finite subset. Translating such a neighborhood by an element of $\mapset{\Omega}{\2}$ gives an open neighborhood of that element, and every open subset of $\mapset{\Omega}{\2}$ is a union of such neighborhoods; the finite unions are precisely the clopen subsets. \section{Functions and terms} Suppose $M$ is in $\Mod(\lang)$. Various functions on $M$ can be derived, by composition, from: \begin{itemize} \item the functions $f^M$, \item the constants $c^M$, and \item the coordinate projections. \end{itemize} These compositions can be described without reference to $M$; the result is the \defn{terms} of $\lang$. The \defn{interpretation} in $M$, or $t^M$, of an $n$-ary term $t$ of $\lang$ will be an $n$-ary function on $M$. Terms can be defined precisely as follows: \begin{itemize} \item Each constant-symbol $c$ is also an $n$-ary term whose interpretation is the constant map $\tuple a\mapsto c^M$ on $M^{n}$. \item There is an $n$-ary term $x_i$ whose interpretation is the coordinate projection $\tuple a\mapsto a_i$ on $M^n$. \item If $t_0$, \dots, $t_{n-1}$ are $m$-ary terms, and $f$ is $n$-ary, then there is an $m$-ary term $f(t_0,\dots,t_{n-1})$ whose interpretation is the map \begin{equation*} \tuple a\mapsto f^M(t_0^M(\tuple a),\dots, t_{n-1}^M(\tuple a)). \end{equation*} \end{itemize} By this account, an $n$-ary term is also $n+1$-ary. The nullary terms are the \defn{constant} terms. \begin{lemma} If $t$ is an $n$-ary term, and $u_0$, \dots, $u_{n-1}$ are $m$-ary terms, then there is an $m$-ary term whose interpretation in $M$ is the map \begin{equation*} \tuple a\mapsto t^M(u_0^M(\tuple a),\dots,u_{n-1}^M(\tuple a)). \end{equation*} \end{lemma} The new term in the lemma can of course be denoted $t(u_0,\dots,u_{n-1})$. We can identify terms whose interpretations are indistinguishable in every structure. In particular, if $t$ is $n$-ary, but not $(n-1)$-ary, then $t$ is precisely $t(x_0,\dots,x_{n-1})$, which we may abbreviate as $t(\tuple x)$. If $A$ is a subset of $M$, we let $\lang(A)$ be the signature $\lang$ augmented with a constant-symbol for each element of $A$. The symbols and the elements are generally not distinguished notationally, and an $\lang$-structure $M$ naturally determines an $\lang(A)$-structure, denoted $M_A$ if there is a need to distinguish. \begin{lemma} Every term of $\lang(A)$ is $t(\tuple a,\tuple x)$ for some term $t$ of $\lang$ and tuple $\tuple a$ from $A$. \end{lemma} \section{Propositional logic} The terms in the signature of Boolean algebras---the \defn{Boolean terms}---can be considered as strings of symbols generated by the following rules: \begin{itemize} \item each constant-symbol $0$ or $1$ is a term; \item each symbol $x_i$ for a coordinate projection is a term; \item if $t$ and $u$ are terms, then so are $(t\land u)$ and $(t\lor u)$ and $\lnot t$. \end{itemize} A term here is $n$-ary just in case $i0$, then $f$ is the interpretation of \begin{equation*} t^0\lor\dots\lor t^{m-1}, \end{equation*} where $t^j$ is $u_0^j\land\dots u_{n-1}^j$, where $u_i^j$ is $x_i$, if $a_i^j=1$, and otherwise is $\lnot x_i$. \end{proof} The Boolean terms can be considered as the \emph{propositional formulas} composing a \emph{propositional logic}---call it $\SL$. The constant-symbols $0$ and $1$ can then be taken to stand for \defn{false} and \defn{true} statements, respectively; an element of $\mapset{\omega}{\2}$ is a \defn{truth-assignment} to the \defn{propositional variables} $x_i$, and under such an assignment $\sigma$, a propositional formula $t$ takes on the \defn{truth-value} \begin{equation*} t^{\2}(\sigma(0),\dots,\sigma(n-1)) \end{equation*} if $t$ is $n$-ary. Write $\pairing{\sigma,t}$ for the truth-value of $t$ under $\sigma$. A \emph{model} for a set of propositional formulas is a truth-assignment $\sigma$ sending the set to $1$ under the map $t\mapsto\pairing{\sigma,t}$. \begin{theorem}[Compactness for sentential logic] A set of propositional formulas has a model if each finite subset does. \end{theorem} \begin{proof} If a set of sentences $t$ satisfies the hypothesis, then the collection of closed subsets $\{\sigma:\pairing{\sigma,t}=1\}$ of $\mapset{\omega}{\2}$ has the finite-intersection property. \end{proof} The sets $\{\sigma:\pairing{\sigma,t}=1\}$ are precisely the clopen subsets of $\mapset{\omega}{\2}$. \section{Relations and formulas} From the relations $R^M$ and the interpretations $t^M$ of terms $t$, new relations on $M$ can be derived by various techniques. These relations will be the \defn{$0$-definable} relations of $M$, and each of them will be the interpretation of a \defn{formula} of $\lang$. (The \defn{definable} relations of $M$ are the interpretations of formulas of $\lang(M)$.) Distinctions are made according to which techniques are needed to derive the relations. The \defn{atomic} formulas are given thus: \begin{itemize} \item If $t_0$ and $t_1$ are $n$-ary terms, then there is an $n$-ary atomic formula $t_0=t_1$ whose interpretation $(t_0=t_1)^M$ is $\{\tuple a\in M^n:t_0^M(\tuple a)=t_1^M(\tuple a)\}$. \item If $t_0$, \dots, $t_{n-1}$ are $m$-ary terms, and $R$ is $n$-ary, then there is an $m$-ary atomic formula $R(t_0,\dots,t_{n-1})$ whose interpretation $R(t_0,\dots,t_{n-1})^M$ is $\{\tuple a\in M^m:(t_0^M(\tuple a),\dots,t_{n-1}^M(\tuple a))\in R^M\}$. \end{itemize} (In particular, $R(x_0,\dots,x_{n-1})^M=R^M$.) If $t$ is an $m$-ary Boolean term, and $\phi_0$, \dots, $\phi_{n-1}$ are $n$-ary atomic formulas, then there is an $n$-ary \defn{basic} or \defn{quantifier-free} formula, say $t(\phi_0,\dots,\phi_{n-1})$, whose interpretation is \begin{equation*} t^{\pow(M^n)}(\phi_0^M,\dots,\phi_{n-1}^M). \end{equation*} If we identify formulas with indistinguishable interpretations in every structure, then the set of basic formulas is a Boolean algebra generated by the atomic formulas. The set of \defn{formulas} is the smallest Boolean algebra containing the atomic formulas and closed under the operation converting an $n+1$-ary formula $\phi$ into an $n$-ary formula $\exists x_n\,\phi$ whose interpretation is the image of $\phi^M$ under the map \begin{equation*} (a_0,\dots,a_n)\mapsto(a_0,\dots,a_{n-1}):M^{n+1}\to M^n. \end{equation*} The Boolean algebra of $n$-ary formulas of $\lang$ can be denoted $\Fm{n}(\lang)$. The formula $\lnot\exists x_n\,\phi$ is also denoted $\forall x_n\,\lnot\phi$, and $\lnot\phi\lor\psi$ is denoted $\phi\to\psi$. If $\phi$ is an $n$-ary formula, and $t_0$, \dots, $t_{n-1}$ are $m$-ary terms, then there is an $m$-ary formula $\phi(t_0,\dots,t_{n-1})$ with the obvious interpretation; in particular, if it is not also $(n-1)$-ary, then $\phi$ is the same as the formula $\phi(x_0,\dots,x_{n-1})$. The $A$-definable relations of $M$ are the interpretations in $M$ of formulas of $\lang(A)$. In particular, they are the sets $\phi(a_0,\dots,a_{m-1},x_0,\dots,x_{n-1})^M$, where $\phi$ is an $m+n$-ary formula of $\lang$, and $\tuple a$ is a tuple from $A$. \defn{Sentences} are $0$-ary formulas. \section{Substructures} Suppose $M$ and $N$ are members of $\Mod(\lang)$. We can now say that an embedding of $M$ in $N$ is a map $h:M\to N$ such that \begin{equation*} h\inv(\phi^N)=\phi^M \end{equation*} for all basic formulas $\phi$ of $\lang$; if the same holds for \emph{all} formulas $\phi$ of $\lang$, then $h$ is an \defn{elementary embedding}. If the universe of $N$ includes the universe of $M$, and the inclusion-map is an embedding, we say $M$ is a \defn{substructure} of $N$ and write \begin{equation*} M\included N; \end{equation*} if the inclusion-map is an elementary embedding, we write \begin{equation*} M\elsub N \end{equation*} and say $M$ is an \defn{elementary} substructure of $N$. \begin{lemma}[Tarski--Vaught] Suppose $M\included N$. Then $M\elsub N$, provided that \begin{equation*} \phi(\tuple a,x_0)^N\cap M \end{equation*} is nonempty whenever $\phi(\tuple a,x_0)^N$ is, for all $\lang$-formulas $\phi$ and all tuples $\tuple a$ from $M$. \end{lemma} \begin{proof} Let $\Sigma$ comprise the formulas $\phi$ such that \begin{equation*} \phi(x_0,\dots,x_{n-1})^M=\phi(x_0,\dots,x_{n-1})^N\cap M^n.\tag{$*$} \end{equation*} Then $\Sigma$ contains all the basic formulas and is closed under the Boolean operations. Suppose $\phi$ is in $\Sigma$ and $\tuple a$ is in $M^n$. Then \begin{equation*} \phi(\tuple a,x_0)^M=\phi(\tuple a,x_0)^N\cap M. \end{equation*} By hypothesis then, $\phi(\tuple a,x_0)^M$ and $\phi(\tuple a,x_0)^N$ are alike empty or not. Hence $(*)$ holds, \emph{mutatis mutandis}, with $\exists x_{n-1}\phi$ in place of $\phi$. Therefore $\Sigma=\Fm{}(\lang)$. \end{proof} \section{Models and theories} Suppose $\phi$ is an $n$-ary formula of $\lang$, and $\tuple a$ is an $n$-tuple of elements of $M$, so that $\phi(\tuple a)$ is a sentence of $\lang(M)$. We write \begin{equation*} M\models\phi(\tuple a) \end{equation*} if $\phi(\tuple a)^M=1$, equivalently, $\tuple a\in\phi^M$. The map $h:M\to N$ is an elementary embedding just in case \begin{equation*} M\models\phi(\tuple a)\iff N\models\phi(h(\tuple a)) \end{equation*} for all such $\phi$ and $\tuple a$. If $\K$ is a subclass of $\Mod(\lang)$, then the \defn{theory} $\Th(\K)$ of $\K$ is the subset of $\Fm 0(\lang)$ comprising $\sigma$ such that $M\models\sigma$ whenever $M\in \K$; this subset is a filter, if $\K$ is nonempty; otherwise it contains every sentence. In general, a \defn{theory} of $\lang$ is $\Fm 0(\lang)$ or a filter of it; a \defn{consistent} theory is a proper filter; a \defn{complete} theory is an ultrafilter. A \defn{model} of a set $\Sigma$ of sentences is a structure $M$ such that $\Sigma\included\Th(M)$. We write \begin{equation*} \Sigma\models\sigma \end{equation*} if every model of $\Sigma$ is a model of $\sigma$ (that is, of $\{\sigma\}$). We write \begin{equation*} \Sigma\vdash\sigma \end{equation*} if $\sigma$ is in the theory generated by $\Sigma$. If $\Sigma\vdash\sigma$, then $\Sigma\models\sigma$. \section{Compactness} It is a consequence of the following that $\Sigma\vdash\sigma$ if $\Sigma\models\sigma$. \begin{theorem}[Compactness] Every consistent theory has a model. \end{theorem} \begin{proof} Let $T$ be a consistent theory in the signature $\lang$. We shall extend $\lang$ to a signature $\lang'$, and extend $T$ to a complete theory $T'$ of $\lang'$. We shall do this in such a way that, for every unary formula $\phi$ of $\lang'$, there will be a constant-symbol $c_{\phi}$ not appearing in $\phi$ such that \begin{equation*} T'\vdash\exists x_0\,\phi\to\phi(c_{\phi}). \end{equation*} Then $T'$ and the constant-symbols $c_{\phi}$ will determine a structure $M$ in the following way. The universe of $M$ will consist of equivalence-classes $[c_{\phi}]$ of the symbols $c_{\phi}$, where \begin{equation*} [c_{\phi}]=[c_{\psi}]\iff T'\vdash c_{\phi}=c_{\psi}. \end{equation*} Then we require \begin{equation*} \tag{$*$} \phi^M=\{[\tuple c]:T'\vdash\phi(\tuple c)\} \end{equation*} for all basic formulas $\phi$ of $\lang'$ and all tuples $\tuple c$ of symbols $c_{\phi}$. The requirements ($*$) do make sense. In particular, $c_{\phi}^M=[c_{\phi}]$. The requirements determine a well-defined structure, since $T'$ is complete. If $T'$ is as claimed, then ($*$) holds for all formulas $\phi$; we show this by induction. If $\phi$ is an $n$-ary formula, and $[\tuple c]$ is an $(n-1)$-tuple from $M$, let $d$ be the constant-symbol determined by the unary formula $\phi(\tuple c,x_0)$. If ($*$) holds for $\phi$, then we have: \begin{align*} [\tuple c]\in(\exists x_n\,\phi)^M & \implies M\models\phi(\tuple c,[e]),\text{ some $[e]$ in }M \\ & \implies T'\vdash\phi(\tuple c,e) \\ & \implies T'\vdash\exists x_0\,\phi(\tuple c,x_0) \\ & \implies T'\vdash\phi(\tuple c,d) \\ & \implies M\models(\tuple c, [d]) \\ & \implies [\tuple c]\in(\exists x_n\,\phi)^M; \end{align*} so ($*$) holds with $\exists x_n\,\phi$ in place of $\phi$. Once ($*$) holds for all formulas $\phi$, then in particular it holds when $\phi$ is a sentence in $T$; so $M\models T$. It remains to find $T'$ as desired. First we construct a chain $\lang=\lang_0\included\lang_1\included\dots$ of signatures, where $\lang_{n+1}\setminus\lang_n$ consists of a constant-symbol $c_{\phi}$ for each unary formula $\phi$ in $\lang_n$. Taking the union of the chain gives $\lang'$. Now we work in the Stone space of $\Fm 0(\lang')$. We claim that the collection \begin{equation*} \{[\sigma]:\sigma\in T\} \cup \{[\forall x_0\,\lnot\phi\lor\phi(c_\phi)]:\phi\in\Fm 1(\lang')\} \end{equation*} of closed sets has the finite-intersection property; from this, by compactness, we can take $T'$ to be an element of the intersection. To establish the f.i.p., suppose that $[\psi]$ is a nonempty finite intersection of sets in the collection. Then $\psi\in\Fm 0(\lang_n)$ for some $n$. If $\phi\in\Fm 1(\lang')\setminus\Fm 1(\lang_{n-1})$, then $c_{\phi}$ does not appear in $\psi$. If also $[\psi]\cap[\forall x_0\,\lnot\phi]$ is empty, then \begin{equation*} [\psi]\cap[\phi(c_{\phi})] \end{equation*} is nonempty; for, if $M\models\psi\land\exists x_0\,\phi$, then we may assume $M\models\psi\land\phi(c_{\phi})$. \end{proof} \begin{theorem}%[downward L\"{o}wenheim--Skolem] Suppose $N\in\Mod(\lang)$, and $\kappa$ is a cardinal such that \begin{equation*} \aleph_0+\abs{\lang}\leq\kappa\leq\abs{N}. \end{equation*} Then there is $M$ in $\Mod(\lang)$ such that $M\elsub N$ and $\abs{M}=\kappa$. \end{theorem} \begin{proof} Use the proof of Compactness, with $\Th(N)$ for $T$. We can choose $T'$, and we can choose $c_{\phi}^N$ in $N$, so that $N\models T'$. Then we may assume $M\included N$, and so $M\elsub N$ by the Tarski--Vaught test. By construction, $\abs{M}\leq\abs{\lang'}=\aleph_0+\abs{\lang}$. To ensure $M=\kappa$, we first add $\kappa$-many new constant-symbols to $\lang$ and let their interpretations in $N$ be distinct. \end{proof} \begin{example} In the signature $\{\in\}$ of set-theory, any infinite structure has a countably infinite elementary substructure, even though the power-set of an infinite set is uncountable. \end{example} \begin{corollary}%[upward L\"{o}wenheim--Skolem] Suppose $A$ is an infinite $\lang$-structure and $\abs{A}+\abs{\lang}\leq\kappa$. Then there is $M$ in $\Mod(\lang)$ such that $A\elsub M$ and $\abs{M}=\kappa$. \end{corollary} \begin{proof} Let $\{c_{\mu}:\mu<\kappa\}$ be a set of new constant-symbols, and let $T$ be the theory generated by $\Th(A_A)$ and $\{c_{\mu}\neq c_{\nu}:\mu\neq\nu\}$. Use Compactness to get a model $N$ of $T$; then use the last Theorem to get $M$ as desired. \end{proof} \bibliographystyle{plain} \bibliography{../references} \end{document}