On arithmetical level of the class of superhigh sets

We determine the proper arithmetical level of the class of superhigh sets.     

Nonsingularity of matrices associated with classes of arithmetical functions on lcm-closed sets

Let S = {x₁, … , x_n} be a set of n distinct positive integers and f be an arithmetical function. Let [f(x_i, x_j)] denote the n × n matrix having f evaluated at the greatest common divisor (x_i, x_j) of x_i and x_j as its i, j-entry and (f[x_i, x_j]) denote the n × n matrix having f evaluated at the least common multiple [x_i, x_j] of x_i and x_j as its i, j-entry. The set S is said to be lcm-closed if [x_i, x_j] ∈ S for all 1 ? i, j ? n. For an integer x > 1, let ω(x) denote the number of distinct prime factors of x. Define ω(1) = 0. In this paper, we show that if S = {x₁, … , x_n} is an lcm-closed set satisfying , and if f is a strictly increasing (resp. decreasing) completely multiplicative function, or if f is a strictly decreasing (resp. increasing) completely multiplicative function satisfying (resp. f(p) ? p) for any prime p, then the matrix [f(x_i, x_j)] (resp. (f[x_i, x_j])) defined on S is nonsingular. By using the concept of least-type multiple introduced in [S. Hong, J. Algebra 281 (2004) 1-14], we also obtain reduced formulas for det(f(x_i, x_j)) and det(f[x_i, x_j]) when f is completely multiplicative and S is lcm-closed. We also establish several results about the nonsingularity of LCM matrices and reciprocal GCD matrices.     

Index sets and Scott sentences

For a computable structure \({\mathcal{A}}\) , there may not be a computable infinitary Scott sentence. When there is a computable infinitary Scott sentence \({\varphi}\) , then the complexity of the index set \({I(\mathcal{A})}\) is bounded by that of \({\varphi}\) . There are results (Ash and Knight in Computable structures and the hyperarithmetical hierarchy. Elsevier, Amsterdam, 2000; Calvert et al. in Algeb Log 45:306–315, 2006; Carson et al. in Trans Am Math Soc 364:5715–5728, 2012; McCoy and Wallbaum in Trans Am Math Soc 364:5729–5734, 2012; Knight and Saraph in Scott sentences for certain groups, pre-print) giving “optimal” Scott sentences for structures of various familiar kinds. These results have been driven by the thesis that the complexity of the index set should match that of an optimal Scott sentence (Ash and Knight in Computable structures and the hyperarithmetical hierarchy. Elsevier, Amsterdam, 2000; Calvert et al. in Algeb Log 45:306–315, 2006; Carson et al. in Trans Am Math Soc 364:5715–5728, 2012; McCoy and Wallbaum in Trans Am Math Soc 364:5729–5734, 2012). In this note, it is shown that the thesis does not always hold. For a certain subgroup of \({\mathbb{Q}}\) , there is no computable d- \({\Sigma_2}\) Scott sentence, even though (as shown in Ash and Knight in Scott sentences for certain groups, pre-print) the index set is d- \({\Sigma^0_2}\) .     

Index sets of computable structures

The index set of a computable structure is the set of indices for computable copies of . We determine complexity of the index sets of various mathematically interesting structures including different finite structures, ℚ-vector spaces, Archimedean real-closed ordered fields, reduced Abelian p-groups of length less than ω², and models of the original Ehrenfeucht theory. The index sets for these structures all turn out to be m-complete Π _n ⁰ , d-Σ _n ⁰ , or Σ _n ⁰ , for various n. In each case the calculation involves finding an optimal sentence (i.e., one of simplest form) that describes the structure. The form of the sentence (computable Π_n, d-Σ_n, or Σ_n) yields a bound on the complexity of the index set. Whenever we show m-completeness of the index set, we know that the sentence is optimal. For some structures, the first sentence that comes to mind is not optimal, and another sentence of simpler form is shown to serve the purpose. For some of the groups, this involves Ramsey’s theory. Supported by the NSF grants DMS-0139626 and DMS-0353748. Supported by the NSF grant DMS-0502499 and by the Columbian Research Fellowship of the George Washington University. Supported by the NSF grant DMS-0353748. __________ Translated from Algebra i Logika, Vol. 45, No. 5, pp. 538–574, September–October, 2006.     

Index sets of decidable models

We study the index sets of the class of d-decidable structures and of the class of d-decidable countably categorical structures, where d is an arbitrary arithmetical Turing degree. It is proved that the first of them is m-complete ∑ ₃ ^{0, d} , and the second is m-complete ∑ ₃ ^{0, d} \∑ ₃ ^{0, d} in the universal computable numbering of computable structures for the language with one binary predicate.     

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     

On the binomial arithmetical rank

The binomial arithmetical rank of a binomial ideal I is the smallest integer s for which there exist binomials f₁,..., f_s in I such that rad (I) = rad (f₁,..., f_s). We completely determine the binomial arithmetical rank for the ideals of monomial curves in P_KⁿP_K^n. In particular we prove that, if the characteristic of the field K is zero, then bar (I(C)) = n - 1 if C is complete intersection, otherwise bar (I(C)) = n. While it is known that if the characteristic of the field K is positive, then bar (I(C)) = n - 1 always.     

Prime-independent arithmetical functions

Summary This paper studies arithmetical functions that are prime-independent and multiplicative. Firstly, it establishes necessary and sufficient conditions for such functions to possess simple formulae relating them to the zeta function. Then it investigates asymptotic average-values and moments of such functions. The results apply to functions of ideals in algebraic numbers fields, or of isomorphism classes in certain categories, as well as to functions of positive integers. Entrata in Redazione il 10 ottobre 1972.     

On exponents in arithmetical semigroups

Let be the factoring of a natural numbern into primes. In 1969Niven found the average order of the functionsh(n)= min {₁,... _r } andH(n)= max {₁,... _r }. In this note a generalization ofNiven's results is discussed, namely the average order of the corresponding functions in certain arithmetical semigroups.     

Index sets of classes of automatic structures

We obtain exact estimates in the arithmetical and analytical hierarchies of index sets of various classes of automatic models. We also obtain estimates for the existence problems for computable isomorphism and embedding of automatic structures.