2Model theory
III Logic
2.2 Products
In model theory, we would often like to produce new models of a theory from
old ones. One way to do so is via products.
We will use λ-notation to denote functions.
Definition
(Product of structures)
.
Suppose
{A
i
}
i∈I
is a family of structures
of the same signature. Then the product
Y
i∈I
A
i
has carrier set the set of all functions
α : I →
[
i∈I
A
i
such that α(i) ∈ A
i
.
Given an
n
-ary function
f
in the language, the interpretation in the product
is given pointwise by
f(α
1
, · · · , α
n
) = λi.f(α
1
(i), · · · , α
n
(i)).
Relations are defined by
ϕ(α
1
, · · · , α
n
) =
^
i∈I
ϕ(α
1
(i), · · · , α
n
(i)).
The natural question to ask is if we have a model of a theory, then is the
product a model again? We know this is not always true. For example, the
product of groups is a group, but the product of total orders is not a total order.
We say a product preserves a formula ϕ if
Y
i∈I
A
i
ϕ ⇐⇒ ∀
i∈I
, A
i
ϕ
What sort of things do products preserve? As we know from undergraduate
mathematics, theories such as groups and rings are preserved.
Definition
(Equational theory)
.
An equational theory is a theory all of whose
axioms are of the form
∀
x
(w
1
(x) = w
2
(x)),
where w
i
are some terms in x.
It is not hard to see that models of equational theories are preserved under
products.
It turns out actually the class of things preserved by products is much more
general.
Definition
(Horn clause)
.
A Horn clause is a disjunction of atomics and
negatomics of which at most one disjunct is atomic.
It is usually better to think of Horn clauses as formulae of the form
^
ϕ
i
→ χ
where
ϕ
i
and
χ
are atomic formulae. Note that
⊥
is considered an atomic
formula.
A universal Horn clause is a universal quantifier followed by a Horn clause.
Example.
Transitivity, symmetry, antisymmetry, reflexivity are all universal
Horn clauses.
Proposition. Products preserve (universal) Horn formulae.
Proof. Suppose every factor
A
i
∀
x
^
ϕ
i
(x) → χ(x).
We want to show that the product believes in the same statement. So let
(
f
1
, · · · , f
k
) be a tuple in the product of the right length satisfying the antecedent,
i.e. for each n ∈ I, we have
A
n
ϕ
i
(f
1
(n), · · · , f
k
(n))
for each i, But then by assumption,
A
n
χ(f
1
(n), · · · , f
k
(n))
for all n. So the product also believes in ϕ
j
(f
1
, · · · , f
n
). So we are done.
Reduced products
Unfortunately, it is rarely the case that products give us new interesting models.
However, reduced products do.
Reduced products arise from having a filter on the index set.
Definition
(Filter)
.
Let
I
be a set. A filter on
I
is a (non-empty) subset
F ⊆ P
(
I
) such that
F
is closed under intersection and superset. A proper filter
is a filter F 6= P(I).
The intuition to hang on to is that F captures the intuition of “largeness”.
Example.
Take
I
=
N
, and
F
the set of cofinite subsets of
N
, namely the sets
whose complement are finite, then F is a filter.
Similarly, we can take
F
to contain the set of naturals with asymptotic
density 1.
Example. Let
F = {x ⊆ N : 17 ∈ N}
Then this is a maximal proper filter.
This is a rather silly filter. We will see later that model-theoretically, these
give us uninteresting reduced products.
Definition (Principal filter). A principal filter is a filter of the form
F = {X ⊆ I : x 6∈ X}
for some x ∈ I.
We don’t tend to care about principal filter, as they are boring.
Definition
(Complete filter)
.
A filter
F
is
κ
-complete if it is closed under
intersection of < κ many things.
Example. By definition, every filter is ℵ
0
-complete.
Example. Principal filters are κ-complete for all κ.
A natural question is, are there any non-principal ultrafilters that are
ℵ
1
complete? It turns out this is a deep question, and a lot of the study of set
theory originated from this question.
Filters on
I
form a complete poset under inclusion, with top element given
by
F
=
P
(
I
). Moreover, the proper filters are a chain complete poset. Thus, by
Zorn’s lemma, there are maximal proper filters.
Definition (Ultrafilter). An ultrafilter is a maximal filter.
We saw that principal filters are ultra. Are there non-principal ultrafilters?
Fortunately, by Zorn’s lemma, they do exist.
Example.
By Zorn’s lemma, there is a maximal filter extending the cofinite
filter on N, and this is non-principal.
It turns out it is impossible to explicitly construct a non-principal ultrafilter,
but Zorn’s lemma says they exist.
Now we can get to reduced products.
Definition
(Reduced product)
.
let
{A
i
:
i ∈ I}
be a family of structures, and
F a filter on I. We define the reduced product
Y
i∈I
A
i
/F
as follows: the underlying set is the usual product
Q
A
i
quotiented by the
equivalence relation
α ∼
F
β ⇐⇒ {i : α(i) = β(i)} ∈ F
Given a function symbol
f
, the interpretation of
f
in the reduced product is
induced by that on the product.
Given a relational symbol ϕ, we define
ϕ(α
1
, · · · , α
n
) ⇐⇒ {i : ϕ(α
1
(i), · · · , α
n
(i))} ∈ F.
If
F
is an ultrafilter, then we call it the ultraproduct. If all the factors in an
ultraproduct are the same, then we call it an ultrapower.
It is an easy exercise to show that these are all well-defined. If we view the
filter as telling us which subsets of
I
are “large” then, our definition of reduced
product says we regard two functions in the reduced products as equivalent if
they agree on a “large” set.
Note that if our filter is principal, say
F
=
{J ⊆ I
:
i ∈ J}
, then the reduced
product is just isomorphic to A
i
itself. So this is completely uninteresting.
Reduced products preserve various things, but not everything. For example,
the property of being a total order is in general not preserved by reduced products.
So we still have the same problem.
But if the filter F is an ultrafilter, then nice things happen.
Theorem
(
L
o´s theorem)
.
Let
{A
i
:
i ∈ I}
be a family of structures of the same
(first-order) signature, and U ⊆ P (I) an ultrafilter. Then
Y
i∈I
A
i
/U ϕ ⇐⇒ {i : A
i
ϕ} ∈ U.
In particular, if A
i
are all models of some theory, then so is
Q
A
i
/U.
The key of the proof is the following lemma, which is a nice exercise:
Lemma. Let F be a filter on I. Then the following are equivalent:
(i) F is an ultrafilter.
(ii) For X ⊆ I, either X ∈ F or I \ X ∈ F (“F is prime”).
(iii) If X, Y ⊆ I and X ∪ Y ∈ I, then X ∈ I or Y ∈ I.
With this in mind, it is hard not to prove the theorem.
Let’s now look at some applications of Lo´s theorem.
Recall the compactness theorem of first order logic — if we have a theory
T
such that every finite subset of
T
has a model, then so does
T
. The way
we proved it was rather roundabout. We proved the completeness theorem of
first order logic. Then we notice that if every finite subset of
T
has a model,
then every finite subset of
T
is consistent. Since proofs are finite, we know
T
is
consistent. So by completeness, T has a model.
Now that we are equipped with ultraproducts, it is possible to prove the
compactness theorem directly!
Theorem
(Compactness theorem)
.
Let
T
be a theory in first order logic such
that every finite subset has a model. Then T has a model.
Proof.
Let ∆ be such a theory. Let
S
=
P
ℵ
0
(∆) be the set of all finite subsets
of ∆. For each s ∈ S, we pick a model M
s
of s.
Given s ∈ S, we define
X
s
= {t ∈ S : s ⊆ t}.
We notice that
{X
s
:
s ∈ S}
generate a proper filter on
S
. We extend this to
ultrafilter U by Zorn’s lemma. Then we claim that
Y
s∈S
M
s
/U ∆.
Indeed, for any ϕ ∈ ∆, we have
{s : M
s
ϕ} ⊇ X
{ϕ}
∈ U.
Example.
Let
T
be the theory consisting of all first-order statements true in
hR,
0
,
1
,
+
, ×i
. Add to
T
a constant
ε
and the axioms
ε <
1
n
for all
n ∈ N
. Then
for any finite subset of this new theory,
R
is still a model, by picking
ε
small
enough. So by the compactness theorem, we know this is consistent.
Using our proof of the compactness theorem, we now have a “concrete” model
of real numbers with infinitesimals — we just take the ultraproduct of infinitely
many copies of R.