Proofs of the Compactness Theorem

Abstract

In this study, several proofs of the compactness theorem for propositional logic with countably many atomic sentences are compared. Thereby some steps are taken towards a systematic philosophical study of the compactness theorem. In addition, some related data and morals for the theory of mathematical explanation are presented.

Acknowledgements

I am grateful to Alan Baker, Andrew Arana, Wilfrid Hodges and two HPL referees for their helpful comments.

Notes

For an excellent introduction to intrinsicness or purity as an ideal of proof taking off from Aristotle see Detflesen 2008. Intrinsicness is semantic purity in the sense of Arana ( 2008 ).

Some brief history and bibliography (see Dawson 1993 for more on the history of the compactness theorem): Henkin 1949 is the basis for the so-called Henkin proof. Gödel 1930 contains the first published statement of the compactness theorem. The topological proof is found in various versions in the literature, e.g. in Burris and Sankappanavar 1981 , which also presents the ultraproduct proof offered here. The topological proof is an instance of a more general proof due to Marshall Stone. So far as I am aware, the combinatorial proof is folklore and not due to any particular author. The ultraproduct proof is a corollary of Łoś's theorem, due in essence to Jerzy Łoś. Needless to say, there are more proofs of PL(ω)'s compactness than those mentioned here.

A more constructive argument for the existence of Γ^max goes as follows. Let {A_i } _i ∊ ω be a (denumerable) enumeration of the set of sentences of PL(ω). Given a finitely satisfiable set of sentences Γ, define the (denumerable) sequence of sets {Γ _i } _i ∊ ω recursively as follows: Γ₀ = Γ; Γ _n + 1 = Γ _n ∪{A_n } if every finite subset of Γ _n ∪{A_n } is satisfiable, and Γ _n + 1 = Γ _n if some finite subset of Γ _n ∪{A_n } is unsatisfiable. We set Γ^max = ∪ _i ∊ ω{Γ _i }.

The falsum may either be a primitive symbol of the language or abbreviate an arbitrary contradiction.

Compare the first paragraph of Henkin 1949 for the motivation for the analogous proof of completeness.

Where the variable X is k-adic. A k-ary property of the domain D is a subset of D^k .

By ‘indefinable’ we mean indefinable in the augmented language.

Here, I disagree with Resnik and Kushner ( 1987 , pp. 149–150), but this is not the place to engage with their compressed discussion.

A cover of a topological space T is a set of open sets {O_i } _i ∊ I such that T = ∪ _i ∊ I {O_i }.

A homeomorphism between topological spaces is a continuous bijection with continuous inverse.

For a proof of Tychonoff's Theorem see e.g. Royden 1988 , pp. 196–198.

The proper class {m ∊ ℳ¹: m⊧φ} is often written ‘Mod(φ)’. This is a topology since U(φ₁) ∩ U(φ₂) = {m ∊ ℳ¹: m⊧φ₁} ∩ {m ∊ ℳ¹: m⊧φ₂} = {m ∊ ℳ¹: m⊧φ₁∧φ₂} = U(φ₁∧φ₂).

By definition, [m]⊧_⋍φ iff ∃m∗ ∊ [m] s.t. m∗⊧φ. The topology is a projection onto ℳ¹/⋍ of the topology on ℳ¹.

Of course, we have also used the fact that sentences of the logic form a Boolean algebra.

The domain of ℳ²/⋍² is the domain ℳ² of models of second-order logic quotiented by second-order equivalence, symbolised here by ‘⋍²’ Two models in ℳ² are in the same ⋍²-equivalence class iff they satisfy the same second-order sentences.

Since N_a  ∩ N_b  = {U ∊ B∗: a ∊ U} ∩ {U ∊ B∗: b ∊ U} = {U ∊ B∗: a∧b ∊ U}, where a∧b is the meet of a and b in B, the N_a are a base for this topology.

If Γ⊧ _L ⊥ then Γ contains a sentence γ whose interpretation in the standard model of arithmetic is false, hence γ⊧ _L ⊥.

We go round full circle by noting that the BPI for the algebra of PL(κ)'s sentences is equivalent to the completeness of PL(κ). Given a deductive system or an equivalence relation ‘≡’ on the set of sentences, we define one in terms of the other by:

We may then verify that the set of sentences quotiented by ≡ is a nontrivial algebra iff ⊢ is consistent.

Following the analogy with topology: a topological space such that any cover for it has a countable subcover is known as a Lindelöf space.

Consider the tree consisting of λ-many disjoint branches of size κ_i < κ where sup {κ _i : i < λ} = κ, for λ = cf(κ) < κ.

For the argument, see e.g. Jech 2003 , pp. 116–117.

For more details of the proof of Cowen's Lemma, which uses Tukey's Lemma, see Cowen 1977 .

There are many other combinatorial proofs of compactness, for instance another by Cowen ( 1970 ) based on a combinatorial lemma due to Rado ( 1949 ).

Keisler had a vested interest, given that he is responsible for a high proportion of the model-theoretic applications of ultraproducts. The use of ultraproducts is now less fashionable in model theory.

Reflexivity and symmetry are immediate, and transitivity follows from the conjunction and containment properties.

In fact, Dom(Π _i ∊ I (A_i )/U) has cardinality 2^ℵ₀ (see Bell and Slomson 1969, pp.127–129).

Ded (F) = _def∀x∀y∀z((F(x) = z∧F(y) = z) →x = y) ∧∃x∀y¬(x = F(y)).

Suppose φ = ¬ψ and that the theorem holds for ψ. Then π _U (φ) = π _U (¬ψ) = 1−π _U (ψ), and π _U (ψ) = 1 iff {i ∊ I: A_i (ψ) = 1} ∊ U by the inductive hypothesis. The result follows from the fact that {i ∊ I: A_i (ψ) = 1}∉U iff I/{i ∊ I: A _i(ψ) = 1} ∊ U since U is an ultrafilter. This is the only step, either in this proof or in that of Łoś’s theorem for the first-order case, that requires U to be an ultrafilter rather than just a filter. If φ = ψ₁∧ψ₂ then π _U (φ) = 1 iff π _U (ψ₁) = π _U (ψ₂) = 1 iff {i ∊ I: A_i (ψ₁) = 1} ∊ U and {i ∊ I: A_i (ψ₂) = 1} ∊ U, by the inductive hypothesis. If {i ∊ I: A_i (ψ₁) = 1} ∊ U and {i ∊ I: A_i (ψ₂) = 1} ∊ U then {i ∊ I: A_i (ψ₁∧ψ₂) = 1} ∊ U, since {i ∊ I: A_i (ψ₁∧ψ₂) = 1} = {i ∊ I: A_i (ψ₁) = 1} ∩ {i ∊ I: A_i (ψ₂) = 1} and U is closed under intersection. The other direction follows from the fact that if {i ∊ I: A_i (ψ₁∧ψ₂) = 1} ∊ U then {i ∊ I: A_i (ψ₁) = 1} ∊ U and {i ∊ I: A_i (ψ₂) = 1} ∊ U, since U is closed under upward containment and {i ∊ I: A_i (ψ₁∧ψ₂) = 1} is contained in both {i ∊ I: A_i (ψ₁) = 1} and {i ∊ I: A_i (ψ₂) = 1}.

Usually with the condition κ ≥ λ.

No extension of first-order logic with a quantifier of the form ‘Q _ℵα ’ or ‘Q _>ℵα ’ or ‘Q _<ℵα or ‘Q _≤ℵα ’ or ‘Q _≥ℵα ’ can be compact (where ‘Q _ℵα xφ’ is interpreted as ‘there are ℵ_α xs satisfying φ’, and so on). However, such logics tend to satisfy weaker notions of compactness, e.g. the logic obtained by adding ‘Q _>ℵ0 ’ to first-order logic is (ℵ₁, ℵ₀)-compact. The completeness proof generalises to this logic: as Keisler ( 1970 ) proved, this logic is ℵ₁-complete, that is to say, there is a deductive system such that if Γ is a set of sentences of cardinality < ℵ₁ then Γ⊧δ iff Γ⊢δ.

See e.g. Jech 2003 , pp. 120–121 and pp. 292–295. Such cardinals are also known as weakly compact, that is, they satisfy the partition property κ→ (κ)². This is the usual definition of weak compactness; it then comes by way of a theorem that a weakly compact cardinal satisfies the Weak Compactness theorem.

See Jech 2003 , pp. 365–366, for the proof.

For an interesting discussion of some of the issues here, and some others touched on in relation to the compactness theorem, see Dawson 2006 .

The importance of visualisation in this regard has been noted by many writers, e.g. Steiner 1978 , p. 143.

For the importance of memorability as a goodness factor in proofs, see Gowers 2007 .

See Hafner and Mancosu 2008 , pp. 170–171, for the criticism of Philip Kitcher's theory of mathematical explanation that generalisability and unification have a qualitative as well as quantitative dimension.

See especially Kitcher 1981 and 1989. The latter, pp. 423–426 and p. 437, discusses the case of mathematics. The further details of Kitcher's theory will not matter for our discussion.

This is not to say that the notion of compactness is more natural than others in its vicinity. For example, there are many theorems of the form ‘if X is a compact and Hausdorff space then …’. It is therefore arguable which of compact and compact and Hausdorff is the mathematically more natural notion. Indeed, different mathematical cultures go their different ways on this point: for instance Bourbaki calls compactness ‘pseudo-compactness’ and reserves the term ‘compact’ for spaces that are compact and Hausdorff. This suggests that the metaphor of a concept carving mathematical reality at the joints is infelicitous. There are better and worse ways to carve up mathematical reality. But that is not to say that there is one best way of doing it, a unique carving that ‘follows the joints’.

This is not to say that they are correct as accounts of mathematical value. Indeed they cannot be if intrinsicness is an aspect of explanatoriness.

Compare the first, logical, sense of purity in Arana 2008 .

Sandborg 1998 is an outline of a theory of mathematical explanation that takes context-dependence seriously, applying van Fraassen's account of explanation to the mathematical case.