Set Theory

We give an exposition of the compactness of L(QcfC), for any set C of regular cardinals.

Given a regular cardinal $\kappa $ such that $\kappa ^{<\kappa }=\kappa $, we study a class of toposes with enough points, the $\kappa $ -separable toposes. These are equivalent to sheaf toposes over a site with $\kappa $ -small limits that has at most $\kappa $ many objects and morphisms, the topology being generated by at most $\kappa $ many covering families, and that satisfy a further exactness property T. We prove that these toposes have enough $\kappa $ -points, that (...) is, points whose inverse image preserve all $\kappa $ -small limits. This generalizes the separable toposes of Makkai and Reyes, that are a particular case when $\kappa =\omega $, when property T is trivially satisfied. This result is essentially a completeness theorem for a certain infinitary logic that we call $\kappa $ -geometric, where conjunctions of less than $\kappa $ formulas and existential quantification on less than $\kappa $ many variables is allowed. We prove that $\kappa $ -geometric theories have a $\kappa $ -classifying topos having property T, the universal property being that models of the theory in a Grothendieck topos with property T correspond to $\kappa $ -geometric morphisms into that topos. Moreover, we prove that $\kappa $ -separable toposes occur as the $\kappa $ -classifying toposes of $\kappa $ -geometric theories of at most $\kappa $ many axioms in canonical form, and that every such $\kappa $ -classifying topos is $\kappa $ -separable. Finally, we consider the case when $\kappa $ is weakly compact and study the $\kappa $ -classifying topos of a $\kappa $ -coherent theory, that is, a theory where only disjunction of less than $\kappa $ formulas are allowed, obtaining a version of Deligne’s theorem for $\kappa $ -coherent toposes from which we can derive, among other things, Karp’s completeness theorem for infinitary classical logic. (shrink)

This paper reconstructs Steel’s multiverse project in his ‘Gödel’s program’ (Steel [2014]), first by comparing it to those of Hamkins [2012] and Woodin [2011], then by detailed analysis what’s presented in Steel’s brief text. In particular, we reconstruct his notion of a ‘natural’ theory, describe his multiverse axioms and his translation function, and assess the resulting status of the Continuum Hypothesis. In the end, we reconceptualize the defect that Steel thinks CH might suffer from and isolate what it would take (...) to remove it while working within his framework. As our goal is to present as coherent and compelling a philosophical and mathematical story as we can, we allow ourselves to augment Steel’s story in places (e.g., in the treatment of Amalgamation) and to depart from it in others (e.g., the removal of ‘meaning’ from the account). The relevant mathematics is laid out in the appendices. (shrink)

We study large cardinal properties associated with Ramseyness in which homogeneous sets are demanded to satisfy various transfinite degrees of indescribability. Sharpe and Welch [25], and independently Bagaria [1], extended the notion of $\Pi ^1_n$ -indescribability where $n<\omega $ to that of $\Pi ^1_\xi $ -indescribability where $\xi \geq \omega $. By iterating Feng’s Ramsey operator [12] on the various $\Pi ^1_\xi $ -indescribability ideals, we obtain new large cardinal hierarchies and corresponding nonlinear increasing hierarchies of normal ideals. We provide (...) a complete account of the containment relationships between the resulting ideals and show that the corresponding large cardinal properties yield a strict linear refinement of Feng’s original Ramsey hierarchy. We isolate Ramsey properties which provide strictly increasing hierarchies between Feng’s $\Pi _\alpha $ -Ramsey and $\Pi _{\alpha +1}$ -Ramsey cardinals for all odd $\alpha <\omega $ and for all $\omega \leq \alpha <\kappa $. We also show that, given any ordinals $\beta _0,\beta _1<\kappa $ the increasing chains of ideals obtained by iterating the Ramsey operator on the $\Pi ^1_{\beta _0}$ -indescribability ideal and the $\Pi ^1_{\beta _1}$ -indescribability ideal respectively, are eventually equal; moreover, we identify the least degree of Ramseyness at which this equality occurs. As an application of our results we show that one can characterize our new large cardinal notions and the corresponding ideals in terms of generic elementary embeddings; as a special case this yields generic embedding characterizations of $\Pi ^1_\xi $ -indescribability and Ramseyness. (shrink)

In the present paper we use the theory of exact completions to study categorical properties of small setoids in Martin-Löf type theory and, more generally, of models of the Constructive Elementary Theory of the Category of Sets, in terms of properties of their subcategories of choice objects. Because of these intended applications, we deal with categories that lack equalisers and just have weak ones, but whose objects can be regarded as collections of global elements. In this context, we study the (...) internal logic of the categories involved, and employ this analysis to give a sufficient condition for the local cartesian closure of an exact completion. Finally, we apply this result to show when an exact completion produces a model of CETCS. (shrink)

Motivated by a characterization of weakly compact cardinals due to Todorcevic, we introduce a new cardinal characteristic, the C-sequence number, which can be seen as a measure of the compactness of a regular uncountable cardinal. We prove a number of ZFC and independence results about the C-sequence number and its relationship with large cardinals, stationary reflection, and square principles. We then introduce and study the more general C-sequence spectrum and uncover some tight connections between the C-sequence spectrum and the strong (...) coloring principle U(. . .), introduced in Part I of this series. (shrink)

We provide comprehensive, level-by-level characterizations of large cardinals, in the range from weakly compact to strongly compact, by closure properties of powerful images of accessible functors. In the process, we show that these properties are also equivalent to various forms of tameness for abstract elementary classes. This systematizes and extends results of [W. Boney and S. Unger, Large cardinal axioms from tameness in AECs, Proc. Amer. Math. Soc.145(10) (2017) 4517–4532; A. Brooke-Taylor and J. Rosický, Accessible images revisited, Proc. AMS145(3) (2016) (...) 1317–1327; M. Lieberman, A category-theoretic characterization of almost measurable cardinals (Submitted, 2018); M. Lieberman and J. Rosický, Classification theory for accessible categories. J. Symbolic Logic81(1) (2016) 1647–1648]. (shrink)

We show that if [Formula: see text] then any nontrivial [Formula: see text]-closed forcing notion of size [Formula: see text] is forcing equivalent to [Formula: see text] the Cohen forcing for adding a new Cohen subset of [Formula: see text] We also produce, relative to the existence of suitable large cardinals, a model of [Formula: see text] in which [Formula: see text] and all [Formula: see text]-closed forcing notion of size [Formula: see text] collapse [Formula: see text] and hence are (...) forcing equivalent to [Formula: see text] These results answer a question of Scott Williams from 1978. We also extend a result of Todorcevic and Foreman–Magidor–Shelah by showing that it is consistent that every partial order which adds a new subset of [Formula: see text] collapses [Formula: see text] or [Formula: see text]. (shrink)

We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on (...) the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture. (shrink)

In this paper, we consider a notion of nonmeasurablity with respect to Marczewski and Marczewski-like tree ideals $s_0$, $m_0$, $l_0$, $cl_0$, $h_0,$ and $ch_0$. We show that there exists a subset of the Baire space $\omega ^\omega,$ which is s-, l-, and m-nonmeasurable that forms a dominating m.e.d. family. We investigate a notion of ${\mathbb {T}}$ -Bernstein sets—sets which intersect but do not contain any body of any tree from a given family of trees ${\mathbb {T}}$. We also obtain a (...) result on ${\mathcal {I}}$ -Luzin sets, namely, we prove that if ${\mathfrak {c}}$ is a regular cardinal, then the algebraic sum of a generalized Luzin set and a generalized Sierpiński set belongs to $s_0, m_0$, $l_0,$ and $cl_0$. (shrink)

Mauldin [15] proved that there is an analytic set, which cannot be represented by $B\cup X$ for some Borel set B and a subset X of a $\boldsymbol{\Sigma }^0_2$-null set, answering a question by Johnson [10]. We reprove Mauldin’s answer by a recursion-theoretical method. We also give a characterization of the Borel generated $\sigma $-ideals having approximation property under the assumption that every real is constructible, answering Mauldin’s question raised in [15].

We show that it is consistent relative to a huge cardinal that for all infinite cardinals [Formula: see text], [Formula: see text] holds and there is a stationary [Formula: see text] such that [Formula: see text] is [Formula: see text]-saturated.

We propose a new method for constructing Turing ideals satisfying principles of reverse mathematics below the Chain–Antichain (CAC) Principle. Using this method, we are able to prove several new separations in the presence of Weak König’s Lemma (WKL), including showing that CAC+WKL does not imply the thin set theorem for pairs, and that the principle “the product of well-quasi-orders is a well-quasi-order” is strictly between CAC and the Ascending/Descending Sequences principle, even in the presence of WKL.

This paper defines provably non-trivial theories that characterize Frege’s notion of a set, taking into account that the notion is inconsistent. By choosing an adaptive underlying logic, consistent sets behave classically notwithstanding the presence of inconsistent sets. Some of the theories have a full-blown presumably consistent set theory T as a subtheory, provided T is indeed consistent. An unexpected feature is the presence of classical negation within the language.

A central area of current philosophical debate in the foundations of mathematics concerns whether or not there is a single, maximal, universe of set theory. Universists maintain that there is such a universe, while Multiversists argue that there are many universes, no one of which is ontologically privileged. Often forcing constructions that add subsets to models are cited as evidence in favour of the latter. This paper informs this debate by analysing ways the Universist might interpret this discourse that seems (...) to necessitate the addition of subsets to V. We argue that despite the prima facie incoherence of such talk for the Universist, she nonetheless has reason to try and provide interpretation of this discourse. We analyse extant interpretations of such talk, and analyse various tradeoffs in naturality that might be made. We conclude that the Universist has promising options for interpreting different forcing constructions. (shrink)

We introduce the property “F-linked” of subsets of posets for a given free filter F on the natural numbers, and define the properties “μ-F-linked” and “θ-F-Knaster” for posets in a natural way. We show that θ-F-Knaster posets preserve strong types of unbounded families and of maximal almost disjoint families. Concerning iterations of such posets, we develop a general technique to construct θ-Fr-Knaster posets (where Fr is the Frechet ideal) via matrix iterations of <θ-ultrafilter-linked posets (restricted to some level of the (...) matrix). This is applied to prove consistency results about Cichoń's diagram (without using large cardinals) and to prove the consistency of the fact that, for each Yorioka ideal, the four cardinal invariants associated with it are pairwise different. At the end, we show that three strongly compact cardinals are enough to force that Cichoń's diagram can be separated into 10 different values. (shrink)

We show that Dependent Choice is a sufficient choice principle for developing the basic theory of proper forcing, and for deriving generic absoluteness for the Chang model in the presence of large cardinals, even with respect to $\mathsf {DC}$ -preserving symmetric submodels of forcing extensions. Hence, $\mathsf {ZF}+\mathsf {DC}$ not only provides the right framework for developing classical analysis, but is also the right base theory over which to safeguard truth in analysis from the independence phenomenon in the presence of (...) large cardinals. We also investigate some basic consequences of the Proper Forcing Axiom in $\mathsf {ZF}$, and formulate a natural question about the generic absoluteness of the Proper Forcing Axiom in $\mathsf {ZF}+\mathsf {DC}$ and $\mathsf {ZFC}$. Our results confirm $\mathsf {ZF} + \mathsf {DC}$ as a natural foundation for a significant portion of “classical mathematics” and provide support to the idea of this theory being also a natural foundation for a large part of set theory. (shrink)

Some non-normal κ-complete ultrafilters over a measurable κ with special properties are constructed. Questions by A. Kanamori [4] about infinite Rudin-Frolik sequences, discreteness and products are answered.

We examine topological pairs (\Delta, \Sigma) which have computable type: if X is a computable topological space and f:\Delta \rightarrow X a topological embedding such that f(\Delta) and f(\Sigma) are semicomputable sets in X, then f(\Delta) is a computable set in X. It it known that (D, W) has computable type, where D is the Warsaw disc and W is the Warsaw circle. In this paper we identify a class of topological pairs which are similar to (D, W) and have (...) computable type: we prove that (\Delta, \Sigma) has computable type if \Delta can somehow be approximated by a 2-cell whose boundary circle approximates \Sigma. Moreover, we examine higher-dimensional analogues of such pairs. (shrink)

Suppose that T^∗ is an ω_1-Aronszajn tree with no stationary antichain. We introduce a forcing axiom PFA(T^∗) for proper forcings which preserve these properties of T^∗. We prove that PFA(T^∗) implies many of the strong consequences of PFA, such as the failure of very weak club guessing, that all of the cardinal characteristics of the continuum are greater than ω_1, and the P-ideal dichotomy. On the other hand, PFA(T^∗) implies some of the consequences of diamond principles, such as the existence (...) of Knaster forcings which are not stationarily Knaster. (shrink)

We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of L-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of (N, +, \times) .

We study Polish spaces for which a set of possible distances $A \subseteq R^+$ is fixed in advance. We determine, depending on the properties of A, the complexity of the collection of all Polish metric spaces with distances in A, obtaining also example of sets in some Wadge classes where not many natural examples are known. Moreover we describe the properties that A must have in order that all Polish spaces with distances in that set belong to a given class, (...) such as zero-dimensional, locally compact, etc. These results lead us to give a fairly complete description of the complexity, with respect to Borel reducibility and again depending on the properties of A, of the relations of isometry and isometric embeddability between these Polish spaces. (shrink)

Set-theoretic pluralism is an increasingly influential position in the philosophy of set theory (Balaguer [1998], Linksy and Zalta [1995], Hamkins [2012]). There is considerable room for debate about how best to formulate set-theoretic pluralism, and even about whether the view is coherent. But there is widespread agreement as to what there is to recommend the view (given that it can be formulated coherently). Unlike set-theoretic universalism, set-theoretic pluralism affords an answer to Benacerraf’s epistemological challenge. The purpose of this paper is (...) to determine what Benacerraf’s challenge could be such that this view is warranted. I argue that it could not be any of the challenges with which it has been traditionally identified by its advocates, like of Benacerraf and Field. Not only are none of the challenges easier for the pluralist to meet. None satisfies a key constraint that has been placed on Benacerraf’s challenge. However, I argue that Benacerraf’s challenge could be the challenge to show that our set-theoretic beliefs are safe – i.e., to show that we could not have easily had false ones. Whether the pluralist is, in fact, better positioned to show that our set-theoretic beliefs are safe turns on a broadly empirical conjecture which is outstanding. If this conjecture proves to be false, then it is unclear what the epistemological argument for set-theoretic pluralism is supposed to be. (shrink)

Motivated by the goal of constructing a model in which there are no κ-Aronszajn trees for any regular $k>\aleph_1$, we produce a model with many singular cardinals where both the singular cardinals hypothesis and weak square fail.

The publisher would like to confirm that the author owns the copyright of the article.

Let κ be a cardinal of cofinality \omega_1 witnessed by a club of cardinals (κ_\alpha | \alpha < \omega_1) . We study Silver's type effects of collapsing of κ^+_\alphas 's on κ^+ . A model in which κ^+_\alphas 's (and also κ^+) are collapsed on a stationary co-stationary set is constructed.

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC^1 (corresponding to the “NC^1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC^1 . This in turn implies that every proof in Gentzen's sequent calculus LK of a (...) monotone sequent can be simulated in the monotone version of LK (MLK) with only polynomial blowup in proof size, strengthening the quasipolynomial simulation result of Atserias, Galesi, and Pudlák [9]. (shrink)

The main result of this paper is an improvement of the upper bound on the cardinal invariant $cov^*(L_0)$ that was discovered in [11]. Here $L_0$ is the ideal of subsets of the set of natural numbers that have asymptotic density zero. This improved upper bound is also dualized to get a better lower bound on the cardinal $non^*(L_0)$. En route some variations on the splitting number are introduced and several relationships between these variants are proved.

We introduce and consider the inner-model reflection principle, which asserts that whenever a statement \varphi(a) in the first-order language of set theory is true in the set-theoretic universe V, then it is also true in a proper inner model W \subset A. A stronger principle, the ground-model reflection principle, asserts that any such \varphi(a) true in V is also true in some non-trivial ground model of the universe with respect to set forcing. These principles each express a form of width (...) reflection in contrast to the usual height reflection of the Lévy–Montague reflection theorem. They are each equiconsistent with ZFC and indeed \Pi_2-conservative over ZFC, being forceable by class forcing while preserving any desired rank-initial segment of the universe. Furthermore, the inner-model reflection principle is a consequence of the existence of sufficient large cardinals, and lightface formulations of the reflection principles follow from the maximality principle MP and from the inner-model hypothesis IMH. We also consider some questions concerning the expressibility of the principles. (shrink)

We introduce the large-cardinal notions of ξ-greatly-Mahlo and ξ-reflection cardinals and prove (1) in the constructible universe, L, the first ξ-reflection cardinal, for ξ a successor ordinal, is strictly between the first ξ-greatly-Mahlo and the first Π1ξ-indescribable cardinals, (2) assuming the existence of a ξ-reflection cardinal κ in L, ξ a successor ordinal, there exists a forcing notion in L that preserves cardinals and forces that κ is (ξ+1)-stationary, which implies that the consistency strength of the existence of a (ξ+1)-stationary (...) cardinal is strictly below a Π1ξ-indescribable cardinal. These results generalize to all successor ordinals ξ the original same result of Mekler–Shelah [A. Mekler and S. Shelah, The consistency strength of every stationary set reflects, Israel J. Math.67(3) (1989) 353–365] about a 2-stationary cardinal, i.e. a cardinal that reflects all its stationary sets. (shrink)

Answering some of the main questions from [L. Motto Ros, The descriptive set-theoretical complexity of the embeddability relation on models of large size, Ann. Pure Appl. Logic164(12) (2013) 1454–1492], we show that whenever κ is a cardinal satisfying κ<κ=κ>ω, then the embeddability relation between κ-sized structures is strongly invariantly universal, and hence complete for (κ-)analytic quasi-orders. We also prove that in the above result we can further restrict our attention to various natural classes of structures, including (generalized) trees, graphs, or (...) groups. This fully generalizes to the uncountable case the main results of [A. Louveau and C. Rosendal, Complete analytic equivalence relations, Trans. Amer. Math. Soc.357(12) (2005) 4839–4866; S.-D. Friedman and L. Motto Ros, Analytic equivalence relations and bi-embeddability, J. Symbolic Logic76(1) (2011) 243–266; J. Williams, Universal countable Borel quasi-orders, J. Symbolic Logic79(3) (2014) 928–954; F. Calderoni and L. Motto Ros, Universality of group embeddability, Proc. Amer. Math. Soc.146 (2018) 1765–1780]. (shrink)

Assuming the existence of a proper class of supercompact cardinals, we force a generic extension in which, for every regular cardinal [Formula: see text], there are [Formula: see text]-Aronszajn trees, and all such trees are special.

Rado’s Conjecture is a compactness/reflection principle that says any nonspecial tree of height ω1 has a nonspecial subtree of size ℵ1. Though incompatible with Martin’s Axiom, Rado’s Conjecture turns out to have many interesting consequences that are also implied by certain forcing axioms. In this paper, we obtain consistency results concerning Rado’s Conjecture and its Baire version. In particular, we show that a fragment of PFA, which is the forcing axiom for Baire Indestructibly Proper forcings, is compatible with the Baire (...) Rado’s Conjecture. As a corollary, the Baire Rado’s Conjecture does not imply Rado’s Conjecture. Then we discuss the strength and limitations of the Baire Rado’s Conjecture regarding its interaction with stationary reflection principles and some families of weak square principles. Finally, we investigate the influence of Rado’s Conjecture on some polarized partition relations. (shrink)

The author requires to retract this paper because there is a gap in the proof of Lemma 3.2, hence also in Theorem 3.1. The revised version is in preparation.

We study the sets that are computable from both halves of some (Martin–Löf) random sequence, which we call 1/2-bases. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.e. elements. It is a proper subideal of the K-trivial sets. We characterize 1/2-bases as the sets computable from both halves of Chaitin’s Ω, and as the sets that obey the cost function c(x,s)=Ωs−Ωx−−−−−−−√. Generalizing these results yields a dense hierarchy of (...) subideals in the K-trivial degrees: For k<n, let Bk/n be the collection of sets that are below any k out of n columns of some random sequence. As before, this is an ideal generated by its c.e. elements and the random sequence in the definition can always be taken to be Ω. Furthermore, the corresponding cost function characterization reveals that Bk/n is independent of the particular representation of the rational k/n, and that Bp is properly contained in Bq for rational numbers p<q. These results are proved using a generalization of the Loomis–Whitney inequality, which bounds the measure of an open set in terms of the measures of its projections. The generality allows us to analyze arbitrary families of orthogonal projections. As it turns out, these do not give us new subideals of the K-trivial sets; we can calculate from the family which Bp it characterizes. We finish by studying the union of Bp for p<1; we prove that this ideal consists of the sets that are robustly computable from some random sequence. This class was previously studied by Hirschfeldt [D. R. Hirschfeldt, C. G. Jockusch, R. Kuyper and P. E. Schupp, Coarse reducibility and algorithmic randomness, J. Symbolic Logic81(3) (2016) 1028–1046], who showed that it is a proper subclass of the K-trivial sets. We prove that all such sets are robustly computable from Ω, and that they form a proper subideal of the sets computable from every (weakly) LR-hard random sequence. We also show that the ideal cannot be characterized by a cost function, giving the first such example of a Σ03 subideal of the K-trivial sets. (shrink)

We study the relationship between effective domination properties and the bounded jump. We answer two open questions about the bounded jump: We prove that the analogue of Sacks jump inversion fails for the bounded jump and the wtt-reducibility. We prove that no c.e. bounded high set can be low by showing that they all have to be Turing complete. We characterize the class of c.e. bounded high sets as being those sets computing the Halting problem via a reduction with use (...) bounded by an ω-c.e. function. We define several notions of a c.e. set being effectively dominant, and show that together with the bounded high sets they form a proper hierarchy. (shrink)

We analyze the descriptive complexity of several Π11-ranks from classical analysis which are associated to Denjoy integration. We show that VBG, VBG∗, ACG, and ACG∗ are Π11-complete, answering a question of Walsh in case of ACG∗. Furthermore, we identify the precise descriptive complexity of the set of functions obtainable with at most α steps of the transfinite process of Denjoy totalization: if |⋅| is the Π11-rank naturally associated to VBG, VBG∗, or ACG∗, and if α<ωck1, then {F∈C(I):|F|≤α} is Σ02α-complete. These (...) finer results are an application of the author’s previous work on the limsup rank on well-founded trees. Finally, {(f,F)∈M(I)×C(I):F∈ACG∗andF'=fa.e.} and {f∈M(I):fis Denjoy integrable} are Π11-complete, answering more questions of Walsh. (shrink)

For a set M, let |M| denote the cardinality of M. A family F is called strongly almost disjoint if there is an n∈ω such that |A∩B|<n for any two distinct elements A, B of F. It is shown in ZF (without the axiom of choice) that, for all infinite sets M and all strongly almost disjoint families F⊆P(M), |F|<|P(M)| and there are no finite-to-one functions from P(M) into F, where P(M) denotes the power set of M.

The large-structure tools of cohomology including toposes and derived categories stay close to arithmetic in practice, yet published foundations for them go beyond ZFC in logical strength. We reduce the gap by founding all the theorems of Grothendieck’s SGA, plus derived categories, at the level of Finite-Order Arithmetic, far below ZFC. This is the weakest possible foundation for the large-structure tools because one elementary topos of sets with infinity is already this strong.

We argue against Foreman’s proposal to settle the continuum hypothesis and other classical independent questions via the adoption of generic large cardinal axioms.