Non-Complementedness and Non-Distributivity of Kleene Degrees

In this note, we study the complementedness and the distributivity of upper semilattices of Kleene degrees assuming V = L. K denotes the upper semilattice of all Kleene degrees. We prove that if V = L, then some sub upper semilattices of K are non-complemented and some are non-distributive.     

Modulo computably enumerable degrees by cupping partners

Cupping partners of an element in an upper semilattice with a greatest element 1 are those joining the element to 1. We define a congruence relation on such an upper semilattice by considering the elements having the same cupping partners as equivalent. It is interesting that this congruence relation induces a non-dense quotient structure of computably enumerable Turing degrees. Another main interesting phenomenon in this article is that on the computably enumerable degrees, this relation is different from that modulo the noncuppable ideal, though they define a same equivalent class for the computable Turing degree.     

The universal Lachlan semilattice without the greatest element

We deal with some upper semilattices of m-degrees and of numberings of finite families. It is proved that the semilattice of all c.e. m-degrees, from which the greatest element is removed, is isomorphic to the semilattice of simple m-degrees, the semilattice of hypersimple m-degrees, and the semilattice of Σ ₂ ⁰ -computable numberings of a finite family of Σ ₂ ⁰ -sets, which contains more than one element and does not contain elements that are comparable w.r.t. inclusion. Supported by the Grant Council (under RF President) for Young Russian Scientists via project MK-1820.2005.1. __________ Translated from Algebra i Logika, Vol. 46, No. 3, pp. 299–345, May–June, 2007.     

Truth tabular degrees of recursively enumerable sets

The upper semilattice of truth tabular degrees of recursively enumerable (r.e.) sets is studied. It is shown that there exists an infinite set of pairwise tabularly incomparable truth tabular degrees higher than any tabularly incomplete r.e. truth tabular degree. A similar assertion holds also for r.e. m-degrees. Hence follows that a complete truth tabular degree contains an infinite antichain of r.e. m-degrees.Translated from Matematicheskie Zametki, Vol. 14, No. 5, pp. 697–702, November, 1973.     

The structure of degrees of finite-automaton transformations of prefix decidable superwords

We show that the structure of degrees of finite automaton transformations of prefix decidable superwords does not form the upper semilattice.     

Differences of Computably Enumerable Sets

We consider the ower semilattice 𝒟 of differences of c.e. sets under inclusion. It is shown that 𝒟 is not distributive as a semilattice, and that the c.e. sets form a definable subclass.     

On a semilattice of numberings

We study some properties of a $ \mathfrak{c} $ \mathfrak{c} -universal semilattice $ \mathfrak{A} $ \mathfrak{A} with the cardinality of the continuum, i.e., of an upper semilattice of m-degrees. In particular, it is shown that the quotient semilattice of such a semilattice modulo any countable ideal will be also $ \mathfrak{c} $ \mathfrak{c} -universal. In addition, there exists an isomorphism $ \mathfrak{A} $ \mathfrak{A} such that $ {\mathfrak{A} \mathord{\left/ {\vphantom {\mathfrak{A} {\iota \left( \mathfrak{A} \right)}}} \right. \kern-\nulldelimiterspace} {\iota \left( \mathfrak{A} \right)}} $ {\mathfrak{A} \mathord{\left/ {\vphantom {\mathfrak{A} {\iota \left( \mathfrak{A} \right)}}} \right. \kern-\nulldelimiterspace} {\iota \left( \mathfrak{A} \right)}} will be also $ \mathfrak{c} $ \mathfrak{c} -universal. Furthermore, a property of the group of its automorphisms is obtained. To study properties of this semilattice, the technique and methods of admissible sets are used. More exactly, it is shown that the semilattice of mΣ-degrees $ L_{m\Sigma }^{\mathbb{H}\mathbb{F}\left( S \right)} $ L_{m\Sigma }^{\mathbb{H}\mathbb{F}\left( S \right)} on the hereditarily finite superstructure $ \mathbb{H}\mathbb{F} $ \mathbb{H}\mathbb{F} (S) over a countable set S will be a $ \mathfrak{c} $ \mathfrak{c} -universal semilattice with the cardinality of the continuum.     

Distributive lattices of numberings

We study into a semilattice of numberings generated by a given fixed numbering via operations of completion and taking least upper bounds. It is proved that, except for the trivial cases, this semilattice is an infinite distributive lattice every principal ideal in which is finite. The least upper and the greatest lower bounds in the semilattice are invariant under extensions in the semilattice of all numberings. Isomorphism types for the semilattices in question are in one-to-one correspondence with pairs of cardinals the first component of which is equal to the cardinality of a set of non-special elements, and the second — to the cardinality of a set of special elements, of the initial numbering. Supported by INTAS grant No. 00-429. __________ Translated from Algebra i Logika, Vol. 46, No. 1, pp. 83–102, January–February, 2007.     

幺半群的强半格上的Rees矩阵半群的平移壳

设含幺元的半群A是幺半群A~_e的半格,其中A的幺元为1_A,A~_e的幺元为e,所有幺元e的集合为E(A),则对于幺半群A上的Rees矩阵半群S和幺半群A~_e上的Rees矩阵半群S~_e,以下五个条件是等价的:(1)任意的e∈E(A),a∈A,有ae=ea;(2)A是幺半群A~_e的强半格;(3)S是S~_e的强半格;(4)A的平移壳和A~_e的平移壳的强半格同构;(5)S的平移壳和S~_e的平移壳的强半格同构.     

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.     

Splitting properties and jump classes

We show that the promptly simple sets of Maass form a filter in the lattice ℰ of recursively enumerable sets. The degrees of the promptly simple sets form a filter in the upper semilattice of r.e. degrees. This filter nontrivially splits the high degrees (a is high ifa′=0″). The property of prompt simplicity is neither definable in ℰ nor invariant under automorphisms of ℰ. However, prompt simplicity is easily shown to imply a property of r.e. sets which is definable in ℰ and which we have called the splitting property. The splitting property is used to answer many questions about automorphisms of ℰ. In particular, we construct lowd-simple sets which are not automorphic, answering a question of Lerman and Soare. We produce classes invariant under automorphisms of ℰ which nontrivially split the high degrees as well as all of the other classes of r.e. degrees defined in terms of the jump operator. This refutes a conjecture of Soare and answers a question of H. Friedman. During preparation of this paper, the first author was supported by the Heisenberg Programm der Deutschen Forschungsgemeinschaft, West Germany. The second author was partially supported by NSF Grant MSC 77-04013. The third author was partially supported by NSF Grant MSC 80-02937.     

On the *-order for Rickart *-rings

It is shown that a Rickart *-ring forms a pseudo upper semilattice under the *-order and that a Baer *-ring in addition forms a complete lower semilattice.Presented by R. S. Pierce.     

A semilattice of numberings. II

\mathfrakc \mathfrak{c} -Universal semilattices \mathfrakA \mathfrak{A} of the power of the continuum (of an upper semilattice of m-degrees ) on admissible sets are studied. Moreover, it is shown that a semilattice of \mathbbH\mathbbF( \mathfrakM ) \mathbb{H}\mathbb{F}\left( \mathfrak{M} \right) -numberings of a finite set is \mathfrakc \mathfrak{c} -universal if \mathfrakM \mathfrak{M} is a countable model of a c-simple theory.     

Conditions for realization of a function on a semilattice over real bases of switching elements

The functions are considered on finite upper semilattices that realize their switching networks. Some necessary condition is given for realization of a function on a semilattice over a base of switching elements as well as necessary and sufficient conditions for realization of a function on a semilattice of states by single-stage and many-stage circuits over bases of real switching elements (transistors and resistors).     

Maximal and Minimal Semilattices on Ordered Sets

The map which takes an element of an ordered set to its principal ideal is a natural embedding of that ordered set into its powerset, a semilattice. If attention is restricted to all finite intersections of the principal ideals of the original ordered set, then an embedding into a much smaller semilattice is obtained. In this paper the question is answered of when this construction is, in a certain arrow-theoretic sense, minimal. Specifically, a characterisation is given, in terms of ideals and filters, of those ordered sets which admit a so-called minimal embedding into a semilattice. Similarly, a candidate maximal semilattice on an ordered set can be constructed from the principal filters of its elements. A characterisation of those ordered sets that extend to a maximal semilattice is given. Finally, the notion of a free semilattice on an ordered set is given, and it is shown that the candidate maximal semilattice in the embedding-theoretic sense is the free object.     

Q 1-degrees of c.e. sets

We show that the Q-degree of a hyperhypersimple set includes an infinite collection of Q ₁-degrees linearly ordered under ${\leq_{Q_1}}$ with order type of the integers and consisting entirely of hyperhypersimple sets. Also, we prove that the c.e. Q ₁-degrees are not an upper semilattice. The main result of this paper is that the Q ₁-degree of a hemimaximal set contains only one c.e. 1-degree. Analogous results are valid for ${\Pi_1^0}$ s ₁-degrees.     

Strong reducibility of partial numberings

A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice.In addition, Ershovs completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from the given set by adding one point and which is enumerated by a total and complete numbering. As is shown, the degrees of complete numberings of the extended set also form an upper semilattice. Moreover, both semilattices are isomorphic.This is not so in the case of the usual, weaker reducibility relation for partial numberings which allows the reduction function to transfer arbitrary numbers into indices.This research has partially been supported by INTAS under grant 00-499 Computability in Hierarchies and Topological Spaces.Mathematics Subject Classification (2000): 03D45     

On the congruence of the upper semilattices of recursively enumerable m-powers and tabular powers

We have proved that in the upper semilattice of recursively enumerable tabular powers the set of minimal powers has an upper bound differing from the total power.Translated from Matematicheskie Zametki, Vol. 20, No. 1, pp. 19–26, July, 1976.     

Numbered distributive semilattices

In this article, we consider several definitions of a Lachlan semilattice; i.e., a semilattice isomorphic to a principal ideal of the semilattice of computably enumerable m-degrees. We also answer a series of questions on constructive posets and prove that each distributive semilattice with top and bottom is a Lachlan semilattice if it admits a Σ ₃ ⁰ -representation as an algebra but need not be a Lachlan semilattice if it admits a Σ ₃ ⁰ -representation as a poset. The examples are constructed of distributive lattices that are constructivizable as posets but not constructivizable as join (meet) semilattices. We also prove that every locally lattice poset (in particular, every lattice and every distributive semilattice) possessing a Δ ₂ ⁰ -representation is positive.     

Degree spectra of the successor relation of computable linear orderings

We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees. The authors acknowledge partial support by the NSF binational grant DMS-0554841, and Harizanov by the NSF grant DMS-0704256, and Chubb by the Sigma Xi Grant in Aid of Research.