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

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

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

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

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

Заметки [ править ]

Ссылки [ править ]

• Булос, Джордж; Берджесс, Джон П .; Джеффри, Ричард К. (2002), вычислимость и логика (4-е изд.), Cambridge University Press, ISBN 978-0-521-00758-0.
• Бовыкин Андрей; Кэй, Ричард (2001), «О порядковых типах моделей арифметики», в Чжан И (ред.), Логика и алгебра , Современная математика, 302 , Американское математическое общество, стр. 275–285, ISBN. 978-0-8218-2984-4.
• Шор, Ричард (2011), «Рекурсивно перечислимые степени», в Griffor, ER (ed.), 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 математики, 105 (1): 121-139, DOI : 10,2307 / 1971028 , ISSN  0003 -486X , JSTOR  1971028 , Руководство по ремонту  0432435
• Тарский, Альфред (1936), "Der Wahrheitsbegriff in den formisierten Sprachen". Английский перевод «Концепция истины в формализованных языках» опубликован в Corcoran, J., ed. (1983), Логика, семантика и метаматематика: документы с 1923 по 1938 год (2-е изд.), Hackett Publishing Company, Inc., ISBN 978-0-915144-75-4

Внешние ссылки [ править ]

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