Let {We}e∈ω be a standard enumeration of the recursively enumerable (r. e.) subsets of ω = {0, 1, 2, …}. The lattice of recursively enumerable sets, is the structure ({We}e∈ω, ∪, ∩). is the sublattice of consisting of the recursive sets.

Suppose is a lattice of subsets of ω. ≡ is said to be a congruence relation on if ≡ is an equivalence relation on and if for all U, U′ ∈ and V, V ∈ , if U ≡ U′ and V ≡ V′ then U ∪ U′ ≡ V ∪ V′ and U ∩ U′ ≡ V ∩ V′. [U] = {V ∈ | V ≡ U} is the equivalence class of U. If ≡ is a congruence relation on , the elements of the quotient lattice / ≡ are the equivalence classes of ≡. [U] ∪ [V] is defined as [U ∪ V], and [U] ∩ [V] is defined as [U ∩ V].

The quotient lattices of (or of some sublattice ) correspond naturally with the congruence relations which give rise to them, and in turn the congruence relations of sublattices of can be characterized in part by their computational complexity. The aim of the present paper is to characterize congruence relations in some of the most important complexity classes.

Each Girard quantale (i.e., commutative quantale with a selected dualizing element) provides a support for a semantics for linear propositional formulas (but not for linear derivations). Several constructions of Girard quantales are known. We give two more constructions, one using an arbitrary partially ordered monoid and one using a partially ordered group (both commutative). In both cases the semantics can be controlled be a relation between pairs of elements of the support and formulas. This gives us a neat way of handling duality.

It is proved that if 1 < m < 2p ≤ n for some integer p then the elementary theories of posets of m-c.e. and n-c.e. e-degrees are distinct. It is proved also that the structures 〈2n, ≤, 〉 and 〈2n, ≤. P〉 are not elementary equivalent where P is the predicate P(a) = “a is a e-degree”.

We prove the following theorems:

1. If X ⊆ 2ω is a γ-set and Y ⊆2ω is a strongly meager set, then X + Y is Ramsey null.

2. If X ⊆2ω is a γ-set and Y belongs to the class of sets, then the algebraic sum X + Y is an set as well.

3. Under CH there exists a set X ∈ MGR* which is not Ramsey null.

This paper develops the very basic notions of analysis in a weak second-order theory of arithmetic BTFA whose provably total functions are the polynomial time computable functions. We formalize within BTFA the real number system and the notion of a continuous real function of a real variable. The theory BTFA is able to prove the intermediate value theorem, wherefore it follows that the system of real numbers is a real closed ordered field. In the last section of the paper, we show how to interpret the theory BTFA in Robinson's theory of arithmetic Q. This fact entails that the elementary theory of the real closed ordered fields is interpretable in Q.

Any model of ZFC + GCH has a generic extension (made with a poset of size ℵ2) in which the following hold: there exists a-well ordering of the reals, The proof consists in iterating posets designed to change at will the guessing properties of ladder systems on ω1. Therefore, the study of such ladders is a main concern of this article.

We use a new version of the Definability Theorem of Beth in order to unify classical theorems of Yuri Matiyasevich and Jan Denef in one structural statement. We give similar forms for other important definability results from Arithmetic and Number Theory.

An interpolation theorem holds for many standard modal logics, but first order S5 is a prominent example of a logic for which it fails. In this paper it is shown that a first order S5 interpolation theorem can be proved provided the logic is extended to contain propositional quantifiers. A proper statement of the result involves some subtleties, but this is the essence of it.

Let K and K′ be two elliptic fields with complex multiplication over an algebraically closed field k of characteristic 0. non k-isomorphic, and let C and C′ be two curves with respectively K and K′ as function fields. We prove that if the endomorphism rings of the curves are not isomorphic then K and K′ are not elementarily equivalent in the language of fields expanded with a constant symbol (the modular invariant). This theorem is an analogue of a theorem from David A. Pierce in the language of k-algebras.

This paper concerns automorphisms of the computably enumerable sets. We prove two results relating semilow sets and prompt degrees via automorphisms, one of which is complementary to a recent result of Downey and Harrington. We also show that the property of effective simplicity is not invariant under automorphism, and that in fact every promptly simple set is automorphic to an effectively simple set. A major technique used in these proofs is a modification of the Harrington-Soare version of the method of Harrington-Soare and Cholak for constructing Δ30 automorphisms; this modification takes advantage of a recent result of Soare on the extension of “restricted” automorphisms to full automorphisms.

We define a property R(A0, A1) in the partial order of computably enumerable sets under inclusion, and prove that R implies that A0 is noncomputable and incomplete. Moreover, the property is nonvacuous. and the A0 and A1 which we build satisfying R form a Friedberg splitting of their union A, with A1 prompt and A promptly simple. We conclude that A0 and A1 lie in distinct orbits under automorphisms of , yielding a strong answer to a question previously explored by Downey, Stob, and Soare about whether halves of Friedberg splittings must lie in the same orbit.

We give some new examples of possible degree spectra of invariant relations on Δ20-categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ20-categorical computable structure is either intrinsically computable or has infinite degree spectrum. This condition also allows us to use the proof of a result of Moses [23] to establish the same result for computable relations on computable linear orderings.

We also place our results in the context of the study of what types of degree-theoretic constructions can be carried out within the degree spectrum of a relation on a computable structure, given some restrictions on the relation or the structure. From this point of view we consider the cases of Δ20-categorical structures, linear orderings, and 1-decidable structures, in the last case using the proof of a result of Ash and Nerode [3] to extend results of Harizanov [14].

In this paper we shall repair some errors and fill some gaps in the inner model theory of [2]. The problems we shall address affect some quite basic definitions and proofs.

We shall be concerned with condensation properties of canonical inner models constructed from coherent sequences of extenders as in [2]. Condensation results have the general form: if x is definable in a certain way over a level , then either x ∈ , or else from x we can reconstruct in a simple way.

The first condensation property considered in [2] is the initial segment condition, or ISC. In section 1 we show that the version of this condition described in [2] is too strong, in that no coherent in which the extenders are indexed in the manner of [2], and which is such that L[] satisfies the mild large cardinal hypothesis that there is a cardinal which is strong past a measurable, can satisfy the full ISC of [2]. It follows that the coherent sequences constructed in [2] do not satisfy the ISC of [2]. We shall describe the weaker ISC which these sequences do satisfy, and indicate the small changes in the arguments of [2] this new condition requires.

We point out that a certain complex compact manifold constructed by Lieberman has the dimensional order property, and has U-rank different from Morley rank. We also give a sufficient condition for a Kähler manifold to be totally degenerate (that is, to be an indiscernible set, in its canonical language) and point out that there are K3 surfaces which satisfy these conditions.

We study local strengthenings of the simplicity condition. In particular, we define and study a local Lascar rank, as well as short, low. supershort and superlow theories. An example of a low non supershort theory is given.

Let K be a function field of one variable over a constant field C of finite transcendence degree over ℂ. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K. Then there exists a set W′ of K-primes such that Hilbert's Tenth Problem is not decidable over OK,W′ = {x ϵ K∣ordþx ≥ 0, ∀þ ∉ W′}, and the set (W′ ∖ W)∪{W ∖ W′) is finite.

Let K be a function field of one variable over a constant field C finitely generated over ℚ. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K and the degree of all the primes in W is bounded by b ϵ ℕ. Then there exists a set W′ of K-primes such that ℤ has a Diophantine definition over OK,W′, and the set (W′ ∖ W)∪(W ∖ W′) is finite.

Let K be a computable field. Let ℱ be a collection of recursive functions over K, possibly including field operations. We investigate the following question. Given an r.e. degree . is there an injective map j : K → ℕ such that j(K) is of degree a and all the functions in ℱ are translated by restrictions of total recursive functions.

Can a supercompact cardinal κ be Laver indestructible when there is a level-by-level agreement between strong compactness and supercompactness? In this article, we show that if there is a sufficiently large cardinal above κ, then no, it cannot. Conversely, if one weakens the requirement either by demanding less indestructibility, such as requiring only indestructibility by stratified posets. or less level-by-level agreement, such as requiring it only on measure one sets, then yes. it can.

Using the description of the Ziegler spectrum we characterise modules with various stability-theoretic properties (ω-stability, superstability, categoricity) over certain classes of finite-dimensional algebras. We also show that, for modules over the algebras we consider, having few types is equivalent to being ω-stable.