Embeddings of L-structures

This is an exercise sheet in model theory and discusses the idea of an embedding of a structure M into another structure N . One of the highlights is a preservation theorem that says exactly when M has an embedding into some L -structure satisfying a given L -theory T .

Fix a first-order language L . Unless otherwise stated, M , N will be understood to be L -structures. I will use here the notation a _ for an undetermined finite number of parameters or variables a 0 , a 1 , . You will also need to know the definitions of: what it means for a structure M to be a substructure of another structure N (written M N ); what it means for f : M N to be an embedding, and an elementary embedding; quantifier-free (q.f.) formulas; and the 1 consequences 1 - ( T ) of an L -theory T .

Exercise.

Show that if M N , a _ M and N x _ θ ( x _ , a _ ) with θ quantifier-free then M x _ θ ( x _ , a _ ) . (Hint: prove N θ ( b _ ) holds if and only if M θ ( b _ ) holds, for all q.f. θ and all b _ M , by using induction on the complexity of θ .)

Exercise.

Let M be an L -structure, let L M be the language obtained by adding a new constant a to L for each a M and regard M as a L M structure in the natural way. Let D 0 ( M ) be the set of q.f. L M sentences that are true in M . Prove that, for any L -structure N , there is an embedding f : M N if and only if N has an expansion N 0 = ( N , , a N , ) a M to L M such that N 0 D 0 ( M ) .

Exercise.

Let T be an L -theory and M 1 - ( T ) . Show that D 0 ( M ) T has a model. (Use the Compactness Theorem. You may find the ∀-Introduction rule helpful.)

Exercise.

Deduce that, for all L -structures M and all L -theories T , there is some L -structure N M with N T if and only if M 1 - ( T ) .

Exercise.

It is an easy observation that if f : M M is an embedding of M properly into itself then M is infinite. Prove that if f : M M is an elementary embedding of M properly into itself and a M is not in the image of f , then the set of elements of M having the same first-order properties as a , i.e. the set

{ b M : M ( θ ( a ) θ ( b ) ) ,   for all formulas   θ }

is infinite.

The following is a variation of the last.

Exercise.

Let M be an L -structure and N M a proper elementary extension. Then for each a N M the type of a , tp ( a ) = { θ ( x ) : N θ ( a ) } consisting of all formulas θ ( x ) true in N at a has the property that for each θ ( x ) tp ( a ) the set { c M : M θ ( c ) } is infinite. It follows that M must be infinite to have a proper elementary extension.

If N M is a proper elementary extension it need not be the case that N M is infinite. For example, let L have 0 unary relations R i and let M be the L -structure consisting of domain and M R i ( j ) iff i = j . Let N = ω be an extension where N ¬ R i ( ω ) for all i . Then it turns out that N M but of course N M = ω .