Интерпретация Брауэра – Гейтинга – Колмогорова - Brouwer–Heyting–Kolmogorov interpretation

В математическая логика, то Интерпретация Брауэра – Гейтинга – Колмогорова, или же Толкование BHK, из интуиционистская логика был предложен Л. Э. Дж. Брауэр и Аренд Хейтинг, и независимо Андрей Колмогоров. Его также иногда называют интерпретация реализуемости, из-за связи с осуществимость теория Стивен Клини.

Интерпретация

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

Доказательство ${ displaystyle P wedge Q}$ пара <а, б> где а является доказательством ${ displaystyle P}$ и б является доказательством ${ displaystyle Q}$ .
Доказательство ${ displaystyle P vee Q}$ пара <а, б> где а равно 0 и б является доказательством ${ displaystyle P}$ , или же а равно 1 и б является доказательством ${ displaystyle Q}$ .
Доказательство ${ displaystyle P to Q}$ это функция ${ displaystyle f}$ что превращает доказательство ${ displaystyle P}$ в доказательство ${ displaystyle Q}$ .
Доказательство ${ Displaystyle существует х в S: varphi (х)}$ пара <а, б> где а является элементом S, и б является доказательством ${ Displaystyle varphi (а)}$ .
Доказательство ${ Displaystyle forall х в S: varphi (x)}$ это функция ${ displaystyle f}$ который преобразует элемент а из S в доказательство ${ Displaystyle varphi (а)}$ .
Формула ${ displaystyle neg P}$ определяется как ${ displaystyle P to bot}$ , так что доказательством этого является функция ж что превращает доказательство ${ displaystyle P}$ в доказательство ${ displaystyle bot}$ .
Нет доказательств ${ displaystyle bot}$ (абсурд, или нижний тип (неопределенность в некоторых языках программирования)).

Интерпретация примитивного предложения должна быть известна из контекста. В контексте арифметики доказательство формулы s=т - это вычисление, сводящее два члена к одной и той же цифре.

Колмогоров придерживался той же линии, но формулировал свою интерпретацию в терминах проблем и решений. Утверждать формулу - значит утверждать, что вы знаете решение проблемы, представленной этой формулой. Например ${ displaystyle P to Q}$ проблема сокращения Q к п; для ее решения требуется метод решения проблемы Q дано решение проблемып.

Примеры

Функция тождества является доказательством формулы ${ displaystyle P to P}$ , независимо от того, что такое P.

В закон непротиворечия ${ Displaystyle neg (P клин neg P)}$ расширяется до ${ Displaystyle (P клин (P to bot)) to bot}$ :

Доказательство ${ Displaystyle (P клин (P to bot)) to bot}$ это функция ${ displaystyle f}$ что превращает доказательство ${ Displaystyle (P клин (P to bot))}$ в доказательство ${ displaystyle bot}$ .
Доказательство ${ Displaystyle (P клин (P to bot))}$ пара доказательств <а,б>, где ${ displaystyle a}$ является доказательством п, и ${ displaystyle b}$ является доказательством ${ displaystyle P to bot}$ .
Доказательство ${ displaystyle P to bot}$ - функция, преобразующая доказательство п в доказательство ${ displaystyle bot}$ .

Собирая все вместе, доказательство ${ Displaystyle (P клин (P to bot)) to bot}$ это функция ${ displaystyle f}$ который преобразует пару <а,б> - где ${ displaystyle a}$ является доказательством п, и ${ displaystyle b}$ - функция, преобразующая доказательство п в доказательство ${ displaystyle bot}$ - в доказательство ${ displaystyle bot}$ .Есть функция ${ displaystyle f}$ что делает это, где ${ Displaystyle е ( langle a, b rangle) = b (a)}$ , доказывая закон непротиворечивости, независимо от того, что такое P.

В самом деле, тот же образ мыслей дает доказательство того, что ${ Displaystyle (P клин (P к Q)) к Q}$ а также где ${ displaystyle Q}$ это любое предложение.

С другой стороны, закон исключенного среднего ${ Displaystyle P vee ( neg P)}$ расширяется до ${ displaystyle P vee (P to bot)}$ , и вообще не имеет доказательств. Согласно интерпретации, доказательство ${ Displaystyle P vee ( neg P)}$ пара <а, б> где а равно 0 и б является доказательством п, или же а равно 1 и б является доказательством ${ displaystyle P to bot}$ . Таким образом, если ни п ни ${ displaystyle P to bot}$ доказуемо, то и ${ Displaystyle P vee ( neg P)}$ .

Что такое абсурд?

Как правило, это невозможно логическая система иметь формальный оператор отрицания, такой, что есть доказательство "не" ${ displaystyle P}$ именно тогда, когда нет доказательства ${ displaystyle P}$ ; видеть Теоремы Гёделя о неполноте. Интерпретация BHK вместо этого принимает "не" ${ displaystyle P}$ иметь в виду, что ${ displaystyle P}$ приводит к абсурду, обозначенному ${ displaystyle bot}$ , так что доказательство ¬ ${ displaystyle P}$ - функция, преобразующая доказательство ${ displaystyle P}$ в доказательство абсурда.

Стандартный пример абсурда - это арифметика. Предположим, что 0 = 1, и действуем по математическая индукция: 0 = 0 по аксиоме равенства. Теперь (предположение индукции), если бы 0 был равен некоторому натуральному числу п, то 1 будет равно п+1, (Аксиома Пеано: Sм = Sп если и только если м = п), но поскольку 0 = 1, значит, 0 также был бы равен п + 1. По индукции 0 равен всем числам, поэтому любые два натуральных числа становятся равными.

Следовательно, есть способ перейти от доказательства 0 = 1 к доказательству любого основного арифметического равенства и, следовательно, к доказательству любого сложного арифметического предложения. Более того, чтобы получить этот результат, не нужно было использовать аксиому Пеано, которая утверждает, что 0 «не» является преемником любого натурального числа. Это делает 0 = 1 подходящим в качестве ${ displaystyle bot}$ в арифметике Гейтинга (и аксиома Пеано переписывается 0 =Sп → 0 = S0). Это использование 0 = 1 подтверждает принцип взрыва.

Что такое функция?

Интерпретация BHK будет зависеть от мнения о том, что составляет функция который преобразует одно доказательство в другое или преобразует элемент области в доказательство. Различные версии конструктивизм будут расходиться по этому поводу.

Клини осуществимость теория отождествляет функции с вычислимые функции. Это касается Арифметика Гейтинга, где область количественного определения - натуральные числа, а примитивные предложения имеют вид x = y. Доказательство x = y - это просто тривиальный алгоритм, если x вычисляет то же число, что и y (которое всегда разрешимо для натуральных чисел), в противном случае доказательства нет. Затем они вводятся в более сложные алгоритмы.

Если взять лямбда-исчисление как определение понятия функции, то интерпретация BHK описывает переписка между естественной дедукцией и функциями.

Интерпретация Брауэра – Гейтинга – Колмогорова - Brouwer–Heyting–Kolmogorov interpretation

Содержание