confusion regarding compactness theorem

Question

I am getting somehow confused of compactness theorem.

The compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful method for constructing models of any set of sentences that is finitely consistent.

I am not sure if I am mistaken, but what it basically seems to say is that if every finite subset of a set of first-order sentences has a model that assigns truth of the sentences, then the set would definitely have a model.

What's the point of having compactness theorem, when you basically have to find that every finite subset has a model? There are at least $\aleph_0$ subsets.

The next question: Aren't there only $\aleph_0$ first-order sentences, as each sentence is finite-sized?

And how can we not construct a model of any set of some sentences, when what we can just do is arbitrarily assign each sentence as true or false? (Edit: so, I am asking, what's the point of referring to every finite subset?)

And finitely consistent? What does this mean?

Edit: I know that for any set of some sentences, models for the set can differ in their domain - that is components.

Answer 1

The Compactness Theorem is usually in the context of First-Order Logic. Formulas in first order logic are always finite. However, there are quantifiers.

Often it is not difficult to prove that every finite subset of a theory has a model.

For instance, consider the language and theory of arithmetics. One wants to prove that there is a model of arithmetics where there is an element that is not the finite successor of $0$. So add to the theory of arithmetics the sentences

$\Phi_n \equiv \neg(c = S( \cdots (S(0)))$ where there are $n$ application of $S$.

Any finite subset of the this new theory has a model; just the the regular natural numbers and interpret $c$ to be a number bigger than $n$. So every finite subset has a model, so by the compactness theorem there exists a model that satisfies all the original arithmetics axioms and there exists a $c$ which is not $S^n(0)$ for any $n$.

This produces a nonstandard model of arithmetics. On the other hand , $\omega + \mathbb{Z}\mathbb{Q}$ is also a nonstandard model of arithmetics. However in some situations, it is not easy to concretely make a model of a theory.

Remark: A $\mathcal{L}$ structure or model of a first order theory is not just an arbitrary assignment of T or F to sentence. I suggests looking in $\textit{Model Theory: an Introduction}$ by David Marker so see the definition of a $\mathcal{L}$-structure.

Answer 2

Consider the axioms $A$ for an ordered field; they are satisfied, most familiarly, by $\Bbb Q$ and $\Bbb R$ with their usual arithmetic operations and linear orders. Now add a constant symbol $c$, and for each positive integer $n$ let $\sigma_n$ be the sentence $$0<c\;\land\;\underbrace{c+c+\ldots+c}_{n\text{ times}}\le 1\;.$$

To find a model for any finite subset $F$ of $T=A\cup\{\sigma_n:n\in\Bbb Z^+\}$, start with $\Bbb Q$ with its usual operations and order, let $m=\max\{n\in\Bbb Z^+:\sigma_n\in F\}$, and interpret $c$ as $1/m$. This model satisfies every sentence in $A\cup\{\sigma_n:1\le n\le m\}$ and hence every sentence in $F$. In other words, $T$ is finitely consistent: this simply means that every finite subset of $T$ is consistent. (Actually, what I’ve really shown here is that $T$ is finitely satisfiable: every finite subset of it has a model. To say that $T$ is finitely consistent is, propertly speaking, to say that every finite subset of it is consistent, meaning that a contradiction cannot be derived from any finite subset of $T$. In this context the two are equivalent.)

Now consider the entire set $T$ of sentences. There is no way to interpret $c$ in either $\Bbb Q$ or $\Bbb R$ so as to get a model of the theory $T$, because neither $\Bbb Q$ nor $\Bbb R$ contains a positive number $r$ such that $nr\le 1$ for all positive integers $n$. Any object simultaneously satisfying $\sigma_n$ for all $n\in\Bbb Z^+$ must be a positive infinitesimal, something that doesn’t exist in the standard rational or real numbers. None the less, the compactness theorem assures us that $T$ does have a model: there is some ordered field that does contain at least one positive infinitesimal. This is by no means obvious, and actually constructing such a field is a non-trivial task, so in this case the compactness theorem is giving us a non-trivial conclusion for a very small amount of work.

Added: The compact theorem can also sometimes be used in reverse, so to speak. The simplest case of the infinite Ramsey theorem says:

Let $G$ be the infinite graph whose vertex set is $\Bbb N$ and that has an edge joining $m$ and $n$ whenever $m,n\in\Bbb N$ with $m\ne n$. (In other words, $G$ is the complete graph on $\omega$ vertices.) Color each edge of $G$ either red or blue. Then there is an infinite $A\subseteq\Bbb N$ such that all of the edges joining vertices in $A$ are the same color.

There is a very easy proof of this result using a free ultrafilter. We can use that easy result and the compactness theorem to prove the corresponding finite Ramsey theorem:

For each $n\in\Bbb Z^+$ there is an $r(n)\in\Bbb Z^+$ such that if $m\ge r(n)$, and each edge of $K_m$, the complete graph on $m$ vertices, is colored either red or blue, then there is a set $A$ of $n$ vertices of $K_m$ such that all of the edges between vertices in $A$ are the same color. Such a set $A$ of vertices is said to be monochromatic.

Let $B$ and $R$ be $2$-place relation symbols, and consider the following sentences:

$$\left\{\begin{align*} &\forall x\Big(\lnot B(x,x)\land\lnot R(x,x)\Big)\\ &\forall x,y\Big(B(x,y)\leftrightarrow B(y,x)\Big)\\ &\forall x,y\Big(R(x,y)\leftrightarrow R(y,x)\Big)\\ &\forall x,y\Big(x\ne y\to B(x,y)\lor R(x,y)\Big)\\ &\forall x,y\Big(\lnot\big(B(x,y)\land R(x,y)\big)\Big) \end{align*}\right.\tag{1}$$

Any model of $(1)$ can be thought of as a complete graph with each edge colored either red or blue: $B(x,y)$ is then interpreted as ‘the edge between $x$ and $y$ is blue’, and $R(x,y)$ as ‘the edge between $x$ and $y$ is red’.

Now for each $m\in\Bbb Z^+$ let $\varphi_m$ be the sentence $$\exists x_1\exists x_2\dots\exists x_m\left(\bigwedge_{1\le i<k\le m}x_i\ne x_k\right)\;;$$ $\varphi_m$ says that there are at least $m$ vertices. Finally, let $\psi$ be the rather ugly sentence

$$\forall x_1\forall x_2\dots\forall x_n\left(\bigwedge_{1\le i<k\le n}x_i\ne x_k\to\bigvee_{{1\le i<j\le n}\atop{1\le k<\ell\le n}}\Big(B(x_i,x_j)\land R(x_k,x_\ell)\Big)\right)\;;$$

$\psi$ says that if $A$ is any set of $n$ distinct vertices, there are two pairs of vertices in $A$ such that one pair are joined by a blue edge and the other by a red edge.

Suppose that this version of the finite Ramsey theorem is false. Then there is some $n\in\Bbb Z^+$ such that for all $m_0\in\Bbb Z^+$ there is an $m\ge m_0$ such that the edges of $K_m$ can be colored red and blue in such a way that no set of $n$ vertices of $K_m$ is monochromatic. This means that every finite subset of the axioms in $(1)$, $\psi$, and the sentences $\varphi_m$ is satisfiable. The compactness theorem then says that $(1)$, $\psi$, and the sentences $\varphi_m$ are all simultaneously satisfiable. But any model of this set of sentences would be a complete graph with infinitely many vertices (because of the $\varphi_m$) whose edges have been colored blue and red in such a way that no set of $n$ vertices is monochromatic (because of $\psi$). This contradicts the infinite Ramsey theorem, showing that the finite Ramsey theorem must be true.

This probably seems very roundabout, but once one is accustomed to using the compactness theorem, the argument is very straightforward and might intelligibly be shortened to this:

Suppose that there is some $n$ for which the finite Ramsey theorem fails. Then there are arbitrarily large counterexamples, complete graphs with red and blue edges in which no set of $n$ vertices is monochromatic. By compactness there is an infinite counterexample, contradicting the infinite Ramsey theorem.

---

I should probably mention that the finite Ramsey theorem can be proved directly in a way that actually gives a crude bound on $r(n)$. This proof isn’t particularly hard, but for someone already familiar with free ultrafilters and compactness arguments it’s a little harder than the argument given above.