Set Theory

Edited by Toby Meadows (University of California, Irvine)
Related categories

2117 found
Order:
1 — 50 / 2117
Material to categorize
  1. An Exposition of the Compactness Of.Enrique Casanovas & Martin Ziegler - 2020 - Bulletin of Symbolic Logic 26 (3-4):212-218.
    We give an exposition of the compactness of L(QcfC), for any set C of regular cardinals.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2. Infinitary Generalizations of Deligne’s Completeness Theorem.Christian Espíndola - 2020 - Journal of Symbolic Logic 85 (3):1147-1162.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3. A Reconstruction of Steel’s Multiverse Project.Penelope Maddy & Toby Meadows - 2020 - Bulletin of Symbolic Logic 26 (2):118-169.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4. A Refinement of the Ramsey Hierarchy Via Indescribability.Brent Cody - 2020 - Journal of Symbolic Logic 85 (2):773-808.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5. Exact Completion and Constructive Theories of Sets.Jacopo Emmenegger & Erik Palmgren - 2020 - Journal of Symbolic Logic 85 (2):563-584.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6. Knaster and Friends II: The C-Sequence Number.Chris Lambie-Hanson & Assaf Rinot - 2020 - Journal of Mathematical Logic 21 (1):2150002.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7. Tameness, Powerful Images, and Large Cardinals.Will Boney & Michael Lieberman - 2020 - Journal of Mathematical Logic 21 (1):2050024.
    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) (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8. Specializing Trees and Answer to a Question of Williams.Mohammad Golshani & Saharon Shelah - 2020 - Journal of Mathematical Logic 21 (1):2050023.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9. Turing Degrees in Polish Spaces and Decomposability of Borel Functions.Vassilios Gregoriades, Takayuki Kihara & Keng Meng Ng - 2020 - Journal of Mathematical Logic 21 (1):2050021.
    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 (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10. Nonmeasurable Sets and Unions with Respect to Tree Ideals.Marcin Michalski, Robert Rałowski & Szymon Żeberski - 2020 - Bulletin of Symbolic Logic 26 (1):1-14.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11. An Application of Recursion Theory to Analysis.Liang Yu - 2020 - Bulletin of Symbolic Logic 26 (1):15-25.
    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].
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12. Local Saturation and Square Everywhere.Monroe Eskew - 2020 - Journal of Mathematical Logic 20 (3):2050019.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13. Constructing Sequences One Step at a Time.Henry Towsner - 2020 - Journal of Mathematical Logic 20 (3):2050017.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14. The Tree Property at Double Successors of Singular Cardinals of Uncountable Cofinality with Infinite Gaps.Mohammad Golshani & Alejandro Poveda - 2021 - Annals of Pure and Applied Logic 172 (1):102853.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15. Adaptive Fregean Set Theory.Diderik Batens - 2020 - Studia Logica 108 (5):903-939.
    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.
    Remove from this list   Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  16. Identity Crisis Between Supercompactness and Vǒpenka’s Principle.Yair Hayut, Menachem Magidor & Alejandro Poveda - forthcoming - Journal of Symbolic Logic:1-32.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17. When P(Λ) (Vaguely) Resembles Κ.Pierre Matet - 2021 - Annals of Pure and Applied Logic 172 (2):102874.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18. Forcing and the Universe of Sets: Must We Lose Insight?Neil Barton - 2020 - Journal of Philosophical Logic 49 (4):575-612.
    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 (...)
    Remove from this list   Direct download (5 more)  
    Translate
     
     
    Export citation  
     
    Bookmark   2 citations  
  19. Filter-Linkedness and its Effect on Preservation of Cardinal Characteristics.Jörg Brendle, Miguel A. Cardona & Diego A. Mejía - 2021 - Annals of Pure and Applied Logic 172 (1):102856.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  20. Dependent Choice, Properness, and Generic Absoluteness.David Asperó & Asaf Karagila - forthcoming - Review of Symbolic Logic:1-25.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21. Mitchell-Inspired Forcing, with Small Working Parts and Collections of Models of Uniform Size as Side Conditions, and Gap-One Simplified Morasses.Charles Morgan - forthcoming - Journal of Symbolic Logic:1-35.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  22. Stably Measurable Cardinals.P. D. Welch - forthcoming - Journal of Symbolic Logic:1-23.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23. Some Constructions of Ultrafilters Over a Measurable Cardinal.Moti Gitik - 2020 - Annals of Pure and Applied Logic 171 (8):102821.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24. Computability of Pseudo-Cubes.Marko Horvat, Zvonko Iljazović & Bojan Pažek - 2020 - Annals of Pure and Applied Logic 171 (8):102823.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  25. A Forcing Axiom for a Non-Special Aronszajn Tree.John Krueger - 2020 - Annals of Pure and Applied Logic 171 (8):102820.
    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 (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  26. The Theory of Ceers Computes True Arithmetic.Uri Andrews, Noah Schweber & Andrea Sorbi - 2020 - Annals of Pure and Applied Logic 171 (8):102811.
    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) .
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  27. Polish Metric Spaces with Fixed Distance Set.Riccardo Camerlo, Alberto Marcone & Luca Motto Ros - 2020 - Annals of Pure and Applied Logic 171 (10):102832.
    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, (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  28. Set-Theoretic Pluralism and the Benacerraf Problem.Justin Clarke-Doane - 2020 - Philosophical Studies 177 (7):2013-2030.
    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 (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  29. A Premouse Inheriting Strong Cardinals From V.Farmer Schlutzenberg - 2020 - Annals of Pure and Applied Logic 171 (9):102826.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30. Diagonal Supercompact Radin Forcing.Omer Ben-Neria, Chris Lambie-Hanson & Spencer Unger - 2020 - Annals of Pure and Applied Logic 171 (10):102828.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  31. Correction to: Some Restricted Lindenbaum Theorems Equivalent to the Axiom of Choice.David W. Miller - 2020 - Logica Universalis 14 (2):279-279.
    The publisher would like to confirm that the author owns the copyright of the article.
    Remove from this list   Direct download (3 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  32. Perfect Tree Forcings for Singular Cardinals.Natasha Dobrinen, Dan Hathaway & Karel Prikry - 2020 - Annals of Pure and Applied Logic 171 (9):102827.
  33. Silver Type Theorems for Collapses.Moti Gitik - 2020 - Annals of Pure and Applied Logic 171 (9):102825.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  34. Expander Construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35. Expansions of Real Closed Fields That Introduce No New Smooth Functions.Pantelis E. Eleftheriou & Alex Savatovsky - 2020 - Annals of Pure and Applied Logic 171 (7):102808.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  36. The Density Zero Ideal and the Splitting Number.Dilip Raghavan - 2020 - Annals of Pure and Applied Logic 171 (7):102807.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  37. Turing Reducibility in the Fine Hierarchy.Alexander G. Melnikov, Victor L. Selivanov & Mars M. Yamaleev - 2020 - Annals of Pure and Applied Logic 171 (7):102766.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  38. 2008 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '08.Alex J. Wilkie - 2009 - Bulletin of Symbolic Logic 15 (1):95-139.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  39. Inner-Model Reflection Principles.Neil Barton, Andrés Eduardo Caicedo, Gunter Fuchs, Joel David Hamkins, Jonas Reitz & Ralf Schindler - 2020 - Studia Logica 108 (3):573-595.
    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 (...)
    Remove from this list   Direct download (3 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  40. The Consistency Strength of Hyperstationarity.Joan Bagaria, Menachem Magidor & Salvador Mancilla - 2019 - Journal of Mathematical Logic 20 (1):2050004.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  41. Uncountable Structures Are Not Classifiable Up to Bi-Embeddability.Filippo Calderoni, Heike Mildenberger & Luca Motto Ros - 2019 - Journal of Mathematical Logic 20 (1):2050001.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42. The Special Aronszajn Tree Property.Mohammad Golshani & Yair Hayut - 2019 - Journal of Mathematical Logic 20 (1):2050003.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  43. Rado’s Conjecture and its Baire Version.Jing Zhang - 2019 - Journal of Mathematical Logic 20 (1):1950015.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  44. Pseudofinite Difference Fields.Tingxiang Zou - 2019 - Journal of Mathematical Logic 20 (1):1993001.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  45. Computing From Projections of Random Points.Noam Greenberg, Joseph S. Miller & André Nies - 2019 - Journal of Mathematical Logic 20 (1):1950014.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  46. Effective Domination and the Bounded Jump.Keng Meng Ng & Hongyuan Yu - 2020 - Notre Dame Journal of Formal Logic 61 (2):203-225.
    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 (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  47. An Effective Analysis of the Denjoy Rank.Linda Westrick - 2020 - Notre Dame Journal of Formal Logic 61 (2):245-263.
    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 (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  48. A Note on Strongly Almost Disjoint Families.Guozhen Shen - 2020 - Notre Dame Journal of Formal Logic 61 (2):227-231.
    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.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  49. The Large Structures of Grothendieck Founded on Finite-Order Arithmetic.Colin Mclarty - 2020 - Review of Symbolic Logic 13 (2):296-325.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  50. Generic Large Cardinals as Axioms.Monroe Eskew - 2020 - Review of Symbolic Logic 13 (2):375-387.
    We argue against Foreman’s proposal to settle the continuum hypothesis and other classical independent questions via the adoption of generic large cardinal axioms.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 2117