Set Theory

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

1996 found
Order:
1 — 50 / 1996
Material to categorize
  1. 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  
  2. 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  
  3. 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  
  4. 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  
  5. 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  
  6. 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   2 citations  
  7. 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  
  8. 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  
  9. 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 (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  10. Perfect Tree Forcings for Singular Cardinals.Natasha Dobrinen, Dan Hathaway & Karel Prikry - 2020 - Annals of Pure and Applied Logic 171 (9):102827.
  11. 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  
  12. 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  
  13. 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  
  14. 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  
  15. 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  
  16. 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  
  17. 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 (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  18. 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  
  19. 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  
  20. 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  
  21. 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  
  22. 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  
  23. 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  
  24. Turing Degrees in Polish Spaces and Decomposibility of Borel Functions.Vassilios Gregoriades, Takayuki Kihara & Keng Meng Ng - forthcoming - Journal of Mathematical Logic.
    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  
  25. 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 (2 more)  
     
    Export citation  
     
    Bookmark  
  26. 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 (2 more)  
     
    Export citation  
     
    Bookmark  
  27. 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 (2 more)  
     
    Export citation  
     
    Bookmark  
  28. 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  
  29. 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  
  30. Another Look at the Second Incompleteness Theorem.Albert Visser - 2020 - Review of Symbolic Logic 13 (2):269-295.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  31. Assigning an Isomorphism Type to a Hyperdegree.Howard Becker - 2020 - Journal of Symbolic Logic 85 (1):325-337.
    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).
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  32. Predicative Collapsing Principles.Anton Freund - 2020 - Journal of Symbolic Logic 85 (1):511-530.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  33. On the Existence of Large Antichains for Definable Quasi-Orders.Benjamin D. Miller & Zoltán Vidnyánszky - 2020 - Journal of Symbolic Logic 85 (1):103-108.
    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.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  34. Ehrenfeucht-Fraïssé Games on a Class of Scattered Linear Orders.Feresiano Mwesigye & John Kenneth Truss - 2020 - Journal of Symbolic Logic 85 (1):37-60.
    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 ω*.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35. The Consistency Strength of Long Projective Determinacy.Juan P. Aguilera & Sandra Müller - 2020 - Journal of Symbolic Logic 85 (1):338-366.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  36. Restricted Mad Families.Osvaldo Guzmán, Michael Hrušák & Osvaldo Téllez - 2020 - Journal of Symbolic Logic 85 (1):149-165.
    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 (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  37. A Minimal Pair in the Generic Degrees.Denis R. Hirschfeldt - 2020 - Journal of Symbolic Logic 85 (1):531-537.
    We show that there is a minimal pair in the nonuniform generic degrees, and hence also in the uniform generic degrees. This fact contrasts with Igusa’s result that there are no minimal pairs for relative generic computability and answers a basic structural question mentioned in several papers in the area.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  38. Slow P-Point Ultrafilters.Renling Jin - 2020 - Journal of Symbolic Logic 85 (1):26-36.
    We answer a question of Blass, Di Nasso, and Forti [2, 7] by proving, assuming Continuum Hypothesis or Martin’s Axiom, that there exists a P-point which is not interval-to-one and there exists an interval-to-one P-point which is neither quasi-selective nor weakly Ramsey.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  39. Factorials of Infinite Cardinals in Zf Part II: Consistency Results.Guozhen Shen & Jiachen Yuan - 2020 - Journal of Symbolic Logic 85 (1):244-270.
    For a set x, let S(x) be the set of all permutations of x. We prove by the method of permutation models that the following statements are consistent with ZF: (1) There is an infinite set x such that |p(x)|<|S(x)|<|seq^1-1(x)|<|seq(x)|, where p(x) is the powerset of x, seq(x) is the set of all finite sequences of elements of x, and seq^1-1(x) is the set of all finite sequences of elements of x without repetition. (2) There is a Dedekind infinite set (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  40. Factorials of Infinite Cardinals in Zf Part I: Zf Results.Guozhen Shen & Jiachen Yuan - 2020 - Journal of Symbolic Logic 85 (1):224-243.
    For a set x, let ${\cal S}\left$ be the set of all permutations of x. We prove in ZF several results concerning this notion, among which are the following: For all sets x such that ${\cal S}\left$ is Dedekind infinite, $\left| {{{\cal S}_{{\rm{fin}}}}\left} \right| < \left| {{\cal S}\left} \right|$ and there are no finite-to-one functions from ${\cal S}\left$ into ${{\cal S}_{{\rm{fin}}}}\left$, where ${{\cal S}_{{\rm{fin}}}}\left$ denotes the set of all permutations of x which move only finitely many elements. For all sets (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  41. The Determined Property of Baire in Reverse Math.Eric P. Astor, Damir Dzhafarov, Antonio Montalbán, Reed Solomon & Linda Brown Westrick - 2020 - Journal of Symbolic Logic 85 (1):166-198.
    We define the notion of a completely determined Borel code in reverse mathematics, and consider the principle $CD - PB$, which states that every completely determined Borel set has the property of Baire. We show that this principle is strictly weaker than $AT{R_0}$. Any ω-model of $CD - PB$ must be closed under hyperarithmetic reduction, but $CD - PB$ is not a theory of hyperarithmetic analysis. We show that whenever $M \subseteq {2^\omega }$ is the second-order part of an ω-model (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42. Forcing and the Halpern–Läuchli Theorem.Natasha Dobrinen & Daniel Hathaway - 2020 - Journal of Symbolic Logic 85 (1):87-102.
    We investigate the effects of various forcings on several forms of the Halpern– Läuchli theorem. For inaccessible κ, we show they are preserved by forcings of size less than κ. Combining this with work of Zhang in [17] yields that the polarized partition relations associated with finite products of the κ-rationals are preserved by all forcings of size less than κ over models satisfying the Halpern– Läuchli theorem at κ. We also show that the Halpern–Läuchli theorem is preserved by <κ-closed (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  43. Indestructibility of the Tree Property.Radek Honzik & Šárka Stejskalová - 2020 - Journal of Symbolic Logic 85 (1):467-485.
    In the first part of the article, we show that if $\omega \le \kappa < \lambda$ are cardinals, ${\kappa ^{ < \kappa }} = \kappa$, and λ is weakly compact, then in $V\left[M {\left} \right]$ the tree property at $$\lambda = \left^{V\left[ {\left} \right]} $$ is indestructible under all ${\kappa ^ + }$-cc forcing notions which live in $V\left[ {{\rm{Add}}\left} \right]$, where ${\rm{Add}}\left$ is the Cohen forcing for adding λ-many subsets of κ and $\left$ is the standard Mitchell forcing for (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  44. The Wadge Order on the Scott Domain is Not a Well-Quasi-Order.Jacques Duparc & Louis Vuilleumier - 2020 - Journal of Symbolic Logic 85 (1):300-324.
    We prove that the Wadge order on the Borel subsets of the Scott domain is not a well-quasi-order, and that this feature even occurs among the sets of Borel rank at most 2. For this purpose, a specific class of countable 2-colored posets $\mathbb{P}_{emb} $ equipped with the order induced by homomorphisms is embedded into the Wadge order on the $\Delta _2^0 $-degrees of the Scott domain. We then show that $\mathbb{P}_{emb} $ admits both infinite strictly decreasing chains and infinite (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  45. Chaitin’s Ω as a Continuous Function.Rupert Hölzl, Wolfgang Merkle, Joseph Miller, Frank Stephan & Liang Yu - 2020 - Journal of Symbolic Logic 85 (1):486-510.
    We prove that the continuous function${\rm{\hat \Omega }}:2^\omega \to $ that is defined via$X \mapsto \mathop \sum \limits_n 2^{ - K\left} $ for all $X \in {2^\omega }$ is differentiable exactly at the Martin-Löf random reals with the derivative having value 0; that it is nowhere monotonic; and that $\mathop \smallint \nolimits _0^1{\rm{\hat{\Omega }}}\left\,{\rm{d}}X$ is a left-c.e. $wtt$-complete real having effective Hausdorff dimension ${1 / 2}$.We further investigate the algorithmic properties of ${\rm{\hat{\Omega }}}$. For example, we show that the maximal (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  46. Randomness Notions and Reverse Mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.
    We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$-random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C-incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  47. On Isomorphism Classes of Computably Enumerable Equivalence Relations.Uri Andrews & Serikzhan A. Badaev - 2020 - Journal of Symbolic Logic 85 (1):61-86.
    We examine how degrees of computably enumerable equivalence relations under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of ω which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained in the (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  48. Hamel Spaces and Distal Expansions.Allen Gehret & Travis Nell - 2020 - Journal of Symbolic Logic 85 (1):422-438.
    In this note, we construct a distal expansion for the structure $(R, +, <, H)$, where $H \subseteq R$ is a dense $Q$-vector space basis of $R$ (a so-called Hamel basis). Our construction is also an expansion of the dense pair $(R, +, <, Q)$ and has full quantifier elimination in a natural language.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  49. Multiple Choices Imply the Ingleton and Krein–Milman Axioms.Marianne Morillon - 2020 - Journal of Symbolic Logic 85 (1):439-455.
    In set theory without the Axiom of Choice, we consider Ingleton’s axiom which is the ultrametric counterpart of the Hahn–Banach axiom. We show that in ZFA, i.e., in the set theory without the Axiom of Choice weakened to allow “atoms,” Ingleton’s axiom does not imply the Axiom of Choice. We also prove that in ZFA, the “multiple choice” axiom implies the Krein–Milman axiom. We deduce that, in ZFA, the conjunction of the Hahn–Banach, Ingleton and Krein–Milman axioms does not imply the (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  50. Univalent polymorphism.Benno van den Berg - 2020 - Annals of Pure and Applied Logic 171 (6):102793.
    We show that Martin Hyland's effective topos can be exhibited as the homotopy category of a path category EFF. Path categories are categories of fibrant objects in the sense of Brown satisfying two additional properties and as such provide a context in which one can interpret many notions from homotopy theory and Homotopy Type Theory. Within the path category EFF one can identify a class of discrete fibrations which is closed under push forward along arbitrary fibrations (in other words, this (...)
    Remove from this list   Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
1 — 50 / 1996