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 … Continue reading Compactness Theorem →.

In this study, the author compares several proofs of the compactness theorem for propositional logic with countably many atomic sentences. He thereby takes some steps towards a systematic philosophical study of the compactness theorem. He also presents some data and morals for the theory of mathematical explanation. [The author is not responsible for the horrific mathematical typo in the second sentence.].

It is proved that a system of linear equations over an arbitrary field has a solution if every finite subsystem has a solution provided that the set of variables can be well ordered.

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

We prove a theorem (1.7) about partial orders which can be viewed as a version of the Barwise compactness theorem which does not mention logic. The Barwise compactness theorem is easily equivalent to 1.7 + "Every Henkin set has a model". We then make the observation that 1.7 gives us the definability of forcing for quantifier-free sentences in the forcing language and use this to give a direct proof of the truth and definability lemmas of (...) forcing. (shrink)

Starting with a model in which κ is the least inaccessible limit of cardinals δ which are δ+ strongly compact, we force and construct a model in which κ remains inaccessible and in which, for every cardinal γ < κ, □γ+ω fails but □γ+ω, ω holds. This generalizes a result of Ben-David and Magidor and provides an analogue in the context of strong compactness to a result of the author and Cummings in the context of supercompactness.

In this paper, we discuss some questions about compactness in MV-topological spaces. More precisely, we first present a Tychonoff theorem for such a class of fuzzy topological spaces and some consequence of this result, among which, for example, the existence of products in the category of Stone MV-spaces and, consequently, of coproducts in the one of limit cut complete MV-algebras. Then we show that our Tychonoff theorem is equivalent, in ZF, to the Axiom of Choice, classical Tychonoff (...) theorem, and Lowen’s analogous result for lattice-valued fuzzy topology. Last, we show an extension of the Stone–Čech compactification functor to the category of MV-topological spaces, and we discuss its relationship with previous works on compactification for fuzzy topological spaces. (shrink)

We prove that the modal logic of a crowded locally compact generalized ordered space is $\textsf {S4}$. This provides a version of the McKinsey–Tarski theorem for generalized ordered spaces. We then utilize this theorem to axiomatize the modal logic of an arbitrary locally compact generalized ordered space.

A weak constructive sequential compactness property of metric spaces is introduced. It is proved that for complete, totally bounded metric spaces this property is equivalent to Brouwer's fan theorem for detachable bars. Our results form a part of constructive reverse mathematics.

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 … Continue reading Compactness →.

THEOREM 1. (⋄ ℵ 1 ) If B is an infinite Boolean algebra (BA), then there is B 1 such that $|\operatorname{Aut} (B_1)| \leq B_1| = \aleph_1$ and $\langle B_1, \operatorname{Aut} (B_1)\rangle \equiv \langle B, \operatorname{Aut}(B)\rangle$ . THEOREM 2. (⋄ ℵ 1 ) There is a countably compact logic stronger than first-order logic even on finite models. This partially answers a question of H. Friedman. These theorems appear in §§ 1 and 2. THEOREM 3. (a) (⋄ ℵ (...) 1 ) If B is an atomic ℵ 1 -saturated infinite BA, ψ ε L ω 1ω and $\langle B, \operatorname{Aut} (B)\rangle \models\psi$ then there is B 1 such that $|\operatorname{Aut}(B_1)| \leq |B_1| = \aleph_1$ and $\langle B_1, \operatorname{Aut}(B_1)\rangle\models\psi$ . In particular if B is 1-homogeneous so is B 1 . (b) (a) holds for B = P(ω) even if we assume only CH. (shrink)

This paper introduces the notion of syntactic feature to provide a unified treatment of earlier model theoretic proofs of both the compactness and interpolation theorems for a variety of two valued logics including sentential logic, first order logic, and a family of modal sentential logic includingM,B,S 4 andS 5. The compactness papers focused on providing a proof of the consequence formulation which exhibited the appropriate finite subset. A unified presentation of these proofs is given by isolating their essential (...) feature and presenting it as an abstract principle about syntactic features. The interpolation papers focused on exhibiting the interpolant. A unified presentation of these proofs is given by isolating their essential feature and presenting it as a second abstract principle about syntactic features. This second principle reduces the problem of exhibiting the interpolant to that of establishing the existence of a family of syntactic features satisfying certain conditions. The existence of such features is established for a variety of logics (including those mentioned above) by purely combinatorial arguments. (shrink)

Though regarded today as one of the most important results in logic, the compactness theorem was largely ignored until nearly two decades after its discovery. This paper describes the vicissitudes of its evolution and transformation during the period 1930-1970, with special attention to the roles of Kurt Gödel, A. I. Maltsev, Leon Henkin, Abraham Robinson, and Alfred Tarski.

Let {: i ∈I } be a family of compact spaces and let X be their Tychonoff product. [MATHEMATICAL SCRIPT CAPITAL C] denotes the family of all basic non-trivial closed subsets of X and [MATHEMATICAL SCRIPT CAPITAL C]R denotes the family of all closed subsets H = V × Πmath imageXi of X, where V is a non-trivial closed subset of Πmath imageXi and QH is a finite non-empty subset of I. We show: Every filterbase ℋ ⊂ [MATHEMATICAL SCRIPT CAPITAL (...) C]R extends to a [MATHEMATICAL SCRIPT CAPITAL C]R-ultrafilter ℱ if and only if every family H ⊂ [MATHEMATICAL SCRIPT CAPITAL C] with the finite intersection property extends to a maximal [MATHEMATICAL SCRIPT CAPITAL C] family F with the fip. The proposition “if every filterbase ℋ ⊂ [MATHEMATICAL SCRIPT CAPITAL C]R extends to a [MATHEMATICAL SCRIPT CAPITAL C]R-ultrafilter ℱ, then X is compact” is not provable in ZF. The statement “for every family {: i ∈ I } of compact spaces, every filterbase ℋ ⊂ [MATHEMATICAL SCRIPT CAPITAL C]R, Y = Πi ∈IYi, extends to a [MATHEMATICAL SCRIPT CAPITAL C]R-ultrafilter ℱ” is equivalent to Tychonoff's compactness theorem. The statement “for every family {: i ∈ ω } of compact spaces, every countable filterbase ℋ ⊂ [MATHEMATICAL SCRIPT CAPITAL C]R, X = Πi ∈ωXi, extends to a [MATHEMATICAL SCRIPT CAPITAL C]R-ultrafilter ℱ” is equivalent to Tychonoff's compactness theorem restricted to countable families. The countable Axiom of Choice is equivalent to the proposition “for every family {: i ∈ ω } of compact topological spaces, every countable family ℋ ⊂ [MATHEMATICAL SCRIPT CAPITAL C] with the fip extends to a maximal [MATHEMATICAL SCRIPT CAPITAL C] family ℱ with the fip”. (shrink)

A structure which generalizes formulas by including substitution terms is used to represent proofs in classical logic. These structures, called expansion trees, can be most easily understood as describing a tautologous substitution instance of a theorem. They also provide a computationally useful representation of classical proofs as first-class values. As values they are compact and can easily be manipulated and transformed. For example, we present an explicit transformations between expansion tree proofs and cut-free sequential proofs. A theorem prover (...) which represents proofs using expansion trees can use this transformation to present its proofs in more human-readable form. Also a very simple computation on expansion trees can transform them into Craig-style linear reasoning and into interpolants when they exist. We have chosen a sublogic of the Simple Theory of Types for our classical logic because it elegantly represents substitutions at all finite types through the use of the typed -calculus. Since all the proof-theoretic results we shall study depend heavily on properties of substitutions, using this logic has allowed us to strengthen and extend prior results: we are able to prove a strengthen form of the firstorder interpolation theorem as well as provide a correct description of Skolem functions and the Herbrand Universe. The latter are not straightforward generalization of their first-order definitions. (shrink)

This is a continuation of [2]. We study the Tychonoff Compactness Theorem for various definitions of compactness and for various types of spaces . We also study well ordered Tychonoff products and the effect that the multiple choice axiom has on such products.

How are the various classically equivalent definitions of compactness for metric spaces constructively interrelated? This question is addressed with Bishop-style constructive mathematics as the basic system – that is, the underlying logic is the intuitionistic one enriched with the principle of dependent choices. Besides surveying today's knowledge, the consequences and equivalents of several sequential notions of compactness are investigated. For instance, we establish the perhaps unexpected constructive implication that every sequentially compact separable metric space is totally bounded. As (...) a by-product, the fan theorem for detachable bars of the complete binary fan proves to be necessary for the unit interval possessing the Heine-Borel property for coverings by countably many possibly empty open balls. (shrink)

The concept of compactness is a necessary condition of any system that is going to call itself a finitary method of proof. However, it can also apply to predicates of sets of formulas in general and in that manner it can be used in relation to level functions, a flavor of measure functions. In what follows we will tie these concepts of measure and compactness together and expand some concepts which appear in d'Entremont's master's thesis, "Inference and Level." (...) We will also provide some applications of the concept of level to the "preservationist" program of paraconsistent logic. We apply the finite level compactness theorem in this paper to get a Lindenbaum flavor extension lemma and a maximal "forcibility" theorem. Each of these is based on an abstract deductive system X which satisfies minimal conditions of inference and has generalizations of 'and' and 'not' as logical words. (shrink)

Linear continuous logic is the fragment of continuous logic obtained by restricting connectives to addition and scalar multiplications. Most results in the full continuous logic have a counterpart in this fragment. In particular a linear form of the compactness theorem holds. We prove this variant and use it to deduce some basic preservation theorems.

We generalize a theorem of Mundici relating compactness of a regular logic L to a strong form of normality of the associated spaces of models. Moreover, it is shown that compactness is in fact equivalent to ordinary normality of the model spaces when L has uniform reduction for infinite disjoint sums of structures. Some applications follow. For example, a countably generated logic is countably compact if and only if every clopen class in the model spaces is elementary. (...) The model spaces of L are not normal for vocabularies of uncountable power ωα. It also follows that first-order logic is the only finite-dependence logic having normal model spaces and satisfying at the same time the downward Löwenheim-Skolem theorem and uniform reduction for pairs. (shrink)

We prove a compactness theorem for pseudopower operations of the form \}\) where \\le {{\,\mathrm{cf}\,}}\). Our main tool is a result that has Shelah’s cov versus pp Theorem as a consequence. We also show that the failure of compactness in other situations has significant consequences for pcf theory, in particular, implying the existence of a progressive set A of regular cardinals for which \\) has an inaccessible accumulation point.

We study the Tychonoff Compactness Theorem for several different definitions of a compact space.

If a locale is presented by a “flat site”, it is shown how its frame can be presented by generators and relations as a dcpo. A necessary and sufficient condition is derived for compactness of the locale . Although its derivation uses impredicative constructions, it is also shown predicatively using the inductive generation of formal topologies. A predicative proof of the binary Tychonoff theorem is given, including a characterization of the finite covers of the product by basic opens. (...) The discussion is then related to the double powerlocale. (shrink)

We investigate the interaction between compactness principles and guessing principles in the Radin forcing extensions. In particular, we show that in any Radin forcing extension with respect to a measure sequence on [Formula: see text], if [Formula: see text] is weakly compact, then [Formula: see text] holds. This provides contrast with a well-known theorem of Woodin, who showed that in a certain Radin extension over a suitably prepared ground model relative to the existence of large cardinals, the diamond (...) principle fails at a strongly inaccessible Mahlo cardinal. Refining the analysis of the Radin extensions, we consistently demonstrate a scenario where a compactness principle, stronger than the diagonal stationary reflection principle, holds yet the diamond principle fails at a strongly inaccessible cardinal, improving a result from [O. B. -Neria, Diamonds, compactness, and measure sequences, J. Math. Log. 19(1) (2019) 1950002]. (shrink)

Jonathan Lear has suggested that Aristotle attempts to demonstrate a proof-theoretic analogue of a compactness theorem in Posterior analyticsI, chs. 19?22. Aristotle argues in these chapters that there cannot be in finite series of predications of terms. Lear's analysis of Aristotle's arguments are shown to be based on confusions about the nature of infinite orderings. Three distinct confusions are identified. In final remarks, it is suggested that a compactness claim is irrelevant to the issues which motivate Aristotle's (...) arguments. (shrink)

This paper explores several topics related to Woodin’s HOD conjecture. We improve the large cardinal hypothesis of Woodin’s HOD dichotomy theorem from an extendible cardinal to a strongly compact cardinal. We show that assuming there is a strongly compact cardinal and the HOD hypothesis holds, there is no elementary embedding from HOD to HOD, settling a question of Woodin. We show that the HOD hypothesis is equivalent to a uniqueness property of elementary embeddings of levels of the cumulative hierarchy. (...) We prove that the HOD hypothesis holds if and only if every regular cardinal above the first strongly compact cardinal carries an ordinal definable [Formula: see text]-Jónsson algebra. We show that if the HOD hypothesis holds and HOD satisfies the Ultrapower Axiom, then every supercompact cardinal is supercompact in HOD. (shrink)

A characterization of groups definable in o-minimal structures having maximal definable definably compact subgroups is given. This follows from a definable decomposition in analogy with Lie groups, where the role of maximal tori is played by maximal 0-subgroups. Along the way we give structural theorems for solvable groups, linear groups, and extensions of definably compact by torsion-free definable groups.

Combining techniques of the first author and Shelah with ideas of Magidor, we show how to get a model in which, for fixed but arbitrary finite n, the first n strongly compact cardinals κ 1 ,..., κ n are so that κ i for i = 1,..., n is both the i th measurable cardinal and κ + i supercompact. This generalizes an unpublished theorem of Magidor and answers a question of Apter and Shelah.

We prove a structure theorem for compact inverse categories. The Ehresmann-Schein-Nambooripad theorem gives a structure theorem for inverse monoids: they are inductive groupoids. A particularly nice case due to Clifford is that commutative inverse monoids become semilattices of abelian groups. It has also been categorified by Hoehnke and DeWolf-Pronk to a structure theorem for inverse categories as locally complete inductive groupoids. We show that in the case of compact inverse categories, this takes the particularly nice form (...) of a semilattice of compact groupoids. Moreover, one-object compact inverse categories are exactly commutative inverse monoids. Compact groupoids, in turn, are determined in particularly simple terms of 3-cocycles by Baez-Lauda. (shrink)

We say that a Hausdorff locale is compactly generated if it is the colimit of the diagram of its compact sublocales connected by inclusions. We show that this is the case if and only if the natural map of its frame of opens into the second Lawson dual is an isomorphism. More generally, for any Hausdorff locale, the second dual of the frame of opens gives the frame of opens of the colimit. In order to arrive at this conclusion, we (...) generalize the Hofmann–Mislove–Johnstone theorem and some results regarding the patch construction for stably locally compact locales. (shrink)

In this paper, we deal with compact operators on a Hilbert space, within the framework of Bishop's constructive mathematics. We characterize the compactness of a bounded linear mapping of a Hilbert space into C n , and prove the theorems: Let A and B be compact operators on a Hilbert space H , let C be an operator on H and let α ϵ C . Then α A is compact, A + B is compact, A ∗ is compact, (...) CA is compact and if C ∗ exists, then AC is compact; An operator on a Hilbert space has an adjoint if and only if it is weakly compact. (shrink)

We study the relationship between the countable axiom of choice and the Tychonoff product theorem for countable families of topological spaces.