The Compactness Theorem
The compactness theorem is a fundamental theorem for the model theory of (classical) propositional and firstorder logic. As well as having importance in several areas of mathematics, such as algebra and combinatorics, it also helps to pinpoint the strength of these logics, which are the standard ones used in mathematics and arguably the most important ones in philosophy.
The main focus of this article is the many different proofs of the compactness theorem, applying different Choicelike principles before later calibrating the strength of these and the compactness theorems themselves over ZermeloFraenkel set theory ZF. Although the article’s focus is mathematical, much of the discussion keeps an eye on philosophical applications and implications.
We first introduce some standard logics, detailing whether the compactness theorem holds or fails for these. We also broach the neglected question of whether natural language is compact. Besides algebra and combinatorics, the compactness theorem also has implications for topology and foundations of mathematics, via its interaction with the Axiom of Choice. We detail these results as well as those of a philosophical nature, such as apparent ‘paradoxes’ and nonstandard models of arithmetic and analysis. We then provide several different proofs of the compactness theorem based on different Choicelike principles.
In later sections, we discuss several variations of compactness in logics that allow for infinite conjunctions / disjunctions or generalised quantifiers, and in higherorder logics. The article concludes with a history of the compactness theorem and its many proofs, starting from those that use syntactic proofs before moving to the semantic proofs model theorists are more accustomed to today.
Table of Contents
 Introduction
 Compactness: Common Logics and Natural Language
 Common Logics
 Natural Language
 Implications of Compactness
 Some NonTopological Proofs
 Deductive: Proofs via Soundness and Completeness
 Syntactic: HenkinStyle Proofs
 Semantic: Ultraproduct Proofs
 Connection to Topology
 Extensions and Generalisations
 Relative Strength
 ZFEquivalents
 Principles Strictly ZFStronger Than the Compactness Theorem
 Principles Strictly ZFWeaker Than the Compactness Theorem
 History of the Compactness Theorem
 References and Further Reading
1. Introduction
A logic consists of a language, grammar, semantics, and consequence relation ⊧ . If Γ is a set of sentences of this logic and δ one of its sentences, Γ ⊧ δ means that any model of Γ is a model of δ. (A model of Γ is a model of all sentences in Γ.) Informally, a logic is called compact if it is determined by its behaviour on finite sets of sentences; there may be infinitely many sentences in the language, but we can always reduce our considerations to finitely many in any given situation. More formally, a logic is compact just when:
 If every finite subset Γ^{fin} of Γ is satisfiable then Γ is also satisfiable.
 If Γ is an unsatisfiable set of sentences then so is Γ^{fin} for some finite subset Γ^{fin} of Γ.
Some authors take the compactness of a logic to be its satisfaction of these statements’ biconditional versions. We have chosen to omit the reverse implication from the definition as it easily follows from the meaning of Γ ⊧ δ. These two characterisations of compactness are equivalent, since the second statement is effectively the contrapositive of the first. In a logic containing a classical negation connective (by which we mean for each sentence δ there is a sentence ¬δ such that 𝔐 ⊧ ¬δ if and only if 𝔐 ⊭ δ), both statements are equivalent to:
 If Γ ⊧ δ then Γ^{fin} ⊧ δ for some finite subset Γ^{fin} of Γ.
This equivalence follows from
Γ ⊧ δ if and only if Γ ∪ {¬ δ} is unsatisfiable.
The compactness theorem is said to hold for a logic precisely when the logic is compact.
Alongside its close cousin, the completeness theorem for firstorder logic, the compactness theorem for firstorder logic is one of the most important theorems in contemporary logic. In this article, we give a few examples of compact and incompact logics and briefly discuss whether natural languages such as English are compact (Section 2). We then mention some mathematical and philosophical implications of the compactness of firstorder logic (Section 3). Following that, we give some nontopological proofs of the compactness of propositional and firstorder logic (Section 4), followed by a topological proof of the propositional case, which gives the compactness theorem its name (Section 5). We continue with a sketch of some generalisations of the usual notion of compactness (Section 6), a calibration of the strength of the compactness theorems relative to the ZF axioms (Section 7), and end with some notes on the history of the compactness theorems (Section 8). Our discussion concerns the logics philosophers are most familiar with.
2. Compactness: Common Logics and Natural Language
a. Common Logics
Propositional logic is usually taken to consist of a set of sentential atoms {p_{1}, . . . , p_{n}, … } and some truthfunctionally complete set of Boolean connectives, for instance {¬, ⋁ , ⋀ } . If we denote by PL_{κ} a propositional logic with κ sentential atoms, PL_{ω} is a propositional logic with a countable infinity of atoms. (κ will usually be taken to be an infinite cardinal in what follows.) Any propositional logic PL_{κ} is compact, whatever its set of truthfunctional connectives may be. Notice that when κ = n is finite, the compactness of any PL_{n} is a trivial consequence of the fact that any sentence is logically equivalent to a sentence drawn from a fixed set of size no greater than 2^{2n}. (This set is of size exactly 2^{2n} just when the set of connectives is truthfunctionally complete.)
Firstorder logic with standard semantics is also compact. This fact is of tremendous importance for logic and its applications, since firstorder logic remains the canonical logic to this day, the widespread interest in higher, supplementary and alternative logics notwithstanding. By ‘firstorder logic’, we understand throughout firstorder logic with identity. Firstorder logic without identity is of course also compact, since it is a sublogic of firstorder logic with identity.
By secondorder logic we mean secondorder logic with standard or full semantics, in which secondorder nplace predicate variables range over all the ntuples from the domain of interpretation (and similarly for functional variables).
In contrast to firstorder logic, secondorder logic is not compact. To see this, let ∃_{≥ n }be a sentence of firstorder logic satisfied in all and only models with domain of size ≥ n; ∃_{≥1} may thus be taken as ∃ x(x = x), ∃_{≥2} as ∃x ∃y ¬ (x = y), and so on. Since firstorder logic is a sublogic of secondorder logic, ∃_{≥} _{n} is a sentence of secondorder logic too. Consider next the sentence
∃R (R is functional ∧ R is injective ∧ ¬R is surjective)
where R is a binary predicate variable, ‘R is functional’ abbreviates ∀ x ∃!yRxy, ‘R is injective’ abbreviates ∀ x∀y∀z ((Rxz∧ Ryz) → x = y) and ‘R is surjective’ abbreviates ∀y∃xRxy. Any interpretation of this sentence states that the domain is Dedekindinfinite. The following secondorder argument is then valid:
∃≥1
∃≥2
.
.
.
∃≥n
.
.
.
∃R(R is functional ∧ R is injective ∧ ¬R is surjective)
However, no finite subset of the premisses entails the conclusion. For let the finite subset be { ∃_{≥1} , ∃_{≥2} , … , ∃_{≥}_{ik } } and take m ≥ max {i_{1}, i_{2}, . . . , i_{k} }. Then there is a model of size m in which the k premisses ∃_{≥1} , ∃_{≥2} , … , ∃_{≥}_{ik }are true but the argument’s conclusion is false. Hence secondorder logic is not compact.
The compactness theorem also typically, but not invariably, fails for infinitary logics. Any logic which allows infinite disjunctions, for example, is incompact, since the set of sentences { c ≠ c_{i} : i ∊ ω } ∪ { ⋁ _{i∊ω} c = c_{i} } is finitelysatisfiable (every finite subset is satisfiable) but unsatisfiable. We return to infinitary logics and to generalisations of the notion of compactness in Section 6.
b. Natural Language
Natural languages are languages such as English, Mandarin, French, and Arabic. Formal languages in contrast are logical languages such as those of propositional, firstorder and secondorder logic. Although of great mathematical and philosophical importance, the latter are not ‘natural’ in the intended sense because they are not anyone’s native language and are only ever ‘spoken’, if at all, in limited contexts.Is natural language, say English, compact? We must first clarify what the question means. Assume there is such a thing as the relation of logical consequence in natural language. For example, consider these two naturallanguage arguments:
Hypatia is a woman. Hypatia is mortal.
All women are mortal. All women are mortal.
Hypatia is mortal. Hypatia is a woman.
The argument on the left is logically valid, whereas the argument on the right is invalid. These two examples, of a logically valid English argument and a logically invalid one respectively, help us home in on the notion we are interested in, namely English logical validity, but they do not, of course, provide definitions of it. Next, let’s say that a natural language is compact just when, for any logically valid argument in this language, there is a logically valid argument whose conclusion remains the same, yet the premiss set is a finite subset of the original argument’s premiss set. This definition is the analogue of our last definition of compactness above for a formal language: if Γ ⊧ δ then Γ^{fin} ⊧ δ for some finite subset Γ^{fin} of Γ. An equivalent definition could be given based on the other definition of compactness for a formal language.
The overwhelming majority of linguists, philosophers, and other theorists of language take natural language to consist of infinitely many sentences. The idea is that since such sentences are of finite, but arbitrary, length, there must be infinitely many of them. The set of these sentences may be specified by a set of recursive procedures, which generate sentences of arbitrary length. For example, all the following are sentences of English:
My grandfather was tall;
My greatgrandfather was tall;
My greatgreatgrandfather was tall;
…
Now as a matter of empirical fact, there is some finite number N such that I do not have a great^{N }grandfather (which N is the least such may be vague). That does not affect the point at issue, which is that these infinitely many sentences are bona fide sentences of English.
Consider now an English argument roughly analogous to the following English analogue of the secondorderlogic argument presented earlier:
There is at least one planet.
There are at least two planets
…
There are at least n planets
…
There are infinitely many planets.
This argument appears to be valid. Clearly, no finite subset of the premiss set entails the conclusion. If this is right, the English consequence relation is incompact. The moral carries over to any natural language into which the argument is translatable.
Resistance to the argument for the incompactness of English may take several forms. One line of resistance, for instance, would query whether any natural language has a single consequence relation. According to this objection, there are only various consequence relations that arise from looking at, say, English through a particular theoretical lens; none is the correct one. Logical pluralists would all take this view, as would some other philosophers of logic: Beall and Restall (2006) and Shapiro (2014) defend different versions of logical pluralism. The objection, then, is that the argument for the incompactness of English given above assumes that there is a determinate notion: the English consequence relation.
This objection, and others, must be addressed before we can conclude that English is incompact. Here we do not take sides but flag the issue as an important one. For more discussion, see Paseau and Griffiths (2021), and Griffiths and Paseau (2022, chap. 5).
3. Implications of Compactness
This section draws some implications of the compactness of firstorder logic. The sample below is a small selection from a list that could fill volumes. Our choices are mostly guided by their philosophical implications, although there are a few examples of primarily mathematical interest. From this point on, we assume some knowledge of elementary model theory (Chang and Keisler 1990; Hodges 1997).
(i) Any compact logic extending firstorder logic cannot express the notions of finitude or infinitude (of a model). Suppose towards a contradiction that ϕ_{F} is satisfied by all and only finite Then {ϕ_{F} } ∪ {∃_{≥n }:n ∊ ω} is unsatisfiable, and hence by compactness it must have an unsatisfiable finite subset, which must be a subset of {ϕ_{F} }∪{∃_{≥i1} , . . . , ∃_{≥ik} } for some i_{1}< . . . < i_{k}. But any finite model with domain of size ≥ i_{k} satisfies (any subset of) {ϕ_{F} }∪{∃_{≥i1} , . . . , ∃_{≥ik} } , thereby contradicting our hypothesis.
And if there were a sentence ϕ_{I} satisfied by all and only infinite models then ¬ϕ_{I} would be satisfied by all and only finite models, a hypothesis we have just refuted.
This application of the compactness theorem is entirely typical. Schematically, one shows by contradiction that the class of models with some ωproperty (expressible by the conjunction of an infinite set S of firstorder sentences) is not definable by a single sentence ϕ. In these arguments, ¬ϕ together with any finite subset of S is satisfiable, but {¬ϕ} ∪ S is not, contradicting compactness. Informally speaking, in these applications the ωproperty is the conjunction of the nproperties; in our example, the nproperty was having size at least n and the ωproperty was having infinite size.
However, it is possible that (depending on the language) there is a sentence which implies that any of these models must be infinite. As an example, take the firstorder language with a single unary function symbol, and take the sentence
ϕ := ∀x∀y(f (x) = f (y) → x = y) ∧∃x∀y¬(f (y) = x)
The models of this sentence are sets endowed with an injective, but nonsurjective function. By the pigeonholeprinciple, each such model must be infinite. Since this sentence cannot express infinitude, there must be an infinite model not satisfying ϕ. An example is the domain of natural numbers, over which f is interpreted as the identity function on the natural numbers. As a further illustration of this technique, compactness implies that the class of torsionfree abelian groups is not finitelyaxiomatisable in firstorder logic. (A group is torsionfree if the identity is the only element with finite order. The prototypical example of a torsionfree abelian group is (ℤ, +).) For if it were, by the single sentence ϕ say, then the set
{abelian group axioms} ∪ {¬ϕ} ∪ {∀x ≠ 0(x +· · · + x ≠ 0) : n = 1, 2, . . . }
(x +· · · + x) n t im es
would be finitelysatisfiable (for finite sets where the sums are bounded by n in the sentences from the rightmost set, take the integers under addition modulo p for some prime p > n). But the set itself is unsatisfiable, since
{abelian group axioms} ∪ {∀x = 0((x +· · · + x ≠ 0) : n = 1, 2, . . . }
(x +· · · + x) n t im es
is satisfied by all and only torsionfree abelian groups. This contradicts compactness. Note that here the ωproperty is that all nonidentity elements of the model have infinite order, and the nproperty that all nonidentity elements have order ≠ n (all these properties incorporate the abelian group axioms too).
As a still further illustration, the same type of argument shows that the class of algebraicallyclosed fields is also not finitelyaxiomatisable. The relevant ωproperty is that the field is algebraicallyclosed, and the relevant nproperty is
∀y_{1}∀y_{2}. . . ∀y_{n}∃x(x^{n} + y_{1}· x^{n}^{−}^{1} + ··· + y_{n}_{−}_{1}· x + y_{n} = 0)
This style of argument is easily applied to many other domains.
(ii) Suppose Σ_{1} and Σ_{2} are two sets of sentences of a compact logic (in which conjunction and negation are definable) with the property that every model satisfies either Σ_{1} or Σ_{2} but not Then there is a sentence σ such that Σ_{1} is logically equivalent to σ (meaning that {σ }and Σ_{1} have the same models) and Σ_{2} is logically equivalent to ¬σ (Chang and Keisler 1990, 12, cor. 1.2.15).
(iii) The compactness theorem may be used to show that any firstorder theory of arithmetic T_{AR} satisfied by the standard model has a nonstandard (By the standard model of arithmetic, for the theory T_{AR} in question, we mean the structure of natural numbers with the standard interpretation of the nonlogical symbols in the language of T_{AR}; the constant 0 denotes 0, the twoplace symbol + denotes addition, · denotes multiplication, and so forth. A nonstandard model can have ‘infinite’ elements: objects greater than those denoted by the terms n for all n. As an ordered set, a nonstandard model looks like N followed by blocks of ℤ, which themselves form a dense linear order without endpoints.) Assuming that each numeral n is definable in T_{AR}, consider
T^{+}_{AR} = T_{AR} ∪ {c ≠ n : n ∈ ω}
where c is any constant not in the language of T_{AR}. Any finite subset of T^{+}_{AR} is satisfied by the standard model, because we may interpret c as anumber distinct from those n where c ≠ n occurs in the given finite subset. Hence by compactness, T^{+}_{AR} has a model 𝔐. The reduct of 𝔐 to thelanguage of T_{AR} is nonstandard since it contains an element c^{𝔐} (the denotation of c in 𝔐) not identical to any natural number.
Supplementing the argument just given with an appeal to the downward LöwenheimSkolem Theorem (Chang and Keisler 1990, p. 66, cor. 2.1.4; Hodges 1997, p. 72, cor. 3.1.4) shows that any such firstorder theory of arithmetic T_{AR} is not even ℵ_{0}categorical, since it has a countably infinite nonstandard model. (For an infinite cardinal κ, a theory is κcategorical if it has exactly one model, up to isomorphism, of cardinality κ.) Observe that a theory may be complete even if it is not ℵ_{0}categorical. To see this, run the previous argument supplemented by an application of the down ward LöwenheimSkolem Theorem for a complete theory of arithmetic T_{AR}. More generally, a theory may fail to be λcategorical for every infinite cardinal λ and still be complete—in other words the converse of the ŁośVaught test (Chang and Keisler 1990, p. 139, prop. 3.1.7) fails.
The same general idea can be used to demonstrate the existence of nonstandard models of real analysis. Let T_{AN} be a firstorder theory of analysis satisfied by the standard model (the ordered field of real numbers). As above, consider T^{+}_{AN} = T_{AN} ∪ {0 < c < n^{−}^{1} : n = 1, 2, . . .} where c is any constant not in T_{AN} ’s language. Any finite subset of T^{+}_{AN} is satisfied by the standard model, because we may interpret c as a positive real number smaller than 1/n , where n is the largest number for which the sentence 0 < c < n^{−}^{1 } is in the given finite subset. Hence by compactness, T^{+}_{AN} has a model 𝔐. The reduct of 𝔐 to the language of T_{AN} is nonstandard since it contains an element c^{𝔐} not identical to any real number. Indeed, this element must be a positive infinitesimal, meaning that it is a numbergreater than 0 ^{𝔐 }but smaller than every (n^{−}^{1} )^{𝔐}. As well as infinitesimals,our nonstandard model also contains infinite elements, since the the model satisfies ∀x ≠ 0 ∃y(x y = 1) and thus any nonzero element has an inverse. From these foundations, a consistent theory of the calculus that revives to a degree the use of infinitesimals in early modern mathematics may be constructed, called nonstandard analysis: see Goldblatt (1998) or the original Robinson (1966). Furthermore, since ℝ and 𝔐 have the same theory, any sentence in the language of T_{AN} that can be proven from T^{+}_{AN} will hold in 𝔐 and thus automatically holds in ℝ . This is the transfer principle of nonstandard analysis.
Since secondorder logic is incompact, the arguments just given fail for secondorder theories of arithmetic and analysis. Indeed, there are categorical secondorder axiomatisations of arithmetic (for example, Peano Arithmetic with secondorder induction (Shapiro 1991, p. 82, thm. 4.8)) and real analysis (for example, the axioms for a complete ordered field (p. 84, thm. 4.10)). For more on secondorder theories, consult (chap. 3–6).
(iv) Assuming the downward LöwenheimSkolem theorem, another corollary of the compactness of firstorder logic is the upward LöwenheimSkolem theorem (Chang and Keisler 1990, p. 67, cor. 2.1.6; Hodges 1997, p. 127, 5.1.4). This upward version of the theorem states that if a firstorder language 𝓛 has cardinality ⩽ λ and 𝔐 is an infinite model with domain of cardinality ⩽ λ then 𝔐 has an elementary extension of cardinality λ. For the proof, we consider the set of sentences consisting of the elementary diagram (the set {𝜙 ∈ 𝓛 (𝔐) : 𝔐 ⊨ 𝜙 } , where 𝓛 (𝔐) is the extension of 𝓛 obtained by adding constant symbols c_{m} for each m in the domain of 𝔐, and the interpretation of c_{m} in 𝔐 is simply m) together with the sentences c_{α} ≠ c_{β} for all distinct α, β ∈ λ, where the c_{α} are new constants. This set is finitelysatisfiable (because the infinite model 𝔐 satisfies any finite subset), and hence by compactness it is satisfiable. Say that it is satisfied by a model 𝔑, which must be of size ≥ λ as it satisfies {c_{α} ≠ c_{β} : α, β ∈ λ s.t. α ≠ β }. Since 𝔑 also satisfies the elementary diagram of 𝔐, an elementary embedding of 𝔐 into 𝔑 exists, and thus there is an elementary extension 𝔒 of 𝔐 with domain of size ≥ λ (𝔒 is an isomorph of 𝔑 whose domain includes that of 𝔐). To find an elementary extension of 𝔐 of size exactly λ, now apply the downward LöwenheimSkolem theorem to 𝔒.
The upward LöwenheimSkolem theorem may be applied to show not only that theories of arithmetic and analysis satisfied by their respective standard models have nonstandard models, but also that they have nonstandard models of every infinite cardinality. More generally, any firstorder theory in a countable language satisfied by an infinite model has models of every cardinality. Applying this to ZF or ZFC, we obtain Skolem’s paradox: if there exists a model of set theory, then there exists a countablyinfinite model, which will nonetheless model the existence of uncountable sets (Skolem 1922, 295–96).
The upward and downward LöwenheimSkolem theorems and the socalled Skolem paradox have generated much philosophical debate. The most famous philosophical use of these results is found in Putnam (1980). Wielding the theorems, Putnam argued that our mathematicalscientific theories do not admit a determinate intepretation. In particular, he claimed that set theory augmented with any theoretical principles from science and scientific data we care to add admits a countable model. This argument has given rise to an extensive literature. The responses to Putnam’s argument, and
to other versions, include technical discussion of exactly what Putnam’s argument requires mathematically speaking, as well as philosophical commentary.
(v) The compactness theorem may be used to prove the OrderExtension Principle (also known as Szpilrajn’s Extension Theorem): any partial order may be extended to a linear A partial order (A, <) consists of a domain A with an irreflexive and transitive relation <. A linear order is a partial or der satisfying the additional linearity axiom ∀x∀y(x < y ∨ x = y ∨ y < x). A linear order (A, < ) extends the partial order (A, <) just when for all a_{1}, a_{2} in A, if a_{1} < a_{2} then a_{1} <_{*} a_{2}; in other words, the identity map from (A, <) into (A, <_{*}) is a homomorphism. The notions of partial and linear order are firstorder definable in the language consisting of a single twoplace nonlogical predicate, which is what permits the application of the compactness theorem.
Unusually for applications of the compactness theorem, this result is of potential importance outside mathematics, logic, and philosophy. A standard assumption in economics is that a subject’s preferences over goods are linearly ordered. Empirically, however, we find that people’s preferences tend at best to be partially ordered: I may prefer going out for a Japanese meal rather than an Italian meal, but I may have no preference between going to the cinema and going out for a Japanese meal. In light of the OrderExtension Principle, one might try to argue that preferences being linearly ordered is a justifiable idealisation of the empirical data. See Szpilrajn (1930) for the first proof of this theorem and Richter (1966) for an early economic application, as well as Gonczarowski, Kominers, and Shorrer (2019) for more applications of the compactness theorem in economics.How does one prove the OrderExtension Principle? A relatively straightforward proof by induction on the size of the domain shows that every partial order with a finite domain can be extended to a linear order. We may then use the compactness theorem to prove that every partial order can be extended to a linear order, whatever the size of the domain, be it finite or infinite. Given a partial order (A, <), let Σ_{A} be a set of sentences consisting of the (Robinson) diagram of (A, <) (the diagram of an 𝔏structure 𝔄 is the set of literals—atomic sentences or negations of atomic sentences—in the language 𝔏’ = 𝔏 ∪ {c_{a} : a ∈ A}, where c_{a} are new constant symbols, satisfied in the expansion 𝔄’ of 𝔄 where we interpret c^{𝔄’}_{a} := a for each a ∈ A.), together with the axioms c_{a} < c_{b} ∨ c_{b} < c_{a }for all distinct a, b ∈ A. Since every partial order with a finite domain can be extended to a linear order, it follows that any finite subset of Σ_{A} is satisfiable. By compactness, Σ_{A }is therefore satisfiable. If 𝔐 is a model of Σ_{A} then (A, <) embeds into the 𝔏_{<}reduct of 𝔐, which we call (B, <_{B}), via f : (A, <) → (B, <_{B}) say. The required linear order extending (A, <) is the inverse under f of the restriction of the order <_{B} to f (A), that is a_{1}<_{∗} a_{2} if and only if f (a_{1}) <_{B} f (a_{2}). Note in passing that the OrderExtension Principle implies that every set A can be linearly ordered: simply consider a linear order that extends the empty partial order on A.
The compactness theorem for firstorder logic has a great many other applications to model theory—as Keisler (1965, 113) puts it, “the most useful theorem in model theory is probably the compactness theorem”—as well as to set theory, other parts of logic, combinatorics, algebra, algebraic geometry; see Hodges
(1997), especially chapter 5, for more.
4. Some NonTopological Proofs
In this section, we give three styles of proofs of the compactness of propositional and firstorder logic that do not draw on topology. These three proofs illustrate some important techniques, and could be broadly classified as deductive, syntac tic, and semantic methods of proof.
a. Deductive: Proofs via Soundness and Completeness
We recall the definitions of soundness and completeness for a logic 𝓛 equipped with semantic consequence relation ⊨ and deductive consequence relation ⊦ . The logic is complete iff for any set of wellformed formulas Γ and any wellformed formula δ, if Γ ⊨ δ then Γ ⊦ δ; and it is sound iff the converse obtains: if Γ ⊦ δ then Γ ⊨ δ.
If a logic has a sound and complete proof procedure, it is compact. A simple argument demonstrates this:
 Γ ⊨ δ Assumption
 Γ ⊦δ From (1) by Completeness
 Γ^{fin} ⊦ δ From (2) by the finiteness of proofs
 Γ^{fin} ⊨ δ From (3) by Soundness
Here Γ^{fin} is some finite subset of Γ. Anything deserving of the name of ‘proof procedure’ usually satisfies a host of syntactic requirements. Given soundness and completeness the only such requirement needed for the validity of the inference above is that the step from (2) to (3) be valid, namely that proofs draw only on finitely many premisses. The argument just given therefore applies to any logic which has a sound and complete proof procedure in this liberal sense. Thus, no incompact logic can be completable by a sound proof procedure; secondorder logic in particular cannot.The proof of compactness via completeness is in an important respect unsatisfactory because it is based on properties incidental to the semantic property of interest. The proof derives compactness, a semantic property, from a property of the logic relating its syntax to its semantics. Thus Keisler (1965, 113): “unlike the completeness theorem, the compactness theorem does not involve the notion of a formal deduction, and so it is desirable to prove it directly without using that notion”. Indeed, from the perspective of a model theorist who sees talk of syntax as a heuristic for the study of certain relations between structures that happen to have syntactic correlates, proving compactness via completeness is tantamount to heresy (Poizat 2000, 53).
b. Syntactic: HenkinStyle Proofs
This proof is modelled on Henkin’s (1949b) proof of the completeness theorem for firstorder logic, with its deductive core replaced by a semantic one. We begin with a relatively concrete argument for the simplest case of PL_{ω} before passing to more abstract versions. Unlike the usual versions of the proof, our argument does not assume any particular set of truthfunctional connectives, only that the set of sentences is countablyinfinite (and thus the set of connectives is countable); the argument is usually simpler (but less general) when a particular set of connectives has been specified.Let { s_{i} : i ∊ ω } be an enumeration of the set of sentences of PL_{ω}. Given a finitelysatisfiable set Γ, define a denumerable sequence of sets Γ_{n} as follows:
By definition, Γ_{n} is finitelysatisfiable for all n, hence Γ_{ω} is finitelysatisfiable since any finite subset of Γ_{ω} must be drawn from some Γ_{n}.
From Γ_{ω}, define the valuation v by letting v(p) = 1 if and only if p∊ Γ_{ω}, where p is a sentence letter. We now prove that v is a valuation in which all the sentences in Γ_{ω} (not just the sentence letters) are true. Suppose towards a contradiction that v(𝛷) = 0 for some 𝛷 ∊ Γ_{ω}. Without loss of generality (renumbering sentence letters if necessary), let p_{1}, . . . , p_{k} be all the sentence letters in 𝛷 with truthvalue 1 under v and p_{k}_{+1}, . . . , p_{n} all the sentence letters in 𝛷 with truthvalue 0 under v (one of these sets may be empty, in which case the argument to follow is easily modified). By the definition of v, none of p_{k}_{+1}, . . . , p_{n} is in Γ_{ω} so for each of these, let ∆_{i} be a finite subset of Γ_{ω} such that ∆_{i }⋃ {p_{i }} is unsatisfiable (k + 1 ≤ i ≤ n); some such ∆_{i} must exist given that p_{i} was omitted in the construction of Γ_{ω}. Now consider the set
Any valuation in which all the elements of ⋃^{n }_{i=k+1} ∆_{i} are true is one in which each of p_{k}_{+1}, . . . , p_{n} is false, since ∆_{i} ∪ {p_{i}} is unsatisfiable, and so any valuation in which p_{1}, . . . , p_{k} and all elements of ⋃^{n }_{i=k+1} ∆_{i} are true is one in which the sentence letters p_{k}_{+1}, . . . , p_{n} have truthvalue 0. It follows that any such valuation is one in which 𝛷 is false, since 𝛷 contains no sentence letters other than p_{1}, . . . , p_{k}, p_{k}_{+1}, . . . , p_{n} and v(𝛷) = 0. Hence S is unsatisfiable, contradicting the fact that this set is a finite subset of Γ_{ω}. Having proved by reductio that any sentence in Γ_{ω} is true under v, it follows that Γ, which is a subset of Γ_{ω}, is satisfiable. It is obvious from its construction that Γ_{ω} is a maximal finitelysatisfiable set, meaning that it is finitelysatisfiable and none of its proper extensions are finitelysatisfiable.
A more abstract version of the argument just presented runs as follows. Suppose Γ is finitelysatisfiable. Order by inclusion the set F_{Γ} of finitelysatisfiable sets of sentences of the language containing Γ. F_{Γ} is nonempty, since it contains at least Γ. Any chain in F_{Γ} has an upper bound, obtained by taking the union of the elements in the chain: this union contains Γ as a subset since all the members of the chain do, and it is finitelysatisfiable since any of its finite subsets must come from some element of the chain, which by hypothesis is finitely satisfiable. Zorn’s Lemma, provable in ZFC, states precisely that every partial order with the property that every chain has an upper bound has a maximal element. Since the conditions of Zorn’s Lemma are satisfied, we deduce from it that F_{Γ} has a maximal element, that is to say, a maximal finitelysatisfiable set extending Γ. We then reason as in the previous paragraph to show that all the elements of Γ are true under the valuation v defined on sentence letters by v(p) = 1 if and only if p is a member of this maximal finitelysatisfiable set. Nowhere did we rely on the fact that the sentence letters are denumerably many, or on any assumption about the set of connectives. So this more general argument shows that PL_{κ} is compact for any cardinal κ whatsoever.The abstract argument just given invoked Zorn’s Lemma, well known to be equivalent to the Axiom of Choice in ZF. Is this use of a ZFequivalent of Choice necessary? No. A weaker principle than Zorn’s Lemma, namely the Ultrafilter Lemma, will do. (Section 7 has more on the relative strengths in ZF of the Ultrafilter Lemma and Zorn’s Lemma. Consult Moore (1982) for more on the Axiom of Choice and its foundational significance.) To explain what the Ultrafilter Lemma is, we must first define the notion of a filter on a Boolean algebra. We denote the bottom, top, join, meet and complement in a Boolean algebra (with which we assume basic familiarity, see Givant and Halmos (2009) for an introduction) by the symbols 0, 1, ∨, ∧, ¬; the derived strong and weak inequality symbols have their customary meanings (x ≤ y means that x ∧ y = x and so on). A filter on a Boolean algebra B is then a subset F of B such that:
(i) 1 ∈ F; 0 ∉ F;
(ii) ∀x, y ∈ F, x ∧ y ∈ F;
(iii) ∀x, y ∈ B, if x ≤ y and x ∈ F then y ∈ F.
An ultrafilter is a maximal filter on B, or alternatively a filter on B that contains exactly one of b or ¬ b for each b ∊ B. The Ultrafilter Lemma, sometimes called the ‘Ultrafilter Theorem’ or ‘Ultrafilter Principle’, states that any filter on a Boolean algebra may be extended to an ultrafilter.
Armed with the notion of an ultrafilter, we may now modify the abstract proof of PL_{κ}’s compactness to rely not on Zorn’s Lemma but on the ZFweaker Ultrafilter Lemma instead. (Henceforth we assume that the set of propositional connectives is truthfunctionally complete.) Consider the Boolean algebra B whose domain is the set of equivalence classes of sentences of PL_{κ} under logical equivalence, 0 and 1 being the equivalence class of a contradiction and tautology respectively, ∨, ∧ and ¬ respectively denoting disjunction, conjunction and negation on the equivalence class representatives (easy check: this is welldefined); such a Boolean algebra is usually called a Lindenbaum algebra. To simplify notation, we denote the equivalence class of 𝜙 by 𝜙 itself; observe that the equivalence of ψ ≤ 𝜙 and ψ ⊨ 𝜙 follows from the fact that 𝜙 ∧ ψ and ψ are logically equivalent if and only if ψ ⊨ 𝜙.
Given a finitelysatisfiable set Γ, form the set Γ^{+} consisting of all the sentences entailed by some finite subset of Γ, that is,
Γ^{+} = {φ : ∃Γ^{fin}⊆ Γ finite s.t. Γ^{fin} ⊨ 𝜙 }.
Clearly, Γ is a subset of Γ^{+}, and Γ^{+} also has the following three properties:
(i) 1 ∈ Γ^{+} but 0 ∉ Γ^{+} (since Γ is finitelysatisfiable);
(ii) ∀x, y ∈ Γ^{+}, x ∧ y ∈ Γ^{+};
(iii) ∀x, y ∈ B, if x ≤ y and x ∈ Γ^{+} then y ∈ Γ^{+}.
In other words, Γ^{+} is a filter on the Boolean algebra of sentences of PL_{κ}. It is the smallest filter containing Γ, that is to say, Γ is a filterbase for Γ^{+}. By the Ultrafilter Lemma, Γ^{+} may be extended to an ultrafilter. The alternative definition
of an ultrafilter shows that this ultrafilter is a maximal finitelysatisfiable set of sentences containing Γ. The rest of the proof proceeds as above. We have thus proved the compactness of PL_{κ} using the Ultrafilter Lemma rather than Zorn’s Lemma.
The compactness of firstorder logic may be demonstrated by a similar argument. We give two versions of the argument: the first and slightly more direct version uses the Axiom of Choice; the second uses only the weaker Ultrafilter Lemma. For the first version, let κ be the size of WFF(𝓛) x Var(𝓛 ) where 𝓛 is the firstorder language in which each of the sentences in our given finitelysatisfiable set Γ is expressed, WFF( 𝓛 ) is the set of formulas of 𝓛 , and Var( 𝓛 ) is ’s set of variables. Add a distinct set of constants of size κ to the language (usually known as nullary Skolem functions), disjoint from 𝓛 and to be used asa source of witnesses. Then 𝓛 ^{+} also has size κ (since κ^{<}^{ℵ0} = κ for infinite κ),and so we can wellorder both the set of formulas 𝓛 ^{+} and the set of new constantsymbols in ordertype κ. We now augment the set Γ recursively by exploiting the wellordering of 𝓛 ^{+} and the wellordering of the set of new constants (each wellordering being of type κ). Let Γ_{0} = Γ and Γ_{λ} = U _{α<λ }Γ_{α} for λ a limit. For the successor case, let
Γ_{α}_{+1} := Γ_{α} ∪ {∃x𝜙 → 𝜙[c\x]},
where 𝜙[c\ x] denotes 𝜙 with c substituted for any free occurrences of x in𝜙, if ∃x𝜙 is the α^{th} formula in the ordering of WFF( 𝓛 ^{+}) and c is the first constant in the ordering of the set of constants not to appear in any element of Γ_{α} nor in φ; otherwise (if the α^{th} formula is not existential) let Γ_{α}_{+1} := Γ_{α}. Finally, let Γ_{κ} := U _{α<λ} Γ_{α} and define Γ^{+} as the set of sentences entailed by any finite subset of Γ_{κ}, that is,
Γ^{+} := {𝜙 ∈ 𝓛 ^{+} : ∃Γ^{fin}⊆ Γ_{κ} finite s.t. Γ^{fin} F ⊨ 𝜙}.
An identical argument to the one in the propositional case now shows that Γ^{+ }is a filter on the Boolean algebra of the firstorder 𝓛^{+} sentences quotiented by logical equivalence. The only difference lies in the verification that 0∉ Γ^{+}, in other words, that Γ^{+} is finitelysatisfiable. For if
{γ_{1}, . . . , γ_{n}, ∃x_{i1} 𝜙_{j1} → 𝜙_{j1} [c_{k1} \x_{i1} ],…,∃x_{im }𝜙_{jm}→ 𝜙_{jm} [c_{km} \x_{im} ]}
were unsatisfiable, with γ_{1}, . . . , γ_{n }∈ Γ and c_{km} is the greatest constant subject to their wellorder (m and n here are natural numbers, and the i, j and kindices are ordinals smaller than κ),then
{γ_{1}, . . . , γ_{n}}∪{∃x_{il} 𝜙_{jl} → 𝜙_{jl} [c_{kl} \x_{il} ]: l = 1 . . . ,m1} ⊨∃x_{im} 𝜙_{jm} → φ_{jm} [c_{km}\x_{im} ]}
But if the premisses
γ_{1}, . . . , γ_{n}, ∃x_{i1} 𝜙_{j1} → 𝜙_{j1} [c_{k1} \x_{i1} ],…,∃x_{im1 }𝜙_{jm1}→ 𝜙_{jm1} [c_{km1} \x_{im1} ]}
are jointly satisfiable then they cannot entail both ∃x_{im }𝜙_{jm} and ¬𝜙_{jm} [c_{km} \x_{im} ]. The reason is that if there is a model in which this premiss set and ∃x_{im }𝜙_{jm} are satisfied, then there is a model in which the interpretation of c_{k}m may be chosen to witness the truth of ∃x_{im }𝜙_{jm}, since c_{k} does not appear in any other sentence than 𝜙_{jm} [c_{km} \x_{im} ]. Having verified that Γ^{+} is a filter, we invoke the Ultrafilter Lemma as before to extend Γ^{+} to an ultrafilter Γ^{++}. Note that Γ^{++} contains Γ_{κ} and hence is witnesscomplete—every existential statement is satisfied by some constant.
To show that Γ^{++} (and hence Γ) is satisfiable, we construct a term model . The term model’s domain consists of the closed terms of +, quotiented by the relation of appearing in an identity statement of Γ^{++}, that is to say τ_{1} τ_{2}if and only if τ_{1} = τ_{2} Γ^{++}. The interpretation a^{T} of the constant a is a’s equivalence class, [a]; the interpretation f ^{T} of the function symbol f applied to[τ_{1}], . . . , [τ_{n}] is [f (τ_{1}, . . . , τ_{n})]; and for any nplace relation symbol R and closed terms τ_{1}, . . . , τ_{n}, R([τ_{1}], . . . , [τ_{n}]) holds in the model if and only if R(τ_{1}, . . . , τ_{n}) is an element of Γ^{++}. A routine argument shows that this interpretation is welldefined and that the term model is a model of Γ^{++}. It is an instructive exercise to determine where exactly the arguments just given break down in the case of secondorder logic: see Paseau (2010a, 75–76) for details.To see how to avoid the use of the Axiom of Choice, we show that turningΓ into a Skolem set (a set containing a witness for every existential statement) does not in fact require the WellOrdering Principle. In this alternative argument for the compactness of firstorder logic, we construct a set c φ,x : φ , x Var( ) of constants disjoint from the set of constants of , one for each ordered pair in WFF( ) Var( ). (If we were to formalise this argument in our settheoretic metatheory, say ZF, we may for instance code each constant c φ,x as φ, x, WFF( ) Var( ) . The point is that no Choice principles are required for this recursive definition.) Then add Skolem sentences xφ φ[c φ,x x] for every such ordered pair φ, x . This gives us a new set of sentences Γ_{1} Γ_{0} = Γ in a language _{1} _{0} = . Iterate this process ωtimes, constructing a chain of sets of sentences Γ_{0} Γ_{1} Γ_{n} , and a corresponding chain of languages _{0} _{1} _{n} . By an inductive argument, each Γ_{n} is readily seen to be finitelysatisfiable (there is no need to assume the wellordering of _{n}_{+1}_{n} at this point), hence so is n ω Γ_{n}. Finally, define Γ^{+} as the filter generated by Γ_{ω}. The rest of the argument, which defines a term model from the ultrafilter extending the filter Γ^{+} proceeds as above. The version of the argument sketched in this paragraph invoked the Ultrafilter Lemma and at no point did it use the Axiom of Choice.The set Γ^{++} is an example of a Hintikka set, which is a set of firstorder sentences T that satisfies the following axioms. (For brevity, we use take , , as primitive symbols in our firstorder logic.)
 For every atomic sentence φ, if φ ∈ T then ¬φ ∈/ T ,
 For every closed term t, t = t ∈ T ,
 If φ(x) is an atomic formula with a single free variable x, and s, t are closed terms such that φ(s), s = t ∈ T , then φ(t) ∈ T ,
 If φ is a sentence and ¬¬φ ∈ T , then φ ∈ T ,
 If Φ is a finite set of sentences, then
 Φ T implies Φ T ,
 ¬ Φ ∈ T implies ¬φ ∈ T for some φ ∈ Φ,
 If φ(x) is a formula with a single free variable x, then
 ∀xφ(x) ∈ T implies φ(t) ∈ T for every closed term t,
 ¬∀xφ(x) ∈ T implies ¬φ(t) ∈ T for some closed term t.
Given a Hintikka set T , we can construct a term model (using the same definition given above) that satisfies T (Hodges 1997, 40–42).c. Semantic: Ultraproduct ProofsIn this subsection, we prove the compactness theorem for firstorder logic from Łoś’ Theorem. We recall the definition of an ultraproduct and state the theorem. For a proof, see Chang and Keisler (1990, p. 217, thm. 4.1.9) or Hodges (1997, p. 241–242, thm. 8.5.3).Let (A_{i})_{i} _{I} be a collection of firstorder structures of the same signature, indexed by I, and U an ultrafilter over this indexing set I. In this context, the Boolean algebra is (I) with the subset ordering , so a filter F (I) is a set of subsets of I which does not contain the empty set and which is closed under finite intersection and upward containment. Denote the domain of each A_{i} by A_{i}. When U is an ultrafilter over I, defining a _{U} b by i I : a(i) = b(i) U yields an equivalence relation over the productIT A_{i} = ff : I → A_{i} ∀i ∈ I, f (i) ∈ A_{i}l.(We tend to view elements of the product as generalised sequences (x_{i})_{i} _{I}.) The characteristic function µ_{U} of U is a finitelyadditive full measure on I and thus intuitively the elements of U are ‘large subsets of I’: two functions in i I A_{i} are identified by this relation precisely when they agree ‘Ualmosteverywhere’. We define a new structure B = i I A_{i}/U as follows:
 Domain of B = i I A_{i} quotiented by _{U} ; [a] denotes the equivalence class of a;
 c^{B} = [( · · , c^{A}i, · · · )];
 f ^{B}([a_{1}], · · , [a_{k}]) = [(· · · , f ^{A}i (a_{1}(i), · · · , , a_{k}(i)), · · · )];
 R^{B}([a_{1}], · · , [a_{k}]) if and only if {i ∈ I : A_{i} F R(a_{1}(i), · · · , a_{k}(i))} ∈ U .
for any kplace function and relation symbols f and R and any constant c of the firstorder language in question. As may be checked, the fact that U is a filter means that the definitions just given do not depend on the choice of representatives from i∈I A_{i}. For φ atomic we have by definition:B F φ(a_{1}, · · · , a_{n}) if and only if {i ∈ I : A_{i} F φ(a_{1}(i), · · · , a_{n}(i))} ∈ U.Łoś’ theorem, which is proved by induction on the complexity of φ, extends this to all φ:for all φ, B F φ(a_{1}, · · · , a_{n}) if and only if {i ∈ I : A_{i} F φ(a_{1}(i), · · · , a_{n}(i))} ∈ U .The induction step for the universal / existential quantifier step does require some Choice. In fact, the Ultrafilter Lemma together with Łoś’ theorem imply the full Axiom of Choice (Howard 1975).To prove the compactness theorem for firstorder logic from Łoś’ Theorem,let Σ be a finitelysatisfiable set of firstorder sentences. Let I be the set of finite subsets of Σ and suppose we are given for each i ∈ I a model A_{i} for the sentences in i. For i ∈ I let
J_{i} := {j ∈ I : i ⊂ j},F := {J ⊂ I : J_{i} ⊂ J for some i ∈ I}.The collection of J_{i} is closed under finite intersection because J_{i}1 J_{i}2 = J_{i}1 i2 , hence F is also closed under finite intersection; by definition, F is closed under
upward containment, and clearly F does not contain the empty set. Thus F satisfies the conditions for being a filter and may therefore be extended to an ultra filter U . Now for any σ Σ, we have σ I and J σ i I : A_{i} F σ , from which it follows that i I : A_{i} F σ U . By Łoś’ theorem, B F σ. This is true for every σ Σ, so B F Σ, in other words if Σ is satisfiable. Intuitively, the model B was designed so as to agree with A_{i} on the ‘large subset’ J_{i} of I and in particular to agree with A_{i} on the truthvalue of each element of i; as this is true for all i, B satisfies Σ. This completes the ultraproduct proof of the compactness of firstorder logic.For particular applications, we may not need the full strength of the Axiom of Choice to apply then ultraproduct method. For example, suppose we wish to use the ultraproduct method to construct a nonstandard model of arithmetic (see Section 2c) with language and standard model A with domain ω. We extend the language to by introducing a new constant symbol c and for each n ω, let A_{n} be the expansion of A given by interpreting c^{A}n := n. Let F be the filter of cofinite subsets of ω and let U be an ultrafilter that extends F . Then the particular instance of Łoś’ Theorem can be proven for (A_{n})_{n} _{ω} and U , utilising the wellfoundedness of ω in place of the Axiom of Choice. ThusB = n∈ω A_{n}/U satisfies the same Lsentences as A, and for all m ∈ ω,{n ∈ ω : A_{n} F c = 1 + · · · + 1} = ω \ {m} ∈ F ⊆ U,m ti mes .,so by Łoś’ Theorem it follows that B F c = 1 + · · · + 1. Therefore B is a non
standard model of arithmetic.5. Connection to TopologyThe Tarski (1952) article gives the compactness theorem its name (see theorems 13 and 17), observing its similarity with the finiteintersectionproperty definition of compactness in topologies. Here we will demonstrate the topological connection in two stages. First, we show that the compactness theorem for a propositional logic is equivalent to the claim that its associated valuation space is compact. (Recall that an open cover of a topological space X is a collection of open subsets of X whose union is X, and that a space X is compact if every open cover has a finite subcover—a finite subset that is also a cover. Equivalently, every collection of closed subsets with the finiteintersection property—every finite subset has nonempty intersection—has nonempty intersection. Intuitively, you cannot ‘escape’ a compact space; every collection of points will accumulate som where.) Second, we show that this space is indeed compact. We assume some basic knowledge of topology (Sutherland 2009; Willard 1970).In this section, we spell out this reasoning for the case of propositional logic. We start with an argument that demonstrates the compactness of any PL_{κ}, initially assuming for the sake of simplicity that the version of PL_{κ} in question is equipped with a truthfunctional set of connectives.Let V_{κ} be the set of all valuations of PL_{κ}. For each sentence φ of PL_{κ} define U (φ) = {v ∈ V_{κ} : v(φ) = 1}, the set of valuations in which φ is true. Since U (φ_{1}) U (φ_{2}) = v V_{κ} : v(φ_{1}) = 1 v V_{κ} : v(φ_{2}) = 1 = U (φ_{1} φ_{2})the sets U (φ) form a basis for a topology on V_{κ}; call this basis . (A basis for a topology is a collection of open sets with the property that if andonly if U = LJ C for some C ⊂ B. Given a collection B of subsets of X, if its
union is X and for all B_{1}, B_{2} , B_{1} B_{2} = for some , then there exists a unique topology on X with basis (Willard 1970, p. 38, thm. 5.3).) The topological space we shall be interested in has domain V_{κ} and topology generated by the basis = U (φ) : φ is a sentence of PL_{κ} ; with this topology, V_{κ} is the dual space of the Boolean algebra of sentences of PL_{κ}. Thus properties of this space are determined only by the logical properties of valuations.Now consider any set of sentences Σ of PL_{κ}. Σ is unsatisfiable if and only if any valuation assigns truthvalue 0 to at least one of its members, or equivalently any valuation assigns truthvalue 1 to at least one sentence s such that s Σ. It follows that Σ is unsatisfiable if and only if each valuation is in some open set of the form U ( s) where s Σ, or equivalently that U ( s) : s Σ is an open cover of the topological space V_{κ}. The compactness of PL_{κ} is therefore equivalent to the following claim:if {U (¬s) : s ∈ Σ} is an open cover of V_{κ} then there is a finite subsetΣ^{fin} of Σ such that {U (¬s) : s ∈ Σ^{fin}} is an open cover of V_{κ}.Thus PL_{κ} is compact if and only if V_{κ} is compact. (Note that any open set is the union of some basis sets and that any basis set U (φ) is identical to U ( s) fors = φ. Also, a space is compact if every open cover drawn from a fixed basis has a finite subcover.) It suffices, then, to show that V_{κ} is compact in the usual topological sense.The last claim is immediate from the fact that V_{κ} is homeomorphic to 0, 1 ^{κ} = f : κ 0, 1 with the (Tychonoff) product topology, when 0, 1 is given the discrete topology . Recall that the product topology on the product i∈I X_{i} of a family of topological spaces (X_{i}, τ_{i}) indexed by I takes asments i in I. (For a finite collection (X_{1}, τ_{1}), …, (X_{n}, τ_{n}), the product topology on X_{1} X_{n} has basis U_{1} U_{n} : i, U_{i} τ_{i} . In general, the product topology is determined by the following universal property: for any space Y and
we remove the restriction that allbutfinitelymany O_{i}’s are equal to X_{i}, we obtain the box product topology. This coincides with the product topology for finite indexes, but varies drastically for infinite products.) Since 0, 1 ^{κ} with the product topology is homeomorphic to the V_{κ} (if the sentence letters in PL_{κ} are p_{α} for α κ, then f (v)(α) := v(p_{α}) defines a homeomorphism f : V_{κ} 0, 1 ^{κ}) the latter is compact if and only if the former is. Now 0, 1 with the discrete topology is compact because finite spaces are trivially compact. Tychonoff’s Theorem, a ZFequivalent of the Axiom of Choice, states that the product of compact spaces is compact. Putting the pieces together, it follows that 0, 1 ^{κ} with the product topology is compact. This proves the compactness of PL_{κ}.We do not in fact need the full power of Tychonoff’s Theorem. The weaker principle that the product of compact Hausdorff spaces is compact will do, because 0, 1 with the discrete topology is Hausdorff (any two of its elements—0 and 1—are contained in disjoint open sets 0 and 1 ). This weaker version of Tychonoff’s Theorem is in fact equivalent to the compactness theorem for propositional logic (and firstorder logic), as discussed in Section 7.The topological proof of PL_{κ}’s compactness just given assumed that PL_{κ}’s set of connectives is truthfunctionally complete. Without this assumption, there isno guarantee that the set B is a basis for the product topology; for example, if a propositional logic cannot define negation, no element of B may correspond to
the open set consisting of all elements of 0, 1 ^{κ} with first coordinate 0, and if it cannot define conjunction then will not be closed under intersection and thus cannot be a basis. The compactness of a propositional logic with κ sentence letters but without a truthfunctional set of connectives is of course immediate from the fact that it is a sublogic of a truthfunctionally complete propositional logic with the same κ sentence letters. The topological way of seeing this is to endowthe space V_{κ} with the topology which has B as a subbase and denote it by Y . (Asubbase for a topological space (X, τ ) is a collection of open sets S ⊂ τ such that= X : (X, τ )lection of subsets of a set X, there is a unique topology τ on X which hasas a subbase. (Willard 1970, p. 39, thm. 5.6).) This topology is coarser than thedual space topology on V_{κ}: every open set in Y is open in the dual space topology. In general, if the topology τ on some set X is coarser than the topology τ^{∗} on X and (X, τ^{∗}) is compact, then so is (X, τ ). Intuitively, there are fewer means of ‘escaping’ (via the finiteintersection property) in τ than in τ^{∗}, so if τ^{∗} is compact then there are no such routes in τ . It follows that the topological space Y is compact, and thus any propositional logic is compact, whether or not its set of connectives is truthfunctionally complete.A ‘bare hands’ argument that avoids anything as strong as either the general Tychonoff Theorem or its compact Hausdorff version above may also be given for the compactness of V_{ω}. We present this argument, since PL_{ω} is the most common propositional logic.Suppose that some open cover of the space A = 0, 1 ^{ω} with the product topology lacks a finite subcover. We reduce this supposition to absurdity by constructing an element a of A with the following property: the set of all elements of A extending an arbitrary finite initial segment of a cannot be coveredby any finite subset of C . If f is a finite sequence of 0’s and 1’s, define A_{f} as the set of elements of A extending f . Let a_{0} = (0) if A(0) does not admit a finite subcover from C, and a_{0} = (1) otherwise. More generally, if a_{m} has beendefined, let a_{m}_{+1} = a_{m}^{ }(0) if Aa (0) does not admit a finite subcover fromC, and a_{m}_{+1} = a_{m} 1 otherwise. Since by the assumption to be reduced to absurdity A = A does not admit a finite subcover from , an easy inductive argument shows that A_{a}m does not admit a finite subcover from either, for any
 m. Letting a be the element of A whose restriction to m is a_{m} (more formally,
a = m ω a_{m}), it follows from the fact that is an open cover of A that a is an element of some basis set B O, where O is an open set in . From a B and the definition of the product topology, it further follows that for some m, A_{a}m B, so that A_{a}m does in fact admit a finite subcover from , namely the open set O which contains B as a subset. This contradicts our supposition and shows that A = 0, 1 ^{ω} with the product topology is compact.The argument just given, which constructs an infinite branch through a binary branching tree, did not require any version of Choice. The reason is that at each stage in the construction of a we used the ordering on 0, 1 to extend a_{m} by 0 if possible and 1 if not. An alternative argument for the compactness of 0, 1 ^{ω} uses the fact that a countable product n ω (X_{n}, d_{n}) of bounded (by 1) metric spaces (X_{i}, d_{i}), is metrisable via the metric
d (x, y) = dn(xn, yn) .ω 2nn∈ωTo say that is metrisable in this way is to say that the metricd_{ω} induces the product topology on ITn∈ω (X_{n}, d_{n}). The rest of the argument
turns on showing that the metric space ( 0, 1 ^{ω}, d_{ω}) is compact, by exploiting the space’s metric properties. This argument cannot be generalised to show that PL_{κ}’s valuation space is compact for any κ ω_{1}: the uncountable product of metric spaces, each having at least two points, is not metrisable, as no point has a countable neighbourhood base.Moving to arbitrary logics , we construct the space X of theories Th(M) ofstructures M, topologised by the subbasic open sets U_{φ} := T X : φ / T for each formula φ in . The compactness of is then easily seen to be equivalent to the compactness of X with this topology (see Figure 1). In the case ofpropositional logic, X_{PL}κ = V_{κ}. (Note that unlike for bases, the implication that compactness of a space follows from every open cover drawn from a fixed subbase has a finite subcover requires the Axiom of Choice. This is the Alexander subbase theorem (Willard 1970, p. 129, problem 17S).) However, the argument for firstorder logic is more complicated than that for propositional logic and not as elementary as exhibiting a simple homeomorphism.
Γ is unsatisfiable
is compact
∆ is unsatisfiable for some finite ∆ ⊂ Γ
Definition of X_{L}{U_{γ} : γ∈ Γ} is an open cover of X_{L}X_{L} is compact
{U_{γ} : γ ∈ ∆} is an open cover of X_{L}for some finite ∆ ⊂ Γ
Figure 1: The connection between compactness of logics and its space of theories.6. Extensions and GeneralisationsThe discussion of the compactness theorem in the most common logics, our concern here, could now ramify in several directions. There are two main dimensions of variation when considering a proof of compactness for a logic: we could vary the notion of compactness, or we could vary the logic. As an example of the latter, we might consider, for example, modal logics (K, T, S4, S5); infinitary logics_{κλ} ( _{κλ} being the extension of firstorder logic which allows for conjunctions and disjunctions of length less than κ and existential and universal quantifications of length less than λ. Usually κ λ: we use to represent no bound on the connectives / quantifiers respectively.); other extensions of firstorder logic, such as logics with cardinality quantifiers.A rough rule of thumb is that infinitary logics are not compact. In particular,as demonstrated in Section 2 with the example of c = c_{i} : i ω i ω c = c_{i} ,_{κλ} is not compact whenever κ > ω. In contrast, logics extending firstorder logicwith generalised quantifiers tend to be compact, but not if they contain cardinality quantifiers. Roughly speaking, the quantifiers Q_{ℵ}κ , Q_{>}_{ℵ}κ , Q_{<}_{ℵ}κ , Q_{≥ℵ}κ , Q_{≤ℵ}κ
are interpretable as ‘there are exactly _{κ}’, ‘there are more than _{κ}’, ‘there are fewer than _{κ}’, ‘there are at least _{κ}’, and ‘there are no more than _{κ}’. Consider the set{¬Q_{≥ℵ}κx(x = x)} ∪ {c_{α} = c_{β} : α, β ∈ κ s.t. α = β}in an infinitary logic containing Q ; this set is finitelysatisfiable but unsatisfiable. (The arguments involving the other cardinality quantifiers are similar.) However, such logics tend to satisfy weaker notions of compactness. In particular, the logic that extends firstorder logic with the quantifier Q_{>} , interpreted as ‘there are uncountably many’, is countablycompact: that is, a countable set of sentences is satisfiable if and only if it is finitelysatisfiable (Keisler 1970).As an aside, it is worth observing that not all logics with higherorder (secondorder or above) quantifiers are incompact. Secondorder logic with nonstandard (Henkin) semantics is compact (Enderton 2001, chap. 4), as is existential secondorder logic, whose sentences are of the form S_{1}. . . S_{n}φ, where S_{1}, . . . , S_{n} are secondorder functions / relations, and φ is a firstorder sentence in a language with symbols for S_{1}, . . . , S_{n}. (Via embeddings, this logic is equivalent to many firstorder logics extended with extra quantifiers and gametheoretic semantics, such as Henkin’s quantifier, HintikkaSandu’s independencefriendly logic, and Väänänen’s dependence logic. However, these logics do not have a classical negation and the alternative form of compactness given in the introduction of this article is false: see section 2a of this article. For further details on these logics, consult Väänänen (2007) and Mann, Sandu, and Sevenster (2011)). As another example, consider what has been called pure secondorder logic with identity, that is, secondorder logic with neither functional nor firstorder variables but with both secondorder and firstorder identity (as well as predicate variables and quantifiers). Pure secondorder logic may be thought of as the complement of firstorder logic relative to secondorder logic in the following sense: firstorder logic has object but not predicate quantifiers, pure secondorder logic has predicate but not object quantifiers, and secondorder logic combines the two. In other words, secondorder logic merges firstorder and pure secondorder logic. As Paseau (2010b) shows, pure secondorder logic with identity is compact; Denyer (1992) gives an argument that applies to pure secondorder logic without identity. The moral is that the incompactness of secondorder logic is not owed solely to the presence of secondorder quantifiers, but to the combination of both first and secondorder quantifiers. Lindström’s Theorem tells us that any regular logical system weakly extending firstorder logic satisfying both the downward LöwenheimSkolem property (if a sentence is satisfiable, it is satisfiable in an at most countable model) and the compactness theorem is in fact identical to first order logic itself (Lindström 1969, p. 8, thm. 2).The other natural dimension of generalisation is the notion of compactness. A fairly obvious generalisation is:a logic is (κ, λ)compact, where κ is an infinite cardinal or ∞ and λ is an infinite cardinal ≤ κ, just when: whenever Γ is an unsatisfiable set of sentences of cardinality ≤ κ there is an unsatisfiable Γ^{λ} ⊂ Γ of cardinality < λ. (By convention κ < ∞ for every cardinal κ.)The ordinary notion of compactness is (∞, ℵ_{0})compactness: whenever Γ is any unsatisfiable set of sentences (of any cardinality) there is an unsatisfiable Γ^{ℵ}0 ⊂ Γ of cardinality < ℵ_{0}, in other words of finite cardinality. A special case arises when κ = λ^{+} and the logic is L_{λλ}. If this logic satisfies (λ, λ)compactness, that is, if whenever Γ is an unsatisfiable set of sentences of cardinality ≤ λ then Γ has
an unsatisfiable subset of cardinality < λ, we say that it satisfies the Weak Compactness Theorem. One can show that for infinite cardinals, having the tree property is equivalent to satisfying the Weak Compactness Theorem, and either imply the weak inaccessibility of the cardinal. Cardinals satisfying the Weak Compactness Theorem are exactly those satisfying the combinatorial partition property κ (κ)^{2}, and indeed the latter is the usual definition of a weaklycompact cardinal. For the definitions of the tree property and the partition property, and more on weaklycompact cardinals, consult chapters 9 and 17 of Jech (2003).Another generalisation of the notion of compactness is strong compactness. An uncountable cardinal κ is stronglycompact if for any set S, any κcompletefilter on S can be extended to a κcomplete ultrafilter on S. (A filter F on a setκ < κthat κ is stronglycompact if and only if the logic _{κω} (or _{κκ}) has the property of ( , κ)compactness, that is, if Γ is an unsatisfiable set of sentences then it has an unsatisfiable subset of cardinality < κ. (p. 366, lemma 20.2)Both weakly and stronglycompact cardinals are large cardinal properties. (A sentence φ(κ) is a large cardinal property if it satisfies the following: ZFCκφ(κ) is equiconsistent with ZFC, ZFC κ(φ(κ) κ is a cardinal), and the consistency strength of ZFC κφ(κ) is strictly larger than ZFC, by which we mean the consistency of the former implies that of the latter, but there is no finitistic argument for the reverse implication, for example, if ZFC κφ(κ) implies the arithmetised consistency of ZFC, by Gödel’s second incompleteness theorem.) Another large cardinal property is the extendible cardinal property, which is defined in terms of elementary embeddings of levels in the von Neumann cumulative hierarchy. However, it was later discovered that extendibility of acardinal κ is equivalent to (∞, κ)compactness of L2 , or the (∞, κ)compactnessof Ln for each positive integer n (Kanamori 2009, p. 315, thm. 23.4). Ln is thenthorder extension of _{κλ}.Generalising the argument in Section 5 above, it is easily shown that a logic is (κ, λ)compact precisely when every subbasic open cover U_{φ} : φ Γ ofX , where Γ is a set of sentences of cardinality at most κ, has a subcover of cardinality less than λ. This is weaker than stating that X is (κ, λ)compact, meaning every cover of cardinality at most κ has a subcover of cardinality less than λ. For example, if is the extension of firstorder logic with the quantifier Q_{>} , then is ( _{0}, _{0})compact, but X is not ( _{0}, _{0})compact. See Ebbing haus (1985, sec. 5.1), Makowsky (1985, sec. 1.1), Mannila (1983), and Stephenson (1984) for more on (κ, λ)compact logics and spaces.These remarks do no more than gesture at an extensive literature generalising the notion of compactness and connecting it to topics of settheoretic interest. We would be remiss if we did not at least mention in passing the Barwise compactness theorem, which is as an important theorem in generalised recursion theory (Keisler and Knight 2004). The interested reader is invited to explore the references contained within this section.7. Relative Strength
As we saw, the compactness theorem for both propositional and firstorder logic may be proven in ZFC; but as also indicated, all that is required for its proof, in the case of both propositional and firstorder logic, is the Ultrafilter Lemma, which is in fact weaker than Choice relative to ZF. Indeed, the Ultrafilter Lemma turns out to be equivalent to the compactness theorem in ZF. By the capitalised
name ‘Compactness Theorem’ we hereafter understand the compactness theorem for both propositional and firstorder logic, since these are of equivalent strength relative to ZF. The relative strength of these and related principles has been wellstudied; in this section we report several of these results.a. ZFEquivalentsTychonoff’s Theorem states that every product of compact spaces (with the product topology) is compact. In proving compactness earlier, we only required Tychonoff’s Theorem in the case when the product consisted of Hausdorff spaces. This weakened version is in fact equivalent to the Compactness Theorem. Some other equivalents are:
 The Boolean Prime Ideal Theorem: every Boolean algebra has a prime
 The Ultrafilter Lemma: every filter on a Boolean algebra can be extended to an
 Stone’s Representation Theorem: every Boolean algebra is isomorphic to a field of
 Alexander subbase theorem: if X is a topological space with a subbase and every open cover has a finite subcover, then X is compact (Rubin and Scott 1954).
 For every graph G, if every finite subgraph of G is 3colourable then G is also 3colourable (Cowen 1990).
 If Σ is a set of propositional sentences consisting of a disjunction of at most three literals and every finite subset is satisfiable, then Σ is also satisfiable (Cowen 1990).
The equivalences of the first three statements with the Compactness Theorem can be found in Jech (1973, chap. 2). For more information, consult Howard and Rubin (1998, form 14).b. Principles Strictly ZFStronger Than the Compactness TheoremIt is known that the full Tychonoff Theorem is equivalent to the Axiom of Choice in ZF (Kunen 2011, 72). To show that the Compactness Theorem does not imply Choice, we will briefly sketch the construction of a model where Choice fails but the Compactness Theorem holds. Suppose we are working in ZFA + AC with a countably infinite set of atoms A (objects which do not contain any elements and are different from the empty set); ZFA is a variant of ZF with atoms (Jech 1973, sec. 4.1). We can develop all of our standard theory in this system, with some minor modifications (for example, the Axiom of Extensionality states that two sets are equal if they have the same elements). Let <l be a dense linear ordering on A without endpoints. Every permutation π of A has an extension π˜ to the entire universe, define recursively by π˜(X) := π˜(x) : x X for each set x. Let G be the group of orderpreserving permutations of A and for every set x definefix(x) := {π ∈ G : ∀y ∈ x, π˜(y) = y} and sym(x) := {π ∈ G : π˜(x) = x}.We shall say that an object x is symmetric if there is a finite set of atoms E such that fix(E) ⊂ sym(x). Denote the class of hereditarily symmetric objects by M .
If V denotes the standard cumulative hierarchy in this theory, then it is easily seen that V M . We may also show that ZFA holds in M . As the Axiom of Choice holds in V , a set X M is wellorderable, according to M , precisely when there is a symmetric function mapping X to some set in V . This turns out to be the case precisely when there is a finite set of atoms E such that fix(E) fix(X). Since for every finite set of atoms E, there is a nonidentity orderpreserving permutation of A fixing E, it follows that A is not wellorderable according to M . However, the Compactness Theorem still holds in M .Although we worked in a theory with atoms, it is possible to translate this model to a model without atoms where Choice fails but the Compactness Theorem holds. The interested reader should consult (Jech 1973, pp. 44–54, chap. 4) for details of this proof. It now follows that, working in ZF, Tychonoff’s Theorem is not implied from the Compactness Theorem.Here are some more examples of theorems equivalent to Choice (a principle we restate for the sake of completeness), and thus unprovable from the Compact ness Theorem:
 Axiom of Choice: every family of nonempty sets has a choice
 Axiom of Multiple Choice: every collection of nonempty sets has a multiple choice function—a function that picks out a nonempty, finite subset from each set in the collection (Chapter 9).
 WellOrdering Principle: every set can be wellordered (Kunen 2011, 68).
 Zorn’s Lemma: every partial order in which every chain has an upper bound has a maximal element (68).
 Every vector space has a basis (Blass 1984).
 Every nonempty set can be endowed with a group operation (Hajnal and Kertész 1972).
See Howard and Rubin (1998, form 1) for more statements equivalent to the Axiom of Choice.c. Principles Strictly ZFWeaker Than the Compactness TheoremThe following is a small selection of Choicelike principles that are weaker than the Compactness Theorem. See Jech (1973) for the construction of models satisfying one of these statements but not the Compactness Theorem.
 OrderExtension Principle, and consequently the statement that every set can be linearlyordered.
 HahnBanach theorem: If p is a sublinear functional on a set X and φ is a linear functional defined on a subspace V X such that φ(v) p(v) for all v V , then there exists a linear extension ψ of φ to all of X such that ψ(x) p(x) for all x X. In fact, the HahnBanach theorem is equivalent to the existence of a finitelyadditive probability measure on every Boolean algebra (28). It is easily seen that a prime ideal gives rise to a finitelyadditive, 0, 1 valued probability measure on every Boolean algebra, and thus the HahnBanach theorem follows from the Boolean Prime Ideal
 Every infinite set has a nonprincipal
8. History of the Compactness TheoremThe first proof of a compactness theorem was published by Gödel:Theorem X. For a denumerably infinite system of formulas to be satisfiable it is necessary and sufficient that every finite subsystem be satisfiable. (Gödel 1930, 118–19)The formulas of the logic, called restricted (functional) calculus (103n3) or firstorder predicate logic (Mal’cev 1936, 1), are those from firstorder logic that do not contain any function, constant, nor equality symbols, but do contain propositional variables; these variables can only be interpreted as 1 (true) or 0 (false) in any model. Thus, this system extends that of propositional logic PL_{ω}.The central idea behind Gödel’s proof is to create an equivalent sequence (φ_{n}) of satisfiable formulas, where each φ_{n}_{+1} is a conjunction, with one of the conjuncts being φ_{n}, for each n. The models for each φ_{n} (in the language restricted to only those nonlogical symbols that occur in φ_{n}) form a finitelybranching tree of height ω, ordered by extension, which by König’s lemma must contain a branch. (Whilst König’s lemma in general requires some Choice to prove, if the tree is countable then it can be proven in ZF. A finitelybranching tree of height ω is a countable union of finite sets, which is not necessarily countable in ZF, even if the finite sets are pairs (Pincus 1974, 224).) The interpretations along this branch are consistent and form a model of the whole sequence (φ_{n}), which in turn models the original sequence. We have not included this approach to the compactness theorem in this article—for details, see Paseau (2010a, 84).This result also proves the corresponding result for firstorder logic with a countable infinity of symbols. Indeed, Gödel does extend his result to allow for equality symbols (Gödel 1930, p. 117, thm. VIII). To allow for constant and function symbols, we introduce new predicate symbols R_{c} and R_{f} of arity 1 and n + 1 for each constant symbol c and nary function symbol f , and make the following substitutions:
 For a constant symbol c occuring in a sentence φ, replace each occurrence of c with a variable y that does not occur in φ to obtain the If φ
denotes this new sentence, we then replace φ with ∃y(φ ∧ R_{c}(y)).
 For an nary function symbol f in a sentence φ, replace each occurrence of
R(σ_{1}, . . . , σ_{k}_{−}_{1}, f (τ_{1}, . . . , τ_{n}), σ_{k}_{+1}, . . . , σ_{m})with∃y(R(σ_{1}, . . . , σ_{k}_{−}_{1}, y, σ_{k}_{+1}, . . . , σ_{m}) ∧ R_{f} (τ_{1}, . . . , τ_{n}, y)),where R is an mary predicate symbol, σ_{1}, . . . , σ_{k} _{1}, σ_{k}_{+1}, . . . , σ_{m}, τ_{1}, …, τ_{n} are terms and y is a variable that does not occur in φ. Viewing equality as a binary predicate, we can perform the same procedure on subformulas of this form.Repeating this procedure until there are no occurrences of constant nor function symbols, we obtain a new set of sentences Γ. Appending to this set sentences of the form !zR_{c}(z) for each constant symbol c and x_{1}, . . . , x_{n} !zR_{f} (x_{1}, . . . , x_{n}, z) for each nary function symbol f , we find that the satisfiability of this new set is equivalent to the satisfiability of Γ, thus extending Gödel’s result to encompass languages with constant and function symbols.
Note that Gödel’s result is only applicable to the countable versions of propositional and firstorder logic. In Gödel’s (1932) short paper, he proves the compactness theorem for propositional logic for arbitrary languages. Given a deductivelyclosed, consistent set Γ of propositional formulas and a wellorder on the set of propositional formulas, Gödel defines by transfinite recursion:
 Γ_{0} := Γ,
 for all ordinals α, if there is a formula φ such that neither φ nor φ belong to Γ_{α}, let φ_{α} be the least such φ and define
Γ_{α}_{+1} := {ψ : (φ_{α} → ψ) ∈ Γ_{α}}.Otherwise, define Γ_{α}_{+1} := Γ_{α}.
 for all limit ordinals λ, Γ_{λ} := α<λ Γ_{α}.
For an ordinal α where Γ_{α}_{+1} = Γ_{α}, it follows that the valuation v defined as follows satisfies every formula in Γ: for all propositional letters p,v(p) = 1 ⇐⇒ p ∈ Γ_{α}.Independently, Mal’cev (1936, thm. 1) also proved the compactness theorem for propositional logic, again using the full strength of the Axiom of Choice. His proof relies on transfinite induction, letting κ be an uncountable cardinal and assuming that the compactness theorem holds for sets of propositional sentences with cardinality strictly less than κ. Let Γ be a finitelysatisfiable set of sentences with cardinality κ and wellordered in this order type. At each nonlimit stage α, he substitutes the αth sentence φ_{α} for a conjunction of literals. Supposing this has been done up to, but not including, stage α < κ, so we have a setΓ_{α} = φ_{β} : β < α φ_{β} : α β < κ . The αth substitution is made according to the following rule: as the initial segments of Γ_{α} are satisfiable, we have a collection of κmany models. One of the truthvalue assignments to the variables that occur in φ_{α} must coincide with κmany of the assignments for these models. Replace φ_{α} with φ_{α}, which is the conjunction of the letters in φ_{α} that are assigned true, together with the negation of the letters that are assigned false. By construction, the final set Γ_{κ} = φ_{α} : α < κ is satisfiable, and any satisfying model is also a model of the original Γ.Mal’cev claimed to have extended this result to firstorder logic in the same paper. However, his terminology is slightly ambiguous. What seems to be at issue is the claim that every sentence is ‘equivalent’ to a sentence; one of the form x_{1}. . . x_{m} y_{1}. . . y_{n}φ, where φ is an atomic formula. This is patently false: for instance, the arithmetical hierarchy does not collapse, so there exists a sentence that is not equivalent to a Π_{2}sentence, even over Peano Arithmetic. However, by ‘equivalent’ Mal’cev appears to mean equisatisfiable:as is well known, every formula of FOPL can be replaced with an equivalent formula in the Skolem normal form for satisfiability. (4)This is also noted in a review of Mal’cev’s later articles (Henkin and Mostowski 1959, 57). Under this interpretation, the statement is true. Skolem’s normal form for satisfiability can be found in (Skolem 1920):Theorem 1. If U is an arbitrary firstorder proposition, there exists a firstorder proposition U in normal form with the property that U is satisfiable in a given domain whenever U is, and conversely. (255)
Note that the languages of U and U are not in general the same. This result readily extends to sets of sentences and is a wellknown tool in model theory. (Nowadays, Skolemisation of a theory usually refers to the introduction of function symbols directly in order to prove, amongst other things, the downward LöwenheimSkolem theorem (Skolem 1920, 257–59). As we do not require this theorem, the predicate approach has the added advantage of not requiring Choice.)The first explicit, publshed proofs of a compactness theorem from completeness were given independently by Henkin (1948, 1949b, 1950) and Robinson (1949, 1951). The logics considered in these dissertations are firstorder logic / theory of simple types for Henkin, and restricted functional calculus for Robinson. However, the proof relies only upon the finitary nature of the deductive system and completeness of the logic. (The completeness theorem for propositional logic is independently proven by Bernays (1918, sec. 3)—see Zach (1999, 340–48) for a discussion on authorship—and Post (1921, 169). For the restricted functional calculus, it was first asked, for an empty set of premisses, in Hilbert and Ackermann (1928, 68). It was proven in the form of the model existence theorem—consistency implies satisfiability, which is also the form Henkin uses to prove compactness—for countable sets in Gödel (1929, 96–101) and for arbitrary sets, using the Axiom of Choice, in Henkin (1949b, p. 164, cor. 2) and Robinson (1951, chap. 3). As noted above, this easily extends to completeness of first order logic.)The compactness theorem finally receives its name in Tarski (1952) in two forms. The second form (p. 467, thm. 17) is the form we are familiar with. By AC, Tarski denotes the collection of arithmetical classes, which are classes of the formCL(φ) := {M : M = φ}where φ is a formula over a fixed firstorder language , and the M range overstructures. In his terminology, the compactness theorem is the statement thatΓ is a collection of Lformulas and {CL(φ) : φ ∈ Γ} = ∅ (which means Γ is(which means Γ is not finitelysatisfiable). The first form (p. 466, thm. 13) is a generalisation that applies to types (Chang and Keisler 1990, 78–79; Hodges 1997, 130–31).Whilst Tarski does not provide a topological argument for these theorems, relying upon completeness instead, he does draw some connection between a topological space based on AC and firstorder logic. By defining a closure operator and then quotienting by equivalence of models, he obtains a space homeomorphic to the one constructed at the end of section 5 of this article. (There are some foundational issues at play here, since each equivalence class is a proper class, as are the open sets. Tarski takes only a set of models as opposed to the whole class. We avoided this issue in our construction by considering the space of theories. As the class of theories is a set, by taking enough representatives (using, for example, the Axiom of Collection) we find that Tarski’s space will be homeomorphic to our construction in section 5.) As he observes, the resulting space is a Stone space, noting that compactness of the space follows from the compactness of the logic. (Tarski uses the term bicompact for what we call compact. Compact used to refer to the countable compactness property (Willard 1970, 304).)The ultraproduct proof is given in Frayne, Morel, and Scott (1962, p. 216, thm. 2.10), which is based on Łoś’ Theorem (p. 213, lemma 2.1)—see Łoś (1971, 105, “(2.6)”) for the original statement (without proof). The argument is similar to the one given in Section 4c. Frayne, Morel, and Scott (1962, 195) acknowledge that Alfred Tarski suggested the use of ultraproducts, which had several applications in the literature already, in proving the compactness theorem. David Gale gave a topological proof of the compactness theorem for propositional logic (as credited by Henkin (1949a, 48n4)), whilst Beth (1951) gives a topological proof of the completeness theorem before deriving compactness as a corollary. A direct topological proof is given by Frayne, Morel, and Scott (1962, p. 225, ex. 2), using a combination of ultraproducts and Stone spaces.More details on this history can be found in Dawson (1993) and the references therein.9. References and Further Reading
 Barwise, J., and Solomon Feferman, eds. 1985. ModelTheoretic Logics. Perspectives in Mathematical Logic. New York: Springer.
 A book on the modeltheory of many logics that extend firstorder logic.
 Beall, J. C., and Greg Restall. 2006. Logical Pluralism. Oxford: Clarendon Press.
 The book that started the contemporary debate on whether there is one correct foundational logic (logical monism) or more than one (logical pluralism). The authors defend logical pluralism.
 Bernays, Paul. 1918. “Beiträge zur axiomatischen Behandlung des LogikKalküls.” In Ewald and Sieg 2013, 231–68.
 Bernays’ habilitiation thesis, in which he proves the completeness theorem for propositional logic, amongst other results related to the chosen propositional calculus.
 Beth, E. W. 1951. “A Topological Proof of the Theorem of LöwenheimSkolemGödel.” Indagationes Mathematicae (Proceedings) 54:436–44. https://doi.org/10.1016/S13857258(51)500628.
 Beth presents a proof of the LöwenheimSkolemGödel theorem: a set of firstorder sentences Γ has a countable model if and only if Γ is consistent.
 Blass, Andreas. 1984. “Existence of Bases Implies the Axiom of Choice.” In Axiomatic Set Theory, edited by James E. Baumgartner, Donald A. Martin, and Saharon Shelah, 31–33. Contemporary Mathematics 31. Providence, RI: American Mathematical Society.
 Blass proves that if every vector space has a basis, then the Axiom of Choice holds, via the Axiom of Multiple Choice.
 Chang, C. C., and H. Jerome Keisler. 1990. Model Theory. 3rd ed. Studies in Logic and the Foundations of Mathematics 73. Amsterdam: NorthHolland.
 A classic model theory text.
 Cowen, Robert H. 1990. “Two Hypergraph Theorems Equivalent to BPI.” Notre Dame Journal of Formal Logic 31 (2): 232–40. https://doi.org/ 10.1305/ndjfl/1093635418.
 Cowen proves that the Boolean Prime Ideal theorem (and thus the Compactness Theorem) is equivalent to the Compactness Theorem restricted to propositional formulas formed from a disjunct of at most 3 literals, and is also equivalent to the statement “a graph G is 3colourable if every finite subgraph is 3colourable”.
 Dawson, John W., Jr. 1993. “The Compactness of FirstOrder Logic: From Gödel to Lindström.” History and Philosophy of Logic 14 (1): 15–37. https://doi.org/10.1080/01445349308837208.
 Another article detailing the development and history of the compactness theorems.
 Denyer, Nicholas. 1992. “Pure SecondOrder Logic.” Notre Dame Journal of Formal Logic 33 (2): 220–24. https://doi.org/10.1305/ndjfl/1093636099.
 Denyer proves that pure secondorder logic (where formulas only have predicate variables) without identity is compact, whilst the corresponding logic with only functional variables is not.
 Ebbinghaus, H.D. 1985. “Extended Logics: The General Framework.” In Barwise and Feferman 1985, chap. 2.
 Ebbinghaus presents a general framework for logics extending firstorder logic and discusses various modeltheoretic properties of these logics, in particular compactness and variations thereof.
 Enderton, Herbert B. 2001. A Mathematical Introduction to Logic. 2nd ed. San Diego: Harcourt/Academic Press.
 An introductory textbook on propositional, firstorder, and secondorder logic, as well as Gödel’s incompleteness theorems.
 Ewald, William, and Wilfried Sieg, eds. 2013. David Hilbert’s Lectures on the Foundations of Arithmetic and Logic: 1917–1933. Vol. 3 of David Hilbert’s Lectures on the Foundations of Mathematics and Physics: 1891–1933. Heidelberg: Springer.
 A collection of Hilbert’s works in the foundations of mathematics, with additional commentary and historical background, as well as a reproduction of Bernays’ habilitation thesis.
 Feferman, Solomon, John W. Dawson Jr., Stephen C. Kleene, Gregory H. Moore, Robert M. Solovay, and Jean van Heijenoort, eds. 1986. Publications 1929–1936. Vol. 1 of Kurt Gödel Collected Works. Oxford: Oxford University Press.
 A collection of many of Gödel’s important works, including his famous results on completeness, incompleteness, and compactness.
 Frayne, T., A. C. Morel, and Dana S. Scott. 1962. “Reduced Direct Products.” Fundamenta Mathematicae 51:195–228. https://doi.org/10.4064/fm513195228.
 This paper presents several results on properties reduced products and ultraproducts.
 Givant, Steven, and Paul Halmos. 2009. Introduction to Boolean Algebras. Undergraduate Texts in Mathematics. New York: Springer.
 An introductory textbook on algebraic, ordertheoretic, and topological aspects of Boolean algebras.
 Gödel, Kurt. 1929. “Über die Vollständigkeit des Logikkalküls.” Translated by Stefan BauerMengelberg and Jean van Heijenoort. In Feferman, Dawson, Kleene, Moore, Solovay, and Van Heijenoort 1986, 60–101.
 Gödel’s doctoral dissertation, in which he proves the completeness of the restricted functional calculus.
 Gödel, Kurt. 1930. “Die Vollständigkeit der Axiome des logischen Funktionenkalküls.” Translated by Stefan BauerMengelberg. In Feferman, Dawson, Kleene, Moore, Solovay, and Van Heijenoort 1986, 102–23.
 Based on his 1929 doctoral dissertation, Gödel proves the compactness (for countable sets of sentences) of restricted functional calculus from the completeness theorem.
 Gödel, Kurt. 1932. “Eine Eigenshaft der Realisierungen des Aussagenkalküls.” Translated by John W. Dawson Jr. In Feferman, Dawson, Kleene, Moore, Solovay, and Van Heijenoort 1986, 238–41.
 Gödel presents his proof of the compactness theorem in general for propositional logic.
 Goldblatt, Robert. 1998. Lectures on the Hyperreals: An Introduction to Nonstandard Analysis. Graduate Texts in Mathematics 188. New York: Springer.
 A graduatelevel textbook on the subject of nonstandard analysis, including the foundational and modeltheoretic justification for its methods.
 Gonczarowski, Yannai A., Scott Duke Kominers, and Ran I. Shorrer. 2019. “To Infinity and Beyond: Scaling Economic Theories via Logical Compactness.” Harvard Business School Entrepreneurial Management Working Paper, no. 19–127, revised November 9, 2020. https://doi.org/10. 2139/ssrn.3409828.
 This substantial working paper demonstrates several applications of the compactness theorem in economics.
 Griffiths, O., and A. C. Paseau. 2022. One True Logic. Oxford: Oxford University Press.
 The authors argue that there is one correct foundational logic, and that it is highly infinitary.
 Hajnal, A., and A. Kertész. 1972. “Some New Algebraic Equivalents of the Axiom of Choice.” Publicationes Mathematicae Debrecen 19:339–40.
 The equivalence, under ZF, of the Axiom of Choice with the existence of groups structures (or other algebraic structures) on any set is proven in this short article.
 Henkin, Leon A. 1948. “The Completeness of Formal Systems.” PhD diss., Princeton University.
 Henkin’s doctoral dissertation which contains his proof of the completeness and compactness theorems for firstorder functional calculus and the simple theory of types, as well as applications of the compactness theorem to algebra among other results. These results were published in Henkin (1949b, 1950).
 Henkin, Leon A. 1949a. “Fragments of the Propositional Calculus.” Journal of Symbolic Logic 14:42–48. https://doi.org/10.2307/2268976.
 Henkin demonstrates how to obtain complete axiomatisations for fragments of propositional logic.
 Henkin, Leon A. 1949b. “The Completeness of the FirstOrder Functional Calculus.” Journal of Symbolic Logic 14:159–66. https://doi.org/10. 2307/2267044.
 This article contains Henkin’s proof of the completeness and compactness theorems of firstorder functional calculus, based on his doctoral dissertation.
 Henkin, Leon A. 1950. “Completeness in the Theory of Types.” Journal of Symbolic Logic 15:81–91. https://doi.org/10.2307/2266967.
 This article contains Henkin proves the completeness theorem for the theory of simple types, based on his doctoral dissertation.
 Henkin, Leon A., and Andrzej Mostowski. 1959. Review of Anatoliĭ Ivanovič Mal’cev. 1941. “Ob odnom obščém métodé polučéniá lokal’nyh téorém téorii grupp.” Ivanovskij Gosudarstvénnyj Pédagogičéskij Institut, Učényé zapiski, Fizikomatématičéskié nauki 1 (1): 3–9 and “O prédstavléniáh modéléj.” 1956 by Anatoliĭ Ivanovič Mal’cev. Doklady Akadémii Nauk SSSR 108:27–29. Journal of Symbolic Logic 24 (1): 55–57. https://doi. org/10.2307/2964581.
 Henkin and Mostowski’s review of two of Mal’cev’s important papers on applications of the compactness theorems in algebra. English translations of these article are found in Mal’cev (1971, 15–26).
 Hilbert, D., and W. Ackermann. 1928. “Grundzüge der theoretischen Logik.” In Ewald and Sieg 2013, 809–915.
 A collection of Hilbert’s works in the foundations of mathematics, with additional commentary and historical background, as well as a reproduction of Bernays’ habilitation thesis.
 Hodges, Wilfrid. 1997. A Shorter Model Theory. Cambridge: Cambridge University Press.
 A comprehensive textbook on model theory.
 Howard, Paul E. 1975. “Łoś’ Theorem and the Boolean Prime Ideal Theo rem Imply the Axiom of Choice.” Proceedings of the American Mathematical Society 49:426–28. https://doi.org/10.2307/2040659.
 In this paper, Howard proves the title statement and discusses the possibility of assumption of the Boolean Prime Ideal Theorem.
 Howard, Paul E., and Jean E. Rubin. 1998. Consequences of the Axiom of Choice. Mathematical Surveys and Monographs 59. Providence, RI: American Mathematical Society.
 A comprehensive source of the myriad Choice principles that occur throughout mathematics, organised by equivalence as well as topic. It also includes descriptions of the many models of set theory that demonstrate nonprovable implications between the different forms of Choice.
 Jech, Thomas J. 1973. The Axiom of Choice. Studies in Logic and the Foundations of Mathematics 75. Amsterdam: NorthHolland.
 A textbook on the Axiom of Choice and other Choicelike principles, which covers the standard permutation models used for proving the independence of one statement from another.
 Jech, Thomas J. 2003. Set Theory. 3rd ed. Springer Monographs in Mathematics. Berlin: Springer.
 A graduatelevel textbook on axiomatic set theory, covering infinitary combinatorics, large cardinals, inner models, and forcing.
 Kanamori, Akihiro. 2009. The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings. 2nd ed. Springer Monographs in Mathematics. Berlin: Springer.
 A graduatelevel textbook on the large cardinal heirarchy.
 Keisler, H. Jerome. 1965. “A Survey of Ultraproducts.” In Logic, Methodology and Philosophy of Science II: Procedings of the 1964 International Congress, edited by Yehoshua BarHillel, 112–26. Studies in Logic and the Foundations of Mathematics. Amsterdam: NorthHolland.
 A survey on the use of ultraproducts in mathematics, including its relationship with the compactness theorem for firstorder logic via Łoś’ theorem.
 Keisler, H. Jerome. 1970. “Logic with the Quantifier ‘There Exist Uncountably Many’.” Annals of Pure and Applied Logic 1:1–93. https://doi.org/ 10.1016/S00034843(70)800055.
 An extensive paper on the modeltheoretic properties of logics that include the quantifier ‘there exist uncountably many’.
 Keisler, H. Jerome, and Julia F. Knight. 2004. “Barwise: Infinitary Logic and Admissible sets.” The Bulletin of Symbolic Logic 10 (1): 4–36. http s://doi.org/10.2178/bsl/1080330272.
 A survey of the Barwise compactness theorem of infinitary logic.
 Kunen, Kenneth. 2011. Set Theory. Studies in Logic 34. London: College Publications.
 A textbook on axiomatic set theory, covering infinitary combinatorics and forcing.
 Lindström, Per. 1969. “On Extensions of Elementary Logic.” Theoria 35:1– 11. https://doi.org/10.1111/j.17552567.1969.tb00356.x.
 Lindström proves his famous theorem characterising firstorder logic via the (countable) compactness and LöwenheimSkolem theorems.
 Łoś, Jerzy. 1971. “Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres.” In Mathematical Interpretation of Formal Systems, 2nd ed., 16:98–113. Studies in Logic and the Foundations of Mathematics. Amsterdam: NorthHolland.
 In this article (originally published in 1955), Łoś states without proof the theorem which bears his name.
 Makowsky, J. A. 1985. “Compactness, Embeddings and Definability.” In Barwise and Feferman 1985, chap. 18.
 Makowsky presents results on several modeltheoretic properties of abstract logics, including generalised compactness properties.
 Mal’cev, Anatoliĭ Ivanovič. 1936. “Investigations in the realm of mathematical logic.” In Mal’cev 1971, 1–14.
 In this article, Mal’cev proves the compactness theorems for propositional and firstorder logic.
 Mal’cev, Anatoliĭ Ivanovič. 1971. The Metamathematics of Algebraic Systems: Collected papers: 1936–1967. Edited and translated by Benjamin Franklin Wells III. Amsterdam: NorthHolland.
 Translations of most of Mal’cev’s works on algebraic applications of mathematical logic.
 Mann, Allen L., Gabriel Sandu, and Merlijn Sevenster. 2011. IndependenceFriendly Logic: A GameTheoretic Approach. London Mathematical Society Lecture Note Series 386. Cambridge: Cambridge University Press.
 This monograph provides an introduction to independencefriendly logic, a logic with gametheoretic semantics.
 Mannila, Heikki. 1983. “A Topological Characterization of (λ, µ)^{∗}Compactness.” Annals of Pure and Applied Logic 25 (3): 301–5. https://doi.org/10.1016/01680072(83)900222.
 Mannila gives a modeltheoretic characterisation of the (λ, µ)compactness of the model space of a logic.
 Moore, Gregory H. 1982. Zermelo’s Axiom of Choice: Its Origins, Development, and Influence. Studies in the History of Mathematics and Physical Sciences 8. New York: SpringerVerlag.
 A comprehensive book detailing the history of Zermelo’s explication of the Axiom of Choice and the consequent controversy surrounding it in the early twentieth century.
 Paseau, A. C. 2010a. “Proofs of the Compactness Theorem.” History and Philosophy of Logic 31 (1): 73–98. https://doi.org/10.1080/014453409 03495340. Corrected in “Proofs of the Compactness Theorem.” History and Philosophy of Logic 32, no. 4 (2011): 407. https://doi.org/https://doi.org/10.1080/01445340.2011.618261.
 This article examines different proofs of the compactness theorem, including some of the ones included in the present article, and draws some philosophical conclusions.
 Paseau, A. C. 2010b. “Pure SecondOrder Logic with SecondOrder Identity.” Notre Dame Journal of Formal Logic 51 (3): 351–60. https://doi. org/10.1215/002945272010021.
 Pure secondorder logic is secondorder logic without firstorder or functional variables. In the context of secondorder logic, it is therefore, in a sense, the complement of firstorder logic. The article states and proves some metalogical results for this logic.
 Paseau, A. C., and Owen Griffiths. 2021. “Is English Consequence Compact?” Thought: A Journal of Philosophy 10 (3): 188–98. https://doi. org/10.1002/tht3.492.
 A detailed investigation of the validity of the ‘planets’ argument discussed in section 2b of the present article.
 Pincus, David. 1974. “The Strength of the HahnBanach Theorem.” In Victoria Symposium on Nonstandard Analysis: University of Victoria 1972, edited by Albert Hurd and Peter Loeb, 203–48. Lecture Notes in Mathematics 369. Berlin: SpringerVerlag.
 Pincus shows the consistency (relative to ZF) of the HahnBanach theorem holding whilst the Boolean Prime Ideal Theorem failing.
 Poizat, Bruno. 2000. A Course in Model Theory. Translated by Moses Klein. Universitext. An Introduction to Contemporary Mathematical Logic. New York: Springer.
 A graduatelevel textbook on model theory.
 Post, Emil L. 1921. “Introduction to a General Theory of Elementary Propositions.” American Journal of Mathematics 43 (3): 163–85. https://doi. org/10.2307/2370324.
 Based on his doctoral dissertation, Post proves the completeness theorem for propositional calculus, as well as some results on manyvalued logics.
 Putnam, Hilary. 1980. “Models and Reality.” Journal of Symbolic Logic 45 (3): 464–82. https://doi.org/10.2307/2273415.
 In this article, Putnam sets out the argument mentioned in section 3 of the present article.
 Richter, Marcel K. 1966. “Revealed Preference Theory.” Econometrica 34 (3): 635–45. https://doi.org/10.2307/1909773.
 Richter characterises the representability and rationality of consumers, where the latter proof uses the OrderExtension Principle.
 Robinson, Abraham. 1949. “On the Metamathematics of Algebraic Systems.” PhD diss., Birkbeck College, University of London.
 Robinson’s doctoral dissertation, which includes his proof of the completeness and compactness theorems for firstorder functional calculus. These results were later published in Robinson (1951).
 Robinson, Abraham. 1951. On the Metamathematics of Algebra. Studies in Logic and the Foundations of Mathematics 4. Amsterdam: NorthHolland.
 A monograph largely based on Robinson’s doctoral dissertation.
 Robinson, Abraham. 1966. NonStandard Analysis. Studies in Logic and the Foundations of Mathematics 42. Amsterdam: NorthHolland.
 A foundational text in nonstandard analysis, providing a rigorous justification of its methods.
 Rubin, Herman, and Dana S. Scott. 1954. Some Topological Theorems Equivalent to the Boolean Prime Ideal Theorem. Presented at 503rd meeting of the American Mathematical Society, May 1, 1954. Abstract in W. Green. “The May Meeting in Yosemite.” Bulletin of the American Mathematical Society 60 (1954): 386–99. https://doi.org/10.1090/ S000299041954098270.
 At this talk, several topological theorems are proven to be equivalent to the Boolean Prime Ideal Theorem.
 Shapiro, Stewart. 1991. Foundations without Foundationalism: A Case for SecondOrder Logic. Oxford Logic Guides 17. Oxford: Clarendon Press.
 A detailed and extensive account of secondorder logic, taking in its historical, mathematical and philosophical aspects.
 Shapiro, Stewart. 2014. Varieties of Logic. Oxford: Oxford University Press. https://doi.org/10.1093/acprof:oso/9780199696529.001.0001.
 The author defends a more radical form of logical pluralism (the thesis that there is more than one correct foundational logic) than that of Beall and Restall (2006).
 Skolem, Thoralf. 1920. “LogicoCombinatorial Investigations in the Satisfiability or Provability of Mathematical Propositions: A Simplified Proof of a Theorem by L. Löwenheim and Generalizations of the Theorem.” Translated by Stefan BauerMengelberg. In From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, edited by Jean van Heijenoort, 254–63. Cambridge, MA: Harverd University Press.
 A translated extract from Skolem’s 1920 paper, in which he presents his normal form for formulas in firstorder logic as well as presenting a fullycorrect proof of the downward LöwenheimSkolem theorem for countable sets of sentences, which uses his Axiom of Choice.
 Skolem, Thoralf. 1922. “Some Remarks on Axiomatized Set Theory.” Translated by Stefan BauerMengelberg, 290–301.
 A translated transcript of Skolem’s address at the Fifth Congress of Scandinavian Address held in Helsinki 4th–7th July 1920, in which he discusses several foundational aspects of set theory, and in particular demonstrates his ‘paradox’.
 Stephenson, R. M., Jr. 1984. “Initially κCompact and Related Spaces.” In Handbook of SetTheoretic Topology, edited by Kenneth Kunen and Jerry E. Vaughan, 603–32. Amsterdam: NorthHolland.
 This article presents a survey of results on (κ, λ)compactness of topological spaces.
 Sutherland, Wilson A. 2009. Introduction to Metric and Topological Spaces. 2nd ed. Oxford: Oxford University Press.
 An introductory textbook to topology. Chapter 13 on compactness is particularly relevant to this article.
 Szpilrajn, Edward. 1930. “Sur l’extension de l’ordre partiel.” Fundamenta Mathematicae 16:386–89. https://doi.org/10.4064/fm161386389.
 In this short paper, Szpilrajn (also known as Marczewski) proves his Order Extension Principle.
 Tarski, Alfred. 1952. “Some Notions and Methods on the Borderline of Algebra and Metamathematics.” In Proceedings of the International Congress of Mathematicians: Cambridge, Massachussetts, U.S.A., August 30–September 6, 1950, 1:705–20. Providence, RI: American Mathematical Society.
 Tarski presents several results in the language of arithmetical classes (the classes of structures that satisfy a particular firstorder sentence). Theorem 13 gives the compactness theorem its name.
 Väänänen, Jouko. 2007. Dependence Logic: A New Approach to Independence Friendly Logic. 70. Cambridge: Cambridge University Press.
 A monograph on dependence logic, and other logics with gametheoretic semantics.
 Willard, Stephen. 1970. General Topology. Reading, MA: AddisonWesley.
 An introductory textbook on topology. Chapter 6 on compactness is particularly relevant to this article.
 Zach, Richard. 1999. “Completeness Before Post: Bernays, Hilbert, and the Development of Propositional Logic.” Bulletin of Symbolic Logic 5 (3): 331–66. https://doi.org/10.2307/421184.
 A historical article on Bernays and Hilbert’s role in development of mathematical logic, particularly focused on propositional logic.
Author InformationA. C. Paseau
Email: alexander.paseau@philosophy.ox.ac.uk
University of Oxford
United KingdomandRobert Leek
Email: r.leek@bham.ac.uk
University of Birmingham
United Kingdom
{∃_{≥} ∃_{≥} ∃_{≥} k } { } 





























































































L ⊂ L ⊂ · · · ⊂ L ⊂ · · · 


















































ITits basic open sets O , where O ∈ τ , and O = X for all but finitely ele_{i} _{i} _{i} _{i} _{i}i∈I 





× · · · × { × · · · × ∀ ∈ } 

function f : Y →ITITi∈I X_{i}, f is continuous if and only if π_{i} ◦f is continuous for all 






_{j}_{∈I} X_{j} → X_{i} is the projection map onto the ith coordinate. If 





n: finite is a basis for . Given an arbitrary col 




































nis complete if for every with .) One may then show 










































unsatisfiable) then there exists a finite set ∆ ⊂ Γ such that n{CL(φ) : φ ∈ ∆} = 

