# The Compactness Theorem

The compactness theorem is a fundamental theorem for the model theory of classical propositional and first-order 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 Choice-like principles before later calibrating the strength of these and the compactness theorems themselves over Zermelo-Fraenkel 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 non-standard models of arithmetic and analysis. We then provide several different proofs of the compactness theorem based on different Choice-like principles.

In later sections, we discuss several variations of compactness in logics that allow for infinite conjunctions / disjunctions or generalised quantifiers, and in higher-order 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.

## Contents

- Introduction
- Compactness: Common Logics and Natural Language
- Implications of Compactness
- Some Non-topological Proofs
- Connection to Topology
- Extensions and Generalisations
- Relative Strength
- 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 of is satisfiable then is also satisfiable.
- If is an unsatisfiable set of sentences then so is for some finite subset 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 for some finite subset of .

This equivalence follows from

The compactness theorem is said to hold for a logic precisely when the logic is compact.

Alongside its close cousin, the completeness theorem for first-order logic, the compactness theorem for first-order logic is one of the most important theorems in contemporary logic.

In this entry, 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 first-order logic (Section 3). Following that, we give some non-topological proofs of the compactness of propositional and first-order 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 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 , and some truth-functionally complete set of Boolean connectives, for instance . If we denote by a propositional logic with sentential atoms, 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 is compact, whatever its set of truth-functional connectives may be. Notice that when is finite, the compactness of any 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 . (This set is of size exactly just when the set of connectives is truth-functionally complete.)

First-order logic with standard semantics is also compact. This fact is of tremendous importance for logic and its applications, since first-order logic remains the canonical logic to this day, the widespread interest in higher, supplementary and alternative logics notwithstanding. By `first-order logic’, we understand throughout first-order logic with identity. First-order logic without identity is of course also compact, since it is a sublogic of first-order logic with identity.

By second-order logic we mean second-order logic with standard or full semantics, in which second-order -place predicate variables range over all the -tuples from the domain of interpretation (and similarly for functional variables). In contrast to first-order logic, second-order logic is not compact. To see this, let be a sentence of first-order logic satisfied in all and only models with domain of size may thus be taken as , as , and so on. Since first-order logic is a sublogic of second-order logic, is a sentence of second-order logic too. Consider next the sentence

where is a binary predicate variable, ` is functional’ abbreviates , ` is injective’ abbreviates and ` is surjective’ abbreviates . Any interpretation of this sentence states that the domain is Dedekind-infinite. The following second-order argument is then valid:

However, no finite subset of the premisses entails the conclusion. For let the finite subset be and take . Then there is a model of size in which the premisses are true but the argument’s conclusion is false. Hence second-order 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 is (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, first-order and second-order 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 natural-language arguments:

The first argument is logically valid, whereas the second argument 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’s 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 for some finite subset 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:

Now as a matter of empirical fact, there is some finite number such that I do not have a great-grandfather (which 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 second-order-logic argument presented earlier:

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 first-order 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).

- Any compact logic extending first-order logic cannot express the notions of finitude or infinitude (of a model). Suppose towards a contradiction that is satisfied by all and only finite models. Then is unsatisfiable, and hence by compactness it must have an unsatisfiable finite subset, which must be a subset of for some . But any finite model with domain of size satisfies (any subset of) , thereby contradicting our hypothesis. And if there were a sentence satisfied by all and only infinite models then 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 of first-order sentences) is not definable by a single sentence . In these arguments, together with any finite subset of is satisfiable, but is not, contradicting compactness.
Informally speaking, in these applications the -property is the conjunction of the

*-properties*; in our example, the -property was having size at least 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 first-order language with a single unary function symbol, and take the sentenceThe models of this sentence are sets endowed with an injective, but non-surjective function. By the pigeonhole-principle, 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 is interpreted as the identity function on the natural numbers.As a further illustration of this technique, compactness implies that the class of torsion-free abelian groups is not finitely-axiomatisable in first-order logic. (A group is

*torsion-free*if the identity is the only element with finite order. The prototypical example of a torsion-free abelian group is (.) For if it were, by the single sentence say, then the set

would be finitely-satisfiable (for finite sets where the sums are bounded by in the sentences from the rightmost set, take the integers under addition modulo for some prime ). But the set itself is unsatisfiable, sinceis satisfied by all and only torsion-free abelian groups. This contradicts compactness. Note that here the -property is that all non-identity elements of the model have infinite order, and the -property that all non-identity elements have order (all these properties incorporate the abelian group axioms too).As a still further illustration, the same type of argument shows that the class of algebraically-closed fields is also not finitely-axiomatisable. The relevant -property is that the field is algebraically-closed, and the relevant -property is

This style of argument is easily applied to many other domains.

- Suppose and are two sets of sentences of a compact logic (in which conjunction and negation are definable) with the property that every model satisfies either or but not both. Then there is a sentence such that is logically equivalent to (meaning that and have the same models) and is logically equivalent to (Chang and Keisler 1990, p. 12, cor. 1.2.15).
- The compactness theorem may be used to show that any first-order theory of arithmetic satisfied by the standard model has a non-standard model. (By the standard model of arithmetic, for the theory in question, we mean the structure of natural numbers with the standard interpretation of the non-logical symbols in the language of denotes 0, the two-place symbol + denotes addition, denotes multiplication, and so forth. A nonstandard model can have `infinite’ elements: objects greater than those denoted by the terms for all . As an ordered set, a nonstandard model looks like followed by blocks of , which themselves form a dense linear order without endpoints.) Assuming that each numeral is definable in , consider
where is any constant not in the language of . Any finite subset of is satisfied by the standard model, because we may interpret as a number distinct from those where occurs in the given finite subset. Hence by compactness, has a model . The reduct of to the language of is non-standard since it contains an element (the denotation of in not identical to any natural number.Supplementing the argument just given with an appeal to the

*downward Löwenheim-Skolem Theorem*(Chang and Keisler 1990, p. 66, cor. 2.1.4; Hodges 1997, p. 72, cor. 3.1.4) shows that any such first-order theory of arithmetic is not even -categorical, since it has a countably infinite non-standard 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 -categorical. To see this, run the previous argument supplemented by an application of the*downward Löwenheim-Skolem Theorem*for a*complete*theory of arithmetic . 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 non-standard models of real analysis. Let be a first-order theory of analysis satisfied by the standard model (the ordered field of real numbers). As above, consider where is any constant not in is satisfied by the standard model, because we may interpret as a positive real number smaller than , where is the largest number for which the sentence is in the given finite subset. Hence by compactness, has a model . The reduct of to the language of is non-standard since it contains an element not identical to any real number. Indeed, this element must be a positive infinitesimal, meaning that it is a number greater than but smaller than every . As well as infinitesimals, our non-standard model also contains infinite elements, since the the model satisfies and thus any non-zero 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*non-standard analysis*: see Goldblatt (1998) or the original Robinson (1966). Furthermore, since and have the same theory, any sentence in the language of that can be proven from will hold in and thus automatically holds in . This is the*transfer principle*of non-standard analysis.Since second-order logic is incompact, the arguments just given fail for second-order theories of arithmetic and analysis. Indeed, there are categorical second-order axiomatisations of arithmetic (for example, Peano Arithmetic with second-order 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 second-order theories, consult (chap. 3–6).

- Assuming the downward Löwenheim-Skolem Theorem, another corollary of the compactness of first-order logic is the
*upward Löwenheim-Skolem Theorem*(Chang and Keisler 1990, p. 67, cor. 2.1.6; Hodges 1997, p. 127,cor. 5.1.4). This upward version of the theorem states that if a first-order 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 for each in the domain of , and the interpretation of in is simply together with the sentences for all distinct , where the are new constants.This set is finitely-satisfiable (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 . 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öwenheim-Skolem Theorem to .The upward Löwenheim-Skolem Theorem may be applied to show not only that theories of arithmetic and analysis satisfied by their respective standard models have non-standard models, but also that they have non-standard models of every infinite cardinality. More generally, any first-order theory in a countable language satisfied by an infinite model has models of every cardinality. Applying this to or , we obtain*Skolem’s paradox*: if there exists a model of set theory, then there exists a countably-infinite model, which will nonetheless model the existence of uncountable sets (Skolem 1922, 295–96).The upward and downward Löwenheim-Skolem Theorems and the so-called 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 mathematical-scientific 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. - The compactness theorem may be used to prove the
*Order-Extension Principle*(also known as*Szpilrajn’s Extension Theorem*): any partial order may be extended to a linear order. A partial order () consists of a domain with an irreflexive and transitive relation . A linear order is a partial order satisfying the additional linearity axiom . A linear order () extends the partial order () just when for all in , if then ; in other words, the identity map from () into () is a homomorphism. The notions of partial and linear order are first-order definable in the language consisting of a single two-place non-logical 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 Order-Extension 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 Order-Extension Principle? A relatively straight-forward 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 (), let be a set of sentences consisting of the*(Robinson) diagram*of () (the diagram of an -structure is the set of literals—atomic sentences or negations of atomic sentences—in the language {}, where are new constant symbols, satisfied in the expansion of where we interpret for each .), together with the axioms for all distinct , .

Since every partial order with a finite domain can be extended to a linear order, it follows that any finite subset of is satisfiable. By compactness, is therefore satisfiable. If is a model of then () embeds into the -reduct of , which we call (), via to () say. The required linear order extending () is the inverse under of the restriction of the order to , that is if and only if .Note in passing that the Order-Extension Principle implies that every set can be linearly ordered: simply consider a linear order that extends the empty partial order on .

The compactness theorem for first-order 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 Non-topological Proofs

In this section, we give three styles proofs of the compactness of propositional and first-order logic that do not draw on topology. These three proofs illustrate some important techniques, and could be broadly classified as deductive, syntactic, 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 well-formed formulas and any well-formed 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:

(1) Assumption

(2) From (1) by Completeness

(3) From (2) by the finiteness of proofs

(4) From (3) by Soundness

Here 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; second-order 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: Henkin-Style Proofs

This proof is modelled on Henkin’s (1949b) proof of the completeness theorem for first-order logic, with its deductive core replaced by a semantic one. We begin with a relatively concrete argument for the simplest case of before passing to more abstract versions. Unlike the usual versions of the proof, our argument does not assume any particular set of truth-functional connectives, only that the set of sentences is countably-infinite (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 be an enumeration of the set of sentences of . Given a finitely-satisfiable set , define a denumerable sequence of sets as follows:

By definition, is finitely-satisfiable for all , hence is finitely-satisfiable since any finite subset of must be drawn from some .

From , define the valuation by letting if and only if , where is a sentence letter. We now prove that is a valuation in which all the sentences in (not just the sentence letters) are true. Suppose towards a contradiction that for some . Without loss of generality (renumbering sentence letters if necessary), let be all the sentence letters in with truth-value 1 under and all the sentence letters in with truth-value 0 under (one of these sets may be empty, in which case the argument to follow is easily modified). By the definition of , none of is in so for each of these, let be a finite subset of such that is unsatisfiable (); some such must exist given that was omitted in the construction of . Now consider the set

Any valuation in which all the elements of are true is one in which each of is false, since is unsatisfiable, and so any valuation in which and all elements of are true is one in which the sentence letters have truth-value 0. It follows that any such valuation is one in which is false, since contains no sentence letters other than and . Hence is unsatisfiable, contradicting the fact that this set is a finite subset of . Having proved by *reductio* that any sentence in is true under , it follows that , which is a subset of , is satisfiable. It is obvious from its construction that is a maximal finitely-satisfiable set, meaning that it is finitely-satisfiable and none of its proper extensions are finitely-satisfiable.

A more abstract version of the argument just presented runs as follows. Suppose is finitely-satisfiable. Order by inclusion the set of finitely-satisfiable sets of sentences of the language containing . is non-empty, since it contains at least . Any chain in 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 finitely-satisfiable 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 , 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 has a maximal element, that is to say, a maximal finitely-satisfiable set extending . We then reason as in the previous paragraph to show that all the elements of are true under the valuation defined on sentence letters by if and only if is a member of this maximal finitely-satisfiable 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 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 . Is this use of a -equivalent 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 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 ; the derived strong and weak inequality symbols have their customary meanings ( means that and so on). A *filter* on a Boolean algebra is then a subset of such that:

- 1 ; ;
- ;
- .

An *ultrafilter* is a maximal filter on , or alternatively a filter on that contains exactly one of or for each . 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 ‘s compactness to rely not on Zorn’s Lemma but on the -weaker Ultrafilter Lemma instead. (Henceforth we assume that the set of propositional connectives is truth-functionally complete.) Consider the Boolean algebra whose domain is the set of equivalence classes of sentences of 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 well-defined); 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 finitely-satisfiable set , form the set consisting of all the sentences entailed by some finite subset of , that is,

Clearly, is a subset of , and also has the following three properties:

- but (since is finitely-satisfiable);
- ;
- .

In other words, is a filter on the Boolean algebra of sentences of . It is the smallest filter containing , that is to say, is a filter-base for . By the Ultrafilter Lemma, may be extended to an ultrafilter. The alternative definition of an ultrafilter shows that this ultrafilter is a maximal finitely-satisfiable set of sentences containing . The rest of the proof proceeds as above. We have thus proved the compactness of using the Ultrafilter Lemma rather than Zorn’s Lemma.

The compactness of first-order 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 where is the first-order language in which each of the sentences in our given finitely-satisfiable set is expressed, is the set of formulas of , and 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 as a source of *witnesses*. Then also has size (since for infinite ), and so we can well-order both the set of formulas and the set of new constant symbols in order-type . We now augment the set recursively by exploiting the well-ordering of and the well-ordering of the set of new constants (each well-ordering being of type ). Let and for a limit. For the successor case, let

where denotes with substituted for any free occurrences of in , if is the formula in the ordering of and is the first constant in the ordering of the set of constants not to appear in any element of nor in ; otherwise (if the formula is not existential) let . Finally, let and define as the set of sentences entailed by any finite subset of , that is,

An identical argument to the one in the propositional case now shows that is a filter on the Boolean algebra of the first-order -sentences quotiented by logical equivalence. The only difference lies in the verification that , in other words, that is finitely-satisfiable. For if

were unsatisfiable, with and is the greatest constant subject to their well-order ( and here are natural numbers, and the and -indices are ordinals smaller than ), then

But if the premisses

are jointly satisfiable then they cannot entail both and . The reason is that if there is a model in which this premiss set and are satisfied, then there is a model in which the interpretation of may be chosen to witness the truth of , since does not appear in any other sentence than .

Having verified that is a filter, we invoke the Ultrafilter Lemma as before to extend to an ultrafilter . Note that contains and hence is *witness-complete*—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 if and only if . The interpretation of the constant is ‘s equivalence class, []; the interpretation of the function symbol applied to is ; and for any -place relation symbol and closed terms , holds in the model if and only if is an element of . A routine argument shows that this interpretation is well-defined 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 second-order 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 *Well-Ordering Principle*. In this alternative argument for the compactness of first-order logic, we construct a set of constants disjoint from the set of constants of , one for each ordered pair in . (If we were to formalise this argument in our set-theoretic metatheory, say , we may for instance code each constant as . The point is that no Choice principles are required for this recursive definition.) Then add Skolem sentences for every such ordered pair . This gives us a new set of sentences in a language . Iterate this process -times, constructing a chain of sets of sentences , and a corresponding chain of languages . By an inductive argument, each is readily seen to be finitely-satisfiable (there is no need to assume the well-ordering of at this point), hence so is . 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 first-order sentences that satisfies the following axioms. (For brevity, we use take as primitive symbols in our first-order logic.)

- For every atomic sentence , if then ,
- For every closed term , ,
- If is an atomic formula with a single free variable , and are closed terms such that , then ,
- If is a sentence and , then ,
- If is a finite set of sentences, then
- implies ,
- implies for some ,

- If is a formula with a single free variable , then
- implies for every closed term ,
- implies for some closed term .

Given a Hintikka set , we can construct a term model (using the same definition given above) that satisfies (Hodges 1997, 40–42).

### c. Semantic: Ultraproduct Proofs

In this subsection, we prove the compactness theorem for first-order 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 be a collection of first-order structures of the same signature, indexed by , and an ultrafilter over this indexing set . In this context, the Boolean algebra is with the subset ordering , so a filter is a set of subsets of which does not contain the empty set and which is closed under finite intersection and upward containment. Denote the domain of each by . When is an ultrafilter over , defining by yields an equivalence relation over the product

(We tend to view elements of the product as generalised sequences .) The characteristic function of is a finitely-additive full measure on and thus intuitively the elements of are `large subsets of ‘: two functions in are identified by this relation precisely when they agree `-almost-everywhere’. We define a new structure as follows:

- Domain of quotiented by ; denotes the equivalence class of ;
- ;
- ;
- if and only if .

for any -place function and relation symbols and and any constant of the first-order language in question. As may be checked, the fact that is a filter means that the definitions just given do not depend on the choice of representatives from . For atomic we have by definition:

Łoś’ theorem, which is proved by induction on the complexity of , extends this to all :

for all , if and only if .

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 first-order logic from Łoś’ Theorem, let be a finitely-satisfiable set of first-order sentences. Let be the set of finite subsets of and suppose we are given for each a model for the sentences in . For let

The collection of is closed under finite intersection because , hence is also closed under finite intersection; by definition, is closed under upward containment, and clearly does not contain the empty set. Thus satisfies the conditions for being a filter and may therefore be extended to an ultrafilter . Now for any , we have and , from which it follows that . By Łoś’ theorem, . This is true for every , so , in other words if is satisfiable. Intuitively, the model was designed so as to agree with on the `large subset’ of and in particular to agree with on the truth-value of each element of ; as this is true for all , satisfies . This completes the ultraproduct proof of the compactness of first-order 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 non-standard model of arithmetic (see Section 2c) with language and standard model with domain . We extend the language to by introducing a new constant symbol and for each , let be the -expansion of given by interpreting . Let be the filter of cofinite subsets of and let be an ultrafilter that extends . Then the particular instance of Łoś’ Theorem can be proven for and , utilising the well-foundedness of in place of the Axiom of Choice. Thus satisfies the same -sentences as , and for all ,

so by Łoś’ Theorem it follows that . Therefore is a non-standard model of arithmetic.

## 5. Connection to Topology

Tarski (1952) article gives the compactness theorem its name (see theorems 13 and 17), observing its similarity with the finite-intersection-property 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 is a collection of open subsets of whose union is , and that a space 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 *finite-intersection property*—every finite subset has non-empty intersection—has non-empty intersection. Intuitively, you cannot `escape’ a compact space; every collection of points will accumulate somewhere.) 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 , initially assuming for the sake of simplicity that the version of in question is equipped with a truth-functional set of connectives.

Let be the set of all valuations of . For each sentence of define , the set of valuations in which is true. Since , the sets form a basis for a topology on ; call this basis . (A *basis* for a topology is a collection of open sets with the property that if and only if for some . Given a collection of subsets of , if its union is and for all , for some , then there exists a unique topology on with basis (Willard 1970, p. 38, thm. 5.3).) The topological space we shall be interested in has domain and topology generated by the basis ; with this topology, is the *dual space* of the Boolean algebra of sentences of . Thus properties of this space are determined only by the logical properties of valuations.

Now consider any set of sentences of . is unsatisfiable if and only if any valuation assigns truth-value 0 to at least one of its members, or equivalently any valuation assigns truth-value 1 to at least one sentence such that . It follows that is unsatisfiable if and only if each valuation is in some open set of the form where , or equivalently that is an open cover of the topological space . The compactness of is therefore equivalent to the following claim:

if is an open cover of then there is a finite subset

of such that is an open cover of .

Thus is compact if and only if is compact. (Note that any open set is the union of some basis sets and that any basis set is identical to for . Also, a space is compact if every open cover drawn from a fixed basis has a finite subcover.) It suffices, then, to show that is compact in the usual topological sense.

The last claim is immediate from the fact that is homeomorphic to with the *(Tychonoff) product topology*, when is given the *discrete topology* . Recall that the product topology on the product of a family of topological spaces () indexed by takes as its basic open sets , where , and for all but finitely elements in . (For a finite collection (), , (, the product topology on has basis {}. In general, the product topology is determined by the following *universal property*: for any space and function , is continuous if and only if is continuous for all , where is the projection map onto the -th coordinate. If we remove the restriction that all-but-finitely-many ‘s are equal to , we obtain the *box product* topology. This coincides with the product topology for finite indexes, but varies drastically for infinite products.) Since with the product topology is homeomorphic to the (if the sentence letters in are for , then defines a homeomorphism ) the latter is compact if and only if the former is. Now with the discrete topology is compact because finite spaces are trivially compact. *Tychonoff’s Theorem*, a ZF-equivalent of the Axiom of Choice, states that the product of compact spaces is compact. Putting the pieces together, it follows that with the product topology is compact. This proves the compactness of .

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 with the discrete topology is Hausdorff (any two of its elements—0 and 1—are contained in disjoint open sets and ). This weaker version of Tychonoff’s Theorem is in fact equivalent to the compactness theorem for propositional logic (and first-order logic), as discussed in Section 7.

The topological proof of ‘s compactness just given assumed that ‘s set of connectives is truth-functionally complete. Without this assumption, there is no guarantee that the set is a basis for the product topology; for example, if a propositional logic cannot define negation, no element of may correspond to the open set consisting of all elements of 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 truth-functional set of connectives is of course immediate from the fact that it is a sublogic of a truth-functionally complete propositional logic with the same sentence letters. The topological way of seeing this is to endow the space with the topology which has as a subbase and denote it by .

(A *subbase* for a topological space () is a collection of open sets such that is a basis for ().Given an arbitrary collection of subsets of a set , there is a unique topology on which has as a subbase. (Willard 1970, p. 39, thm. 5.6).) This topology is *coarser* than the dual space topology on : every open set in is open in the dual space topology. In general, if the topology on some set is coarser than the topology on and () is compact, then so is ). Intuitively, there are fewer means of `escaping’ (via the finite-intersection property) in than in , so if is compact then there are no such routes in . It follows that the topological space is compact, and thus any propositional logic is compact, whether or not its set of connectives is truth-functionally 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 . We present this argument, since is the most common propositional logic.

Suppose that some open cover of the space with the product topology lacks a finite subcover. We reduce this supposition to absurdity by constructing an element of with the following property: the set of all elements of extending an arbitrary finite initial segment of cannot be covered by any finite subset of . If is a finite sequence of 0’s and 1’s, define as the set of elements of extending . Let if does not admit a finite subcover from , and otherwise. More generally, if has been defined, let ^{} if does not admit a finite subcover from , and ^{} otherwise. Since by the assumption to be reduced to absurdity does not admit a finite subcover from , an easy inductive argument shows that does not admit a finite subcover from either, for any . Letting be the element of whose restriction to is (more formally, ), it follows from the fact that is an open cover of that is an element of some basis set , where is an open set in . From and the definition of the product topology, it further follows that for some , , so that does in fact admit a finite subcover from , namely the open set which contains as a subset. This contradicts our supposition and shows that 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 we used the ordering on to extend by 0 if possible and 1 if not. An alternative argument for the compactness of uses the fact that a countable product of bounded (by 1) metric spaces (), is metrisable via the metric

To say that is metrisable in this way is to say that the metric induces the product topology on . The rest of the argument turns on showing that the metric space is compact, by exploiting the space’s metric properties. This argument cannot be generalised to show that ‘s valuation space is compact for any : 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 of theories of -structures , topologised by the subbasic open sets for each formula in . The compactness of is then easily seen to be equivalent to the compactness of with this topology (see Figure 1). In the case of propositional logic, . (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 first-order logic is more complicated than that for propositional logic and not as elementary as exhibiting a simple homeomorphism.

*Figure 1: The connection between compactness of logics and its space of theories.*

## 6. Extensions and Generalisations

The 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 (); infinitary logics ( being the extension of first-order 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 first-order 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 , is not compact whenever . In contrast, logics extending first-order logic with generalised quantifiers tend to be compact, but not if they contain cardinality quantifiers. Roughly speaking, the quantifiers , , , , and 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

in an infinitary logic containing ; this set is finitely-satisfiable 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 first-order logic with the quantifier , interpreted as ‘there are uncountably many’, is *countably-compact*: that is, a countable set of sentences is satisfiable if and only if it is finitely-satisfiable (Keisler 1970).

As an aside, it is worth observing that not all logics with higher-order (second-order or above) quantifiers are incompact. Second-order logic with non-standard (Henkin) semantics is compact (Enderton 2001, chap. 4), as is *existential second-order logic*, whose sentences are of the form , where are second-order functions / relations, and is a first-order sentence in a language with symbols for . (Via embeddings, this logic is equivalent to many first-order logics extended with extra quantifiers and game-theoretic semantics, such as Henkin’s quantifier, Hintikka-Sandu’s independence-friendly 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 second-order logic* with identity, that is, second-order logic with neither functional nor first-order variables but with both second-order and first-order identity (as well as predicate variables and quantifiers). Pure second-order logic may be thought of as the complement of first-order logic relative to second-order logic in the following sense: first-order logic has object but not predicate quantifiers, pure second-order logic has predicate but not object quantifiers, and second-order logic combines the two. In other words, second-order logic merges first-order and pure second-order logic. As Paseau (2010b) shows, pure second-order logic with identity is compact; Denyer (1992) gives an argument that applies to pure second-order logic without identity. The moral is that the incompactness of second-order logic is not owed solely to the presence of second-order quantifiers, but to the combination of both first- and second-order quantifiers. *Lindström’s Theorem* tells us that any regular logical system weakly extending first-order logic satisfying both the downward Löwenheim-Skolem 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:

The ordinary notion of compactness is (-compactness: whenever is any unsatisfiable set of sentences (of any cardinality) there is an unsatisfiable of cardinality , in other words of finite cardinality. A special case arises when and the logic is . 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 , and indeed the latter is the usual definition of a *weakly-compact* cardinal. For the definitions of the tree property and the partition property, and more on weakly-compact cardinals, consult chapters 9 and 17 of Jech (2003).

Another generalisation of the notion of compactness is strong compactness. An uncountable cardinal is *strongly-compact* if for any set , any -complete filter on can be extended to a -complete ultrafilter on . (A filter on a set is -complete if for every with .) One may then show that is strongly-compact 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 strongly-compact cardinals are *large cardinal* properties. (A sentence is a large cardinal property if it satisfies the following: is equiconsistent with , , and the consistency strength of is strictly larger than , 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 implies the arithmetised consistency of , 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 a cardinal is equivalent to (-compactness of , or the (-compactness of for each positive integer (Kanamori 2009, p. 315, thm. 23.4). is the th-order extension of .

Generalising the argument in Section 5 above, it is easily shown that a logic is (-compact precisely when every subbasic open cover of , where is a set of -sentences of cardinality at most , has a subcover of cardinality less than . This is weaker than stating that is (-compact, meaning *every* cover of cardinality at most has a subcover of cardinality less than . For example, if is the extension of first-order logic with the quantifier , then is (-compact, but is not (-compact. See Ebbinghaus (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 set-theoretic 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 first-order logic may be proven in ; but as also indicated, all that is required for its proof, in the case of both propositional and first-order logic, is the Ultrafilter Lemma, which is in fact weaker than Choice relative to . Indeed, the Ultrafilter Lemma turns out to be equivalent to the compactness theorem in . By the capitalised name `Compactness Theorem’ we hereafter understand the compactness theorem for both propositional and first-order logic, since these are of equivalent strength relative to . The relative strength of these and related principles has been well-studied; in this section we report several of these results.

### a. ZF-Equivalents

Tychonoff’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 ideal.
- The Ultrafilter Lemma: every filter on a Boolean algebra can be extended to an ultrafilter.
- Stone’s Representation Theorem: every Boolean algebra is isomorphic to a field of sets.
- Alexander subbase theorem: if is a topological space with a subbase and every open cover has a finite subcover, then is compact (Rubin and Scott 1954).
- For every graph , if every finite subgraph of is 3-colourable then is also 3-colourable (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 ZF-Stronger Than the Compactness Theorem

It is known that the full Tychonoff Theorem is equivalent to the Axiom of Choice in (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 with a countably infinite set of atoms (objects which do not contain any elements and are different from the empty set); is a variant of 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 be a dense linear ordering on without endpoints. Every permutation of has an extension to the entire universe, define recursively by for each set . Let be the group of order-preserving permutations of and for every set define { } and }. We shall say that an object is *symmetric* if there is a finite set of atoms such that . Denote the class of hereditarily symmetric objects by .

If denotes the standard cumulative hierarchy in this theory, then it is easily seen that . We may also show that holds in . As the Axiom of Choice holds in , a set is well-orderable, according to , precisely when there is a symmetric function mapping to some set in . This turns out to be the case precisely when there is a finite set of atoms such that . Since for every finite set of atoms , there is a non-identity order-preserving permutation of fixing , it follows that is not well-orderable according to . However, the Compactness Theorem still holds in .

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 , 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 Compactness Theorem:

- Axiom of Choice: every family of non-empty sets has a choice function.
- Axiom of Multiple Choice: every collection of non-empty sets has a
*multiple choice function*—a function that picks out a non-empty, finite subset from each set in the collection (Chapter 9). - Well-Ordering Principle: every set can be well-ordered (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 non-empty 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 ZF-Weaker Than the Compactness Theorem

The following is a small selection of Choice-like 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.

- Order-Extension Principle, and consequently the statement that
*every set can be linearly-ordered*. - Hahn-Banach theorem:
*If is a sublinear functional on a set and is a linear functional defined on a subspace such that for all , then there exists a linear extension of to all of such that for all*. In fact, the Hahn-Banach theorem is equivalent to the existence of a finitely-additive probability measure on every Boolean algebra (28). It is easily seen that a prime ideal gives rise to a finitely-additive, -valued probability measure on every Boolean algebra, and thus the Hahn-Banach theorem follows from the Boolean Prime Ideal Theorem. - Every infinite set has a non-principal ultrafilter.

## 8. History of the Compactness Theorem

The 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 *first-order predicate logic* (Mal’cev 1936, 1), are those from first-order 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 .

The central idea behind Gödel’s proof is to create an equivalent sequence ( of satisfiable formulas, where each is a conjunction, with one of the conjuncts being , for each .

The models for each (in the language restricted to only those non-logical symbols that occur in ) form a finitely-branching 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 . A finitely-branching tree of height is a countable union of finite sets, which is not necessarily countable in , 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 (, which in turn models the original sequence. We have not included this approach to the compactness theorem in this entry—for details, see Paseau (2010a, 84).

This result also proves the corresponding result for first-order 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 and of arity 1 and for each constant symbol and -ary function symbol , and make the following substitutions:

- For a constant symbol occuring in a sentence , replace each occurrence of with a variable that does not occur in to obtain the formula. If denotes this new sentence, we then replace with .
- For an -ary function symbol in a sentence , replace each occurrence of
with

where is an -ary predicate symbol, , , are terms and 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 for each constant symbol and for each -ary function symbol , 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 first-order logic. In Gödel’s (1932) short paper, he proves the compactness theorem for propositional logic for arbitrary languages. Given a deductively-closed, consistent set of propositional formulas and a well-order on the set of propositional formulas, Gödel defines by transfinite recursion:

- ,
- for all ordinals , if there is a formula such that neither nor belong to , let be the least such and define
Otherwise, define .

- for all limit ordinals , .

For an ordinal where , it follows that the valuation defined as follows satisfies every formula in ,

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 finitely-satisfiable set of sentences with cardinality and well-ordered in this order type. At each non-limit 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 truth-value 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 first-order 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 , 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 -sentence, even over Peano Arithmetic. However, by `equivalent’ Mal’cev appears to mean *equisatisfiable*:

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 is an arbitrary first-order proposition, there exists a first-order proposition in normal form with the property that is satisfiable in a given domain whenever is, and conversely. (255)*

Note that the languages of and are not in general the same. This result readily extends to sets of sentences and is a well-known 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öwenheim-Skolem (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 *first-order 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—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 , Tarski denotes the collection of *arithmetical classes*, which are classes of the form

where is a formula over a fixed first-order language , and the range over -structures. In his terminology, the compactness theorem is the statement that if is a collection of -formulas and (which means is unsatisfiable) then there exists a finite set such that (which means is not finitely-satisfiable). 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 and first-order 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.
*Model-Theoretic Logics.*Perspectives in Mathematical Logic. New York: Springer.- A book on the model-theory of many logics that extend first-order 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 Logik-Kalkü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öwenheim-Skolem-Gödel.”
*Indagationes Mathematicae (Proceedings)*54:436–44. https://doi.org/10.1016/S1385-7258(51)50062-8.- Beth presents a proof of the Löwenheim-Skolem-Gödel theorem: a set of first-order 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: North-Holland.- 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 3-colourable if every finite subgraph is 3-colourable”.

- 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
- Dawson, John W., Jr. 1993. “The Compactness of First-Order 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 Second-Order Logic.”
*Notre Dame Journal of Formal Logic*33 (2): 220–24. https://doi.org/10.1305/ndjfl/1093636099.- Denyer proves that pure second-order 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 first-order logic and discusses various model-theoretic 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, first-order, and second-order 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/fm-51-3-195-228.- 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, order-theoretic, and topological aspects of Boolean algebras.

- Gödel, Kurt. 1929. “Über die Vollständigkeit des Logikkalküls.” Translated by Stefan Bauer-Mengelberg 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 Bauer-Mengelberg. 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 graduate-level textbook on the subject of non-standard analysis, including the foundational and model-theoretic 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 first-order 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 First-Order 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 first-order 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, Fiziko-maté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 non-provable 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: North-Holland.- A textbook on the Axiom of Choice and other Choice-like 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 graduate-level 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 graduate-level 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 Bar-Hillel, 112–26. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland.- A survey on the use of ultraproducts in mathematics, including its relationship with the compactness theorem for first-order 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/S0003-4843(70)80005-5.- An extensive paper on the model-theoretic 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. https: //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.1755-2567.1969.tb00356.x.- Lindström proves his famous theorem characterising first-order logic via the (countable) compactness and Löwenheim-Skolem 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: North-Holland.- 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 model-theoretic 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 first-order logic.

- Mal’cev, Anatoliĭ Ivanovič. 1971.
*The Metamathematics of Algebraic Systems: Collected papers: 1936–1967.*Edited and translated by Benjamin Franklin Wells III. Amsterdam: North-Holland.- Translations of most of Mal’cev’s works on algebraic applications of mathematical logic.

- Mann, Allen L., Gabriel Sandu, and Merlijn Sevenster. 2011.
*Independence-Friendly Logic: A Game-Theoretic Approach.*London Mathematical Society Lecture Note Series 386. Cambridge: Cambridge University Press.- This monograph provides an introduction to independence-friendly logic, a logic with game-theoretic semantics.

- Mannila, Heikki. 1983. “A Topological Characterization of (
*λ, µ*)-Compactness.”^{∗}*Annals of Pure and Applied Logic*25 (3): 301–5. https://doi.org/10.1016/0168-0072(83)90022-2.- Mannila gives a model-theoretic characterisation of the (
*λ, µ*)-compactness of the model space of a logic.

- Mannila gives a model-theoretic characterisation of the (
- 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: Springer-Verlag.- 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 Second-Order Logic with Second-Order Identity.”
*Notre Dame Journal of Formal Logic*51 (3): 351–60. https://doi. org/10.1215/00294527-2010-021.- Pure second-order logic is second-order logic without first-order or functional variables. In the context of second-order logic, it is therefore, in a sense, the complement of first-order 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 Hahn-Banach 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: Springer-Verlag.- Pincus shows the consistency (relative to ZF) of the Hahn-Banach 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 graduate-level 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 many-valued 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 Order-Extension 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 first-order 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: North-Holland.- A monograph largely based on Robinson’s doctoral dissertation.

- Robinson, Abraham. 1966.
*Non-Standard Analysis.*Studies in Logic and the Foundations of Mathematics 42. Amsterdam: North-Holland.- A foundational text in non-standard 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/ S0002-9904-1954-09827-0.- 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 Second-Order Logic.*Oxford Logic Guides 17. Oxford: Clarendon Press.- A detailed and extensive account of second-order 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. “Logico-Combinatorial 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 Bauer-Mengelberg. 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 first-order logic as well as presenting a fully-correct proof of the downward Löwenheim-Skolem theorem for countable sets of sentences, which uses his Axiom of Choice.

- Skolem, Thoralf. 1922. “Some Remarks on Axiomatized Set Theory.” Translated by Stefan Bauer-Mengelberg, 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 Set-Theoretic Topology,*edited by Kenneth Kunen and Jerry E. Vaughan, 603–32. Amsterdam: North-Holland.- This article presents a survey of results on (
*κ, λ*)-compactness of topological spaces.

- This article presents a survey of results on (
- 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/fm-16-1-386-389.- 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 first-order 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 game-theoretic semantics.

- Willard, Stephen. 1970.
*General**Topology.*Reading, MA: Addison-Wesley.- 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 Information

A. C. Paseau

Email: alexander.paseau@philosophy.ox.ac.uk

University of Oxford

United Kingdom

and

Robert Leek

Email: r.leek@bham.ac.uk

University of Birmingham

United Kingdom