Σ-Definability of countable structures over real numbers, complex numbers, and quaternions

We study Σ-definability of countable models over hereditarily finite {ie193-01} superstructures over the field ℝ of reals, the field ℂ of complex numbers, and over the skew field ℍ of quaternions. In particular, it is shown that each at most countable structure of a finite signature, which is Σ-definable over {ie193-02} with at most countable equivalence classes and without parameters, has a computable isomorphic copy. Moreover, if we lift the requirement on the cardinalities of the classes in a definition then such a model can have an arbitrary hyperarithmetical complexity, but it will be hyperarithmetical in any case. Also it is proved that any countable structure Σ-definable over {ie193-03}, possibly with parameters, has a computable isomorphic copy and that being Σ-definable over {ie193-04} is equivalent to being Σ-definable over {ie193-05}. Supported by RFBR-DFG, grant No. 06-01-04002 DFGa. __________ Translated from Algebra i Logika, Vol. 47, No. 3, pp. 335–363, May–June, 2008.     

Σ-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.     

Σ-Bounded algebraic systems and universal functions. I

We introduce the concept of a Σ-bounded algebraic system and prove that if a system is Σ- bounded with respect to a subset A then in a hereditarily finite admissible set over this system there exists a universal Σ-function for the family of functions definable by Σ-formulas with parameters in A. We obtain a necessary and sufficient condition for the existence of a universal Σ-function in a hereditarily finite admissible set over a Σ-bounded algebraic system. We prove that every linear order is a Σ-bounded system and in a hereditarily finite admissible set over it there exists a universal Σ-function.     

Isomorphisms,definable relations,and Scott families of class 2 nilpotent groups

The paper deals in questions on the complexity of isomorphisms and relations on universes of structures, on the number and properties of numberings in various hierarchies of sets, and on the existence of connections between semantic and syntactic properties of the structures and relations for the class of nilpotent groups of class two. Supported by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools via project NSh-4413.2006.1. __________ Translated from Algebra i Logika, Vol. 46, No. 4, pp. 514–524, July–August, 2007.     

Degrees of presentability of structures. II

We show that the property of being locally constructivizable is inherited under Muchnik reducibility, which is weakest among the effective reducibilities considered over countable structures. It is stated that local constructivizability of level higher than 1 is inherited under Σ-reducibility but is not inherited under Medvedev reducibility. An example of a structure and a relation P ⊆ M is constructed for which but ≢_∑ . Also, we point out a class of structures which are effectively defined by a family of their local theories. Supported by RFBR (grant Nos. 05-0100481 and 06-0104002), by the Council for Grants (under RF President) for State Support of Young Candidates of Science and Their Supervisors (project MK-1239.2005.1), and by INTAS (project YSF 04-83-3310). __________ Translated from Algebra i Logika, Vol. 47, No. 1, pp. 108–126, January–February, 2008.     

Σ-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.     

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.     

On infinite real trace rational languages of maximum topological complexity

We consider the set ℝ^ω(Γ, D) of infinite real traces, over a dependence alphabet (Γ,D) with no isolated letter, equipped with the topology induced by the prefix metric. We prove that all rational languages of infinite real traces are analytic sets. We also reprove that there exist some rational languages of infinite real traces that are analytic but non-Borel sets; in fact, these sets are even Σ ₁ ¹ -complete, hence have maximum possible topological complexity. For this purpose, we give an example of a Σ ₁ ¹ -complete language that is fundamentally different from the known example of a Σ ₁ ¹ -complete infinitary rational relation given by Finkel (2003). Bibliography: 35 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 205–223.     

Approximation Schemes for Functional Optimization Problems

Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow “fast” with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the “curse of dimensionality,” which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables. Marcello Sanguineti was partially supported by a PRIN grant from the Italian Ministry for University and Research (project “Models and Algorithms for Robust Network Optimization”).     

Σ-Subsets of Natural Numbers

It is shown that the class of all possible families of -subsets of finite ordinals in admissible sets coincides with a class of all non-empty families closed under e-reducibility and . The construction presented has the property of being minimal under effective definability. Also, we describe the smallest (w.r.t. inclusion) classes of families of subsets of natural numbers, computable in hereditarily finite superstructures. A new series of examples is constructed in which admissible sets lack in universal -function. Furthermore, we show that some principles of classical computability theory (such as the existence of an infinite non-trivial enumerable subset, existence of an infinite computable subset, reduction principle, uniformization principle) are always satisfied for the classes of all -subsets of finite ordinals in admissible sets.     

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.     

Extentions between admissible representations of isometry groups of regular trees

This is the continuation of our previous work (Demir, Geom. Dedicata 105, 189–207, 2004). In this paper, we study extensions between admissible representations of the isometry groups of regular trees. We use the results of Demir, (Geom. Dedicata 105, 189–207, 2004) to show, following Schneider and Stuhler (J. Reine. Angew. Math. 436, 19–32, 1993) in the p-adic case, that extensions between admissible representations of G are finite-dimensional.     

Gabor pairs, and a discrete approach to wave-front sets

We introduce admissible lattices and Gabor pairs to define discrete versions of wave-front sets with respect to Fourier–Lebesgue and modulation spaces. We prove that these wave-front sets agree with each other and with corresponding wave-front sets of “continuous type”. This implies that the coefficients of a Gabor frame expansion of f are parameter dependent, and describe the wave-front set of f.     

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.     

Embedding c<Subscript>0</Subscript> in bvca(Σ, <Emphasis Type="Italic">X</Emphasis>)

If (Ω,Σ) is a measurable space and X a Banach space, we provide sufficient conditions on Σ and X in order to guarantee that bvca(Σ, X) the Banach space of all X-valued countably additive measures of bounded variation equipped with the variation norm, contains a copy of c₀ if and only if X does. This work was supported by the project MTM2005-01182 of the Spanish Ministry of Education and Science, co-financed by the European Community (Feder projects).     

Ordered representations of spaces of integrable functions

Let X be a Banach space, (Ω,Σ) a measurable space and let m : Σ → X be a (countably additive) vector measure. Consider the corresponding space of integrable functions L¹(m). In this paper we analyze the set of (countably additive) vector measures n satisfying that L¹(n) = L¹(m). In order to do this we define a (quasi) order relation on this set to obtain under adequate requirements the simplest representation of the space L¹(m) associated to downward directed subsets of the set of all the representations. This research has been partially supported by La Junta de Andalucía. The support of D.G.I. under project MTM2006–11690–C02 (M.E.C. Spain) and FEDER is gratefully acknowledged.     

Definability of Boolean Algebras in \mathbb{H}\mathbb{F} -Superstructures

Within the frames of the -definability approach propounded by Yu. L. Ershov, we study into the definability of Boolean algebras and their Frechet ranks in hereditarily finite superstructures. Examples are constructed of a superatomic Boolean algebra whose Frechet rank is not -definable in the hereditarily finite superstructure over that algebra, and of an admissible set in which the atomless Boolean algebra is not autostable.     

Additive problems for integers with a given number of prime divisors

The asymptotics of sums of the form Στ(|bn−a|) (summation overn<N, ω(n)=k) is studied, whereω(n) is the number of distinct prime divisors ofn, andτ(n) is the number of all divisors. Translated fromMatematicheskie Zametki, Vol. 63, No. 5, pp. 749–762, May, 1998. In conclusion, the author wishes to express his gratitude to Professor N. M. Timofeev for valuable advice. This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00502.     

On Σ-nilpotent ideals of topological PI-rings

We show that under certain conditions on the topology of a faithful module M over a topological PI-ring R, if M has at most countable dual topological Krull dimension, then the closure of the sum of all Σ-nilpotent ideals of the ring R is a Σ-nilpotent ideal too, and in the case of a bounded ring R its topological Baer radical is Σ-nilpotent. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 12, No. 2, pp. 111–118, 2006.