Authors:Joan Bagaria; Victoria Gitman; Ralf Schindler Pages: 1 - 20 Abstract: We introduce and study the first-order Generic Vopěnka’s Principle, which states that for every definable proper class of structures \(\mathcal {C}\) of the same type, there exist \(B\ne A\) in \(\mathcal {C}\) such that B elementarily embeds into A in some set-forcing extension. We show that, for \(n\ge 1\) , the Generic Vopěnka’s Principle fragment for \(\Pi _n\) -definable classes is equiconsistent with a proper class of n-remarkable cardinals. The n-remarkable cardinals hierarchy for \(n\in \omega \) , which we introduce here, is a natural generic analogue for the \(C^{(n)}\) -extendible cardinals that Bagaria used to calibrate the strength of the first-order Vopěnka’s Principle in Bagaria (Arch Math Logic 51(3–4):213–240, 2012). Expanding on the theme of studying set theoretic properties which assert the existence of elementary embeddings in some set-forcing extension, we introduce and study the weak Proper Forcing Axiom, \(\mathrm{wPFA}\) . The axiom \(\mathrm{wPFA}\) states that for every transitive model \(\mathcal M\) in the language of set theory with some \(\omega _1\) -many additional relations, if it is forced by a proper forcing \(\mathbb P\) that \(\mathcal M\) satisfies some \(\Sigma _1\) -property, then V has a transitive model \(\bar{\mathcal M}\) , satisfying the same \(\Sigma _1\) -property, and in some set-forcing extension there is an elementary embedding from \(\bar{\mathcal M}\) into \(\mathcal M\) . This is a weakening of a formulation of \(\mathrm{PFA}\) due to Claverie and Schindler (J Symb Logic 77(2):475–498, 2012), which asserts that the embedding from \(\bar{\mathcal M}\) to \(\mathcal M\) exists in V. We show that \(\mathrm{wPFA}\) is equiconsistent with a remarkable cardinal. Furthermore, the axiom \(\mathrm{wPFA}\) implies \(\mathrm{PFA}_{\aleph _2}\) , the Proper Forcing Axiom for antichains of size at most \(\omega _2\) ... PubDate: 2017-02-01 DOI: 10.1007/s00153-016-0511-x Issue No:Vol. 56, No. 1-2 (2017)

Authors:Leonardo M. Cabrer; Luca Spada Pages: 21 - 42 Abstract: We connect the dual adjunction between MV-algebras and Tychonoff spaces with the general theory of natural dualities, and provide a number of applications. In doing so, we simplify the aforementioned construction by observing that there is no need of using presentations of MV-algebras in order to obtain the adjunction. We also provide a description of the dual maps that is intrinsically geometric, and thus avoids the syntactic notion of definable map. Finally, we apply these results to better explain the relation between semisimple tensor products and coproducts of MV-algebras, and we extend beyond the finitely generated case the characterisations of strongly semisimple and polyhedral MV-algebras. PubDate: 2017-02-01 DOI: 10.1007/s00153-016-0512-9 Issue No:Vol. 56, No. 1-2 (2017)

Authors:Assia Mahboubi Pages: 43 - 49 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:Daniel W. Cunningham 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: 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: 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: 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: 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: 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: 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: 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:Somayyeh Tari 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-01-27 DOI: 10.1007/s00153-017-0523-1

Authors:Jianyong Hong; Shuguo Zhang 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:Gregory Igusa; Henry Towsner Abstract: In Ramsey’s Theorem and Recursion Theory, Theorem 4.2, Jockusch proved that for any computable k-coloring of pairs of integers, there is an infinite \(\Pi ^0_2\) homogeneous set. The proof used a countable collection of \(\Pi ^0_2\) sets as potential infinite homogeneous sets. In a remark preceding the proof, Jockusch stated without proof that it can be shown that there is no computable way to prove this result with a finite number of \(\Pi ^0_2\) sets. We provide a proof of this claim, showing that there is no computable way to take an index for an arbitrary computable coloring and produce a finite number of indices of \(\Pi ^0_2\) sets with the property that one of those sets will be homogeneous for that coloring. While proving this result, we introduce n-trains as objects with useful combinatorial properties which can be used as approximations to infinite \(\Pi ^0_2\) sets. PubDate: 2016-12-21 DOI: 10.1007/s00153-016-0519-2

Authors:Xianghui Shi; Nam Trang Abstract: We investigate the compatibility of \(I_0\) with various combinatorial principles at \(\lambda ^+\) , which include the existence of \(\lambda ^+\) -Aronszajn trees, square principles at \(\lambda \) , the existence of good scales at \(\lambda \) , stationary reflections for subsets of \(\lambda ^{+}\) , diamond principles at \(\lambda \) and the singular cardinal hypothesis at \(\lambda \) . We also discuss whether these principles can hold in \(L(V_{\lambda +1})\) . PubDate: 2016-12-10 DOI: 10.1007/s00153-016-0518-3

Authors:Quentin Brouette 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: In this article we provide an intrinsic characterization of the famous Howard–Bachmann ordinal in terms of a natural well-partial-ordering by showing that this ordinal can be realized as a maximal order type of a class of generalized trees with respect to a homeomorphic embeddability relation. We use our calculations to draw some conclusions about some corresponding subsystems of second order arithmetic. All these subsystems deal with versions of light-face \(\varPi ^1_1\) -comprehension. PubDate: 2016-11-05 DOI: 10.1007/s00153-016-0515-6

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

Authors:Emil Jeřábek Abstract: For any sufficiently strong theory of arithmetic, the set of Diophantine equations provably unsolvable in the theory is algorithmically undecidable, as a consequence of the MRDP theorem. In contrast, we show decidability of Diophantine equations provably unsolvable in Robinson’s arithmetic Q. The argument hinges on an analysis of a particular class of equations, hitherto unexplored in Diophantine literature. We also axiomatize the universal fragment of Q in the process. PubDate: 2016-09-22 DOI: 10.1007/s00153-016-0508-5