Compactness in model theory

This is the second in a series of posts about model theory.

Last time we discussed the limitations of mathematical logic and how it leads to many worlds of mathematics, regardless of whatever system of rules we choose. This time, we will discuss a theorem known as compactness which allows us to do some powerful things in mathematics, as well as demonstrate some more limitations of first order logic.

To motivate this, let’s start with a theorem:

If every finite subgraph of an infinite graph is $k$-colorable, then the entire graph is $k$-colorable.

At first glance this is not obvious. But with compactness, we will be able to show this very easily.

Terminology

Before we dive into compactness, let me first informally define some terminology.

1. A theory is a set of rules. It is a purely syntactic object.
2. A model of a theory is a concrete mathematical object that satisfies the theory’s rules.

For example, the vector space axioms form the theory of vector spaces, and $\mathbb R^3$ is a model of this theory.

Compactness

Suppose we have an inconsistent theory. That means we may derive a contradiction. The important thing about a contradiction is that it is finite, as it is a proof of a false statement, and every proof is a finite sequence of steps. This means that the contradiction must reference a finite number of rules.

Therefore, if a theory is inconsistent, it has a finite inconsistent subtheory. Taking the converse of this statement, we get the following:

A theory is consistent if every finite subtheory is consistent.

How does this prove our theorem? Here is how we do it: given a graph $G$, we construct a theory that describes $k$-colorings of $G$. If it is consistent, then Godel’s Completeness says $G$ is $k$-colorable.

Let me be a little more descriptive: our theory describes functions from $V$ (the set of vertices of $G$) to the set ${1, \dots, k}$. For every edge $(u, v) \in E$ (the set of edges of $G$), we have the following rule: the color of $u$ must not equal the color of $v$ (more formally, $f(u) \neq f(v)$).

To show the consistency of this theory, we just need to show the consistency of every finite subtheory. Each finite subtheory only references a finite number of vertices, say $S$. And by assumption, the finite subgraph $S$ is $k$-colorable, so the finite theory has a model. Therefore, it must be consistent.

And we have just proved the theorem!

Upwards Lowenheim-Skolem

Aka: Blowing up models of a theory.

There is a theorem that roughly says the following:

If I have a theory $T$ and an infinite model $M$ of $T$, then I can construct a model $M'$ of $T$ that is as big as I wish.

Here is how you prove it: consider the theory $T'$ that consists of the rules in $T$, as well as some rules expressing “I have $\lambda$ many elements, and all of them are distinct.” (Here $\lambda$ is a cardinality.) The sentences we use to specify they are distinct is “element $c_i$ and element $c_j$ are not equal” for every pair of elements $c_i, c_j$ whose existences we mandate.¹

If we have a model of $T'$, then it is also a model of $T$ with $\lambda$ many elements. By Godel’s Completeness, we just need to show $T'$ is consistent. And by compactness, we just need to appeal to finite subtheories.

Note that any finite subtheory references a finite number of elements $c_i$. Therefore, all we need to do is have a finite number of distinct elements in our model of this finite subtheory. But since $M$ is infinite, it already does the trick.

Limitations of first-order logic

You may know about the Archimedean property of an ordered field, which states

A field $F$ is Archimedean if for every $x \in F$, there is some $n \in \mathbb N$ such that $n > x$.

In English, it states that for every element of the field, there is a larger natural number. Most ordered fields you know are Archimedean; think the rationals and reals.

In propositional logic, we can write things such as “$p \implies q$”. First-order logic allows us to access the entire universe of our model: for instance, if we are working in the theory of ordered fields, then we can write statements such as “for all elements $x$ in our field $F$, if $x$ is not $0$, then $x$ has an inverse; furthermore, that inverse has the same sign as $x$.”

The Archimedean property is what we call a “second-order property”. This is because we have two universes we are quantifying over: we are writing $\forall x \in F$, which is quantifying over $F$ (first-order), but then we have $\exists n \in \mathbb N$, and quantifying over $\mathbb N$ is not something you can do in first order logic.

You may try to express the Archimedean property in first order logic. You may even try to establish a theory with an infinite number of sentences that is equivalent to being Archimedean (i.e. if it is satisfied, then the ordered field is Archimedean, and if it is not satisfied, then the ordered field is not Archimedean). Both of these will fail. Is there a way to prove this?

It turns out Upwards Lowenheim Skolem gives us a very easy way to prove this. There is one important thing you need to know: every Archimedean field is isomorphic to a subfield of $\mathbb R$. In particular, this means that no Archimedean field has a bigger cardinality. Just take this fact for granted.

Great. Now assume for the sake of contradiction that there is some theory of Archimedean ordered fields. We have an infinite Archimedean ordered field: $\mathbb R$. Now blow it up to a model with cardinality larger than $|\mathbb R|$ that satisfies this theory, contradiction.

There are other properties that cannot be expressed in the language of first order logic. Two of them are the phrase “this field is algebraic” and “this ordering is a well-ordering”. And the way we prove neither of these are expressible is quite similar to the proof for the Archimedean property.