We begin the fine analysis of nonBorel pointclasses. Working in ZFC + DET$\left( {_1^1 } \right)$, we describe the Wadge hierarchy of the class of increasing differences of co-analytic subsets of the Baire space by extending results obtained by Louveau ([5]) for the Borel sets.

One partially ordered set, Q, is a Tukey quotient of another, P, if there is a map (a Tukey quotient) $\phi :P \to Q$ carrying cofinal sets of P to cofinal sets of Q. Two partial orders which are mutual Tukey quotients of each other are said to be Tukey equivalent. Let ${\cal D}_{\rm{}} $ be the partially ordered set of Tukey equivalence classes of directed sets of size $ \le {\rm{}}$. It is shown that ${\cal D}_{\rm{}} $ contains an antichain of size $2^{\rm{}} $, and so has size $2^{\rm{}} $. The elements of the antichain are of the form ${\cal K}\left( M \right)$, the set of compact subsets of a separable metrizable space M, ordered by inclusion. The order structure of such ${\cal K}\left( M \right)$’s under Tukey quotients is investigated. Relative Tukey quotients are introduced. Applications are given to function spaces and to the complexity of weakly countably determined Banach spaces and Gul’ko compacta.

We extend Ahlbrandt and Ziegler’s reconstruction results ([1]) to the metric setting: we show that separably categorical structures are determined, up to bi-interpretability, by their automorphism groups.

We consider a group G that does not have the independence property and study the definability of certain subgroups of G, using parameters from a fixed elementary extension G of G. If X is a definable subset of G, its trace on G is called an externally definable subset. If H is a definable subgroup of G, we call its trace on G an external subgroup. We show the following. For any subset A of G and any external subgroup H of G, the centraliser of A, the A-core of H and the iterated centres of H are external subgroups. The normaliser of H and the iterated centralisers of A are externally definable. A soluble subgroup S of derived length ℓ is contained in an S-invariant externally definable soluble subgroup of G of derived length ℓ. The subgroup S is also contained in an externally definable subgroup X ∩ G of G such that X generates a soluble subgroup of G of derived length ℓ. Analogue results are discussed when G is merely a type definable group in a structure that does not have the independence property.

Quasiminimal pregeometry classes were introduced by [6] to isolate the model theoretical core of several interesting examples. He proves that a quasiminimal pregeometry class satisfying an additional axiom, called excellence, is categorical in all uncountable cardinalities. Recently, [2] showed that the excellence axiom follows from the rest of the axioms. In this paper we present a direct proof of the categoricity result without using excellence.

We say that a theory T is intermediate under effective reducibility if the isomorphism problems among its computable models is neither hyperarithmetic nor on top under effective reducibility. We prove that if an infinitary sentence T is uniformly effectively dense, a property we define in the paper, then no extension of it is intermediate, at least when relativized to every oracle in a cone. As an application we show that no infinitary sentence whose models are all linear orderings is intermediate under effective reducibility relative to every oracle in a cone.

We show that any simple group of Morley rank 4 must be a bad group with no proper definable subgroups of rank larger than 1. We also give an application to groups acting on sets of Morley rank 2.

All spaces are assumed to be separable and metrizable. Our main result is that the statement “For every space X, every closed subset of X has the perfect set property if and only if every analytic subset of X has the perfect set property” is equivalent to b > ω1 (hence, in particular, it is independent of ZFC). This, together with a theorem of Solecki and an example of Miller, will allow us to determine the status of the statement “For every space X, if every Γ subset of X has the perfect set property then every Γ′ subset of X has the perfect set property” as Γ, Γ′ range over all pointclasses of complexity at most analytic or coanalytic.

Along the way, we define and investigate a property of independent interest. We will say that a subset W of 2ω has the Grinzing property if it is uncountable and for every uncountable Y ⊆ W there exists an uncountable collection consisting of uncountable subsets of Y with pairwise disjoint closures in 2ω. The following theorems hold.

1. (1) There exists a subset of 2ω with the Grinzing property.

2. (2) Assume MA + ¬CH. Then 2ω has the Grinzing property.

3. (3) Assume CH. Then 2ω does not have the Grinzing property.

We show that provability in the implicational fragment of relevance logic is complete for doubly exponential time, using reductions to and from coverability in branching vector addition systems.

Pseudoexponential fields are exponential fields similar to complex exponentiation which satisfy the Schanuel Property, i.e., the abstract statement of Schanuel’s Conjecture, and an adapted form of existential closure.

Here we show that if we remove the Schanuel Property and just care about existential closure, it is possible to create several existentially closed exponential functions on the algebraic numbers that still have similarities with complex exponentiation. The main difficulties are related to the arithmetic of algebraic numbers, and they can be overcome with known results about specialisations of multiplicatively independent functions on algebraic varieties.

We consider natural ${\rm{\Sigma }}_2^1$ definable analogues of many of the classical statements that have been shown to be equivalent to CH. It is shown that these ${\rm{\Sigma }}_2^1$ analogues are equivalent to that all reals are constructible. We also prove two partition relations for ${\rm{\Sigma }}_2^1$ colourings which hold precisely when there is a non-constructible real.

A generic computation of a subset A of ℕ is a computation which correctly computes most of the bits of A, but which potentially does not halt on all inputs. The motivation for this concept is derived from complexity theory, where it has been noticed that frequently, it is more important to know how difficult a type of problem is in the general case than how difficult it is in the worst case. When we study this concept from a recursion theoretic point of view, to create a transitive relationship, we are forced to consider oracles that sometimes fail to give answers when asked questions. Unfortunately, this makes working in the generic degrees quite difficult. Indeed, we show that generic reduction is $\Pi _1^1$―complete. To help avoid this difficulty, we work with the generic degrees of density-1 reals. We demonstrate how an understanding of these degrees leads to a greater understanding of the overall structure of the generic degrees, and we also use these density-1 sets to provide a new a characterization of the hyperartithmetical Turing degrees.

We consider ${\cal S}$, the class of finite semilattices; ${\cal T}$, the class of finite treeable semilattices; and ${{\cal T}_m}$, the subclass of ${\cal T}$ which contains trees with branching bounded by m. We prove that ${\cal E}{\cal S}$, the class of finite lattices with linear extensions, is a Ramsey class. We calculate Ramsey degrees for structures in ${\cal S}$, ${\cal T}$, and ${{\cal T}_m}$. In addition to this we give a topological interpretation of our results and we apply our result to canonization of linear orderings on finite semilattices. In particular, we give an example of a Fraïssé class ${\cal K}$ which is not a Hrushovski class, and for which the automorphism group of the Fraïssé limit of ${\cal K}$ is not extremely amenable (with the infinite universal minimal flow) but is uniquely ergodic.

We give model theoretic criteria for the existence of ∃∀ and ∀∃- formulas in the ring language to define uniformly the valuation rings ${\cal O}$ of models $\left( {K,\,{\cal O}} \right)$ of an elementary theory Σ of henselian valued fields. As one of the applications we obtain the existence of an ∃∀-formula defining uniformly the valuation rings ${\cal O}$ of valued henselian fields $\left( {K,\,{\cal O}} \right)$ whose residue class field k is finite, pseudofinite, or hilbertian. We also obtain ∀∃-formulas φ2 and φ4 such that φ2 defines uniformly k[[t]] in k(t) whenever k is finite or the function field of a real or complex curve, and φ4 replaces φ2 if k is any number field.

An expansion of a definably complete field either defines a discrete subring, or the image of every definable discrete set under every definable map is nowhere dense. As an application we show a definable version of Lebesgue’s differentiation theorem.

Soare [20] proved that the maximal sets form an orbit in ${\cal E}$. We consider here ${\cal D}$-maximal sets, generalizations of maximal sets introduced by Herrmann and Kummer [12]. Some orbits of ${\cal D}$-maximal sets are well understood, e.g., hemimaximal sets [8], but many are not. The goal of this paper is to define new invariants on computably enumerable sets and to use them to give a complete nontrivial classification of the ${\cal D}$-maximal sets. Although these invariants help us to better understand the ${\cal D}$-maximal sets, we use them to show that several classes of ${\cal D}$-maximal sets break into infinitely many orbits.

We present a forcing to obtain a localized version of Local Club Condensation, a generalized Condensation principle introduced by Sy Friedman and the first author in [3] and [5]. This forcing will have properties nicer than the forcings to obtain this localized version that could be derived from the forcings presented in either [3] or [5]. We also strongly simplify the related proofs provided in [3] and [5]. Moreover our forcing will be capable of introducing this localized principle at κ while simultaneously performing collapses to make κ become the successor of any given smaller regular cardinal. This will be particularly useful when κ has large cardinal properties in the ground model. We will apply this to measure how much L-likeness is implied by Local Club Condensation and related principles. We show that Local Club Condensation at κ+ is consistent with ¬☐κ whenever κ is regular and uncountable, generalizing and improving a result of the third author in [14], and that if κ ≥ ω2 is regular, CC(κ+) - Chang’s Conjecture at κ+ - is consistent with Local Club Condensation at κ+, both under suitable large cardinal consistency assumptions.