Запрягаев Александр//Арифметика Бюхи и теорема Кобхэма-Семёнова скачать в хорошем качестве

Запрягаев Александр//Арифметика Бюхи и теорема Кобхэма-Семёнова

Аннотация. На докладе пойдёт речь о представлении множеств, распознаваемых конечными автоматами, формулами в слабых арифметических теориях. Мы покажем, что распознаваемость подмножества N^m чисел, записанных в k-ичной системе счисления, автоматом эквивалентна выразимости с помощью сложения и дополнительной функции "y - наибольшая степень k, на которую делится x." Тем самым, существует серия расширений арифметики Пресбургера (теории натуральных чисел со сложением), естественно соответствующая автоматным подмножествам натурального ряда. Мы обсудим связанные вопросы алгоритмической разрешимости. Также мы наметим доказательство фундаментальной теоремы Кобхэма-Семёнова, которая связывает определимость при различных основаниях систем счисления k1, k2: если показатели k1 и k2 мультипликативно независимы (т.е. не существует s, t > 0, r > 1 таких, что r^s = k1, r^t = k2), то определимость подмножества N^m независимо в арифметиках Бюхи с показателем k1 и k2 эквивалентна простой определимости в арифметике Пресбургера.