Model theory

Lindström's Theorem

content/model-theory/lindstrom/lindstrom.tex

% Part: model-theory% Chapter: lindstrom\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{mod}{lin}{Lindstr\"om's Theorem}\olimport{introduction}\olimport{abstract-logics}\olimport{ls-property}\olimport{lindstrom-proof}\OLEndChapterHook\end{document}

content/model-theory/lindstrom/introduction.tex

% Part: first-order-logic% Chapter: lindstrom% Section: introduction\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mod}{lin}{int}\section{Introduction}In this chapter we aim to prove Lindstr\"om's characterization offirst-order logic as the maximal logic for which (given certainfurther constraints) the Compactness and the DownwardL\"owenheim--Skolem theorems hold(\olref[fol][com][com]{thm:compactness} and\olref[fol][com][dls]{thm:downward-ls}). First, we need a more generalcharacterization of the general class of logics to which the theoremapplies. We will restrict ourselves to \emph{relational} languages,i.e., languages which only contain !!{predicate}s and individualconstants, but no !!{function}s.\end{document}

content/model-theory/lindstrom/abstract-logics.tex

% Part: first-order-logic% Chapter: lindstrom% Section: abstract-logics\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mod}{lin}{alg}\olsection{Abstract Logics}\begin{defn}An \emph{abstract logic} is a pair $\tuple{L, \models_L}$, where $L$is a function that assigns to each !!{language}~$\Lang{L}$ a set$L(\Lang{L})$ of !!{sentence}s, and $\models_L$ is a relation between!!{structure}s for the !!{language}~$\Lang{L}$ and !!{element}s of$L(\Lang{L})$. In particular, $\tuple{F, \models}$ is ordinaryfirst-order logic, i.e., $F$ is the function assigning to the!!{language}~$\Lang{L}$ the set of first-order !!{sentence}s built fromthe constants in $\Lang{L}$, and $\models$ is the satisfaction relationof first-order logic.\end{defn}Notice that we are still employing the same notion of !!{structure}for a given !!{language} as for first-order logic, but we do notpresuppose that !!{sentence}s are build up from the basic symbols in$\Lang{L}$ in the usual way, nor that the relation $\models_L$ isrecursively defined in the same way as for first-order logic. So forinstance the definition, being completely general, is intended tocapture the case where !!{sentence}s in $\tuple{L,\models_L}$ containinfinitely long conjunctions or disjunction, or quantifiers other than$\lexists$ and $\lforall$ (e.g., ``there are infinitely many~$x$ suchthat \dots''), or perhaps infinitely long quantifier prefixes. Toemphasize that ``!!{sentence}s'' in $L(\Lang{L})$ need not be ordinary!!{sentence}s of first-order logic, in this chapter we use !!{variable}s $!E$,$!F$,~\dots to range over them, and reserve $!A$, $!B$,~\dots forordinary first-order !!{formula}s.\begin{defn}Let $\Mod(L){!E}$ denote the class $\Setabs{\Struct{M}}{\Struct{M}  \models_L !E}$. If the !!{language} needs to be made explicit, wewrite $\Mod[L](L){!E}$. Two !!{structure}s $\Struct{M}$ and$\Struct{N}$ for $\Lang{L}$ are \emph{elementarily equivalent in}$\tuple{L, \models_L}$, written $\Struct{M} \elemequiv[L] \Struct{N}$, ifthe same !!{sentence}s from $L(\Lang{L})$ are true in each.\end{defn}\begin{defn}An abstract logic $\tuple{L,\models_L}$ for the !!{language} $\Lang{L}$is \emph{normal} if it satisfies the following properties:\begin{enumerate}\item (\emph{$L$-Monotonicity}) For !!{language}s $\Lang{L}$ and  $\Lang{L'}$, if $\Lang{L} \subseteq \Lang{L'}$, then  $L(\Lang{L}) \subseteq L(\Lang{L'})$.\item (\emph{Expansion Property}) For each $!E \in L(\Lang{L})$  there is a \emph{finite} subset $\Lang{L'}$ of $\Lang{L}$ such that  the relation $\Struct{M} \models_L !E$ depends only on the  reduct of $\Struct{M}$ to $\Lang{L'}$; i.e., if $\Struct{M}$ and  $\Struct{N}$ have the same reduct to $\Lang{L'}$ then $\Struct{M}  \models_L !E$ if and only if $\Struct{N} \models_L !E$.\item (\emph{Isomorphism Property}) If $\Struct{M} \models_L !E$  and $\Struct{M} \simeq \Struct{N}$ then also $\Struct{N} \models_L  !E$.\item (\emph{Renaming Property}) The relation $\models_L$ is preserved  under renaming: if the !!{language} $\Lang{L}'$ is obtained from  $\Lang{L}$ by replacing each symbol $P$ by a symbol $P'$ of the same  arity and each constant $c$ by a distinct constant $c'$, then for  each !!{structure}~$\Struct{M}$ and !!{sentence}~$!E$, $\Struct{M}  \models_L !E$ if and only if $\Struct{M}' \models_L !E'$,  where $\Struct{M}'$ is the $\Lang{L}'$-!!{structure} corresponding  to $\Lang{L}$ and $!E' \in L(\Lang{L}')$.\item (\emph{Boolean Property}) The abstract logic $\tuple{L,  \models_L}$ is closed under the Boolean connectives in the sense  that for each $!E \in L(\Lang{L})$ there is a~$!F \in  L(\Lang{L})$ such that $\Struct{M} \models_L !F$ if and only if  $\Struct{M} \not\models_L !E$, and for each $!E$ and $!F$  there is a $!G$ such that $\Mod(L){!G} = \Mod(L){!E} \cap  \Mod(L){!F}$.  Similarly for atomic !!{formula}s and the other  connectives.\item (\emph{Quantifier Property}) For each constant $c$ in $\Lang{L}$  and $!E \in L(\Lang{L})$ there is a $!F \in L(\Lang{L})$ such  that  \[  \Mod[L'](L){!F} = \Setabs{\Struct{M}}{\Expan{M}{a} \in  \Mod[L](L){!E} \text{ for some } a \in \Domain{M}},  \]  where $\Lang{L'} = \Lang{L} \setminus \{c\}$ and $\Expan{M}{a}$  is the expansion of $\Struct{M}$ to $\Lang{L}$ assigning $a$  to~$c$.\item (\emph{Relativization Property}) Given !!a{sentence} $!E \in  L(\Lang{L})$ and symbols $R$, $c_1$, \dots, $c_n$ not in $\Lang{L}$,  there is !!a{sentence} $!F \in L(\Lang{L} \cup \{R,c_1,\ldots,c_n\})$  called the \emph{relativization} of $!E$ to $\Atom{R}{x, c_1, \dots c_n}$,  such that for each !!{structure}~$\Struct{M}$:  \[  \Expan{M}{X, b_1, \ldots, b_n} \models_L !F \text{ if and    only if } \Struct{N} \models_L !E,  \]  where $\Struct{N}$ is the substructure of $\Struct{M}$ with !!{domain}  $\Domain{N} = \Setabs{a\in \Domain{M}}{\Assign{R}{M}(a, b_1, \dots, b_n)}$  (see \olref[bas][sub]{rem:substructure}), and $\Expan{M}{X, b_1, \ldots,    b_n}$ is the expansion of $\Struct{M}$ interpreting $R$, $c_1$,  \dots, $c_n$ by $X$, $b_1,$ \dots, $b_n$, respectively (with $X  \subseteq M^{n+1}$).\end{enumerate}\end{defn} \begin{defn}Given two abstract logics $\tuple{L_1, \models_{L_1}}$ and$\tuple{L_2, \models_{L_2}}$ we say that the latter is \emph{at least  as expressive} as the former, written $\tuple{L_1, \models_{L_1}}\leq \tuple{L_2, \models_{L_2}}$, if for each !!{language} $\Lang{L}$and !!{sentence} $!E \in L_1(\Lang{L})$ there is !!a{sentence} $!F\in L_2(\Lang{L})$ such that $\Mod[L](L_1){!E} =\Mod[L](L_2){!F}$. The logics $\tuple{L_1, \models_{L_1}}$ and$\tuple{L_2, \models_{L_2}}$ are \emph{equivalent} if $\tuple{L_1,  \models_{L_1}} \leq \tuple{L_2, \models_{L_2}}$ and $\tuple{L_2,  \models_{L_2}} \leq \tuple{L_1, \models_{L_1}}$.\end{defn}\begin{rem}  First-order logic, i.e., the abstract logic $\tuple{F, \models}$, is  normal. In fact, the above properties are mostly straightforward for  first-order logic. We just remark that the expansion property comes  down to extensionality, and that the relativization of  !!a{sentence} $!E$ to $\Atom{R}{x, c_1, \dots, c_n}$ is obtained by  replacing each !!{subformula} $\lforall[x][!F]$ by  $\lforall[x][(\Atom{R}{x, c_1, \dots, c_n} \lif \ !F)]$. Moreover,  if $\tuple{L, \models_L}$ is normal, then  $\tuple{F, \models} \leq \tuple{L, \models_{L}}$, as can be can  shown by induction on first-order !!{formula}s. Accordingly, with no  loss in generality, we can assume that every first-order  !!{sentence} belongs to every normal logic.\end{rem}\end{document}

content/model-theory/lindstrom/ls-property.tex

% Part: first-order-logic% Chapter: lindstrom% Section: ls-property\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mod}{lin}{lsp}\olsection{Compactness and L\"owenheim--Skolem Properties}We now give the obvious extensions of compactness andL\"owenheim--Skolem to the case of abstract logics.\begin{defn}An abstract logic $\tuple{L, \models_L}$ has the \emph{Compactness  Property} if each set $\Gamma$ of $L(\Lang{L})$-!!{sentence}s issatisfiable whenever each finite $\Gamma_0 \subseteq \Gamma$ issatisfiable.\end{defn}\begin{defn}$\tuple{L, \models_L}$ has the \emph{Downward L\"owenheim--Skolem  property} if any satisfiable $\Gamma$ has !!a{enumerable} model.\end{defn}The notion of partial isomorphism from\olref[bas][pis]{defn:partialisom} is purely ``algebraic'' (i.e.,given without reference to the !!{sentence}s of the language but onlyto the constants provided by the !!{language}~$\Lang{L}$ of the!!{structure}s), and hence it applies to the case of abstractlogics. In case of first-order logic, we know from\olref[bas][pis]{thm:p-isom2} that if two !!{structure}s are partiallyisomorphic then they are elementarily equivalent. That proof does notcarry over to abstract logics, for induction on !!{formula}s need notbe available for arbitrary $!E \in L(\Lang{L})$, but the theorem istrue nonetheless, provided the L\"owenheim--Skolem property holds.\begin{thm}\ollabel{thm:abstract-p-isom}Suppose $\tuple{L, \models_L}$ is a normal logic with theL\"owenheim--Skolem property. Then any two !!{structure}s that arepartially isomorphic are elementarily equivalent in $\tuple{L,  \models_L}$.\end{thm}\begin{proof}Suppose $\Struct{M} \simeq_p \Struct{N}$, but for some $!E$ also$\Struct{M} \models_L !E$ while $\Struct{N} \not\models_L !E$. By theIsomorphism Property we can assume that $\Domain{M}$ and $\Domain{N}$are disjoint, and by the Expansion Property we can assume that $!E \inL(\Lang{L})$ for a finite !!{language}~$\Lang{L}$. Let $\mathcal{I}$be a set of partial isomorphisms between $\Struct{M}$ and$\Struct{N}$, and with no loss of generality also assume that if $p\in \mathcal{I}$ and $q \subseteq p$ then also $q \in \mathcal{I}$.$\Domain{M}^{<\omega}$ is the set of finite sequences of !!{element}sof~$\Domain{M}$. Let $S$ be the ternary relation over $\Domain{M}^{<\omega}$representing concatenation, i.e., if $\mathbf{a}, \mathbf{b},\mathbf{c} \in \Domain{M}^{<\omega}$ then $S(\mathbf{a}, \mathbf{b},\mathbf{c})$ holds if and only if $\mathbf{c}$ is the concatenation of$\mathbf{a}$ and $\mathbf{b}$; and let $T$ be the ternary relationsuch that $T(\mathbf{a}, b, \mathbf{c})$ holds for $b \in M$ and$\mathbf{a}, \mathbf{c} \in \Domain{M}^{<\omega}$ if and only if $\mathbf{a} =a_1, \dots a_n$ and $\mathbf{c} = a_1, \dots a_n, b$.  Pick new3-place !!{predicate}s $P$ and $Q$ and form the !!{structure}$\Struct{M}^*$ having the universe $\Domain{M} \cup \Domain{M}^{<\omega}$, having$\Struct{M}$ as a substructure, and interpreting $P$ and $Q$ by theconcatenation relations $S$ and $T$ (so $\Struct{M}^*$ is in the!!{language} $\Lang{L} \cup \{ P, Q\}$).Define $\Domain{N}^{<\omega}$, $S'$, $T'$, $P'$, $Q'$ and$\Struct{N}^*$ analogously. Since by hypothesis $\Struct{M} \simeq_p\Struct{N}$, there is a relation $I$ between $\Domain{M}^{<\omega}$and $\Domain{N}^{<\omega}$ such that $I(\mathbf{a}, \mathbf{b})$holds if and only if $\mathbf{a}$ and $\mathbf{b}$ are isomorphic andsatisfy the back-and-forth condition of\olref[bas][pis]{defn:partialisom}.  Now, let $\Struct{M}$ be the!!{structure} whose !!{domain} is the union of the !!{domain}s of$\Struct{M}^*$ and $\Struct{N}^*$, having $\Struct{M}^*$ and$\Struct{N}^*$ as sub!!{structure}s, in the !!{language} with one extrabinary !!{predicate}~$R$ interpreted by the relation~$I$ and!!{predicate}s denoting the !!{domain}s $\Domain{M}^*$and~$\Domain{N}*$.\begin{figure}[h]  \centering  \begin{tikzpicture}[node distance=2cm, auto, thick, >=stealth']    \draw [rounded corners] (0,0) -- (8,0) -- (8,4) -- (0,4) --  cycle;    \draw (2,2) circle (0.5cm);    \draw (2,2) circle (1.25cm);    \draw (6,2) circle (0.5cm);    \draw (6,2) circle (1.25cm);    \path node at (0.75,3.5) {\large $\Struct{M}$};    \path node at (2,2) {\large $\Struct{M}$};    \path node at (6,2) {\large $\Struct{N}$};    \path node at (3.5,1) {\large $\Struct{M}^*$};    \path node at (7.5,1) {\large $\Struct{N}^*$};    \node (Idom) at (2.8,2) {};    \node (Irng) at (5.2,2) {};    \draw[<->, bend left] (Idom) to node {\large $I$} (Irng) ;  \end{tikzpicture}   \caption{The !!{structure}~$\Struct{M}$ with the internal    partial isomorphism.}\end{figure}The crucial observation is that in the !!{language} of the!!{structure}~$\Struct{M}$ there is a \emph{first-order} !!{sentence} $!D_1$true in $\Struct{M}$ saying that $\Struct{M} \models_L !E$ and$\Struct{N} \not\models_L !E$ (this requires the RelativizationProperty), as well as a \emph{first-order} !!{sentence} $!D_2$ true in$\Struct{M}$ saying that $\Struct{M} \simeq_p \Struct{N}$ via thepartial isomorphism~$I$. By the L\"owenheim--Skolem Property, $!D_1$and $!D_2$ are jointly true in !!a{enumerable} model $\Struct{M}_0$containing partially isomorphic substructures $\Struct{M}_0$ and$\Struct{N}_0$ such that $\Struct{M}_0 \models_L !E$ and $\Struct{N}_0\not\models_L !E$. But !!{enumerable} partially isomorphic !!{structure}s arein fact isomorphic by \olref[bas][pis]{thm:p-isom1}, contradicting theIsomorphism Property of normal abstract logics.\end{proof}\end{document}

content/model-theory/lindstrom/lindstrom-proof.tex

% Part: first-order-logic% Chapter: lindstrom% Section: lindstrom-proof\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mod}{lin}{prf}\olsection{Lindstr\"om's Theorem}\begin{lem}\ollabel{lem:lindstrom}Suppose $!E \in L(\Lang{L})$, with $\Lang{L}$ finite, and assumealso that there is an $n \in \Nat$ such that for any two!!{structure}s $\Struct{M}$ and~$\Struct{N}$, if $\Struct{M} \equiv_n\Struct{N}$ and $\Struct{M} \models_L !E$ then also $\Struct{N}\models_L !E$. Then $!E$ is equivalent to a first-order!!{sentence}, i.e., there is a first-order $!D$ such that$\Mod(L){!E} = \Mod(L){!D}$.\end{lem}\begin{proof} Let $n$ be such that any two $n$-equivalent !!{structure}s$\Struct{M}$ and $\Struct{N}$ agree on the value assigned to~$!E$.Recall \olref[bas][pis]{prop:qr-finite}: there are only finitely manyfirst-order !!{sentence}s in a finite !!{language} that havequantifier rank no greater than~$n$, up to logical equivalence. Now,for each fixed !!{structure}~$\Struct{M}$ let $!D_{\Struct{M}}$ be theconjunction of all first-order !!{sentence}s~$!E$ true in~$\Struct{M}$with $\QuantRank{!E} \le n$ (this conjunction is finite), so that$\Struct{N} \models !D_{\Struct{M}}$ if and only if $\Struct{N}\equiv_n \Struct{M}$. Then put $!D = \textstyle\bigvee\Setabs{!D_{\Struct{M}}}{\Struct{M} \models_L !E}$; this disjunctionis also finite (up to logical equivalence).The conclusion $\Mod(L){!E} = \Mod(L){!D}$ follows. In fact, if$\Struct{N} \models_L !D$ then for some $\Struct{M} \models_L!E$ we have $\Struct{N} \models !D_{\Struct{M}}$, whence also$\Struct{N} \models_L !E$ (by the hypothesis of thelemma). Conversely, if $\Struct{N} \models_L !E$ then$!D_\Struct{N}$ is a disjunct in $!D$, and since $\Struct{N}\models !D_\Struct{N}$, also $\Struct{N} \models_L !D$.\end{proof}\begin{thm}[Lindstr\"om's Theorem]  \ollabel{thm:lindstrom} Suppose $\tuple{L, \models_L}$ has the  Compactness and the L\"owenheim--Skolem Properties. Then  $\tuple{L, \models_L} \le \tuple{F, \models}$ (so  $\tuple{L, \models_L}$ is equivalent to first-order logic).\end{thm}\begin{proof}By \olref{lem:lindstrom}, it suffices to show that for any $!E\in L(\Lang{L})$, with $\Lang{L}$ finite, there is $n \in \Nat$such that for any two !!{structure}s $\Struct{M}$ and~$\Struct{N}$: if$\Struct{M} \equiv_n \Struct{N}$ then $\Struct{M}$ and $\Struct{N}$agree on~$!E$. For then $!E$ is equivalent to a first-order!!{sentence}, from which $\tuple{L, \models_L} \le \tuple{F, \models}$follows. Since we are working in a finite, purely relational!!{language}, by \olref[bas][pis]{thm:b-n-f} we can replace the statementthat $\Struct{M} \equiv_n \Struct{N}$ by the corresponding algebraicstatement that $I_n(\emptyset,\emptyset)$.Given $!E$, suppose towards a contradiction that for each $n$ thereare !!{structure}s $\Struct{M}_n$ and $\Struct{N}_n$ such that$I_n(\emptyset, \emptyset)$, but (say) $\Struct{M}_n \models_L !E$whereas $\Struct{N}_n \not\models_L !E$. By the Isomorphism Propertywe can assume that all the $\Struct{M}_n$'s interpret the constants ofthe language by the same objects; furthermore, since there are onlyfinitely many atomic !!{sentence}s in the language, we may also assumethat they satisfy the same atomic !!{sentence}s (we can take asubsequence of the $\Struct{M}$'s otherwise). Let $\Struct{M}$ be theunion of all the $\Struct{M}_n$'s, i.e., the unique minimal!!{structure} having each $\Struct{M}_n$ as a substructure.  As in theproof of \olref[lsp]{thm:abstract-p-isom}, let $\Struct{M}^*$ be theextension of $\Struct{M}$ with !!{domain} $\Domain{M} \cup\Domain{M}^{<\omega}$, in the expanded !!{language} comprising theconcatenation predicates $P$ and~$Q$.Similarly, define $\Struct{N}_n$, $\Struct{N}$ and $\Struct{N}^*$. Nowlet $\Struct{M}$ be the !!{structure} whose !!{domain} comprises the!!{domain}s of $\Struct{M}^*$ and $\Struct{N}^*$ as well as the naturalnumbers~$\Nat$ along with their natural ordering~$\le$, in the!!{language} with extra predicates representing the !!{domain}s$\Domain{M}$, $\Domain{N}$, $\Domain{M}^{<\omega}$ and$\Domain{N}^{<\omega}$ as well as predicates coding the domains of$\Struct{M}_n$ and $\Struct{N}_n$ in the sense that:\begin{align*}  \Domain{M_n} & = \Setabs{a \in \Domain{M}}{R(a, n)}; &   \Domain{N_n} & = \Setabs{a \in \Domain{N}}{S(a,n)}; \\  \Domain{M}^{<\omega}_n & = \Setabs{a \in \Domain{M}^{<\omega}}{R(a,n)}; &  \Domain{N}^{<\omega}_n & = \Setabs{a \in \Domain{N}^{<\omega}}{S(a,n)}. \end{align*}The !!{structure}~$\Struct{M}$ also has a ternary relation $J$ suchthat $J(n, \mathbf{a}, \mathbf{b})$ holds if and only if$I_n(\mathbf{a}, \mathbf{b})$.Now there is !!a{sentence}~$!D$ in the !!{language}~$\Lang{L}$ augmentedby $R$, $S$, $J$, etc., saying that $\le$ is a discrete linear orderingwith first but no last element and such that $\Struct{M}_n \models!E$, $\Struct{N}_n \not\models !E$, and for each $n$ in theordering, $J(n, \mathbf{a}, \mathbf{b})$ holds if and only if$I_n(\mathbf{a}, \mathbf{b})$.Using the Compactness Property, we can find a model $\Struct{M}^*$ of$!D$ in which the ordering contains a non-standard element~$n^*$. Inparticular then $\Struct{M^*}$ will contain sub!!{structure}s$\Struct{M_{n^*}}$ and $\Struct{N_{n^*}}$ such that $\Struct{M_{n^*}}\models_L !E$ and $\Struct{N_{n^*}} \not\models_L !E$. But now we candefine a set $\mathcal{I}$ of pairs of $k$-tuples from$\Domain{M_{n^*}}$ and $\Domain{N_{n^*}}$ by putting$\tuple{\mathbf{a}, \mathbf{b}} \in \mathcal{I}$ if and only if$J(n^*-k, \mathbf{a}, \mathbf{b})$, where $k$ is the length of$\mathbf{a}$ and $\mathbf{b}$. Since $n^*$ is non-standard, for eachstandard $k$ we have that $n^* - k >0$, and the set $\mathcal{I}$witnesses the fact that $\Struct{M_{n^*}} \simeq_p\Struct{N_{n^*}}$. But by \olref[lsp]{thm:abstract-p-isom},$\Struct{M_{n^*}}$ is $L$-equivalent to $\Struct{N_{n^*}}$, acontradiction.\end{proof}\end{document}