Year:

  1.  2
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  5
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  1
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  6
    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).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  26
    Choice-Free Stone Duality.Nick Bezhanishvili & Wesley H. Holliday - 2020 - Journal of Symbolic Logic 85 (1):109-148.
    The standard topological representation of a Boolean algebra via the clopen sets of a Stone space requires a nonconstructive choice principle, equivalent to the Boolean Prime Ideal Theorem. In this article, we describe a choice-free topological representation of Boolean algebras. This representation uses a subclass of the spectral spaces that Stone used in his representation of distributive lattices via compact open sets. It also takes advantage of Tarski’s observation that the regular open sets of any topological space form a Boolean (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  6.  4
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  6
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  9
    Truth and Feasible Reducibility.Ali Enayat, Mateusz Łełyk & Bartosz Wcisło - 2020 - Journal of Symbolic Logic 85 (1):367-421.
    Let ${\cal T}$ be any of the three canonical truth theories CT^− (compositional truth without extra induction), FS^− (Friedman–Sheard truth without extra induction), or KF^− (Kripke–Feferman truth without extra induction), where the base theory of ${\cal T}$ is PA. We establish the following theorem, which implies that ${\cal T}$ has no more than polynomial speed-up over PA. Theorem.${\cal T}$is feasibly reducible to PA, in the sense that there is a polynomial time computable function f such that for every ${\cal T}$-proof (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  3
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  9
    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.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  6
    Two New Series of Principles in the Interpretability Logic of All Reasonable Arithmetical Theories.Evan Goris & Joost J. Joosten - 2020 - Journal of Symbolic Logic 85 (1):1-25.
    The provability logic of a theory T captures the structural behavior of formalized provability in T as provable in T itself. Like provability, one can formalize the notion of relative interpretability giving rise to interpretability logics. Where provability logics are the same for all moderately sound theories of some minimal strength, interpretability logics do show variations.The logic IL is defined as the collection of modal principles that are provable in any moderately sound theory of some minimal strength. In this article (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  3
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13.  2
    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.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  2
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  2
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16.  2
    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.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  5
    A Game Characterizing Baire Class 1 Functions.Viktor Kiss - 2020 - Journal of Symbolic Logic 85 (1):456-466.
    Duparc introduced a two-player game for a function f between zero-dimensional Polish spaces in which Player II has a winning strategy iff f is of Baire class 1. We generalize this result by defining a game for an arbitrary function f : X → Y between arbitrary Polish spaces such that Player II has a winning strategy in this game iff f is of Baire class 1. Using the strategy of Player II, we reprove a result concerning first return recoverable (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18.  2
    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.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  4
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20.  3
    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 ω*.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  5
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  22.  7
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  4
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  13
    Coherent Extension of Partial Automorphisms, Free Amalgamation and Automorphism Groups.Daoud Siniora & Sławomir Solecki - 2020 - Journal of Symbolic Logic 85 (1):199-223.
    We give strengthened versions of the Herwig–Lascar and Hodkinson–Otto extension theorems for partial automorphisms of finite structures. Such strengthenings yield several combinatorial and group-theoretic consequences for homogeneous structures. For instance, we establish a coherent form of the extension property for partial automorphisms for certain Fraïssé classes. We deduce from these results that the isometry group of the rational Urysohn space, the automorphism group of the Fraïssé limit of any Fraïssé class that is the class of all ${\cal F}$-free structures, and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
 Previous issues
  
Next issues