Set Theory

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 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)

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 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 ZFC 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 an exposition of the compactness of L(QcfC), for any set C of regular cardinals.

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)

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 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)

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.

In this paper we study proofs of some general forms of the Second Incompleteness Theorem. These forms conform to the Feferman format, where the proof predicate is fixed and the representation of the set of axioms varies. We extend the Feferman framework in one important point: we allow the interpretation of number theory to vary.

Let L be a computable vocabulary, let X_L be the space of L-structures with universe ω and let f:2^\omega \rightarrow X_L be a hyperarithmetic function such that for all x,y \in 2^\omega, if x \equiv _h y then f(x) \cong f(y). One of the following two properties must hold. (1) The Scott rank of f(0) is \omega _1^{CK} + 1. (2) For all x \in 2^\omega, f(x) \cong f(0).

We show that arithmetical transfinite recursion is equivalent to a suitable formalization of the following: For every ordinal \alpha there exists an ordinal /beta such that 1 + \beta \cdot (\beta + \alpha) admits an almost order preserving collapse into \beta. Arithmetical comprehension is equivalent to a statement of the same form, with \beta \cdot \alpha at the place of \beta \cdot (\beta + \alpha). We will also characterise the principles that any set is contained in a countable coded ω-model (...) of arithmetical transfinite recursion and arithmetical comprehension, respectively. (shrink)

We simultaneously generalize Silver’s perfect set theorem for co-analytic equivalence relations and Harrington-Marker-Shelah’s Dilworth-style perfect set theorem for Borel quasi-orders, establish the analogous theorem at the next definable cardinal, and give further generalizations under weaker definability conditions.

Two structures A and B are n-equivalent if Player II has a winning strategy in the n-move Ehrenfeucht-Fraïssé game on A and B. In earlier articles we studied n-equivalence classes of ordinals and coloured ordinals. In this article we similarly treat a class of scattered order-types, focussing on monomials and sums of monomials in ω and its reverse ω*.

We determine the consistency strength of determinacy for projective games of length ω^2. Our main theorem is that $\Pi _{n + 1}^1$-determinacy for games of length ω^2 implies the existence of a model of set theory with ω + n Woodin cardinals. In a first step, we show that this hypothesis implies that there is a countable set of reals A such that M_n(A), the canonical inner model for n Woodin cardinals constructed over A, satisfies $A = R$ and the (...) Axiom of Determinacy. Then we argue how to obtain a model with ω + n Woodin cardinal from this. We also show how the proof can be adapted to investigate the consistency strength of determinacy for games of length ω^2 with payoff in $R^R\Pi _1^1$ or with σ-projective payoff. (shrink)

Let ${\cal I}$ be an ideal on ω. By cov${}_{}^{\rm{*}}$ we denote the least size of a family ${\cal B} \subseteq {\cal I}$ such that for every infinite $X \in {\cal I}$ there is $B \in {\cal B}$ for which $B\mathop \cap \nolimits X$ is infinite. We say that an AD family ${\cal A} \subseteq {\cal I}$ is a MAD family restricted to${\cal I}$ if for every infinite $X \in {\cal I}$ there is $A \in {\cal A}$ such that $|X\mathop (...) \cap \nolimits A| = \omega$. Let a$\left$ be the least size of an infinite MAD family restricted to ${\cal I}$. We prove that If $max${a,cov${}_{}^{\rm{*}}\}$ then a$\left = {\omega _1}$, and consequently, if ${\cal I}$ is tall and $\le {\omega _2}$ then a$\left = max$ {a,cov${}_{}^{\rm{*}}\}$. We use these results to prove that if c$\le {\omega _2}$ then o$= \overline o$ and that as$= max${a,non$\}$. We also analyze the problem whether it is consistent with the negation of CH that every AD family of size ω1 can be extended to a MAD family of size ω1. (shrink)