502 – Notes on compactness

The goal of this note is to present a proof of the following fundamental result. A theory is said to be satisfiable iff there is a model of

Theorem 1 (Compactness) Let be a first order theory. Suppose that any finite subtheory is satisfiable. Then itself is satisfiable.

 

As indicated on the set of notes on the completeness theorem, compactness is an immediate consequence of completeness. Here I want to explain a purely semantic proof, that does not rely on the notion of proof.

The argument I present uses the notion of ultraproducts. Although their origin is in model theory, ultraproducts have become an essential tool in modern set theory, so it seems a good idea to present them here. We will require the axiom of choice, in the form of Zorn’s lemma.

The notion of ultraproduct is a bit difficult to absorb the first time one encounters it. I recommend working out through some examples in order to understand it well. Here I confine myself to the minimum necessary to make sense of the argument.

502 – Compactness

First, two exercises to work some with the notion of ultrapower: Check that whenever is a nonprincipal ultrafilter on the natural numbers, and

1. for all or
2. 

Our argument for compactness required the existence of nonprincipal ultrafilters. One might wonder whether this is a necessity or just an artifact of the proof. It is actually necessary. To see this, I will in fact show the following result as a corollary of compactness:

Theorem.  If is a nonprincipal filter on a set then there is a nonprincipal ultrafilter on that extends

(Of course, this is a consequence of Zorn’s lemma. The point is that all we need is the compactness theorem.)

Proof. Consider the language Here, each is a constant symbol, is another constant symbol, and is a symbol for a binary relation (which we will interpret below as membership).

In this language, consider the theory A model of this theory would look a lot like except that the natural interpretation of in namely, is no longer nonprincipal in , because is a common element of all these sets.

Note that there are indeed models of thanks to the compactness theorem.

If let and note that is a nonprincipal ultrafilter over that contains

502 – Propositional logic (3)

Example 13 is a tautology. This is an example of De Morgan’s laws.

 

Example 14 is a tautology.

 

Definition 19 A formula is satisfiable iff there is some valuation such that Otherwise, we say that is contradictory, or unsatisfiable.

 

Remark 7 is unsatisfiable iff is a tautology.

 

Example 15 is not a tautology, but it is satisfiable.

 

Definition 20 If is a valuation and is a set of formulas, iff for all For a given if there is such a valuation we say that is satisfiable, or has a model, and that is a model of Otherwise, is unsatisfiable or contradictory.

580 -Cardinal arithmetic (11)

4. Strongly compact cardinals and

 

Definition 1 A cardinal is strongly compact iff it is uncountable, and any -complete filter (over any set ) can be extended to a -complete ultrafilter over

 

The notion of strong compactness has its origin in infinitary logic, and was formulated by Tarski as a natural generalization of the compactness of first order logic. Many distinct characterizations have been found.