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 (...) the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating and is not small, and obtain similar results for the separation of from along with the separation of from. We also show that the set of oracles equating with is large in this new sense. We demonstrate that this version of the hypothesis provides a sufficient condition for unrelativized relationships, at least in the cases considered here. Second, we examine the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel hierarchy. (shrink)

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.

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 (...) spaces are effectively Hausdorff” in. The Boolean Prime Ideal Theorem and the statement “For every infinite set X, the Stone space of the Boolean algebra is effectively Hausdorff” are mutually independent. In particular, the latter statement is not provable in. The Axiom of Choice for non‐empty subsets of () is equivalent to each of “Separable Hausdorff spaces are effectively Hausdorff” and “The Cantor cube is effectively Hausdorff”. The Principle of Dependent Choices in conjunction with the Axiom of Choice for continuum sized families of non‐empty subsets of does not imply the axiom of choice for partitions of. The latter independence result fills the gap in information in Howard and Rubin's book “Consequences of the Axiom of Choice”. The axiom of countable choice for non‐empty subsets of is equivalent to each of “Denumerable Hausdorff spaces are effectively Hausdorff”, “Denumerable T3 spaces are completely normal” and “Denumerable Tychonoff spaces are Urysohn”. (shrink)

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 (...) lemma, and we isolate the weakest conditions a filter must satisfy in order for the truth lemma to work. (shrink)

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 (...) also show under that for any infinite cardinal, implies is Dedekind‐infinite. (shrink)

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).

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 (...) the equation. Inspired by the fact that in any subresiduated lattice whose order is total the previous equation and the condition for every are satisfied, we also study the subvariety of generated by the class whose members satisfy that for every. (shrink)

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 (...) discrete set D and a dense‐codense set X are definable, then translates of X must witness the Independence Property (Theorem 2.26). In the last section, an explicit example of an ordered Abelian group of burden 2 is given in which both an infinite discrete set and a dense‐codense set are definable. (shrink)

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 (...) the finitary case. To do this, we develop and use an appropriate notion of bisimulation games between Verbrugge models. (shrink)

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.

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 (...) p‐morphisms. It is well‐known that orthomodular lattices provide an algebraic semantics for the quantum logic. Hence, as an application of our duality, we develop a topological semantics for using orthomodular spaces and prove soundness and completeness. (shrink)

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 (...) variety of subresiduated lattices, the variety of reflexive WH‐algebras (RWH‐algebras), and the variety of transitive WH‐algebras (TWH‐algebras). (shrink)

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 (...) such a linear order yields an ordinal of extremely high complexity, whereas this construction produces a low‐level‐arithmetic example. Additionally, the constructions here are “coarse” in the sense that they lift to other uniform reducibility notions in place of Medvedev reducibility itself. (shrink)

We show that the countable universal ω‐categorical bowtie‐free graph admits generic automorphisms. Moreover, we show that this graph is not finitely homogenisable.

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.

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.

We exhibit a theory where definable types lack the amalgamation property.

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.

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.

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.

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 (...) the theory of infinite atomic boolean algebras and a minimum subsystem,, of are identified with the property that if is a model of, then is a model of, where M is the underlying set of, is the unary predicate that distinguishes sets from classes and is the definable subset relation. These results are used to show that that decides every 2‐stratified sentence of set theory and decides every 2‐stratified sentence of class theory. (shrink)

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.

We investigate the cofinality of the strong measure zero ideal for κ inaccessible and show that it is independent of the size of 2κ.

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.

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.

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.