We characterise strongly minimal groups interpretable in elementary extensions of compact complex analytic spaces.

We consider two theories of “bad fields” constructed by B.Poizat using Hrushovski's amalgamation and show that these theories have natural models representable as the field of complex numbers with a distinguished subset given as a union of countably many real analytic curves. One of the two examples is based on the complex exponentiation and the proof assumes Schanuel's conjecture.

One concern of descriptive set theory is the classification of definable sets of reals. Taken loosely ‘definable’ can mean anything from projective to formally describable in the language of Zermelo-Fraenkel set theory (ZF). Recursiveness, in the case of Kleene recursion, can be a particularly informative notion of definability. Sets of integers, for example, are categorized by their positions in the upper semilattice of Turing degrees, and the algorithms for computing their characteristic functions may be taken as their defining presentations. In turn it is interesting to position the common fauna of descriptive set theory in the upper semilattice of Kleene degrees. In so doing not only do we gain a perspective on the complexity of those sets common to the study of descriptive set theory but also a refinement of the theory of analytic sets of reals. The primary concern of this paper is to calculate the relative complexity of several notable coanalytic sets of reals and display (under suitable set theoretic hypothesis) several natural solutions to Post's problem for Kleene recursion.

For sets of reals A and B one says A is Kleene recursive in B (written A ≤KB) iff there is a real y so that the characteristic function XA of A is recursive (in the sense of Kleene [1959]) in y, XB and the existential integer quantifier ∃; i.e. there is an integer e so that XA(x) ≃ {e}(x, y, XB, ≃). Intuitively, membership of a real x ϵ ωω in A can be decided from an oracle for x, y and B using a computing machine with a countably infinite memory and an ability to search and manipulate that memory in finite time. A set is Kleene semirecursive in B if it is the domain of an integer valued partial function recursive in y, XB and ≃ for some real y.

Let (M, ≤,…) denote a Boolean ordered o-minimal structure. We prove that a Boolean subalgebra of M determined by an algebraically closed subset contains no dense atoms. We show that Boolean algebras with finitely many atoms do not admit proper expansions with o-minimal theory. The proof involves decomposition of any definable set into finitely many pairwise disjoint cells, i.e., definable sets of an especially simple nature. This leads to the conclusion that Boolean ordered structures with o-minimal theories are essentially bidefinable with Boolean algebras with finitely many atoms, expanded by naming constants. We also discuss the problem of existence of proper o-minimal expansions of Boolean algebras.

We shall show the consistency of CH+⌝(+) and CH+(+)+there are no club guessing sequences on ω1. We shall also prove that ◊+ does not imply the existence of a strong club guessing sequence on ω1.

One of the fundamental results of descriptive complexity theory, due to Immerman [13] and Vardi [18], says that a class of ordered finite structures is definable in fixed-point logic if, and only if, it is computable in polynomial time. Much effort has been spent on the problem of capturing polynomial time, that is, describing all polynomial time computable classes of not necessarily ordered finite structures by a logic in a similar way.

The most obvious shortcoming of fixed-point logic itself on unordered structures is that it cannot count. Immerman [14] responded to this by adding counting constructs to fixed-point logic. Although it has been proved by Cai, Fürer, and Immerman [1] that the resulting fixed-point logic with counting, denoted by IFP+C, still does not capture all of polynomial time, it does capture polynomial time on several important classes of structures (on trees, planar graphs, structures of bounded tree-width [15, 9, 10]).

The main motivation for such capturing results is that they may give a better understanding of polynomial time. But of course this requires that the logical side is well understood. We hope that our analysis of IFP+C-formulas will help to clarify the expressive power of IFP+C; in particular, we derive a normal form. Moreover, we obtain a problem complete for IFP+C under first-order reductions.

I analyze the hierarchies of the bounded and the weak bounded forcing axioms, with a focus on their versions for the class of subcomplete forcings, in terms of implications and consistency strengths. For the weak hierarchy, I provide level-by-level equiconsistencies with an appropriate hierarchy of partially remarkable cardinals. I also show that the subcomplete forcing axiom implies Larson’s ordinal reflection principle at ω2, and that its effect on the failure of weak squares is very similar to that of Martin’s Maximum.

Ramsey’s theorem asserts that every k-coloring of $[\omega ]^n$ admits an infinite monochromatic set. Whenever $n \geq 3$ , there exists a computable k-coloring of $[\omega ]^n$ whose solutions compute the halting set. On the other hand, for every computable k-coloring of $[\omega ]^2$ and every noncomputable set C, there is an infinite monochromatic set H such that $C \not \leq _T H$ . The latter property is known as cone avoidance.

In this article, we design a natural class of Ramsey-like theorems encompassing many statements studied in reverse mathematics. We prove that this class admits a maximal statement satisfying cone avoidance and use it as a criterion to re-obtain many existing proofs of cone avoidance. This maximal statement asserts the existence, for every k-coloring of $[\omega ]^n$ , of an infinite subdomain $H \subseteq \omega $ over which the coloring depends only on the sparsity of its elements. This confirms the intuition that Ramsey-like theorems compute Turing degrees only through the sparsity of its solutions.

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.

The research presented in this paper was motivated by our aim to study a problem due to J. Bourgain [3]. The problem in question concerns the uniform boundedness of the classical separation rank of the elements of a separable compact set of the first Baire class. In the sequel we shall refer to these sets (separable or non-separable) as Rosenthal compacta and we shall denote by ∝(f) the separation rank of a real-valued function f in B1(X), with X a Polish space. Notice that in [3], Bourgain has provided a positive answer to this problem in the case of K satisfying with X a compact metric space. The key ingredient in Bourgain's approach is that whenever a sequence of continuous functions pointwise converges to a function f, then the possible discontinuities of the limit function reflect a local ℓ1-structure to the sequence (fn)n. More precisely the complexity of this ℓ1-structure increases as the complexity of the discontinuities of f does. This fruitful idea was extensively studied by several authors (c.f. [5], [7], [8]) and for an exposition of the related results we refer to [1]. It is worth mentioning that A.S. Kechris and A. Louveau have invented the rank rND(f) which permits the link between the c0-structure of a sequence (fn)n of uniformly bounded continuous functions and the discontinuities of its pointwise limit. Rosenthal's c0-theorem [11] and the c0-index theorem [2] are consequences of this interaction.

Passing to the case where either (fn)n are not continuous or X is a non-compact Polish space, this nice interaction is completely lost.

We study Σ1(ω1)-definable sets (i.e., sets that are equal to the collection of all sets satisfying a certain Σ1-formula with parameter ω1 ) in the presence of large cardinals. Our results show that the existence of a Woodin cardinal and a measurable cardinal above it imply that no well-ordering of the reals is Σ1(ω1)-definable, the set of all stationary subsets of ω1 is not Σ1(ω1)-definable and the complement of every Σ1(ω1)-definable Bernstein subset of ${}_{}^{{\omega _1}}\omega _1^{}$ is not Σ1(ω1)-definable. In contrast, we show that the existence of a Woodin cardinal is compatible with the existence of a Σ1(ω1)-definable well-ordering of H(ω2) and the existence of a Δ1(ω1)-definable Bernstein subset of ${}_{}^{{\omega _1}}\omega _1^{}$. We also show that, if there are infinitely many Woodin cardinals and a measurable cardinal above them, then there is no Σ1(ω1)-definable uniformization of the club filter on ω1. Moreover, we prove a perfect set theorem for Σ1(ω1)-definable subsets of ${}_{}^{{\omega _1}}\omega _1^{}$, assuming that there is a measurable cardinal and the nonstationary ideal on ω1 is saturated. The proofs of these results use iterated generic ultrapowers and Woodin’s ℙmax-forcing. Finally, we also prove variants of some of these results for Σ1(κ)-definable subsets of κκ, in the case where κ itself has certain large cardinal properties.

A great deal of the interest in the theory of models of sets of sentences in the lower predicate calculus is due to the increasing success with which this theory has been applied to problems from algebra (see, for example [6, particularly pp. 90–103]).

The existence of nonstandard models prevents this language from being altogether appropriate for application to analysis.

Up to equivalence, a substitution in propositional logic is an endomorphism of its free algebra. On the dual space, this results in a continuous function, and whenever the space carries a natural measure one may ask about the stochastic properties of the action. In classical logic there is a strong dichotomy: while over finitely many propositional variables everything is trivial, the study of the continuous transformations of the Cantor space is the subject of an extensive literature, and is far from being a completed task. In many-valued logic this dichotomy disappears: already in the finite-variable case many interesting phenomena occur, and the present paper aims at displaying some of these.

By operations on models we show how to relate completeness with respect to permissive-nominal models to completeness with respect to nominal models with finite support. Models with finite support are a special case of permissive-nominal models, so the construction hinges on generating from an instance of the latter, some instance of the former in which sufficiently many inequalities are preserved between elements. We do this using an infinite generalisation of nominal atoms-abstraction.

The results are of interest in their own right, but also, we factor the mathematics so as to maximise the chances that it could be used off-the-shelf for other nominal reasoning systems too. Models with infinite support can be easier to work with, so it is useful to have a semi-automatic theorem to transfer results from classes of infinitely-supported nominal models to the more restricted class of models with finite support.

In conclusion, we consider different permissive-nominal syntaxes and nominal models and discuss how they relate to the results proved here.

We explore a general method based on trees of elementary submodels in order to present highly simplified proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we significantly broaden this framework by developing the corresponding technique for countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic.

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 answer a question of Garcia-Ferreira and Hrušák by consistently constructing a MAD family maximal in the Katětov order. We also answer several questions of Garcia-Ferreira.

A relational structure is called weakly atomic-compact if and only if every set Σ of atomic formulas (taken from the first-order language of the similarity type of augmented by a possibly uncountable set of additional variables as “unknowns”) is satisfiable in whenever every finite subset of Σ is so satisfiable. This notion (as well as some related ones which will be mentioned in §4) was introduced by J. Mycielski as a generalization to model theory of I. Kaplansky's notion of an algebraically compact Abelian group (cf. [5], [7], [1], [8]).

We build on an existing a term-sequent logic for the λ-calculus. We formulate a general sequent system that fully integrates αβη-reductions between untyped λ-terms into first order logic.

We prove a cut-elimination result and then offer an application of cut-elimination by giving a notion of uniform proof for λ-terms. We suggest how this allows us to view the calculus of untyped αβ-reductions as a logic programming language (as well as a functional programming language, as it is traditionally seen).

In this paper we investigate the connections between categoricity and ranks. We use stability theory to prove some old and new results.