#матлог #не_мехмат #МИАН

Научный семинар кафедры методов современной математики (базовая кафедра МИАН в МФТИ),
25 марта, вторник, 18.00, только онлайн (для получения ссылки пишите учёному секретарю кафедры Оноприенко А.А.)

К. А. Ковалёв. Об аксиоматизации арифметики Бюхи

Аннотация: Арифметикой Бюхи (с основанием p = 2) называется теория натуральных чисел в языке с нулем, функцией последователя, сложением и специальной функцией, обозначаемой V_p, которая число n отображает в наибольшую степень p, делящую n. Хорошо известно, что данная теория является разрешимой, однако неизвестно никакой явной аксиоматизации этой теории (есть некоторые отрицательные результаты, полученные А. Запрягаевым). Цель данной работы состоит в отыскании такой аксиоматизации. Наша аксиоматизация состоит из некоторого конечного числа простых аксиом (похожих на арифметику Робинсона) и схемы аксиом вида ∃x φ(x) → ∃x ≤ n_φ φ(x), где натуральное число n_φ подбирается так, чтобы данная формула была истинна в стандартной модели. Выбор такого числа n_φ опирается на важное свойство арифметики Бюхи, а именно, что любое определимое в рассматриваемом языке множество A является p-автоматным (т. е., множество p-ичных записей элементов A распознаваемо некоторым конечным автоматом).

➰ ВК