Jumps of Minimal Degrees Below 0'

We show that there is a degree a REA in and low over 0' suchthat no minimal degree below 0' jumps to a degree above a. Wealso show that every nonlow recursively enumerable degree boundsa nonlow minimal degree.     

On the Density of the Pseudo-Isolated Degrees

A d.c.e. (2-computably enumerable) degree d is pseudo-isolatedif d itself is non-isolated (in the sense that no computablyenumerable (c.e.) degree below d can bound the c.e. degreesbelow d) and there is a d.c.e. degree b < d bounding allc.e. degrees below d. We prove in this paper that the pseudo-isolateddegrees are densely distributed in the c.e. degrees. 2000 MathematicsSubject Classification 03D25, 03D28.     

Strong Minimal Covers for Recursively Enumerable Degrees

We prove that there exists a nonzero recursively enumerable Turing degree possessing a strong minimal cover. Mathematics Subject Classification: 03D30.     

Splittings of 0' into the Recursively Enumerable Degrees

Lachlan [9] proved that there exists a non-recursive recursively enumerable (r. e.) degree such that every non-recursive r. e. degree below it bounds a minimal pair. In this paper we first prove the dual of this fact. Second, we answer a question of Jockusch by showing that there exists a pair of incomplete r. e. degrees a₀, a₁ such that for every non-recursive r. e. degree w, there is a pair of incomparable r. e. degrees b₀, b₂ such that w = b₀ V b₁ and b_i for i = 0, 1. Mathematics Subject Classification: 03D25, 03D30.     

Degrees of autostability relative to strong constructivizations

The spectra of the Turing degrees of autostability of computable models are studied. For almost prime decidable models, it is shown that the autostability spectrum relative to strong constructivizations of such models always contains a certain recursively enumerable Turing degree; moreover, it is shown that for any recursively enumerable Turing degree, there exist prime models in which this degree is the least one in the autostability spectrum relative to strong constructivizations.     

Every Set has a Least Jump Enumeration

Given a computably enumerable set W, there is a Turing degreewhich is the least jump of any set in which W is computablyenumerable, namely 0'. Remarkably, this is not a phenomenonof computably enumerable sets. It is shown that for every subsetA of N, there is a Turing degree, c'_µ(A), which is theleast degree of the jumps of all sets X for which A is . In addition this result providesan isomorphism invariant method for assigning Turing degreesto certain torsion-free abelian groups.     

Recursively Enumerable Equivalence Relations Modulo Finite Differences

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th(Eq*) has the same computational complexity as the true first-order arithmetic. Mathematics Subject Classification: 03D25, 03D15, 03D35.     

Lattice embeddings below a nonlow2 recursively enumerable degree

We introduce techniques that allow us to embed below an arbitary nonlow₂ recursively enumerable degree any lattice currently known to be embeddable into the recursively enumerable degrees. Research partially supported by NSF Grants DMS-9204308, DMS-93-44740, a US-NZ binational grant NSF 90-20558, the U.S. ARO through ACSyAM at the Mathematical Sciences Institute of Cornell Univrsity Contract DAAL03-91-C-0027 and the IGC of Victoria University.     

The computably enumerable degrees are locally non-cappable

We prove that every non-computable incomplete computably enumerable degree is locally non-cappable, and use this result to show that there is no maximal non-bounding computably enumerable degree. The author was supported by an EPSRC Research Studentship. Mathematics Subject Classification (2000):03D25 Keywords or phrases:Computably enumerable – Degree     

Effectively and Noneffectively Nowhere Simple Sets

R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ? of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two (non) effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* (A) is effectively isomorphic to ?*, and that there is a nowhere simple set A such that L*(A) is not effectively isomorphic to ?*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L*(A) effectively isomorphic to ?*. Mathematics Subject Classification: 03D25, 03D10.     

Algebras of Recursively Enumerable Sets and Their Applications to Fuzzy Logic

Algebras of operations defined on recursively enumerable sets of different kinds are considered. Every such algebra is specified by a list of operations involved and a list of basic elements. An element of an algebra is said to be representable in this algebra if it can be obtained from given basic elements by operations of the algebra. Two kinds of recursively enumerable sets are considered: recursively enumerable sets in the usual sense and fuzzy recursively enumerable sets. On binary, i.e., two-dimensional recursively enumerable sets of these kinds, algebras of operations are introduced. An algebra θ is constructed in which all binary recursively enumerable sets are representable. A subalgebra θ⁰ of θ is constructed in which all binary recursively enumerable sets are representable if and only if they are described by formulas of Presburger’s arithmetic system. An algebra Ω is constructed in which all binary recursively enumerable fuzzy sets are representable. A subalgebra Ω⁰ of the algebra Ω is constructed such that fuzzy recursively enumerable sets representable in Ω⁰ can be treated as fuzzy counterparts of sets representable by formulas of Presburger’s system. Bibliography: 16 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 304, 2003, pp. 75–98.     

Weak density and cupping in the d-r.e. degrees

Consider the Turing degrees of differences of recursively enumerable sets (the d-r.e. degrees). We show that there is a properly d-r.e. degree (a d-r.e. degree that is not r.e.) between any two comparable r.e. degrees, and that given a high r.e. degreeh, every nonrecursive d-r.e. degree ≦h cups toh by a low d-r.e. degree. The second author was partially supported by NSF grant DMS-8701891.     

On the classification of first order Gödel logics

We characterize the recursively enumerable first order Gödel logics with △ with respect to validity and non-satisfiability. The finitely valued and four infinitely valued Gödel logics with △ are recursively enumerable, not-satisfiability is recursively enumerable if validity is recursively enumerable. This is in contrast to first order Gödel logics without △, where validity is recursively enumerable for finitely valued and two infinitely valued Gödel logics, not-satisfiability is recursively enumerable if validity is recursively enumerable or 0 isolated in the truth value set.     

An Interval of Computably Enumerable Isolating Degrees

We construct computably enumerable degrees a < b such that all computably enumerable degrees c with a < c < b isolate some d. c. e. degree d.     

Some New Lattice Constructions in High R. E. Degrees

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable (r. e.) degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets (Lerman, Lachlan). In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction of simplicity- and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that (i) A has no dense simple superset, (ii) the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with (i), and (iii) A ?_T B if B is high, and A ≥_T B otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail.     

Enumerating Transitive Finite Permutation Groups

Denote by f(n) the number of subgroups of the symmetric groupSym(n) of degree n, and by f_trans(n) the number of its transitivesubgroups. It was conjectured by Pyber [9] that almost all subgroupsof Sym(n) are not transitive, that is, f_trans(n)/f(n) tendsto 0 when n tends to infinity. It is still an open questionwhether or not this conjecture is true. The difficulty comesfrom the fact that, from many points of view, transitivity isnot a really strong restriction on permutation groups, and thereare too many transitive groups [9, Sections 3 and 4]. In thispaper we solve the problem in the particular case of permutationgroups of prime power degree, proving the following result.1991 Mathematics Subject Classification 20B05, 20D60.     

System function languages

In this paper we define the concept of a system function language which is a language generated by a system function. We identify system function languages with recursively enumerable sets which are non-simple and co-infinite. We then define restricted system function languages and identify them with recursive sets which are co-infinite. Finally we state and prove some independence and dependence relationships between system function languages and some of the more well-known decision problems. MSC: 03D05, 03D20, 03D25.     

On Artin's Conjecture, I: Systems of Diagonal Forms

As a special case of a well-known conjecture of Artin, it isexpected that a system of R additive forms of degree k, say [formula] with integer coefficients a_ij, has a non-trivial solution inQ_p for all primes p whenever [formula] Here we adopt the convention that a solution of (1) is non-trivialif not all the x_i are 0. To date, this has been verified onlywhen R=1, by Davenport and Lewis [4], and for odd k when R=2,by Davenport and Lewis [7]. For larger values of R, and in particularwhen k is even, more severe conditions on N are required toassure the existence of p-adic solutions of (1) for all primesp. In another important contribution, Davenport and Lewis [6]showed that the conditions [formula] are sufficient. There have been a number of refinements of theseresults. Schmidt [13] obtained N>>R²k³ log k, and Low,Pitman and Wolff [10] improved the work of Davenport and Lewisby showing the weaker constraints [formula] to be sufficient for p-adic solubility of (1). A noticeable feature of these results is that for even k, onealways encounters a factor k³ log k, in spite of the expectedk² in (2). In this paper we show that one can reach the expectedorder of magnitude k². 1991 Mathematics Subject Classification11D72, 11D79.     

Asymptotic Results for Transitive Permutation Groups

In this paper we give answers to some open questions concerninggeneration and enumeration of finite transitive permutationgroups. In [1], Bryant, Kovács and Robinson proved thatthere is a number c^' such that each soluble transitive permutationgroup of degree n2 can be generated by elements, and later A. Lucchini [5] extended thisresult (with a different constant c') to finite permutationgroups containing a soluble transitive subgroup. We are nowable to prove this theorem in full generality, and this solvesthe question of bounding the number of generators of a finitetransitive permutation group in terms of its degree. The resultobtained is the following. 1991 Mathematics Subject Classification20B05, 20D60.     

There is no fat orbit

We give a proof of a theorem of Harrington that there is no orbit of the lattice of recursively enumerable sets containing elements of each nonzero recursively enumerable degree. We also establish some degree theoretical extensions.