We further develop a previously introduced method of constructing forcing notions with the help of morasses. There are two new results: (1) If there is a simplified (ω1, 1)-morass, then there exists a ccc forcing of size ω1 that adds an ω2-Suslin tree. (2) If there is a simplified (ω1, 2)-morass, then there exists a ccc forcing of size ω1 that adds a 0-dimensional Hausdorff topology τ on ω3 which has spread s(τ) = ω1. While (2) is the main result of the paper, (1) is only an improvement of a previous result, which is based on a simple observation. Both forcings preserve GCH. To show that the method can be changed to produce models where CH fails, we give an alternative construction of Koszmider's model in which there is a chain 〈Xα ∣ α < ω2〉 such that Xα ⊆ ω1. Xβ – Xα is finite and Xα – Xβ has size ω1 for all β < α < ω2.

If the bounded proper forcing axiom BPFA holds and ω1 = ω1L, then there is a lightface Σ31 well-ordering of the reals. The argument combines a well-ordering due to Caicedo-Veličković with an absoluteness result for models of MA in the spirit of “David's trick.” We also present a general coding scheme that allows us to show that BPFA is equiconsistent with R being lightface Σ41 for many “consistently locally certified” relations R on ℝ. This is accomplished through a use of David's trick and a coding through the Σ2 stable ordinals of L.

Say that an incomplete d.r.e. degree has almost universal cupping property, if it cups all the r.e. degrees not below it to 0′. In this paper, we construct such a degree d, with all the r.e. degrees not cupping d to 0′ bounded by some r.e. degree strictly below d. The construction itself is an interesting 0″′ argument and this new structural property can be used to study final segments of various degree structures in the Ershov hierarchy.

We present a method to iterate finitely splitting lim-sup tree forcings along non-wellfounded linear orders. As an application, we introduce a new method to force (weak) measurability of all definable sets with respect to a certain (non-ccc) ideal.

Let denote the collection of all Π10 classes, ordered by inclusion. A collection of Turing degrees in is called invariant over if there is some collection of Π10 classes representing exactly the degrees such that is invariant under automorphisms of . Herein we expand the known degree invariant classes of , previously including only {0} and the array noncomputable degrees, to include all highn and non-lown degrees for n > 2. This is a corollary to a very general definability result. The result is carried out in a substructure G of , within which the techniques used model those used by Cholak and Harrington [6] to obtain the same definability for the c.e. sets. We work back and forth between G and to show that this definability in G gives the desired degree invariance over .

We use the notions of effective dimension and Kolmogorov complexity to describe a geometry on the set of infinite binary sequences. Geometric concepts that we define and use include angle, projections and scalar multiplication. A question related to compressibility is addressed using these ideas.

Let (K, v) be a henselian valued field of characteristic 0. Then K admits a definable partition on each piece of which the leading term of a polynomial in one variable can be computed as a definable function of the leading term of a linear map. The main step in obtaining this partition is an answer to the question, given a polynomial f(x) ∈ K[x], what is v(f(x))?

Two applications are given: first, a constructive quantifier elimination relative to the leading terms, suggesting a relative decision procedure; second, a presentation of every definable subset of K as the pullback of a definable set in the leading terms subjected to a linear translation.

Varieties like groups, rings, or Boolean algebras have the property that, in any of their members, the lattice of congruences is isomorphic to a lattice of more manageable objects, for example normal subgroups of groups, two-sided ideals of rings, filters (or ideals) of Boolean algebras. Abstract algebraic logic can explain these phenomena at a rather satisfactory level of generality: in every member A of a τ-regular variety the lattice of congruences of A is isomorphic to the lattice of deductive filters on A of the τ-assertional logic of . Moreover, if has a constant 1 in its type and is 1-subtractive, the deductive filters on A ∈ of the 1-assertional logic of coincide with the -ideals of A in the sense of Gumm and Ursini, for which we have a manageable concept of ideal generation.

However, there are isomorphism theorems, for example, in the theories of residuated lattices, pseudointerior algebras and quasi-MV algebras that cannot be subsumed by these general results. The aim of the present paper is to appropriately generalise the concepts of subtractivity and τ-regularity in such a way as to shed some light on the deep reason behind such theorems. The tools and concepts we develop hereby provide a common umbrella for the algebraic investigation of several families of logics, including substructural logics, modal logics, quantum logics, and logics of constructive mathematics.

We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a δ20 set B >tt ∅′ such that there is no c.e. set A with A′ ≡wttB. We also show that there is a Σ20 set C >tt ∅′ such that there is no δ20 set D with D′ ≡wttC.

We investigate extensions of S. Solecki's theorem on closing off finite partial isometries of metric spaces [11] and obtain the following exact equivalence: any action of a discrete group Γ by isometries of a metric space is finitely approximable if and only if any product of finitely generated subgroups of Γ is closed in the profinite topology on Γ.

Given a finitely generated group Γ we study the space Isom(Γ, ) of all actions of Γ by isometries of the rational Urysohn metric space , where Isom (Γ, ) is equipped with the topology it inherits seen as a closed subset of Isom . When Γ is the free group on n generators this space is just Isom , but is in general significantly more complicated. We prove that when Γ is finitely generated Abelian there is a generic point in Isom(Γ, ), i.e., there is a comeagre set of mutually conjugate isometric actions of Γ on .

We prove the statement in the title.

We prove that the additive group of the rationals does not have an automatic presentation. The proof also applies to certain other abelian groups, for example, torsion-free groups that are p-divisible for infinitely many primes p, or groups of the form ⊕pϵIZ(p∞), where I is an infinite set of primes.

The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar results also for tree automatic structures. These findings close the gaps left open in [28] by improving both the lower and the upper bounds.

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.

We study relationships between certain algebraic properties of groups and rings definable in a first order structure or *-closed in a compact G-space. As a consequence, we obtain a few structural results about ω-categorical rings as well as about small, nm-stable compact G-rings, and we also obtain surprising relationships between some conjectures concerning small profinite groups.

We show that the theory of the real field with a generic real power function is decidable, relative to an oracle for the rational cut of the exponent of the power function. We also show the existence of generic computable real numbers, hence providing an example of a decidable o-minimal proper expansion of the real field by an analytic function.

The transitive closure of a binary relation R can be thought of as the best possible approximation of R “from above” by a transitive relation. We consider the question of approximating a relation from below by transitive relations. Our main result is that every thick relation (a relation whose complement contains no infinite chain) on a countable set has a transitive thick subrelation. This allows for a solution to a problem arising from previous work by the author and Alan Taylor. We also exhibit a thick relation on an uncountable set with no transitive thick subrelation.

We show that MRP + MA implies that ITP(λ,ω2) holds for all cardinal λ ≥ ω2. This generalizes a result by Weiβ who showed that PFA implies that ITP(λ, ω2) holds for all cardinal λ ≥ ω2. Consequently any of the known methods to prove MRP + MA consistent relative to some large cardinal hypothesis requires the existence of a strongly compact cardinal. Moreover if one wants to force MRP + MA with a proper forcing, it requires at least a supercompact cardinal. We also study the relationship between MRP and some weak versions of square. We show that MRP implies the failure of □(λ, ω) for all λ ≥ ω2 and we give a direct proof that MRP + MA implies the failure of □(λ, ω1) for all λ ≥ ω2.

We clarify and correct some statements and results in the literature concerning unimodularity in the sense of Hrushovski [7], and measurability in the sense of Macpherson and Steinhorn [8], pointing out in particular that the two notions coincide for strongly minimal structures and that another property from [7] is strictly weaker, as well as “completing” Elwes' proof [5] that measurability implies 1-basedness for stable theories.