Истинная арифметика

Множество всех истинных утверждений первого порядка об арифметике натуральных чисел

В математической логике истинная арифметика — это множество всех истинных утверждений первого порядка об арифметике натуральных чисел . ^[1] Это теория, связанная со стандартной моделью аксиом Пеано на языке аксиом Пеано первого порядка. Истинная арифметика иногда называется арифметикой Скулема, хотя этот термин обычно относится к другой теории натуральных чисел с умножением .

Определение

Сигнатура арифметики Пеано включает символы сложения, умножения и функции следования, символы равенства и отношения «меньше», а также константный символ для 0. (Правильно сформированные) формулы языка арифметики первого порядка строятся из этих символов вместе с логическими символами обычным способом логики первого порядка .

Структура определяется как модель арифметики Пеано следующим образом . ${\displaystyle {\mathcal {N}}}$

• Областью дискурса является множество натуральных чисел, ${\displaystyle \mathbb {N} }$
• Символ 0 интерпретируется как число 0,
• Символы функций интерпретируются как обычные арифметические операции над , ${\displaystyle \mathbb {N} }$
• Символы равенства и отношения «меньше» интерпретируются как обычные отношения равенства и порядка на . ${\displaystyle \mathbb {N} }$

Эта структура известна как стандартная модель или предполагаемая интерпретация арифметики первого порядка.

Предложение на языке арифметики первого порядка называется истинным в , если оно истинно в только что определенной структуре. Обозначение используется для указания того, что предложение истинно в ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\mathcal {N}}\models \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {N}}.}$

Истинная арифметика определяется как множество всех предложений на языке арифметики первого порядка, которые истинны в , записанных как Th( ) . Это множество, что эквивалентно, является (полной) теорией структуры . ^[2] ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\mathcal {N}}}$

Арифметическая неопределимость

Центральным результатом истинной арифметики является теорема о неопределимости Альфреда Тарского (1936). Она утверждает, что множество Th( ) ${\displaystyle {\mathcal {N}}}$ не является арифметически определимым. Это означает, что в языке арифметики первого порядка нет формулы такой, что для каждого предложения θ в этом языке ${\displaystyle \varphi (x)}$

${\displaystyle {\mathcal {N}}\models \theta \quad {\text{if and only if}}\quad {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}}).}$

Здесь представлена ​​цифра канонического гёделева номера предложения θ . ${\displaystyle {\underline {\#(\theta )}}}$

Теорема Поста — это более точная версия теоремы о неопределимости, которая показывает связь между определимостью Th( ) ${\displaystyle {\mathcal {N}}}$ и степенями Тьюринга с использованием арифметической иерархии . Для каждого натурального числа n пусть Th _n ( ) ${\displaystyle {\mathcal {N}}}$ будет подмножеством Th( ), ${\displaystyle {\mathcal {N}}}$ состоящим только из предложений, которые находятся или ниже в арифметической иерархии. Теорема Поста показывает, что для каждого n , Th _n ( ) арифметически определим, но только формулой сложности выше . Таким образом, ни одна формула не может определить Th( ) , потому что ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle {\mathcal {N}}}$

${\displaystyle {\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N}})}$

но ни одна формула не может определить Th _n ( ) ${\displaystyle {\mathcal {N}}}$ для произвольно большого n .

Свойства вычислимости

Как обсуждалось выше, Th( ) ${\displaystyle {\mathcal {N}}}$ не является арифметически определимым по теореме Тарского. Следствие теоремы Поста устанавливает, что степень Тьюринга Th ( ) ${\displaystyle {\mathcal {N}}}$ равна 0 ^(ω) , и поэтому Th( ) ${\displaystyle {\mathcal {N}}}$ не является ни разрешимым , ни рекурсивно перечислимым .

Th( ) ${\displaystyle {\mathcal {N}}}$ тесно связана с теорией Th( ) ${\displaystyle {\mathcal {R}}}$ рекурсивно перечислимых степеней Тьюринга в сигнатуре частичных порядков . ^[3] В частности, существуют вычислимые функции S и T, такие что:

• Для каждого предложения φ в сигнатуре арифметики первого порядка φ принадлежит Th( ) ${\displaystyle {\mathcal {N}}}$ тогда и только тогда, когда S ( φ ) принадлежит Th( ) ${\displaystyle {\mathcal {R}}}$ .
• Для каждого предложения ψ в сигнатуре частичных порядков ψ находится в Th( ) ${\displaystyle {\mathcal {R}}}$ тогда и только тогда, когда T ( ψ ) находится в Th( ) ${\displaystyle {\mathcal {N}}}$ .

Теоретико-модельные свойства

Истинная арифметика — нестабильная теория , и поэтому имеет модели для каждого несчетного кардинала . Поскольку существует континуум типов над пустым множеством, истинная арифметика также имеет счетные модели. Поскольку теория является полной , все ее модели элементарно эквивалентны . ${\displaystyle 2^{\kappa }}$ ${\displaystyle \kappa }$ ${\displaystyle 2^{\aleph _{0}}}$

Истинная теория арифметики второго порядка

Истинная теория арифметики второго порядка состоит из всех предложений на языке арифметики второго порядка , которым удовлетворяет стандартная модель арифметики второго порядка, часть первого порядка которой является структурой , а часть второго порядка состоит из каждого подмножества . ${\displaystyle {\mathcal {N}}}$ ${\displaystyle \mathbb {N} }$

Истинная теория арифметики первого порядка, Th( ) ${\displaystyle {\mathcal {N}}}$ , является подмножеством истинной теории арифметики второго порядка, и Th( ) ${\displaystyle {\mathcal {N}}}$ определима в арифметике второго порядка. Однако обобщение теоремы Поста на аналитическую иерархию показывает, что истинная теория арифметики второго порядка не определима никакой одной формулой в арифметике второго порядка.

Симпсон (1977) показал, что истинная теория арифметики второго порядка вычислимо интерпретируема с помощью теории частичного порядка всех степеней Тьюринга в сигнатуре частичных порядков, и наоборот .

Примечания

1. Булос, Берджесс и Джеффри 2002, стр. 295
2. см . теории, связанные со структурой
3. Шор 2011, стр. 184

Ссылки

• Булос, Джордж ; Берджесс, Джон П.; Джеффри , Ричард К. (2002), Вычислимость и логика (4-е изд.), Cambridge University Press, ISBN 978-0-521-00758-0.
• Бовыкин, Андрей; Кей, Ричард (2001), «О типах порядка моделей арифметики», в Чжан, И (ред.), Логика и алгебра , Contemporary Mathematics, т. 302, Американское математическое общество, стр. 275–285, ISBN 978-0-8218-2984-4.
• Shore, Richard (2011), «Рекурсивно перечислимые степени», в Griffor, ER (ред.), Handbook of Computability Theory , Studies in Logic and the Foundations of Mathematics, т. 140, North-Holland (опубликовано в 1999 г.), стр. 169–197, ISBN 978-0-444-54701-9.
• Симпсон, Стивен Г. (1977), «Теория первого порядка степеней рекурсивной неразрешимости», Annals of Mathematics , вторая серия, 105 (1), Annals of Mathematics: 121–139, doi : 10.2307/1971028, ISSN  0003-486X, JSTOR  1971028, MR  0432435
• Tarski, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". Английский перевод "The Concept of Truth in Formalized Languages" появляется в Corcoran, J., ed. (1983), Logic, Semantics and Metamathematics: Papers from 1923 to 1938 (2nd ed.), Hackett Publishing Company, Inc., ISBN 978-0-915144-75-4

Внешние ссылки

• Вайсштейн, Эрик В. «Арифметика». Математический мир .
• Вайсштейн, Эрик В. «Арифметика Пеано». MathWorld .
• Вайсштейн, Эрик В. «Теорема Тарского». MathWorld .