Принципы индукции, ограничения и наименьшего числа

В арифметике первого порядка принципы индукции , ограничивающие принципы и принципы наименьшего числа представляют собой три связанных семейства принципов первого порядка, которые могут выполняться или не выполняться в нестандартных моделях арифметики . Эти принципы часто используются в обратной математике для проверки аксиоматической силы теорем.

Определения [ править ]

Неформально, для первого порядка формулы арифметики $\varphi (x)$ с одной свободной переменной, принцип индукции для $\varphi$ выражает справедливость математической индукции по $\varphi$ , а принцип наименьшего числа для $\varphi$ утверждает, что если $\varphi$ есть свидетель , есть хотя бы один. Для формулы $\psi (x,y)$ в двух свободных переменных ограничивающий принцип для $\psi$ утверждает, что для фиксированной границы $k$ , если для каждого $n<k$ есть $m_{n}$ такой, что $\psi (n,m_{n})$ , то мы можем найти границу $m_{n}$ х.

Формально принцип индукции для $\varphi$ это предложение: ^[1]

{\mathsf {I}}\varphi :\quad {\big [}\varphi (0)\land \forall x{\big (}\varphi (x)\to \varphi (x+1){\big )}{\big ]}\to \forall x\ \varphi (x)

Аналогичный принцип сильной индукции действует и для $\varphi$ : ^[1]

{\mathsf {I}}'\varphi :\quad \forall x{\big [}{\big (}\forall y<x\ \ \varphi (y){\big )}\to \varphi (x){\big ]}\to \forall x\ \varphi (x)

Принцип наименьшего числа для $\varphi$ это предложение: ^[1]

{\mathsf {L}}\varphi :\quad \exists x\ \varphi (x)\to \exists x'{\big (}\varphi (x')\land \forall y<x'\ \,\lnot \varphi (y){\big )}

Наконец, ограничивающий принцип для $\psi$ это предложение: ^[1]

{\mathsf {B}}\psi :\quad \forall u{\big [}{\big (}\forall x<u\ \,\exists y\ \,\psi (x,y){\big )}\to \exists v\ \,\forall x<u\ \,\exists y<v\ \,\psi (x,y){\big ]}

Чаще всего мы рассматриваем эти принципы не просто для одной формулы, а для класса формул в арифметической иерархии . Например, ${\mathsf {I}}\Sigma _{2}$ представляет собой схему аксиом, состоящую из ${\mathsf {I}}\varphi$ для каждого $\Sigma _{2}$ формула $\varphi (x)$ в одной свободной переменной.

Нестандартные модели [ править ]

Может показаться, что принципы ${\mathsf {I}}\varphi$ , ${\mathsf {I}}'\varphi$ , ${\mathsf {L}}\varphi$ , ${\mathsf {B}}\psi$ тривиальны и действительно справедливы для всех формул $\varphi$ , $\psi$ в стандартной модели арифметики $\mathbb {N}$ . Однако они становятся более актуальными в нестандартных моделях. Напомним, что нестандартная модель арифметики имеет вид $\mathbb {N} +\mathbb {Z} \cdot K$ для некоторого линейного порядка $K$ . Другими словами, он состоит из исходной копии $\mathbb {N}$ , элементы которого называются конечными или стандартными , за которыми следует множество копий $\mathbb {Z}$ расположены в форме $K$ , элементы которого называются бесконечными или нестандартными .

Теперь, учитывая принципы ${\mathsf {I}}\varphi$ , ${\mathsf {I}}'\varphi$ , ${\mathsf {L}}\varphi$ , ${\mathsf {B}}\psi$ в нестандартной модели ${\mathcal {M}}$ , мы видим, как они могут потерпеть неудачу. Например, гипотеза принципа индукции ${\mathsf {I}}\varphi$ только гарантирует, что $\varphi (x)$ справедливо для всех элементов стандартной части ${\mathcal {M}}$ - это может не выполняться для нестандартных элементов, до которых невозможно добраться путем итерации операции-преемника с нуля. Аналогично, ограничивающий принцип ${\mathsf {B}}\psi$ может потерпеть неудачу, если привязано $u$ нестандартно, так как тогда (бесконечный) набор $y$ может быть решающим в ${\mathcal {M}}$ .

Отношения между принципами [ править ]

Между принципами (по теории слабой базы) имеют место следующие соотношения: ${\mathsf {PA}}^{-}+{\mathsf {I}}\Sigma _{0}$ ): ^[1]^[2]

${\mathsf {I}}'\varphi \equiv {\mathsf {L}}\lnot \varphi$ для каждой формулы $\varphi$ ;
${\mathsf {I}}\Sigma _{n}\equiv {\mathsf {I}}\Pi _{n}\equiv {\mathsf {I}}'\Sigma _{n}\equiv {\mathsf {I}}'\Pi _{n}\equiv {\mathsf {L}}\Sigma _{n}\equiv {\mathsf {L}}\Pi _{n}$ ;
${\mathsf {I}}\Sigma _{n+1}\implies {\mathsf {B}}\Sigma _{n+1}\implies {\mathsf {I}}\Sigma _{n}$ , и оба импликации являются строгими;
${\mathsf {B}}\Sigma _{n+1}\equiv {\mathsf {B}}\Pi _{n}\equiv {\mathsf {L}}\Delta _{n+1}$ ;
${\mathsf {L}}\Delta _{n}\implies {\mathsf {I}}\Delta _{n}$ , но неизвестно, изменится ли это.

Над ${\mathsf {PA}}^{-}+{\mathsf {I}}\Sigma _{0}+{\mathsf {exp}}$ Сламан что доказал, ${\mathsf {B}}\Sigma _{n}\equiv {\mathsf {L}}\Delta _{n}\equiv {\mathsf {I}}\Delta _{n}$ . ^[3]

Обратная математика [ править ]

Принципы индукции, ограничения и наименьшего числа обычно используются в обратной математике и арифметике второго порядка . Например, ${\mathsf {I}}\Sigma _{1}$ является частью определения подсистемы ${\mathsf {RCA}}_{0}$ арифметики второго порядка. Следовательно, ${\mathsf {I}}'\Sigma _{1}$ , ${\mathsf {L}}\Sigma _{1}$ и ${\mathsf {B}}\Sigma _{1}$ это все теоремы ${\mathsf {RCA}}_{0}$ . Подсистема ${\mathsf {ACA}}_{0}$ подтверждает все принципы ${\mathsf {I}}\varphi$ , ${\mathsf {I}}'\varphi$ , ${\mathsf {L}}\varphi$ , ${\mathsf {B}}\psi$ для арифметических $\varphi$ , $\psi$ . Известно, что принцип бесконечной ячейки эквивалентен принципу ${\mathsf {B}}\Pi _{1}$ и ${\mathsf {B}}\Sigma _{2}$ над ${\mathsf {RCA}}_{0}$ . ^[4]

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

^ Jump up to: ^а ^б ^с ^д ^и Гаек, Петр; Пудлак, Павел (2016). Метаматематика арифметики первого порядка . Ассоциация символической логики c/- Издательство Кембриджского университета. ISBN 978-1-107-16841-1 . OCLC 1062334376 .
^ Пэрис, Дж.Б.; Кирби, LAS (1978), «Σn-Схемы коллекций в арифметике» , Logic Colloquium '77 , Elsevier, стр. 199–209, doi : 10.1016/s0049-237x(08)72003-2 , ISBN 978-0-444-85178-9 , получено 14 апреля 2021 г.
^ Сламан, Теодор А. (1 августа 2004 г.). " $\Sigma _{n}$ -ограничивающий и $\Delta _{n}$ -индукция» . Proceedings of the American Mathematical Society . 132 (8): 2449. doi : 10.1090/s0002-9939-04-07294-6 . ISSN 0002-9939 .
^ Херст, Джеффри (август 1987 г.). Комбинаторика в подсистемах арифметики второго порядка (доктор философии). Государственный университет Пенсильвании.

[:0-1] Jump up to: ^а ^б ^с ^д ^и Гаек, Петр; Пудлак, Павел (2016). Метаматематика арифметики первого порядка . Ассоциация символической логики c/- Издательство Кембриджского университета. ISBN 978-1-107-16841-1 . OCLC 1062334376 .

[2] Пэрис, Дж.Б.; Кирби, LAS (1978), «Σn-Схемы коллекций в арифметике» , Logic Colloquium '77 , Elsevier, стр. 199–209, doi : 10.1016/s0049-237x(08)72003-2 , ISBN 978-0-444-85178-9 , получено 14 апреля 2021 г.

[3] Сламан, Теодор А. (1 августа 2004 г.). " $\Sigma _{n}$ -ограничивающий и $\Delta _{n}$ -индукция» . Proceedings of the American Mathematical Society . 132 (8): 2449. doi : 10.1090/s0002-9939-04-07294-6 . ISSN 0002-9939 .

[:1-4] Херст, Джеффри (август 1987 г.). Комбинаторика в подсистемах арифметики второго порядка (доктор философии). Государственный университет Пенсильвании.

[1]

[2]

[3]

[4]