Истинная арифметика - True arithmetic - Wikipedia

В математическая логика, истинная арифметика это набор всех истинных утверждений о арифметика из натуральные числа. ^[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}}.}$

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

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

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

${\displaystyle {\mathcal {N}}\models \theta \qquad }$ если и только если ${\displaystyle {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}}).}$

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

Теорема Поста является более точной версией теоремы о неопределенности, которая показывает связь между определимостью Чт (${\displaystyle {\mathcal {N}}}$) и Степени Тьюринга, с использованием арифметическая иерархия. Для каждого натурального числа п, позволять Чт_п(${\displaystyle {\mathcal {N}}}$) быть подмножеством Чт (${\displaystyle {\mathcal {N}}}$) состоящий только из предложений, которые ${\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}})}$

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

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

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

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

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

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

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

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

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

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

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

Примечания

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

Рекомендации

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

внешняя ссылка

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