A Fine Structure in the Theory of Isols

In this paper we introduce a collection of isols having some interesting properties. Imagine a collection W of regressive isols with the following features: (1) u, v ? W implies that u ? v or v ? u, (2) u ? v and v ? W imply u ? W, (3) W contains ? = {0,1,2,…} and some infinite isols, and (4) u e? W, u infinite, and u + v regressive imply u + v ? W. That such a collection W exists is proved in our paper. It has many nice features. It also satisfies (5) u, v ? W, u ? v and u infinite imply v ? g(u) for some recursive combinatorial function g, and (6) each u ? W is hereditarily odd-even and is hereditarily recursively strongly torre. The collection W that we obtain may be characterized in terms of a semiring of isols D(c) introduced by J. C. E. Dekker in [5]. We will show that W = D(c), where c is an infinite regressive isol that is called completely torre.     

On hyper‐torre isols

In this paper we present a contribution to a classical result of E. Ellentuck in the theory of regressive isols. E. Ellentuck introduced the concept of a hyper‐torre isol, established their existence for regressive isols, and then proved that associated with these isols a special kind of semi‐ring of isols is a model of the true universal‐recursive statements of arithmetic. This result took on an added significance when it was later shown that for regressive isols, the property of being hyper‐torre is equivalent to being hereditarily odd‐even. In this paper we present a simplification to the original proof for establishing that equivalence. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Combinatorial Isols and the Arithmetic of Dekker Semirings

In his long and illuminating paper [1] Joe Barback defined and showed to be non‐vacuous a class of infinite regressive isols he has termed “complete y torre” (CT) isols. These particular isols a enjoy a property that Barback has since labelled combinatoriality. In [2], he provides a list of properties characterizing the combinatoria isols. In Section 2 of our paper, we extend this list of characterizations to include the fact that an infinite regressive isol X is combinatorial if and only if its associated Dekker semiring D (X) satisfies all those Π₂ sentences of the anguage L_N for isol theory that are true in the set ω of natural numbers. (Moreover, with X combinatorial, the interpretations in D(X)of the various function and relation symbols of L_N via the “lifting ” to D(X) of their Σ₁ definitions in ω coincide with their interpretations via isolic extension.) We also note in Section 2 that Π₂(L)‐correctness, for semirings D(X), cannot be improved to Π ₃(L)‐correctness, no matter how many additional properties we succeed in attaching to a combinatoria isol; there is a fixed (L) sentence that blocks such extension. (Here L is the usual basic first‐order language for arithmetic.) In Section 3, we provide a proof of the existence of combinatorial isols that does not involve verification of the extremely strong properties that characterize Barback's CT isols.     

A Generic relation on Recursively Enumerable Sets

We introduce the concept of a generic relation for algorithmic problems, which preserves the property of being decidable for a problem for almost all inputs and possesses the transitive property. As distinct from the classical m-reducibility relation, the generic relation under consideration does not possess the reflexive property: we construct an example of a recursively enumerable set that is generically incomparable with itself. We also give an example of a set that is complete with respect to the generic relation in the class of recursively enumerable sets.     

Effective Nonrecursiveness

Productive sets are sets which are “effectively non recursively enumerable”. In the same spirit, we introduce a notion of “effectively nonrecursive sets” and prove an effective version of Post's theorem. We also show that a set is recursively enumerable and effectively nonrecursive in our sense if and only if it is effectively nonrecursive in the sense of Odifreddi [1].     

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.     

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.     

Cupping the Recursively Enumerable Degrees by D.R.E. Degrees

We prove that there are two incomplete d.r.e. degrees (the Turingdegrees of differences of two recursively enumerable sets) suchthat every non-zero recursively enumerable degree cups at leastone of them to 0', the greatest recursively enumerable (Turing)degree. 1991 Mathematics Subject Classification: primary 03D25,03D30; secondary 03D35.     

The translation theorem

Summary We state and prove the Translation Theorem. Then we apply the Translation Theorem to Soare's Extension Theorem, weakening slightly the hypothesis to yield a theorem we call the Modified Extension Theorem. We use this theorem to reprove several of the known results about orbits in the lattice of recursively enumerable sets. It is hoped that these proofs are easier to understand than the old proofs.Mathematics subject classification (1991): 03D25The author was partially supported by a NSF Postdoctoral Fellowship and by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University and wishes to thank Michael Stob and Rodney Downey for their help     

On the Universal Splitting Property

We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low₂. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed.     

Minimal numerations of positively computable families

It is proved that among computable numerations that are limit-equivalent to some positive numeration of a computable family of recursively enumerable sets, either there exists one least numeration, or there are countably many nonequivalent, minimal numerations. In particular, semilattices of computable numerations for computable families of finite sets and of weakly effectively discrete families of recursively enumerable sets either have a least element or possess countably many minimal elements.Translated fromAlgebra i Logika, Vol. 33, No. 3, pp. 233–254, May–June, 1994.     

Recursive analysis of singular ordinary differential equations

We investigate systems of ordinary differential equations with a parameter. We show that under suitable assumptions on the systems the solutions are computable in the sense of recursive analysis. As an application we give a complete characterization of the recursively enumerable sets using Fourier coefficients of recursive analytic functions that are generated by differential equations and elementary operations.     

Recursive analysis of singular ordinary differential equations

We investigate systems of ordinary differential equations with a parameter. We show that under suitable assumptions on the systems the solutions are computable in the sense of recursive analysis. As an application we give a complete characterization of the recursively enumerable sets using Fourier coefficients of recursive analytic functions that are generated by differential equations and elementary operations.     

Embedding relations in the lattice of recursively enumerable sets

Let ?* be the lattice of recursively enumerable sets of natural numbers modulo finite differences. We characterize the relations which can be embedded in ?* by using certain collections of maximal sets as domain and using Lachlan's notion of major subsets to code in the relation in certain natural ways. We show that attempts to prove the undecidability of ?* by using such embeddings fail.     

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.     

A property of creative sets

A new approach to the study of creative sets using the notion of a table is offered. Making use of tables conforming to recursively enumerable sets, novel properties of creative sets are established. Harrington's theorem on the definability of creative sets in the lattice of recursively enumerable sets is proved, and we reprove Lachlan's theorem which states that one of the factors in a direct product of creative sets is again creative. Supported by RFFR grant No. 93-01-16014. Translated fromAlgebra i Logika, Vol. 35, No. 3, pp. 294–307, May–June, 1996.     

Boolean Hierarchies of Partitions over a Reducible Base

The Boolean hierarchy of partitions was introduced and studied by Kosub and Wagner, primarily over the lattice of NP-sets. Here, this hierarchy is treated over lattices with the reduction property, showing that it has a much simpler structure in this instance. A complete characterization is given for the hierarchy over some important lattices, in particular, over the lattices of recursively enumerable sets and of open sets in the Baire space.     

On the Schröder–Bernstein property for modules

The well known Schröder–Bernstein Theorem states that any two sets with one to one maps into each other are isomorphic. The question of whether any two (subisomorphic or) direct summand subisomorphic algebraic structures are isomorphic, has long been of interest. Kaplansky asked whether direct summands subisomorphic abelian groups are always isomorphic? The question generated a great deal of interest. The study of this question for the general class of modules has been somewhat limited. We extend the study of this question for modules in this paper. We say that a module Msatisfies the Schröder–Bernstein property (S-B property) if any two direct summands of M which are subisomorphic to direct summands of each other, are isomorphic. We show that a large number of classes of modules satisfy the S-B property. These include the classes of quasi-continuous, directly finite, quasi-discrete and modules with ACC on direct summands. It is also shown that over a Noetherian ring R, every extending module satisfies the S-B property. Among applications, it is proved that the class of rings R for which every R-module satisfies the S-B property is precisely that of pure-semisimple rings. We show that over a commutative domain R, any two quasi-continuous subisomorphic R-modules are isomorphic if and only if R is a PID. We study other conditions related to the S-B property and obtain characterizations of certain classes of rings via those conditions. Examples which delimit and illustrate our results are provided.     

The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.