Compactness

As almost the last thing in almost my last lecture a week or so ago, one of the highlights was the Compactness Theorem for first-order logic together with some of its consequences (sucuh as the upward Löwenheim–Skolem theorem).

Some of the students who had met complactness in the Topology module were interested to know how the connection worked. There wasn’t time within the lectures to explain this in detail, so I will have a go here.

I will stick to propositional logic since the situation is simpler and clearer.

Logic: syntax and semantics

In propositional logic, we have a set P of propositional variables which can take the values T (true) or F (false). Formulae are built from propositional variables by combining them with connectives, typically → (implies) and ¬ (not). A valuation is an assignment of values to the variables; by the usual truth table rules, it assigns values to the formulae.

A set Σ of formulae is said to be satisfiable if there is a valuation which gives the value T to every formula in Σ.

There is also a deduction system for propositional logic, which comes into the argument. A set of formulae are designated as axioms; there is a single rule of inference, namely Modus Ponens (MP), which allows B to be deduced from A and (A→B).

A proof of a formula A from a set Σ in the deductive system is a sequence of formulae such that each formula in the sequence is an axiom, a member of Σ, or deduced from earlier formulae in the sequence by MP.

Now the set Σ of formulae is said to be consistent if no contradiction can be deduced from it.

The Soundness and Completeness Theorem asserts that a set of formulae is satisfiable if and only if it is consistent. The forward direction is easier; we only need to ensure that the axioms are tautologies (take the value T for all valuations) and that MP preserves the value T. The converse requires us to construct a valuation satisifying a consistent set of formula, which involves enlarging our set to a maximal consistent set Σ*, and showing that the function which is T on elements of Σ* is a valuation.

Clearly the truth of this theorem depends on the choice of deduction system. But it has consequences for the semantics, which make no mention of deduction,

There is a hidden difficulty here, which I will come to later.

Compactness

The Compactness Theorem for this logical system states the following:

Theorem A set of formulae is satisfiable if and only if every finite subset is satisfiable.

The proof uses the existence of a sound and complete deduction system: it suffices to prove that a set Σ of formulae is consistent if and only if every finite subset is consistent. The forward direction is clear, so suppose that every finite subset is consistent, but a contradiction could be deduced from Σ. Since proofs are finite strings of formulae, only finitely many formulae from Σ can be quoted in the proof, so there is an inconsistent finite subset of Σ, contrary to hypothesis.

This already has consequences for mathematics, for example the theorem that a graph can be properly coloured with a fixed finite number k of colours if and only if every finite subgraph can be properly coloured with k colours.

How is this connected with topology?

Our proof of compactness used soundness and completeness, but the statement does not refer to the deductive system at all. Is there a proof not depending on soundness and completeness?

Indeed there is, and it depends on Tychonoff’s Theorem in topology, according to which a product of compact topological spaces is compact. Now consider the set of all valuations of our first-order logic. Eacch valuation is determined by its values on the propositional variables, so the set of valuations is bijective with the Cartesian product over P of copies of {T,F}. So it is a topological space, with the product topology inherited from the discrete topology on {T,F}. The definition of this is that the basic open sets are sets of valuations taking prescribed values on finite subsets of P. By Tychonoff’s Theorem, this space V is compact.

Now suppose that Σ is an unsatisfiable set of formulae. For each formula A in Σ, let V(A) be the set of valuations giving A the value F. Since A only contains finitely many variables, this is an open set; and, by the assumption that Σ is unsatisfiable, V is the union of these open sets, which thus form an open cover. By compactness, there is a finite subcover; that is, a finite subset Σ₀ such that the corresponding open sets cover V. This means that every valuation gives some formula A in the set Σ₀ the value F. So some finite subset of Σ is not satisfiable. This proves the logical Compactness Theorem.

Set theory

If you have studied topology, I hope you are aware that the proof of Tychonoff’s Theorem uses the Axiom of Choice (AC). There was a hint of this in the observation that the proof of the Completeness Theorem involves choosing a set maximal with respect to some property.

But, as it turns out, the Propositional Compactness Theorem is strictly weaker than the Axiom of Choice. It is equivalent to a principle called the Boolean Prime Ideal Theorem (BPIT). (AC) is equivalent to the statement that every set can be well-ordered; on the other hand, (BPIT) implies the weaker statement that every set can be totally ordered. (Exercise: Prove this: translate the existence of a total order into a condition on a set of propositional variables indexed by distinct pairs of elements of the set.)

Boolean rings

Boolean rings (and the equivalent Boolean algebras) arose from George Boole’s program to turn logic into a branch of algebra.

Take P to be a set of propositional variables. Call two formulae equivalent if their truth values under every valuation are equivalent. Let R(P) be the set of equivalence classes of formulae.

Now define two operations + and · on R(P) by the rules that [A]+[B] = [(AB)] and [A]·[B] = [(A∧B)]. These operations make R(P) into a ring satisfying the equation x² = x. Such a ring is called a Boolean ring. Any quotient is also a Boolean ring. So if (Σ) denotes the ideal generated by a set Σ of formulae, then R(P)/(Σ) is a Boolean ring. It can be shown that, if every finite subset of Σ is satisfiable, then the element 1 (corresponding to a contradiction) cannot be expressed as a finite combination of elements in Σ. If we assume that every Boolean ring has a prime (or maximal) ideal, then Σ is contained in such an ideal. Now it is not hard to prove that, if I is a maximal ideal, then for any formula A, either [A] or (1+[A]) belongs to I; so mapping formula in I to T and the others to F is a valuation, and clearly it makes all formulae in Σ true.

The statement that every Boolean ring has a maximal ideal is (BPIT). So this set-theoretic principle, weaker than (AC), suffices to prove the propositional compactness theorem.

Final note

We noted that some set-theoretic principle is required to prove propositional compactness. One can work more locally.

If the set P of propositional variables can be well-ordered (in particular, if it is finite or countable), then the proof of the soundness and completeness theorem goes through, and so propositional compactness holds for P.

I assume that a weaker condition on P suffices for propositional compactness over P. But I have not thought about this, and have gone on long enough.