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.
Best Answer
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:
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:
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:
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.