This is an exercise sheet in model theory and discusses the idea of an embedding of a structure into another structure . One of the highlights is a preservation theorem that says exactly when has an embedding into some -structure satisfying a given -theory .
Fix a first-order language . Unless otherwise stated, , will be understood to be -structures. I will use here the notation for an undetermined finite number of parameters or variables . You will also need to know the definitions of: what it means for a structure to be a substructure of another structure (written ); what it means for to be an embedding, and an elementary embedding; quantifier-free (q.f.) formulas; and the consequences of an -theory .
Show that if , and with quantifier-free then . (Hint: prove holds if and only if holds, for all q.f. and all , by using induction on the complexity of .)
Let be an -structure, let be the language obtained by adding a new constant to for each and regard as a structure in the natural way. Let be the set of q.f. sentences that are true in . Prove that, for any -structure , there is an embedding if and only if has an expansion to such that .
Let be an -theory and . Show that has a model. (Use the Compactness Theorem. You may find the ∀-Introduction rule helpful.)
Deduce that, for all -structures and all -theories , there is some -structure with if and only if .
It is an easy observation that if is an embedding of properly into itself then is infinite. Prove that if is an elementary embedding of properly into itself and is not in the image of , then the set of elements of having the same first-order properties as , i.e. the set
The following is a variation of the last.
Let be an -structure and a proper elementary extension. Then for each the type of , consisting of all formulas true in at has the property that for each the set is infinite. It follows that must be infinite to have a proper elementary extension.
If is a proper elementary extension it need not be the case that is infinite. For example, let have unary relations and let be the -structure consisting of domain and iff . Let be an extension where for all . Then it turns out that but of course .