Archive for Mathematical Logic

ISSNs: 0933-5846, 1432-0665

56 found

View year:

  1. Implicit recursion-theoretic characterizations of counting classes.Ugo Dal Lago, Reinhard Kahle & Isabel Oitavem - 2022 - Archive for Mathematical Logic 61 (7):1129-1144.
    We give recursion-theoretic characterizations of the counting class \, the class of those functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Moreover, we characterize in a recursion-theoretic manner all the levels \ of the counting hierarchy of functions \, which result from allowing queries to functions of the previous level, and \ itself as a whole. This is done in the style of Bellantoni and Cook’s safe recursion, and it places \ in (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  2.  1
    Ramsey degrees of ultrafilters, pseudointersection numbers, and the tools of topological Ramsey spaces.Natasha Dobrinen & Sonia Navarro Flores - 2022 - Archive for Mathematical Logic 61 (7):1053-1090.
    This paper investigates properties of \-closed forcings which generate ultrafilters satisfying weak partition relations. The Ramsey degree of an ultrafilter \ for n-tuples, denoted \\), is the smallest number t such that given any \ and coloring \, there is a member \ such that the restriction of c to \ has no more than t colors. Many well-known \-closed forcings are known to generate ultrafilters with finite Ramsey degrees, but finding the precise degrees can sometimes prove elusive or quite (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  3. On decidability of amenability in computable groups.Karol Duda & Aleksander Ivanov - 2022 - Archive for Mathematical Logic 61 (7):891-902.
    The main result of the paper states that there is a finitely presented group G with decidable word problem where detection of finite subsets of G which generate amenable subgroups is not decidable.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  4.  2
    $$\Delta ^0_1$$ variants of the law of excluded middle and related principles.Makoto Fujiwara - 2022 - Archive for Mathematical Logic 61 (7):1113-1127.
    We systematically study the interrelations between all possible variations of \ variants of the law of excluded middle and related principles in the context of intuitionistic arithmetic and analysis.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  5. Δ10\documentclass[12pt]{Minimal} \usepackage{Amsmath} \usepackage{Wasysym} \usepackage{Amsfonts} \usepackage{Amssymb} \usepackage{Amsbsy} \usepackage{Mathrsfs} \usepackage{Upgreek} \setlength{\oddsidemargin}{-69pt} \begin{Document}$$\delta ^0_1$$\end{Document} Variants of the Law of Excluded Middle and Related Principles. [REVIEW]Makoto Fujiwara - 2022 - Archive for Mathematical Logic 61 (7-8):1113-1127.
    We systematically study the interrelations between all possible variations of Δ10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta ^0_1$$\end{document} variants of the law of excluded middle and related principles in the context of intuitionistic arithmetic and analysis.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  6. The existence of states based on Glivenko semihoops.Pengfei He, Juntao Wang & Jiang Yang - 2022 - Archive for Mathematical Logic 61 (7):1145-1170.
    In this paper, we mainly investigate the existence of states based on the Glivenko theorem in bounded semihoops, which are building blocks for the algebraic semantics for relevant fuzzy logics. First, we extend algebraic formulations of the Glivenko theorem to bounded semihoops and give some characterizations of Glivenko semihoops and regular semihoops. The category of regular semihoops is a reflective subcategory of the category of Glivenko semihoops. Moreover, by means of the negative translation term, we characterize the Glivenko variety. Then (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  7.  1
    Dividing lines in unstable theories and subclasses of Baire 1 functions.Karim Khanaki - 2022 - Archive for Mathematical Logic 61 (7):977-993.
    We give a new characterization of SOP in terms of the behaviour of formulas in any model of the theory as opposed to having to look at the behaviour of indiscernible sequences inside saturated ones. We refine a theorem of Shelah, namely a theory has OP if and only if it has IP or SOP, in several ways by characterizing various notions in functional analytic style. We point out some connections between dividing lines in first order theories and subclasses of (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  8.  1
    On extendability to $$F_\sigma $$ ideals.Adam Kwela - 2022 - Archive for Mathematical Logic 61 (7):881-890.
    Answering in negative a question of M. Hrušák, we construct a Borel ideal not extendable to any \ ideal and such that it is not Katětov above the ideal \.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  9.  1
    On Extendability to Fσ\documentclass[12pt]{Minimal} \usepackage{Amsmath} \usepackage{Wasysym} \usepackage{Amsfonts} \usepackage{Amssymb} \usepackage{Amsbsy} \usepackage{Mathrsfs} \usepackage{Upgreek} \setlength{\oddsidemargin}{-69pt} \begin{Document}$$F_\sigma $$\end{Document} Ideals. [REVIEW]Adam Kwela - 2022 - Archive for Mathematical Logic 61 (7-8):881-890.
    Answering in negative a question of M. Hrušák, we construct a Borel ideal not extendable to any Fσ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_\sigma $$\end{document} ideal and such that it is not Katětov above the ideal conv\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {conv}$$\end{document}.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  10.  2
    Disjunctive logic programs, answer sets, and the cut rule.Éric Martin - 2022 - Archive for Mathematical Logic 61 (7):903-937.
    In Minker and Rajasekar :45–74, 1990), Minker proposed a semantics for negation-free disjunctive logic programs that offers a natural generalisation of the fixed point semantics for definite logic programs. We show that this semantics can be further generalised for disjunctive logic programs with classical negation, in a constructive modal-theoretic framework where rules are built from claims and hypotheses, namely, formulas of the form \ and \ where \ is a literal, respectively, yielding a “base semantics” for general disjunctive logic programs. (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  11.  1
    Weak essentially undecidable theories of concatenation.Juvenal Murwanashyaka - 2022 - Archive for Mathematical Logic 61 (7):939-976.
    In the language \, where 0 and 1 are constant symbols, \ is a binary function symbol and \ is a binary relation symbol, we formulate two theories, \ and \, that are mutually interpretable with the theory of arithmetic \ and Robinson arithmetic \, respectively. The intended model of \ and \ is the free semigroup generated by \ under string concatenation extended with the prefix relation. The theories \ and \ are purely universally axiomatised, in contrast to \ (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12.  1
    Enhancing Induction in a Contraction Free Logic with Unrestricted Abstraction: From $$\mathbf {Z}$$ to $$\mathbf {Z}_2$$.Uwe Petersen - 2022 - Archive for Mathematical Logic 61 (7-8):1007-1051.
    \ is a new type of non-finitist inference, i.e., an inference that involves treating some infinite collection as completed, designed for contraction free logic with unrestricted abstraction. It has been introduced in Petersen and shown to be consistent within a system \ \ of contraction free logic with unrestricted abstraction. In Petersen :665–694, 2003) it was established that adding \ to \ \ is sufficient to prove the totality of primitive recursive functions but it was also indicated that this would (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  13. Enhancing Induction in a Contraction Free Logic with Unrestricted Abstraction: From Z\documentclass[12pt]{Minimal} \usepackage{Amsmath} \usepackage{Wasysym} \usepackage{Amsfonts} \usepackage{Amssymb} \usepackage{Amsbsy} \usepackage{Mathrsfs} \usepackage{Upgreek} \setlength{\oddsidemargin}{-69pt} \begin{Document}$$\mathbf {Z}$$\end{Document} to Z2\documentclass[12pt]{Minimal} \usepackage{Amsmath} \usepackage{Wasysym} \usepackage{Amsfonts} \usepackage{Amssymb} \usepackage{Amsbsy} \usepackage{Mathrsfs} \usepackage{Upgreek} \setlength{\oddsidemargin}{-69pt} \begin{Document}$$\mathbf {Z}_2$$\end{Document}. [REVIEW]Uwe Petersen - 2022 - Archive for Mathematical Logic 61 (7-8):1007-1051.
    Z\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {Z}$$\end{document} is a new type of non-finitist inference, i.e., an inference that involves treating some infinite collection as completed, designed for contraction free logic with unrestricted abstraction. It has been introduced in Petersen and shown to be consistent within a system LiD\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {{}L^iD{}}{}$$\end{document}λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_{\uplambda }$$\end{document} of contraction free logic with unrestricted abstraction. In Petersen (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  14. On well-splitting posets.Dušan Repovš & Lyubomyr Zdomskyy - 2022 - Archive for Mathematical Logic 61 (7):995-1005.
    We introduce a class of proper posets which is preserved under countable support iterations, includes \-bounding, Cohen, Miller, and Mathias posets associated to filters with the Hurewicz covering properties, and has the property that the ground model reals remain splitting and unbounded in corresponding extensions. Our results may be considered as a possible path towards solving variations of the famous Roitman problem.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15. Destructibility and axiomatizability of Kaufmann models.Corey Bacal Switzer - 2022 - Archive for Mathematical Logic 61 (7):1091-1111.
    A Kaufmann model is an \-like, recursively saturated, rather classless model of \ ). Such models were constructed by Kaufmann under the combinatorial principle \ and Shelah showed they exist in \ by an absoluteness argument. Kaufmann models are an important witness to the incompactness of \ similar to Aronszajn trees. In this paper we look at some set theoretic issues related to this motivated by the seemingly naïve question of whether such a model can be “killed” by forcing without (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  16.  3
    Monadic $$k\times j$$ k × j -rough Heyting algebras.Federico Almiñana & Gustavo Pelaitay - 2022 - Archive for Mathematical Logic 61 (5):611-625.
    In this paper, we introduce the variety of algebras, which we call monadic \-rough Heyting algebras. These algebras constitute an extension of monadic Heyting algebras and in \ case they coincide with monadic 3-valued Łukasiewicz–Moisil algebras. Our main interest is the characterization of simple and subdirectly irreducible monadic \-rough Heyting algebras. In order to this, an Esakia-style duality for these algebras is developed.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  2
    Mutual algebraicity and cellularity.Samuel Braunfeld & Michael C. Laskowski - 2022 - Archive for Mathematical Logic 61 (5):841-857.
    We prove two results intended to streamline proofs about cellularity that pass through mutual algebraicity. First, we show that a countable structure M is cellular if and only if M is \-categorical and mutually algebraic. Second, if a countable structure M in a finite relational language is mutually algebraic non-cellular, we show it admits an elementary extension adding infinitely many infinite MA-connected components. Towards these results, we introduce MA-presentations of a mutually algebraic structure, in which every atomic formula is mutually (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  18.  2
    The covering number of the strong measure zero ideal can be above almost everything else.Miguel A. Cardona, Diego A. Mejía & Ismael E. Rivera-Madrid - 2022 - Archive for Mathematical Logic 61 (5):599-610.
    We show that certain type of tree forcings, including Sacks forcing, increases the covering of the strong measure zero ideal \. As a consequence, in Sacks model, such covering number is equal to the size of the continuum, which indicates that this covering number is consistently larger than any other classical cardinal invariant of the continuum. Even more, Sacks forcing can be used to force that \<\mathrm {cov}<\mathrm {cof}\), which is the first consistency result where more than two cardinal invariants (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  2
    Hindman’s theorem for sums along the full binary tree, $$\Sigma ^0_2$$ Σ 2 0 -induction and the Pigeonhole principle for trees. [REVIEW]Lorenzo Carlucci & Daniele Tavernelli - 2022 - Archive for Mathematical Logic 61 (5):827-839.
    We formulate a restriction of Hindman’s Finite Sums Theorem in which monochromaticity is required only for sums corresponding to rooted finite paths in the full binary tree. We show that the resulting principle is equivalent to \-induction over \. The proof uses the equivalence of this Hindman-type theorem with the Pigeonhole Principle for trees \ with an extra condition on the solution tree.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  20.  2
    Reflection and not SCH with overlapping extenders.Moti Gitik - 2022 - Archive for Mathematical Logic 61 (5):591-597.
    We use the forcing with overlapping extenders to give a direct construction of a model of \SCH+Reflection.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  1
    An alternative proof of the Hilbert-style axiomatization for the $$\{\wedge,\vee \}$$ { ∧, ∨ } -fragment of classical propositional logic.Luciano J. González - 2022 - Archive for Mathematical Logic 61 (5):859-865.
    Dyrda and Prucnal gave a Hilbert-style axiomatization for the \-fragment of classical propositional logic. Their proof of completeness follows a different approach to the standard one proving the completeness of classical propositional logic. In this note, we present an alternative proof of Dyrda and Prucnal’s result following the standard arguments which prove the completeness of classical propositional logic.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  22.  3
    An Alternative Proof of the Hilbert-Style Axiomatization for the {∧,∨}\documentclass[12pt]{Minimal} \usepackage{Amsmath} \usepackage{Wasysym} \usepackage{Amsfonts} \usepackage{Amssymb} \usepackage{Amsbsy} \usepackage{Mathrsfs} \usepackage{Upgreek} \setlength{\oddsidemargin}{-69pt} \begin{Document}$$\{\wedge,\vee \}$$\end{Document}-Fragment of Classical Propositional Logic. [REVIEW]Luciano J. González - 2022 - Archive for Mathematical Logic 61 (5-6):859-865.
    Dyrda and Prucnal gave a Hilbert-style axiomatization for the {∧,∨}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{\wedge,\vee \}$$\end{document}-fragment of classical propositional logic. Their proof of completeness follows a different approach to the standard one proving the completeness of classical propositional logic. In this note, we present an alternative proof of Dyrda and Prucnal’s result following the standard arguments which prove the completeness of classical propositional logic.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  1
    On the isomorphism problem for some classes of computable algebraic structures.Valentina S. Harizanov, Steffen Lempp, Charles F. D. McCoy, Andrei S. Morozov & Reed Solomon - 2022 - Archive for Mathematical Logic 61 (5):813-825.
    We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  24.  2
    Iterated multiplication in $$ VTC ^0$$ V T C 0.Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5):705-767.
    We show that \, the basic theory of bounded arithmetic corresponding to the complexity class \, proves the \ axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the \ iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, \ can also prove the integer division axiom, and the \-translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories \ and \. As a side (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  25.  1
    Iterated Multiplication in $$ VTC ^0$$ V T C 0. [REVIEW]Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5-6):705-767.
    We show that VTC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ VTC ^0$$\end{document}, the basic theory of bounded arithmetic corresponding to the complexity class TC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {TC}^0$$\end{document}, proves the IMUL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ IMUL $$\end{document} axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the TC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {TC}^0$$\end{document} iterated (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  26.  1
    Many different uniformity numbers of Yorioka ideals.Lukas Daniel Klausner & Diego Alejandro Mejía - 2022 - Archive for Mathematical Logic 61 (5):653-683.
    Using a countable support product of creature forcing posets, we show that consistently, for uncountably many different functions the associated Yorioka ideals’ uniformity numbers can be pairwise different. In addition we show that, in the same forcing extension, for two other types of simple cardinal characteristics parametrised by reals, for uncountably many parameters the corresponding cardinals are pairwise different.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  27.  1
    Antichains of copies of ultrahomogeneous structures.Miloš S. Kurilić & Boriša Kuzeljević - 2022 - Archive for Mathematical Logic 61 (5):867-879.
    We investigate possible cardinalities of maximal antichains in the poset of copies \,\subseteq \rangle \) of a countable ultrahomogeneous relational structure \. It turns out that if the age of \ has the strong amalgamation property, then, defining a copy of \ to be large iff it has infinite intersection with each orbit of \, the structure \ can be partitioned into countably many large copies, there are almost disjoint families of large copies of size continuum and, hence, there are (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  28.  1
    Remarks on weak amalgamation and large conjugacy classes in non-archimedean groups.Maciej Malicki - 2022 - Archive for Mathematical Logic 61 (5):685-704.
    We study the notion of weak amalgamation in the context of diagonal conjugacy classes. Generalizing results of Kechris and Rosendal, we prove that for every countable structure M, Polish group G of permutations of M, and \, G has a comeager n-diagonal conjugacy class iff the family of all n-tuples of G-extendable bijections between finitely generated substructures of M, has the joint embedding property and the weak amalgamation property. We characterize limits of weak Fraïssé classes that are not homogenizable. Finally, (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29.  11
    Between Hilbert and Gentzen: four-valued consequence systems and structural reasoning.Yaroslav Shramko - 2022 - Archive for Mathematical Logic 61 (5):627-651.
    Structural reasoning is simply reasoning that is governed exclusively by structural rules. In this context a proof system can be said to be structural if all of its inference rules are structural. A logic is considered to be structuralizable if it can be equipped with a sound and complete structural proof system. This paper provides a general formulation of the problem of structuralizability of a given logic, giving specific consideration to a family of logics that are based on the Dunn–Belnap (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30.  1
    Equivalence of generics.Iian B. Smythe - 2022 - Archive for Mathematical Logic 61 (5):795-812.
    Given a countable transitive model of set theory and a partial order contained in it, there is a natural countable Borel equivalence relation on generic filters over the model; two are equivalent if they yield the same generic extension. We examine the complexity of this equivalence relation for various partial orders, focusing on Cohen and random forcing. We prove, among other results, that the former is an increasing union of countably many hyperfinite Borel equivalence relations, and hence is amenable, while (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  31.  5
    Hindman’s Theorem for Sums Along the Full Binary Tree, $$\sigma ^0_2$$ Σ 2 0 -Induction and the Pigeonhole Principle for Trees. [REVIEW]Daniele Tavernelli & Lorenzo Carlucci - 2022 - Archive for Mathematical Logic 61 (5-6):827-839.
    We formulate a restriction of Hindman’s Finite Sums Theorem in which monochromaticity is required only for sums corresponding to rooted finite paths in the full binary tree. We show that the resulting principle is equivalent to Σ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Sigma ^0_2$$\end{document}-induction over RCA0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {RCA}_0$$\end{document}. The proof uses the equivalence of this Hindman-type theorem with the Pigeonhole Principle for trees TT1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  32.  4
    Reverse mathematics and semisimple rings.Huishan Wu - 2022 - Archive for Mathematical Logic 61 (5):769-793.
    This paper studies various equivalent characterizations of left semisimple rings from the standpoint of reverse mathematics. We first show that \ is equivalent to the statement that any left module over a left semisimple ring is semisimple over \. We then study characterizations of left semisimple rings in terms of projective modules as well as injective modules, and obtain the following results: \ is equivalent to the statement that any left module over a left semisimple ring is projective over \; (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  33.  3
    Hanf numbers for extendibility and related phenomena.John T. Baldwin & Saharon Shelah - 2022 - Archive for Mathematical Logic 61 (3):437-464.
    This paper contains portions of Baldwin’s talk at the Set Theory and Model Theory Conference and a detailed proof that in a suitable extension of ZFC, there is a complete sentence of \ that has maximal models in cardinals cofinal in the first measurable cardinal and, of course, never again.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  34.  2
    Definable groups in dense pairs of geometric structures.Alexander Berenstein & Evgueni Vassiliev - 2022 - Archive for Mathematical Logic 61 (3):345-372.
    We study definable groups in dense/codense expansions of geometric theories with a new predicate P such as lovely pairs and expansions of fields by groups with the Mann property. We show that in such expansions, large definable subgroups of groups definable in the original language \ are also \-definable, and definably amenable \-definable groups remain amenable in the expansion. We also show that if the underlying geometric theory is NIP, and G is a group definable in a model of T, (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  35.  5
    Model theory of monadic predicate logic with the infinity quantifier.Facundo Carreiro, Alessandro Facchini, Yde Venema & Fabio Zanasi - 2022 - Archive for Mathematical Logic 61 (3):465-502.
    This paper establishes model-theoretic properties of \, a variation of monadic first-order logic that features the generalised quantifier \. We will also prove analogous versions of these results in the simpler setting of monadic first-order logic with and without equality and \, respectively). For each logic \ we will show the following. We provide syntactically defined fragments of \ characterising four different semantic properties of \-sentences: being monotone and continuous in a given set of monadic predicates; having truth preserved under (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  36.  3
    Condensable models of set theory.Ali Enayat - 2022 - Archive for Mathematical Logic 61 (3):299-315.
    A model \ of ZF is said to be condensable if \\prec _{\mathbb {L}_{{\mathcal {M}}}} {\mathcal {M}}\) for some “ordinal” \, where \:=,\in )^{{\mathcal {M}}}\) and \ is the set of formulae of the infinitary logic \ that appear in the well-founded part of \. The work of Barwise and Schlipf in the 1970s revealed the fact that every countable recursively saturated model of ZF is cofinally condensable \prec _{\mathbb {L}_{{\mathcal {M}}}}{\mathcal {M}}\) for an unbounded collection of \). Moreover, it (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  37.  1
    A criterion for uniform finiteness in the imaginary sorts.Will Johnson - 2022 - Archive for Mathematical Logic 61 (3):583-589.
    Let T be a theory. If T eliminates \, it need not follow that \ eliminates \, as shown by the example of the p-adics. We give a criterion to determine whether \ eliminates \. Specifically, we show that \ eliminates \ if and only if \ is eliminated on all interpretable sets of “unary imaginaries.” This criterion can be applied in cases where a full description of \ is unknown. As an application, we show that \ eliminates \ when (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  38.  3
    Efficient elimination of Skolem functions in $$\text {LK}^\text {h}$$ LK h.Ján Komara - 2022 - Archive for Mathematical Logic 61 (3):503-534.
    We present a sequent calculus with the Henkin constants in the place of the free variables. By disposing of the eigenvariable condition, we obtained a proof system with a strong locality property—the validity of each inference step depends only on its active formulas, not its context. Our major outcomes are: the cut elimination via a non-Gentzen-style algorithm without resorting to regularization and the elimination of Skolem functions with linear increase in the proof length for a subclass of derivations with cuts.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  39.  4
    A note on cut-elimination for classical propositional logic.Gabriele Pulcini - 2022 - Archive for Mathematical Logic 61 (3):555-565.
    In Schwichtenberg, Schwichtenberg fine-tuned Tait’s technique so as to provide a simplified version of Gentzen’s original cut-elimination procedure for first-order classical logic. In this note we show that, limited to the case of classical propositional logic, the Tait–Schwichtenberg algorithm allows for a further simplification. The procedure offered here is implemented on Kleene’s sequent system G4. The specific formulation of the logical rules for G4 allows us to provide bounds on the height of cut-free proofs just in terms of the logical (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  40.  4
    Bounded inductive dichotomy: separation of open and clopen determinacies with finite alternatives in constructive contexts.Kentaro Sato - 2022 - Archive for Mathematical Logic 61 (3):399-435.
    In his previous work, the author has introduced the axiom schema of inductive dichotomy, a weak variant of the axiom schema of inductive definition, and used this schema for elementary ) positive operators to separate open and clopen determinacies for those games in which two players make choices from infinitely many alternatives in various circumstances. Among the studies on variants of inductive definitions for bounded ) positive operators, the present article investigates inductive dichotomy for these operators, and applies it to (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  41.  2
    Coanalytic ultrafilter bases.Jonathan Schilhan - 2022 - Archive for Mathematical Logic 61 (3-4):567-581.
    We study the definability of ultrafilter bases on \ in the sense of descriptive set theory. As a main result we show that there is no coanalytic base for a Ramsey ultrafilter, while in L we can construct \ P-point and Q-point bases. We also show that the existence of a \ ultrafilter is equivalent to that of a \ ultrafilter base, for \. Moreover we introduce a Borel version of the classical ultrafilter number and make some observations.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  42.  1
    Multiplicative finite embeddability vs divisibility of ultrafilters.Boris Šobot - 2022 - Archive for Mathematical Logic 61 (3):535-553.
    We continue the exploration of various aspects of divisibility of ultrafilters, adding one more relation to the picture: multiplicative finite embeddability. We show that it lies between divisibility relations \ and \. The set of its minimal elements proves to be very rich, and the \-hierarchy is used to get a better intuition of this richness. We find the place of the set of \-maximal ultrafilters among some known families of ultrafilters. Finally, we introduce new notions of largeness of subsets (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  43.  4
    Computability and the game of cops and robbers on graphs.Rachel D. Stahl - 2022 - Archive for Mathematical Logic 61 (3):373-397.
    Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and graphs are explored. The (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  44.  4
    Combinatory logic with polymorphic types.William R. Stirton - 2022 - Archive for Mathematical Logic 61 (3):317-343.
    Sections 1 through 4 define, in the usual inductive style, various classes of object including one which is called the “combinatory terms of polymorphic type”. Section 5 defines a reduction relation on these terms. Section 6 shows that the weak normalizability of the combinatory terms of polymorphic type entails the weak normalizability of the lambda terms of polymorphic type. The entailment is not vacuous, because the combinatory terms of polymorphic type are indeed weakly normalizable, as is proven in Sect. 7 (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  45.  4
    Various forms of infinity for finitely supported structures.Andrei Alexandru & Gabriel Ciobanu - 2022 - Archive for Mathematical Logic 61 (1):173-222.
    The goal of this paper is to define and study the notion of infinity in the framework of finitely supported structures, presenting new properties of infinite cardinalities. Some of these properties are extended from the non-atomic Zermelo–Fraenkel set theory to the world of atomic objects with finite support, while other properties are specific to finitely supported structures. We compare alternative definitions for infinity in the world of finitely supported sets, and provide relevant examples of atomic sets which satisfy some forms (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  46.  3
    The independence of $$\mathsf {GCH}$$ GCH and a combinatorial principle related to Banach–Mazur games.Will Brian, Alan Dow & Saharon Shelah - 2022 - Archive for Mathematical Logic 61 (1):1-17.
    It was proved recently that Telgársky’s conjecture, which concerns partial information strategies in the Banach–Mazur game, fails in models of \. The proof introduces a combinatorial principle that is shown to follow from \, namely: \::Every separative poset \ with the \-cc contains a dense sub-poset \ such that \ for every \. We prove this principle is independent of \ and \, in the sense that \ does not imply \, and \ does not imply \ assuming the consistency (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  47.  3
    On Hilbert algebras generated by the order.J. L. Castiglioni, S. A. Celani & H. J. San Martín - 2022 - Archive for Mathematical Logic 61 (1):155-172.
    In this paper we study the variety of order Hilbert algebras, which is the equivalent algebraic semantics of the order implicational calculus of Bull.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  48.  3
    Degree structures of conjunctive reducibility.Irakli Chitaia & Roland Omanadze - 2022 - Archive for Mathematical Logic 61 (1):19-31.
    We show: for every noncomputable c.e. incomplete c-degree, there exists a nonspeedable c-degree incomparable with it; The c-degree of a hypersimple set includes an infinite collection of \-degrees linearly ordered under \ with order type of the integers and consisting entirely of hypersimple sets; there exist two c.e. sets having no c.e. least upper bound in the \-reducibility ordering; the c.e. \-degrees are not dense.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  49.  3
    A boundedness principle for the Hjorth rank.Ohad Drucker - 2022 - Archive for Mathematical Logic 61 (1):223-232.
    Hjorth introduced a Scott analysis for general Polish group actions, and asked whether his notion of rank satisfies a boundedness principle similar to the one of Scott rank—namely, if the orbit equivalence relation is Borel, then Hjorth ranks are bounded. We answer Hjorth’s question positively. As a corollary we prove the following conjecture of Hjorth—for every limit ordinal \, the set of elements whose orbit is of complexity less than \ is a Borel set.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  50.  1
    Representability and compactness for pseudopowers.Todd Eisworth - 2022 - Archive for Mathematical Logic 61 (1):55-80.
    We prove a compactness theorem for pseudopower operations of the form \}\) where \\le {{\,\mathrm{cf}\,}}\). Our main tool is a result that has Shelah’s cov versus pp Theorem as a consequence. We also show that the failure of compactness in other situations has significant consequences for pcf theory, in particular, implying the existence of a progressive set A of regular cardinals for which \\) has an inaccessible accumulation point.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  51.  6
    Small $$\mathfrak {u}(\kappa )$$ u ( κ ) at singular $$\kappa $$ κ with compactness at $$\kappa ^{++}$$ κ + +.Radek Honzik & Šárka Stejskalová - 2022 - Archive for Mathematical Logic 61 (1):33-54.
    We show that the tree property, stationary reflection and the failure of approachability at \ are consistent with \= \kappa ^+ < 2^\kappa \), where \ is a singular strong limit cardinal with the countable or uncountable cofinality. As a by-product, we show that if \ is a regular cardinal, then stationary reflection at \ is indestructible under all \-cc forcings.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  52.  2
    First-order theories of bounded trees.Ruaan Kellerman - 2022 - Archive for Mathematical Logic 61 (1):263-297.
    A maximal chain in a tree is called a path, and a tree is called bounded when all its paths contain leaves. This paper concerns itself with first-order theories of bounded trees. We establish some sufficient conditions for the existence of bounded end-extensions that are also partial elementary extensions of a given tree. As an application of tree boundedness, we obtain a conditional axiomatisation of the first-order theory of the class of trees whose paths are all isomorphic to some ordinal (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  53. Normalisation and Subformula Property for a System of Classical Logic with Tarski’s Rule.Nils Kürbis - 2022 - Archive for Mathematical Logic 61 (1):105-129.
    This paper considers a formalisation of classical logic using general introduction rules and general elimination rules. It proposes a definition of ‘maximal formula’, ‘segment’ and ‘maximal segment’ suitable to the system, and gives reduction procedures for them. It is then shown that deductions in the system convert into normal form, i.e. deductions that contain neither maximal formulas nor maximal segments, and that deductions in normal form satisfy the subformula property. Tarski’s Rule is treated as a general introduction rule for implication. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  54.  3
    Sprague–Grundy theory in bounded arithmetic.Satoru Kuroda - 2022 - Archive for Mathematical Logic 61 (1):233-262.
    We will give a two-sort system which axiomatizes winning strategies for the combinatorial game Node Kayles. It is shown that our system captures alternating polynomial time reasonings in the sense that the provably total functions of the theory corresponds to those computable in APTIME. We will also show that our system is equivalently axiomatized by Sprague–Grundy theorem which states that any Node Kayles position is provably equivalent to some NIM heap.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  55.  2
    Does weak quasi-o-minimality behave better than weak o-minimality?Slavko Moconja & Predrag Tanović - 2022 - Archive for Mathematical Logic 61 (1):81-103.
    We present a relatively simple description of binary, definable subsets of models of weakly quasi-o-minimal theories. In particular, we closely describe definable linear orders and prove a weak version of the monotonicity theorem. We also prove that weak quasi-o-minimality of a theory with respect to one definable linear order implies weak quasi-o-minimality with respect to any other such order.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  56.  2
    Rosenthal families, filters, and semifilters.Miroslav Repický - 2022 - Archive for Mathematical Logic 61 (1):131-153.
    We continue the study of Rosenthal families initiated by Damian Sobota. We show that every Rosenthal filter is the intersection of a finite family of ultrafilters that are pairwise incomparable in the Rudin-Keisler partial ordering of ultrafilters. We introduce a property of filters, called an \-filter, properly between a selective filter and a \-filter. We prove that every \-ultrafilter is a Rosenthal family. We prove that it is consistent with ZFC to have uncountably many \-ultrafilters such that any intersection of (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
 Previous issues
  
Next issues