Compactness Theorem explanation

Question

Compactness Theorem definition:

If $T$ is a theory in a first-order language $L$, then $T$ has a model iff every finite subset $S$ of $T$ has a model.

A number of questions regarding this definition.

1. As I understand, the statement “has a model” means that there is at least one combination, when $T$ returns TRUE, am I right?

2. If the answer to the first question is “Yes”, I'm right, then why should we deal with “every finite subset” and proof, that every finite subset returns TRUE, why we just can't to be satisfied with one subset (= at least one), which returns TRUE, why should we be assure, that every finite subset returns TRUE?

3. If I'm not right, so what exactly means “has a model”?

Answer 1

Mike, I think Clive is correct that you may be thinking in terms of propositional logic (a.k.a. sentential logic). In propositional logic there is a set of sentence symbols $S=\{X_0,X_1,X_2,\ldots\}$, a set $\bar S$ of well-formed formulas (or wffs), and a function called a truth assignment $v:S \rightarrow \{F,T\}$ telling us whether a particular symbol $X_i$ is true or false. This function extends to $v:\bar S \rightarrow \{F,T\}$ telling us whether a particular formula is true, essentially by plugging in truth values and seeing if the formula combines them correctly. (Hopefully this is the context that you're thinking of.)

(1) In general we don't speak of models when we discuss propositional logic. Instead, you say that a theory $\Sigma$ is satisfiable if there is a truth assignment $v$ such that for every formula $\varphi \in \Sigma$, we have $v(\varphi)=T$. Such a truth assingment satisfies $\Sigma$. You might rephrase the compactness theorem as follows:

If $\Sigma$ is a theory of propositional logic, then $\Sigma$ is satisfiable if every finite subset of $\Sigma$ is satisfiable.

In first-order logic, saying that a theory is satisfiable is the same as saying it has a model. (This fact is called the completeness theorem.)

(2) It's true that we are only looking for one truth assignment, but the subsets we are looking at are subsets of variables. For example, suppose we are working with infinitely many variables $\{S_n:n \in \mathbb N\}$ and $\Sigma_n$ is the set of formulas in $\Sigma$ with only the variables $S_1,\ldots,S_n$. Then the compactness theorem tells us that if $\Sigma_n$ is satisfiable for every $n \in \mathbb N$, then there is a truth assignment satisfying all of $\Sigma$.

(3) The definition of a model is a bit elaborate if you haven't seen it before, but there are some good lecture notes explaining sentential logic and first-order logic here: http://www.math.uiuc.edu/~vddries/main.pdf.

Answer 2

To say that a set $S$ of sentence "has a model" means that there is an interpretation to the language, $\mathcal M$ such that for every $\varphi\in S$, $M\models\varphi$ or in other words, there is a structure to the language in which all the sentences in $S$ are satisfied.

I'm not sure if that is what you have meant by "at least one combination where $T$ returns TRUE", so I can't quite say if that is the same thing or not.

But I should point out that "true" is a semantic meaning. It is the truth value of a sentence, or a formula, in a particular interpretation - or structure - under a given assignment to the free variables (for sentences the assignment is irrelevant, of course).

So a theory $T$ does not "return TRUE" because it is not a function. It is a set of sentences.

Finally, the compactness theorem says that $T$ has a model if and only if every finite subset of $T$ has a model. If $T$ has a model, then clearly all its subsets have models; so the other direction is the non-trivial one.

And it is important that we say all subsets because the empty set is always a subset of $T$ and every structure is a model for the empty set.