26 found

View year:

  1.  19
    Borel complexity and Ramsey largeness of sets of oracles separating complexity classes.Alex Creiner & Stephen Jackson - 2023 - Mathematical Logic Quarterly 69 (3):267-286.
    We prove two sets of results concerning computational complexity classes. First, we propose a new variation of the random oracle hypothesis, originally posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, with probability 1. Their original hypothesis was quickly disproven in several ways, most famously in 1992 with the result that, in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to be “large” using (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2.  14
    Coding of real‐valued continuous functions under WKL$\mathsf {WKL}$.Tatsuji Kawai - 2023 - Mathematical Logic Quarterly 69 (3):370-391.
    In the context of constructive reverse mathematics, we show that weak Kőnig's lemma () implies that every pointwise continuous function is induced by a code in the sense of reverse mathematics. This, combined with the fact that implies the Fan theorem, shows that implies the uniform continuity theorem: every pointwise continuous function has a modulus of uniform continuity. Our results are obtained in Heyting arithmetic in all finite types with quantifier‐free axiom of choice.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  21
    On Hausdorff operators in ZF$\mathsf {ZF}$.Kyriakos Keremedis & Eleftherios Tachtsis - 2023 - Mathematical Logic Quarterly 69 (3):347-369.
    A Hausdorff space is called effectively Hausdorff if there exists a function F—called a Hausdorff operator—such that, for every with,, where U and V are disjoint open neighborhoods of x and y, respectively. Among other results, we establish the following in, i.e., in Zermelo–Fraenkel set theory without the Axiom of Choice (): is equivalent to “For every set X, the Cantor cube is effectively Hausdorff”. This enhances the result of Howard, Keremedis, Rubin and Rubin [13] that is equivalent to “Hausdorff (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  66
    Forcing revisited.Toby Meadows - 2023 - Mathematical Logic Quarterly 69 (3):287-340.
    The purpose of this paper is to propose and explore a general framework within which a wide variety of model construction techniques from contemporary set theory can be subsumed. Taking our inspiration from presheaf constructions in category theory and Boolean ultrapowers, we will show that generic extensions, ultrapowers, extenders and generic ultrapowers can be construed as examples of a single model construction technique. In particular, we will show that Łoś's theorem can be construed as a specific case of Cohen's truth (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  18
    The permutations with n non‐fixed points and the subsets with n elements of a set.Supakun Panasawatwong & Pimpen Vejjajiva - 2023 - Mathematical Logic Quarterly 69 (3):341-346.
    We write and for the cardinalities of the set of permutations with n non‐fixed points and the set of subsets with n elements, respectively, of a set which is of cardinality, where n is a natural number greater than 1. With the Axiom of Choice, and are equal for all infinite cardinals. We show, in ZF, that if is assumed, then for any infinite cardinal. Moreover, the assumption cannot be removed for and the superscript cannot be replaced by n. We (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  26
    Spherically complete models of Hensel minimal valued fields.David B. Bradley-Williams & Immanuel Halupczok - 2023 - Mathematical Logic Quarterly 69 (2):138-146.
    We prove that Hensel minimal expansions of finitely ramified Henselian valued fields admit spherically complete immediate elementary extensions. More precisely, the version of Hensel minimality we use is 0‐hmix‐minimality (which, in equi‐characteristic 0, amounts to 0‐h‐minimality).
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  18
    On the variety of strong subresiduated lattices.Sergio Celani & Hernán J. San Martín - 2023 - Mathematical Logic Quarterly 69 (2):207-220.
    A subresiduated lattice is a pair, where A is a bounded distributive lattice, D is a bounded sublattice of A and for every there exists the maximum of the set, which is denoted by. This pair can be regarded as an algebra of type (2, 2, 2, 0, 0), where. The class of subresiduated lattices is a variety which properly contains the variety of Heyting algebras. In this paper we study the subvariety of subresiduated lattices, denoted by, whose members satisfy (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  19
    Topological properties of definable sets in ordered Abelian groups of burden 2.Alfred Dolich & John Goodrick - 2023 - Mathematical Logic Quarterly 69 (2):147-164.
    We obtain some new results on the topology of unary definable sets in expansions of densely ordered Abelian groups of burden 2. In the special case in which the structure has dp‐rank 2, we show that the existence of an infinite definable discrete set precludes the definability of a set which is dense and codense in an interval, or of a set which is topologically like the Cantor middle‐third set (Theorem 2.9). If it has burden 2 and both an infinite (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  20
    Bisimulations and bisimulation games between Verbrugge models.Sebastijan Horvat, Tin Perkov & Mladen Vuković - 2023 - Mathematical Logic Quarterly 69 (2):231-243.
    Interpretability logic is a modal formalization of relative interpretability between first‐order arithmetical theories. Verbrugge semantics is a generalization of Veltman semantics, the basic semantics for interpretability logic. Bisimulation is the basic equivalence between models for modal logic. We study various notions of bisimulation between Verbrugge models and develop a new one, which we call w‐bisimulation. We show that the new notion, while keeping the basic property that bisimilarity implies modal equivalence, is weak enough to allow the converse to hold in (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  23
    Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts.Emil Jeřábek - 2023 - Mathematical Logic Quarterly 69 (2):244-260.
    We prove that (additive) ordered group reducts of nonstandard models of the bounded arithmetical theory are recursively saturated in a rich language with predicates expressing the integers, rationals, and logarithmically bounded numbers. Combined with our previous results on the construction of the real exponential function on completions of models of, we show that every countable model of is an exponential integer part of a real‐closed exponential field.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  30
    Topological duality for orthomodular lattices.Joseph McDonald & Katalin Bimbó - 2023 - Mathematical Logic Quarterly 69 (2):174-191.
    A class of ordered relational topological spaces is described, which we call orthomodular spaces. Our construction of these spaces involves adding a topology to the class of orthomodular frames introduced by Hartonas, along the lines of Bimbó's topologization of the class of orthoframes employed by Goldblatt in his representation of ortholattices. We then prove that the category of orthomodular lattices and homomorphisms is dually equivalent to the category of orthomodular spaces and certain continuous frame morphisms, which we call continuous weak (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  25
    On self‐distributive weak Heyting algebras.Mohsen Nourany, Shokoofeh Ghorbani & Arsham Borumand Saeid - 2023 - Mathematical Logic Quarterly 69 (2):192-206.
    We use the left self‐distributive axiom to introduce and study a special class of weak Heyting algebras, called self‐distributive weak Heyting algebras (SDWH‐algebras). We present some useful properties of SDWH‐algebras and obtain some equivalent conditions of them. A characteristic of SDWH‐algebras of orders 3 and 4 is given. Finally, we study the relation between the variety of SDWH‐algebras and some of the known subvarieties of weak Heyting algebras such as the variety of Heyting algebras, the variety of basic algebras, the (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  15
    Avoiding Medvedev reductions inside a linear order.Noah Schweber - 2023 - Mathematical Logic Quarterly 69 (2):165-173.
    While every endpointed interval I in a linear order J is, considered as a linear order in its own right, trivially Muchnik‐reducible to J itself, this fails for Medvedev‐reductions. We construct an extreme example of this: a linear order in which no endpointed interval is Medvedev‐reducible to any other, even allowing parameters, except when the two intervals have finite difference. We also construct a scattered linear order which has many endpointed intervals Medvedev‐incomparable to itself; the only other known construction of (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  14
    Bowtie‐free graphs and generic automorphisms.Daoud Siniora - 2023 - Mathematical Logic Quarterly 69 (2):221-230.
    We show that the countable universal ω‐categorical bowtie‐free graph admits generic automorphisms. Moreover, we show that this graph is not finitely homogenisable.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  16
    Strongly unfoldable, splitting and bounding.Ömer Faruk Bağ & Vera Fischer - 2023 - Mathematical Logic Quarterly 69 (1):7-14.
    Assuming, we show that generalized eventually narrow sequences on a strongly inaccessible cardinal κ are preserved under a one step iteration of the Hechler forcing for adding a dominating κ‐real. Moreover, we show that if κ is strongly unfoldable, and λ is a regular cardinal such that, then there is a set generic extension in which.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16.  14
    Decomposition into special submanifolds.Masato Fujita - 2023 - Mathematical Logic Quarterly 69 (1):104-116.
    We study definably complete locally o‐minimal expansions of ordered groups. We propose a notion of special submanifolds with tubular neighborhoods and show that any definable set is decomposed into finitely many special submanifolds with tubular neighborhoods.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  16
    Some definable types that cannot be amalgamated.Martin Hils & Rosario Mennuni - 2023 - Mathematical Logic Quarterly 69 (1):46-49.
    We exhibit a theory where definable types lack the amalgamation property.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18.  19
    A note on fsg$\text{fsg}$ groups in p‐adically closed fields.Will Johnson - 2023 - Mathematical Logic Quarterly 69 (1):50-57.
    Let G be a definable group in a p-adically closed field M. We show that G has finitely satisfiable generics ( fsg $\text{fsg}$ ) if and only if G is definably compact. The case M = Q p $M = \mathbb {Q}_p$ was previously proved by Onshuus and Pillay.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  19.  16
    Cofinal types on ω 2.Borisa Kuzeljevic & Stevo Todorcevic - 2023 - Mathematical Logic Quarterly 69 (1):92-103.
    In this paper we start the analysis of the class, the class of cofinal types of directed sets of cofinality at most ℵ2. We compare elements of using the notion of Tukey reducibility. We isolate some simple cofinal types in, and then proceed to find some of these types which have an immediate successor in the Tukey ordering of.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  20.  16
    On splitting trees.Giorgio Laguzzi, Heike Mildenberger & Brendan Stuber-Rousselle - 2023 - Mathematical Logic Quarterly 69 (1):15-30.
    We investigate two variants of splitting tree forcing, their ideals and regularity properties. We prove connections with other well‐known notions, such as Lebesgue measurablility, Baire‐ and Doughnut‐property and the Marczewski field. Moreover, we prove that any absolute amoeba forcing for splitting trees necessarily adds a dominating real, providing more support to Hein's and Spinas' conjecture that.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  15
    The subset relation and 2‐stratified sentences in set theory and class theory.Zachiri McKenzie - 2023 - Mathematical Logic Quarterly 69 (1):77-91.
    Hamkins and Kikuchi (2016, 2017) show that in both set theory and class theory the definable subset ordering of the universe interprets a complete and decidable theory. This paper identifies the minimum subsystem of,, that ensures that the definable subset ordering of the universe interprets a complete theory, and classifies the structures that can be realised as the subset relation in a model of this set theory. Extending and refining Hamkins and Kikuchi's result for class theory, a complete extension,, of (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  22.  18
    A proof‐theoretic metatheorem for tracial von Neumann algebras.Liviu Păunescu & Andrei Sipoş - 2023 - Mathematical Logic Quarterly 69 (1):63-76.
    We adapt a continuous logic axiomatization of tracial von Neumann algebras due to Farah, Hart and Sherman in order to prove a metatheorem for this class of structures in the style of proof mining, a research programme that aims to obtain the hidden computational content of ordinary mathematical proofs using tools from proof theory.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  18
    The cofinality of the strong measure zero ideal for κ inaccessible.Johannes Philipp Schürz - 2023 - Mathematical Logic Quarterly 69 (1):31-39.
    We investigate the cofinality of the strong measure zero ideal for κ inaccessible and show that it is independent of the size of 2κ.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  19
    Nice ℵ 1 generated non‐P‐points, Part I.Saharon Shelah - 2023 - Mathematical Logic Quarterly 69 (1):117-129.
    We define a family of non‐principal ultrafilters on which are, in a sense, very far from P‐points. We prove the existence of such ultrafilters under reasonable conditions. In subsequent articles, we intend to prove that such ultrafilters may exist while no P‐point exists. Though our primary motivations came from forcing and independence results, the family of ultrafilters introduced here should be interesting from combinatorial point of view too.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  25.  21
    The power set and the set of permutations with finitely many non‐fixed points of a set.Guozhen Shen - 2023 - Mathematical Logic Quarterly 69 (1):40-45.
    For a cardinal, we write for the cardinality of the set of permutations with finitely many non‐fixed points of a set which is of cardinality. We investigate the relationships between and for an arbitrary infinite cardinal in (without the axiom of choice). It is proved in that for all infinite cardinals, and we show that this is the best possible result.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  26.  18
    Incomparable Vγ$V_\gamma$‐degrees.Teng Zhang - 2023 - Mathematical Logic Quarterly 69 (1):58-62.
    In [3], Shi proved that there exist incomparable Zermelo degrees at γ if there exists an ω‐sequence of measurable cardinals, whose limit is γ. He asked whether there is a size antichain of Zermelo degrees. We consider this question for the ‐degree structure. We use a kind of Prikry‐type forcing to show that if there is an ω‐sequence of measurable cardinals, then there are ‐many pairwise incomparable ‐degrees, where γ is the limit of the ω‐sequence of measurable cardinals.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
 Previous issues
  
Next issues