Fraïssé characterization of elementary equivalence

Interpretations for a formal language are equivalent provided that they give the same truth values to sentences in the language. Equivalent interpretations for first-order languages are said to be elementarily equivalent. R. Fraïssé [a2] established a characterization for elementary equivalence that is purely mathematical, in the sense that it does not mention sentences. Unlike the characterizations of S. Kochen [a5] and H.J. Keisler [a4], Fraïssé's characterization applies only to those first-order languages whose non-logical vocabulary is finite and contains no functional constants.

Let $ L $ be such a first-order language (with equality). Each predicate constant in the non-logical vocabulary of $ L $ is associated with an unique positive integer called its degree. Let $ \{ c _ {1} \dots c _ {n} , \dots \} $ be an infinite set of individual constants not in the non-logical vocabulary of $ L $. The family of first-order languages $ \{ {L ( n ) } : {n \geq 0 } \} $ is defined as follows:

1) $ L ( 0 ) $ is $ L $;

2) $ L ( n + 1 ) $ is the language obtained from $ L ( n ) $ by adding $ c _ {n+1 } $ to the non-logical vocabulary of $ L ( n ) $.

Interpretations for $ L ( n ) $ are ordered pairs $ \mathfrak A = ( A,f _ {\mathfrak A} ) $, where $ A $ is a non-empty set (the domain of $ \mathfrak A $) and $ f _ {\mathfrak A} $ is a function defined on the non-logical vocabulary of $ L ( n ) $ as follows:

1) if $ k $ is an individual constant, $ f _ {\mathfrak A} ( k ) $( the denotation of $ k $ on $ \mathfrak A $) is a member of $ A $;

2) if $ P $ is a predicate constant of degree $ m $, $ f _ {\mathfrak A} ( P ) $( the extension of $ P $ on $ \mathfrak A $) is a subset of $ A ^ {m} $.

When $ \mathfrak A $ is an interpretation of $ L ( n ) $ and $ b _ {1} \dots b _ {t} $ are members of $ A $, $ ( \mathfrak A b _ {1} \dots b _ {t} ) $ denotes the interpretation of $ L ( n + t ) $ with domain $ A $ that agrees with $ \mathfrak A $ on the non-logical vocabulary of $ L ( n ) $ and in which $ b _ {i} $ is the denotation of $ c _ {n+i } $ for all $ i $, $ 1 \leq i \leq t $.

Given interpretations $ \mathfrak A $ and $ \mathfrak B $ for $ L ( n ) $, $ \mathfrak A $ is a sub-interpretation, or subsystem, of $ \mathfrak B $ provided that:

1) $ A \subseteq B $;

2) $ f _ {\mathfrak A} $ and $ f _ {\mathfrak B} $ give the same denotations to individual constants of $ L ( n ) $;

3) if $ P $ is a predicate constant of degree $ m $, $ f _ {\mathfrak A} ( P ) = f _ {\mathfrak B} ( P ) \cap A ^ {m} $.

Let $ D $ be a subset of $ A $. $ \mathfrak A [ D ] $ denotes the subsystem of $ \mathfrak A $ generated by $ D $( i.e., the smallest subsystem of $ \mathfrak A $ whose domain contains $ D $). When $ D $ is non-empty, $ \mathfrak A [ D ] $ exists and its domain is finite if $ D $ is finite. Let $ \Lambda $ denote the null set. $ \mathfrak A [ \Lambda ] $ exists when $ n \geq 1 $ or when $ n = 0 $ and $ L ( 0 ) $ contains individual constants.

For each $ l \geq 0 $, $ \sim _ {l} $ is defined on pairs of interpretations for $ L ( n ) $ as follows:

1) $ \mathfrak A \sim _ {0} \mathfrak B $ if and only if $ \mathfrak A [ \Lambda ] $ and $ \mathfrak B [ \Lambda ] $ are isomorphic;

2) $ \mathfrak A \sim _ {l + 1 } \mathfrak B $ if and only if

2a) for all $ a \in A $ there is a $ b \in B $ such that $ ( \mathfrak A a ) \sim _ {l} ( \mathfrak B b ) $;

2b) for all $ b \in B $ there is an $ a \in A $ such that $ ( \mathfrak B b ) \sim _ {l} ( \mathfrak A a ) $.

Fraïssé proved that $ \mathfrak A $ and $ \mathfrak B $ are elementarily equivalent if and only if $ \mathfrak A \sim _ {l} \mathfrak B $ for all $ l \geq 0 $.

For $ \phi $ a sentence in $ L ( n ) $, $ q ( \phi ) $ is the number of distinct variables occurring in $ \phi $; $ q ( \phi ) $ is called the quantifier rank of $ \phi $. One writes $ \mathfrak A \equiv _ {l} \mathfrak B $ when $ \mathfrak A $ and $ \mathfrak B $ give the same truth values to all sentences in $ L ( n ) $ of quantifier rank less than or equal to $ l $. $ \mathfrak A $ and $ \mathfrak B $ are elementarily equivalent if and only if $ \mathfrak A \equiv _ {l} \mathfrak B $ for all $ l \geq 0 $.

Let $ x _ {1} \dots x _ {n} , \dots $ be an enumeration (without repeats) of the individual variables in $ L $. Fix an enumeration (without repeats) of the formulas in $ L ( n ) $. Let $ S $ be a non-empty finite set of formulas. There is an $ m $ such that $ S = \{ \phi _ {1} \dots \phi _ {m} \} $ and $ \phi _ {i} $ occurs before $ \phi _ {j} $ in the enumeration when $ i < j $. Let $ \& S $ denote $ ( \phi _ {1} \& \dots \& \phi _ {n} ) $, and let $ \lor S $ denote $ ( \phi _ {1} \lor \dots \lor \phi _ {n} ) $.

Given $ \mathfrak A $, $ m \geq 0 $, $ l \geq 0 $, and a sequence $ {\overline{a}\; } $ of members of $ A $ of length $ m $, the formula $ \psi _ {\mathfrak A} ^ {l} {\overline{a}\; } $ is defined as follows. $ \psi _ {\mathfrak A} ^ {0} {\overline{a}\; } $ is the conjunction of the set consisting of all atomic formulas in $ L ( n ) $ in the variables $ x _ {1} \dots x _ {m} $ which are satisfied by $ {\overline{a}\; } $ in $ \mathfrak A $, and of the negations of all such formulas which are not satisfied by $ {\overline{a}\; } $ in $ \mathfrak A $. $ \psi _ {\mathfrak A} ^ {l+1 } {\overline{a}\; } $ is the conjunction of

$$ \& \left \{ {\exists x _ {n + 1 } \psi _ {\mathfrak A} ^ {l} {\overline{a}\; } a } : {a \in A } \right \} $$

and

$$ \forall x _ {n + 1 } \lor \left \{ {\psi _ {\mathfrak A} ^ {l} {\overline{a}\; } a } : {a \in A } \right \} . $$

Let $ e $ denote the null sequence. When $ m = 0 $, $ \psi _ {\mathfrak A} ^ {l} {\overline{a}\; } $ is written $ \psi _ {\mathfrak A} ^ {l} e $. For fixed $ m $ and $ l $ there are only finitely many formulas of the form $ \psi _ {\mathfrak A} ^ {l} {\overline{a}\; } $. $ \psi _ {\mathfrak A} ^ {l} {\overline{a}\; } $ is a formula in $ m $ free variables and $ l $ bound variables. Hence $ \psi _ {\mathfrak A} ^ {l} e $ is of quantifier rank $ l $.

Assume that $ \mathfrak A $ and $ \mathfrak B $ are interpretations for $ L ( n ) $, $ m $ and $ l $ are natural numbers such that $ 1 \leq m \leq l $, $ {\overline{a}\; } $ is a sequence of members of $ A $ of length $ m $, and $ {\overline{b}\; } $ is a sequence of members of $ B $ of length $ m $. $ \psi _ {\mathfrak A} ^ {l - m } {\overline{a}\; } $ is satisfied by $ {\overline{b}\; } $ in $ \mathfrak B $ if and only if $ ( \mathfrak A {\overline{a}\; } ) \sim _ {l - m } ( \mathfrak B {\overline{b}\; } ) $. This result implies that for all $ l \geq 0 $ the following assertions are equivalent:

1) $ \mathfrak A \equiv _ {l} \mathfrak B $;

2) $ \mathfrak A \sim _ {l} \mathfrak B $;

3) $ \mathfrak B $ is a model of $ \psi _ {\mathfrak A} ^ {l} e $. Fraïssé's characterization is immediate.

It also follows that any sentence of quantifier rank less than or equal to $ l $ which is true on $ \mathfrak A $ is a logical consequence of $ \psi _ {\mathfrak A} ^ {l} e $( i.e., true on all models of $ \psi _ {\mathfrak A} ^ {l} e $). Hence every such sentence of its negation is a logical consequence of $ \psi _ {\mathfrak A} ^ {l} e $. Since for fixed $ l $ there are only finitely many sentences of the form $ \psi _ {\mathfrak A} ^ {l} e $, there are only finitely many non-equivalent sentences of quantifier rank less than or equal to $ l $. Let $ \phi $ be a sentence of quantifier rank $ l $. Assume that $ \phi $ has models. Let $ \psi $ be the sentence

$$ \lor \left \{ {\psi _ {\mathfrak A} ^ {l} e } : {\phi \textrm{ is true on } \mathfrak A } \right \} . $$

$ \psi $ is a distributive normal form in the sense of J. Hintikka [a3]. Furthermore, $ \phi $ and $ \psi $ are logically equivalent (i.e., have exactly the same models).

Let $ T $ be a set of sentences. Call $ T $ a theory when every logical consequence of $ T $ is a member of $ T $. Assume that $ T $ has models. Let

$$ P ( T,l ) = \lor \left \{ {\psi _ {\mathfrak A} ^ {l} e } : {\mathfrak A \textrm{ is a model of } T } \right \} . $$

Let $ P ( T, \omega ) = \{ {P ( T,l ) } : {l \geq 0 } \} $. $ T $ and $ P ( T, \omega ) $ have exactly the same models; $ T $ is decidable if and only if $ P ( T, \omega ) $ is recursive and $ T $ is finitely axiomatizable if and only if there is an $ l $ such that the models of $ T $ are closed under $ \sim _ {l} $.

Alternative definitions of $ \sim _ {l} $ can be found in [a6] and [a7]. A. Ehrenfeucht [a1] independently obtained Fraïssé's characterization formulated in terms of two-person games. Fraïssé's characterization has been extended to provide characterizations of equivalence for a variety of "non-elementary" languages. For example, see [a6], [a7], and [a8].

References

[a1]	A. Ehrenfeucht, "An application of games to the completeness problem for formalised theories" Fundam. Math. , 49 (1956) pp. 129–141
[a2]	R. Fraïssé, "Sur quelques classifications des relations basés sur des isomorphismes restraintes" Publ. Sci. Univ. Alger. Ser. A , 2 (1955) pp. 11–60, 273–295
[a3]	J. Hintikka, "Distributive normal forms in first order logic" J.N. Crossley (ed.) M.A.E. Dummet (ed.) , Formal Systems and Recursive Functions , North-Holland (1965) pp. 48–91
[a4]	H.J. Keisler, "Ultraproducts and elementary classes" Indagationes Mathematicae , 23 (1961) pp. 277–295 MR0140396 Zbl 0118.01501
[a5]	S. Kochen, "Ultraproducts in the theory of models" Ann. of Math. , 74 (1961) pp. 231–261
[a6]	A. Mostowski, "Thirty years of foundational studies" , Barnes and Noble (1966)
[a7]	D. Scott, "Logic with denumerably long formulas and finite strings of quantifiers" J.W. Addison (ed.) L. Henkin (ed.) A. Tarski (ed.) , The Theory of Models , North-Holland (1966) pp. 329–341
[a8]	G. Weaver, J. Welaish, "Back and forth arguments in modal logic" J. Symb. Logic , 51 (1987) pp. 969–980