It is known that for all finite n ≥ 5, there are relation algebras with n-dimensional relational bases but no weak representations. We prove that conversely, there are finite weakly representable relation algebras with no n-dimensional relational bases. In symbols: neither of the classes RAn and wRRA contains the other.

We locate winning strategies for various -games in the L-hierarchy in order to prove the following:

Theorem 1. KP + Σ2-Comprehension -Determinacy.”

Alternatively: “there is a β-model of-Determinacy.” The implication is not reversible. (The antecedent here may be replaced with instances of Comprehension with only -lightface definable parameters—or even weaker theories.)

Theorem 2. KP + Δ2-Comprehension + Σ2-Replacement + -Determinacy.

(Here AQI is the assertion that every arithmetical quasi-inductive definition converges.) Alternatively: -Determinacy.

Hence the theories: , and are in strictly descending order of strength.

This paper introduces a natural extension of Kolchin's differential Galois theory to positive characteristic iterative differential fields, generalizing to the non-linear case the iterative Picard–Vessiot theory recently developed by Matzat and van der Put. We use the methods and framework provided by the model theory of iterative differential fields. We offer a definition of strongly normal extension of iterative differential fields, and then prove that these extensions have good Galois theory and that a G-primitive element theorem holds. In addition, making use of the basic theory of arc spaces of algebraic groups, we define iterative logarithmic equations, finally proving that our strongly normal extensions are Galois extensions for these equations.

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.

We employ an infinite-signature Hrushovski amalgamation construction to yield two results in Recursive Model Theory. The first result, that there exists a strongly minimal theory whose only recursively presentable models are the prime and saturated models, adds a new spectrum to the list of known possible spectra. The second result, that there exists a strongly minimal theory in a finite language whose only recursively presentable model is saturated, gives the second non-trivial example of a spectrum produced in a finite language.

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.

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn–Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense.

We prove that the set of all Polish groups admitting a compatible complete left-invariant metric (called CLI) is coanalytic non-Borel as a subset of a standard Borel space of all Polish groups. As an application of this result, we show that there does not exist a weakly universal CLI group. This, in particular, answers in the negative a question of H.Becker.

We show basic facts about dp-minimal ordered structures. The main results are: dp-minimal groups are abelian-by-finite-exponent, in a divisible ordered dp-minimal group, any infinite set has nonempty interior, and any theory of pure tree is dp-minimal.

A set of natural numbers B is computably enumerable in and strictly above (or c.e.a. for short) another set C if C <TB and B is computably enumerable in C. A Turing degree b is c.e.a. c if b and c respectively contain B and C as above. In this paper, it is shown that if b is c.e.a. c then b is c.e.a. some 1-generic g.

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 prove that for every Σ20 enumeration degree b there exists a noncuppable Σ20 degree a > 0e such that and . This allows us to deduce, from results on the high/low jump hierarchy in the local Turing degrees and the jump preserving properties of the standard embedding , that there exist Σ20 noncuppable enumeration degrees at every possible—i.e., above low1—level of the high/low jump hierarchy in the context of .

Let κ < λ be regular uncountable cardinals. Using a finite support iteration (in fact a matrix iteration) of ccc posets we obtain the consistency of . If μ is a measurable cardinal and μ < κ < λ, then using similar techniques we obtain the consistency of .

This paper studies several systems of the transfinite iteration and autonomous progression of self-applicable truth and determines their proof-theoretic strength.

We show that there is a complete, consistent Borel theory which has no “Borel model” in the following strong sense: There is no structure satisfying the theory for which the elements of the structure are equivalence classes under some Borel equivalence relation and the interpretations of the relations and function symbols are uniformly Borel.

We also investigate Borel isomorphisms between Borel structures.

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 introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a ≤wtt version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very close to the definition of superlow cuppability.

Further, we study the strongly prompt c.e. sets in the context of other notions related promptness, superlowness, and cupping. In particular, we show that every benign cost function has a strongly prompt set which obeys it, providing an analogue to the known result that every cost function with the limit condition has a prompt set which obeys it. We also study the effect that lowness properties have on the behaviour of a set under the join operator. In particular we construct an array noncomputable c.e. set whose join with every low c.e. set is low.

Assuming the existence of a weakly compact hypermeasurable cardinal we prove that in some forcing extension ℵω is a strong limit cardinal and ℵω+2 has the tree property. This improves a result of Matthew Foreman (see [2]).

For any group satisfying a suitable chain condition, we construct a finitely additive measure on it that is invariant under certain actions.

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