2Model theory
III Logic
2.3 Ehrenfeucht–Mostowski theorem
Definition
(Skolem function)
.
Skolem functions for a structure are functions
f
ϕ
for each ϕ ∈ L such that if
M ∀
x
∃
y
ϕ(x, y),
then
M ∀
x
ϕ(x, f
ϕ
(x)).
Definition
(Skolem hull)
.
The Skolem hull of a structure is obtained from the
constants term by closure under the Skolem functions.
Definition
(Elementary embedding)
.
Let Γ be a set of formulae. A function
i
:
M
1
→ M
2
is Γ-elementary iff for all
ϕ ∈
Γ we have
M
1
ϕ
(
x
) implies
M
2
ϕ(i(x)).
If Γ is the set of all formulae in the language, then we just say it is elementary.
Usually, we take Γ to be the set of all formulae, and
M
1
to be a substructure
of M
2
.
Example.
It is, at least intuitively, clear that the inclusion
hQ, ≤i → hR, ≤i
is
elementary.
However, Q as a field is not elementary as a substructure of R as a field.
Note that first order logic is not decidable. However, monadic first order
logic is.
Definition
(Monadic first order logic)
.
Monadic first-order logic is first order
logic with only one-place predicates, no equality and no function symbols.
Proposition. Monadic first-order logic is decidable.
Proof.
Consider any formula
ϕ
. Suppose it involves the one-place predicates
p
1
, . . . , p
n
. Given any structure M, we consider the quotient of M by
x ∼ y ⇔ p
i
(x) = p
i
(y) for all i.
Then there are at most 2
n
things in the quotient.
Then given any transversal of the quotient, we only have to check if the
formula holds for this transversal, and this is finite. So we can decide.
Definition
(Set of indiscernibles)
.
We say
hI, ≤
I
i
is a set of indiscernibles for
L
and a structure
M
with
I ⊆ M
if for any
ϕ ∈ L
(
M
) of arity
n
, and for all
increasing tuples x, y ∈ I,
M ϕ(x) ⇐⇒ M ϕ(y)
This is weaker than just saying everything in there are the same.
Example. hQ, Ii is a set of indiscernibles for hR, ≤i.
Let
T
be a theory with infinite models. The general line of thought is — can
we get a model of T with special properties?
Given any set
M
, invent names for every member of
M
. Add these names to
the language of
T
. We add axioms to say all these constants are distinct. Since
T has infinite models, we know this theory has a model.
Let Ω be the set of countable ordinals, consider the language of
R
, and add
a name to this language for every countable ordinal. We further add axioms to
say that α < β in the ordering of R whenever α < β as ordinals.
Again by compactness, we find that this has a model. So we can embed the
set of countable ordinals into a model of reals, which we know is impossible for
the genuine
R
. However, in general, there is no reason to believe these elements
are a set of indiscernibles. What Ehrenfeucht–Mostowski says is that we can in
fact do so.
Theorem
(Ehrenfeucht–Mostowski theorem (1956))
.
Let
hI, ≤i
be a total order,
and let
T
be a theory with infinite models. Suppose we have a unary predicate
P and a 2-ary relation 4∈ L(T ) such that
T ` 4 is a total order on {x : P (x)}.
Then
T
has a model
M
with a copy of
I
as a sub-order of
4
, and the copy of
I
is a set of indiscernibles. Moreover, we can pick
M
such that every order-
automorphism of hI, ≤i extends to an automorphism of M.
We will give two proofs of this result. We first give the original proof of
Ehrenfeucht–Mostowski, which uses Ramsey theory.
Proof.
Let
T
and
hI, ≤i
be as in the statement of the theorem. We add to
L
(
T
)
names for every element of
I
, say
{c
i
:
i ∈ I}
. We add axioms that says
P
(
c
i
)
and
c
i
4 c
j
whenever
i < j
. We will thereby confuse the orders
≤
and
4
, partly
because ≤ is much easier to type. We call this theory T
∗
.
Now we add to
T
∗
new axioms to say that the
c
i
form a set of indiscernibles.
So we are adding axioms like
ϕ(c
i
, c
j
) ⇔ ϕ(c
i
0
, c
j
0
) (∗)
for all
i < j
and
i
0
< j
0
. We do this simultaneously for all
ϕ ∈ L
(
T
) and all
tuples of the appropriate length. We call this theory
T
I
, and it will say that
hI, ≤i
forms a set of indiscernibles. The next stage is, of course, to prove that
T
I
is consistent.
Consider any finite fragment
T
0
of
T
I
. We want to show that
T
0
is consistent.
By finiteness,
T
0
only mentions finitely many constants, say
c
1
< · · · < c
K
, and
only involve finitely many axioms of the form (
∗
). Denote those predicates as
ϕ
1
, · · · , ϕ
n
. We let N be the supremum of the arities of the ϕ
i
.
Pick an infinite model M of T . We write
M
[N]
= {A ⊆ M : |A| = N},
For each
ϕ
i
, we partition
M
[N]
as follows — given any collection
{a
k
}
N
k=1
, we
use the order relation
4
to order them, so we suppose
a
k
4 a
k+1
. If
ϕ
i
has arity
m ≤ N
, then we can check whether
ϕ
i
(
a
1
, · · · , a
m
) holds, and the truth value
gives us a partition of M
[N]
into 2 bits.
If we do this for all
ϕ
i
, then we have finitely partitioned
M
[N]
. By Ramsey’s
theorem, this has an infinite monochromatic subset, i.e. a subset such that
any two collection of
N
members fall in the same partition. We pick elements
c
1
, · · · , c
K
, · · · , c
K+N
, in increasing order (under
4
). We claim that picking the
c
1
, · · · , c
K
to be our constants satisfy the axioms of T
0
.
Indeed, given any
ϕ
i
mentioned in
T
0
with arity
m < N
, and sequences
c
`
1
< · · · < c
`
m
and
c
`
0
1
< · · · < c
`
0
m
, we can extend these sequences on the right
by adding more of those c
i
. Then by our choice of the colouring, we know
ϕ
i
(c
`
1
, · · · , c
`
m
) ⇔ ϕ
i
(c
`
0
1
, · · · ,
`
0
m
).
So we know
T
0
is consistent. So
T
I
is consistent. So we can just take a model of
T
I
, and the Skolem hull of the indiscernibles is the model desired.
There is another proof of Ehrenfeucht–Mostowski due to Gaifman, using
ultraproducts. We will sketch the proof here.
To do so, we need the notion of colimits.
Definition
(Colimit)
.
Let
{A
i
:
i ∈ I}
be a family of structures index by a poset
hI, ≤i
, with a family of (structure-preserving) maps
{σ
ij
:
A
i
→ A
j
| i ≤ j}
such
that whenever i ≤ j ≤ k, we have
σ
jk
σ
ij
= σ
ik
.
In particular
σ
ii
is the identity. A colimit or direct limit of this family of
structures is a “minimal” structure
A
∞
with maps
σ
i
:
A
i
→ A
∞
such that
whenever i ≤ j, then the maps
A
i
A
∞
A
j
σ
ij
σ
i
σ
j
commute.
By “minimal”, we mean if
A
0
∞
is another structure with this property, then
there is a unique inclusion map A
∞
→ A
0
∞
such that for any i ∈ I, the maps
A
i
A
∞
A
0
∞
σ
i
σ
0
i
Example.
The colimit of a family of sets is obtained by taking the union of all
of them, and then identifying x ∼ σ
ij
(x) for all x ∈ A
i
and i ≤ j.
The key observation is the following:
Every structure is a direct limit of its finitely generated substructures,
with the maps given by inclusion.
We will neither prove this nor make this more precise, but it will be true for the
different kinds of structures we are interested in. In particular, for a poset, a
finitely generated substructure is just a finite suborder, because there are no
function symbols to “generate” anything in the language of posets.
To prove Ehrenfeucht–Mostowski, we construct a model satisfying the state-
ment of Ehrenfeucht–Mostowski as the direct limit of structures indexed by finite
subset of I:
{M
s
: s ∈ P(I)}
and when
s ⊆ t ∈ P
(
I
), we have an elementary embedding
M
s
→ M
t
. We
then note that if all the
σ
ij
are elementary, then the
σ
i
:
A
i
→ A
∞
are also
elementary. In particular, if each M
s
are models of our theory, then so is A
∞
.
We start by picking any infinite model
M
of
I
. By standard compactness
arguments, we may wlog there is no last
4
-thing in
M
, and also that
J
=
{x
:
P
(
x
)
}
is infinite. We pick
U
an ultrafilter on
J
that contains all terminal
segments of
4
. Since
J
does not have a last element, this is a non-principal
ultrafilter.
We now write
L(M) = M
|J|
/U.
We will define
M
s
= L
|s|
(M).
In particular, M
∅
= M.
To construct the embedding, we consider the following two classes of maps:
(i)
For any structure
M
, there is a map
K
=
K
(
M
) :
M → L
(
M
) given by
the constant embedding.
(ii) If i is an embedding from M into N , then there is an embedding
L(i) : L(M) → L(N ).
which is “compose with i on the right”.
It is easy to see that both of these maps are elementary embeddings, where
we require
i
to be elementary in the second case. Moreover, these maps are
compatible in the sense that the following diagram always commutes:
M N
L(M) L(N )
i
K(M) K(N )
L(i)
We now further consider the functions
head
and
tail
defined on finite linear orders
by
head(a
1
< · · · < a
n
) = a
1
tail(a
1
< · · · < a
n
) = a
2
< · · · < a
n
.
We can now define the embeddings recursively. We write
I
(
s, t
) for the desired
inclusion from M
s
into M
t
. We set
– If s = t, then I(s, t) is the identity.
– If head(s) = head(t), then I(s, t) is L(I(tail(s), tail(t))).
– Otherwise, I(s, t) is K ◦ I(s, tail(t)).
By our previous remark, we know these are all elementary embeddings, and that
these maps form a commuting set. Thus, we obtain a direct limit M
∞
.
Now we want to produce a copy of
I
in the direct limit. So we want to
produce a copy of
s
in
M
s
for each
s
, such that the maps preserve these copies.
It suffices to be able to do it in the case
|s|
= 2, and then we can bootstrap it
up by induction, since if
|s| >
3, then we find two sets of
s
of order
< |s|
whose
union gives
s
, and compatibility means we can glue them together. To ensure
compatibility, we pick a fixed element
x ∈ L
(
M
), and set this as the desired
element in
M
s
whenever
|s|
= 1. It then suffices to prove that, say, if 0
<
1,
then
I
(
{
0
}, {
0
,
1
}
)(
x
)
< I
(
{
1
}, {
0
,
1
}
)(
x
). It is then a straightforward exercise
to check that
x = [λp.p] ∈ L(M) = M
|P |
/U
works.
Once we have done this, it is immediate that the copy of
I
in the direct limit
is a family of indiscernibles. Indeed, we simply have to check that the copy of
s
in
M
s
is a family of indiscernibles, since every formula only involves finitely
many things. Then since the inclusino of
M
s
into
M
is elementary, the result
follows.