Позивамо вас да присуствујете заједничком састанку Одељења за математику и Семинара за рачунарску логику у петак, 17. априла, са почетком у 14.15 часова, у сали 301ф, Математичког института САНУ, Кнеза Михаила 36, као и онлајн.
Предавач: Станиcлав Сперански, Steklov Mathematical Institute of RAS
Тема предавања: WEAK ARITNMETIC FROM THE VIEWPOINT OF MONADIC SECOND-ORDER LOGIC
Апстракт:
By a weak arithmetical structure we shall mean a structure on the natural numbers such that: a) all the corresponding predicates and functions are computable; b) its elementary (that is, first-order) theory
is decidable. Among the structures of this kind are Presburger’s and Skolem’s arithmetics, viz. the natural numbers with equality and either addition or multiplication. We are going to discuss monadic second-order definability in weak arithmetical structures and related complexity issues. Here `monadic’ means that only predicate variables of arity 1 — which range over unary predicates on the natural numbers — are allowed. In effect, in second order logic, it is often natural to focus on monadic formulas. We shall examine in detail the case of Presburger arithmetic, and somewhat less explicitly, the case of Skolem arithmetic and its reducts.
Напомена: Предавања можете пратити на даљину. Све информације су доступне на страници:
