Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Логика структур

Что можно выразить? Что можно проверить? Теория моделей, теория множеств

Вопросом о том, что можно определить, выразить на языке математики, обладая некоторым исходным запасом понятий, занимается выпускник нашей кафедры академик РАН Алексей Львович Семенов вместе с ее выпускником, учеником В. А. Успенского Сергеем Федоровичем Сопруновым, с ними работал и рано умерший замечательный математик, и тоже наш выпускник Андрей Альбертович Мучник, ученик А. Л. Семенова. Примером результата о выразимости является теорема Семенова о выразимости через сложение натуральных чисел всех отношений, задаваемых конечные автоматами в двух разных системах счисления. Недавний результат — описание всех подпространств выразимости в пространстве сложения рациональных чисел.

Среди других их результатов — решение вопросов о существовании алгоритма, который проверяет истинность утверждения в логическом языке относящихся к некоторых естественным структурам чисел и слов. Примером такой структуры являются натуральные числе со сложением и операцией экспоненты с фиксированным натуральным основанием. Ан. А. Мучник решил проблему, относящуюся к разрешимости теории бесконечного дерева и множества его вершин, поставленную М. Рабином на Международном математическом конгрессе в Ницце.

Одной из основных областей математической логики является теория моделей. Эта теория исследует соотношения между теориями и классами структур, ими описываемых. Исследования в теории моделей также ведет В. А. Любецкий.