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

Основная информация

• ID статьи: 2110.01673
• Название: Model-completeness and decidability of the additive structure of integers expanded with a function for a Beatty sequence
• Авторы: Мохсен Хани, Али Н. Ализаде, Афшин Зарей
• Классификация: math.LO (математическая логика)
• Дата публикации: 17 апреля 2024 г. (финальная версия)
• Ссылка на статью: https://arxiv.org/abs/2110.01673

Аннотация

В данной работе представлена модельно-полная теория, которая полностью аксиоматизирует структуру $Z_α = ⟨Z, +, 0, 1, f⟩$, где $f : x ↦ ⌊αx⌋$ — унарная функция, а $α$ — фиксированное трансцендентное число. Когда $α$ вычислимо, данная теория рекурсивно перечислима и, как следствие полноты, разрешима. Этот результат соответствует более общей тематике добавления мультипликативных следов к целым числам без потери разрешимости.

Исследовательский контекст и мотивация

Проблемный фон

1. Основная проблема: Исследование разрешимости расширенных структур аддитивной группы целых чисел $⟨Z, +⟩$, в частности структур с добавлением функции последовательности Битти $f(x) = ⌊αx⌋$.
2. Научная значимость:
   • Находится на пересечении двух активных направлений исследований: с одной стороны, разрешимость и классификация расширений $⟨Z, +⟩$ (стабильные или нестабильные структуры)
   • С другой стороны, исследование расширений вещественной прямой с конкретными дискретными подгруппами сложения
3. Ограничения существующих работ:
   • Иеронимус в H16 доказал разрешимость только для квадратичных чисел $α$
   • Для трансцендентных чисел $α$ разрешимость более общей структуры $R_α$ остаётся нерешённой
   • Требуются новые методы для обработки независимости различных степеней $f$ в трансцендентном случае
4. Исследовательская мотивация:
   • Предоставить доказательство разрешимости для трансцендентных чисел
   • Использовать фундаментальные инструменты теории моделей и теории чисел для конструктивного доказательства
   • Заложить основу для решения более общей проблемы структуры $R_α$

Основные вклады

1. Построение модельно-полной теории: Конструирована теория $T_α$, полностью аксиоматизирующая структуру $Z_α = ⟨Z, +, 0, 1, f⟩$, где $f(x) = ⌊αx⌋$, $α$ — трансцендентное число.
2. Доказательство разрешимости: При вычислимости $α$ теория $T_α$ рекурсивно перечислима, и в сочетании с полнотой получается разрешимость.
3. Технические инновации:
   • Преобразование отношений дробной части в формулы первого порядка
   • Применение расширённой леммы Кронекера для обработки неалгебраических формул
   • Разработка методов редукции для алгебраических формул
4. Теоретический анализ: Доказано, что данная структура обладает свойством строгого порядка, проанализирована структура определимых множеств.

Подробное описание методов

Определение задачи

Исследование теории первого порядка структуры $Z_α = ⟨Z, +, 0, 1, f⟩$ в языке $L = \{+, -, 0, 1, f\}$, где:

• $Z$ — множество целых чисел
• $+$ — операция сложения
• $f: x ↦ ⌊αx⌋$ — функция последовательности Битти
• $α$ — фиксированное вычислимое трансцендентное число

Основная техническая схема

1. Логическое выражение дробной части

Ключевое наблюдение: Хотя дробная часть отсутствует в языке, её ключевые свойства можно описать в $L$ следующим образом:

Для $a, b ∈ Z$ и $n ∈ N$:

• $f(na) = nf(a) + i$ тогда и только тогда, когда $\frac{i}{n} < [αa] < \frac{i+1}{n}$
• $[αa] + [αb] < 1$ тогда и только тогда, когда $f(a+b) = f(a) + f(b)$
• $[αa] < [αb]$ тогда и только тогда, когда $f(b-a) = f(b) - f(a)$

где $[x] = x - ⌊x⌋$ обозначает дробную часть.

2. Стратегия классификации формул

Систематическое разделение $L$-формул на два класса:

Неалгебраические формулы: вида $\sum_{i=0}^{\ell_1} n_{1i}[αf^i(x_1)] + \cdots + \sum_{i=0}^{\ell_k} n_{ki}[αf^i(x_k)] \triangleleft \sum_{i=0}^{k'} m_i[αy_i] + [αq] + \ell$

Алгебраические формулы: вида $h_1(x_1) + \cdots + h_n(x_n) = y$, где $h_i(x)$ — $f$-полиномы.

3. Расширённая лемма Кронекера

Теорема 3.4 (Расширённая лемма Кронекера): Для каждого $n ∈ N$ следующее множество $(n+1)$-кортежей плотно в $(0,1)^{n+1}$: $\{([αa], [αf(a)], [αf^2(a)], \ldots, [αf^n(a)]) : a ∈ N\}$

Это верно, поскольку трансцендентность $α$ гарантирует линейную независимость $1, α, α^2, \ldots, α^n$ над $\mathbb{Q}$.

Стратегия доказательства модельной полноты

Шаг 1: Обработка неалгебраических формул

• Лемма 3.6: Для множества неалгебраических формул $Γ(x; \bar{y})$ существует бескванторная формула $χ(\bar{y})$ такая, что $Z_α ⊨ ∀\bar{y}(∃xΓ(x; \bar{y}) ↔ χ(\bar{y}))$
• Применение алгоритма исключения Фурье-Мотцкина для обработки систем линейных неравенств

Шаг 2: Методы редукции

• Лемма 4.12 (Техническая лемма): Редукция смешанных систем с алгебраическими формулами к неалгебраическим системам с меньшим числом переменных
• Ключевая идея: введение вспомогательной переменной $w$ и члена $h(x)$ для преобразования многопеременного алгебраического уравнения в однопеременный случай

Шаг 3: Алгебраическая замкнутость

• Лемма 4.13: Если $M_1 ⊆ M_2$ — модели $T_α$, $b ∈ M_1$, $a ∈ M_2$ и $h(a) = b$, то $a ∈ M_1$
• Гарантирует замкнутость подструктур относительно обратных операций различных степеней $f$

Аксиоматическая система

Схема аксиом 1 (Вычисление $f(n)$)

Для $n ∈ N$ и $0 ≤ i < n$ такого, что $\frac{f(n)}{n} ≡ i$: $f(\underbrace{1 + \cdots + 1}_{n \text{ раз}}) = \underbrace{f(1) + \cdots + f(1)}_{n \text{ раз}} + \underbrace{1 + \cdots + 1}_{i \text{ раз}}$

Аксиома 2 (Основные свойства)

1. $∀x∀y(f(x+y) = f(x) + f(y) ∨ f(x+y) = f(x) + f(y) + 1)$
2. $∀x(f(-x) = -f(x) - 1)$
3. $∀y∃x(\bigvee_{i=0}^{f(1)} y + i = f(x))$
4. Отношение $[αx] < [αy]$ является плотным линейным порядком

Схема аксиом 3 (Плотность)

Для $m, n ∈ N$: если $\bigwedge_{i=1}^n [αz_i] < [αy_i]$, то существует по крайней мере $m$ различных $x$ таких, что $\bigwedge_{i=1}^n [αy_i] < [αf^i(x)] < [αz_i]$.

Экспериментальные результаты и теоретический анализ

Основные результаты

Главная теорема: Пусть $α$ — трансцендентное вещественное число, тогда:

1. $T_α$ — полная и модельно-полная аксиоматизация структуры $Z_α$
2. $Z_α$ обладает свойством строгого порядка
3. Когда $α$ вычислимо, $T_α$ разрешима

Свойства определимых множеств

1. Структурированные множества: Формулы без степеней $f$ определяют классы вычетов (бесконечные арифметические прогрессии)
2. Случайные множества: Множества, определяемые формулами со степенями $f$, не содержат бесконечные арифметические прогрессии
3. Смешанные свойства: Область значений любого $f$-полинома содержит конечные арифметические прогрессии произвольной длины

Предложение 5.1: Для $h(x) = \sum_{i=0}^k m_i f^i(x)$ для каждого $n ∈ N$ в области значений $h$ существует арифметическая прогрессия длины $n$.

Связанные работы

1. Иеронимус H16: Доказательство разрешимости $R_α$ для квадратичных $α$
2. Конант и Пиллэй CP18: Исследование классификации стабильности расширений $⟨Z, +⟩$
3. Гюнайдин и Озсахакян GO22: Независимое исследование, рассматривающее последовательности Битти как предикаты, а не функции
4. Хани и Зарей KZ22: Упрощённое доказательство для золотого сечения

Заключение и обсуждение

Основные выводы

1. Успешное обобщение результата Иеронимуса с квадратичных чисел на трансцендентные
2. Предоставление конструктивного доказательства модельной полноты
3. Установление новой технической схемы для работы с трансцендентными числами

Ограничения

1. Требуется вычислимость $α$ для гарантии рекурсивной перечислимости
2. Проблема более общей структуры $R_α$ остаётся нерешённой
3. Исключение кванторов в трансцендентном случае, по-видимому, невозможно

Направления будущих исследований

1. Открытая проблема: Разрешимость и модельная полнота структуры $⟨Z, <, +, -, 0, 1, f⟩$ (с добавлением порядка целых чисел)
2. Обобщение на другие типы трансцендентных чисел
3. Исследование разрешимости более сложных комбинаций последовательностей Битти

Технические инновационные моменты

1. Эффективная модельная полнота: Процесс доказательства конструктивен и позволяет эффективно выполнять исключение кванторов
2. Связь с o-минимальностью: Связь неалгебраической части $T_{nalg}$ с o-минимальными теориями
3. Унифицированная схема: Единый подход к обработке алгебраических и неалгебраических формул

Глубокая оценка

Преимущества

1. Теоретический вклад: Значительное обобщение известных результатов, переход от квадратичных чисел к трансцендентным — важный прогресс
2. Технические инновации: Применение расширённой леммы Кронекера и разработка методов редукции весьма творческие
3. Универсальность методов: Методы применимы к случаям алгебраических чисел
4. Конструктивное доказательство: Предоставляет эффективный результат модельной полноты

Недостатки

1. Вычислительная сложность: Хотя теоретически разрешима, практическая сложность может быть очень высокой
2. Ограничения выразительности: Невозможно обработать некоторые естественные связанные структуры
3. Техническая сложность: Доказательство включает несколько сложных технических лемм

Влияние

1. Научная ценность: Предоставляет новые методы и результаты для области математической логики и теории моделей
2. Перспективы применения: Закладывает основу для исследования более сложных арифметических структур
3. Методологический вклад: Демонстрирует систематический подход к обработке смешанных алгебро-аналитических структур

Области применения

1. Исследование теории разрешимости в математической логике
2. Диофантовы проблемы в арифметической геометрии
3. Автоматическое доказательство теорем в информатике
4. Исследование свойств распределения в теории чисел

Список литературы

• H16 P. Hieronymi, Expansions of the ordered additive group of real numbers by two discrete subgroups
• KZ22 M. Khani and A. Zarei, The additive structure of integers with the lower Wythoff sequence
• HM+21 P. Hieronymi et al., Decidability for Sturmian words
• C60 I. G. Connell, Some properties of Beatty sequences II