Turing jumps in the Ershov hierarchy

We look at infinite levels of the Ershov hierarchy in the natural system of notation, which are proper for jumps of sets. It is proved that proper infinite levels for jumps are confined to D_a ^{- 1} \Delta_a^{ - 1} -levels, where a stands for an ordinal ωⁿ > 1.     

Computable numberings of families of low sets and Turing jumps in the Ershov hierarchy

If ν and μ are some Δ₂⁰-computable numberings of families of sets of the naturals then P(x,y) ⇔ ν(x)′ ≠ μ(y) is a Σ₂⁰-predicate. Deriving corollaries from this result, we obtain a sufficient condition for existence of a Δ₂⁰-computable numbering of the subfamily of all sets in a given family with the Turing jumps belonging to a fixed level of the Ershov hierarchy, and we deduce existence of a Σ_ω⁻¹-computable numbering of the family of all superlow sets.     

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.     

Positive Numberings of Families of Sets in the Ershov Hierarchy

It is proved that there exist infinitely many positive undecidable _n ^-1 -computable numberings of every infinite family that admits at least one _n ^-1 -computable numbering and contains either the empty set, for even n, or N for odd n.     

Index sets and parametric reductions

We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W _e ≤ _q ^u A} for q∈ {m, T} are Σ₄ ⁰ complete. We also show hat FPT(≤ _q ⁿ ), that is {e : W _e computable and ≡ _q ⁿ ?}, is Σ₄ ⁰ complete. We also look at computable presentability of these classes. Received: 13 July 1996 / Revised version: 14 April 2000 / Published online: 18 May 2001     

Initial segments of computable linear orders with additional computable predicates

We study computable linear orders with computable neighborhood and block predicates. In particular, it is proved that there exists a computable linear order with a computable neighborhood predicate, having a Π₁⁰ -initial segment which is isomorphic to no computable order with a computable neighborhood predicate. On the other hand, every Σ₁⁰ -initial segment of such an order has a computable copy enjoying a computable neighborhood predicate. Similar results are stated for computable linear orders with a computable block predicate replacing a neighborhood relation. Moreover, using the results obtained, we give a simpler proof for the Coles–Downey–Khoussainov theorem on the existence of a computable linear order with Π₂⁰ -initial segment, not having a computable copy.     

Effectively closed sets and enumerations

An effectively closed set, or class, may viewed as the set of infinite paths through a computable tree. A numbering, or enumeration, is a map from ω onto a countable collection of objects. One numbering is reducible to another if equality holds after the second is composed with a computable function. Many commonly used numberings of classes are shown to be mutually reducible via a computable permutation. Computable injective numberings are given for the family of classes and for the subclasses of decidable and of homogeneous classes. However no computable numberings exist for small or thin classes. No computable numbering of trees exists that includes all computable trees without dead ends. Research partially supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.     

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.     

Σ-bounded algebraic systems and universal functions. II

Ershov algebras, Boolean algebras, and abelian p-groups are Σ-bounded systems, and there exist universal Σ-functions in hereditarily finite admissible sets over them.     

On one-sided versus two-sided classification

One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the gven class. Such a classifier istwo-sided if the sequence of its output in addition converges to 0 on setsnot belonging to the class. The present work obtains the below mentionedresults for one-sided classes (= Σ⁰ ₂ classes) with respect to four areas: Turing complexity, 1-reductions, index sets and measure. There are one-sided classes which are not two-sided. This can have two reasons: (1) the class has only high Turing complexity. Then there are some oracles which allow to construct noncomputale two-sided classifiers. (2) The class is difficult because of some topological constraints and then there are also no nonrecursive two-sided classifiers. For case (1), several results are obtainedto localize the Turing complexity of certain types of one-sided classes. The concepts of 1-reduction, 1-completeness and simple sets is transferred to one-sided classes: There are 1-complete classes and simple classes, but no class is at the same time 1-complete nd simple. The one-sided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity Π¹ ₁: the index set of the class {0,1}^∞, the index set of the equality problem and the index set of all two-sided classes. On the other side the index set of the empty class has complexity Π⁰ ₂; Π⁰ ₂ and Σ⁰ ₂ are the least complexities any nontrivial index set can have. Lusin showed that any one-sided class is measurable. Concerning the effectiveness of this measure, it is shown that a one-sided class has recursive measure 0 if it has measure 0, but that thre are one-sided classes having measure 1 without having measure 1 effectively. The measure of a two-sided class can be computed in the limit. Received: 2 December 1999 / Revised version: 28 February 2000 / Published online: 15 June 2001     

Σ-Uniform structures and Σ-functions. II

We construct a family of Σ-uniform Abelian groups and a family of Σ-uniform rings. Conditions are specified that are necessary and sufficient for a universal Σ-function to exist in a hereditarily finite admissible set over structures in these families. It is proved that there is a set S of primes such that no universal Σ-function exists in hereditarily finite admissible sets \mathbbH\mathbbF(G) \mathbb{H}\mathbb{F}(G) and \mathbbH\mathbbF(K) \mathbb{H}\mathbb{F}(K) , where G = ⊕{Z _p | p ∈ S} is a group, Z _p is a cyclic group of order p, K = ⊕{F _p | p ∈ S} is a ring, and F _p is a prime field of characteristic p.     

On a Sharper Lower Bound for a Percentile of a Student’s <Emphasis Type="Italic">t</Emphasis> Distribution with an Application

In this communication, we first compare z _α and t _ν,α , the upper 100α% points of a standard normal and a Student’s t _ν distributions respectively. We begin with a proof of a well-known result, namely, for every fixed 0 < a < \frac120<\alpha <\frac{1}{2} and the degree of freedom ν, one has t _ν,α  > z _α . Next, Theorem 3.1 provides a new and explicit expression b _ν ( > 1) such that for every fixed 0 < a < \frac120<\alpha < \frac{1}{2} and ν, we can conclude t _ν,α  > b _ν z _α . This is clearly a significant improvement over the result that is customarily quoted in nearly every textbook and elsewhere. A proof of Theorem 3.1 is surprisingly simple and pretty. We also extend Theorem 3.1 in the case of a non-central Student’s t distribution (Section 3.3). In the context of Stein’s (Ann Math Stat 16:243–258, 1945; Econometrica 17:77–78, 1949) 100(1 − α)% fixed-width confidence intervals for the mean of a normal distribution having an unknown variance, we have examined the oversampling rate on an average for a variety of choices of m, the pilot sample size. We ran simulations to investigate this issue. We have found that the oversampling rates are approximated well by t_n,a/2²z_a/2^-2t_{\nu ,\alpha /2}^{2}z_{\alpha /2}^{-2} for small and moderate values of m( ≤ 50) all across Table 2 where ν = m − 1. However, when m is chosen large (≥ 100), we find from Table 3 that the oversampling rates are not approximated by t_n,a/2²z_a/2^-2t_{\nu ,\alpha /2}^{2}z_{\alpha /2}^{-2} very well anymore in some cases, and in those cases the oversampling rates either exceed the new lower bound of t_n,a/2²z_a/2^-2,t_{\nu ,\alpha /2}^{2}z_{\alpha /2}^{-2}, namely b_n²,b_{\nu }^{2}, or comes incredibly close to b_n²b_{\nu }^{2} where ν = m − 1. That is, the new lower bound for a percentile of a Student’s t distribution may play an important role in order to come up with diagnostics in our understanding of simulated output under Stein’s fixed-width confidence interval method.     

Decomposability of low 2-computably enumerable degrees and turing jumps in the Ershov hierarchy

In this paper we prove the following theorem: For every notation of a constructive ordinal there exists a low 2-computably enumerable degree that is not splittable into two lower 2-computably enumerable degrees whose jumps belong to the corresponding Δ-level of the Ershov hierarchy.     

Slices for biparabolics of index 1

Let \mathfraka \mathfrak{a} be an algebraic Lie subalgebra of a simple Lie algebra \mathfrakg \mathfrak{g} with index \mathfraka \mathfrak{a}  ≤ rank \mathfrakg \mathfrak{g} . Let Y( \mathfraka ) Y\left( \mathfrak{a} \right) denote the algebra of \mathfraka \mathfrak{a} invariant polynomial functions on \mathfraka^* {\mathfrak{a}^*} . An algebraic slice for \mathfraka \mathfrak{a} is an affine subspace η + V with h ? \mathfraka^* \eta \in {\mathfrak{a}^*} and V ì \mathfraka^* V \subset {\mathfrak{a}^*} subspace of dimension index \mathfraka \mathfrak{a} such that restriction of function induces an isomorphism of Y( \mathfraka ) Y\left( \mathfrak{a} \right) onto the algebra R[η + V] of regular functions on η + V. Slices have been obtained in a number of cases through the construction of an adapted pair (h, η) in which h ? \mathfraka h \in \mathfrak{a} is ad-semisimple, η is a regular element of \mathfraka^* {\mathfrak{a}^*} which is an eigenvector for h of eigenvalue minus one and V is an h stable complement to ( \textad  \mathfraka )h \left( {{\text{ad}}\;\mathfrak{a}} \right)\eta in \mathfraka^* {\mathfrak{a}^*} . The classical case is for \mathfrakg \mathfrak{g} semisimple [16], [17]. Yet rather recently many other cases have been provided; for example, if \mathfrakg \mathfrak{g} is of type A and \mathfraka \mathfrak{a} is a “truncated biparabolic” [12] or a centralizer [13]. In some of these cases (in particular when the biparabolic is a Borel subalgebra) it was found [13], [14], that η could be taken to be the restriction of a regular nilpotent element in \mathfrakg \mathfrak{g} . Moreover, this calculation suggested [13] how to construct slices outside type A when no adapted pair exists. This article makes a first step in taking these ideas further. Specifically, let \mathfraka \mathfrak{a} be a truncated biparabolic of index one. (This only arises if \mathfrakg \mathfrak{g} is of type A and \mathfraka \mathfrak{a} is the derived algebra of a parabolic subalgebra whose Levi factor has just two blocks whose sizes are coprime.) In this case it is shown that the second member of an adapted pair (h, η) for \mathfraka \mathfrak{a} is the restriction of a particularly carefully chosen regular nilpotent element of \mathfrakg \mathfrak{g} . A by-product of our analysis is the construction of a map from the set of pairs of coprime integers to the set of all finite ordered sequences of ±1.     

Disconnected Ordered Sets are Max-Reconstructible

Every finite disconnected set P is determined (up to automorphism) by the family {P − {a}:a ∈ Max _P }.     

On Order Types of Systems of Segments in the Plane

Let r(n) denote the largest integer such that every family C\mathcal{C} of n pairwise disjoint segments in the plane in general position has r(n) members whose order type can be represented by points. Pach and Tóth gave a construction that shows r(n) < n ^log8/log9 (Pach and Tóth 2009). They also stated that one can apply the Erdős–Szekeres theorem for convex sets in Pach and Tóth (Discrete Comput Geom 19:437–445, 1998) to obtain r(n) > log₁₆ n. In this note, we will show that r(n) > cn ^1/4 for some absolute constant c.     

The theory of the <Emphasis Type="Italic">α</Emphasis> degrees is undecidable

Let α be an arbitrary Σ₁-admissible ordinal. For each n, there is a formula φ _n ([(x)\vec],[(y)\vec]\vec x,\vec y) such that for any relation R on a finite set F with n elements, there are α-degrees [(p)\vec]{\vec p} such that the relation defined by φ _n ([(x)\vec],[(p)\vec]\vec x,\vec p) is isomorphic to R. Consequently, the theory of α-degrees is undecidable.     

Locally Closed Semirings

 We call a semiring S locally closed if for all a ∈ S there is some integer k such that 1 + a + ⋯ + a ^k  =1 + a + ⋯ + a ^k + 1 . In any locally closed semiring we may define a star operation a ↦ a ^*, where a ^* is the above finite sum. We prove that when S is locally closed and commutative, then S is an iteration semiring.     

Some Exponential Inequalities for Positively Associated Random Variables and Rates of Convergence of the Strong Law of Large Numbers

We present some exponential inequalities for positively associated unbounded random variables. By these inequalities, we obtain the rate of convergence n ^−1/2 β _n log ^3/2 n in which β _n can be particularly taken as (log log n)^1/σ with any σ>2 for the case of geometrically decreasing covariances, which is faster than the corresponding one n ^−1/2(log log n)^1/2log ² n obtained by Xing, Yang, and Liu in J. Inequal. Appl., doi: (2008) for the case mentioned above, and derive the convergence rate n ^−1/2 β _n log ^1/2 n for the above β _n under the given covariance function, which improves the relevant one n ^−1/2(log log n)^1/2log n obtained by Yang and Chen in Sci. China, Ser. A 49(1), 78–85 (2006) for associated uniformly bounded random variables. In addition, some moment inequalities are given to prove the main results, which extend and improve some known results.     

Decidable Computable A-Numberings

The article deals in the numbering theory for admissible sets, brought in sight in [1]. For models of two special classes, we resolve the problem of there being 1-1 computable numberings of the families of all computable sets and of all computable functions. In proofs, for the former case the role of finite objects is played by syntactic constructions, and for the latter — by finite subsets on hereditarily finite superstructures.