Аннотация:
Под слабой арифметической структурой мы будем понимать структуру на натуральных числах такую, что: а) все соответствующие ей предикаты и функции вычислимы; б) её элементарная (т.е. первопорядковая) теория разрешима. Примерами такого рода структур являются арифметики Пресбургера и Сколема, т.е. натуральные числа с равенством и сложением либо умножением. Цель настоящего доклада — познакомить слушателей с рядом результатов и проблем, связанных с определимостью в слабых арифметических структурах посредством монадических формул второго порядка. Здесь «монадические» означает, что все предикатные переменные имеют арность 1, т.е. их значениями являются одноместные предикаты на натуральных числах. На самом деле, в логике второго порядка именно монадические формулы зачастую представляют наибольший интерес. В докладе будет подробно разобран случай арифметики Пресбургера, менее подробно — случаи арифметики Сколема и некоторых родственных ей структур.
|
