Authors:Sylvy Anscombe; Franziska Jahnke Pages: 872 - 895 Abstract: Publication date: September 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 9 Author(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.

Authors:Alex Kruckman; Nicholas Ramsey Pages: 755 - 774 Abstract: Publication date: August 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 8 Author(s): Alex Kruckman, Nicholas Ramsey We study expansions of NSOP 1 theories that preserve NSOP 1 . We prove that if T is a model complete NSOP 1 theory eliminating the quantifier ∃ ∞ , then the generic expansion of T by arbitrary constant, function, and relation symbols is still NSOP 1 . We give a detailed analysis of the special case of the theory of the generic L-structure, the model companion of the empty theory in an arbitrary language L. Under the same hypotheses, we show that T may be generically expanded to an NSOP 1 theory with built-in Skolem functions. In order to obtain these results, we establish strengthenings of several properties of Kim-independence in NSOP 1 theories, adding instances of algebraic independence to their conclusions.

Authors:Daniel Palacín; Saharon Shelah Pages: 835 - 849 Abstract: Publication date: August 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 8 Author(s): Daniel Palacín, Saharon Shelah A new notion of independence relation is given and associated to it, the class of flat theories, a subclass of strong stable theories including the superstable ones is introduced. More precisely, after introducing this independence relation, flat theories are defined as an appropriate version of superstability. It is shown that in a flat theory every type has finite weight and therefore flat theories are strong. Furthermore, it is shown that under reasonable conditions any type is non-orthogonal to a regular one. Concerning groups in flat theories, it is shown that type-definable groups behave like superstable ones, since they satisfy the same chain condition on definable subgroups and also admit a normal series of definable subgroup with semi-regular quotients.

Authors:Guohua Wu; Maxim Zubkov Pages: 467 - 486 Abstract: Publication date: June 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 6 Author(s): Guohua Wu, Maxim Zubkov In this paper, we prove Kierstead's conjecture for linear orders whose order types are ∑ q ∈ Q F ( q ) , where F is an extended 0′-limitwise monotonic function, i.e. F can take value ζ. Linear orders in our consideration can have finite and infinite blocks simultaneously, and in this sense our result subsumes a recent result of C. Harris, K. Lee and S.B. Cooper, where only those linear orders with finite blocks are considered. Our result also covers one case of R. Downey and M. Moses' work, i.e. ζ ⋅ η . It covers some instances not being considered in both previous works mentioned above, such as m ⋅ η + ζ ⋅ η + n ⋅ η , for example, where m , n > 0 .

Authors:Saeideh Bahrami; Ali Enayat Pages: 487 - 513 Abstract: Publication date: June 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 6 Author(s): Saeideh Bahrami, Ali Enayat We investigate the structure of fixed point sets of self-embeddings of models of arithmetic. Our principal results are Theorems A, B, and C below. In what follows M is a countable nonstandard model of the fragment I Σ 1 of PA (Peano Arithmetic); N is the initial segment of M consisting of standard numbers of M ; I fix ( j ) is the longest initial segment of fixed points of j; Fix ( j ) is the fixed point set of j; K 1 ( M ) consists of Σ 1 -definable elements of M ; and a self-embedding j of M is said to be a proper initial self-embedding if j ( M ) is a proper initial segment of M . Theorem A The following are equivalent for a proper initial segment I of M : (1) I = I fix ( j ) for some self-embedding j of M . (2) I is closed under exponentiation. (3) I = I fix ( j ) for some proper initial self-embedding j of M . Theorem B The following are equivalent for a proper initial segment I of M : (1) I = Fix ( j ) for some self-embedding j of M . (2) I is a strong cut of M and I ≺ Σ 1 M . (3) I = Fix ( j ) for some proper initial self-embedding j of M . Theorem C PubDate: 2018-04-15T07:23:22Z DOI: 10.1016/j.apal.2018.01.004

Authors:Alexei G. Myasnikov; Francis Oger; Mahmood Sohrabi Pages: 514 - 522 Abstract: Publication date: June 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 6 Author(s): Alexei G. Myasnikov, Francis Oger, Mahmood Sohrabi We give algebraic characterizations of elementary equivalence between rings with finitely generated additive groups. They are similar to those previously obtained for finitely generated nilpotent groups. Here, the rings are not supposed associative, commutative or unitary.

Authors:Olga Kharlampovich; Alexei Myasnikov Pages: 523 - 547 Abstract: Publication date: June 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 6 Author(s): Olga Kharlampovich, Alexei Myasnikov We describe solutions to the problem of elementary classification in the class of group algebras of free groups. We will show that unlike free groups, two group algebras of free groups over infinite fields are elementarily equivalent if and only if the groups are isomorphic and the fields are equivalent in the weak second order logic. We will show that the set of all free bases of a free group F is 0-definable in the group algebra K ( F ) when K is an infinite field, the set of geodesics is definable, and many geometric properties of F are definable in K ( F ) . Therefore K ( F ) “knows” some very important information about F. We will show that similar results hold for group algebras of limit groups.

Authors:Sy-David Friedman; Radek Honzik; Šárka Stejskalová Pages: 548 - 564 Abstract: Publication date: June 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 6 Author(s): Sy-David Friedman, Radek Honzik, Šárka Stejskalová Starting from a Laver-indestructible supercompact κ and a weakly compact λ above κ, we show there is a forcing extension where κ is a strong limit singular cardinal with cofinality ω, 2 κ = κ + 3 = λ + , and the tree property holds at κ + + = λ . Next we generalize this result to an arbitrary cardinal μ such that κ < cf ( μ ) and λ + ≤ μ . This result provides more information about possible relationships between the tree property and the continuum function.

Authors:Liming Cai; Jainer Chen; Rod Downey; Mike Fellows Pages: 463 - 465 Abstract: Publication date: May 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 5 Author(s): Liming Cai, Jainer Chen, Rod Downey, Mike Fellows

Authors:Tamar Lando Pages: 277 - 311 Abstract: Publication date: Available online 3 January 2018 Source:Annals of Pure and Applied Logic Author(s): Tamar Lando Space, as we typically represent it in mathematics and physics, is composed of dimensionless, indivisible points. On an alternative, region-based approach to space, extended regions together with the relations of ‘parthood’ and ‘contact’ are taken as primitive; points are represented as mathematical abstractions from regions. Region-based theories of space have been traditionally modeled in regular closed (or regular open) algebras, in work that goes back to [5] and [20]. More recently, formal logics for region-based theories of space were developed in, e.g., [3] and [18]. It was shown that these logics have both a nice topological and relational semantics, and that the minimal logic for contact algebras, L m i n c o n t (defined below), is complete for both. The present paper explores the question of completeness of L m i n c o n t and its extensions for individual topological spaces of interest: the real line, Cantor space, the rationals, and the infinite binary tree. A second aim is to study a different, algebraic model of logics for region-based theories of space, based on the Lebesgue measure algebra (or algebra of Borel subsets of the real line modulo sets of Lebesgue measure zero). As a model for point-free space, the algebra was first discussed in [2]. The main results of the paper are that L m i n c o n t is weakly complete for any zero-dimensional, dense-in-itself metric space (including, e.g., Cantor space and the rationals); the extension L m i n c o n t + ( C o n ) is weakly complete for the real line and the Lebesgue measure contact algebra. We also prove that the logic L m i n c o n t + ( U n i v ) is weakly complete for the infinite binary tree.

Abstract: Publication date: Available online 19 June 2018 Source:Annals of Pure and Applied Logic Author(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.

Authors:Martin Abstract: Publication date: September 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 9 Author(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.

Authors:Brian Davey; Jane Pitkethly Ross Willard Abstract: Publication date: July 2018 Source:Annals of Pure and Applied Logic, Volume 169, Issue 7 Author(s): Brian A. Davey, Jane G. Pitkethly, Ross Willard We study different full dualities based on the same finite algebra. Our main theorem gives conditions on two different alter egos of a finite algebra under which, if one yields a full duality, then the other does too. We use this theorem to obtain a better understanding of several important examples from the theory of natural dualities. We also clarify what it means for two full dualities based on the same finite algebra to be different. Throughout the paper, a fundamental role is played by the universal Horn theory of the dual categories.

Authors:Saeed Salehi; Payam Seraji Abstract: Publication date: Available online 29 May 2018 Source:Annals of Pure and Applied Logic Author(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.

Authors:John Krueger Abstract: Publication date: Available online 29 May 2018 Source:Annals of Pure and Applied Logic Author(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.

Authors:Shokoofeh Ghorbani Abstract: Publication date: Available online 16 May 2018 Source:Annals of Pure and Applied Logic Author(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.

Authors:M. Giraudet; G. Leloup; F. Lucas Abstract: Publication date: Available online 26 April 2018 Source:Annals of Pure and Applied Logic Author(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.

Authors:Vladimir Kanovei; Vassily Lyubetsky Abstract: Publication date: Available online 24 April 2018 Source:Annals of Pure and Applied Logic Author(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 Π n 1 -set of reals, which is a E 0 -equivalence class, hence a countable set, and which does not contain any OD element, while every non-empty countable Σ n 1 -set of reals is constructible, hence contains only OD reals.

Authors:Rod Downey; Keng Meng Ng Abstract: Publication date: Available online 17 April 2018 Source:Annals of Pure and Applied Logic Author(s): Rod Downey, Keng Meng Ng We investigate the extent to which a c.e. degree can be split into two smaller c.e. degrees which are computationally weak. In contrast to a result of Bickford and Mills that 0 ′ can be split into two superlow c.e. degrees, we construct a SJT-hard c.e. degree which is not the join of two superlow c.e. degrees. We also prove that every high c.e. degree is the join of two array computable c.e. degrees, and that not every high2 c.e. degree can be split in this way. Finally we extend a result of Downey, Jockusch and Stob by showing that no totally ω-c.a. wtt-degree can be cupped to the complete wtt-degree.

Authors:Peter Holy; Regula Krapf; Philipp Schlicht Abstract: Publication date: Available online 10 April 2018 Source:Annals of Pure and Applied Logic Author(s): Peter Holy, Regula Krapf, Philipp Schlicht It is well known that pretameness implies the forcing theorem, and that pretameness is characterized by the preservation of the axioms of ZF − , that is ZF without the power set axiom, or equivalently, by the preservation of the axiom scheme of replacement, for class forcing over models of ZF . We show that pretameness in fact has various other characterizations, for instance in terms of the forcing theorem, the preservation of the axiom scheme of separation, the forcing equivalence of partial orders and their dense suborders, and the existence of nice names for sets of ordinals. These results show that pretameness is a strong dividing line between well and badly behaved notions of class forcing, and that it is exactly the right notion to consider in applications of class forcing. Furthermore, for most properties under consideration, we also present a corresponding characterization of the Ord-chain condition.

Authors:Silvio Ghilardi; Alessandro Gianola Abstract: Publication date: Available online 4 April 2018 Source:Annals of Pure and Applied Logic Author(s): Silvio Ghilardi, Alessandro Gianola Wolter in [38] proved that the Craig interpolation property transfers to fusion of normal modal logics. It is well-known [21] that for such logics Craig interpolation corresponds to an algebraic property called superamalgamability. In this paper, we develop model-theoretic techniques at the level of first-order theories in order to obtain general combination results transferring quantifier-free interpolation to unions of theories over non-disjoint signatures. Such results, once applied to equational theories sharing a common Boolean reduct, can be used to prove that superamalgamability is modular also in the non-normal case. We also state that, in this non-normal context, superamalgamability corresponds to a strong form of interpolation that we call “comprehensive interpolation property” (which consequently transfers to fusions).

Authors:Saharon Shelah; Sebastien Vasey Abstract: Publication date: Available online 2 April 2018 Source:Annals of Pure and Applied Logic Author(s): Saharon Shelah, Sebastien Vasey We study abstract elementary classes (AECs) that, in ℵ 0 , have amalgamation, joint embedding, no maximal models and are stable (in terms of the number of orbital types). Assuming a locality property for types, we prove that such classes exhibit superstable-like behavior at ℵ 0 . More precisely, there is a superlimit model of cardinality ℵ 0 and the class generated by this superlimit has a type-full good ℵ 0 -frame (a local notion of nonforking independence) and a superlimit model of cardinality ℵ 1 . We also give a supersimplicity condition under which the locality hypothesis follows from the rest.

Authors:Levon Haykazyan; Rahim Moosa Abstract: Publication date: Available online 30 March 2018 Source:Annals of Pure and Applied Logic Author(s): Levon Haykazyan, Rahim Moosa The correspondence between definable connected groupoids in a theory T and internal generalised imaginary sorts of T, established by Hrushovski in [“Groupoids, imaginaries and internal covers,” Turkish Journal of Mathematics, 2012], is here extended in two ways: First, it is shown that the correspondence is in fact an equivalence of categories, with respect to appropriate notions of morphism. Secondly, the equivalence of categories is shown to vary uniformly in definable families, with respect to an appropriate relativisation of these categories. Some elaborations on Hrushovki's original constructions are also included.

Authors:Beke Abstract: Publication date: Available online 13 March 2018 Source:Annals of Pure and Applied Logic Author(s): T. Beke, J. Rosický We introduce the notion of λ-equivalence and λ-embeddings of objects in suitable categories. This notion specializes to L ∞ λ -equivalence and L ∞ λ -elementary embedding for categories of structures in a language of arity less than λ, and interacts well with functors and λ-directed colimits. We recover and extend results of Feferman and Eklof on “local functors” without fixing a language in advance. This is convenient for formalizing Lefschetz's principle in algebraic geometry, which was one of the main applications of the work of Eklof.

Authors:Alexander C. Block; Benedikt Löwe Abstract: Publication date: Available online 13 March 2018 Source:Annals of Pure and Applied Logic Author(s): Alexander C. Block, Benedikt Löwe Assuming AD + DC , the hierarchy of norms is a wellordered structure of equivalence classes of ordinal-valued maps. We define operations on the hierarchy of norms, in particular an operation that dominates multiplication as an operation on the ranks of norms, and use these operations to establish a considerably improved lower bound for the length of the hierarchy of norms.

Authors:Aaron Stump Abstract: Publication date: Available online 13 March 2018 Source:Annals of Pure and Applied Logic Author(s): Aaron Stump In this paper, it is shown that induction is derivable in a type-assignment formulation of the second-order dependent type theory λ P 2 , extended with the implicit product type of Miquel, dependent intersection type of Kopylov, and a built-in equality type. The crucial idea is to use dependent intersections to internalize a result of Leivant's showing that Church-encoded data may be seen as realizing their own type correctness statements, under the Curry–Howard isomorphism.

Authors:F. Mwesigye; J.K. Truss Abstract: Publication date: Available online 9 March 2018 Source:Annals of Pure and Applied Logic Author(s): F. Mwesigye, J.K. Truss 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. Ordinals and m-coloured ordinals are studied up to n-equivalence for various values of m and n.

Authors:Joseph S. Miller; Mariya I. Soskova Abstract: Publication date: Available online 8 January 2018 Source:Annals of Pure and Applied Logic Author(s): Joseph S. Miller, Mariya I. Soskova We prove that the cototal enumeration degrees are exactly the enumeration degrees of sets with good approximations, as introduced by Lachlan and Shore [17]. Good approximations have been used as a tool to prove density results in the enumerations degrees, and indeed, we prove that the cototal enumerations degrees are dense.

Authors:Terry Abstract: Publication date: Available online 8 January 2018 Source:Annals of Pure and Applied Logic Author(s): C. Terry Given a finite relational language L , a hereditary L -property is a class of finite L -structures which is closed under isomorphism and model theoretic substructure. This notion encompasses many objects of study in extremal combinatorics, including (but not limited to) hereditary properties of graphs, hypergraphs, and oriented graphs. In this paper, we generalize certain definitions, tools, and results form the study of hereditary properties in combinatorics to the setting of hereditary L -properties, where L is any finite relational language with maximum arity at least two. In particular, the goal of this paper is to generalize how extremal results and stability theorems can be combined with well-known techniques and tools to yield approximate enumeration and structure theorems. We accomplish this by generalizing the notions of extremal graphs, asymptotic density, and graph stability theorems using structures in an auxiliary language associated to a hereditary L -property. Given a hereditary L -property H , we prove an approximate asymptotic enumeration theorem for H in terms of its generalized asymptotic density. Further we prove an approximate structure theorem for H , under the assumption of that H has a stability theorem. The tools we use include a new application of the hypergraph containers theorem (Balogh-Morris-Samotij [14], Saxton-Thomason [38]) to the setting of L -structures, a general supersaturation theorem for hereditary L -properties (also new), and a general graph removal lemma for L -structures proved by Aroskar and Cummings in [5]. Similar results in the setting of multicolored graphs and hypergraphs were recently proved independently by Falgas-Ravry, O'Connel, Strömberg, and Uzzell [21].