Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 510, № 1, стр. 3-7

1. ВВЕДЕНИЕ

Арифметической теорией называется первопорядковая теория, моделью которой служат натуральные числа $\mathbb{N}$ с некоторыми операциями над ними.

Согласно первой теореме Гёделя о неполноте, арифметика Пеано PA, язык которой содержит как сложение, так и умножение, является неполной и неразрешимой теорией. В связи с этим представляет интерес изучение арифметических теорий с менее выразительным языком, для которых устанавливаются полнота и разрешимость. Такие теории называют слабыми арифметиками. В частности, в литературе рассматриваются арифметика Пресбургера ${\mathbf{PrA}} = {\mathbf{Th}}(\mathbb{N}; = , + )$ [6] и арифметика Сколема ${\mathbf{Th}}(\mathbb{N}; = , \cdot )$.

Арифметики Бюхи являются важным классом расширений арифметики Пресбургера, поскольку сохраняют свойство разрешимости и находят применение в описании множеств, принимаемых конечными автоматами.

Определение 1. Арифметикой Бюхи BA_n, $n \geqslant 2$, называется элементарная теория ${\mathbf{Th}}(\mathbb{N}, = , + ,{{V}_{n}})$, где V_n – унарный функциональный символ такой, что ${{V}_{n}}(x)$ – наибольшая степень n, делящая x. Для определенности полагаем ${{V}_{n}}(0) = 0$.

Серия теорий BA_n была предложена Ю. Бюхи [1] в качестве инструмента для описания распознаваемости подмножеств $\mathbb{N}$ в конечных автоматах на арифметическом языке. Эта связь явно устанавливается посредством следующего классического результата В. Брюйер [2, 3]:

Теорема 1.1. Пусть $\varphi ({{x}_{1}}, \ldots ,{{x}_{m}})$ – формула в языке BA_n. Тогда существует и эффективно строится автомат $\mathcal{A}$ такой, что $({{a}_{1}}, \ldots ,{{a}_{m}})$ принимается $\mathcal{A}$ тогда и только тогда, когда $\mathbb{N} \vDash \varphi ({{a}_{1}}, \ldots ,{{a}_{m}})$.

Наоборот, пусть $\mathcal{A}$ – конечный автомат, обрабатывающий $m$-кортежи $n$-ичных натуральных чисел. Тогда существует и эффективно строится формула $\varphi ({{x}_{1}}, \ldots ,{{x}_{m}})$ в языке BA_n такая, что $\mathbb{N} \vDash \varphi ({{a}_{1}}$, ..., a_m) тогда и только тогда, когда (a₁, ..., a_m) принимается $\mathcal{A}$.

Здесь подразумевается, что автомат $\mathcal{A}$ получает на вход $m$-кортежи натуральных чисел в виде последовательных $m$-кортежей последних, затем предпоследних и т.д. цифр их n-ичной записи. Теорема Кобхэма-Семёнова [4, 5] утверждает, что для мультипликативно независимых натуральных чисел $n,m$ (пара чисел $n,m$ называется мультипликативно независимой, если уравнение ${{n}^{k}}$ = m^l не имеет решений в целых числах, кроме $k = l$ = 0), всякое множество, определимое в BA_n и BA_m, на самом деле определимо в арифметике Пресбургера PrA.

Мы рассматриваем интерпретации BA_n в себя. А. Виссер поставил следующий вопрос: если дана слабая арифметическая теория $T$, верно ли, что всякая интерпретация (одномерная или многомерная) $T$ в себя изоморфна тождественной, и если так, то всегда ли возникающий изоморфизм выразим формулой $T$? Этот вопрос был положительно разрешен в случае арифметики Пресбургера PrA в работе автора с Ф. Пахомовым [7]. Поскольку арифметики Бюхи являются консервативными расширениями PrA с добавлением нового функционального символа, они являются естественным классом теорий для дальнейшего рассмотрения.

В настоящей работе мы доказываем, что даже для всякой интерпретации PrA в BA_n внутренняя модель изоморфна стандартной, что дает частичный положительный ответ на вопрос Виссера. Остается открытым вопросом, обязательно ли этот изоморфизм является BA_n-определимым.

Можно показать, что для всякой $m$-мерной интерпретации $\iota $ некоторой структуры A в BA_n, существует одномерная интерпретация $\iota {\kern 1pt} '$, изоморфная $\iota $, но не обязательно определимо. Тем самым, в многомерном случае вопрос наличия изоморфизма (но не его BA_n-определимости) также разрешен положительно.

2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

Мы рассматриваем одномерные непараметрические интерпретации арифметик Бюхи согласно [8, с. 20–21]. Интерпретацией $\iota $ языка первого порядка $\mathcal{K}$ в структуре $\mathfrak{B}$ языка $\mathcal{L}$ называют следующую совокупность формул в языке $\mathcal{L}$:

1. ${{D}_{\iota }}(y)$, задающая множество ${{{\mathbf{D}}}_{\iota }} \subseteq \mathfrak{B}$ (область определения);

2. ${{P}_{\iota }}({{x}_{1}}, \ldots ,{{x}_{n}})$ для всякого предикатного символа $P({{x}_{1}}, \ldots ,{{x}_{n}})$ из $\mathcal{K}$;

3. ${{f}_{\iota }}({{x}_{1}}, \ldots ,{{x}_{n}},y)$ для всякого функционального символа $f({{x}_{1}}, \ldots ,{{x}_{n}})$ из $\mathcal{K}$.

Здесь от всех ${{f}_{\iota }}$ требуется, чтобы они задавали график некоторой функции (по модулю интерпретации предиката равенства).

Естественным образом $\iota $ и $\mathfrak{B}$ задают модель $\mathfrak{A}$ языка $\mathcal{K}$ с носителем ${{{\mathbf{D}}}_{\iota }}/{{ \sim }_{\iota }}$, где отношение эквивалентности ${{ \sim }_{\iota }}$ задается ${{ = }_{\iota }}({{x}_{1}},{{x}_{2}})$. $\mathfrak{A}$ называют внутренней моделью $\mathcal{K}$.

Если к тому же $\mathfrak{A} \vDash {\mathbf{T}}$, то $\iota $ называют интерпретацией теории ${\mathbf{T}}$ в $\mathfrak{B}$. Если для теории первого порядка U интерпретация $\iota $ является интерпретацией ${\mathbf{T}}$ вне зависимости от выбора $\mathfrak{B} \vDash {\mathbf{U}}$, то $\iota $ называют интерпретацией теории ${\mathbf{T}}$ в U.

Мы будем рассматривать интерпретации BA_n в себя. Поскольку BA_n является элементарной теорией $(\mathbb{N}; = , + ,{{V}_{n}})$, это эквивалентно рассмотрению интерпретаций в стандартной модели BA_n, т.е. $\mathbb{N}$. Наша задача состоит в установлении, для всякой ли интерпретации $\iota $ теории BA_n получающаяся внутренняя модель изоморфна стандартной. Тем самым требуется определить, интерпретируема ли какая-либо нестандартная модель BA_n в арифметике Бюхи. Порядковые типы нестандартных моделей BA_n описывает следующий стандартный результат.

Теорема 2.1. Всякая нестандартная модель $\mathcal{A} \vDash {\mathbf{B}}{{{\mathbf{A}}}_{n}}$ имеет порядковый тип $\mathbb{N} + \mathbb{Z} \cdot A$, где $\langle A{{, < }_{A}}\rangle $ – некоторый плотный линейный порядок без первой и последней точек. В частности, всякая счетная нестандартная модель BA_n имеет порядковый тип $\mathbb{N} + \mathbb{Z} \cdot \mathbb{Q}$.

Забывая о ${{V}_{n}}(x)$, становится возможным рассматривать интерпретацию нестандартной модели BA_n в арифметике Бюхи как интерпретацию одного сложения (т.е., интерпретацию арифметики Пресбургера PrA). Согласно теореме 1.1, всякая интерпретация произвольной структуры A в BA_n является ее автоматным представлением; в частности, интерпретация $(\mathbb{N}; = , + )$ индуцирует автоматный моноид в качестве своей внутренней модели.

Следующее необходимое условие для автоматных групп установили Браун и Штрюнгманн [9, теорема 10].

Теорема 2.2. Пусть $(A, + )$ – автоматная абелева группа без кручения. Тогда в $A$ существует подгруппа $B$, изоморфная ${{\mathbb{Z}}^{m}}$ для некоторого $m$ такая, что факторгруппа $C = A{\text{/}}B$ является прямой суммой конечного числа групп вида $\mathbb{Z}({{p}^{\infty }})$. В частности, порядки элементов $C$ могут делиться лишь на конечный список различных простых ${{p}_{1}}, \ldots ,{{p}_{s}}$.

Понятно, что внутренняя модель, индуцируемая интерпретацией PrA, является не абелевой группой, а лишь моноидом, поскольку ни один из элементов, кроме нуля, не наделен аддитивным обратным. Однако это легко исправить, введя отрицательные числа отдельно и определив покомпонентное сложение. Тем самым, всякая интерпретация PrA в BA_n на самом деле порождает интерпретацию соответствующей абелевой группы.

Лемма 2.1. Пусть PrA интерпретируется в BA_n посредством интерпретации $\iota $. Тогда она продолжается до интерпретации упорядоченной абелевой группы таким образом, что интерпретация PrA соответствует неотрицательным целым числам.

3. ТЕОРЕМА И ДОКАЗАТЕЛЬСТВО

Лемма 3.1. Пусть $\iota $ – интерпретация PrA в стандартной модели $\mathbb{N}$ арифметики Бюхи BA_n. Тогда внутренняя модель $\mathcal{A}$, индуцированная $\iota $, изоморфна тождественной.

Доказательство. Предположим противное. Пусть $\iota $ – такая интерпретация PrA, что внутренняя модель нестандартна. Поскольку $\mathbb{N}$ счетна, по теореме 2.1 получаем, что порядковый тип внутренней модели равен $\mathbb{N} + \mathbb{Z} \cdot \mathbb{Q}$.

Применяя лемму 2.1, можем перейти к интерпретации $\iota {\kern 1pt} '$ упорядоченной абелевой группы $\mathcal{B}$, порядковый тип которой изоморфен $\mathbb{Z} \cdot \mathbb{Q} + \mathbb{Z} + \mathbb{Z} \cdot \mathbb{Q}$ = = $\mathbb{Z} \cdot \mathbb{Q}$.

Поскольку порядковый тип упорядоченной абелевой группы $\mathcal{B}$ равен $\mathbb{Z} \cdot \mathbb{Q}$, можно рассматривать галактики, т.е. множества вида $[c]: = \{ d \in \mathcal{B}\,|\,\left| {c - d} \right|\; - $ стандартное натуральное число}. В частности, стандартные целые числа являются одной из галактик, а именно содержащей нуль (нейтральный элемент $\mathcal{B}$). Стандартным образом, по аналогии с доказательством теоремы 2.1, устанавливается следующая

Лемма 3.1. Сложение на галактиках [c + d] := := $[c] + [d]$, а также порядок [c] < $[d]\,\mathop = \limits^{{\text{def}}} \,c\, < \,d\, \wedge \,[c]\, \ne \,[d]$, корректно определены.

Иными словами, на множестве $\mathcal{B}{\text{/}}\mathbb{Z}$, где $\mathbb{Z}$ – стандартные целые числа, индуцируется структура группы, упорядоченной в соответствии с индуцированным порядком. Более того, выполнена следующая лемма:

Лемма 3.2. $\mathcal{B}{\text{/}}\mathbb{Z}$ содержит подгруппу Q, изоморфную $(\mathbb{Q}, + )$.

Доказательство. Зафиксируем произвольную положительную нестандартную галактику $[c]$. Мы определим изоморфизм $\varphi :\mathbb{Q} \to \mathcal{B}{\text{/}}\mathbb{Z}$ следующим образом. Для всякого $n \in \mathbb{Z}$ положим $\varphi (n): = [nc]$. Согласно лемме 3.1, это корректно определенное вложение $\mathbb{Z}$ в $\mathcal{B}{\text{/}}\mathbb{Z}$.

Пусть теперь k/l – рациональное число. Зададим $\varphi (k{\text{/}}l)$ как такую галактику [x], что $l \cdot x = kc$ + t для некоторого стандартного t. Поскольку в арифметике Пресбургера ровно одно из чисел kc, kc + 1, ..., $kc + l - 1$ всегда делится $l$, такие t и $x$ всегда возможно подобрать. Теперь покажем, что определение $\varphi (k{\text{/}}l)$ корректно.

Класс [x] не зависит от выбора t. В самом деле, пусть t и $t{\kern 1pt} '$ – разные стандартные числа, и lx = = $kc + t$, $lx{\kern 1pt} ' = kc + t{\kern 1pt} '$. Тогда $l(x - x{\kern 1pt} ') = (t - t{\kern 1pt} ')$ – стандартное число. Поэтому $x - x{\kern 1pt} '$ стандартно, откуда $[x] = [x{\kern 1pt} ']$.

Класс $[x] = \varphi (k{\text{/}}l)$ не зависит от представления $k{\text{/}}l$. Пусть ${{k}_{1}}{\text{/}}{{l}_{1}}\, = \,{{k}_{2}}{\text{/}}{{l}_{2}}$, т.е., ${{l}_{2}}{{k}_{1}} = {{l}_{1}}{{k}_{2}}$, и $\varphi ({{k}_{i}}{\text{/}}{{l}_{i}})$ = = [x_i], $i = 1,2$. Это означает, что ${{l}_{i}} \cdot {{x}_{i}} = {{k}_{i}}c + {{t}_{i}}$. Поэтому

Поскольку ${{l}_{2}}{{t}_{1}} - {{l}_{1}}{{t}_{2}}$ стандартно, ${{x}_{1}} - {{x}_{2}}$ тоже стандартно, и $[{{x}_{1}}] = [{{x}_{2}}]$.

Сложение согласовано со сложением на $\mathbb{Q}$. Пусть ${{k}_{1}}{\text{/}}{{l}_{1}},{{k}_{2}}{\text{/}}{{l}_{2}} \in \mathbb{Q}$, и $\varphi ({{k}_{i}}{\text{/}}{{l}_{i}}) = [{{x}_{i}}]$, $i = 1,2$. В $\mathbb{Q}$ мы имеем ${{k}_{1}}{\text{/}}{{l}_{1}} + {{k}_{2}}{\text{/}}{{l}_{2}} = ({{k}_{1}}{{l}_{2}} + {{k}_{2}}{{l}_{1}}){\text{/}}{{l}_{1}}{{l}_{2}}$. Пусть y – такой элемент $\mathcal{B}{\text{/}}\mathbb{Z}$, что для некоторого t выполнено ${{l}_{1}}{{l}_{2}}y = {{k}_{1}}{{l}_{2}}c + {{k}_{2}}{{l}_{1}}c + t$. Требуется показать, что $[{{x}_{1}}] + [{{x}_{2}}] = [y]$. Запишем ${{l}_{i}} \cdot {{x}_{i}} = {{k}_{i}}c + {{t}_{i}}$. Умножая равенства на ${{l}_{2}}$ и ${{l}_{1}}$ соответственно и складывая, получаем

Следовательно, $y - ({{x}_{1}} + {{x}_{2}}) = t - ({{l}_{1}}{{t}_{2}} + {{l}_{2}}{{t}_{1}})$, что является стандартным числом φ инъективно. Пусть ${{k}_{1}}{\text{/}}{{l}_{1}} \ne {{k}_{2}}{\text{/}}{{l}_{2}}$, $\varphi ({{k}_{i}}{\text{/}}{{l}_{i}}) = [{{x}_{i}}]$, i = 1, 2. Нужно показать, что $[{{x}_{1}}] \ne [{{x}_{2}}]$. Предположим, что $[{{x}_{1}}]$ = = [x₂]. Тогда ${{x}_{1}} - {{x}_{2}}$ стандартно. Но в таком случае $[0] = [{{x}_{1}} - {{x}_{2}}] = \varphi ({{k}_{1}}{\text{/}}{{l}_{1}} - {{k}_{2}}{\text{/}}{{l}_{2}})$, где ${{k}_{1}}{\text{/}}{{l}_{1}}\, - \,{{k}_{2}}{\text{/}}{{l}_{2}}$ – ненулевое рациональное число. По определению это означает, что $0 = ({{k}_{1}}{{l}_{2}} - {{l}_{1}}{{k}_{2}})c + t$ для некоторого t. Но t – стандартно, а $({{k}_{1}}{{l}_{2}} - {{l}_{1}}{{k}_{2}})c$ – нет, поэтому указанное равенство невозможно. Доказательство леммы завершено.

Вернемся к доказательству Теоремы 3.1 и покажем, что $\mathcal{B}$ не может быть автоматной. Предположим противное: пусть $\mathcal{B}$ автоматна. Тогда она удовлетворяет условиям Теоремы 2.2. Таким образом, в $\mathcal{B}$ существует подгруппа $\mathcal{E}$, изоморфная ${{\mathbb{Z}}^{m}}$, такая, что $\mathcal{F} = \mathcal{B}{\text{/}}\mathcal{E}$ – группа кручения, и порядки всех ее элементов делятся только на простые из списка ${{p}_{1}}, \ldots ,{{p}_{s}}$. Мы покажем, что это противоречит лемме 3.2 о существовании подгруппы $Q \subseteq \mathcal{B}{\text{/}}\mathbb{Z}$, изоморфной $\mathbb{Q}$. Далее под $\mathbb{Z}$ понимается конкретная подгруппа стандартных целых чисел в $\mathcal{B}$.

Пусть $\mathcal{G} = \langle \mathbb{Z},\mathcal{E}\rangle $ – подгруппа $\mathcal{B}$, порожденная $\mathbb{Z}$ и $\mathcal{E}$, и $\pi :\mathcal{B}{\text{/}}\mathbb{Z} \twoheadrightarrow \mathcal{B}{\text{/}}\mathcal{G}$ – естественный сюръективный гомоморфизм, переводящий всякий из классов эквивалентности в содержащий его класс из $\mathcal{B}{\text{/}}\mathcal{G}$. Рассмотрев цепочку сюръективных гомоморфизмов $\mathcal{B}\xrightarrow{\rho }\mathcal{B}{\text{/}}\mathbb{Z}\xrightarrow{\pi }\mathcal{B}{\text{/}}\mathcal{G}$, мы видим, что $\mathcal{G}\, = \,Ker(\pi \circ \rho )\, = \,{{\rho }^{{ - 1}}}(Ker(\pi ))$, откуда $Ker(\pi )\, = \,\mathcal{G}{\text{/}}\mathbb{Z}$.

Теперь установим образ Q под действием $\pi $. В общем случае, если имеется сюръективный гомоморфизм между группами $\sigma :A \twoheadrightarrow B$ и S – подгруппа A, то выполнено $\sigma (S) \cong S{\text{/}}(S \cap Ker(\sigma ))$. В самом деле, два элемента $a,b \in S$ попадают в один и тот же класс $S{\text{/}}(S \cap Ker(\sigma ))$ тогда и только тогда, когда $(a - b) \in Ker(\sigma )$, что эквивалентно $\sigma (a) = \sigma (b)$. В нашем случае, находим, что $\pi (Q) \cong Q{\text{/}}(Q \cap Ker(\pi )) = Q{\text{/}}(Q \cap \mathcal{G}{\text{/}}\mathbb{Z}).$

Группа $\mathcal{G}{\text{/}}\mathbb{Z}$ конечно порождена как факторгруппа конечно порожденной. Она не обязательно свободна, но, согласно теореме о классификации конечно порожденных абелевых групп, может быть представлена в виде прямой суммы ${{\mathbb{Z}}^{r}}$ для некоторого r и компонента кручения $T = {{\mathbb{Z}}_{{{{q}_{1}}}}} \oplus \ldots \oplus {{\mathbb{Z}}_{{{{q}_{t}}}}}$. Поскольку $Q \cap T = \{ 0\} $, имеем $Q{\text{/}}(Q \cap \mathcal{G}{\text{/}}\mathbb{Z}) \cong Q{\text{/}}{{\mathbb{Z}}^{r}}$. Следующая лемма показывает, что $Q{\text{/}}{{\mathbb{Z}}^{r}}$ изоморфно $Q{\text{/}}h\mathbb{Z}$ для некоторого рационального $h$:

Лемма 3.3. Множество, порожденное в $(\mathbb{Q}, + )$ набором элементов

Доказательство. Приведем дроби к общему знаменателю:

Для d из формулировки леммы согласно алгоритму Евклида существует представление в виде линейной комбинации a₁ · k₁l₂l₃...l_r + a₂ · l₁k₂l₃...l_r + ... + + ${{a}_{r}} \cdot {{l}_{1}}{{l}_{2}} \ldots {{k}_{r}}$ = d, причем любая линейная комбинация с другими коэффициентами равна кратному d. Поэтому ${{a}_{1}} \cdot {{k}_{1}}{\text{/}}{{l}_{1}} + \ldots + {{a}_{r}} \cdot {{k}_{r}}{\text{/}}{{l}_{r}} = d{\text{/}}({{l}_{1}} \ldots {{l}_{r}})$, и всякая прочая линейная комбинация равна кратному $d{\text{/}}({{l}_{1}} \ldots {{l}_{r}})$.

Итак, $\mathbb{Q}{\text{/}}{{\mathbb{Z}}^{r}} = \mathbb{Q}{\text{/}}h\mathbb{Z}$, где $h: = d/({{l}_{1}} \ldots {{l}_{r}})$ найдено в доказательстве Леммы 3.3. Пусть $q$ – простое, отсутствующее в списке ${{p}_{1}}, \ldots ,{{p}_{s}}$. Тогда элемент $[h{\text{/}}q] \in Q{\text{/}}(Q \cap \mathcal{G}{\text{/}}\mathbb{Z}) \subseteq \mathcal{B}{\text{/}}\mathcal{G}$ имеет в точности порядок q. Однако, поскольку $\mathcal{F} = \mathcal{B}{\text{/}}\mathcal{E}$ является группой кручения с ограничением на порядки элементов, это же выполнено и для $\mathcal{B}{\text{/}}\mathcal{G}$, где отождествлено больше элементов. Следовательно, мы указали элемент $\mathcal{B}{\text{/}}\mathcal{G}$ с порядком, разложение которого не ограничено ${{p}_{1}}, \ldots ,{{p}_{s}}$. Противоречие с Теоремой 2.2.