Тезис Чёрча (конструктивная математика) - Churchs thesis (constructive mathematics)

В конструктивная математика, Тезис Чёрча (CT) является аксиомой, утверждающей, что все полные функции вычислимый. Аксиома получила свое название от Тезис Черча – Тьюринга,^{[нужна цитата ]} в котором говорится, что каждый эффективно вычислимая функция это вычислимая функция, но конструктивистская версия намного сильнее, утверждая, что каждая функция вычислима.

Аксиома CT несовместима с классическая логика в достаточно сильных системах. Например, Арифметика Гейтинга (HA) с CT в качестве аксиомы сложения может опровергнуть некоторые примеры закон исключенного среднего. Однако арифметика Гейтинга равноправный с Арифметика Пеано (PA), а также с арифметикой Гейтинга и тезисом Черча. То есть добавление либо закона исключенного третьего, либо тезиса Черча не делает арифметику Гейтинга противоречивой, но добавление обоих делает.

Официальное заявление

В теориях первого порядка, таких как HA, которые не могут дать количественную оценку функций напрямую, CT утверждается как схема аксиом, говорящая, что любая определяемая функция является вычислимой, используя T-предикат Клини для определения вычислимости. Для каждой формулы φ (Икс,у) двух переменных, схема включает аксиому

{ Displaystyle ( forall x ; существует y ; varphi (x, y)) to ( exists e ; forall x ; существует y, u ; mathbf {T} (e, х, у, и) клин varphi (х, у))}

Эта аксиома утверждает, что если для каждого Икс Существует у удовлетворяющий φ, то на самом деле существует е это Число Гёделя общей рекурсивной функции, которая будет для каждого Икс, произвести такой у удовлетворяющий формуле, с некоторыми ты число Гёделя, кодирующее проверяемое вычисление свидетельство к тому, что у на самом деле значение этой функции в Икс.

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

Отношение к классической логике

Показанная выше схематическая форма CT при добавлении к конструктивным системам, таким как HA, подразумевает отрицание закона исключенного третьего. Например, это классический тавтология что каждая машина Тьюринга либо останавливается, либо не останавливается на заданном входе. Предполагая эту тавтологию, в достаточно сильных системах, таких как HA, можно сформировать функцию час который принимает код для машины Тьюринга и возвращает 1, если машина останавливается, и 0, если она не останавливается. Тогда из тезиса Чёрча можно было бы заключить, что эта функция вычислима, но это, как известно, неверно, потому что проблема остановки вычислимо не разрешима. Таким образом, HA и CT опровергают некоторые следствия закона исключенного третьего.

Упомянутая выше форма "единой аксиомы" СТ,

{ Displaystyle ( forall f) ( существует е) ( forall п) ( существует и) [ mathbf {T} (е, п, е (п), и)],}

определяет количество функций и говорит, что каждая функция ж вычислимо (с индексом е). Эта аксиома согласуется с некоторыми слабыми классическими системами, у которых нет силы формировать такие функции, как функция ж предыдущего абзаца. Например, слабая классическая система ${ displaystyle { mathsf {RCA}} _ {0}}$ согласуется с этой единственной аксиомой, потому что ${ displaystyle { mathsf {RCA}} _ {0}}$ имеет модель, в которой каждая функция вычислима. Однако форма с одной аксиомой становится несовместимой с законом исключенного третьего в любой системе, которая имеет достаточно аксиом для построения таких функций, как функция час в предыдущем абзаце.

Расширенная диссертация Черча

Расширенная диссертация Чёрча (ECT) расширяет требования к функциям, которые полностью определены для определенного типа домена. Его использует школа конструктивной математики, основанная Андрей Марков-младший. Формально это можно выразить схемой:

{ Displaystyle ( forall x ; psi (x) к существует y ; varphi (x, y)) к существует f ( forall x ; psi (x) to exists y , и ; mathbf {T} (f, x, y, u) wedge varphi (x, y))}

В приведенном выше описании ${ displaystyle psi}$ ограничено быть почти отрицательный. Для арифметики первого порядка (где обозначена схема ${ displaystyle ECT_ {0}}$ ), это означает ${ displaystyle psi}$ не может содержать дизъюнкция, и экзистенциальный кванторы может появляться только перед ${ displaystyle Delta _ {0} ^ {0}}$ (разрешимые) формулы.

Этот тезис можно охарактеризовать как утверждение, что предложение истинно тогда и только тогда, когда оно вычислимо. осуществимый. Фактически это фиксируется следующими мета-теоретическими эквивалентностями:^[1]

{ Displaystyle HA + ECT_ {0} vdash ( varphi leftrightarrow ( существует п ; п Vdash varphi))}

{ Displaystyle (HA + ECT_ {0} vdash varphi) leftrightarrow (HA vdash существует п ; (п Vdash varphi))}

Здесь, ${ Displaystyle п Vdash varphi}$ означает " ${ Displaystyle п { текст {реализует}} varphi}$ ". Итак, это доказуемо в ${ displaystyle HA}$ с ${ displaystyle ECT_ {0}}$ что предложение истинно, если оно реализуемо. Но также, ${ displaystyle varphi}$ доказуемо верно в ${ displaystyle HA}$ с ${ displaystyle ECT_ {0}}$ если только ${ displaystyle varphi}$ доказуемо осуществимо в ${ displaystyle HA}$ без ${ displaystyle ECT_ {0}}$ .

Вторую эквивалентность можно расширить с помощью Принцип Маркова (M) следующим образом:

{ displaystyle (HA + ECT_ {0} + M vdash varphi) leftrightarrow ( существует п ; PA vdash ({ bar {n}} Vdash varphi))}

Так, ${ displaystyle varphi}$ доказуемо верно в ${ displaystyle HA}$ с ${ displaystyle ECT_ {0}}$ и ${ displaystyle M}$ если есть номер п который доказуемо реализует ${ displaystyle varphi}$ в ${ displaystyle PA}$ . Квантор существования должен быть снаружи ${ displaystyle PA}$ в этом случае, поскольку PA неконструктивен и не имеет свойство существования.

Тезис Чёрча (конструктивная математика) - Churchs thesis (constructive mathematics)

Содержание

Официальное заявление

Отношение к классической логике

Расширенная диссертация Черча

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