Добро пожаловать!

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |   ...   | 29 |

Kazan State University, Kazan E-mail:Andrey.Frolov@ksu.ru Мальцевские чтения 2009 Теория вычислимости Structures associated with real closed fields J. F. Knight, K. M. Lange A real closed ordered field is a model of T = Th(R, +, ·, 0, 1, <). We report results on the effectiveness of structures associated with real closed fields. For x, y K, we say x y if there exist integers m and n such that m|x| > |y| and n|y| > |x|. It is possible to choose a representative from each equivalence class such that the result is a subgroup G of (K+, ·).

Such a subgroup G is called a value group of K. A residue field of K is a subfield of K containing exactly one representative for each rational cut that is filled in K. Any two value groups of K and any two residue fields of K are isomorphic. We will present exact characterizations of the complexity of value groups and residue fields of computable real closed fields.

An integer part for K is a discrete ordered subring I such that 1 is the first positive element of I, and for all r K, there exists i I such that i r

References [1] Mourgues M. H., Ressayre J. P. Every real closed field has an integer part. Journal of Symbolic Logic, 58 (1993), N. 2, 641–647.

University of Notre Dame, Notre Dame (U.S.A.) E-mail:klange1@nd.edu Мальцевские чтения 2009 Теория вычислимости On definability in the subword order O. V. Kudinov, V. L. Selivanov, L. V. Yartseva Starting with classical works of A. Tarski and A. I. Mal’cev, the study of definability in natural structures became a central issue of logic and computation theory. For computation theory, the study of structures on words and trees is most relevant [1, 2].

In [3, 4] a complete definability theory was developed for the h-quasiorder of finite labeled forests and for the structure (A; ), where A is the set of words over the finite k k alphabet Ak = {0,..., k - 1}, k 1, and is the infix partial order (u v iff v = xuy for some x, y A). We use some notation and terminology of these papers.

k In this work we start to develop a similar theory for the subword order on A defined k as follows: u v iff u is a subword of v, i.e., u is obtained from v by deleting some symbols.

Theorem. 1. For any k 1, any element of A is -definable in the A[1,2]-expansion k k of (A; ) (i.e. in the expansion obtained by adding to the signature { } the constant k symbols denoting words of lengths 1 or 2).

2. For any k 1, any automorphism of (A; ) identical on A[1,2] is the identity k k automorphism.

3. For any k 2, Aut(A; ) where is the symmetric group on k elements k 2 k k {0,..., k - 1}.

4. For any k 1, the structure (A; ) is definable in (A; ).

k k References [1] Kuske D. Theories of orders on the set of words. RAIRO Theoretical Informatics and Applications, (2006), 53–74.

[2] Rabin M. O. Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math.

Soc., 576 (1969) 141, 1–35.

[3] Kudinov O. V., Selivanov V. L. A Gandy theorem for abstract structures and applications to first-order definability. Proc. of CiE-2009, Lecture Notes in Computer Science, v. 5635. Berlin: Springer, 2009, 290–299.

[4] Kudinov O. V., Selivanov V. L. Definability in the infix order on words. Proc. of DLT-2009, Lecture Notes in Computer Science, v. 5583. Berlin: Springer, 2009, 454–465.

S. L. Sobolev Institute of Mathematics SB RAS E-mail:kud@math.nsc.ru A. P. Ershov Institute of Informatics Systems SB RAS E-mail:vseliv@ngs.ru A. P. Ershov Institute of Informatics Systems SB RAS E-mail:kotofejnik@gmail.com Мальцевские чтения 2009 Теория вычислимости Arithmetical categoricity of ordered abelian groups A. G. Mel’nikov One of the main topics of computable model theory is the study of isomorphisms between computable copies of a given structure. A structure A is computably categorical if there is a computable isomorphism between any two computable copies of A. Goncharov, Remmel, Solomon, Lempp and others obtained characterisations of computable categoricity in the classes of Boolean algebras, linear orders, abelian groups, ordered abelian groups and trees (see e. g. [4], [8] or [3]).

If structure A is not computably categorical, then we may ask if A is 0 -categorical, n for a given n (i.e. every pair of computable copies of A has a 0 -computable isomorphism n between them). In [6] McCoy studies 0-categorical linear orders and Boolean algebras. In [1] Ash gives a characterization of hyperarithmetical categoricity of ordinals. In [5], for any given n>0, a tree is constructed that is 0 -categorical but not 0 -categorical. Similar n+1 n examples can be constructed in the class abelian p-groups [2]. There are also examples of 0 -categorical torsion-free abelian groups for small n [7].

n We study 0 -categorical ordered abelian groups. The main result is the following n theorem.

Theorem. For every natural number n>0 there is an ordered abelian group which is 0 -categorical but not 0 -categorical.

n+1 n To prove this theorem we introduce a coding technique that transforms linear orders into ordered abelian groups. Using this technique we also show that the isomorphism problem for ordered abelian groups is 1-complete.

References [1] Ash C. J. Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees.

Trans. of Amer. Math. Soc., 298 (1986), 497–514.

[2] Barker E. J. Back and forth relations for reduced abelian p-groups. Annals of Pure and Applied Logic, 75 (1995) 223–249.

[3] Goncharov S. S., Lempp S., Solomon R. The computable dimension of ordered abelian groups. Advances in Mathematics, 175 (2003), 102–143.

[4] Goncharov S. S. Countable Boolean algebras and decidability. Siberian School of Algebra and Logic, Novosibirsk, Nauchnaya Kniga, 1996.

[5] Lempp S., McCoy C., Miller R., Solomon R. Computable Categoricity of Trees of Finite Height. Journal of Symbolic Logic, 70 (2005), N. 1, 151–215.

[6] McCoy C. Categoricity in Boolean algebras and linear orderings. Annals of Pure and Applied Logic, (2003), 85–120.

[7] Melnikov A. G. 0 -Categorical completely decomposable torsion-free abelian groups. Proceedings of CiE 2009, Springer, Accepted.

[8] Remmel J. B. Recursively categorical linear orderings. Proc. Amer. Math. Soc., 83 (1981), 387–391.

The University of Auckland, and The Novosibirsk State University E-mail:vokinlem@bk.ru Мальцевские чтения 2009 Теория вычислимости Fine hierarchies via Priestley duality V. L. Selivanov In most applications of fine hierarchies (see [1] for a survey) their characterizations in terms of so called alternating trees is of principal importance. Also, in many cases a suitable version of many-one reducibility exists that fits a given fine hierarchy. Here we show a surprising result that suitable versions of alternating trees and of m-reducibilities may be found for any given fine hierarchy, i.e. the methods of alternating trees and mreducibilities are quite general, which is of some methodological interest.

The result (which is formulated, because of lack of space, only for the difference hierarchy (DH) which is the simplest and most important version of fine hierarchy; for the DH the alternating trees are simplified to alternating chains) is naturally described in terms of Priestley duality [2] that states the dual equivalence between the category of bounded distributive lattices (with {,, 0, 1}-homomorphisms) and the category of Priestley spaces (with continuous monotone mappings). Recall that a Priestley space (X; ) is a compact topological space X equipped with a partial order such that for any x, y X with x y there is a clopen up-set U with x U, y U.

Let X = p(L) be the Priestley space corresponding to a given bounded distributive lattice L and let L be the lattice of clopen up-sets in X. Then L and L are canonically isomorphic, and this isomorphism uniquely extends to an isomorphism between L(n) and L(n) for each n< where {L(n)} and {L(n)} are the DH’s over L and L, respectively.

Theorem. 1. For any n<, L(n) coincides with the class of clopen subsets of X that have no 1-alternating -chain of length n.

2. If the class C = L(n) \ co-L(n) is non-empty then L(n) has a complete set and C is a degree under the m-reducibility by the continuous monotone functions.

3. If the class C =(L(n +1) co-L(n +1)) \ (L(n) co-L(n)) is non-empty and L has the reduction property then L(n +1) co-L(n +1) has a complete set and C is a degree under the m-reducibility by the continuous monotone functions.

References [1] Selivanov V. L. Fine hierarchies and m-reducibilities in theoretical computer science. Theoretical Computer Science, 405 (2008), 116–163.

[2] Davey B. A., Priestley H. A. Introduction to Lattices and Order. Cambridge, 1994.

A. P. Ershov Institute of Informatics Systems SB RAS, Novosibirsk (Russia) E-mail:vseliv@ngs.ru Мальцевские чтения 2009 Теория вычислимости Isomorphisms and algorithmic complexity relations over structures with two binary predicates J. A. Tussupov There are the next basic generalized problems of computable algebraic structures.

1. The problem of Goncharov S. S. and Manasse M. S. — ”The problem of characterization of relative categoricity in hyperarithmetical hierarchies by given levels of complexity of Scott families” and ”The problem of connection of relative categoricity of computable presentations and abstract presentation”.

2. The problem of Ershov Yu. L. — ”The problem of finite algorithmitical dimensions in hyperarithmetical hierarchy”.

3. The problem of Nerode A. — ”The problem of connection between relations of bounded complexity on different computable presentations and definability of relations by formulas of given complexity”.

4. The problem of Knight J. F. — ”The problem of structures with presentations in just the degrees of sets X such that 0 (X) =0 ”.

We give the results which are connected with decisions of problems 1–4. for some algebraic structure. Let A structure of signature of two binary predicates.

Theorem 1. For each computable successor ordinal there is computable structure A that is 0 categorical but not relatively 0 (and without formally 0 Scott family).

Theorem 2. For each computable successor ordinal there is computable structure A that is 0 with a relation that is intrinsically 0 but not relatively intrinsically 0.

Theorem 3. For each computable successor ordinal for each finite n there is computable structure A with 0 dimension n.

Theorem 4. For each computable successor ordinal there is computable structure A with presentations in just the degrees of sets X such that 0 (X) =0. In particular, for each finite n there is computable structure A with presentations in just the non - lown degrees.

Supported by the grant Fundamental Sciences — 1.18 ”Spectra of universe theory and minimal models”.

References [1] Goncharov S. S., Harizanov V. S., Knight J. F., McCoy C., Miller R. G., Solomon R. Enumerations in computable structure theory. Annals of Pure and Applied Logic, 136 (2005), N. 3, 219–246.

[2] Tussupov J. A. Isomorphisms, Definable Relations Scott Family on the Integral Domains and the Commutative Semigroups. Siberian Advances in Mathematics, 1 (2007).

Taraz State University, Taraz E-mail:tussupov@mail.ru Мальцевские чтения 2009 Теория вычислимости Index Sets of Free Groups J. Wallbaum We use computable infinitary logic to investigate how hard it is to distinguish a free group within the class of all free groups and then within the class of all groups. Let Fn denote the free group of rank n and F the free group of countable infinite rank. For a group G, let I(G) be the set of computable indices of copies of G. We prove the following:

Within the class of free groups, I(F2) is m-complete 0, I(Fn) for n 3 is m-complete d - 0, and I(F) is m-complete 0.

2 Within the class of all groups, I(Fn) for n 2 is m-complete d - 0 while I(F) is 0.

2 We leave open the question of whether I(F) is m-complete 0 or there is a better description. This is joint work with J. Carson, V. Harizanov, J. Knight, K. Lange, C. Maher, C. McCoy, A. Morozov, and S. Quinn.

Notre Dame, U.S.A.

E-mail:jwallbau@nd.edu Мальцевские чтения 2009 Теория вычислимости Splitting properties in 2-c.e. degrees M. M. Yamaleev ATuring degree a is splittable in a class of degrees C avoiding an upper cone of a degree d if there exist degrees x0, x1 C such that a = x0 x1, xi


Theorem 1. Let a and d be properly 2-c.e. degrees such that 0 Theorem 1 holds when d is a 0-degree, which does not contain c.e. sets. Theorem states that the well-known bubble (see [1]) can be constructed in low 2-c.e. degrees.

Theorem 2. There exist low noncomputable 2-c.e. degrees b

As a consequence we obtain the following: the partial orders of m-low c.e. and m-low 2-c.e. degrees are not elementarily equivalent for any m 1. Also, I will talk about a link between splitting properties (Theorem 1) and the bubbles and how the link could be uniformly adapted to higher levels of the Ershov’s hierarchy.

References [1] Arslanov M. M., Kalimullin I. Sh., Lempp S. On Downey’s conjecture. The Journal of Symbolic Logic, to appear, http://www.math.wisc.edu/ lempp/papers.

Kazan State University, Department of Mathematics, Kazan E-mail:marsiam2@yandex.ru Мальцевские чтения 2009 Теория вычислимости Undecidability in the 2-quasiorder of labeled forests A. V. Zhukov By a forest we mean an (at most) countable poset in which every lower cone is a chain.

A k-labeled forest (or just a k-forest) is an object (F ;, c) consisting of a forest (F ; ) and a labeling c : P k (a natural number k 2 is identified with the set {0,...,k-1}). Let Fk and Fk be the classes of all finite k-forests and all (at most) countable k-forests without infinite chains, respectively.

We study the 2-quasiorder on Fk and Fk which can be defined as follows [1]: (F ;

, c) 2 (F ;, c ) iff there is a monotone function f : (P ; ) (P ; ) such that for all x, y F, c(x) = c(y) implies c (f(x)) = c (f(y)). The 2-quasiorder is a generalization of the h-quasiorder for which the undecidability results were proven in [2, 3].

Theorem. For k 3, the first-order theories of (Fk, 2) and (Fk, 2) are hereditary undecidable.

References [1] Hertling P. Unstetigkeitsgrade von Funktionen in der effektiven Analysis. Doktorarbeit (PhD thesis, in German). FernUniversitt Hagen, Informatik-Bericht 208, November 1996.

[2] Kudinov O. V., Selivanov V. L. Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests. J. Log. Comput., 17 (2007), N. 6, 1135–1151.

[3] Selivanov V. L. Undecidability in Some Structures Related to Computation Theory. J. Log. Comput., 19 (2009), N. 1, 177–197.

Novosibirsk State Pedagogical University, Novosibirsk E-mail:zhukan@ngs.ru VII. Секция «Философия математики» Мальцевские чтения 2009 Философия математики Приложения теории групп в естествознании и в информационных технологиях: возможности и ограничения Г. С. Садовой По словам А. И. Мальцева теория групп представляет собой язык для выражения глубоких законов природы и дает средства для технических вычислений. Цели настоящего доклада — показать, что в последние десятилетия теория групп была одной из самых востребованных естествознанием и техникой разделов математики; привести новые приложения теории групп; выяснить ограничения на применение теоретикогрупповых методов.

Теория групп широко применяется для изучения закономерностей симметрии или приближенной симметрии.

Если какой-либо объект или закон природы обладает симметрией, то существует вполне определённая группа операций, сохраняющих эту симметрию. А все возможные состояния объекта находятся в точном соответствии с представлениями группы.

Перечисление и классификация групп и их представлений известны из математики.

Зная симметрию, можно сделать определённые заключения о свойствах объекта, не выполняя сложные вычисления. Аппарат теории групп связан с преобразованиями симметрии молекул и твердых тел, с их матричными представлениями, характерами и классами и с рассмотрением неприводимых представлений.

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |   ...   | 29 |

© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.