Authors:Yinhe Peng Pages: 237 - 251 Abstract: Abstract First, we show that every coherent tree that contains a Countryman suborder is \({\mathbb {R}}\) -embeddable when restricted to a club. Then for a linear order O that can not be embedded into \(\omega \) , there exists (consistently) an \({{\mathbb {R}}}\) -embeddable O-ranging coherent tree which is not Countryman. And for a linear order \(O'\) that can not be embedded into \({\mathbb {Z}}\) , there exists (consistently) an \({\mathbb {R}}\) -embeddable \(O'\) -ranging coherent tree which contains no Countryman suborder. Finally, we will see that this is the best we can do. PubDate: 2017-05-01 DOI: 10.1007/s00153-017-0530-2 Issue No:Vol. 56, No. 3-4 (2017)

Authors:Somayyeh Tari Pages: 309 - 317 Abstract: Abstract Let \({\mathcal {M}}=(M,<,+,\cdot ,\ldots )\) be a non-valuational weakly o-minimal expansion of a real closed field \((M,<,+,\cdot )\) . In this paper, we prove that \({\mathcal {M}}\) has a \(C^r\) -strong cell decomposition property, for each positive integer r, a best analogous result from Tanaka and Kawakami (Far East J Math Sci (FJMS) 25(3):417–431, 2007). We also show that curve selection property holds in non-valuational weakly o-minimal expansions of ordered groups. Finally, we extend the notion of definable compactness suitable for weakly o-minimal structures which was examined for definable sets (Peterzil and Steinhorn in J Lond Math Soc 295:769–786, 1999), and prove that a definable set is definably compact if and only if it is closed and bounded. PubDate: 2017-05-01 DOI: 10.1007/s00153-017-0523-1 Issue No:Vol. 56, No. 3-4 (2017)

Authors:Assia Mahboubi Pages: 43 - 49 Abstract: Abstract We give a constructive proof of the open induction principle on real numbers, using bar induction and enumerative open sets. We comment the algorithmic content of this result. PubDate: 2017-02-01 DOI: 10.1007/s00153-016-0513-8 Issue No:Vol. 56, No. 1-2 (2017)

Authors:Mateusz Łełyk; Bartosz Wcisło Abstract: Abstract In the following paper we propose a model-theoretical way of comparing the “strength” of various truth theories which are conservative over \( PA \) . Let \({\mathfrak {Th}}\) denote the class of models of \( PA \) which admit an expansion to a model of theory \({ Th}\) . We show (combining some well known results and original ideas) that $$\begin{aligned} {{\mathfrak {PA}}}\supset {\mathfrak {TB}}\supset {{\mathfrak {RS}}}\supset {\mathfrak {UTB}}\supseteq \mathfrak {CT^-}, \end{aligned}$$ where \({\mathfrak {PA}}\) denotes simply the class of all models of \( PA \) and \({\mathfrak {RS}}\) denotes the class of recursively saturated models of \( PA \) . Our main original result is that every model of \( PA \) which admits an expansion to a model of \( CT ^-\) , admits also an expansion to a model of \( UTB \) . Moreover, as a corollary to one of the results (brought to us by Carlo Nicolai) we conclude that \( UTB \) is not relatively interpretable in \( TB \) , thus answering the question from Fujimoto (Bull Symb Log 16:305–344, 2010). PubDate: 2017-04-22 DOI: 10.1007/s00153-017-0531-1

Authors:Ludovic Patey Abstract: Abstract Every function over the natural numbers has an infinite subdomain on which the function is non-decreasing. Motivated by a question of Dzhafarov and Schweber, we study the reverse mathematics of variants of this statement. It turns out that this statement restricted to computably bounded functions is computationally weak and does not imply the existence of the halting set. On the other hand, we prove that it is not a consequence of Ramsey’s theorem for pairs. This statement can therefore be seen as an arguably natural principle between the arithmetic comprehension axiom and stable Ramsey’s theorem for pairs. PubDate: 2017-04-21 DOI: 10.1007/s00153-017-0536-9

Authors:Tapani Hyttinen; Gianluca Paolini; Jouko Väänänen Abstract: Abstract We use sets of assignments, a.k.a. teams, and measures on them to define probabilities of first-order formulas in given data. We then axiomatise first-order properties of such probabilities and prove a completeness theorem for our axiomatisation. We use the Hardy–Weinberg Principle of biology and the Bell’s Inequalities of quantum physics as examples. PubDate: 2017-04-13 DOI: 10.1007/s00153-017-0535-x

Authors:Burak Kaya Abstract: Abstract In this paper, we analyze the complexity of topological conjugacy of pointed Cantor minimal systems from the point of view of descriptive set theory. We prove that the topological conjugacy relation on pointed Cantor minimal systems is Borel bireducible with the Borel equivalence relation \(\varDelta _{\mathbb {R}}^+\) on \(\mathbb {R}^{{\mathbb {N}}}\) defined by \(x \varDelta _{\mathbb {R}}^+y \Leftrightarrow \{x_i{:}\,i \in {\mathbb {N}}\}=\{y_i{:}\,i \in {\mathbb {N}}\}\) . Moreover, we show that \(\varDelta _{\mathbb {R}}^+\) is a lower bound for the Borel complexity of topological conjugacy of Cantor minimal systems. Finally, we interpret our results in terms of properly ordered Bratteli diagrams and discuss some applications. PubDate: 2017-04-03 DOI: 10.1007/s00153-017-0534-y

Authors:Will Boney; Sebastien Vasey Abstract: We study when a union of saturated models is saturated in the framework of tame abstract elementary classes (AECs) with amalgamation. We prove: Theorem 0.1. If K is a tame AEC with amalgamation satisfying a natural definition of superstability (which follows from categoricity in a high-enough cardinal), then for all high-enough \(\lambda {:}\) The union of an increasing chain of \(\lambda \) -saturated models is \(\lambda \) -saturated. There exists a type-full good \(\lambda \) -frame with underlying class the saturated models of size \(\lambda \) . There exists a unique limit model of size \(\lambda \) . Our proofs use independence calculus and a generalization of averages to this non first-order context. PubDate: 2017-04-03 DOI: 10.1007/s00153-017-0532-0

Authors:Monica M. VanDieren; Sebastien Vasey Abstract: This paper is part of a program initiated by Saharon Shelah to extend the model theory of first order logic to the non-elementary setting of abstract elementary classes (AECs). An abstract elementary class is a semantic generalization of the class of models of a complete first order theory with the elementary substructure relation. We examine the symmetry property of splitting (previously isolated by the first author) in AECs with amalgamation that satisfy a local definition of superstability. The key results are a downward transfer of symmetry and a deduction of symmetry from failure of the order property. These results are then used to prove several structural properties in categorical AECs, improving classical results of Shelah who focused on the special case of categoricity in a successor cardinal. We also study the interaction of symmetry with tameness, a locality property for Galois (orbital) types. We show that superstability and tameness together imply symmetry. This sharpens previous work of Boney and the second author. PubDate: 2017-03-28 DOI: 10.1007/s00153-017-0533-z

Authors:Daniel W. Cunningham Abstract: Abstract Assuming \(\text {ZF}+\text {DC}\) , we prove that if there exists a strong partition cardinal greater than \(\varTheta \) , then (1) there is an inner model of \(\text {ZF}+\text {AD}+\text {DC}+ {{{\mathbb {R}}} }^{{\#}}\) exists, and (2) there is an inner model of \(\text {ZF}+\text {AD}+\text {DC}+ (\exists \kappa >\varTheta )\,(\kappa \) is measurable). Here \(\varTheta \) is the supremum of the ordinals which are the surjective image of the set of reals \({{{\mathbb {R}}} }\) . PubDate: 2017-03-18 DOI: 10.1007/s00153-017-0529-8

Authors:Joël Adler Abstract: Abstract As the class \(\mathcal {PCSL}\) of pseudocomplemented semilattices is a universal Horn class generated by a single finite structure it has a \(\aleph _0\) -categorical model companion \(\mathcal {PCSL}^*\) . As \(\mathcal {PCSL}\) is inductive the models of \(\mathcal {PCSL}^*\) are exactly the existentially closed models of \(\mathcal {PCSL}\) . We will construct the unique existentially closed countable model of \(\mathcal {PCSL}\) as a direct limit of algebraically closed pseudocomplemented semilattices. PubDate: 2017-03-17 DOI: 10.1007/s00153-017-0527-x

Authors:Mohammad Golshani Abstract: Abstract We show that Shelah cardinals are preserved under the canonical \({{\mathrm{GCH}}}\) forcing notion. We also show that if \({{\mathrm{GCH}}}\) holds and \(F:{{\mathrm{REG}}}\rightarrow {{\mathrm{CARD}}}\) is an Easton function which satisfies some weak properties, then there exists a cofinality preserving generic extension of the universe which preserves Shelah cardinals and satisfies \(\forall \kappa \in {{\mathrm{REG}}},~ 2^{\kappa }=F(\kappa )\) . This gives a partial answer to a question asked by Cody (Arch Math Logic 52(5–6):569–591, 2013) and independently by Honzik (Acta Univ Carol 1:55–72, 2015). We also prove an indestructibility result for Shelah cardinals. PubDate: 2017-03-07 DOI: 10.1007/s00153-017-0528-9

Authors:Takashi Sato; Takeshi Yamazaki Abstract: Abstract The theory of countable partially ordered sets (posets) is developed within a weak subsystem of second order arithmetic. We within \(\mathsf {RCA_0}\) give definitions of notions of the countable order theory and present some statements of countable lattices equivalent to arithmetical comprehension axiom over \(\mathsf {RCA_0}\) . Then we within \(\mathsf {RCA_0}\) give proofs of Knaster–Tarski fixed point theorem, Tarski–Kantorovitch fixed point theorem, Bourbaki–Witt fixed point theorem, and Abian–Brown maximal fixed point theorem for countable lattices or posets. We also give Reverse Mathematics results of the fixed point theory of countable posets; Abian–Brown least fixed point theorem, Davis’ converse for countable lattices, Markowski’s converse for countable posets, and arithmetical comprehension axiom are pairwise equivalent over \(\mathsf {RCA_0}\) . Here the converses state that some fixed point properties characterize the completeness of the underlying spaces. PubDate: 2017-02-27 DOI: 10.1007/s00153-017-0526-y

Authors:Saharon Shelah Abstract: Abstract It is well known how to generalize the meagre ideal replacing \(\aleph _0\) by a (regular) cardinal \(\lambda > \aleph _0\) and requiring the ideal to be \(({<}\lambda )\) -complete. But can we generalize the null ideal? In terms of forcing, this means finding a forcing notion similar to the random real forcing, replacing \(\aleph _0\) by \(\lambda \) . So naturally, to call it a generalization we require it to be \(({<}\lambda )\) -complete and \(\lambda ^+\) -c.c. and more. Of course, we would welcome additional properties generalizing the ones of the random real forcing. Returning to the ideal (instead of forcing) we may look at the Boolean Algebra of \(\lambda \) -Borel sets modulo the ideal. Common wisdom have said that there is no such thing because we have no parallel of Lebesgue integral, but here surprisingly first we get a positive \(=\) existence answer for a generalization of the null ideal for a “mild” large cardinal \(\lambda \) —a weakly compact one. Second, we try to show that this together with the meagre ideal (for \(\lambda \) ) behaves as in the countable case. In particular, we consider the classical Cichoń diagram, which compares several cardinal characterizations of those ideals. We shall deal with other cardinals, and with more properties of related forcing notions in subsequent papers (Shelah in The null ideal for uncountable cardinals; Iterations adding no \(\lambda \) -Cohen; Random \(\lambda \) -reals for inaccessible continued; Creature iteration for inaccesibles. Preprint; Bounding forcing with chain conditions for uncountable cardinals) and Cohen and Shelah (On a parallel of random real forcing for inaccessible cardinals. arXiv:1603.08362 [math.LO]) and a joint work with Baumhauer and Goldstern. PubDate: 2017-02-20 DOI: 10.1007/s00153-017-0524-0

Authors:Richard Rast Abstract: Abstract Suppose A is a linear order, possibly with countably many unary predicates added. We classify the isomorphism relation for countable models of \(\text {Th}(A)\) up to Borel bi-reducibility, showing there are exactly five possibilities and characterizing exactly when each can occur in simple model-theoretic terms. We show that if the language is finite (in particular, if there are no unary predicates), then the theory is \(\aleph _0\) -categorical or Borel complete; this generalizes a theorem due to Schirmann (Theories des ordres totaux et relations dequivalence. Master’s thesis, Universite de Paris VII, 1997). PubDate: 2017-02-09 DOI: 10.1007/s00153-017-0525-z

Authors:Yair Hayut Abstract: Abstract In this paper we investigate the consistency and consequences of the downward Löwenheim–Skolem–Tarski theorem for extension of the first order logic by the Magidor–Malitz quantifier. We derive some combinatorial results and improve the known upper bound for the consistency of Chang’s conjecture at successor of singular cardinals. PubDate: 2017-02-06 DOI: 10.1007/s00153-017-0522-2

Authors:Tapani Hyttinen; Vadim Kulikov; Miguel Moreno Abstract: Abstract We study the \(\kappa \) -Borel-reducibility of isomorphism relations of complete first order theories in a countable language and show the consistency of the following: For all such theories T and \(T^{\prime }\) , if T is classifiable and \(T^{\prime }\) is not, then the isomorphism of models of \(T^{\prime }\) is strictly above the isomorphism of models of T with respect to \(\kappa \) -Borel-reducibility. In fact, we can also ensure that a range of equivalence relations modulo various non-stationary ideals are strictly between those isomorphism relations. The isomorphism relations are considered on models of some fixed uncountable cardinality obeying certain restrictions. PubDate: 2017-02-02 DOI: 10.1007/s00153-017-0521-3

Authors:Jianyong Hong; Shuguo Zhang Abstract: Abstract Under CH we show the following results: There is a discrete ultrafilter which is not a \({\mathcal {Z}}_{0}\) -ultrafilter. There is a \(\sigma \) -compact ultrafilter which is not a \({\mathcal {Z}}_{0}\) -ultrafilter. There is a \({\mathcal {J}}_{\omega ^{3}}\) -ultrafilter which is not a \({\mathcal {Z}}_{0}\) -ultrafilter. PubDate: 2016-12-24 DOI: 10.1007/s00153-016-0520-9

Authors:Quentin Brouette Abstract: Abstract We study definable types in the theory of closed ordered differential fields (CODF). We show a condition for a type to be definable, then we prove that definable types are dense in the Stone space of CODF. PubDate: 2016-11-18 DOI: 10.1007/s00153-016-0517-4

Abstract: Abstract When formalizing mathematics in constructive type theories, or more practically in proof assistants such as Coq or Agda, one is often using setoids (types with explicit equivalence relations). In this note we consider two categories of setoids with equality on objects and show, within intensional Martin-Löf type theory, that they are isomorphic. Both categories are constructed from a fixed proof-irrelevant family F of setoids. The objects of the categories form the index setoid I of the family, whereas the definition of arrows differs. The first category has for arrows triples \((a,b,f:F(a)\,\rightarrow \,F(b))\) where f is an extensional function. Two such arrows are identified if appropriate composition with transportation maps (given by F) makes them equal. In the second category the arrows are triples \((a,b,R \hookrightarrow \Sigma (I,F)^2)\) where R is a total functional relation between the subobjects \(F(a), F(b) \hookrightarrow \Sigma (I,F)\) of the setoid sum of the family. This category is simpler to use as the transportation maps disappear. Moreover we also show that the full image of a category along an E-functor into an E-category is a category. PubDate: 2016-11-01 DOI: 10.1007/s00153-016-0514-7