On the structures of continuous and smooth functions, and some ideas on decidability of elementary theories

Oleg Kudinov and Vladislav Amstislavskiy

(Novosibirsk)

Some ideas on decidablity of elementary theories
Oleg Kudinov, Sobolev Institute of Mathematics

The first part of the present talk is devoted to some new method, that is similar to the famous interpretation method, that could be used for establishing decidability results as well as for obtaining results on undecidability.
After the origin of the method, only few applications were obtained by V. Amstislavskiy, related to the elementary theories of some lattices of continuous and smooth functions. It is a real challenge to find more applications or adopt the method for more complicated problems.
The second part of the talk is devoted to the situation around the famous problem in field theory, related to decidability of the elementary theory of the field Fp t . Mostly, the problem of model completeness of mentioned theory and the theory of some assosiated class of fields of positive characteristic will be considered.

On the structures of continuous and smooth functions
Vladislav Amstislavskiy. Sobolev Institute of Mathematics, Novosibirsk

We study some new applications of the generalized method of interpretations. With this method offered by Kudinov O.V. we proved decidability of the theory of the lattice of continuous functions from R to R and from Rn to R for n > 1. Using this method we also proved that the theories of the structures of continuous functions over some perfectly normal space are m− equivalent to the theories of open subsets of this space. Thereby, by proving that the theory of the structure of open subsets of some perfectly normal space is decidable, decidability of the theory of the structure of continuous functions over this space is proved as well.

All these results are about the lattices of continuous functions. In our recent work we study the question of decidability of the theory of differential functions (C 1 (R); ≤), where C 1 (R) is an algebraic structure of the set of differential functions from R to R and ≤ is the pointwise order. To use the generalized method of interpretations it is required to understand where we can interpret this theory satisfying all the formal conditions of the method. The new applications of the generalized method of interpretations let consider it as a useful tool to prove decidability of theories.
Thursday 18th July 2013, 14:00
Robert Recorde Room
Department of Computer Science