Lindström's Theorem

Definition: abstract logic

An abstract logic is a pair $⟨L,{\models }_L⟩$source, where $L$source is a function that assigns to each language $L$source a set $L\left(L\right)$source of sentences, and ${\models }_L$source is a relation between structures for the language $L$source and elements of $L\left(L\right)$source. In particular, $⟨F,\models ⟩$source is ordinary first-order logic, i.e., $F$source is the function assigning to the language $L$source the set of first-order sentences built from the constants in $L$source, and $\models$source is the satisfaction relation of first-order logic.

Definition: model class and elementary equivalence

Let ${\mathrm{Mod}}_{}\left(L\right)\left(E\right)$source denote the class $\{M:M{\models }_{L}E\}$source. If the language needs to be made explicit, we write ${\mathrm{Mod}}_L\left(L\right)\left(E\right)$source. Two structures $M$source and $N$source for $L$source are elementarily equivalent in $⟨L,{\models }_L⟩$source, written $M{\equiv }_{L}N$source, if the same sentences from $L\left(L\right)$source are true in each.

Definition: normal abstract logic

An abstract logic $⟨L,{\models }_L⟩$source for the language $L$source is normal if it satisfies the following properties:

1. ($L$source-Monotonicity) For languages $L$source and $L^{\prime }$source, if $L\subseteq L^{\prime }$source, then $L\left(L\right)\subseteq L\left(L^{\prime }\right)$source.

2. (Expansion Property) For each $E\in L\left(L\right)$source there is a finite subset $L^{\prime }$source of $L$source such that the relation $M{\models }_{L}E$source depends only on the reduct of $M$source to $L^{\prime }$source; i.e., if $M$source and $N$source have the same reduct to $L^{\prime }$source then $M{\models }_{L}E$source if and only if $N{\models }_{L}E$source.

3. (Isomorphism Property) If $M{\models }_{L}E$source and $M\simeq N$source then also $N{\models }_{L}E$source.

4. (Renaming Property) The relation ${\models }_L$source is preserved under renaming: if the language $L^{\prime }$source is obtained from $L$source by replacing each symbol $P$source by a symbol $P^{\prime }$source of the same arity and each constant $c$source by a distinct constant $c^{\prime }$source, then for each structure $M$source and sentence $E$source, $M{\models }_{L}E$source if and only if $M^{\prime }{\models }_L{E}^{\prime }$source, where $M^{\prime }$source is the $L^{\prime }$source-structure corresponding to $L$source and $E^{\prime }\in L\left(L^{\prime }\right)$source.

5. (Boolean Property) The abstract logic $⟨L,{\models }_L⟩$source is closed under the Boolean connectives in the sense that for each $E\in L\left(L\right)$source there is a $F\in L\left(L\right)$source such that $M{\models }_{L}F$source if and only if $M{⊭}_{L}E$source, and for each $E$source and $F$source there is a $G$source such that ${\mathrm{Mod}}_{}\left(L\right)\left(G\right)={\mathrm{Mod}}_{}\left(L\right)\left(E\right)\cap {\mathrm{Mod}}_{}\left(L\right)\left(F\right)$source. Similarly for atomic formulas and the other connectives.

6. (Quantifier Property) For each constant $c$source in $L$source and $E\in L\left(L\right)$source there is a $F\in L\left(L\right)$source such that

   $${\mathrm{Mod}}_{L^{\prime }}\left(L\right)\left(F\right)=\{M:M\left[a\right]\in {\mathrm{Mod}}_L\left(L\right)\left(E\right)\text{for some}a\in \left|M\right|\},$$source

   where $L^{\prime }=L\setminus \left\{c\right\}$source and $M\left[a\right]$source is the expansion of $M$source to $L$source assigning $a$source to $c$source.

7. (Relativization Property) Given a sentence $E\in L\left(L\right)$source and symbols $R$source, $c_1$source, dots, $c_n$source not in $L$source, there is a sentence $F\in L(L\cup \{R,c_1,\dots ,c_n\left\}\right)$source called the relativization of $E$source to $R\left(x,c_1,\dots c_n\right)$source, such that for each structure $M$source:

   $$M\left[X,b_1,\dots ,b_n\right]{\models }_{L}F\text{if and only if}N{\models }_{L}E,$$source

   where $N$source is the substructure of $M$source with domain $\left|N\right|=\{a\in \left|M\right|:R^M(a,b_1,\dots ,b_n)\}$source (see the rem labeled substructure), and $M\left[X,b_1,\dots ,b_n\right]$source is the expansion of $M$source interpreting $R$source, $c_1$source, dots, $c_n$source by $X$source, $b_1,$source dots, $b_n$source, respectively (with $X\subseteq M^{n+1}$source).

Definition: expressive comparison of logics

Given two abstract logics $⟨L_1,{\models }_{L_1}⟩$source and $⟨L_2,{\models }_{L_2}⟩$source we say that the latter is at least as expressive as the former, written $⟨L_1,{\models }_{L_1}⟩\le ⟨L_2,{\models }_{L_2}⟩$source, if for each language $L$source and sentence $E\in L_1\left(L\right)$source there is a sentence $F\in L_2\left(L\right)$source such that ${\mathrm{Mod}}_L\left(L_1\right)\left(E\right)={\mathrm{Mod}}_L\left(L_2\right)\left(F\right)$source. The logics $⟨L_1,{\models }_{L_1}⟩$source and $⟨L_2,{\models }_{L_2}⟩$source are equivalent if $⟨L_1,{\models }_{L_1}⟩\le ⟨L_2,{\models }_{L_2}⟩$source and $⟨L_2,{\models }_{L_2}⟩\le ⟨L_1,{\models }_{L_1}⟩$source.

Definition: compactness property

An abstract logic $⟨L,{\models }_L⟩$source has the Compactness Property if each set $\Gamma$source of $L\left(L\right)$source-sentences is satisfiable whenever each finite ${\Gamma }_0\subseteq \Gamma$source is satisfiable.

Definition: downward Lowenheim Skolem property

$⟨L,{\models }_L⟩$source has the Downward L\"owenheim--Skolem property if any satisfiable $\Gamma$source has an enumerable model.

Theorem: partial isomorphism in a normal logic

Suppose $⟨L,{\models }_L⟩$source is a normal logic with the L\"owenheim--Skolem property. Then any two structures that are partially isomorphic are elementarily equivalent in $⟨L,{\models }_L⟩$source.

Proof

Suppose $M{\simeq }_{p}N$source, but for some $E$source also $M{\models }_{L}E$source while $N{⊭}_{L}E$source. By the Isomorphism Property we can assume that $\left|M\right|$source and $\left|N\right|$source are disjoint, and by the Expansion Property we can assume that $E\in L\left(L\right)$source for a finite language $L$source. Let $I$source be a set of partial isomorphisms between $M$source and $N$source, and with no loss of generality also assume that if $p\in I$source and $q\subseteq p$source then also $q\in I$source.

${\left|M\right|}^{<\omega }$source is the set of finite sequences of elements of $\left|M\right|$source. Let $S$source be the ternary relation over ${\left|M\right|}^{<\omega }$source representing concatenation, i.e., if $a,b,c\in {\left|M\right|}^{<\omega }$source then $S(a,b,c)$source holds if and only if $c$source is the concatenation of $a$source and $b$source; and let $T$source be the ternary relation such that $T(a,b,c)$source holds for $b\in M$source and $a,c\in {\left|M\right|}^{<\omega }$source if and only if $a=a_1,\dots a_n$source and $c=a_1,\dots a_n,b$source. Pick new 3-place predicate symbols $P$source and $Q$source and form the structure $M^{*}$source having the universe $\left|M\right|\cup {\left|M\right|}^{<\omega }$source, having $M$source as a substructure, and interpreting $P$source and $Q$source by the concatenation relations $S$source and $T$source (so $M^{*}$source is in the language $L\cup \{P,Q\}$source).

Define ${\left|N\right|}^{<\omega }$source, $S^{\prime }$source, $T^{\prime }$source, $P^{\prime }$source, $Q^{\prime }$source and $N^{*}$source analogously. Since by hypothesis $M{\simeq }_{p}N$source, there is a relation $I$source between ${\left|M\right|}^{<\omega }$source and ${\left|N\right|}^{<\omega }$source such that $I(a,b)$source holds if and only if $a$source and $b$source are isomorphic and satisfy the back-and-forth condition of the defn labeled partialisom. Now, let $M$source be the structure whose domain is the union of the domains of $M^{*}$source and $N^{*}$source, having $M^{*}$source and $N^{*}$source as substructures, in the language with one extra binary predicate symbol $R$source interpreted by the relation $I$source and predicate symbols denoting the domains ${\left|M\right|}^{*}$source and ${\left|N\right|}^{*}$source.

The crucial observation is that in the language of the structure $M$source there is a first-order sentence $D_1$source true in $M$source saying that $M{\models }_{L}E$source and $N{⊭}_{L}E$source (this requires the Relativization Property), as well as a first-order sentence $D_2$source true in $M$source saying that $M{\simeq }_{p}N$source via the partial isomorphism $I$source. By the L\"owenheim--Skolem Property, $D_1$source and $D_2$source are jointly true in an enumerable model $M_0$source containing partially isomorphic substructures $M_0$source and $N_0$source such that $M_0{\models }_{L}E$source and $N_0{⊭}_{L}E$source. But enumerable partially isomorphic structures are in fact isomorphic by the thm labeled p isom1, contradicting the Isomorphism Property of normal abstract logics.

Lemma: bounded equivalence implies first-order definability

Suppose $E\in L\left(L\right)$source, with $L$source finite, and assume also that there is an $n\in \mathbb{N}$source such that for any two structures $M$source and $N$source, if $M{\equiv }_{n}N$source and $M{\models }_{L}E$source then also $N{\models }_{L}E$source. Then $E$source is equivalent to a first-order sentence, i.e., there is a first-order $D$source such that ${\mathrm{Mod}}_{}\left(L\right)\left(E\right)={\mathrm{Mod}}_{}\left(L\right)\left(D\right)$source.

Proof

Let $n$source be such that any two $n$source-equivalent structures $M$source and $N$source agree on the value assigned to $E$source. Recall the prop labeled qr finite: there are only finitely many first-order sentences in a finite language that have quantifier rank no greater than $n$source, up to logical equivalence. Now, for each fixed structure $M$source let $D_M$source be the conjunction of all first-order sentences $E$source true in $M$source with $\mathrm{qr}\left(E\right)\le n$source (this conjunction is finite), so that $N\models D_M$source if and only if $N{\equiv }_{n}M$source. Then put $D=\bigvee \{D_M:M{\models }_{L}E\}$source; this disjunction is also finite (up to logical equivalence).

The conclusion ${\mathrm{Mod}}_{}\left(L\right)\left(E\right)={\mathrm{Mod}}_{}\left(L\right)\left(D\right)$source follows. In fact, if $N{\models }_{L}D$source then for some $M{\models }_{L}E$source we have $N\models D_M$source, whence also $N{\models }_{L}E$source (by the hypothesis of the lemma). Conversely, if $N{\models }_{L}E$source then $D_N$source is a disjunct in $D$source, and since $N\models D_N$source, also $N{\models }_{L}D$source.

Theorem: Lindstrom's theorem

[Lindstr\"om's Theorem] Suppose $⟨L,{\models }_L⟩$source has the Compactness and the L\"owenheim--Skolem Properties. Then $⟨L,{\models }_L⟩\le ⟨F,\models ⟩$source (so $⟨L,{\models }_L⟩$source is equivalent to first-order logic).

Proof

By the lem labeled lindstrom, it suffices to show that for any $E\in L\left(L\right)$source, with $L$source finite, there is $n\in \mathbb{N}$source such that for any two structures $M$source and $N$source: if $M{\equiv }_{n}N$source then $M$source and $N$source agree on $E$source. For then $E$source is equivalent to a first-order sentence, from which $⟨L,{\models }_L⟩\le ⟨F,\models ⟩$source follows. Since we are working in a finite, purely relational language, by the thm labeled b n f we can replace the statement that $M{\equiv }_{n}N$source by the corresponding algebraic statement that $I_n(\varnothing ,\varnothing )$source.

Given $E$source, suppose towards a contradiction that for each $n$source there are structures $M_n$source and $N_n$source such that $I_n(\varnothing ,\varnothing )$source, but (say) $M_n{\models }_{L}E$source whereas $N_n{⊭}_{L}E$source. By the Isomorphism Property we can assume that all the $M_n$source's interpret the constants of the language by the same objects; furthermore, since there are only finitely many atomic sentences in the language, we may also assume that they satisfy the same atomic sentences (we can take a subsequence of the $M$source's otherwise). Let $M$source be the union of all the $M_n$source's, i.e., the unique minimal structure having each $M_n$source as a substructure. As in the proof of the thm labeled abstract p isom, let $M^{*}$source be the extension of $M$source with domain $\left|M\right|\cup {\left|M\right|}^{<\omega }$source, in the expanded language comprising the concatenation predicates $P$source and $Q$source.

Similarly, define $N_n$source, $N$source and $N^{*}$source. Now let $M$source be the structure whose domain comprises the domains of $M^{*}$source and $N^{*}$source as well as the natural numbers $\mathbb{N}$source along with their natural ordering $\le$source, in the language with extra predicates representing the domains $\left|M\right|$source, $\left|N\right|$source, ${\left|M\right|}^{<\omega }$source and ${\left|N\right|}^{<\omega }$source as well as predicates coding the domains of $M_n$source and $N_n$source in the sense that:

The structure $M$source also has a ternary relation $J$source such that $J(n,a,b)$source holds if and only if $I_n(a,b)$source.

Now there is a sentence $D$source in the language $L$source augmented by $R$source, $S$source, $J$source, etc., saying that $\le$source is a discrete linear ordering with first but no last element and such that $M_n\models E$source, $N_n⊭E$source, and for each $n$source in the ordering, $J(n,a,b)$source holds if and only if $I_n(a,b)$source.

Using the Compactness Property, we can find a model $M^{*}$source of $D$source in which the ordering contains a non-standard element $n^{*}$source. In particular then $M^{*}$source will contain substructures $M_{n^{*}}$source and $N_{n^{*}}$source such that $M_{n^{*}}{\models }_{L}E$source and $N_{n^{*}}{⊭}_{L}E$source. But now we can define a set $I$source of pairs of $k$source-tuples from $\left|M_{n^{*}}\right|$source and $\left|N_{n^{*}}\right|$source by putting $⟨a,b⟩\in I$source if and only if $J(n^{*}-k,a,b)$source, where $k$source is the length of $a$source and $b$source. Since $n^{*}$source is non-standard, for each standard $k$source we have that $n^{*}-k>0$source, and the set $I$source witnesses the fact that $M_{n^{*}}{\simeq }_p{N}_{n^{*}}$source. But by the thm labeled abstract p isom, $M_{n^{*}}$source is $L$source-equivalent to $N_{n^{*}}$source, a contradiction.