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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

модельные

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

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

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

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

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

Ссылки

• Булос, Джордж ; Берджесс, Джон П .; Джеффри, Ричард К. (2002), Вычислимость и логика (4-е изд.), Cambridge University Press, ISBN  978-0-521-00758-0 .
• Бовыкин, Андрей; Кэй, Ричард (2001), «О порядковых типах моделей арифметики», в книге Чжан И (редактор), «Логика и алгебра» , «Современная математика», том. 302, Американское математическое общество, стр. 275–285, ISBN.  978-0-8218-2984-4 .
• Шор, Ричард (2011), «Рекурсивно перечислимые степени», в Гриффор, Э.Р. (ред.), Справочник по теории вычислимости , Исследования по логике и основам математики, том. 140, Северная Голландия (опубликовано в 1999 г.), стр. 169–197, ISBN.  978-0-444-54701-9 .
• Симпсон, Стивен Г. (1977), «Теория первого порядка степеней рекурсивной неразрешимости», Annals of Mathematics , Second Series, 105 (1), Annals of Mathematics: 121–139, doi : 10.2307/1971028 , ISSN   0003 -486X , JSTOR   1971028 , MR   0432435
• Тарский, Альфред (1936), «Понятие истины в формализованных языках». Английский перевод «Концепция истины на формализованных языках» опубликован в Коркоран, Дж., изд. (1983), Логика, семантика и метаматематика: статьи с 1923 по 1938 год (2-е изд.), Hackett Publishing Company, Inc., ISBN  978-0-915144-75-4

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

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