Abstract: Publication date: Available online 17 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Vera Koponen We describe all binary simple homogeneous structures M in terms of ∅-definable equivalence relations on M, which “coordinatize” M and control dividing, and extension properties that respect these equivalence relations.

Abstract: Publication date: Available online 16 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Barbara F. Csima, Jonathan Stephenson We first give an example of a rigid structure of computable dimension 2 such that the unique isomorphism between two non-computably isomorphic computable copies has Turing degree strictly below 0″, and not above 0′. This gives a first example of a computable structure with a degree of categoricity that does not belong to an interval of the form [0(α),0(α+1)] for any computable ordinal α. We then extend the technique to produce a rigid structure of computable dimension 3 such that if d0, d1, and d2 are the degrees of isomorphisms between distinct representatives of the three computable equivalence classes, then each di

Abstract: Publication date: Available online 15 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Toshiyasu Arai In this paper we calibrate the strength of the soundness of a set theory KPω+(Π1-Collection) with the assumption that ‘there exists an uncountable regular ordinal’ in terms of the existence of ordinals.

Abstract: Publication date: Available online 14 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Matthias Baaz, Norbert Preining We characterize the recursively enumerable first order Gödel logics with △ with respect to validity and non-satisfiability. The finitely valued and four infinitely valued Gödel logics with △ are recursively enumerable, not-satisfiability is recursively enumerable if validity is recursively enumerable. This is in contrast to first order Gödel logics without △, where validity is recursively enumerable for finitely valued and two infinitely valued Gödel logics, not-satisfiability is recursively enumerable if validity is recursively enumerable or 0 isolated in the truth value set.

Abstract: Publication date: Available online 13 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Gilda Ferreira We present a purely proof-theoretic proof of the existence property for the full intuitionistic first-order predicate calculus, via natural deduction, in which commuting conversions are not needed. Such proof illustrates the potential of an atomic polymorphic system with only three generators of formulas – conditional and first and second-order universal quantifiers – as a tool for proof-theoretical studies.

Abstract: Publication date: Available online 10 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Steve Awodey We construct an algebraic weak factorization system (L,R) on the category of cartesian cubical sets, in which the canonical path object factorization A→AI→A×A, induced by the 1-cube I, is an (L,R)-factorization for any R-object A.

Abstract: Publication date: Available online 8 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Richard Pettigrew In this paper, I describe and motivate a new species of mathematical structuralism, which I call Instrumental Nominalism about Set-Theoretic Structuralism. As the name suggests, this approach takes standard Set-Theoretic Structuralism of the sort championed by Bourbaki, and removes its ontological commitments by taking an instrumental nominalist approach to that ontology of the sort described by Joseph Melia and Gideon Rosen. I argue that this avoids all of the problems that plague other versions of structuralism.

Abstract: Publication date: Available online 8 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Danielle Macbeth For over a century we have been reading Frege's Begriffsschrift notation as a variant of standard notation. But Frege's notation can also be read differently, in a way enabling us to understand how reasoning in Begriffsschrift is at once continuous with and a significant advance beyond earlier mathematical practices of reasoning within systems of signs. It is this second reading that I outline here, beginning with two preliminary claims. First, I show that one does not reason in specially devised systems of signs of mathematics as one reasons in natural language; the signs are not abbreviations of words. Then I argue that even given a system of signs within which to reason in mathematics, there are two ways one can read expressions involving those signs, either mathematically or mechanically. These two lessons are then applied to a reading of Frege's proof of Theorem 133 in Part III of his 1879 logic, a proof that Frege claims is at once strictly deductive and ampliative, a real extension of our knowledge. In closing, I clarify what this might mean, and how it might be possible.

Abstract: Publication date: Available online 8 August 2018Source: Annals of Pure and Applied LogicAuthor(s): Victoria Gitman, Ralf Schindler We introduce the concept of virtual large cardinals and apply it to obtain a hierarchy of new large cardinal notions between ineffable cardinals and 0#. Given a large cardinal notion A characterized by the existence of elementary embeddings j:Vα→Vβ satisfying some list of properties, we say that a cardinal is virtually A if the embeddings j:VαV→VβV exist in the generic multiverse of V. Unlike their ideological cousins generic large cardinals, virtual large cardinals are actual large cardinals that are compatible with V=L. We study virtual versions of extendible, n-huge, and rank-into-rank cardinals and determine where they fit into the large cardinal hierarchy.

Abstract: Publication date: Available online 30 July 2018Source: Annals of Pure and Applied LogicAuthor(s): Damian Sobota We present a general method of constructing Boolean algebras with the Nikodym property and of some given cardinalities. The construction is dependent on the values of some classical cardinal characteristics of the continuum. As a result we obtain a consistent example of an infinite Boolean algebra with the Nikodym property and of cardinality strictly less than the continuum c. It follows that the existence of such an algebra is undecidable by the usual axioms of set theory. Besides, our results shed some new light on the Efimov problem and cofinalities of Boolean algebras.

Abstract: Publication date: Available online 20 July 2018Source: Annals of Pure and Applied LogicAuthor(s): Amitayu Banerjee, Mohamed Khaled Let α≥2 be any ordinal. We consider the class Drsα of relativized diagonal free set algebras of dimension α. With same technique, we prove several important results concerning this class. Among these results, we prove that almost all free algebras of Drsα are atomless, and none of these free algebras contains zero-dimensional elements other than zero and top element. The class Drsα corresponds to first order logic, without equality symbol, with α-many variables and on relativized semantics. Hence, in this variation of first order logic, there is no finitely axiomatizable, complete and consistent theory.

Abstract: Publication date: October 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 10Author(s): Vassilios Gregoriades We are concerned with two separation theorems about analytic sets by Dyck and Preiss, the former involves the positively-defined subsets of the Cantor space and the latter the Borel-convex subsets of finite dimensional Banach spaces. We show by introducing the corresponding separation trees that both of these results admit a constructive proof. This enables us to give the uniform version of these separation theorems, and to derive as corollaries the results, which are analogous to the fundamental fact “HYP is effectively bi-analytic” provided by the Suslin–Kleene Theorem.

Abstract: Publication date: October 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 10Author(s): Mohammad Ardeshir, Mojtaba Mojtahedi In this paper we introduce a modal theory iHσ which is sound and complete for arithmetical Σ1-interpretations in HA, in other words, we will show that iHσ is the Σ1-provability logic of HA. Moreover we will show that iHσ is decidable. As a by-product of these results, we show that HA+□⊥ has de Jongh property.

Abstract: Publication date: October 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 10Author(s): Shokoofeh Ghorbani In this paper, we introduce and study a logic that corresponds to abstract hoop twist-structures and present some results on this logic. We prove the local deductive theorem for this logic and show that this logic is algebraizable with respect to the quasi-variety of abstract hoop twist-structures.

Abstract: Publication date: October 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 10Author(s): Saeed Salehi, Payam Seraji The proofs of Kleene, Chaitin and Boolos for Gödel's First Incompleteness Theorem are studied from the perspectives of constructivity and the Rosser property. A proof of the incompleteness theorem has the Rosser property when the independence of the true but unprovable sentence can be shown by assuming only the (simple) consistency of the theory. It is known that Gödel's own proof for his incompleteness theorem does not have the Rosser property, and we show that neither do Kleene's or Boolos' proofs. However, we show that a variant of Chaitin's proof can have the Rosser property. The proofs of Gödel, Rosser and Kleene are constructive in the sense that they explicitly construct, by algorithmic ways, the independent sentence(s) from the theory. We show that the proofs of Chaitin and Boolos are not constructive, and they prove only the mere existence of the independent sentences.

Abstract: Publication date: October 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 10Author(s): John Krueger We prove the consistency, assuming an ineffable cardinal, of the statement that CH holds and any two normal countably closed ω2-Aronszajn trees are club isomorphic. This work generalizes to higher cardinals the property of Abraham–Shelah [1] that any two normal ω1-Aronszajn trees are club isomorphic, which follows from PFA. The statement that any two normal countably closed ω2-Aronszajn trees are club isomorphic implies that there are no ω2-Suslin trees, so our proof also expands on the method of Laver–Shelah [5] for obtaining the ω2-Suslin hypothesis.

Abstract: Publication date: September 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 9Author(s): Martin Lück In a modular approach, we lift Hilbert-style proof systems for propositional, modal and first-order logic to generalized systems for their respective team-based extensions. We obtain sound and complete axiomatizations for the dependence-free fragment FO(∼) of Väänänen's first-order team logic TL, for propositional team logic PTL, quantified propositional team logic QPTL, modal team logic MTL, and for the corresponding logics of dependence, independence, inclusion and exclusion.As a crucial step in the completeness proof, we show that the above logics admit, in a particular sense, a semantics-preserving elimination of modalities and quantifiers from formulas.

Abstract: Publication date: September 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 9Author(s): M. Giraudet, G. Leloup, F. Lucas By a result known as Rieger's theorem (1956), there is a one-to-one correspondence, assigning to each cyclically ordered group H a pair (G,z) where G is a totally ordered group and z is an element in the center of G, generating a cofinal subgroup 〈z〉 of G, and such that the cyclically ordered quotient group G/〈z〉 is isomorphic to H. We first establish that, in this correspondence, the first-order theory of the cyclically ordered group H is uniquely determined by the first-order theory of the pair (G,z). Then we prove that the class of cyclically orderable groups is an elementary class and give an axiom system for it. Finally we show that, in contrast to the fact that all theories of totally ordered Abelian groups have the same universal part, there are uncountably many universal theories of Abelian cyclically ordered groups.

Abstract: Publication date: September 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 9Author(s): Sylvy Anscombe, Franziska Jahnke We consider four properties of a field K related to the existence of (definable) henselian valuations on K and on elementarily equivalent fields and study the implications between them. Surprisingly, the full pictures look very different in equicharacteristic and mixed characteristic.

Abstract: Publication date: September 2018Source: Annals of Pure and Applied Logic, Volume 169, Issue 9Author(s): Vladimir Kanovei, Vassily Lyubetsky Using a modification of the invariant Jensen forcing of [11], we define a model of ZFC, in which, for a given n≥3, there exists a lightface Πn1-set of reals, which is a E0-equivalence class, hence a countable set, and which does not contain any OD element, while every non-empty countable Σn1-set of reals is constructible, hence contains only OD reals.

Abstract: Publication date: Available online 5 July 2018Source: Annals of Pure and Applied LogicAuthor(s): Paul Potgieter We consider some random series parametrised by Martin-Löf random sequences. The simplest case is that of Rademacher series, independent of a time parameter. This is then extended to the case of Fourier series on the circle with Rademacher coefficients. Finally, a specific Fourier series which has coefficients determined by a computable function is shown to converge to an algorithmically random Brownian motion.

Abstract: Publication date: Available online 21 June 2018Source: Annals of Pure and Applied LogicAuthor(s): A. Alibek, B.S. Baizhanov, B.Sh. Kulpeshov, T.S. Zambarnaya We study Vaught's problem for weakly o-minimal theories of convexity rank 1. We investigate such theories having less than 2ω countable models and prove their binarity. The main result of the paper is a description of the countable spectrum of weakly o-minimal theories of convexity rank 1.

Abstract: Publication date: Available online 19 June 2018Source: Annals of Pure and Applied LogicAuthor(s): Steven Givant, Hajnal Andréka A relation algebra is called measurable when its identity is the sum of measurable atoms, where an atom is called measurable if its square is the sum of functional elements.In this paper we show that atomic measurable relation algebras have rather strong structural properties: they are constructed from systems of groups, coordinated systems of isomorphisms between quotients of the groups, and systems of cosets that are used to “shift” the operation of relative multiplication. An atomic and complete measurable relation algebra is completely representable if and only if there is a stronger coordination between these isomorphisms induced by a scaffold (the shifting cosets are not needed in this case). We also prove that a measurable relation algebra in which the associated groups are all finite is atomic.