Namespaces
Variants
Actions

Keisler-Shelah isomorphism theorem

From Encyclopedia of Mathematics
Jump to: navigation, search

Interpretations for a first-order language $ L $ are said to be elementarily equivalent (in $ L $) provided that they make exactly the same sentences in $ L $ true (cf. also Interpretation). The Keisler–Shelah isomorphism theorem provides a characterization of elementary equivalence: Interpretations for $ L $ are elementarily equivalent if and only if they have isomorphic ultrapowers (cf. also Ultrafilter).

This theorem was formulated and proved by H.J. Keisler in 1961 [a2]. Keisler gave a second proof in 1964 using saturated ultrapowers [a3]. Both proofs used the generalized continuum hypothesis ($ \mathsf{GCH} $). In 1971, S. Shelah gave a third proof [a5] that avoided $ \mathsf{GCH} $.

Given a non-empty family $ (\mathfrak{A}_{i})_{i \in I} $ of interpretations for $ L $, and given an ultrafilter $ \mathcal{F} $ on $ I $, the ultraproduct $ \prod_{i \in I} \mathfrak{A}_{i} \big/ \mathcal{F} $ of the family is defined as the quotient system on the direct product of the family induced by $ \mathcal{F} $. When there is a fixed interpretation $ \mathfrak{A} $ for $ L $, so that each $ \mathfrak{A}_{i} $ coincides with $ \mathfrak{A} $, the ultraproduct $ \prod_{i \in I} \mathfrak{A}_{i} \big/ \mathcal{F} $ is denoted by $ \mathfrak{A}^{I} \big/ \mathcal{F} $ and is called an ultrapower of $ \mathfrak{A} $. It follows from results of J. Łos [a4] that $ \mathfrak{A} $ and any of its ultrapowers are elementarily equivalent (this is the Łos isomorphism theorem). Hence, interpretations with isomorphic ultrapowers are elementarily equivalent.

Let $ \lambda $ be an infinite cardinal no smaller than the cardinality of the set of sentences in $ L $, and let $ \mathfrak{A} $ and $ \mathfrak{B} $ be interpretations for $ L $ of cardinality less than or equal to $ 2^{\lambda} $. Let $ \lambda^{+} $ denote the successor cardinal of $ \lambda $. Keisler showed (assuming that $ 2^{\lambda} = \lambda^{+} $) that $ \mathfrak{A} $ and $ \mathfrak{B} $ are elementarily equivalent if and only if there are ultrafilters $ \mathcal{F} $ and $ \mathcal{G} $ on $ \lambda $ such that $ \mathfrak{A}^{\lambda} \big/ \mathcal{F} $ and $ \mathfrak{B}^{\lambda} \big/ \mathcal{G} $ are isomorphic.

Let $ \lambda $ be as above, and let $ \beta $ be the least cardinal such that $ \lambda^{\beta} > \lambda $. Shelah showed (without assuming that $ 2^{\lambda} = \lambda^{+} $) that there is an ultrafilter $ \mathcal{F} $ on $ \lambda $ such that given elementarily equivalent interpretations $ \mathfrak{A} $ and $ \mathfrak{B} $ for $ L $ of cardinality less than $ \beta $, the ultrapowers $ \mathfrak{A}^{\lambda} \big/ \mathcal{F} $ and $ \mathfrak{B}^{\lambda} \big/ \mathcal{F} $ are isomorphic.

The motivation for Keisler’s results can be found in a program propounded by A. Tarski [a6]: To provide characterizations of meta-mathematical notions in “purely mathematical terms”. A discussion of this program and its history can be found in [a7]. To appreciate what was intended here, recall G. Birkhoff’s 1935 characterization [a1] of the classes of models of sets of equations (the equational classes): A class of algebras is an equational class if and only if it is closed under sub-algebras, homomorphic images and direct products. This result characterizes equational classes without mentioning equations.

Among the consequences of the Keisler–Shelah isomorphism theorem is a comparable “mathematical” characterization of the classes of models of sentences in $ L $. Given a class $ \mathcal{T} $ of interpretations for $ L $, we say that $ \mathcal{T} $ is an elementary class provided that there is a sentence in $ L $ whose models are exactly the members of $ \mathcal{T} $; we say that $ \mathcal{T} $ is an elementary class in the wider sense provided that there is a set of sentences in $ L $ whose models are exactly the members of $ \mathcal{T} $. It follows from the compactness theorem that $ \mathcal{T} $ is an elementary class if and only if both $ \mathcal{T} $ and its complement (relative to the class of interpretations for $ L $) are elementary classes in the wider sense. Keisler [a2] showed (assuming $ \mathsf{GCH} $) that:

1) $ \mathcal{T} $ is an elementary class in the wider sense, provided that $ \mathcal{T} $ is closed under isomorphic images and ultraproducts and the complement of $ \mathcal{T} $ is closed under ultrapowers;

2) $ \mathcal{T} $ is an elementary class if and only if both $ \mathcal{T} $ and its complement are closed under isomorphic images and ultraproducts.

Whilst Keisler’s proof of this result used $ \mathsf{GCH} $, its application was restricted to establishing that elementarily equivalent interpretations have isomorphic ultrapowers. Hence, by eliminating $ \mathsf{GCH} $ from the proof of the latter result, Shelah also eliminated the use of $ \mathsf{GCH} $ from Keisler’s characterization of elementary classes.

References

[a1] G. Birkhoff, “On the structure of abstract algebras”, Proc. Cambridge Philos. Soc., 31 (1935), pp. 433–454.
[a2] H.J. Keisler, “Ultraproducts and elementary models”, Indagationes Mathematicae, 23 (1961), pp. 477–495.
[a3] H.J. Keisler, “Ultraproducts and saturated classes”, Indagationes Mathematicae, 26 (1964), pp. 178–186.
[a4] J. Łos, “Quelques remarqes, théorèmes et problèmes sur les classes définissables d'algèbres”, Mathematical Interpretations of Formal Systems, North-Holland (1955), pp. 98–113.
[a5] S. Shelah, “Every two elementarily equivalent models have isomorphic ultrapowers”, Israel J. Math., 10 (1971), pp. 224–233.
[a6] A. Tarski, “Some notions and methods on the borderline of algebra and metamathematics”, Proc. Intern. Congress of Math. (Cambridge, MA, 1950), 1, Amer. Math. Soc. (1952), pp. 705–720.
[a7] R.L. Vaught, “Model theory before 1945”, Proc. Tarski Symp., Amer. Math. Soc. (1974), pp. 153–172.
How to Cite This Entry:
Keisler–Shelah isomorphism theorem. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Keisler%E2%80%93Shelah_isomorphism_theorem&oldid=22640