Uniformity in Computable Structure Theory

We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, previously studied by Kudinov and by Ventsov. We discuss some of their results and establish new ones, while also exploring the connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman and Chisholm and with previous work of Ash, Knight, and Slaman on uniformity in a general computable structure-theoretical setting.     

The Computable Dimension of I-Trees of Infinite Height

We study computable trees with distinguished initial subtree (briefly, I-trees). It is proved that all I-trees of infinite height are computably categorical, and moreover, they all have effectively infinite computable dimension.     

Computable Structure and Non-Structure Theorems

In a lecture in Kazan (1977), Goncharov dubbed a number of problems regarding the classification of computable members of various classes of structures. Some of the problems seemed likely to have nice answers, while others did not. At the end of the lecture, Shore asked what would be a convincing negative result. The goal of the present article is to consider some possible answers to Shore's question. We consider structures of some computable language, whose universes are computable sets of constants. In measuring complexity, we identify with its atomic diagram D(), which, via the Gödel numbering, may be treated as a subset of . In particular, is computable if D() is computable. If K is some class, then K^c denotes the set of computable members of K. A computable characterization for K should separate the computable members of K from other structures, that is, those that either are not in K or are not computable. A computable classification (structure theorem) should describe each member of K^c up to isomorphism, or other equivalence, in terms of relatively simple invariants. A computable non-structure theorem would assert that there is no computable structure theorem. We use three approaches. They all give the correct answer for vector spaces over Q, and for linear orderings. Under all of the approaches, both classes have a computable characterization, and there is a computable classification for vector spaces, but not for linear orderings. Finally, we formulate some open problems.     

Computable Families of Superatomic Boolean Algebras

We describe the families of superatomic Boolean algebras which have a computable numbering. We define the notion of majorizability and establish a criterion that is formulated only on using algorithmic terms and majorizability. We give some examples showing that the condition of majorizability is essential. We also prove some criterion for the existence of a computable numbering for a family of -atomic algebras ( is a computable ordinal).     

Isomorphisms,definable relations,and Scott families for integral domains and commutative semigroups

In the present article, we prove the following four assertions: (1) For every computable successor ordinal α, there exists a Δ _α ⁰ -categorical integral domain (commutative semigroup) which is not relatively Δ _α ⁰ -categorical (i.e., no formally Σ _α ⁰ Scott family exists for such a structure). (2) For every computable successor ordinal α, there exists an intrinsically Σ _α ⁰ -relation on the universe of a computable integral domain (commutative semigroup) which is not a relatively intrinsically Σ _α ⁰ -relation. (3) For every computable successor ordinal α and finite n, there exists an integral domain (commutative semigroup) whose Δ _α ⁰ -dimension is equal to n. (4) For every computable successor ordinal α, there exists an integral domain (commutative semigroup) with presentations only in the degrees of sets X such that Δ _α ⁰ (X) is not Δ _α ⁰ . In particular, for every finite n, there exists an integral domain (commutative semigroup) with presentations only in the degrees that are not n-low.     

Monotonically Computable Real Numbers

Area number x is called k‐monotonically computable (k‐mc), for constant k > 0, if there is a computable sequence (x_n)_{n ∈ ℕ} of rational numbers which converges to x such that the convergence is k‐monotonic in the sense that k · |x — x_n| ≥ |x — x_m| for any m > n and x is monotonically computable (mc) if it is k‐mc for some k > 0. x is weakly computable if there is a computable sequence (x_s)_{s ∈ ℕ} of rational numbers converging to x such that the sum $\sum _{s \in \mathbb{N}}$|x_s — x_{s + 1}| is finite. In this paper we show that a mc real numbers are weakly computable but the converse fails. Furthermore, we show also an infinite hierarchy of mc real numbers.     

An autostable 2 nilpotent group with no Scott family of finitary formulas

We construct an autostable 2 nilpotent group with no Scott family of finitary formulas but having a unique constructivization up to autoequivalence.     

On Automorphic Tuples of Elements in Computable Models

A criterion is obtained for existence of two isomorphic but not hyperarithmetically isomorphic tuples in a hyperarithmetical model. This criterion is used to show that such a situation occurs in the models of well-known classes.Original Russian Text Copyright © 2005 Goncharov S. S., Harizanov V. S., Knight J. F., Morozov A. S., Romina A. V.The first four authors are supported by the Binational Grant NSF DMS-0075899; the first and fourth authors are partially supported by the Russian Foundation for Basic Research (Grant 02-01-00953) and the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-2112.03.1).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 3, pp. 523–532, May–June, 2005.     

Complexity of Categorical Theories with Computable Models

M. Lerman and J. Scmerl specified some sufficient conditions for computable models of countably categorical arithmetical theories to exist. More precisely, it was shown that if T is a countably categorical arithmetical theory, and the set of its sentences beginning with an existential quantifier and having at most n+1 alternations of quantifiers is _n+1 ⁰ for any n, then T has a computable model. J. Night improved this result by allowing certain uniformity and omitting the requirement that T is arithmetical. However, all of the known examples of theories of₀-categorical computable models had low level of algorithmic complexity, and whether there are theories that would satisfy the above conditions for sufficiently large n was unknown. This paper will include such examples.     

On Classifying Subsets of Natural Numbers by Their Computable Permutations

We introduce some alternative definitions of the concept of computable automorphism of a set of natural numbers. We study their relationships and investigate whether some classes of sets having isomorphic groups of automorphisms coincide with other classes of sets usual in computability. Finally, we show that the classification of sets by these groups of automorphisms is nontrivial.     

Computable Homogeneous Boolean Algebras and a Metatheorem

We consider computable homogeneous Boolean algebras. Previously, countable homogeneous Boolean algebras have been described up to isomorphism and a simple criterion has been found for the existence of a strongly constructive (decidable) isomorphic copy for such. We propose a natural criterion for the existence of a constructive (computable) isomorphic copy. For this, a new hierarchy of -computable functions and sets is introduced, which is more delicate than Feiner's. Also, a metatheorem is proved connecting computable Boolean algebras and their hyperarithmetical quotient algebras.     

Relatively Hyperimmune Relations on Structures

Let be a computable structure and let R be an additional relation on its domain. We establish a necessary and sufficient condition for the existence of an isomorphic copy of such that the image of R is h-simple (h-immune) relative to .     

Boolean Algebras with Finite Families of Computable Automorphisms

We prove that each computable Boolean algebra has a computable presentation in which for every computable family of automorphisms the set of atoms moved by at least one of its members is finite. This implies that each computable atomic Boolean algebra has a computable presentation in which its every computable family of automorphisms is finite. The priority argument is not used in the proof.     

On the complexity of categoricity in computable structures

We investigate the computational complexity the class of Γ‐categorical computable structures. We show that hyperarithmetic categoricity is Π¹₁‐complete, while computable categoricity is Π⁰₄‐hard. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

变换思想在重积分三大公式讲授中的应用

就Green公式、GBUSS公式和Stokes公式这一教学中的重点和难点问题,针对传统的教学方法对积分区域进行"补"或"挖"处理的不足,探讨使用变换的思想从变换的角度来讲解三大定理的应用,揭示定理的核心问题,以便帮助学生理解和掌握.     

A Weak Constructive Second-Order Arithmetic with Extraction of Algorithms Computable in Polynomial Time

In this paper, a family of weak constructive theories, containing arithmetic and a theory of natural-valued functions of natural arguments, is suggested. The functions are polynomially bounded and computable in time bounded by polynomials in their arguments. The languages of these theories contain functional constants for addition and multiplication and the equality predicate. Other functional constants are also allowed, provided that the corresponding functions satisfy the above conditions of polynomial boundedness. From the proofs of the theories considered witness functions for provable formulas, computable in polynomial time, can algorithmically be extracted. If an argument of a witness is a function, then the latter is used in the witness algorithm as an oracle. Bibliography: 2 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 304, 2003, pp. 7–12.     

Plemelj公式及其应用

本文介绍了Ｃ￣ｎ空间中函数经Ｂｏｃｈｎｅｒ－Ｍａｒｔｉｎｅｌｌｉ变换后的Ｐｌｅｍｅｌｊ公式和它在Ｓｔｅｉｎ流形上的拓广，同时还介绍了Ｃ￣ｎ空间和Ｓｔｅｉｎ流形上微分形式在Ｂｏｃｈｎｅｒ－Ｍａｒｔｉｎｅｌｌｉ变换下的跳跃公式以及这些公式分别在全纯开拓，闭开拓，方程和线性奇异积分方程上的应用．