О неразрешимости теории поля рациональных чисел и теории натуральных чисел с функцией последователя и отношением делимости

Планируется разобрать доказательства двух важных результатов Джулии Робинсон, связанных с неразрешимостью теорий структур $(\mathbb{Q}; +, \cdot, =)$ и $(\mathbb{N}; s, |)$, где $s$ обозначает функцию последователя, а $|$ — отношение делимости. Точнее, в первой из этих структур оказываются определимы натуральные числа, а во второй — сложение и умножение. Как следствие, обе теории имеют сложность $\Pi^0_\infty$. Мы также обсудим смежные результаты и открытые вопросы в данной области. Один из самых известных таких вопросов — об определимости сложения и умножения в структуре $(\mathbb{N}; s, \bot)$, где $x \bot y$ означает, что $x$ и $y$ взаимно просты, т.е. не имеют общих простых делителей. Этот вопрос тесно связан с интересной и по-прежнему открытой теоретико-числовой гипотезой, именуемой гипотезой Эрдёша–Вудса. Вместе с тем известно, что $(\mathbb{N}; +, \cdot, =)$ интерпретируема в $(\mathbb{N}; s, \bot)$, а потому теория последней также имеет сложность $\Pi^0_\infty$.

Рассказ будет разбит на два заседания семинара. Первая часть будет посвящена определимости натуральных чисел в поле рациональных чисел, а вторая — определимости сложения и умножения в $(\mathbb{N}; s, |)$, а также обсуждению определимости в $(\mathbb{N}; s, \bot)$ и гипотезе Эрдёша–Вудса.