We consider the question “Is every nonzero generic degree a density-1-bounding generic degree?” By previous results [8] either resolution of this question would answer an open question concerning the structure of the generic degrees: A positive result would prove that there are no minimal generic degrees, and a negative result would prove that there exist minimal pairs in the generic degrees.

We consider several techniques for showing that the answer might be positive, and use those techniques to prove that a wide class of assumptions is sufficient to prove density-1-bounding.

We also consider a historic difficulty in constructing a potential counterexample: By previous results [7] any generic degree that is not density-1-bounding must be quasiminimal, so in particular, any construction of a non-density-1-bounding generic degree must use a method that is able to construct a quasiminimal generic degree. However, all previously known examples of quasiminimal sets are also density-1, and so trivially density-1-bounding. We provide several examples of non-density-1 sets that are quasiminimal.

Using cofinite and mod-finite reducibility, we extend our results to the uniform coarse degrees, and to the nonuniform generic degrees. We define all of the above terms, and we provide independent motivation for the study of each of them.

Combined with a concurrently written paper of Hirschfeldt, Jockusch, Kuyper, and Schupp [4], this paper provides a characterization of the level of randomness required to ensure quasiminimality in the uniform and nonuniform coarse and generic degrees.

We introduce the concept of a locally finite abstract elementary class and develop the theory of disjoint$\left( { \le \lambda ,k} \right)$-amalgamation) for such classes. From this we find a family of complete ${L_{{\omega _1},\omega }}$ sentences ${\phi _r}$ that a) homogeneously characterizes ${\aleph _r}$ (improving results of Hjorth [11] and Laskowski–Shelah [13] and answering a question of [21]), while b) the ${\phi _r}$ provide the first examples of a class of models of a complete sentence in ${L_{{\omega _1},\omega }}$ where the spectrum of cardinals in which amalgamation holds is other that none or all.

We analyze the set-theoretic strength of determinacy for levels of the Borel hierarchy of the form $\Sigma _{1 + \alpha + 3}^0 $, for α < ω1. Well-known results of H. Friedman and D.A. Martin have shown this determinacy to require α + 1 iterations of the Power Set Axiom, but we ask what additional ambient set theory is strictly necessary. To this end, we isolate a family of weak reflection principles, Π1-RAPα, whose consistency strength corresponds exactly to the logical strength of ${\rm{\Sigma }}_{1 + \alpha + 3}^0 $ determinacy, for $\alpha < \omega _1^{CK} $. This yields a characterization of the levels of L by or at which winning strategies in these games must be constructed. When α = 0, we have the following concise result: The least θ so that all winning strategies in ${\rm{\Sigma }}_4^0 $ games belong to Lθ+1 is the least so that $L_\theta \models {\rm{``}}{\cal P}\left( \omega \right)$ exists, and all wellfounded trees are ranked”.

We extend Solovay’s theorem about definable subsets of the Baire space to the generalized Baire space λλ, where λ is an uncountable cardinal with λ<λ= λ. In the first main theorem, we show that the perfect set property for all subsets of λλ that are definable from elements of λOrd is consistent relative to the existence of an inaccessible cardinal above λ. In the second main theorem, we introduce a Banach–Mazur type game of length λ and show that the determinacy of this game, for all subsets of λλ that are definable from elements of λOrd as winning conditions, is consistent relative to the existence of an inaccessible cardinal above λ. We further obtain some related results about definable functions on λλ and consequences of resurrection axioms for definable subsets of λλ.

The principle (*) of Sierpinski is the assertion that there is a family of functions $\left\{ {{\varphi _n}:{\omega _1} \to {\omega _1}|n \in \omega } \right\}$ such that for every $I \in {[{\omega _1}]^{{\omega _1}}}$ there is n ε ω such that ${\varphi _n}[I] = {\omega _1}$. We prove that this principle holds if there is a nonmeager set of size ω1 answering question of Arnold W. Miller. Combining our result with a theorem of Miller it then follows that (*) is equivalent to $non\left( {\cal M} \right) = {\omega _1}$. Miller also proved that the principle of Sierpinki is equivalent to the existence of a weak version of a Luzin set, we will construct a model where all of these sets are meager yet $non\left( {\cal M} \right) = {\omega _1}$.

In this article we introduce and study hyperclass-forcing (where the conditions of the forcing notion are themselves classes) in the context of an extension of Morse-Kelley class theory, called MK**. We define this forcing by using a symmetry between MK** models and models of ZFC− plus there exists a strongly inaccessible cardinal (called SetMK**). We develop a coding between β-models ${\cal M}$ of MK** and transitive models M+ of SetMK** which will allow us to go from ${\cal M}$ to M+ and vice versa. So instead of forcing with a hyperclass in MK** we can force over the corresponding SetMK** model with a class of conditions. For class-forcing to work in the context of ZFC− we show that the SetMK** model M+ can be forced to look like LK*[X], where κ* is the height of M+, κ strongly inaccessible in M+ and $X \subseteq \kappa$. Over such a model we can apply definable class forcing and we arrive at an extension of M+ from which we can go back to the corresponding β-model of MK**, which will in turn be an extension of the original ${\cal M}$. Our main result combines hyperclass forcing with coding methods of [3] and [4] to show that every β-model of MK** can be extended to a minimal such model of MK** with the same ordinals. A simpler version of the proof also provides a new and analogous minimality result for models of second-order arithmetic.

We develop the theory of Krull dimension for S4-algebras and Heyting algebras. This leads to the concept of modal Krull dimension for topological spaces. We compare modal Krull dimension to other well-known dimension functions, and show that it can detect differences between topological spaces that Krull dimension is unable to detect. We prove that for a T1-space to have a finite modal Krull dimension can be described by an appropriate generalization of the well-known concept of a nodec space. This, in turn, can be described by modal formulas zemn which generalize the well-known Zeman formula zem. We show that the modal logic S4.Zn := S4 + zemn is the basic modal logic of T1-spaces of modal Krull dimension ≤ n, and we construct a countable dense-in-itself ω-resolvable Tychonoff space Zn of modal Krull dimension n such that S4.Zn is complete with respect to Zn. This yields a version of the McKinsey-Tarski theorem for S4.Zn. We also show that no logic in the interval [S4n+1S4.Zn) is complete with respect to any class of T1-spaces.

We prove that for p-optimal fields (a very large subclass of p-minimal fields containing all the known examples) a cell decomposition theorem follows from methods going back to Denef’s paper [7]. We derive from it the existence of definable Skolem functions and strong p-minimality. Then we turn to strongly p-minimal fields satisfying the Extreme Value Property—a property which in particular holds in fields which are elementarily equivalent to a p-adic one. For such fields K, we prove that every definable subset of K × Kd whose fibers over K are inverse images by the valuation of subsets of the value group is semialgebraic. Combining the two we get a preparation theorem for definable functions on p-optimal fields satisfying the Extreme Value Property, from which it follows that infinite sets definable over such fields are in definable bijection iff they have the same dimension.

It is shown that Tarski’s set of ten axioms for the calculus of relations is independent in the sense that no axiom can be derived from the remaining axioms. It is also shown that by modifying one of Tarski’s axioms slightly, and in fact by replacing the right-hand distributive law for relative multiplication with its left-hand version, we arrive at an equivalent set of axioms which is redundant in the sense that one of the axioms, namely the second involution law, is derivable from the other axioms. The set of remaining axioms is independent. Finally, it is shown that if both the left-hand and right-hand distributive laws for relative multiplication are included in the set of axioms, then two of Tarski’s other axioms become redundant, namely the second involution law and the distributive law for converse. The set of remaining axioms is independent and equivalent to Tarski’s axiom system.

Let S be the group of finitely supported permutations of a countably infinite set. Let $K[S]$ be the group algebra of S over a field K of characteristic 0. According to a theorem of Formanek and Lawrence, $K[S]$ satisfies the ascending chain condition for two-sided ideals. We study the reverse mathematics of this theorem, proving its equivalence over $RC{A_0}$ (or even over $RCA_0^{\rm{*}}$) to the statement that ${\omega ^\omega }$ is well ordered. Our equivalence proof proceeds via the statement that the Young diagrams form a well partial ordering.

In the context of abstract elementary classes (AECs) with a monster model, several possible definitions of superstability have appeared in the literature. Among them are no long splitting chains, uniqueness of limit models, and solvability. Under the assumption that the class is tame and stable, we show that (asymptotically) no long splitting chains implies solvability and uniqueness of limit models implies no long splitting chains. Using known implications, we can then conclude that all the previously-mentioned definitions (and more) are equivalent:

• Corollary.LetKbe a tame AEC with a monster model. Assume thatKis stable in a proper class of cardinals. The following are equivalent:

  1. (1) For all high-enough λ,Khas no long splitting chains.

  2. (2) For all high-enough λ, there exists a good λ-frame on a skeleton ofKλ.

  3. (3) For all high-enough λ,Khas a unique limit model of cardinality λ.

  4. (4) For all high-enough λ,Khas a superlimit model of cardinality λ.

  5. (5) For all high-enough λ, the union of any increasing chain of λ-saturated models is λ-saturated.

  6. (6) There exists μ such that for all high-enough λ,Kis (λ,μ) -solvable.

This gives evidence that there is a clear notion of superstability in the framework of tame AECs with a monster model.

In [8], the third author defined a reducibility $\le _w^{\rm{*}}$ that lets us compare the computing power of structures of any cardinality. In [6], the first two authors showed that the ordered field of reals ${\cal R}$ lies strictly above certain related structures. In the present paper, we show that $\left( {{\cal R},exp} \right) \equiv _w^{\rm{*}}{\cal R}$ . More generally, for the weak-looking structure ${\cal R}$ ℚ consisting of the real numbers with just the ordering and constants naming the rationals, all o-minimal expansions of ${\cal R}$ ℚ are equivalent to ${\cal R}$ . Using this, we show that for any analytic function f, $\left( {{\cal R},f} \right) \equiv _w^{\rm{*}}{\cal R}$ . (This is so even if $\left( {{\cal R},f} \right)$ is not o-minimal.)

We study the problem of extending an abstract independence notion for types of singletons (what Shelah calls a good frame) to longer types. Working in the framework of tame abstract elementary classes, we show that good frames can always be extended to types of independent sequences. As an application, we show that tameness and a good frame imply Shelah’s notion of dimension is well-behaved, complementing previous work of Jarden and Sitton. We also improve a result of the first author on extending a frame to larger models.

In this paper we shall prove that any 2-transitive finitely homogeneous structure with a supersimple theory satisfying a generalized amalgamation property is a random structure. In particular, this adapts a result of Koponen for binary homogeneous structures to arbitrary ones without binary relations. Furthermore, we point out a relation between generalized amalgamation, triviality and quantifier elimination in simple theories.

This paper considers a generalisation of selection functions over an arbitrary strong monad T, as functionals of type $J_R^T X = (X \to R) \to TX$. It is assumed throughout that R is a T-algebra. We show that $J_R^T$ is also a strong monad, and that it embeds into the continuation monad $K_R X = (X \to R) \to R$. We use this to derive that the explicitly controlled product of T-selection functions is definable from the explicitly controlled product of quantifiers, and hence from Spector’s bar recursion. We then prove several properties of this product in the special case when T is the finite powerset monad ${\cal P}_{\rm{f}} \left( \cdot \right)$. These are used to show that when $TX = {\cal P}_{\rm{f}} \left( X \right)$ the explicitly controlled product of T-selection functions calculates a witness to the Herbrand functional interpretation of the double negation shift.

We show that dp-minimal valued fields are henselian and give classifications of dp-minimal ordered abelian groups and dp-minimal ordered fields without additional structure.

In this paper, we prove the decidability of the theory of ℚp in the language (+, −,⋅, 0, 1, Pn(n ∈ ℕ)) expanded by a predicate for the multiplicative subgroup nℤ (where n is a fixed integer). There are two cases: if $v_p \left( n \right) > 0$ then the group determines a cross-section and we get an axiomatization of the theory and a result of quantifier elimination. If $v_p \left( n \right) = 0$, then we use the Mann property of the group to get an axiomatization of the theory.

Given a scattered space $\mathfrak{X} = \left( {X,\tau } \right)$ and an ordinal λ, we define a topology $\tau _{ + \lambda } $ in such a way that τ +0 = τ and, when $\mathfrak{X}$ is an ordinal with the initial segment topology, the resulting sequence {τ +λ}λ∈Ord coincides with the family of topologies $\left\{ {\mathcal{I}_\lambda } \right\}_{\lambda \in Ord} $ used by Icard, Joosten, and the second author to provide semantics for polymodal provability logics.

We prove that given any scattered space $\mathfrak{X}$ of large-enough rank and any ordinal λ > 0, GL is strongly complete for τ + λ. The special case where $\mathfrak{X} = \omega ^\omega + 1$ and λ = 1 yields a strengthening of a theorem of Abashidze and Blass.

We show that metric abstract elementary classes (mAECs) are, in the sense of [15], coherent accessible categories with directed colimits, with concrete ℵ1-directed colimits and concrete monomorphisms. More broadly, we define a notion of κ-concrete AEC—an AEC-like category in which only the κ-directed colimits need be concrete—and develop the theory of such categories, beginning with a category-theoretic analogue of Shelah’s Presentation Theorem and a proof of the existence of an Ehrenfeucht–Mostowski functor in case the category is large. For mAECs in particular, arguments refining those in [15] yield a proof that any categorical mAEC is μ-d-stable in many cardinals below the categoricity cardinal.

A relational structure is called reversible iff each bijective endomorphism (condensation) of that structure is an automorphism. We show that reversibility is an invariant of some forms of L∞ω −bi-interpretability, implying that the condensation monoids of structures are topologically isomorphic. Applying these results, we prove that, in particular, all orbits of ultrahomogeneous tournaments and reversible ultrahomogeneous m-uniform hypergraphs are reversible relations and that the same holds for the orbits of reversible ultrahomogeneous digraphs definable by formulas which are not R-negative.