In this talk, I will give a survey of elements of the history of computable functionals of finite types with an emphasis on the diversity both in approaches and in the applicability of the theory.

Towards the end, I will discuss some recent results on partial, sequential functionals obtained jointly with V. Sazonov.

The University of Oslo, Oslo (Norway) E-mail:dnormann@math.uio.no Мальцевские чтения 2009 Пленарные доклады Isotyped algebras B. Plotkin Let a variety of algebras be fixed. For every finite set of variables X we consider the free in algebra W (X) and a special algebra of first order formulas (X). The precise definition of (X) is given in terms of algebraic logic. Each ultrafilter T in (X) is called X-type. A type T is called an X-type of the algebra H in if it can be presented as a logical kernel of a point in the affine space HX. For every algebra H consider all X-types of the algebra H. The set of such types is denoted by SX(H).

Definition. Algebras H1 and H2 are called isotyped if for every X we have SX(H1) =SX(H2).

In the talk we consider a geometric approach to this model-theoretic notion. This approach leads to new results and various problems.

Hebrew University, Jerusalem E-mail:plotkin@macs.biu.ac.il Мальцевские чтения 2009 Пленарные доклады Algebraic geometry over solvable groups N. S. Romanovski Algebraic geometry over groups is a new theory which was recently used in solving well-known Tarski problems. As in the classical case one can define the Zariski topology on affine space Gn for any group G. This topology is good (noetherian) if and only if the group G is equationally noetherian, i.e., any system of equations over x1,..., xn is equivalent to some finite subsystem. For example, free groups are equationally noetherian.

We describe a wide class of solvable groups, so-called rigid groups, which contains free solvable groups, and study algebraic geometry over such groups. We prove that any rigid group is equationally noetherian and develop the dimension (Krull) theory over rigid groups.

Furthermore, we introduce divisible rigid groups and describe the coordinate groups of their irreducible algebraic sets. Some results are joint with Kanta Gupta and Alexei Miasnikov.

Institute of Mathematics, Novosibirsk, Russia E-mail:rmnvski@math.nsc.ru Мальцевские чтения 2009 Пленарные доклады Mixing modality and probability D. S. Scott Orlov first [1928] and Gdel later [1933] pointed out the connection between the Lewis System S4 and Intuitionistic Logic. McKinsey and Tarski gave an algebraic formulation and proved completeness theorems for propositional systems using as models topological spaces with the interior operator corresponding to the necessitation modality. Earlier, Tarski and Stone had each shown that the lattice of open subsets of a topological space models intuitionistic propositional logic. Expanding on a suggestion of Mostowski about interpreting quantifiers, Rasiowa and Sikorski used the topological models to model many first-order logics.

After the advent of Solovey’ s recasting of Cohen’ s independence proofs as using Boolean-valued models, topological models for modal higher- order logic were studied by Gallin and others. For Boolean-valued logic, the complete Boolean algebra M = Meas([0, 1])/Null of measurable subsets of the unit interval modulo sets of measure zero gives every proposition a probability. Perhaps not as well known is the observation that the measure algebra also carries a nontrivial S4 modality defined with the aid of the sublattice Open([0, 1])/Null of open sets modulo null sets. This sublattice is closed under arbitrary joins and finite meets in the measure algebra, but it is not the whole of the measure algebra.

By working by analogy to the construction of Boolean-valued models for ZF, we can construct over M a model for a modal ZF (MZF) where membership and equality predicates have interesting and natural modal properties. In such a universe the real numbers correspond to random variables, and — following a suggestion of Alex Simpson (Edinburgh) — there is also an well motivated modeling of random reals.

A modal set theory, however, requires a reexamination of comprehension principles, and much work remains to be done to organize methods of proof to take account of the new distinctions encountered. It is also possible to recast well known theorems of Ergodic Theory as principles about this modal universe, and the question to be considered is whether the new perspective can lead to some new results.

Carnegie Mellon University and University of California, Berkeley E-mail:dana.scott@cs.cmu.edu Мальцевские чтения 2009 Пленарные доклады Embedding lattices into derived lattices M. Semenova The problem of embedding algebras into algebras possessing certain properties is a classical one in universal algebra. Due to a well-known result of A. I. Maltsev, the class of semigroups embeddable into groups forms a quasivariety, and that quasivariety is not finitely based.

In the talk, I shall consider classes of lattices which are embeddable into certain derived lattices. Most often, those classes of lattices turn to be quasivarieties. However, sometimes, they are varieties, and sometimes, they are even not first-order. I shall also mention some open problems and related topics.

Sobolev Institute of Mathematics SB RAS E-mail:udav17@gmail.com, semenova@math.nsc.ru Мальцевские чтения 2009 Пленарные доклады The omega-enumeration degrees I. Soskov The semi-lattice of the omega enumeration degrees is an extension of the enumeration degrees based on a certain reducibility on sequences of sets of natural numbers. In the talk we shall discuss some features of the omega enumeration degrees concerning the properties of the jump operation, the group of the automorphisms and the local theory. We will argue that studying the omega enumeration degrees could give us a powerful tool for better understanding the classical structures of the enumeration and Turing degrees.

Sofia University E-mail:soskov@fmi.uni-sofia.bg Мальцевские чтения 2009 Пленарные доклады Distributions of countable models of small theories S. V. Sudoplatov It is known [1] that any countable model of a small theory T is either prime over a tuple or limit. Therefore the number I(T, ) of countable models of T can be represented as the sum of the number Ip(T, ) of prime models over tuples and the number Il(T ) of limit models.

Atheory T is p-categorical (accordingly l-categorical, p-Ehrenfeucht, l-Ehrenfeucht) if Ip(T, ) = 1 (accordingly Il(T ) =1, 1

Obviously that the p-categoricity of T is equivalent to the countable categoricity, its p-Ehrenfeuchtness means that the system RK(T ) of Rudin—Keisler preorder (see [1]) is finite, and the p-Ehrenfeuchtness and the condition 1 Il(T ) < are satisfied iff I(T, ) <, i.e. T is an Ehrenfeucht theory. Using the following theorem, generalizing the characterization [2] of p-Ehrenfeucht theories to the class of all small theories, we characterize the classes of l-categorical and l-Ehrenfeucht theories.

Theorem 1. Any small theory T satisfies the following conditions:

(1) the system RK(T ) is upward directed and has the least element (the isomorphism type of prime model of T ), IL( ) =0;

(2) if is a RK-sequence of nonprincipal types qn, n, such that each type q of T is related by q RK qn for some n, then there exists a limit model over ; in particular, Il(T ) 1 and the countable saturated model is limit over if exists;

(3) if is a RK-sequence of types qn, n, and (Mq )n is an elementary chain n such that any co-finite subchain doesn’t consist of pairwise isomorphic models, then there exists a limit model over ;

(4) if =(qn)n is a subsequence of RK-sequence, then any limit model over is limit over ;

(5) if = (qn)n and = (qn)n are RK-sequences of types such that for some k, m, since some n, any types qk+n and qm+n are connected by Mq Mq, then k+n m+n any model M is limit over iff M is limit over ;

Moreover the following decomposition formula is true:

I(T, ) =|RK(T )| + IL, where IL {, 1, 2} is the number of limit models related to the RK-sequence and not related to extensions and restrictions of that used for the calculation of all limit models, and the family of RK-sequences of types represents all RK-sequences, over which limit models exist.

The following Theorem generalizes Theorem 1 in [2] for arbitrary Rudin—Keisler preorders and correspondent distribution functions for numbers of limit models, where values of functions belong to {, 2}.

Theorem 2. Let X, be a finite or countable upward directed preordered set with a least element x0, f : Y {, 2} be a function with the set Y of all 0-sequences, i.e. of sequences in X \{x0}, forming all -chains, and satisfying the following conditions:

(1) f(y) 1, if for any x X there exists some x from the sequence y such that x x ;

(2) f(y) 1, if any co-finite subsequence of y doesn’t contain of pairwise equal elements;

(3) f(y) f(y ), if y is a subsequence of y;

(4) f(y) =f(y ), if y =(yn)n and y =(yn)n are sequences such that there exist some k, m for which yk+n = ym+n since some n.

Мальцевские чтения 2009 Пленарные доклады Then there exists a small theory T and an isomorphism g : X, RK(T ) such that any value f(y) is equal to the number of limit models over a RK-sequence (qn)n, correspondent the 0-sequence y = (yn)n, where g(yn) is the isomorphism type of the model Mq, n.

n Constructions in [3] allow to represent stable structures for the proof of Theorem 2.

The work is supported by RFBR grant No. 09-01-00336-a and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools via project NSh-344.2008.1.

References [1] Sudoplatov S. V. Complete Theories with Finitely Many Countable Models. I. Algebra and Logic, (2004), N 1, 62–69.

[2] Sudoplatov S. V. On the number of countable models of complete theories with finite Rudin — Keisler preorders. Siberian Math. J., 48 (2007), N 2, 334–338.

[3] Sudoplatov S. V. Stable theories with finitely many countable models. Algebra and Logic (submitted) Sobolev Institute of Mathematics, Novosibirsk (Russia) E-mail:sudoplat@math.nsc.ru Мальцевские чтения 2009 Пленарные доклады Constraints, graphs, algebra, logic, and complexity M. Y. Vardi A large class of problems in AI and other areas of computer science can be viewed as constraint-satisfaction problems. This includes problems in database query optimization, machine vision, belief maintenance, scheduling, temporal reasoning, type reconstruction, graph theory, and satisfiability. All of these problems can be recast as questions regarding the existence of homomorphisms between two directed graphs. It is well-known that the constraint-satisfaction problem is NP-complete. This motivated an extensive research program into identify tractable cases of constraint satisfaction.

This research proceeds along two major lines. The first line of research focuses on non-uniform constraint satisfaction, where the target graph is fixed. The goal is to identify those target graphs that give rise to a tractable constraint-satisfaction problem. The second line of research focuses on identifying large classes of source graphs for which constraintsatisfaction is tractable. We show in how tools from graph theory, universal algebra, logic, and complexity theory, shed light on the tractability of constraint satisfaction [1].

Work supported in part by NSF grants CCR-0311326, CCF-0613889, ANI-0216467, and CCF-0728882.

References [1] Kolaitis P. G., Vardi M. Y. A logical approach to constraint satisfaction. In: Complexity of Constraints, Lecture Notes in Computer Science 5250, pp. 125–155, Springer, 2008.

Rice University, Houston, TX (USA) E-mail:vardi@cs.rice.edu Мальцевские чтения 2009 Пленарные доклады Computing bounds from (arithmetical) proofs S. S. Wainer This survey talk will be about the function a +2x, its various generalizations to higher number classes, their natural role in providing ordinal analyses for a range of theories between “polynomial-time arithmetic” and 1-CA0, and their direct connections with associated combinatorial independence results such as Friedman’s miniaturized Kruskal theorems.

School of Mathematics, University of Leeds, UK E-mail:s.s.wainer@leeds.ac.uk Мальцевские чтения 2009 Пленарные доклады Computable separation in topology K. Weihrauch We study computable separation axioms for computable topological spaces. A computable topological space is a 4-tuple =(X,,, ) such that (X, ) is a topological T0space and : is a notation of a base of such that dom() is recursive and for some r.e. set S (dom())3, (u) (v) = {(w) | (u, v, w) S} for all u, v dom().

Let be the standard representation of the points, let be the inner representation of the open sets and let - be the outer representation of the closed sets. We introduce computable versions of the topological separation axioms T0 to T3. Examples:

: The multi-function t0 is (,, )-computable where t0 maps every (x, y) X2 such that x = y to some U such that (x U and y U) or (x U and y U).

: There is an r.e. set H such that (x, y, x = y)((u, v) H)(x (u)y (v)) and for all (u, v) H, (u) (v) = or (x) (u) ={x} (v).

: There are an r.e. set R dom() dom() and a computable function r :

such that for all w dom(), (w) = {(u) | (u, w) R} and for all (u, w) R, (u) - r(u, w) (w).

The relations between these axioms are clarified completely. We have the following equivalences: SCT0 CT0 CT, CT1 CT CT2 CT (that is, 0 1 computable T1 = computable T2) and CT3 CT.

The remaining relations are summarized in the picture below. “A - B” means A = B, “A - B” means that we have constructed a computable topological space for C which A ¬B, and A - B” means that we have constructed a computable topological space for which (AC)¬B. D means that the space is discrete, hence topologically trivial.

WCT3 TT1 TD T4 CT SCT3 CT3 SCT2 CT2 CT0 WCTTD D D Further positive and negative results follow by transitivity of implication.

University of Hagen, Hagen, Germany E-mail:klaus.weihrauch@fernuni-hagen.de Мальцевские чтения 2009 Пленарные доклады On model theory, noncommutative geometry and physics B. Zilber In recent developments in the theory of Zariski structures it has been established that many quantum algebras can be represented as co-ordinate rings of Zariski geometries. We note that, on the other hand, the corresponding Zariski geometries can be approximated (in a certain model-theoretic sense) by Zariski structures of a finitary type, where Dirac calculus has a well-defined meaning. We use this to give a mathematically rigorous calculation of the Feynman propagator in a few simple cases.

Mathematical Institute, University of Oxford E-mail:zilber@maths.ox.ac.uk II. Секция «Теория групп» Мальцевские чтения 2009 Теория групп Об изоморфизме графов Кэли, порожденных транспозициями С. В. Августинович, Д. Г. Храмцов Пусть G — конечная группа, S — некоторое подмножество ее элементов, и пусть Cay(G, S) —граф Кэли группы G относительно множества порождающих S. Если всякий автоморфизм графа Cay(G, S) является автоморфизмом группы G, то говорят,что S обладает свойством CI (Cayley isomorphism). Также, пусть —произвольный граф на множестве вершин V = {1, 2,..., n}, обозначим через T () множество транспозиций, соответствующих ребрам графа. Множество T () порождает некоторую группу H и определяет граф Кэли Cay(H, T ()). Легко понять, что изоморфизм графов и влечет изоморфизм графов Cay(H, T ()) и Cay(H, T ( )). Верно и обратное.

Теорема. Пусть и — два произвольных графа на n вершинах. Если граф Cay(H, T ()) изоморфен графу Cay(H, T ( )), то графы и изоморфны.

Cледствие. Всякое множество транспозиций обладает CI-свойством.

Заметим, что не всякое множество инволюций порождает группу, в которой оно будет обладать CI-свойством. Это, в частности, следует из примера B. Alspach и L. Nowitz [1], доказавших, что элементарная абелева группа порядка 64 не является CI-группой. Тем не менее, есть основания полагать, что справедлива следующая Гипотеза. Произвольное множество инволюций,порождающих симметрическую группу Sn или знакопеременную группу An, удовлетворяет свойству CI.

Работа выполнена при государственной поддержке Ведущих научных школ России ИШ-344.2008.1 и АВЦП Рособразования ”Развитие потенциала Высшей школы”, проект 2.1.1.419, и финансовой поддержке РФФИ (проект 07-01-00248-а).

Список литературы 2 [1] Alspach B., Nowitz L. A. Elementary proofs that Zp and Zp are CI-groups. European Journal of Combinatorics, 20 (1999), N. 7, 607–617.

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