Year:

  1. Self-Referential Theories.Samuel A. Alexander - 2020 - Journal of Symbolic Logic 85 (4):1687-1716.
    We study the structure of families of theories in the language of arithmetic extended to allow these families to refer to one another and to themselves. If a theory contains schemata expressing its own truth and expressing a specific Turing index for itself, and contains some other mild axioms, then that theory is untrue. We exhibit some families of true self-referential theories that barely avoid this forbidden pattern.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  2.  5
    The Fundamental Theorem of Central Element Theory.Mariana Vanesa Badano & Diego Jose Vaggione - 2020 - Journal of Symbolic Logic 85 (4):1599-1606.
    We give a short proof of the fundamental theorem of central element theory. The original proof is constructive and very involved and relies strongly on the fact that the class be a variety. Here we give a more direct nonconstructive proof which applies for the more general case of a first-order class which is both closed under the formation of direct products and direct factors.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  1
    Uniform Definability of Integers in Reduced Indecomposable Polynomial Rings.Marco Barone, Nicolás Caro & Eudes Naziazeno - 2020 - Journal of Symbolic Logic 85 (4):1376-1402.
    We prove first-order definability of the prime subring inside polynomial rings, whose coefficient rings are reduced and indecomposable. This is achieved by means of a uniform formula in the language of rings with signature $$. In the characteristic zero case, the claim implies that the full theory is undecidable, for rings of the referred type. This extends a series of results by Raphael Robinson, holding for certain polynomial integral domains, to a more general class.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  2
    Weihrauch Goes Brouwerian.Vasco Brattka & Guido Gherardi - 2020 - Journal of Symbolic Logic 85 (4):1614-1653.
    We prove that the Weihrauch lattice can be transformed into a Brouwer algebra by the consecutive application of two closure operators in the appropriate order: first completion and then parallelization. The closure operator of completion is a new closure operator that we introduce. It transforms any problem into a total problem on the completion of the respective types, where we allow any value outside of the original domain of the problem. This closure operator is of interest by itself, as it (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  2
    Computability, Orders, and Solvable Groups.Arman Darbinyan - 2020 - Journal of Symbolic Logic 85 (4):1588-1598.
    The main objective of this paper is the following two results. There exists a computable bi-orderable group that does not have a computable bi-ordering; there exists a bi-orderable, two-generated computably presented solvable group with undecidable word problem. Both of the groups can be found among two-generated solvable groups of derived length $3$. [a]nswers a question posed by Downey and Kurtz; answers a question posed by Bludov and Glass in Kourovka Notebook.One of the technical tools used to obtain the main results (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  1
    Elementary Equivalence Theorem for Pac Structures.Jan Dobrowolski, Daniel Max Hoffmann & Junguk Lee - 2020 - Journal of Symbolic Logic 85 (4):1467-1498.
    We generalize a well-known theorem binding the elementary equivalence relation on the level of PAC fields and the isomorphism type of their absolute Galois groups. Our results concern two cases: saturated PAC structures and nonsaturated PAC structures.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  3
    Punctual Categoricity and Universality.Rod Downey, Noam Greenberg, Alexander Melnikov, Keng Meng Ng & Daniel Turetsky - 2020 - Journal of Symbolic Logic 85 (4):1427-1466.
    We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is ${\text {PA}}$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is $0''$. We also prove that, with a bit of work, the latter result can be pushed beyond $\Delta ^1_1$, thus showing that punctually categorical structures can (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  3
    Dimension Inequality for a Definably Complete Uniformly Locally o-Minimal Structure of the Second Kind.Masato Fujita - 2020 - Journal of Symbolic Logic 85 (4):1654-1663.
    Consider a definably complete uniformly locally o-minimal expansion of the second kind of a densely linearly ordered abelian group. Let $f:X \rightarrow R^n$ be a definable map, where X is a definable set and R is the universe of the structure. We demonstrate the inequality $\dim ) \leq \dim $ in this paper. As a corollary, we get that the set of the points at which f is discontinuous is of dimension smaller than $\dim $. We also show that the (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9. Cupping and Jump Classes in the Computably Enumerable Degrees.Noam Greenberg, Keng Meng Ng & Guohua Wu - 2020 - Journal of Symbolic Logic 85 (4):1499-1545.
    We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are ${\operatorname {\mathrm {low}}}_3$-cuppable, or indeed ${\operatorname {\mathrm {low}}}_n$ cuppable for any n, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the ${\operatorname {\mathrm {low}}}_2$-cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  1
    Computability of Polish Spaces Up to Homeomorphism.Matthew Harrison-Trainor, Alexander Melnikov & Keng Meng Ng - 2020 - Journal of Symbolic Logic 85 (4):1664-1686.
    We study computable Polish spaces and Polish groups up to homeomorphism. We prove a natural effective analogy of Stone duality, and we also develop an effective definability technique which works up to homeomorphism. As an application, we show that there is a $\Delta ^0_2$ Polish space not homeomorphic to a computable one. We apply our techniques to build, for any computable ordinal $\alpha $, an effectively closed set not homeomorphic to any $0^{}$-computable Polish space; this answers a question of Nies. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  1
    The Kim–Pillay Theorem for Abstract Elementary Categories.Mark Kamsma - 2020 - Journal of Symbolic Logic 85 (4):1717-1741.
    We introduce the framework of AECats, generalizing both the category of models of some first-order theory and the category of subsets of models. Any AEC and any compact abstract theory forms an AECat. In particular, we find applications in positive logic and continuous logic: the category of models of a positive or continuous theory is an AECat. The Kim–Pillay theorem for first-order logic characterizes simple theories by the properties dividing independence has. We prove a version of the Kim–Pillay theorem for (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  1
    Lifschitz Realizability as a Topological Construction.Michael Rathjen & Andrew W. Swan - 2020 - Journal of Symbolic Logic 85 (4):1342-1375.
    We develop a number of variants of Lifschitz realizability for $\mathbf {CZF}$ by building topological models internally in certain realizability models. We use this to show some interesting metamathematical results about constructive set theory with variants of the lesser limited principle of omniscience including consistency with unique Church’s thesis, consistency with some Brouwerian principles and variants of the numerical existence property.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13.  2
    Around Rubin’s “Theories of Linear Order”.Predrag Tanović, Slavko Moconja & Dejan Ilić - 2020 - Journal of Symbolic Logic 85 (4):1403-1426.
    Let $\mathcal M=$ be a linearly ordered first-order structure and T its complete theory. We investigate conditions for T that could guarantee that $\mathcal M$ is not much more complex than some colored orders. Motivated by Rubin’s work [5], we label three conditions expressing properties of types of T and/or automorphisms of models of T. We prove several results which indicate the “geometric” simplicity of definable sets in models of theories satisfying these conditions. For example, we prove that the strongest (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  1
    Multidimensional Exact Classes, Smooth Approximation and Bounded 4-Types.Daniel Wolf - 2020 - Journal of Symbolic Logic 85 (4):1305-1341.
    In connection with the work of Anscombe, Macpherson, Steinhorn and the present author in [1] we investigate the notion of a multidimensional exact class, a special kind of multidimensional asymptotic class with measuring functions that yield the exact sizes of definable sets, not just approximations. We use results about smooth approximation [24] and Lie coordinatization [13] to prove the following result, as conjectured by Macpherson: For any countable language $\mathcal {L}$ and any positive integer d the class $\mathcal {C}$ of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15. A Metric Version of Schlichting’s Theorem.Itaï Ben Yaacov & Frank O. Wagner - 2020 - Journal of Symbolic Logic 85 (4):1607-1613.
    If ${\mathfrak {F}}$ is a type-definable family of commensurable subsets, subgroups or subvector spaces in a metric structure, then there is an invariant subset, subgroup or subvector space commensurable with ${\mathfrak {F}}$. This in particular applies to type-definable or hyper-definable objects in a classical first-order structure.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16.  3
    A Schematic Definition of Quantum Polynomial Time Computability.Tomoyuki Yamakami - 2020 - Journal of Symbolic Logic 85 (4):1546-1587.
    In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper seeks the third model, which is a quantum analogue of the schematic definition of recursive functions. For quantum functions mapping finite-dimensional Hilbert spaces to themselves, we present such a schematic definition, composed of a small set of initial quantum functions and a few construction rules that dictate how to build a new quantum function from (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  5
    Games and Reflection In.J. P. Aguilera - 2020 - Journal of Symbolic Logic 85 (3):1102-1123.
    We characterize the determinacy of $F_\sigma $ games of length $\omega ^2$ in terms of determinacy assertions for short games. Specifically, we show that $F_\sigma $ games of length $\omega ^2$ are determined if, and only if, there is a transitive model of ${\mathsf {KP}}+{\mathsf {AD}}$ containing $\mathbb {R}$ and reflecting $\Pi _1$ facts about the next admissible set.As a consequence, one obtains that, over the base theory ${\mathsf {KP}} + {\mathsf {DC}} + ``\mathbb {R}$ exists,” determinacy for $F_\sigma $ (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18.  9
    Provably Games.J. P. Aguilera & D. W. Blue - 2020 - Journal of Symbolic Logic 85 (3):1124-1146.
    We isolate two abstract determinacy theorems for games of length $\omega_1$ from work of Neeman and use them to conclude, from large-cardinal assumptions and an iterability hypothesis in the region of measurable Woodin cardinals thatif the Continuum Hypothesis holds, then all games of length $\omega_1$ which are provably $\Delta_1$ -definable from a universally Baire parameter are determined;all games of length $\omega_1$ with payoff constructible relative to the play are determined; andif the Continuum Hypothesis holds, then there is a model of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  4
    The Complexity of Scott Sentences of Scattered Linear Orders.Rachael Alvir & Dino Rossegger - 2020 - Journal of Symbolic Logic 85 (3):1079-1101.
    We calculate the complexity of Scott sentences of scattered linear orders. Given a countable scattered linear order L of Hausdorff rank $\alpha $ we show that it has a ${d\text {-}\Sigma _{2\alpha +1}}$ Scott sentence. It follows from results of Ash [2] that for every countable $\alpha $ there is a linear order whose optimal Scott sentence has this complexity. Therefore, our bounds are tight. We furthermore show that every Hausdorff rank 1 linear order has an optimal ${\Pi ^{\mathrm {c}}_{3}}$ (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20.  4
    A Simplified Ordinal Analysis of First-Order Reflection.Toshiyasu Arai - 2020 - Journal of Symbolic Logic 85 (3):1163-1185.
    In this note we give a simplified ordinal analysis of first-order reflection. An ordinal notation system $OT$ is introduced based on $\psi $ -functions. Provable $\Sigma _{1}$ -sentences on $L_{\omega _{1}^{CK}}$ are bounded through cut-elimination on operator controlled derivations.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  3
    On the Complexity of Classifying Lebesgue Spaces.Tyler A. Brown, Timothy H. Mcnicholl & Alexander G. Melnikov - 2020 - Journal of Symbolic Logic 85 (3):1254-1288.
    Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  22.  2
    Bases for Functions Beyond the First Baire Class.Raphaël Carroy & Benjamin D. Miller - 2020 - Journal of Symbolic Logic 85 (3):1289-1303.
    We provide a finite basis for the class of Borel functions that are not in the first Baire class, as well as the class of Borel functions that are not $\sigma $ -continuous with closed witnesses.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  8
    Categorical Semantics of Metric Spaces and Continuous Logic.Simon Cho - 2020 - Journal of Symbolic Logic 85 (3):1044-1078.
    Using the category of metric spaces as a template, we develop a metric analogue of the categorical semantics of classical/intuitionistic logic, and show that the natural notion of predicate in this “continuous semantics” is equivalent to the a priori separate notion of predicate in continuous logic, a logic which is independently well-studied by model theorists and which finds various applications. We show this equivalence by exhibiting the real interval $[0,1]$ in the category of metric spaces as a “continuous subobject classifier” (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  4
    Decomposing Functions of Baire Class on Polish Spaces.Longyun Ding, Takayuki Kihara, Brian Semmes & Jiafei Zhao - 2020 - Journal of Symbolic Logic 85 (3):960-971.
    We prove the Decomposability Conjecture for functions of Baire class $2$ from a Polish space to a separable metrizable space. This partially answers an important open problem in descriptive set theory.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  25.  29
    The Logic of Comparative Cardinality.Yifeng Ding, Matthew Harrison-Trainor & Wesley H. Holliday - 2020 - Journal of Symbolic Logic 85 (3):972-1005.
    This paper investigates the principles that one must add to Boolean algebra to capture reasoning not only about intersection, union, and complementation of sets, but also about the relative size of sets. We completely axiomatize such reasoning under the Cantorian definition of relative size in terms of injections.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  26.  9
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  27.  8
    The Exact Strength of the Class Forcing Theorem.Victoria Gitman, Joel David Hamkins, Peter Holy, Philipp Schlicht & Kameryn J. Williams - 2020 - Journal of Symbolic Logic 85 (3):869-905.
    The class forcing theorem, which asserts that every class forcing notion ${\mathbb {P}}$ admits a forcing relation $\Vdash _{\mathbb {P}}$, that is, a relation satisfying the forcing relation recursion—it follows that statements true in the corresponding forcing extensions are forced and forced statements are true—is equivalent over Gödel–Bernays set theory $\text {GBC}$ to the principle of elementary transfinite recursion $\text {ETR}_{\text {Ord}}$ for class recursions of length $\text {Ord}$. It is also equivalent to the existence of truth predicates for the (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  28.  5
    Stationary Reflection.Yair Hayut & Spencer Unger - 2020 - Journal of Symbolic Logic 85 (3):937-959.
    We improve the upper bound for the consistency strength of stationary reflection at successors of singular cardinals.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29.  4
    Searching for an Analogue of Atr0 in the Weihrauch Lattice.Takayuki Kihara, Alberto Marcone & Arno Pauly - 2020 - Journal of Symbolic Logic 85 (3):1006-1043.
    There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30.  10
    A Note on Derivability Conditions.Taishi Kurahashi - 2020 - Journal of Symbolic Logic 85 (3):1224-1253.
    We investigate relationships between versions of derivability conditions for provability predicates. We show several implications and non-implications between the conditions, and we discuss unprovability of consistency statements induced by derivability conditions. First, we classify already known versions of the second incompleteness theorem, and exhibit some new sets of conditions which are sufficient for unprovability of Hilbert–Bernays’ consistency statement. Secondly, we improve Buchholz’s schematic proof of provable $\Sigma_1$ -completeness. Then among other things, we show that Hilbert–Bernays’ conditions and Löb’s conditions are (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  31.  5
    On a Generalized Fraïssé Limit Construction and its Application to the Jiang–Su Algebra.Shuhei Masumoto - 2020 - Journal of Symbolic Logic 85 (3):1186-1223.
    In this paper, we present a version of Fraïssé theory for categories of metric structures. Using this version, we show that every UHF algebra can be recognized as a Fraïssé limit of a class of C*-algebras of matrix-valued continuous functions on cubes with distinguished traces. We also give an alternative proof of the fact that the Jiang–Su algebra is the unique simple monotracial C*-algebra among all the inductive limits of prime dimension drop algebras.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  32.  6
    What the Łukasiewicz Axioms Mean.Daniele Mundici - 2020 - Journal of Symbolic Logic 85 (3):906-917.
    Let $\to $ be a continuous $\protect \operatorname {\mathrm {[0,1]}}$ -valued function defined on the unit square $\protect \operatorname {\mathrm {[0,1]}}^2$, having the following properties: $x\to = y\to $ and $x\to y=1 $ iff $x\leq y$. Let $\neg x=x\to 0$. Then the algebra $W=$ satisfies the time-honored Łukasiewicz axioms of his infinite-valued calculus. Let $x\to _{\text {\tiny \L }}y=\min $ and $\neg _{\text {\tiny \L }}x=x\to _{\text {\tiny \L }} 0 =1-x.$ Then there is precisely one isomorphism $\phi $ of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  33.  3
    Dimensional Groups and Fields.Frank O. Wagner - 2020 - Journal of Symbolic Logic 85 (3):918-936.
    We shall define a general notion of dimension, and study groups and rings whose interpretable sets carry such a dimension. In particular, we deduce chain conditions for groups, definability results for fields and domains, and show that a pseudofinite $\widetilde {\mathfrak M}_c$ -group of finite positive dimension contains a finite-by-abelian subgroup of positive dimension, and a pseudofinite group of dimension 2 contains a soluble subgroup of dimension 2.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  34. On Configurations Concerning Cardinal Characteristics at Regular Cardinals.Omer Ben-Neria & Shimon Garti - 2020 - Journal of Symbolic Logic 85 (2):691-708.
    We study the consistency and consistency strength of various configurations concerning the cardinal characteristics $\mathfrak {s}_\theta, \mathfrak {p}_\theta, \mathfrak {t}_\theta, \mathfrak {g}_\theta, \mathfrak {r}_\theta $ at uncountable regular cardinals $\theta $. Motivated by a theorem of Raghavan–Shelah who proved that $\mathfrak {s}_\theta \leq \mathfrak {b}_\theta $, we explore in the first part of the paper the consistency of inequalities comparing $\mathfrak {s}_\theta $ with $\mathfrak {p}_\theta $ and $\mathfrak {g}_\theta $. In the second part of the paper we study variations (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35.  7
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  36.  1
    First-Order Recognizability in Finite and Pseudofinite Groups.Yves Cornulier & John S. Wilson - 2020 - Journal of Symbolic Logic 85 (2):852-867.
    It is known that there exists a first-order sentence that holds in a finite group if and only if the group is soluble. Here it is shown that the corresponding statements with ‘solubility’ replaced by ‘nilpotence’ and ‘perfectness’, among others, are false.These facts present difficulties for the study of pseudofinite groups. However, a very weak form of Frattini’s theorem on the nilpotence of the Frattini subgroup of a finite group is proved for pseudofinite groups.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  37.  3
    N-Berkeley Cardinals and Weak Extender Models.Raffaella Cutolo - 2020 - Journal of Symbolic Logic 85 (2):809-816.
    For a given inner model N of ZFC, one can consider the relativized version of Berkeley cardinals in the context of ZFC, and ask if there can exist an “N-Berkeley cardinal.” In this article we provide a positive answer to this question. Indeed, under the assumption of a supercompact cardinal $\delta $, we show that there exists a ZFC inner model N such that there is a cardinal which is N-Berkeley, even in a strong sense. Further, the involved model N (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  38.  7
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  39.  1
    How Strong Are Single Fixed Points of Normal Functions?Anton Freund - 2020 - Journal of Symbolic Logic 85 (2):709-732.
    In a recent paper by M. Rathjen and the present author it has been shown that the statement “every normal function has a derivative” is equivalent to $\Pi ^1_1$ -bar induction. The equivalence was proved over $\mathbf {ACA_0}$, for a suitable representation of normal functions in terms of dilators. In the present paper, we show that the statement “every normal function has at least one fixed point” is equivalent to $\Pi ^1_1$ -induction along the natural numbers.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  40.  2
    Computable Linear Orders and Products.Andrey N. Frolov, Steffen Lempp, Keng Meng Ng & Guohua Wu - 2020 - Journal of Symbolic Logic 85 (2):605-623.
    We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$, $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  41.  7
    The Ketonen Order.Gabriel Goldberg - 2020 - Journal of Symbolic Logic 85 (2):585-604.
    We study a partial order on countably complete ultrafilters introduced by Ketonen [2] as a generalization of the Mitchell order. The following are our main results: the order is wellfounded; its linearity is equivalent to the Ultrapower Axiom, a principle introduced in the author’s dissertation [1]; finally, assuming the Ultrapower Axiom, the Ketonen order coincides with Lipschitz reducibility in the sense of generalized descriptive set theory.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42.  3
    On Obdd-Based Algorithms and Proof Systems That Dynamically Change the Order of Variables.Dmitry Itsykson, Alexander Knop, Andrei Romashchenko & Dmitry Sokolov - 2020 - Journal of Symbolic Logic 85 (2):632-670.
    In 2004 Atserias, Kolaitis, and Vardi proposed $\text {OBDD}$ -based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false $\text {OBDD}$ from $\text {OBDD}$ s representing clauses of the initial formula. All $\text {OBDD}$ s in such proofs have the same order of variables. We initiate the study of $\text {OBDD}$ based proof systems that additionally contain a rule that allows changing the order in $\text {OBDD}$ s. At first we consider a proof (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  43.  5
    Deciding Some Maltsev Conditions in Finite Idempotent Algebras.Alexandr Kazda & Matt Valeriote - 2020 - Journal of Symbolic Logic 85 (2):539-562.
    In this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  44.  3
    Coding in Graphs and Linear Orderings.Julia F. Knight, Alexandra A. Soskova & Stefan V. Vatev - 2020 - Journal of Symbolic Logic 85 (2):673-690.
    There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph G (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  45.  4
    The Complexity of Homeomorphism Relations on Some Classes of Compacta.Paweł Krupski & Benjamin Vejnar - 2020 - Journal of Symbolic Logic 85 (2):733-748.
    We prove that the homeomorphism relation between compact spaces can be continuously reduced to the homeomorphism equivalence relation between absolute retracts, which strengthens and simplifies recent results of Chang and Gao, and Cieśla. It follows then that the homeomorphism relation of absolute retracts is Borel bireducible with the universal orbit equivalence relation. We also prove that the homeomorphism relation between regular continua is classifiable by countable structures and hence it is Borel bireducible with the universal orbit equivalence relation of the (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  46.  5
    Homogeneous Structures with Nonuniversal Automorphism Groups.Wiesław Kubiś & Saharon Shelah - 2020 - Journal of Symbolic Logic 85 (2):817-827.
    We present three examples of countable homogeneous structures whose automorphism groups are not universal, namely, fail to contain isomorphic copies of all automorphism groups of their substructures.Our first example is a particular case of a rather general construction on Fraïssé classes, which we call diversification, leading to automorphism groups containing copies of all finite groups. Our second example is a special case of another general construction on Fraïssé classes, the mixed sums, leading to a Fraïssé class with all finite symmetric (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  47.  4
    Equational Theories of Fields.Amador Martin-Pizarro & Martin Ziegler - 2020 - Journal of Symbolic Logic 85 (2):828-851.
    A first-order theory is equational if every definable set is a Boolean combination of instances of equations, that is, of formulae such that the family of finite intersections of instances has the descending chain condition. Equationality is a strengthening of stability. We show the equationality of the theory of proper extensions of algebraically closed fields and of the theory of separably closed fields of arbitrary imperfection degree.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  48.  8
    Interpretability Logics and Generalised Veltman Semantics.Luka Mikec & Mladen Vuković - 2020 - Journal of Symbolic Logic 85 (2):749-772.
    We obtain modal completeness of the interpretability logics IL $\!\!\textsf {P}_{\textsf {0}}$ and ILR w.r.t. generalised Veltman semantics. Our proofs are based on the notion of full labels [2]. We also give shorter proofs of completeness w.r.t. the generalised semantics for many classical interpretability logics. We obtain decidability and finite model property w.r.t. the generalised semantics for IL $\textsf {P}_{\textsf {0}}$ and ILR. Finally, we develop a construction that might be useful for proofs of completeness of extensions of ILW w.r.t. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  49.  2
    The Exponential Diophantine Problem For.Mihai Prunescu - 2020 - Journal of Symbolic Logic 85 (2):671-672.
    We show that the set of natural numbers has an exponential diophantine definition in the rationals. It follows that the corresponding decision problem is undecidable.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  50.  3
    Voiculescu’s Theorem for Nonseparable -Algebras.Andrea Vaccaro - 2020 - Journal of Symbolic Logic 85 (2):624-631.
    We prove that Voiculescu’s noncommutative version of the Weyl-von Neumann Theorem can be extended to all unital, separably representable $\mathrm {C}^\ast $ -algebras whose density character is strictly smaller than the cardinal invariant $\mathfrak {p}$. We show moreover that Voiculescu’s Theorem consistently fails for $\mathrm {C}^\ast $ -algebras of larger density character.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  51.  9
    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   2 citations  
  52.  4
    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  
  53.  12
    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  
  54.  38
    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  
  55.  6
    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  
  56.  7
    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  
  57.  12
    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   3 citations  
  58.  4
    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  
  59.  10
    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  
  60.  9
    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  
  61.  5
    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  
  62.  5
    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  
  63.  4
    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  
  64.  3
    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   1 citation  
  65.  3
    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  
  66.  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  
  67.  3
    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  
  68.  5
    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  
  69.  4
    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  
  70.  7
    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  
  71.  13
    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  
  72.  9
    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  
  73.  15
    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  
  74.  1
    Fσ Games and Reflection in L.J. P. Aguilera - 2020 - Journal of Symbolic Logic:1-22.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
 Previous issues
  
Next issues