# 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
How to Cite This Entry:
Fraïssé characterization of elementary equivalence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fra%C3%AFss%C3%A9_characterization_of_elementary_equivalence&oldid=46975
This article was adapted from an original article by G. Weaver (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article