Russian Academy of Sciences

St.Petersburg Department of Steklov Mathematical Institute

Euler International Mathematical Institute

Methods of Logic in Mathematics

July 18-24, 2005

Program

Abstracts

Russian Academy of Sciences

St.Petersburg Department of Steklov Mathematical Institute

Euler International Mathematical Institute

Methods of Logic in Mathematics July 18-24, 2004

Program

Abstracts

Program Committee Marat Arslanov Andreas Blass Andrey Bovykin Su Gao Edward Griffor Jan Krajicek Alexander Kechris Alexandr Razborov Robert Soare Juris Steprans Anatoly Vershik — co-chair Yi Zhang — co-chair Boris Zilber Organizing Committee Andrey Bovykin Elena Novikova Anatoly Vershik Yi Zhang Edward Griffor

Methods of Logic in Mathematics II. Short abstracts of an international meeting held on July 18–24, 2005.– St. Petersburg, 2005.– 28pp.

The international conference “Methods of Logic in Mathematics II” is organized by the St.Petersburg Department of Steklov Institute of Mathematics and the Euler International Mathematical Institute. Included are 24 short abstracts of tutorials, invited talks and contributed talks. More information about the conference can be found on the meeting’s

website: http://www.pdmi.ras.ru/EIMI/2005/2lag/.

The conference “Methods of Logic in Mathematics” is supported by the Russian Foundation for Fundamental Research (grant number 05-01-10051-g) and the National Science Foundation (grant number DMS-0432603).

\begin{matrix}c \\ ◯ \end{matrix}POMI RAN, 2005

Contents

Conference Program . . . . . . . . . . . . . . . . . . . . . . . . 1 Marat Arslanov . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Andrey Bovykin . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Misha Gavrilovich . . . . . . . . . . . . . . . . . . . . . . . . . 9 Sergei Goncharov . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Evgeniy Gordon . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Edward Griffor . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Wilfrid Hodges . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Jose Iovino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Iskander Kalimullin . . . . . . . . . . . . . . . . . . . . . . . . . 16 Bart Kastermans and Yi Zhang . . . . . . . . . . . . . . . . . . 17 Ilya V. Kazatchkov . . . . . . . . . . . . . . . . . . . . . . . . . 17 Meeri Kesälä (Viljanen) . . . . . . . . . . . . . . . . . . . . . . 18 Igor Lysenok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Ilia Ponomarenko . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Zlil Sela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Neil Thapen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Simon Thomas . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Vladimir Tolstykh . . . . . . . . . . . . . . . . . . . . . . . . . 22 Nikolai Vereschagin . . . . . . . . . . . . . . . . . . . . . . . . . 23 Anatoly Vershik . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Andreas Weiermann . . . . . . . . . . . . . . . . . . . . . . . . 24 Boris Zilber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Contributed Talks 26 Michael Benedikt . . . . . . . . . . . . . . . . . . . . . . . . . . 26 G.L.Litvinov, V.P.Maslov, G.B.Shpiz . . . . . . . . . . . . . . . 27

Conference Program July 18, Monday

13:00–14:00 Registration, coffee
14:00–14:10 Welcoming address by Anatoly Vershik

14:10–15:00 Zlil Sela Diophantine geometry over groups and the elementary theory of a free group I

15:10–16:00 Simon Thomas Borel equivalence relations and classification problems for countable structures I

16:00–16:30 Coffee break

16:30–17:20 Marat Arslanov Applications of completeness criterions to questions of computational complexity and randomness

17:30–18:20 Vladimir Tolstykh On the Bergman property for the automorphism groups of relatively free groups

July 19, Tuesday

10:00 - 10:50 Zlil Sela Diophantine geometry over groups and the elementary theory of a free group II

11:10 - 12:00 Simon Thomas Borel equivalence relations and classification problems for countable structures II

12:00 - 14:00 LUNCH

14:00 - 14:50 Wilfrid Hodges Model theory of pairs of abelian groups

15:00 - 15:50 Ilia Ponomarenko Variations on the Burnside-Schur theorem

15:50 - 16:20 Coffee

16:20 - 17:10 Andrey Bovykin New model-theoretic unprovability proofs for Peano Arithmetic

17:20 - 18:10 Andreas Weiermann Phase transitions in logic and combinatorics

July 20, Wednesday

10:00 - 10:50 Zlil Sela Diophantine geometry over groups and the elementary theory of a free group III

11:10 - 12:00 Simon Thomas Borel equivalence relations and classification problems for countable structures III

12:00 - 14:00 LUNCH

14:00 - 14:50 Boris Zilber Zariski Geometries: from classical to quantum

15:00 - 15:50 Anatoly Vershik Globalization of the partial isomorphisms

15:50 - 16:20 Coffee

16:20 - 17:10 Misha Gavrilovich On the Model Theory of Universal Covering Spaces of Complex Algebraic Varieties

17:20 - 18:10 Igor Lysenok A view on Makanin–Razborov process

Thursday, July 21

A trip to Peterhof, starts at 10:00 from the Euler Institute.

July 22, Friday

10:00 - 10:50 Zlil Sela Diophantine geometry over groups and the elementary theory of a free group IV

11:10 - 12:00 Nikolai Vereschagin Computational Complexity I

12:00 - 14:00 LUNCH

14:00 - 14:50 Bart Kastermans and Yi Zhang Cardinal Invariants Related to Permutation Groups

15:00 - 15:50 Jose Iovino The Maximality of Continuous Logic

15:50 - 16:20 Coffee

16:20 - 17:10 Meeri Kesälä (Viljanen)

Finitary abstract elementary classes

17:20 - 18:10 Evgeniy Gordon Some applications of approximations of infinite groups by finite ones

July 23, Saturday

10:00 - 10:50 Zlil Sela Diophantine geometry over groups and the elementary theory of a free group V

11:10 - 12:00 Nikolai Vereschagin Computational Complexity II

12:00 - 14:00 LUNCH

14:00 - 14:50 Neil Thapen Δ_{1} induction and Σ_{1} collection

15:00 - 15:50 Iskander Kalimullin On the problems of definability in the enumeration degrees

15:50 - 16:20 Coffee

16:20 - 17:10 Edward Griffor Recursion on spaces of non-linear operators

Contributed Talks

17:20 - 17:45 Michael Benedikt Characterizations of topological queries in Spatial Databases

17:45 - 18:10 G.Litvinov, V.Maslov, G.Shpiz Dequantization, logic and fuzzy sets

July 24, Sunday

10:00 - 10:50 Zlil Sela Diophantine geometry over groups and the elementary theory of a free group VI

11:10 - 12:00 Nikolai Vereschagin Computational Complexity III

12:00 - 14:00 LUNCH

14:00 - 14:50 Ilya Kazachkov Axiomatisation and decidability of the universal theory of a free metabelian Lie algebra

15:00 - 15:50 TBA

Abstracts

Applications of completeness criterions to questions of computational complexity and randomness Marat Arslanov

                   Marat.Arslanov@ksu.ru

In my talk I shall be using my completeness criterions for several reducibilities (Turing reducibility, weak truth-table and truth-table reducibilities, conjunctive and many-one reducibilities) to estimate lower bounds of degrees (for these reducibilities) for a number of sets related to the computational complexity of computable functions, random strings and the halting probability of a universal self-delimitimg Turing machine.

New model-theoretic unprovability proofs for Peano Arithmetic Andrey Bovykin

                  andrey@logic.pdmi.ras.ru

We shall talk about model-theoretic independence results for Peano Arithmetic. We start off by mentioning major developments in the subject and explaining the model-theoretic reasons for unprovability of certain ramseyan statements. We shall proceed by discussing threshold results (determining the gap between provability and unprovability) and a model-theoretic approach to determining logical strength of Canonical Ramsey Theorem and Regressive Ramsey Theorem (using strong initial segments of J.Paris and L.Kirby). We shall conclude the talk with a discussion of recent results on approximation of infinitary principles by their densities.

On the Model Theory of Universal Covering Spaces of Complex Algebraic Varieties Misha Gavrilovich

                  gavrilov@maths.ox.ac.uk

We ask what is an appropriate language for formalising the notion of a path (up to homotopy), and provide a partial answer by proposing the notion of catogoricity, canonicity, as the measure of being “appropriate”, and proving a partial result toward the statement that the groupoid of paths on a smooth projective complex variety in a (the?) natural language describing the groupoid structure, is uncountably categorical in infinitary logic L_{ω_{1}ω}.

This is our motivation; however, the main part of the talk will be devoted to the following question of of complex analytic geometry, and could be understood independently. We consider the universal covering space of a smooth projective complex manifold, and define a topology on it; a set is T-closed if it can be obtained as a union of connected components of of a complex analytic subset invariant under the action of a finite index subgroup of the fundamental group, or a finite union of such sets. Under a conjecture of Shafarevich and some conditions, we prove that such sets do form a topology, which enjoys the following properties important it our context: an analytic irreducible component of closed set is T-closed, the projection of a closed set is closed, and these sets are definable in a natural countable language associated with subvarieties defined over the rational numbers.

Complexity of definable relations in computable models and

non-autoequivalent representations Sergei Goncharov

                     sergei@math.nsc.ru

We will discuss the problems about characterization of theoretical-model complexity of computable models and definable relations on computable models. It is connected with problems of algorithmic dimensions and complexity index sets for different classes of models. We will consider the connection of complexity definable relations of computable models with computable numberings in general sense relative to classification of sets. The main results from my talk were proved by S.Goncharov, V. S. Harizanov, J. F. Knight, C. McCoy, R. Miller, and R. Solomon. This work was supported by NSF grant.

Families of sets with special enumeration properties have been used to produce interesting examples in computable structure theory. V. Selivanov constructed a family of sets that S.Goncharov used to produce a structure that is computably categorical but not relatively computably categorical. M. Manasse used Selivanov’s family of sets to produce a computable structure with a relation that is intrinsically c.e. but not relatively intrinsically c.e. S. Goncharov constructed families of sets that he then used to produce computable structures with computable dimension n, for all finite n. S.Wehner constructed a family of sets that yields a structure with isomorphic copies in exactly the non-computable degrees. T. Slaman produced another such structure.

Here we lift the results of S.Goncharov, M.Manasse, and T.Slaman and S.Wehner to higher levels. Using Selivanov’s construction, in relativized form, we show that for each computable successor ordinal α, there is a computable structure that is Δ_{α}^{0} categorical, but not relatively Δ_{α}^{0} categorical. From this structure, we obtain another computable structure, with a relation that is intrinsically Δ_{α}^{0} but not relatively intrinsically Δ_{α}^{0}. Using the enumeration results of S.Goncharov, relativized, we show that for each computable successor ordinal α, and each finite n, there is a computable structure with exactly n computable copies, up to Δ_{α}^{0} isomorphism. Using the enumeration result of S.Wehner, also relativized, we show that for each computable successor ordinal α, there is a structure with copies in just the degrees of sets X such that Δ_{α}^{0}(X) is not Δ_{α}^{0}. In particular, for each finite n, there is a structure with copies in just the non-low_{n} degrees.

We state the enumeration results of Selivanov, Goncharov, and Wehner. We say how enumeration properties of a family of sets translate into properties of graph structures derived from the family. We proved the basic results of Goncharov, Manasse, and Slaman and Wehner from general construction models from families of c.s.sets. We found a construction that, for a computable successor ordinal α, transforms a graph G into a structure G^{∗} such that G has a Δ_{α}^{0} copy iff G^{∗} has a computable copy, and we indicate how various special features of G translate into features of G^{∗} and constructed new series of models with non-autoequivalent computable representations relative to arithmetical hierarchy.

References

[1] Ash, C. J., and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, 2000.

[2] Ash, C. J., J. F. Knight, M. Mannasse, and T. Slaman, “Generic copies of countable structures”, Annals of Pure and Applied Logic, vol. 42(1989), pp. 195-205.

[3] Ash, C. J., and A. Nerode, “Intrinsically recursive relations”, in Aspects of Effective Algebra, ed. by J. N. Crossley, Upside Down A

Book Co., Steel’s Creek, Australia, pp. 26-41.

[4] Barker, E., “Intrinsically Σ_{1}^{0} relations”, Annals of Pure and Applied Logic, vol. 39(1988), pp. 105-130.

[5] Chisholm, J., “Effective model theory versus recursive model theory”, J. Symb. Logic, vol. 55(1990), pp. 1168-1191.

[6] Cholak, P., S. S. Goncharov, B. Khoussainov, and R. A. Shore, “Computably categorical structures and expansions by constants, J. of Symb. Logic, vol. 64(1999), pp. 13-37.

[7] Goncharov, S. S., “The quantity of non-autoequivalent constructivizations”, Algebra and Logic, vol. 16(1977), pp. 257-282.

[8] Manasse, M., Techniques and Counterexamples in Almost Categorical Recursive Model Theory, Ph.D. Thesis, Univ. of Wisconsin, Madison, 1982.

[9] Selivanov, V. L., “Enumerations of families of general recursive functions”, Algebra and Logic, vol. 15(1976), pp. 205-226.

[10] Slaman, T., “Relative to any non-recursive set”, Proc. of the Amer. Math. Soc., vol. 126(1998), pp. 2117-2122.

[11] Wehner, S., “Enumerations, countable structures, and Turing degrees”, Proc. of the Amer. Math. Soc., vol. 126(1998), pp. 2131-2139.

Institute of Mathematics SB RAS, Novosibirsk University, Russia Some applications of approximations of infinite groups by

finite ones Evgeniy Gordon

                       cfyig@eiu.edu

The notion of approximation of infinite groups by finite algebraic systems was introduced in the author’s monograph “Nonstandard methods in commutative harmonic analysis”. The language of nonstandard analysis (or the language of ultraproducts) is very convenient for investigation of problems connected with this notion. In this talk we discuss various of approximations of infinite groups in various areas of mathematics from Approximations of pseudodifferential operators to cellular automata on discrete groups and the property of amenability. The techique of ultraproducts (nonstandard analysis) is crucial for all these applications

Recursion on Spaces of Non-Linear Operators Edward Griffor^{1}

                     egriffor@umich.edu

The talk will introduce definable classes of non-linear operators that arise from closed loop control systems using a new scheme of continuous recursion. The recursion scheme is defined explicitly over the linear space obtained as an image of L^{2} under the LaPlace transform. Both it and its inverse are studied in terms of the original dynamical system.

1This research is supported by NSF Grant DMS-0432603

References

[1] M Cosnard M Garzon and P Koiran, Computability Properties of Low dimensional Dynamical Systems, Theoretical Computer Science 132 (1994)

[2] L. Lipshitz and L A Rube. Differentially Algebraic Replacement Theorem and Analog Computability, Proceeding of the American Mathematical Society, 99 (1987)

[3] M B PourEl, Abstract Computability and its Relation to the General Purpose Analog Computer, Transaction of the American Mathematical Society, 199 (1974)

[4] C. Moore, Recursion Theory on the Reals and Continuous-time Computation, Sante Fe Institute, 1995.

DaimlerChrysler, Auburn Hills, MI and The University of Michigan, Ann Arbor, MI 48230

Model theory of pairs of abelian groups Wilfrid Hodges

                    w.hodges@qmul.ac.uk

This finally sorts out work I began in the 1980s. Anatolii Yakovlev helped to get it moving again when I visited St Petersburg nine years ago, and a preliminary account appeared in the proceedings of the 1997 Leeds Logic Colloquium. But only recently I found time to sort the details properly. The questions revolve round categoricity properties of abelian groups with a distinguished subgroup.

The Maximality of Continuous Logic Jose Iovino

                    iovino@math.utsa.edu

In recent years, a great deal of effort has been devoted to replicating the successes of first-order model theory in non first-order contexts; particularly, in contexts of analysis and topology. Two approaches that have received some attention are that of compact abstract theories [1] and that of positive bounded formulas and approximate satisfaction [3]. Recently, these two approaches have converged in a new formalism, developed by Ben-Yaacov, Berenstein, Henson, and Usvyatsov and based on old ideas of Keisler [2], called Continuous Logic .

We will discuss a Lindstrom-type maximality theorem for Continuous Logic.

References

[1] I. Ben-Yaacov, Positive model theory and compact abstract theories, J. Math. Logic 3 (2003), 85–118.

[2] C. C. Chang and H. J. Keisler, Continuous Model Theory, Princeton Univ. Press (1966).

[3] C. W. Henson and J. Iovino, Ultraproducts in Analysis, in Analysis and Logic, London Mathematical Society Lecture Notes 262, Cambridge University Press (2002), 1–113.

On the problems of definability in the enumeration degrees Iskander Sh. Kalimullin^{2}

                 Iskander.Kalimullin@ksu.ru

The talk will be devoted to problems of definability of natural classes and predicates in the ordering of enumeration degrees.

In particular, the problem on definability of the class TOT of total degrees posed by Rogers [2] in 1967 will be discussed.

It is interesting to note that the problem has a positive solution if we replace the class TOT by the class TOT(≥ 0′_{e}) of all total enumeration degrees above the e-degree 0′_{e}. Theorem. ([1]) The class TOT(≥ 0′_{e}) is definable by the formula

Ψ(x) = (∃a > 0_{e})(∃b > 0_{e})[x = a ∪ b & (∀z)[(a ∪ z) ∩ (b ∪ z) = z]] & (∀c > 0_{e})(∀d > 0_{e})(∀e > 0_{e})[(∀z)[(c ∪ z) ∩ (d ∪ z) = (c ∪ z) ∩ (e ∪ z) = z] → d ∪ x = e ∪ x]. The results from [1] allow to state the following hypothesis

Hypothesis. An e-degree x is total iff

(∀u)(∀a)[[(∀z ≥ u)[(a ∪ z) ∩ (x ∪ z) = z] ⟹ a ≤ u ∨ x ≤ u].

There are series of new results in favour this hypothesis.

References

[1] Kalimullin, I. Sh. Definability of the jump operator in the enumeration degrees, J. Math. Logic., vol. 3, no. 2 (2003), 257–267.

[2] H. Rogers, Jr. Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.

Kazan State University, Kazan, Russia

2Supported by grants of RFBR 02-01-00169

Cardinal Invariants Related to Permutation Groups Bart Kastermans and Yi Zhang

          bkasterm@umich.edu and yizhang@umich.edu

This talk will consist of three parts. In the first part we will introduce the almost disjoint families we are interested in and their related cardinal invariants, 𝔞_{p} and 𝔞_{g}, and the diamond principle we use, ♢(^{ℕ}ℕ, =^{∞}). In the second part we present the results and an outline of how to get them. The main result is Con(𝔞_{p} = 𝔞_{g} = ℵ_{1} < ℵ_{2} = cf(Sym(ℕ)), obtained through ♢(^{ℕ}ℕ, =^{∞}) ⇒ 𝔞_{g} = ℵ_{1} ∧ 𝔞_{p} = ℵ_{1}. Then in the last part we present some open questions.

Axiomatisation and decidability of the universal theory of a

free metabelian Lie algebra Ilya V. Kazatchkov

                  Ilya.Kazachkov@gmail.com

In this talk we study universal closures ucl(F) and ucl_{F} (F) of a free metabelian Lie algebra F over a finite field in the first order language of Lie algebras and in the language enriched by constants from F from several viewpoints. We give an axiomatic description (we present recursive sets of axioms for ucl(F) and for ucl_{F} (F)), an algebraic description and describe the algebras from ucl(F) and ucl_{F} (F) as coordinate algebras of irreducible algebraic sets. This allows us to prove that the universal theory of F is decidable and give a description of irreducible algebraic sets over F.

Finitary abstract elementary classes Meeri Kesälä (Viljanen)

                 meeri.viljanen@helsinki.fi

In recent years classical geometric stability theory has been generalized to homogeneous and excellent classes. Questions arise in what generality the methods behind these generalizations still work. Abstract elementary classes provide a nice platform for such studies.

Finitary AEC is a distinguished subclass of abstract elementary classes with additional assumptions. The assumptions follow from disjoint amalgamation, the existence of a prime model over ∅, Löwenheim-Skolem number being ω, Tameness and a property we call Finite Character. We begin with the ω-stable case. This setting generalizes the context of excellent classes and ω-stable homogeneous classes.

We say that an abstract elementary class (𝕂, ≼_{𝕂}) has finite character if the following holds: whenever A, B ∈ 𝕂, A ⊂ B, and for all finite ā ∈ A we have C ∈ 𝕂 and strong embeddings f : A → C and g : B → C such that f(ā) = g(ā), then A ≼_{𝕂} B. For example, if L is any logic with the property that every formula φ ∈ L has only finitely many free variables, then the L-elementary submodel -relation has finite character. Finite character allows us to use weak types, as we call them, in place of Galois types.

In finitary AEC we are able to construct a notion of independence which, under simplicity, has all the usual properties of first order non-forking over complete types. This is joint work with Tapani Hyttinen.

References

[1] Tapani Hyttinen, Uncountably categorical local tame abstract elementary classes with disjoint amalgamation, Submitted [2] Tapani Hyttinen and Meeri Viljanen, Independence in Local Abstract

Elementary Classes, Submitted, 2005.

Department of Mathematics and Statistics P.O. Box 68 (Gustaf Hällströmin katu 2b) FIN-00014 University of Helsinki, Finland

A view on Makanin–Razborov process Igor Lysenok

                     lysionok@mi.ras.ru

Equations in free groups are solved by Makanin’s algorithm and solutions sets of equations are described in terms of Razborov fundamental sequences. In both cases, a technique of so-called generalized equations is essentially used. We provide a geometric way of interpreting generalized equations and their solutions.

Variations on the Burnside-Schur theorem Ilia Ponomarenko

                      inp@pdmi.ras.ru

According to the Burnside-Schur theorem any primitive permutation group containing a regular cyclic subgroup is either doubly transitive or is a subgroup of a one-dimensional affine group over a prime field. We discuss some generalizations of this theorem which are closely related with algorithmic problems (recognizing, isomorphism testing, finding the automorphism group) for circulant graphs.

Diophantine geometry over groups and the elementary theory

of a free group Zlil Sela

                    zlil@math.huji.ac.il

We study sets of solutions to systems of equations in a free group, projections of such sets (Diophantine sets), and the structure of elementary sets defined over a free group. The structure theory we obtain enable us to prove quantifier elimination, and answer affirmatively some of Alfred Tarski’s questions on the elementary theory of a free group.

Δ_{1} induction and Σ_{1} collection Neil Thapen

             neil.thapen@st-hildas.oxford.ac.uk

We present some recent work on these theories at the bottom of the arithmetic hierarchy. We show that Σ_{1} collection follows from Δ_{1} induction plus a very weak form of exponentiation.

Borel equivalence relations and classification problems for

countable structures Simon Thomas

                  sthomas@math.rutgers.edu

Suppose that L is a countable first-order language and that K is the class of countable models of some L_{ω_{1},ω}-sentence. In this tutorial, following Friedman-Stanley and Hjorth-Kechris, I will explain how to use the theory of Borel equivalence relations to analyze the isomorphism relation on K and develop a framework for measuring the complexity of possible complete invariants.

Throughout, I will concentrate on classes K of structures which are “finitely generated” in some broad sense, such as the class of finitely generated groups, the class of torsion-free abelian groups of finite rank, the class of fields of finite transcendence dimension, etc. As we shall see, these are the classes K whose isomorphism relations correspond to countable Borel equivalence relations; i.e. Borel equivalence relations E such that every E-equivalence class is countable. The tutorial will include an account of the connections between countable Borel equivalence relations and Zimmer’s superrigidity theory, as well as discussions of some of the many easily stated open problems in this area.

On the Bergman property for the automorphism groups of relatively free groups Vladimir Tolstykh

                 vtolstykh@yeditepe.edu.tr

A group G is said to have finite width relative to a generating set X if there is a natural number k such that every element of G can be expressed as a product of at most k elements of X^{±1}. A group with the Bergman property is a group which has finite width relative to any generating set.

The property is named after George Bergman who proved recently that it is satisfied by all infinite symmetric groups [1]. This result attracted a considerable attention and soon another examples of groups with the Bergman property have been found.

In a preprint version of [1] Bergman posed the following problem: does the automorphism group of a free group of infinite rank have finite width relative to any generating set? We shall present a sketch of the proof that the automoprhism group of a free group of countably infinite rand does have the Bergman property. The assumption of countability of rank is essential in our proof and so the general case remains open. We shall also give a sketch of the proof of the fact that the automorphism group of any free nilpotent group of infinite rank has the Bergman property.

References

[1] G. M. Bergman, ‘Generating infinite symmteric groups‘, Bull. Lon. Math. Soc, to appear.

Computational Complexity Nikolai Vereschagin

                        ver@mccme.ru

Computational models: deterministic machines, randomized machines, Boolean circuits. Complexity classes: Polynomial time (P), Polynomial size circuits (P/poly), Polynomial space (PSPACE), Randomized polynomial time (BPP). Provably hard problems. Theory of NP-completeness and Polynomial hierarchy. PSPACE-completeness. One-way functions and pseudo random generators.

Globalization of the partial isomorphisms Anatoly Vershik

                    vershik@pdmi.ras.ru

We consider a gerneral problem of the extension of partial actions upto global actions. Most improtant special cases are the case of finitie graphs and finits metric spaces. Celebrated theorem by Hrushevski (1991) solved the part of the problem for graphs. But the essential addendum to it consists in the possibility to give the extension which is equivariant with respect to global isomorhpisms. The same theorem can be proved for metric spaces. The general fact asserts that in a category it is possible iff

1. there exist Fraisse limit in the category;

2. the group of the automorphisms of the universal object contains everywhere dense locally finite subgroup.

In Russian:

Глобализация частичных изоморфизмов

Рассматривается общая проблема продолжения чаcтичных действий до глобальных. Два наиболее важных случая этой проблемы - продолжение частичных изоморфищмов графов и продолжение частичных изометрий конечных метрических пространств. Замечателньая теорема Хрущевского (1991) отчасти решает первую проблему. Однако существенное дополнение к ней состоит в том, что продолжение частичных изоморфизмов должно быть эквивариантным относительно глобальных изоморфизмов. Такое усиление возможно. Для метрических пространств аналогичная теорема также имеет место. Общая теорема состоит в том, что в некоторой категории такое продолжение возможно в том и только в том случае, когда

1. в категории существует универсальный объект (предел Фрессе) и

2. группа автоморфизмов универсального объекта содержит всюду плотную локально конечную подгруппу.

Phase transitions in logic and combinatorics Andreas Weiermann

                    weierman@math.uu.nl

We will present recent results on classifying the phase transition from provability to unprovability for mathematically appealing assertion in the context of first order Peano arithmetic (and related systems). We will show surprising connections between this area of logic and other fields in mathematics, like analytic combinatorics and Ramsey theory.

To this end we consider combinatorial assertions, like Friedman style tree theorems, and Paris Harrington- or Kanamori McAloon style Ramsey principles, and parameterize these with respect to a number-theoretic function. If this parameter function is bounded by a function of slow growth then the resulting assertion remains provable in the system under consideration but when the parameter function exceeds in growth a critical threshold then the resulting assertion, although still true, becomes unprovable.

The fine structure analysis of phase transitions yields applications to some classical open problems in mathematics. In particular we will discuss how the asymptotic of the standard Ramsey function for triples and three colors (a classical Erdös problem) is affected by the possible independence of a certain Paris Harrington principle.

Zariski Geometries: from classical to quantum Boris Zilber

                   zilber@maths.ox.ac.uk

We consider Geometry as a very broad concept and argue that a purely logical criterion for a ‘good mathematical theory’ explains the central role played by classical geometric theories, such as algebraic geometry and the theory of compact complex manifolds. This broad view on geometric structures led to a classification result and applications in Diophantine geometry and transcendental number theory. Recent discoveries indicate that the adequate context for representing good (Zariski) geometries is non-commutative (quantum) algebraic geometry.

Contributed Talks

Characterizations of topological queries in Spatial Databases

Michael Benedikt

              benedikt@research.bell-labs.com

A spatial query is a first-order sentence with predicates that range over semi-algebraic relations (or, more generally, definable relations in some o-minimal expansion of the real field). A query is topological if (informally) it depends only on the shape of a region. Our work concerns characterizing which first-order sentences are topological. One cannot decide whether a query is topological, but one can hope to give effective syntactic capturing exactly the topological queries. Our main result is a language capturing topological queries in the case where the relation symbol is restricted to be a closed region in the plane. I’ll overview the proof, which combines some results about queries over o-minimal structures, along with some automata theory. The main tool from automata theory is a characterization of which regular languages are first-order definable relative to a modulus class. This is joint work with Christoph Loeding, Jan van den Bussche, and Thomas Wilke.

Dequantization, logic and fuzzy sets G.L.Litvinov^{3}, V.P.Maslov, G.B.Shpiz

                     glitvinov@mail.ru

In this talk a brief survey of basic ideas of idempotent mathematics is presented. Relations between this theory and the logic, theory of fuzzy sets as well as the possibility theory and some applications are discussed.

Idempotent mathematics is the mathematics over semifiels and semirings with idempotent addition (this means that x+x=x). One of the most important idempotent semifields is the well-known max-plus algebra. Modern tropical mathematics is the mathematics over the max-plus algebra.

Let S be an idempotent semiring with neutral elements 0 and 1 and semiring operations ⊕ and ⊙. Then the Boolean algebra B = {0, 1} is a natural idempotent subsemiring of S. Thus S can be treated as a generalized (extended) logic with logical operations ⊕ (disjuction) and ⊙ (conjunction). Ideas of this kind are discussed in many books and papers with respect to generalized versions of logic and especially quantum logic.

Let Ω be the so-called universe consisting of “elementary events.” Denote by F(S) the set of functions defined on Ω and taking their values in S; then F(S) is an idempotent semiring with respect to the pointwise addition and multiplication of functions. We shall say that elements of F(S) are generalized fuzzy sets. We have the well-known classical definition of fuzzy sets (L. A. Zadeh) if S = P, where P is the segment [0, 1] with the semiring operations ⊕ = max and ⊙ = min. Of course, functions from F(P) taking their values in the Boolean algebra B = {0, 1} ⊂ P correspond to traditional sets from Ω and semiring operations correspond to standard operations for sets. In the general case functions from F(S) taking their values in B = {0, 1} ⊂ S can be treated as traditional subsets in Ω. If S is a lattice (i.e. x ⊙ y = inf{x, y} and x ⊕ y = sup{x, y}), then generalized fuzzy sets coincide with L-fuzzy sets in the sense of J. A. Goguen.

3This research was supported by the Russian Foundation for Basic Research, grant 05–01–00824

It is well known that the classical theory of fuzzy sets is a basis for the theory of possibility. Of course, it is possible to develop a similar generalized theory of possibility starting from generalized fuzzy sets. Generalized theories can be noncommutative; they seem to be more qualitative and less quantitative with respect to the classical theories.

In a sense, the traditional mathematics over numerical fields can be treated as a quantum theory, while the idempotent mathematics can be treated as a ‘classical shadow (or counterpart)’ of the traditional one. There exists the corresponding procedure of an idempotent dequantization. A special case of this dequantization is the so-called Maslov dequantization based on logarithmic transforms used by E. Schrödinger (1926) and E. Hopf (1950). In this case the parameter of the dequantization coincides with the Planck constant taking imaginary values. The Maslov dequantization generates ”tropicalization” and leads to tropical mathematics.

There exists a correspondence between interesting, useful and important constructions and results in the traditional mathematics and similar constructions and results in idempotent mathematics. This heuristic correspondence can be formulated in the spirit of the well-known N. Bohr’s correspondence principle in quantum mechanics; in fact, the two principles are intimately connected. For example, the Hamilton–Jacobi equation is an idempotent version of the Schrödinger equation, the variational principles of classical mechanics can be treated as an idempotent version of the Feynman path integral approach to quantum mechanics. The Legendre transform turns out to be an idempotent version of the Fourier transform etc. A systematic and consistent application of the idempotent correspondence principle leads to a variety of results (often quite unexpected) in different areas including algebra, geometry, mathematical physics, differential equations, optimization, analysis and numerical analysis, stochastic problems, computer applications.