Journal of Symbolic Logic

ISSN: 0022-4812

36 found

View year:

  1.  4
    Investigating the Computable Friedman–Stanley Jump.Uri Andrews & Luca San Mauro - 2024 - Journal of Symbolic Logic 89 (2):918-944.
    The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2.  6
    On Cohen and Prikry Forcing Notions.Tom Benhamou & Moti Gitik - 2024 - Journal of Symbolic Logic 89 (2):858-904.
    Abstract(1)We show that it is possible to add $\kappa ^+$ -Cohen subsets to $\kappa $ with a Prikry forcing over $\kappa $. This answers a question from [9].(2)A strengthening of non-Galvin property is introduced. It is shown to be consistent using a single measurable cardinal which improves a previous result by S. Garti, S. Shelah, and the first author [5].(3)A situation with Extender-based Prikry forcings is examined. This relates to a question of H. Woodin.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  10
    Classification of -Categorical Monadically Stable Structures.Bertalan Bodor - 2024 - Journal of Symbolic Logic 89 (2):460-495.
    A first-order structure $\mathfrak {A}$ is called monadically stable iff every expansion of $\mathfrak {A}$ by unary predicates is stable. In this paper we give a classification of the class $\mathcal {M}$ of $\omega $ -categorical monadically stable structure in terms of their automorphism groups. We prove in turn that $\mathcal {M}$ is the smallest class of structures which contains the one-element pure set, is closed under isomorphisms, and is closed under taking finite disjoint unions, infinite copies, and finite index (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4. Partitioning the Real Line Into Borel Sets.Will Brian - 2024 - Journal of Symbolic Logic 89 (2):549-568.
    For which infinite cardinals $\kappa $ is there a partition of the real line ${\mathbb R}$ into precisely $\kappa $ Borel sets? Work of Lusin, Souslin, and Hausdorff shows that ${\mathbb R}$ can be partitioned into $\aleph _1$ Borel sets. But other than this, we show that the spectrum of possible sizes of partitions of ${\mathbb R}$ into Borel sets can be fairly arbitrary. For example, given any $A \subseteq \omega $ with $0,1 \in A$, there is a forcing extension (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5. Modular Many-Valued Semantics for Combined Logics.Carlos Caleiro & Sérgio Marcelino - 2024 - Journal of Symbolic Logic 89 (2):583-636.
    We obtain, for the first time, a modular many-valued semantics for combined logics, which is built directly from many-valued semantics for the logics being combined, by means of suitable universal operations over partial non-deterministic logical matrices. Our constructions preserve finite-valuedness in the context of multiple-conclusion logics, whereas, unsurprisingly, it may be lost in the context of single-conclusion logics. Besides illustrating our constructions over a wide range of examples, we also develop concrete applications of our semantic characterizations, namely regarding the semantics (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  7
    Forbidden Induced Subgraphs and the Łoś–Tarski Theorem.Yijia Chen & Jörg Flum - 2024 - Journal of Symbolic Logic 89 (2):516-548.
    Let $\mathscr {C}$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś–Tarski Theorem from classical model theory implies that $\mathscr {C}$ is definable in first-order logic by a sentence $\varphi $ if and only if $\mathscr {C}$ has a finite set of forbidden induced finite subgraphs. This result provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of forbidden (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  2
    Discontinuous Homomorphisms of With.Bob A. Dumas - 2024 - Journal of Symbolic Logic 89 (2):665-696.
    Assume that M is a transitive model of $ZFC+CH$ containing a simplified $(\omega _1,2)$ -morass, $P\in M$ is the poset adding $\aleph _3$ generic reals and G is P-generic over M. In M we construct a function between sets of terms in the forcing language, that interpreted in $M[G]$ is an $\mathbb R$ -linear order-preserving monomorphism from the finite elements of an ultrapower of the reals, over a non-principal ultrafilter on $\omega $, into the Esterle algebra of formal power series. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  3
    Tight Eventually Different Families.Vera Fischer & Corey Bacal Switzer - 2024 - Journal of Symbolic Logic 89 (2):697-723.
    Generalizing the notion of a tight almost disjoint family, we introduce the notions of a tight eventually different family of functions in Baire space and a tight eventually different set of permutations of $\omega $. Such sets strengthen maximality, exist under $\mathsf {MA} (\sigma \mathrm {-centered})$ and come with a properness preservation theorem. The notion of tightness also generalizes earlier work on the forcing indestructibility of maximality of families of functions. As a result we compute the cardinals $\mathfrak {a}_e$ and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  89
    Axiomatizability of Propositionally Quantified Modal Logics on Relational Frames.Peter Fritz - 2024 - Journal of Symbolic Logic 89 (2):758-793.
    Propositional modal logic over relational frames is naturally extended with propositional quantifiers by letting them range over arbitrary sets of worlds of the relevant frame. This is also known as second-order propositional modal logic. The propositionally quantified modal logic of a class of relational frames is often not axiomatizable, although there are known exceptions, most notably the case of frames validating the strong modal logic $\mathrm {S5}$. Here, we develop new general methods with which many of the open questions in (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  9
    Keisler’s Theorem and Cardinal Invariants.Tatsuya Goto - 2024 - Journal of Symbolic Logic 89 (2):905-917.
    We consider several variants of Keisler’s isomorphism theorem. We separate these variants by showing implications between them and cardinal invariants hypotheses. We characterize saturation hypotheses that are stronger than Keisler’s theorem with respect to models of size $\aleph _1$ and $\aleph _0$ by $\mathrm {CH}$ and $\operatorname {cov}(\mathsf {meager}) = \mathfrak {c} \land 2^{<\mathfrak {c}} = \mathfrak {c}$ respectively. We prove that Keisler’s theorem for models of size $\aleph _1$ and $\aleph _0$ implies $\mathfrak {b} = \aleph _1$ and $\operatorname (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  2
    Katětov Order on Mad Families.Osvaldo Guzmán - 2024 - Journal of Symbolic Logic 89 (2):794-828.
    We continue with the study of the Katětov order on MAD families. We prove that Katětov maximal MAD families exist under $\mathfrak {b=c}$ and that there are no Katětov-top MAD families assuming $\mathfrak {s\leq b}.$ This improves previously known results from the literature. We also answer a problem form Arciga, Hrušák, and Martínez regarding Katětov maximal MAD families.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  4
    Nsop-Like Independence in Aecats.Mark Kamsma - 2024 - Journal of Symbolic Logic 89 (2):724-757.
    The classes stable, simple, and NSOP $_1$ in the stability hierarchy for first-order theories can be characterised by the existence of a certain independence relation. For each of them there is a canonicity theorem: there can be at most one nice independence relation. Independence in stable and simple first-order theories must come from forking and dividing (which then coincide), and for NSOP $_1$ theories it must come from Kim-dividing. We generalise this work to the framework of Abstract Elementary Categories (AECats) (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  9
    Isomorphism of Locally Compact Polish Metric Structures.Maciej Malicki - 2024 - Journal of Symbolic Logic 89 (2):646-664.
    We study the isomorphism relation on Borel classes of locally compact Polish metric structures. We prove that isomorphism on such classes is always classifiable by countable structures (equivalently: Borel reducible to graph isomorphism), which implies, in particular, that isometry of locally compact Polish metric spaces is Borel reducible to graph isomorphism. We show that potentially $\boldsymbol {\Pi }^{0}_{\alpha + 1}$ isomorphism relations are Borel reducible to equality on hereditarily countable sets of rank $\alpha $, $\alpha \geq 2$. We also study (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  19
    Partition Genericity and Pigeonhole Basis Theorems.Benoit Monin & Ludovic Patey - 2024 - Journal of Symbolic Logic 89 (2):829-857.
    There exist two main notions of typicality in computability theory, namely, Cohen genericity and randomness. In this article, we introduce a new notion of genericity, called partition genericity, which is at the intersection of these two notions of typicality, and show that many basis theorems apply to partition genericity. More precisely, we prove that every co-hyperimmune set and every Kurtz random is partition generic, and that every partition generic set admits weak infinite subsets, for various notions of weakness. In particular, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  13
    Cantorian Models of Predicative.Panagiotis Rouvelas - 2024 - Journal of Symbolic Logic 89 (2):637-645.
    Tangled Type Theory was introduced by Randall Holmes in [3] as a new way of approaching the consistency problem for $\mathrm {NF}$. Although the task of finding models for this theory is far from trivial (considering it is equiconsistent with $\mathrm {NF}$ ), ways of constructing models for certain fragments of it have been discovered. In this article, we present a simpler way of constructing models of predicative Tangled Type Theory and consequently of predicative $\mathrm {NF}$. In these new models (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16.  8
    More on Galois Cohomology, Definability, and Differential Algebraic Groups.Omar León Sánchez, David Meretzky & Anand Pillay - 2024 - Journal of Symbolic Logic 89 (2):496-515.
    As a continuation of the work of the third author in [5], we make further observations on the features of Galois cohomology in the general model theoretic context. We make explicit the connection between forms of definable groups and first cohomology sets with coefficients in a suitable automorphism group. We then use a method of twisting cohomology (inspired by Serre’s algebraic twisting) to describe arbitrary fibres in cohomology sequences—yielding a useful “finiteness” result on cohomology sets.Applied to the special case of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  1
    The Definability of the Extender Sequence From In.Farmer Schlutzenberg - 2024 - Journal of Symbolic Logic 89 (2):427-459.
    Let M be a short extender mouse. We prove that if $E\in M$ and $M\models $ “E is a countably complete short extender whose support is a cardinal $\theta $ and $\mathcal {H}_\theta \subseteq \mathrm {Ult}(V,E)$ ”, then E is in the extender sequence $\mathbb {E}^M$ of M. We also prove other related facts, and use them to establish that if $\kappa $ is an uncountable cardinal of M and $\kappa ^{+M}$ exists in M then $(\mathcal {H}_{\kappa ^+})^M$ satisfies the (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18.  6
    On the Cofinality of the Least -Strongly Compact Cardinal.Y. O. U. Zhixing & Jiachen Yuan - 2024 - Journal of Symbolic Logic 89 (2):569-582.
    In this paper, we characterize the possible cofinalities of the least $\lambda $ -strongly compact cardinal. We show that, on the one hand, for any regular cardinal, $\delta $, that carries a $\lambda $ -complete uniform ultrafilter, it is consistent, relative to the existence of a supercompact cardinal above $\delta $, that the least $\lambda $ -strongly compact cardinal has cofinality $\delta $. On the other hand, provably the cofinality of the least $\lambda $ -strongly compact cardinal always carries a (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19. Polyhedral Completeness of Intermediate Logics: The Nerve Criterion.Sam Adam-day, Nick Bezhanishvili, David Gabelaia & Vincenzo Marra - 2024 - Journal of Symbolic Logic 89 (1):342-382.
    We investigate a recently devised polyhedral semantics for intermediate logics, in which formulas are interpreted in n-dimensional polyhedra. An intermediate logic is polyhedrally complete if it is complete with respect to some class of polyhedra. The first main result of this paper is a necessary and sufficient condition for the polyhedral completeness of a logic. This condition, which we call the Nerve Criterion, is expressed in terms of Alexandrov’s notion of the nerve of a poset. It affords a purely combinatorial (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  20.  22
    Maximality of Logic Without Identity.Guillermo Badia, Xavier Caicedo & Carles Noguera - 2024 - Journal of Symbolic Logic 89 (1):147-162.
    Lindström’s theorem obviously fails as a characterization of first-order logic without identity ( $\mathcal {L}_{\omega \omega }^{-} $ ). In this note, we provide a fix: we show that $\mathcal {L}_{\omega \omega }^{-} $ is a maximal abstract logic satisfying a weak form of the isomorphism property (suitable for identity-free languages and studied in [11]), the Löwenheim–Skolem property, and compactness. Furthermore, we show that compactness can be replaced by being recursively enumerable for validity under certain conditions. In the proofs, we (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  21.  17
    Stationary Reflection and the Failure of the Sch.Omer Ben-Neria, Yair Hayut & Spencer Unger - 2024 - Journal of Symbolic Logic 89 (1):1-26.
    In this paper we prove that from large cardinals it is consistent that there is a singular strong limit cardinal $\nu $ such that the singular cardinal hypothesis fails at $\nu $ and every collection of fewer than $\operatorname {\mathrm {cf}}(\nu )$ stationary subsets of $\nu ^{+}$ reflects simultaneously. For $\operatorname {\mathrm {cf}}(\nu )> \omega $, this situation was not previously known to be consistent. Using different methods, we reduce the upper bound on the consistency strength of this situation for (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  19
    Euclidean Numbers and Numerosities.Vieri Benci & Lorenzo Luperi Baglini - 2024 - Journal of Symbolic Logic 89 (1):112-146.
    Several different versions of the theory of numerosities have been introduced in the literature. Here, we unify these approaches in a consistent frame through the notion of set of labels, relating numerosities with the Kiesler field of Euclidean numbers. This approach allows us to easily introduce, by means of numerosities, ordinals and their natural operations, as well as the Lebesgue measure as a counting measure on the reals.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  8
    The Baire Closure and its Logic.G. Bezhanishvili & D. Fernández-Duque - 2024 - Journal of Symbolic Logic 89 (1):27-49.
    The Baire algebra of a topological space X is the quotient of the algebra of all subsets of X modulo the meager sets. We show that this Boolean algebra can be endowed with a natural closure operator, resulting in a closure algebra which we denote $\mathbf {Baire}(X)$. We identify the modal logic of such algebras to be the well-known system $\mathsf {S5}$, and prove soundness and strong completeness for the cases where X is crowded and either completely metrizable and continuum-sized (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  13
    -Ultrafilters in the Rational Perfect Set Model.Jonathan Cancino-manríquez - 2024 - Journal of Symbolic Logic 89 (1):175-194.
    We give a new characterization of the cardinal invariant $\mathfrak {d}$ as the minimal cardinality of a family $\mathcal {D}$ of tall summable ideals such that an ultrafilter is rapid if and only if it has non-empty intersection with all the ideals in the family $\mathcal {D}$. On the other hand, we prove that in the Miller model, given any family $\mathcal {D}$ of analytic tall p-ideals such that $\vert \mathcal {D}\vert <\mathfrak {d}$, there is an ultrafilter $\mathcal {U}$ which (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  25.  10
    Note on Implying.Sean Cody - 2024 - Journal of Symbolic Logic 89 (1):211-217.
    A short core model induction proof of $\mathsf {AD}^{L(\mathbb {R})}$ from $\mathsf {TD} + \mathsf {DC}_{\mathbb {R}}$.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  26.  19
    (Extra)Ordinary Equivalences with the Ascending/Descending Sequence Principle.Marta Fiori-Carones, Alberto Marcone, Paul Shafer & Giovanni Soldà - 2024 - Journal of Symbolic Logic 89 (1):262-307.
    We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  27.  19
    The Simplest Low Linear Order with No Computable Copies.Andrey Frolov & Maxim Zubkov - 2024 - Journal of Symbolic Logic 89 (1):97-111.
    A low linear order with no computable copy constructed by C. Jockusch and R. Soare has Hausdorff rank equal to $2$. In this regard, the question arises, how simple can be a low linear order with no computable copy from the point of view of the linear order type? The main result of this work is an example of a low strong $\eta $ -representation with no computable copy that is the simplest possible example.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  28.  41
    Classical Determinate Truth I.Kentaro Fujimoto & Volker Halbach - 2024 - Journal of Symbolic Logic 89 (1):218-261.
    We introduce and analyze a new axiomatic theory $\mathsf {CD}$ of truth. The primitive truth predicate can be applied to sentences containing the truth predicate. The theory is thoroughly classical in the sense that $\mathsf {CD}$ is not only formulated in classical logic, but that the axiomatized notion of truth itself is classical: The truth predicate commutes with all quantifiers and connectives, and thus the theory proves that there are no truth value gaps or gluts. To avoid inconsistency, the instances (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29.  7
    On Model-Theoretic Connected Groups.Jakub Gismatullin - 2024 - Journal of Symbolic Logic 89 (1):50-79.
    We introduce and study the model-theoretic notions of absolute connectedness and type-absolute connectedness for groups. We prove that groups of rational points of split semisimple linear groups (that is, Chevalley groups) over arbitrary infinite fields are absolutely connected and characterize connected Lie groups which are type-absolutely connected. We prove that the class of type-absolutely connected group is exactly the class of discretely topologized groups with the trivial Bohr compactification, that is, the class of minimally almost periodic groups.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30.  18
    Usuba’s Principle Can Fail at Singular Cardinals.Mohammad Golshani & Saharon Shelah - 2024 - Journal of Symbolic Logic 89 (1):195-203.
    We answer a question of Usuba by showing that the combinatorial principle $\mathrm {UB}_\lambda $ can fail at a singular cardinal. Furthermore, $\lambda $ can be taken to be $\aleph _\omega.$.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  31.  20
    Completeness of the Gödel–Löb Provability Logic for the Filter Sequence of Normal Measures.Mohammad Golshani & Reihane Zoghifard - 2024 - Journal of Symbolic Logic 89 (1):163-174.
    Assuming the existence of suitable large cardinals, we show it is consistent that the Provability logic $\mathbf {GL}$ is complete with respect to the filter sequence of normal measures. This result answers a question of Andreas Blass from 1990 and a related question of Beklemishev and Joosten.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  32.  21
    Stability Results Assuming Tameness, Monster Model, and Continuity of Nonsplitting.Samson Leung - 2024 - Journal of Symbolic Logic 89 (1):383-425.
    Assuming the existence of a monster model, tameness, and continuity of nonsplitting in an abstract elementary class (AEC), we extend known superstability results: let $\mu>\operatorname {LS}(\mathbf {K})$ be a regular stability cardinal and let $\chi $ be the local character of $\mu $ -nonsplitting. The following holds: 1.When $\mu $ -nonforking is restricted to $(\mu,\geq \chi )$ -limit models ordered by universal extensions, it enjoys invariance, monotonicity, uniqueness, existence, extension, and continuity. It also has local character $\chi $. This generalizes (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  33.  18
    The Turing Degrees and Keisler’s Order.Maryanthe Malliaris & Saharon Shelah - 2024 - Journal of Symbolic Logic 89 (1):331-341.
    There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  34.  35
    The first-order logic of CZF is intuitionistic first-order logic.Robert Passmann - 2024 - Journal of Symbolic Logic 89 (1):308-330.
    We prove that the first-order logic of CZF is intuitionistic first-order logic. To do so, we introduce a new model of transfinite computation (Set Register Machines) and combine the resulting notion of realisability with Beth semantics. On the way, we also show that the propositional admissible rules of CZF are exactly those of intuitionistic propositional logic.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35.  16
    A Generalized Cantor Theorem In.Yinhe Peng & Guozhen Shen - 2024 - Journal of Symbolic Logic 89 (1):204-210.
    It is proved in $\mathsf {ZF}$ (without the axiom of choice) that, for all infinite sets M, there are no surjections from $\omega \times M$ onto $\operatorname {\mathrm {\mathscr {P}}}(M)$.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  36.  53
    An Incompleteness Theorem Via Ordinal Analysis.James Walsh - 2024 - Journal of Symbolic Logic 89 (1):80-96.
    We present an analogue of Gödel’s second incompleteness theorem for systems of second-order arithmetic. Whereas Gödel showed that sufficiently strong theories that are $\Pi ^0_1$ -sound and $\Sigma ^0_1$ -definable do not prove their own $\Pi ^0_1$ -soundness, we prove that sufficiently strong theories that are $\Pi ^1_1$ -sound and $\Sigma ^1_1$ -definable do not prove their own $\Pi ^1_1$ -soundness. Our proof does not involve the construction of a self-referential sentence but rather relies on ordinal analysis.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
 Previous issues
  
Next issues