An official website of the United States government
Abstract We construct divergent models of$$\mathsf {AD}^+$$along with the failure of the Continuum Hypothesis ($$\mathsf {CH}$$) under various assumptions. Divergent models of$$\mathsf {AD}^+$$play an important role in descriptive inner model theory; all known analyses of HOD in$$\mathsf {AD}^+$$models (without extra iterability assumptions) are carried out in the region below the existence of divergent models of$$\mathsf {AD}^+$$. Our results are the first step toward resolving various open questions concerning the length of definable prewellorderings of the reals and principles implying$$\neg \mathsf {CH}$$, like$$\mathsf {MM}$$, that divergent models shed light on, see Question 5.1.
more »
« less
This content will become publicly available on February 11, 2026
THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
Abstract We study versions of the tree pigeonhole principle,$$\mathsf {TT}^1$$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether$$\mathsf {TT}^1$$is$$\Pi ^1_1$$-conservative over the ordinary pigeonhole principle,$$\mathsf {RT}^1$$. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike$$\mathsf {RT}^1$$, the problem$$\mathsf {TT}^1$$is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of$$\mathsf {TT}^1$$.
more »
« less
- Award ID(s):
- 1854355
- PAR ID:
- 10612169
- Publisher / Repository:
- CUP
- Date Published:
- Journal Name:
- The Journal of Symbolic Logic
- ISSN:
- 0022-4812
- Page Range / eLocation ID:
- 1 to 23
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A set of reals isuniversally Baireif all of its continuous preimages in topological spaces have the Baire property.$$\mathsf {Sealing}$$is a type of generic absoluteness condition introduced by Woodin that asserts in strong terms that the theory of the universally Baire sets cannot be changed by forcing. The$$\mathsf {Largest\ Suslin\ Axiom}$$($$\mathsf {LSA}$$) is a determinacy axiom isolated by Woodin. It asserts that the largest Suslin cardinal is inaccessible for ordinal definable bijections. Let$$\mathsf {LSA-over-uB}$$be the statement that in all (set) generic extensions there is a model of$$\mathsf {LSA}$$whose Suslin, co-Suslin sets are the universally Baire sets. We show that over some mild large cardinal theory,$$\mathsf {Sealing}$$is equiconsistent with$$\mathsf {LSA-over-uB}$$. In fact, we isolate an exact large cardinal theory that is equiconsistent with both (see Definition 2.7). As a consequence, we obtain that$$\mathsf {Sealing}$$is weaker than the theory ‘$$\mathsf {ZFC} +$$there is a Woodin cardinal which is a limit of Woodin cardinals’. A variation of$$\mathsf {Sealing}$$, called$$\mathsf {Tower\ Sealing}$$, is also shown to be equiconsistent with$$\mathsf {Sealing}$$over the same large cardinal theory. The result is proven via Woodin’s$$\mathsf {Core\ Model\ Induction}$$technique and is essentially the ultimate equiconsistency that can be proven via the current interpretation of$$\mathsf {CMI}$$as explained in the paper.more » « less
-
Abstract Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set$$S \subset \mathbb {R}^k$$by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$, is semialgebraically homeomorphic toS. In this paper, we consider a weaker version of this question. We prove that for any$$\ell \geq 0$$, there exists an algorithm which takes as input a description of a semialgebraic subset$$S \subset \mathbb {R}^k$$given by a quantifier-free first-order formula$$\phi $$in the language of the reals and produces as output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$is$$\ell $$-equivalent toS. The complexity of our algorithm is bounded by$$(sd)^{k^{O(\ell )}}$$, wheresis the number of polynomials appearing in the formula$$\phi $$, andda bound on their degrees. For fixed$$\ell $$, this bound issingly exponentialink. In particular, since$$\ell $$-equivalence implies that thehomotopy groupsup to dimension$$\ell $$of$$|\Delta |$$are isomorphic to those ofS, we obtain a reduction (having singly exponential complexity) of the problem of computing the first$$\ell $$homotopy groups ofSto the combinatorial problem of computing the first$$\ell $$homotopy groups of a finite simplicial complex of size bounded by$$(sd)^{k^{O(\ell )}}$$.more » « less
-
Abstract This paper will study almost everywhere behaviors of functions on partition spaces of cardinals possessing suitable partition properties. Almost everywhere continuity and monotonicity properties for functions on partition spaces will be established. These results will be applied to distinguish the cardinality of certain subsets of the power set of partition cardinals. The following summarizes the main results proved under suitable partition hypotheses.•If$$\kappa $$is a cardinal,$$\epsilon < \kappa $$,$${\mathrm {cof}}(\epsilon ) = \omega $$,$$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$$and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the almost everywhere short length continuity property: There is a club$$C \subseteq \kappa $$and a$$\delta < \epsilon $$so that for all$$f,g \in [C]^\epsilon _*$$, if$$f \upharpoonright \delta = g \upharpoonright \delta $$and$$\sup (f) = \sup (g)$$, then$$\Phi (f) = \Phi (g)$$.•If$$\kappa $$is a cardinal,$$\epsilon $$is countable,$$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$$holds and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the strong almost everywhere short length continuity property: There is a club$$C \subseteq \kappa $$and finitely many ordinals$$\delta _0, ..., \delta _k \leq \epsilon $$so that for all$$f,g \in [C]^\epsilon _*$$, if for all$$0 \leq i \leq k$$,$$\sup (f \upharpoonright \delta _i) = \sup (g \upharpoonright \delta _i)$$, then$$\Phi (f) = \Phi (g)$$.•If$$\kappa $$satisfies$$\kappa \rightarrow _* (\kappa )^\kappa _2$$,$$\epsilon \leq \kappa $$and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the almost everywhere monotonicity property: There is a club$$C \subseteq \kappa $$so that for all$$f,g \in [C]^\epsilon _*$$, if for all$$\alpha < \epsilon $$,$$f(\alpha ) \leq g(\alpha )$$, then$$\Phi (f) \leq \Phi (g)$$.•Suppose dependent choice ($$\mathsf {DC}$$),$${\omega _1} \rightarrow _* ({\omega _1})^{\omega _1}_2$$and the almost everywhere short length club uniformization principle for$${\omega _1}$$hold. Then every function$$\Phi : [{\omega _1}]^{\omega _1}_* \rightarrow {\omega _1}$$satisfies a finite continuity property with respect to closure points: Let$$\mathfrak {C}_f$$be the club of$$\alpha < {\omega _1}$$so that$$\sup (f \upharpoonright \alpha ) = \alpha $$. There is a club$$C \subseteq {\omega _1}$$and finitely many functions$$\Upsilon _0, ..., \Upsilon _{n - 1} : [C]^{\omega _1}_* \rightarrow {\omega _1}$$so that for all$$f \in [C]^{\omega _1}_*$$, for all$$g \in [C]^{\omega _1}_*$$, if$$\mathfrak {C}_g = \mathfrak {C}_f$$and for all$$i < n$$,$$\sup (g \upharpoonright \Upsilon _i(f)) = \sup (f \upharpoonright \Upsilon _i(f))$$, then$$\Phi (g) = \Phi (f)$$.•Suppose$$\kappa $$satisfies$$\kappa \rightarrow _* (\kappa )^\epsilon _2$$for all$$\epsilon < \kappa $$. For all$$\chi < \kappa $$,$$[\kappa ]^{<\kappa }$$does not inject into$${}^\chi \mathrm {ON}$$, the class of$$\chi $$-length sequences of ordinals, and therefore,$$|[\kappa ]^\chi | < |[\kappa ]^{<\kappa }|$$. As a consequence, under the axiom of determinacy$$(\mathsf {AD})$$, these two cardinality results hold when$$\kappa $$is one of the following weak or strong partition cardinals of determinacy:$${\omega _1}$$,$$\omega _2$$,$$\boldsymbol {\delta }_n^1$$(for all$$1 \leq n < \omega $$) and$$\boldsymbol {\delta }^2_1$$(assuming in addition$$\mathsf {DC}_{\mathbb {R}}$$).more » « less
-
Abstract This is the second installment in a series of papers applying descriptive set theoretic techniques to both analyze and enrich classical functors from homological algebra and algebraic topology. In it, we show that the Čech cohomology functorson the category of locally compact separable metric spaces each factor into (i) what we term theirdefinable version, a functortaking values in the category$$\mathsf {GPC}$$ofgroups with a Polish cover(a category first introduced in this work’s predecessor), followed by (ii) a forgetful functor from$$\mathsf {GPC}$$to the category of groups. These definable cohomology functors powerfully refine their classical counterparts: we show that they are complete invariants, for example, of the homotopy types of mapping telescopes ofd-spheres ord-tori for any$$d\geq 1$$, and, in contrast, that there exist uncountable families of pairwise homotopy inequivalent mapping telescopes of either sort on which the classical cohomology functors are constant. We then apply the functorsto show that a seminal problem in the development of algebraic topology – namely, Borsuk and Eilenberg’s 1936 problem of classifying, up to homotopy, the maps from a solenoid complement$$S^3\backslash \Sigma $$to the$$2$$-sphere – is essentially hyperfinite but not smooth. Fundamental to our analysis is the fact that the Čech cohomology functorsadmit two main formulations: a more combinatorial one and a more homotopical formulation as the group$$[X,P]$$of homotopy classes of maps fromXto a polyhedral$$K(G,n)$$spaceP. We describe the Borel-definable content of each of these formulations and prove a definable version of Huber’s theorem reconciling the two. In the course of this work, we record definable versions of Urysohn’s Lemma and the simplicial approximation and homotopy extension theorems, along with a definable Milnor-type short exact sequence decomposition of the space$$\mathrm {Map}(X,P)$$in terms of its subset ofphantom maps; relatedly, we provide a topological characterization of this set for any locally compact Polish spaceXand polyhedronP. In aggregate, this work may be more broadly construed as laying foundations for the descriptive set theoretic study of the homotopy relation on such spaces$$\mathrm {Map}(X,P)$$, a relation which, together with the more combinatorial incarnation of, embodies a substantial variety of classification problems arising throughout mathematics. We show, in particular, that ifPis a polyhedralH-group, then this relation is both Borel and idealistic. In consequence,$$[X,P]$$falls in the category ofdefinable groups, an extension of the category$$\mathsf {GPC}$$introduced herein for its regularity properties, which facilitate several of the aforementioned computations.more » « less
