Интуиционистская логика

Оглавление:

Интуиционистская логика
Интуиционистская логика

Видео: Интуиционистская логика

Видео: Интуиционистская логика
Видео: 1. Доказательство в интуиционистской и классической логиках 2024, Март
Anonim

Входная навигация

  • Содержание входа
  • Библиография
  • Академические инструменты
  • Friends PDF Preview
  • Информация об авторе и цитировании
  • Вернуться к началу

Интуиционистская логика

Впервые опубликовано ср 1 сентября 1999 г.; существенная редакция вт 4 сентября 2018 г.

Интуиционистская логика включает в себя общие принципы логического мышления, которые были извлечены логиками из интуиционистской математики, как это было разработано LEJ Brouwer, начиная с его [1907] и [1908]. Поскольку эти принципы применимы и к русской рекурсивной математике и конструктивному анализу Э. Бишопа и его последователей, интуиционистскую логику можно считать логической основой конструктивной математики. Хотя интуиционистский анализ противоречит классическому анализу, интуиционистская арифметика Хейтинга является подсистемой классической арифметики Пеано. Отсюда следует, что интуиционистская логика высказываний является собственной подсистемой классической логики высказываний, а чисто интуиционистская логика предикатов является надлежащей подсистемой чисто классической логики предикатов.

С философской точки зрения, интуиционизм отличается от логики трактовкой логики как части математики, а не как основы математики; от финитизмапозволяя конструктивно рассуждать о несчетных структурах (например, индукция монотонного стержня на дереве потенциально бесконечных последовательностей натуральных чисел); и из платонизма, рассматривая математические объекты как ментальные конструкции без независимого идеального существования. Формалистская программа Гильберта, чтобы оправдать классическую математику путем ее преобразования в формальную систему, последовательность которой должна быть установлена финитистскими (а следовательно, конструктивными) средствами, была самым мощным современным конкурентом развивающемуся интуиционизму Брауэра. В своем эссе 1912 года «Интуиционизм и формализм» Брауэр правильно предсказал, что любая попытка доказать последовательность полной индукции натуральных чисел приведет к замкнутому кругу.

Брауэр отверг формализм как таковой, но признал потенциальную полезность формулирования общих логических принципов, выражающих интуитивно правильные конструкции, такие как modus ponens. Формальные системы для интуиционистской логики высказываний и предикатов и арифметики были полностью разработаны Heyting [1930], Gentzen [1935] и Kleene [1952]. Гедель [1933] доказал равенство интуиционистских и классических теорий. Бет [1956] и Крипке [1965] предоставили семантику, в отношении которой интуиционистская логика является правильной и полной, хотя доказательства полноты для интуиционистской логики предикатов требуют некоторых классических рассуждений.

  • 1. Отказ от Tertium Non Datur
  • 2. Интуиционистская логика предикатов первого порядка

    • 2.1 Формальные системы (mathbf {H – IPC}) и (mathbf {H – IQC})
    • 2.2 Альтернативные формализмы и теорема дедукции
  • 3. Интуиционистская теория чисел (арифметика Хейтинга) (mathbf {HA})
  • 4. Основная теория доказательства

    • 4.1 Перевод классической логики в интуиционистскую
    • 4.2 Допустимые правила интуиционистской логики и арифметики
  • 5. Базовая семантика

    • 5.1 Семантика Крипке для интуиционистской логики
    • 5.2. Семантика реализуемости для арифметики Хейтинга
  • 6. Дополнительные темы и дальнейшее чтение

    • 6.1 Субинтуиционистская и промежуточная логика
    • 6.2 Расширенные темы
    • 6.3 Рекомендуемое чтение
  • Библиография
  • Академические инструменты
  • Другие интернет-ресурсы
  • Связанные Записи

1. Отказ от Tertium Non Datur

Интуиционистская логика может быть кратко описана как классическая логика без аристотелевского закона исключенного среднего:

(tag {LEM} A / vee / neg A)

или классический закон исключения двойного отрицания:

(tag {DNE} neg / neg A / rightarrow A)

но с законом противоречия:

[(A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A))

и ex falso sequitur quodlibet:

(neg A / rightarrow (A / rightarrow B).)

Брауэр [1908] заметил, что LEM абстрагировался от конечных ситуаций, а затем распространялся без объяснения на утверждения о бесконечных коллекциях. Например, пусть (x, y) располагается над натуральными числами (0, 1, 2, / ldots) и пусть (B (y)) сокращается ((primepred (y) oldand) primepred (y + 2))), где (primepred (y)) выражает «(y) простое число». Тогда (forall y (B (y) vee / neg B (y))) выполняется как интуитивно, так и классически, поскольку для определения, является ли натуральное число простым, нам нужно только проверить, действительно ли оно имеет делитель строго между собой и 1.

Но если (A (x)) сокращается (существует y (y / gt x / oldand B (y))), то для утверждения (forall x (A (x) vee / neg) A (x))) интуитивистски нам понадобится эффективный (см. Тезис Черча-Тьюринга) метод, позволяющий определить, существует ли пара простых чисел, больших, чем произвольное натуральное число (x), и до сих пор такой метод не известен. Очевидный полуэффективный метод состоит в том, чтобы перечислить пары простых чисел, используя уточнение сита Эратосфена (генерируя натуральные числа одно за другим и вычеркивая каждое число (y), которое не удовлетворяет (B (y))), и если пара простых чисел больше (x), этот метод в конечном итоге найдет первое. Тем не менее, (forall x A (x)) выражает гипотезу о двойных простых числах, которая еще не была доказана или опровергнута,поэтому в нынешнем состоянии наших знаний мы не можем утверждать ни (forall x (A (x) vee / neg A (x))), ни (forall x A (x) vee / neg / forall x А (х)).

Можно возразить, что эти примеры зависят от того факта, что гипотеза о двойных простых числах еще не исчерпана. Ряд первоначальных «контрпримеров» Брауэра зависел от задач (таких как последняя теорема Ферма), которые с тех пор были решены. Но Брауэру общий LEM был эквивалентен априорному предположению, что у каждой математической проблемы есть решение - предположение, которое он отклонил, опередив теорему Гёделя о неполноте на четверть века.

Отказ от LEM имеет далеко идущие последствия. С одной стороны,

  • Интуиционистски сокращение до абсурда доказывает только отрицательные утверждения, поскольку (neg / neg A / rightarrow A) в общем случае не выполняется. (Если бы это произошло, LEM следовал бы по modus ponens из интуитивно доказуемого (neg / neg (A / vee / neg A)).)
  • Интуиционистская логика высказываний не имеет конечной интерпретации таблицы истинности. Существует бесконечно много различных аксиоматических систем между интуиционистской и классической логикой.
  • Не каждая пропозициональная формула имеет интуитивистски эквивалентную дизъюнктивную или конъюнктивную нормальную форму, построенную из простых формул и их отрицаний с использованием только (vee) и (oldand).
  • Не каждая формула предиката имеет интуитивно-эквивалентную преднормальную нормальную форму со всеми квантификаторами впереди.
  • В то время как (forall x / neg / neg (A (x) vee / neg A (x))) является теоремой интуиционистской логики предикатов, (neg / neg / forall x (A (x) vee) neg A (x))) нет; поэтому (neg / forall x (A (x) vee / neg A (x))) согласуется с интуиционистской логикой предикатов.

С другой стороны,

  • Каждое интуиционистское доказательство замкнутого утверждения вида (A / vee B) может быть эффективно преобразовано в интуитивистское доказательство (A) или интуиционистское доказательство (B) и аналогично для замкнутых экзистенциальных утверждений.
  • Интуиционистская логика высказываний эффективно разрешима в том смысле, что конечный конструктивный процесс равномерно применяется к любой формуле высказываний, либо производя интуитивистское доказательство формулы, либо демонстрируя, что такого доказательства не может быть.
  • Отрицательный фрагмент интуиционистской логики (без (vee) или (Существует)) содержит точный перевод классической логики, а также для интуиционистской и классической арифметики.
  • Интуиционистская арифметика может последовательно расширяться аксиомами, которые противоречат классической арифметике, позволяя формально изучать рекурсивную математику.
  • Спорный интуиционистский анализ Брауэра, который конфликтует с LEM, может быть формализован и показан последовательным по отношению к классически и интуитивистски правильной субтеории.

2. Интуиционистская логика предикатов первого порядка

Формализованная интуиционистская логика естественным образом мотивируется неформальным объяснением Брауэром-Хейтингом-Колмогоровым интуиционистской истины, изложенным в статьях об интуиционизме в философии математики и развитии интуиционистской логики. Конструктивная независимость логических операций (oldand, / vee, / rightarrow, / neg, / forall, / exist) контрастирует с классической ситуацией, где, например, (A / vee B) эквивалентно (neg (neg A / oldand / neg B)), и (существует xA (x)) эквивалентно (neg / forall x / neg A (x)). С точки зрения BHK, предложение вида (A / vee B) утверждает, что либо доказательство (A), либо доказательство (B) было построено;в то время как (neg (neg A / oldand / neg B)) утверждает, что был построен алгоритм, который эффективно преобразовал бы любую пару конструкций, доказывающих (neg A) и (neg B) соответственно, в доказательство известного противоречия.

2.1 Формальные системы (mathbf {H – IPC}) и (mathbf {H – IQC})

Ниже приводится формализм в гильбертовом стиле (mathbf {H – IQC}) из Kleene [1952] (ср. Troelstra и van Dalen [1988]) для интуиционистской логики предикатов первого порядка. Язык (L) из (mathbf {H – IQC}) имеет предикаты (P, Q (.), / Ldots) всех арностей и отдельных переменных (x, y, z, / ldots) (с или без индексов (1, 2, / ldots)), а также символы (oldand, / vee, / rightarrow, / neg, / forall, / exist) для логических связок и квантификаторы и скобки (,). Атомарные (или простые) формулы (L) являются такими выражениями, как (P, Q (x), R (x, y, x)), где (P, Q ({.}), R ({.} {.} {.})) являются (0) - арными, (1) - арой и (3) - арой предикатами соответственно; то есть результат заполнения каждого пробела в букве предиката отдельным символом переменной является простой формулой.(Хорошо сформированные) формулы (L) определяются индуктивно следующим образом.

  • Каждая атомная формула является формулой.
  • Если (A) и (B) являются формулами, то ((A / oldand B), (A / vee B), (A / rightarrow B)) и (neg A).
  • Если (A) - формула, а (x) - переменная, то (forall xA) и (существующие xA) - формулы.

В общем, мы используем (A, B, C) в качестве мета-переменных для правильно сформированных формул и (x, y, z) в качестве мета-переменных для отдельных переменных. Предвидя приложения (например, интуитивистскую арифметику), мы используем (s, t) в качестве мета-переменных для терминов; в случае чистой логики предикатов термины - это просто отдельные переменные. Вхождение переменной (x) в формулу (A) связывается, если она находится в области действия квантификатора (forall x) или (существует x), в противном случае она свободна. Интуиционистски, как и классически, ((A / leftrightarrow B)) сокращается (((A / rightarrow B) oldand (B / rightarrow A))), и скобки будут опущены, когда это не вызывает путаницы.

Существует три правила вывода:

Модус Поненс

Из (A) и (A / rightarrow B) заключите (B).

(forall) - Введение

Из (C / rightarrow A (x)), где (x) - переменная, которая не встречается свободно в (C), заключите (C / rightarrow / forall х А (х)).

(Существует) - Исключение

из (A (x) rightarrow C), где (x) - переменная, которая не встречается свободно в (C), заключить (существует x A (x) rightarrow C).

Все аксиомы являются формулами следующих форм, где в последних двух схемах подформа формула (A (t)) является результатом подстановки вхождения термина (t) для каждого свободного вхождения (x)) в (A (x)), и никакая переменная, свободная в (t), не становится связанной в (A (t)) в результате подстановки.

(begin {array} {l} A / rightarrow (B / rightarrow A) (A / rightarrow B) rightarrow ((A / rightarrow (B / rightarrow C)) rightarrow (A / rightarrow C)) / A / rightarrow (B / rightarrow (A / oldand B)) (A / oldand B) rightarrow A \(A / oldand B) rightarrow B \\ A / rightarrow (A / vee B) / B / rightarrow (A / vee B) (A / rightarrow C) rightarrow ((B / rightarrow C) rightarrow ((A / vee B) rightarrow C)) (A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A) / \ neg A / rightarrow (A / rightarrow B) / \ forall xA (x) rightarrow A (t) / A (t) правая стрелка / существует xA (x) end {array})

Доказательством является любая конечная последовательность формул, каждая из которых является аксиомой или непосредственным следствием, по правилу вывода, (одной или двух) предшествующих формул последовательности. Говорят, что любое доказательство доказывает свою последнюю формулу, которая называется теоремой или доказуемой формулой интуиционистской логики предикатов первого порядка. Вывод формулы (E) из набора (F) предположений - это любая последовательность формул, каждая из которых принадлежит (F) или является аксиомой или непосредственным следствием по правилу вывода, из предыдущих формул последовательности, так что (E) является последней формулой последовательности. Если такой вывод существует, мы говорим, что (E) выводимо из (F).

Интуиционистская логика высказываний (mathbf {H – IPC}) является подсистемой (mathbf {H – IQC}), которая возникает, когда язык ограничен формулами, построенными из букв высказываний (P, Q, R, / ldots) с использованием пропозициональных связок (oldand, / vee, / rightarrow) и (neg), и используются только пропозициональные постулаты. Таким образом, последние два правила вывода и последние две схемы аксиом отсутствуют в пропозициональной подсистеме.

Если в приведенном списке схем аксиом для интуиционистской логики высказываний или предикатов первого порядка существует закон, выражающий ex falso sequitur quodlibet:

(neg A / rightarrow (A / rightarrow B))

заменяется классическим законом исключения двойного отрицания DNE:

(neg / neg A / rightarrow A)

(или, что эквивалентно, если интуиционистский закон отрицания введен:

[(A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A))

заменяется LEM), формальной системой (mathbf {H – CPC}) для классической логики высказываний или (mathbf {H – CQC}) для результатов классической логики предикатов. Поскольку ex falso и закон противоречия являются классическими теоремами, интуиционистская логика содержится в классической логике. В некотором смысле классическая логика также содержится в интуиционистской логике; см. раздел 4.1 ниже.

Важно отметить, что хотя LEM и DNE эквивалентны как схемы над (mathbf {H – IPC}), это означает, что

[(neg / neg A / rightarrow A) rightarrow (A / vee / neg A))

не является схемой теоремы (mathbf {H – IPC}). Для теорий (mathbf {T}), основанных на интуиционистской логике, если (E) - произвольная формула (L (mathbf {T})), то по определению:

(E) разрешима в (mathbf {T}) тогда и только тогда, когда (mathbf {T}) доказывает (E / vee / neg E).

(E) устойчиво в (mathbf {T}) тогда и только тогда, когда (mathbf {T}) доказывает (neg / neg E / rightarrow E).

(E) тестируется в (mathbf {T}) тогда и только тогда, когда (mathbf {T}) доказывает (neg E / vee / neg / neg E).

Разрешимость подразумевает стабильность, но не наоборот. Сочетание стабильности и тестируемости эквивалентно разрешимости. Сам Брауэр доказал, что «абсурд абсурда абсурда эквивалентен абсурду» (Брауэр [1923C]), поэтому любая формула вида (neg A) является устойчивой; но в (mathbf {H – IPC}) и (mathbf {H – IQC}) простые формулы и их отрицания неразрешимы, как показано в разделе 5.1 ниже.

2.2 Альтернативные формализмы и теорема дедукции

Система в стиле Гильберта (mathbf {H – IQC}) полезна для метаматематических исследований интуиционистской логики, но ее принудительная линеаризация выводов и ее предпочтение аксиомам над правилами делают ее неуклюжим инструментом для установления выводимости. Естественная система дедукции (mathbf {N – IQC}) для интуиционистской логики предикатов получается из дедуктивной системы (mathbf {D}), представленной в разделе 3 статьи о классической логике в этой энциклопедии, опуская символ и правила идентичности и замена классического правила (DNE) устранения двойного отрицания на интуиционистское правило исключения отрицания, выражающее ex falso:

(INE) Если (F) влечет за собой (A), а (F) влечет за собой (neg A), то (F) влечет за собой (B)

Ключи к доказательству того, что (mathbf {H – IQC}) эквивалентна (mathbf {N – IQC}), являются modus ponens, и наоборот:

Теорема дедукции

Если (B) выводится из (A) и, возможно, из других формул (F), все переменные, свободные в (A), остаются постоянными при выводе (т. Е. Без использования второго или третье правило вывода для любой переменной (x), встречающейся в (A) свободно, если только предположение (A) не встречается при выводе до рассматриваемого вывода), то (A / rightarrow B) выводится из (F).

Этот фундаментальный результат, грубо выражающий правило ((rightarrow I)) для (mathbf {I}), можно доказать для (mathbf {H – IQC}) по индукции по определению вывод. Другие правила (mathbf {I}) выполняются для (mathbf {H – IQC}) по существу с помощью modus ponens, что соответствует ((rightarrow E)) в (mathbf {N -IQC}); и все аксиомы (mathbf {H – IQC}) доказуемы в (mathbf {N – IQC}).

Чтобы проиллюстрировать полезность теоремы дедукции, рассмотрим (очевидно тривиальную) схему теоремы ((A / rightarrow A)). Правильное доказательство в (mathbf {H – IPC}) занимает пять строк:

  • 1. (A / rightarrow (A / rightarrow A))
  • 2. ((A / rightarrow (A / rightarrow A)) rightarrow ((A / rightarrow ((A / rightarrow A) rightarrow A)) rightarrow (A / rightarrow A)))
  • 3. ((A / rightarrow ((A / rightarrow A) rightarrow A)) rightarrow (A / rightarrow A))
  • 4. (A / rightarrow ((A / rightarrow A) rightarrow A))
  • 5. (A / rightarrow A)

где 1, 2 и 4 - аксиомы, а 3, 5 взяты из более ранних строк по modus ponens. Однако (A) выводится из (A) (как предположение) за один очевидный шаг, поэтому теорема дедукции позволяет заключить, что доказательство (A / rightarrow A) существует. (Фактически, формальное доказательство (A / rightarrow A), только что представленное, является частью конструктивного доказательства теоремы дедукции!)

Важно отметить, что в определении вывода из допущений в (mathbf {H – IQC}) формулы предположения рассматриваются так, как если бы все их свободные переменные были универсально определены количественно, так что (forall x A (x)) выводится из гипотезы (A (x)). Тем не менее, переменная (x) будет изменяться (не удерживаться постоянной) в этом производном, используя правило (forall) - вводный; и, следовательно, теорема дедукции не может быть использована для того, чтобы заключить (ложно), что (A (x) rightarrow / forall x A (x)) (и, следовательно, посредством (Существует) - исключение (существует x A (x) rightarrow / forall x A (x))) доказуемо в (mathbf {H – IQC}). В качестве примера правильного использования теоремы дедукции для логики предикатов рассмотрим импликацию (существует x A (x) rightarrow / neg / forall x / neg A (x)). Чтобы показать, что это доказуемо в (mathbf {H – IQC}),сначала мы выводим (neg / forall x / neg A (x)) из (A (x)) со всеми свободными переменными, которые остаются постоянными:

  • 1. (forall x / neg A (x) rightarrow / neg A (x))
  • 2. (A (x) rightarrow (forall x / neg A (x) rightarrow A (x)))
  • 3. (A (x)) (предположение)
  • 4. (forall x / neg A (x) rightarrow A (x))
  • 5. ((forall x / neg A (x) rightarrow A (x)) rightarrow ((forall x / neg A (x) rightarrow / neg A (x)) rightarrow / neg / forall x / neg A (x)))
  • 6. ((forall x / neg A (x) rightarrow / neg A (x)) rightarrow / neg / forall x / neg A (x))
  • 7. (neg / forall x / neg A (x))

Здесь 1, 2 и 5 - аксиомы; 4 происходит от 2 и 3 по modus ponens; и 6 и 7 взяты из более ранних строк modus ponens; так что переменные не менялись. Теорема дедукции говорит нам, что в (mathbf {H – IQC}) есть доказательство (P) для (A (x) rightarrow / neg / forall) x (neg A (x)), и одно применение (Существует) - исключение превращает (P) в доказательство (существует x A (x) rightarrow / neg / forall x / neg A (x)). Обратное не доказуемо в (mathbf {H – IQC}), как показано в разделе 5.1 ниже.

Другими важными альтернативами (mathbf {H – IQC}) и (mathbf {N – IQC}) являются различные последовательные исчисления для интуиционистской логики высказываний и предикатов. Первое такое исчисление было определено Генценом [1934–5], ср. Клини [1952]. Системы секвенций, которые доказывают те же формулы, что и (mathbf {H – IQC}) и (mathbf {N – IQC}), отслеживают все предположения и выводы на каждом этапе доказательства, заменяя их modus ponens (который исключает промежуточную формулу) с помощью правила сокращения (которое может быть показано как допустимое правило (см. раздел 4.2) для подсистемы, остающейся, когда она опущена).

Когда детали формализма не важны, отныне мы следуем Троельстре и ван Далену [1988], позволяя «(mathbf {IQC})» или «(mathbf {IPC})» обращаться к любому формальная система для интуиционистского предиката или логики высказываний соответственно, и аналогично «(mathbf {CQC})» и «(mathbf {CPC})» для классического предиката и логики высказываний.

И (mathbf {IPC}), и (mathbf {IQC}) удовлетворяют интерполяционным теоремам, например: если (A) и (B) являются пропозициональными формулами, имеющими хотя бы одну общую букву предложения, и если (A / rightarrow B) доказуемо в (mathbf {IPC}), то существует формула (C), содержащая только буквы предложения, встречающиеся как в (A), так и в (B), такие что (A / rightarrow C) и (C / rightarrow B) доказуемы. Эти темы рассматриваются в Kleene [1952] и Troelstra and Schwichtenberg [2000].

Хотя идентичность, конечно, может быть добавлена к интуиционистской логике, для приложений (например, к арифметике) символ равенства обычно рассматривается как выделенная константа предиката, удовлетворяющая аксиомам для отношения эквивалентности (рефлексивности, симметрии и транзитивности) и дополнительных нелогических аксиом (например,, примитивные рекурсивные определения сложения и умножения). Идентичность разрешима как на интуитивистском, так и на классическом уровне, но интуиционистское экстенсиональное равенство не всегда разрешимо; см. обсуждение аксиом непрерывности Брауэра в разделе 3 статьи об интуиционизме в философии математики.

3. Интуиционистская теория чисел (арифметика Хейтинга) (mathbf {HA})

Интуиционистская (хейтинговая) арифметика (mathbf {HA}) и классическая (Пеано) арифметика (mathbf {PA}) используют один и тот же язык первого порядка и одни и те же нелогические аксиомы; только логика отличается. В дополнение к логическим связям, квантификаторам и круглым скобкам и отдельным переменным (x, y, z, / ldots) (также используемым в качестве мета-переменных), язык (L (mathbf {HA})) арифметики имеет двоичный символ предиката (=), индивидуальная константа (0), константа унарной функции (S) и конечное или счетное бесконечно много дополнительных констант для примитивных рекурсивных функций, включая сложение и умножение; Точный выбор зависит от вкуса и удобства. Термины построены из переменных и (0) с использованием констант функции; в частности,каждое натуральное число (n) выражается в языке цифрой (mathbf {n}), полученной путем применения (S) (n) раз к (0) (например, (S (S (0))) - цифра для (2)). Простые формулы имеют вид ((s = t)), где (s, t) - члены, и составные формулы получаются из них, как обычно.

Логические аксиомы и правила (mathbf {HA}) аналогичны интуиционистской логике предикатов первого порядка (mathbf {IQC}). Нелогичные аксиомы включают рефлексивные, симметричные и транзитивные свойства (=): (forall x (x = x),) (forall x / forall y (x = y / rightarrow y = x),) (forall x / forall y / forall z ((x = y / oldand y = z) rightarrow x = z);) аксиома, характеризующая (0) как наименее натуральное число:

(forall x / neg (S (x) = 0),)

аксиома, характеризующая (S) как взаимно-однозначную функцию:

(forall x / forall y (S (x) = S (y) rightarrow x = y),)

аксиома экстенсионального равенства для (S):

(forall x / forall y (x = y / rightarrow S (x) = S (y));)

примитивно-рекурсивные определяющие уравнения для каждой постоянной функции, в частности для сложения: (forall x (x + 0 = x),) (forall x / forall y (x + S (y) = S (x +) y));) и умножение: (forall x (x / cdot 0 = 0),) (forall x / forall y (x / cdot S (y) = (x / cdot y) + x);) и (универсальное замыкание) схемы математической индукции для произвольных формул (A (x)):

[(A (0) oldand / forall x (A (x) rightarrow A (S (x)))) rightarrow / forall x A (x).)

Аксиомы экстенсионального равенства для всех констант функций выводятся путем математической индукции из аксиомы равенства для (S) и аксиом примитивно-рекурсивной функции.

Отношение естественного порядка (x / lt y) может быть определено в (mathbf {HA}) как (существует z (S (z) + x = y)) или не содержит кванторов формула (S (x) dot {-} y = 0), если символ и примитивные рекурсивные определяющие уравнения для предшественника: [Pd (0) = 0,) (forall x (Pd (S (x (x (x)))) = x)) и вычитание отсечки: (forall x (x / dot {-} 0 = 0),) (forall x (x / dot {-} S (y) = Pd (x / dot {-} y))) присутствуют в формализме. (mathbf {HA}) доказывает сравнительный закон

(forall x / forall y (x / lt y / vee x = y / vee y / lt x))

и интуиционистская форма принципа наименьшего числа для произвольных формул (A (x)):

(forall x (forall y (y / lt x / rightarrow (A (y) vee / neg A (y))) rightarrow \(существует y ((y / lt x / oldand A (y))) oldand / forall z (z / lt y / rightarrow / neg A (z))) vee \\ / forall y (y / lt x / rightarrow / neg A (y)))].)

Эта гипотеза необходима, потому что не все арифметические формулы разрешимы в (mathbf {HA}). Однако (forall x / forall y (x = y / vee / neg (x = y))) может быть доказан непосредственно математической индукцией, и поэтому

Простые формулы (и, следовательно, все формулы без кванторов) разрешимы и устойчивы в (mathbf {HA}).

Если (A (x)) разрешимо в (mathbf {HA}), то по индукции на (x) так же (forall y (y / lt x / rightarrow A (y))) и (существует y (y / lt x / oldand A (y))). следовательно

Формулы, в которых все кванторы являются ограниченными, разрешимы и устойчивы в (mathbf {HA}).

Набор (Delta_0) арифметических формул, в которых все квантификаторы ограничены, является самым низким уровнем классической арифметической иерархии, основанной на шаблоне чередований кванторов в формуле пренекса. В (mathbf {HA}) не каждая формула имеет предпринципную форму, но Барр [2004] обнаружил простую интуиционистскую арифметическую иерархию, соответствующую уровню за уровнем классической. Только в следующих двух определениях (forall x) обозначает блок конечного числа квантификаторов универсальных чисел, и аналогично (Существует x) обозначает блок конечного числа квантификаторов экзистенциальных чисел. С этими соглашениями классы Берра (Phi_n) и (Psi_n) определяются как:

  • (Phi_0 = / Psi_0 = / Delta_0),
  • (Phi_1) - это класс всех формул вида (forall x A (x)), где (A (x)) находится в (Psi_0). Для (n / ge 2) (Phi_n) - это класс всех формул вида (forall x [A (x) rightarrow / существует y B (x, y)]), где (A (x)) находится в (Phi_ {n-1}) и (B (x, y)) находится в (Phi_ {n-2}),
  • (Psi_1) - это класс всех формул вида (существует x A (x)), где (A (x)) находится в (Phi_0). Для (n / ge 2) (Psi_n) - это класс всех формул вида (A / rightarrow B), где (A) находится в (Phi_n) и (B) находится в (Phi_ {n-1}).

Соответствующие классические классы prenex определены более просто:

  • (Pi_0 = / Sigma_0 = / Delta_0),
  • (Pi_ {n +1}) - это класс всех формул вида (forall x A (x)), где (A (x)) находится в (Sigma_n),
  • (Sigma_ {n +1}) - это класс всех формул вида (существует x A (x)), где (A (x)) находится в (Pi_n).

Арифметика Пеано (mathbf {PA}) получается из арифметики Хейтинга (mathbf {HA}) путем добавления LEM или (neg / neg A / rightarrow A) в список логических аксиом, т.е. используя классическую вместо интуиционистской логики. Следующие результаты справедливы даже для фрагментов (mathbf {HA}) и (mathbf {PA}) со схемой индукции, ограниченной формулами (Delta_0).

Теорема Бурра:

  • Каждая арифметическая формула доказуемо эквивалентна в (mathbf {HA}) формуле в одном из классов (Phi_n).
  • Каждая формула в (Phi_n) доказуемо эквивалентна в (mathbf {PA}) формуле в (Pi_n), и наоборот.
  • Каждая формула в (Psi_n) доказуемо эквивалентна в (mathbf {PA}) формуле в (Sigma_n), и наоборот.

(mathbf {HA}) и (mathbf {PA}) доказательственно-теоретически эквивалентны, как будет показано в разделе 4. Каждый из них способен (численно) выражать свой собственный предикат доказательства. По известной теореме Гёделя о неполноте, если (mathbf {HA}) непротиворечиво, то ни (mathbf {HA}), ни (mathbf {PA}) не могут доказать свою собственную непротиворечивость.

4. Основная теория доказательства

4.1 Перевод классической логики в интуиционистскую

Фундаментальный факт об интуиционистской логике состоит в том, что она обладает той же силой согласованности, что и классическая логика. Для логики высказываний это было впервые доказано Гливенко [1929].

Теорема Гливенко. Любая

пропозициональная формула (A) классически доказуема тогда и только тогда, когда (neg / neg A) интуитивистски доказуема.

Теорема Гливенко не распространяется на логику предикатов, хотя произвольная формула предиката (A) классически доказуема тогда и только тогда, когда (neg / neg A) доказуема в интуиционистской логике предикатов плюс схема «сдвиг двойного отрицания».

(tag {DNS} forall x / neg / neg B (x) rightarrow / neg / neg / forall x B (x))

Более сложный отрицательный перевод классических в интуиционистские теории, независимо от Гёделя и Генцена, ассоциирует с каждой формулой (A) языка (L) другую формулу (g (A)) (без (vee) или (Существует)), так что

  • (I) Классическая логика предикатов доказывает (A / leftrightarrow g (A)).
  • (II) Интуиционистская логика предикатов доказывает (g (A) leftrightarrow / neg / neg g (A)).
  • (III) Если классическая логика предикатов доказывает (A), то интуиционистская логика предикатов доказывает (g (A)).

Доказательства очевидны из следующего индуктивного определения (g (A)) (используя прямой перевод импликации Гентцена, а не Геделя в терминах (neg) и (oldand)):

(begin {align *} g (P) & / text {is} neg / neg P, / text {if} P / text {простое число}. \\ g (A / oldand B) & / text { is} g (A) oldand g (B). \\ g (A / vee B) & / text {is} neg (neg g (A) oldand / neg g (B)). \\ g (A / rightarrow B) & / text {is} g (A) rightarrow g (B). \\ g (neg A) & / text {is} neg g (A). \\ g (forall xA (x)) & / text {is} forall xg (A (x)). \\ g (существует xA (x)) & / text {is} neg / forall x / neg g (A (x)). / Конец {выравнивание *})

Для каждой формулы (A) (g (A)) доказуемо интуитивистски тогда и только тогда, когда (A) доказуемо классически. В частности, если (B / oldand / neg B) были классически доказуемы для некоторой формулы (B), то (g (B) oldand / neg g (B)) (то есть (g (B / oldand / neg B))), в свою очередь, доказуемо интуитивно. следовательно

(IV) Классическая и интуиционистская логика предикатов равносильны

Отрицательный перевод классической в интуиционистскую теорию чисел еще проще, поскольку простые формулы интуиционистской арифметики устойчивы. Таким образом, (g (s = t)) можно принять за (s = t), а остальные предложения не изменились. Отрицательный перевод любого случая математической индукции является еще одним примером математической индукции, а другие нелогические аксиомы арифметики являются их собственными отрицательными переводами, поэтому

(I), (II), (III) и (IV) справедливы и для теории чисел

Гедель [1933e] интерпретировал эти результаты как показы- вающие, что интуиционистская логика и арифметика богаче классической логики и арифметики, потому что интуиционистская теория различает формулы, которые классически эквивалентны, и имеет такую же прочность согласованности, что и классическая теория. В частности, теоремы Гёделя о неполноте применимы как к (mathbf {HA}), так и к (mathbf {PA}).

Прямые попытки распространить отрицательную интерпретацию на анализ проваливаются, потому что отрицательный перевод исчисляемой аксиомы выбора не является теоремой интуиционистского анализа. Однако это согласуется с интуиционистским анализом, включая спорный принцип непрерывности Брауэра, функциональной версией рекурсивной реализуемости Клини (см. Раздел 6.2 ниже). Отсюда следует, что интуиционистская математика, которая может быть выражена только с использованием всех стандартных логических связок и квантификаторов, согласуется с точным переводом классической математики, избегая (vee) и (Существует).

Это важно, потому что интуиционистский анализ Брауэра не согласуется с LEM. Однако, если (A) - любая отрицательная формула (без (vee) или (Существует)), то (neg / neg A / rightarrow A) доказуемо с помощью интуиционистской логики. Примирение интуиционистского и классического анализа по этим направлениям, вдохновленное идеей последовательности выбора Крипке, предложено в Moschovakis [2017].

4.2 Допустимые правила интуиционистской логики и арифметики

Гедель [1932] заметил, что интуиционистская логика высказываний обладает свойством дизъюнкции:

(DP) Если (A / vee B) - теорема, то (A) - теорема или (B) - теорема

Генцен [1935] установил свойство дизъюнкции для замкнутых формул интуиционистской логики предикатов. Из этого следует, что если интуиционистская логика непротиворечива, то (P / vee / neg P) не является теоремой, если (P) является атомарной формулой. Клини [1945, 1952] доказал, что интуиционистская теория чисел первого порядка также имеет свойство существования (см. Фридман [1975]):

(EP) Если (существует x A (x)) - замкнутая теорема, то для некоторого замкнутого члена (t), (A (t)) - теорема

Свойства дизъюнкции и существования являются частными случаями общего явления, свойственного неклассическим теориям. Допустимые правила теории - это правила, по которым теория замкнута. Например, Харроп [1960] заметил, что правило

Если (neg A / rightarrow (B / vee C)) является теоремой, то ((neg A / rightarrow B) vee (neg A / rightarrow C))

допустимо для интуиционистской логики высказываний (mathbf {IPC}), потому что если (A), (B) и (C) - это любые формулы, такие что (neg A / rightarrow (B / vee) C)) доказуемо в (mathbf {IPC}), тогда также ((neg A / rightarrow B) vee (neg A / rightarrow C)) доказуемо в (mathbf {IPC }). Правило Харропа не выводимо в (mathbf {IPC}), потому что ((neg A / rightarrow (B / vee C)) rightarrow (neg A / rightarrow B) vee (neg A / rightarrow C)) интуитивно не доказуемо. Другим важным примером допустимого недопустимого правила (mathbf {IPC}) является правило Минца:

Если ((A / rightarrow B) rightarrow (A / vee C)) является теоремой, то (((A / rightarrow B) rightarrow A) vee ((A / rightarrow B) rightarrow C)).

Двузначная интерпретация таблицы истинности классической логики высказываний (mathbf {CPC}) дает простое доказательство того, что каждое допустимое правило (mathbf {CPC}) выводимо: в противном случае некоторое присвоение (A), (B) и т. Д. Сделают гипотезу верной, а заключение неверным, и, например, заменив, например, (P / rightarrow P) на буквы, которым присвоены "истина" и (P / oldand / neg P) для назначенных «ложных» можно было бы доказать доказуемую гипотезу и недоказуемое заключение. Тот факт, что интуиционистская ситуация более интересна, приводит ко многим естественным вопросам, на некоторые из которых недавно был дан ответ.

Обобщая правило Минца, Виссер и де Йонг определили рекурсивно перечисляемую последовательность последовательно более строгих допустимых правил («правила Виссера»), которые, как они предполагали, легли в основу допустимых правил (mathbf {IPC}) в смысле что каждое допустимое правило выводится из свойства дизъюнкции и одного из правил последовательности. Опираясь на работу Гиларди [1999], Иемхоффу [2001] удалось доказать их гипотезу. Рыбаков [1997] доказал, что совокупность всех допустимых правил (mathbf {IPC}) разрешима, но не имеет конечного базиса. Виссер [2002] показал, что его правила также являются допустимыми пропозициональными правилами (mathbf {HA}) и (mathbf {HA}), расширенными принципом Маркова MP (определенным в разделе 5.2 ниже). В последнее время,Джерабек [2008] нашел независимый базис для допустимых правил (mathbf {IPC}), обладающий тем свойством, что ни одно правило в базе не выводит другого.

Гораздо меньше известно о допустимых правилах интуиционистской логики предикатов. Pure (mathbf {IQC}), без индивидуальных или предикатных констант, имеет следующее замечательное допустимое правило для (A (x)) без свободных переменных, но (x):

Если (существует x A (x)) - теорема, то и (forall x A (x)).

Не все допустимые правила предикатов (mathbf {IQC}) допустимы для всех формальных систем, основанных на (mathbf {IQC}); например, (mathbf {HA}) явно нарушает только что указанное правило. Виссер доказал в [1999], что свойство быть допустимым правилом предикатов (mathbf {HA}) является (Pi_2) полным, а в [2002], что (mathbf {HA}) (+) MP имеет те же допустимые правила предиката, что и (mathbf {HA}). Плиско [1992] доказал, что логика предикатов (mathbf {HA}) (+) MP (множество предложений на языке (mathbf {IQC})) всех экземпляров равномерной подстановки в язык арифметики доказуем в (mathbf {HA}) (+) MP) полон (Pi_2); Visser [2006] расширил этот результат до некоторых конструктивно интересных последовательных расширений (mathbf {HA}), которые не содержатся в (mathbf {PA}).

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

Если (forall x (A (x) vee / neg A (x)) oldand / neg / forall x / neg A (x)) является теоремой, то (существует x A (x)).

и следующее правило независимости помещения (где предполагается, что (y) не должно быть свободным в (A (x))):

Если (forall x (A (x) vee / neg A (x)) oldand (forall x A (x) rightarrow / существующие y B (y))) является теоремой, то и (существует y (forall x A (x) rightarrow B (y))).

Оба правила также допустимы для (mathbf {HA}). Соответствующие значения (MP и IP соответственно), которые не доказуемы интуитивистски, подтверждаются интерпретацией Геделя «Диалектика» (mathbf {HA}) (см. Раздел 6.3 ниже). Так же как и импликация (CT), соответствующая одному из наиболее интересных допустимых правил арифметики Хейтинга, назовем его правилом Чёрча-Клини:

Если (forall x / существует y A (x, y)) является замкнутой теоремой (mathbf {HA}), то существует число (n) такое, что доказуемо в (mathbf {HA}), частичная рекурсивная функция с числом Геделя (n) является полной и отображает каждое (x) в (y), удовлетворяющее (A (x, y)) (и, более того, (A (mathbf {x}, / mathbf {y})) доказуемо, где (mathbf {x}) - это число для натурального числа (x) и (mathbf {y}) это цифра для (y)).

Объединение правила Маркова с отрицательным переводом приводит к тому, что классическая и интуиционистская арифметика доказывают одинаковые формулы вида (forall x / существует y A (x, y)), где (A (x, y)) бескванторная. В общем, если (A (x, y)) доказуемо разрешимо в (mathbf {HA}) и если (forall x / существует, y A (x, y)) является замкнутой теоремой В классической арифметике (mathbf {PA}) заключение правила Чёрча-Клини имеет место даже в интуиционистской арифметике. Ибо если (mathbf {HA}) окажется (forall x / forall y (A (x, y) vee / neg A (x, y))), то по правилу Чёрча-Клини характерная функция из (A (x, y)) имеет число Гёделя (m), доказуемо в (mathbf {HA}); поэтому (mathbf {HA}) доказывает (forall x / существует y A (x, y) leftrightarrow / forall x / существует y / существует z B (mathbf {m}, x, y, z)) где (B) не содержит кванторов,а соседние экзистенциальные кванторы можно заключить в (mathbf {HA}). Отсюда следует, что (mathbf {HA}) и (mathbf {PA}) имеют одинаково доказуемо рекурсивные функции.

Вот доказательство того, что правило «Если (forall x (A / vee B (x))) является теоремой, то же самое относится и к (A / vee / forall x B (x)) (где (x) не является свободным в (A)), не допустимо для (mathbf {HA}), если (mathbf {HA}) согласован. Нумерация Гёделя дает формулу без кванторов (G (x)), которая (численно) выражает предикат «(x) - это код доказательства в (mathbf {HA}) of ((0 = 1)). » Интуиционистская логика с разрешимостью арифметических формул без кванторов (mathbf {HA}) доказывает (forall x (существует y G (y) vee / neg G (x))). Однако если (mathbf {HA}) доказано (существует yG (y) vee / forall x / neg G (x)), то по свойству дизъюнкции (mathbf {HA}) должно докажите либо (существует yG (y)), либо (forall x / neg G (x)). Первый случай невозможен,свойством существования с предположением согласованности и тем фактом, что (mathbf {HA}) доказывает все истинные предложения без кванторов. Но второй случай также невозможен по второй теореме Гёделя о неполноте, поскольку (forall x / neg G (x)) выражает согласованность (mathbf {HA}).

5. Базовая семантика

Интуиционистские системы вдохновили множество интерпретаций, включая таблицы Бета, топологические модели Расова и Сикорского, алгебры Хейтинга, формулы как типы, рекурсивные реализуемости Клини, слэши Клина и Акселя и модели, основанные на пучках и топоях. Из всех этих интерпретаций семантика возможного мира Крипке [1965], в отношении которой интуиционистская логика предикатов является полной и последовательной, больше всего напоминает классическую теорию моделей. С другой стороны, интерпретации рекурсивной реализуемости пытаются эффективно реализовать объяснение БХК интуиционистской истины.

5.1 Семантика Крипке для интуиционистской логики

Структура Крипке (mathbf {K}) для (L) состоит из частично упорядоченного множества (K) узлов и доменной функции D, присваиваемой каждому узлу (k) в (K)) обитаемое множество (D (k)), такое, что если (k / le k '), то (D (k) subseteq D (k')). Кроме того, (mathbf {K}) имеет принудительное отношение, определяемое следующим образом.

Для каждого узла (k) пусть (L (k)) - язык, расширяющий (L) новыми константами для всех элементов (D (k)). Каждому узлу (k) и каждой (0) - любой предикатной букве (каждой букве предложения) (P) либо присвойте (f (P, k) =) true, либо оставьте (f (P, k)) не определено, в соответствии с требованием, что если (k / le k ') и (f (P, k) =) true, то (f (P, k') =) true также. Скажи это

(k) (vDash) (P) тогда и только тогда, когда (f (P, k) =) верно.

Каждому узлу (k) и каждой ((n + 1)) - любой предикатной букве (Q (ldots)) назначьте (возможно, пустой) набор (T (Q, k)) ((n + 1)) - кортежей элементов (D (k)) таким образом, что если (k / le k '), то (T (Q, k) subseteq T (Q, k ')). Скажи это

(k) (vDash) (Q (d_0, / ldots, d_n)) тогда и только тогда, когда ((d_0, / ldots, d_n) in T (Q, k)).

Теперь определите (k) (vDash) (E) (что можно прочитать как "(k) сила (E)") для составных предложений (E) of (L (k)) индуктивно следующим образом:

(k) (vDash) ((A / oldand B)) if (k) (vDash) (A) и (k) (vDash) (B).
(k) (vDash) ((A / vee B)) if (k) (vDash) (A) или (k) (vDash) (B).
(k) (vDash) ((A / rightarrow B)) если для каждого (k '\ ge k), если (k') (vDash) (A), то (k ') (vDash) (B),
(k) (vDash) (neg A) если нет (k '\ ge k) делает (k') (vDash) (A).
(k) (vDash) (forall x A (x)) если для каждого (k '\ ge k) и каждого (d / in D (k')), (k ') (vDash) (A (d)).
(k) (vDash) (существует x A (x)) если для некоторого (d / in D (k)), (k) (vDash) (A (d)).

Любое такое принудительное отношение непротиворечиво:

Ни для одного предложения (A) и для (k) это не тот случай, когда (k) (vDash) (A) и (k) (vDash) (neg A).

и монотонный:

Если (k / le k ') и (k) (vDash) (A), то (k') (vDash) (A).

Теоремы Крипке об обоснованности и полноте устанавливают, что предложение (L) доказуемо в интуиционистской логике предикатов тогда и только тогда, когда оно навязывается каждым узлом каждой структуры Крипке. Таким образом, чтобы показать, что (neg / forall x / neg P (x) rightarrow / существует x P (x)) интуитивистски недоказуемо, достаточно рассмотреть структуру Крипке с (K = {k, k '},) (k / lt k',) (D (k) = D (k ') = {0 }), (T (P, k)) пусто, но (T (P, k ') = {0 }). И чтобы показать, что обратное утверждение интуитивно доказуемо (без фактического доказательства), нужны только свойства согласованности и монотонности произвольных моделей Крипке с определением (vDash).

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

Пропозициональная семантика Крипке особенно проста, поскольку произвольная пропозициональная формула интуитивистски доказуема тогда и только тогда, когда она форсируется корнем каждой модели Крипке, чей каркас (множество (K) узлов вместе с их частичным упорядочением) конечен дерево с наименьшим элементом (корень). Например, модель Крипке с (K = {k, k ', k' '}, k / lt k') и (k / lt k '') и с (P) true только в (k '), показывает, что и (P / vee / neg P), и (neg P / vee / neg / neg P) недоказуемы в (mathbf {IPC}), Каждый конечный узел или лист модели Крипке является классической моделью, потому что лист форсирует каждую формулу или ее отрицание. Только те пропозициональные буквы, которые встречаются в формуле (E), и только те узлы (k '), которые (k / le k'), имеют отношение к принятию решения о силе (k) (E). Такие соображения позволяют нам эффективно ассоциировать с каждой формулой (E) группы (L (mathbf {IPC})) конечный класс конечных структур Крипке, который будет содержать контрмодель к (E), если таковая существует. Поскольку класс всех теорем (mathbf {IPC}) рекурсивно перечислим, мы заключаем, что

(mathbf {IPC}) эффективно разрешима. Существует рекурсивная процедура, которая определяет для каждой пропозициональной формулы (E), является ли (E) теорема (mathbf {IPC}), и заканчивается доказательством (E)) или (конечная) контрмодель Крипке.

Разрешимость (mathbf {IPC}) была впервые получена Генценом в 1935 году. Неразрешимость (mathbf {IQC}) следует из неразрешимости (mathbf {CQC}) отрицательной интерпретацией, Знакомые неинтуиционистские логические схемы соответствуют структурным свойствам моделей Крипке, например

  • DNS сохраняется в каждой модели Крипке с конечным кадром.
  • ((A / rightarrow B) vee (B / rightarrow A)) выполняется в любой модели Крипке с линейно упорядоченной системой отсчета. Наоборот, каждая пропозициональная формула, которая не выводима в (mathbf {IPC} + (A / rightarrow B) vee (B / rightarrow A)), имеет контрмодель Крипке с линейно упорядоченной системой отсчета (см. Раздел 6.1 ниже).
  • Если (x) не свободна в (A), то (forall x (A / vee B (x)) rightarrow (A / vee / forall x B (x))) выполняется в каждом Крипке модель (mathbf {K}) с постоянной областью (так что (D (k) = D (k ')) для всех (k, k') в (K)). То же самое относится и к депутату.

Модели Крипке и модели Бет (которые отличаются от моделей Крипке в деталях, но интуитивно эквивалентны) являются мощным инструментом для определения свойств формальных систем интуиционизма; ср Troelstra и van Dalen [1988], Smorynski [1973], de Jongh и Smorynski [1976], Ghilardi [1999] и Iemhoff [2001], [2005]. Однако не существует чисто интуитивного доказательства того, что каждое предложение, которое справедливо во всех моделях Крипке и Бет, доказуемо в (mathbf {IQC}). После наблюдения Гёделя Крейзель [1958] подтвердил, что полнота интуиционистской логики предикатов для семантики Бета эквивалентна принципу М. П. Маркова, который Брауэр отверг.

Более того, Дайсон и Крейзель [1961] показали, что если (mathbf {IQC}) слабо завершено для семантики Бета (то есть, если в каждой модели Бета не выполняется недоказуемого предложения), то имеет место следующее следствие MP: [tag {GDK} forall / alpha_ {B (alpha)} neg / neg / существует x R (alpha, x) rightarrow / neg / neg / forall / alpha_ {B (alpha)} существует x R (alpha, x),) где (x) охватывает все натуральные числа, (alpha) распространяется на все бесконечные последовательности натуральных чисел, (B (alpha)) сокращает (forall x (alpha (x) leq 1)), а (R) выражает примитивно-рекурсивное отношение (alpha) и (x). И наоборот, GDK влечет за собой слабую полноту (mathbf {IQC}). Этот интересный принцип, который оправдывает отрицательную интерпретацию формы теоремы Брауэра,слабее MP, но недоказуемым в современных системах интуиционистского анализа. Kreisel [1962] предположил, что GDK может в конечном итоге быть доказуемым на основе еще не открытых свойств интуиционистской математики.

Изменяя определение модели Крипке, чтобы разрешить «взрывающиеся узлы», которые вводят каждое предложение, Вельдман [1976] нашел доказательство полноты, используя только интуиционистскую логику, но он поставил под сомнение, являются ли модели Крипке с взрывающимися узлами интуитивно-значимыми математическими объектами.

5.2. Семантика реализуемости для арифметики Хейтинга

Один из способов реализовать объяснение интуиционистской истины в BHK для арифметики - связать с каждым предложением (E) of (mathbf {HA}) некоторую коллекцию числовых кодов для алгоритмов, которые могут установить конструктивную истину (E). Следуя Клини [1945], число (e) реализует предложение (E) языка арифметики по индукции по логической форме (E):

(е) реализует (г = т) если (r = t) верно.
(е) реализует (A / oldand B) если (e) кодирует пару ((f, g)) такую, что (f) реализует (A), а (g) реализует (B).
(е) реализует (A / vee B) если (e) кодирует пару ((f, g)) так, что если (f = 0), то (g) реализует (A), а если (f / gt 0) тогда (g) реализует (B).
(е) реализует (A / rightarrow B) если всякий раз, когда (f) реализует (A), то (e) -ая частичная рекурсивная функция определяется в (f), а ее значение реализуется (B).
(e) реализует (neg A) если нет (f) реализует (A).
(e) реализует (forall x A (x)) если для каждого (n) (e) -ая частичная рекурсивная функция определена в (n) и ее значение реализуется (A (mathbf {n})).
(e) реализует (существует x A (x)) если (e) кодирует пару ((n, g)) и (g) реализует (A (mathbf {n})).

Произвольная формула реализуема, если некоторое число реализует свое универсальное замыкание. Заметим, что не обе (A) и (neg A) реализуемы для любой формулы (A). Основным результатом является

Теорема Нельсона [1947]

Если (A) выводима в (mathbf {HA}) из реализуемых формул (F), то (A) реализуема.

Некоторые неинтуиционистские принципы могут быть реализованы. Например, принцип Маркова (для разрешимых формул) можно выразить схемой

(MP) (forall x (A (x) vee / neg A (x)) oldand / neg / forall x / neg A (x) rightarrow / существует x A (x))

Несмотря на то, что в (mathbf {HA}) это недоказуемо, MP реализуется с помощью аргумента, который неофициально использует принцип Маркова. Но реализуемость - это принципиально неклассическая интерпретация. В (mathbf {HA}) можно выразить аксиому рекурсивного выбора CT (для «тезиса Черча»), которая противоречит LEM, но (конструктивно) осуществима. Следовательно, по теореме Нельсона (mathbf {HA}) (+) MP (+) CT согласован.

Клини использовала вариант реализуемости чисел, чтобы доказать, что (mathbf {HA}) удовлетворяет правилу Черча-Клини; тот же аргумент работает для (mathbf {HA}) с MP или CT, а также для (mathbf {HA}) (+) MP (+) CT. В Kleene и Vesley [1965] и Kleene [1969] функции заменяют числа как реализующие объекты, устанавливая согласованность формализованного интуиционистского анализа и его замыкание в соответствии с версией правила Чёрча-Клини второго порядка.

Теорема Нельсона устанавливает недоказуемость в (mathbf {IQC}) некоторых теорем классической логики предикатов. Если для каждой (n) - поставить предикатную букву (P (ldots)), формула (f (P)) из (L (mathbf {HA})) с (n) присваиваются свободные переменные, и если формула (f (A)) of (L (mathbf {HA})) получается из формулы (A) of (L) путем замены каждого простая формула (P (x_1, / ldots, x_n)) через (f (P) (x_1, / ldots, x_n)), тогда (f (A)) называется экземпляром арифметической подстановки (А). Например, если формула (L (mathbf {HA})), выражающая «(x)», кодирует доказательство в (mathbf {HA}) формулы с кодом (y)”Присваивается (P (x, y)), результирующий экземпляр арифметической замены (forall y (существует x P (x, y) vee / neg / Существует x P (x, y))) нереализуемо и, следовательно, недоказуемо в (mathbf {HA}), как и его двойное отрицание. Следовательно, (neg / neg / forall y (существует x P (x, y) vee / neg / существует x P (x, y))) не доказуемо в (mathbf {IQC}).

Де Джонг [1970] объединил реализуемость с моделированием Крипке, чтобы показать, что интуиционистская логика высказываний (mathbf {IPC}) и фрагмент (mathbf {IQC}) арифметически полны для (mathbf {HA})). Достаточно доказать равномерное назначение простых экзистенциальных формул для предикатов букв.

Теорема де Джонга (для МПК) [1970]

Если пропозициональная формула (A) языка (L) не доказуема в (mathbf {IPC}), то существует некоторый случай арифметической подстановки (A) не доказуемо в (mathbf {HA}).

Доказательство этой версии теоремы де Джонга не нуждается в реализуемости; ср Сморинский [1973]. Например, форма Россера теоремы Гёделя о неполноте дает предложение (C) о (L (mathbf {HA})) такое, что (mathbf {PA}) не доказывает ни (C), ни (neg C), поэтому свойство дизъюнкции (mathbf {HA}) не может доказать ((C / vee / neg C)). Но семантическое доказательство де Джонга также установило, что каждая интуитивно недоказуемая формула предиката ограниченного вида имеет экземпляр арифметической замены, который недоказуем в (mathbf {HA}). Используя синтаксический метод, Дэниел Лейвант [1979] расширил теорему де Йонга на все интуитивно-недоказуемые формулы предикатов, доказав, что (mathbf {IQC}) арифметически полон для (bf {HA}). См. Van Oosten [1991] для исторического изложения и более простого доказательства полной теоремы, используя абстрактную реализуемость с моделями Бета вместо моделей Крипке.

Не утверждая, что реализуемость числа совпадает с интуиционистской арифметической истиной, Нельсон заметил, что для каждой формулы (A) из (L (mathbf {HA})) предикат «(y) реализует (A)”Можно выразить в (mathbf {HA}) с помощью другой формулы (сокращенно« (y / realizesrel A) »), а схема (A / leftrightarrow / существует y (y / realizesrel A)) согласуется с (mathbf {HA}). Troelstra [1973] показал, что (mathbf {HA}) (+) ((A / leftrightarrow / существует y (y / realizesrel A))) эквивалентно (mathbf {HA}) (+) ЭСТ, где ЭСТ является усиленной формой КТ. В (mathbf {HA}) (+) MP (+) ECT, которую Троэльстра считает формализацией русской рекурсивной математики (см. Раздел 3.2 статьи по конструктивной математике), каждая формула форма ((y / realizesrel A)) имеет эквивалентную «классическую» предрасковую форму (A '(y)), состоящий из подформулы без кванторов, которому предшествуют чередующиеся «классические» кванторы форм (neg / neg / существующие x) и (forall z / neg / neg) и т. д. (Существует y A '(y)) является своего рода prenex формой (A).

6. Дополнительные темы и дальнейшее чтение

6.1 Субинтуиционистская и промежуточная логика

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

Субинтуиционистская логика высказываний может быть получена из (mathbf {IPC}) путем ограничения языка или ослабления логики, или обоих. Крайним примером первого является (mathbf {RN}), интуиционистская логика с единственной пропозициональной переменной (P), которая названа в честь ее первооткрывателей Ригера и Нисимуры [1960]. (mathbf {RN}) характеризуется решеткой Ригера-Нисимуры бесконечного числа неэквивалентных формул (F_n), такой что каждая формула, единственная пропозициональная переменная которой (P), эквивалентна интуиционистской логике некоторой (F_n). Версия Нисимуры

(begin {align *} F _ { infty} & = P / rightarrow P. \\ F_0 & = P / oldand / neg P. \\ F_1 & = P. \\ F_2 & = / neg P. \\ F_ {2 n + 3} & = F_ {2 n + 1} vee F_ {2n + 2}. \\ F_ {2 n + 4} & = F_ {2 n + 3} rightarrow F_ {2 n + 1}. / Конец {выравнивание *})

В (mathbf {RN}) ни (F_ {2 n + 1}), ни (F_ {2 n + 2}) не подразумевают другого; но (F_ {2 n}) подразумевает (F_ {2 n + 1}), а (F_ {2 n + 1}) подразумевает каждый из (F_ {2 n + 3}) и (F_ {2 n + 4}).

Фрагменты (mathbf {IPC}), пропускающие одно или несколько логических связок, ограничивают язык и, между прочим, логику, поскольку интуитивные связки (oldand), (vee), (rightarrow), (neg) логически независимы от (mathbf {IPC}). Роуз [1953] доказал, что неявный фрагмент (без (rightarrow)) является полным относительно реализуемости, в том смысле, что если каждый случай арифметической замены формулы высказывания (E) без (rightarrow) (число) -реализуемо, тогда (E) является теоремой (mathbf {IPC}). Этот результат контрастирует с

Теорема Роуза [1953]

(mathbf {IPC}) является неполной в отношении реализуемости.

Пусть (F) - пропозициональная формула [((neg / neg D / rightarrow D) rightarrow (neg / neg D / vee / neg D)) rightarrow (neg / neg D / vee / neg D)) где (D) есть ((neg P / vee / neg Q)) и (P), (Q) простые. Каждый экземпляр арифметической замены (F) реализуем (используя классическую логику), но (F) не доказуем в (mathbf {IPC}).

Отсюда следует, что (mathbf {IPC}) арифметически неполно для (mathbf {HA}) (+) ECT (см. Раздел 5.2).

Минимальная логика (mathbf {ML}) происходит из интуиционистской логики путем удаления ex falso. Колмогоров [1925] показал, что этот фрагмент уже содержит негативную интерпретацию классической логики, сохраняя оба квантификатора, ср. Leivant [1985]. Минимальная логика доказывает частный случай (neg A / rightarrow (A / rightarrow / neg B)) ex falso для отрицаний. Colacito, de Jongh и Vardas [2017] изучают различные субминимальные логики, каждая из которых слабее (mathbf {ML}).

Грисс оспаривал использование Брауером отрицания, возражая против закона противоречия и ex falso. Стоит отметить, что отрицание в действительности не требуется для интуиционистской математики, поскольку (0 = 1) является известным противоречием, поэтому (neg A) можно определить как (A / rightarrow 0 = 1). Тогда ex falso может быть определено как (0 = 1 / rightarrow A), и закон противоречия доказуем из остальных аксиом (mathbf {H}).

Промежуточной пропозициональной логикой является любой непротиворечивый набор пропозициональных формул, содержащий все аксиомы (mathbf {IPC}) и замкнутый относительно modus ponens и подстановки произвольных формул для букв пропозиции. Каждая промежуточная логика высказываний содержится в (mathbf {CPC}). Некоторые конкретные промежуточные логики высказываний, характеризующиеся добавлением одной или нескольких классически правильных, но интуитивистски недоказуемых аксиомных схем к (mathbf {IPC}), были тщательно изучены.

Одной из самых простых промежуточных пропозициональных логик является логика Геделя-Даммета (mathbf {LC}), полученная путем добавления к (mathbf {IPC}) схемы ((A / rightarrow B) vee (B) rightarrow A)), которая действует на всех и только на тех кадрах Крипке, в которых частичный порядок узлов является линейным. Гедель [1932] использовал бесконечную последовательность последовательно более сильных промежуточных логик, чтобы показать, что (mathbf {IPC}) не имеет конечной интерпретации таблицы истинности. Для каждого положительного целого числа (n) пусть (mathbf {G_n}) будет (mathbf {LC}) плюс схема ((A_1 / rightarrow A_2) vee / ldots / vee (A_1) oldand / ldots / oldand A_n / rightarrow A_ {n + 1})). Тогда (mathbf {G_n}) действует на всех и только на тех линейно упорядоченных фреймах Крипке, в которых не более (n) узлов.

Янковская логика (mathbf {KC}), которая добавляет к (mathbf {IPC}) принцип тестируемости (neg A / vee / neg / neg A), очевидно, не имеет дизъюнкции свойство. Логика Крейзеля-Путнама (mathbf {KP}), полученная путем добавления к (mathbf {IPC}) схемы ((neg A / rightarrow B / vee C) rightarrow ((neg A / rightarrow B) vee (neg A / rightarrow C))), обладает свойством дизъюнкции, но не удовлетворяет всем правилам Visser. Промежуточная логика получается путем добавления схемы (((neg / neg D / rightarrow D) rightarrow (D / vee / neg D)) rightarrow (neg / neg D / vee / neg D)), соответствующей в контрпример Роуз, в (mathbf {IPC}) также имеется свойство дизъюнкции. Iemhoff [2005] доказал, что (mathbf {IPC}) - единственная промежуточная логика высказываний со свойством дизъюнкции, которое замкнуто по всем правилам Виссера. Iemhoff и Metcalfe [2009] разработали формальное исчисление для обобщенной допустимости для (mathbf {IPC}) и некоторых промежуточных логик. Гудсмит [2015] - это тщательное изучение допустимых правил промежуточных логик с обширной библиографией.

Говорят, что промежуточная логика высказываний (mathbf {L}) обладает свойством конечного фрейма, если существует класс конечных фреймов, в котором формулы, допустимые по Крипке, являются в точности теоремами (mathbf {L}), Многие промежуточные логики, включая (mathbf {LC}) и (mathbf {KP}), обладают этим свойством. Янков [1968] использовал бесконечную последовательность фреймов Крипке с конечными корнями, чтобы доказать существование континуума многих промежуточных логик. Де Йонг, Вербрюгге и Виссер [2009] доказали, что каждая промежуточная логика (mathbf {L}) со свойством конечного фрейма является пропозициональной логикой (mathbf {HA (L)}), то есть класс всех формул на языке (mathbf {IPC}), все экземпляры арифметической замены которых доказуемы в логическом расширении (mathbf {HA}) с помощью (mathbf {L}).

Промежуточная логика высказываний (mathbf {L}) является структурно полной, если каждое правило, допустимое для (mathbf {L}), выводима в (mathbf {L}) и наследственно структурно завершена, если каждая промежуточная логика, расширяющая (mathbf {L}), также является структурно полной. Каждая промежуточная логика (mathbf {L}) имеет структурное пополнение (mathbf { overline {L}}), полученное присоединением всех допустимых правил. (mathbf {LC}) и (mathbf {G_n}) наследственно структурно завершены. Хотя (mathbf {IPC}), (mathbf {RN}) и (mathbf {KC}) не являются структурно полными, их структурные дополнения наследственно структурно полны. Эти и другие результаты см. В Citkin [2016, Другие интернет-ресурсы].

Некоторые логики промежуточных предикатов, расширяющие (mathbf {IQC}) и закрытые при замене, являются (mathbf {IQC}) (+) DNS (раздел 4.1), (mathbf {IQC}) (+) MP (см. Раздел 5.2), (mathbf {IQC}) (+) MP (+) IP (ср. Раздел 4.2) и интуиционистская логика постоянных областей (mathbf {CD}), полученный путем добавления в (mathbf {IQC}) схемы (forall x (A / vee B (x)) rightarrow (A / vee / forall x B (x))) для всех формул (A), (B (x)), где (x) не существует свободно в (A). Минц, Ольховиков и Уркхарт [2012, Другие интернет-ресурсы] показали, что (mathbf {CD}) не обладает свойством интерполяции, опровергая ранее опубликованные доказательства других авторов.

6.2 Расширенные темы

Влияние Брауэра на Геделя было значительным, хотя Гедель никогда не становился интуиционистом. Перевод Геделя [1933f] интуиционистской логики высказываний в модальную логику (mathbf {S4}) описан в разделе 2.5 вступления о Геделе и во вступительной заметке Троельстры к переводу [1933f] в томе I сборника Геделя. Работает. Смотрите также Мяты [2012]. Модели Крипке для модальной логики предшествовали моделям интуиционистской логики.

Альтернативы семантике Крипке и Бета для интуиционистской логики высказываний и предикатов включают топологическую интерпретацию Стоуна [1937], Тарского [1938] и Мостовского [1948] (ср. Расиова и Сикорский [1963], Расиова [1974]), которая была расширена. к интуиционистскому анализу Скотта [1968] и Крола [1978]. М. Хайланд [1982] определил эффективный топос Эфф и доказал, что его логика интуиционистская. Для очень информативного обсуждения семантики для интуиционистской логики и математики В. Райтенбергом и интересной новой перспективы Г. Бежанишвили и В. Холлидея см. Другие интернет-ресурсы (ниже).

Одной альтернативой семантике реализуемости для интуиционистской арифметики является интерпретация Геделя [1958] «Диалектика», которая связывает с каждой формулой (B) из (L (mathbf {HA})) формулу без кванторов (B_D)) на языке интуиционистской арифметики всех конечных типов. «Диалектическая» интерпретация (B), назовите это (B ^ D), есть (существует Y / forall x B_D (Y, x)). Если (B) является замкнутой теоремой (mathbf {HA}), то (B_D (F, x)) доказуемо для некоторого члена (F) в теории Гёделя (mathbf { T}) «примитивно-рекурсивных» функционалов более высокого типа. Для перевода из (B) в (B ^ D) требуется аксиома выбора (для всех конечных типов), MP и IP, поэтому она не является строго конструктивной; тем не мение,теоретико-числовые функции, выражаемые членами (F) из (mathbf {T}), являются в точности доказуемо рекурсивными функциями (mathbf {HA}) (и (mathbf {PA})). Интерпретация была расширена до анализа Спектором [1962]; ср Говард [1973]. Четкие описания и дополнительные ссылки можно найти во введении Троэльстры к английскому переводу в Гёделе [1990], в оригинальной статье «Диалектика», в «Авигад и Феферман» (1998) и «Феррейра» (2008).

Хотя (mathbf {HA}) является надлежащей частью классической арифметики, интуиционистское отношение к математическим объектам приводит к теории действительных чисел (см. Разделы 3.4–3.7 статьи об интуиционизме в философии математики), расходящейся от классического. Интерпретация функциональности реализуемости Клини, разработанная для доказательства согласованности его формализации (mathbf {FIM}) интуиционистской теории последовательностей («интуиционистский анализ»), меняет интерпретацию арифметических формул; например, (neg / neg / forall x (A (x) vee / neg A (x))) реализуема для каждой арифметической формулы (A (x)). На языке анализаПринцип Маркова и отрицательный перевод счетной аксиомы выбора входят в число многих неинтуиционистских принципов, которые реализуемы по функциям (классическими аргументами) и, следовательно, согласуются с (mathbf {FIM}); ср Kleene [1965], Vesley [1972] и Moschovakis [2003].

Конкретная и абстрактная семантика реализуемости для широкого спектра формальных систем была разработана и изучена логиками и компьютерными учеными; ср Troelstra [1998] и van Oosten [2002] и [2008]. Вариации основных понятий особенно полезны для установления относительной согласованности и относительной независимости нелогических аксиом в теориях, основанных на интуиционистской логике; некоторые примеры - Moschovakis [1971], Lifschitz [1979], и понятия реализуемости для конструктивных и интуиционистских теорий множеств, разработанные Rathjen [2006, 2012] и Chen [2012]. Ранние абстрактные понятия реализуемости включают косые черты Kleene [1962, 1963] и Aczel [1968], а также Lauuchli [1970]. Коленбах, Авигад и другие разработали интерпретации реализуемости для частей классической математики.

Логика оправдания Артемова - это альтернативная интерпретация объяснения БХК интуиционистских связок и квантификаторов с (идеализированными) доказательствами, играющими роль реализующих объектов. См. Также Артемов и Иемхофф [2007].

Другое направление в интуиционистской логике касается весьма противоречивого «создания предметных контрпримеров» Брауэра к принципам классического анализа (таким как принцип Маркова), которые нельзя опровергнуть на основе теории (mathbf {FIM}) Клини и Веслей [1965]. Ослабив форму Клини принципа непрерывного выбора Брауэра и добавив аксиому, которую он назвал Схемой Крипке (КП), Михилл удалось формализовать аргументы создавшего субъекта. КП несовместимо с (mathbf {FIM}), но Весли [1970] нашел альтернативный принцип (схема В. Весли), который можно последовательно добавлять в (mathbf {FIM}) и подразумевает все контрпримеры, для которых Брауэр требовал создания темы. Крол [1978] и Скоукрофт дали топологические доказательства непротиворечивости для интуиционистского анализа со схемой Крипке и слабой непрерывностью.

6.3 Рекомендуемое чтение

Запись о LEJ Brouwer обсуждает философию и математику Брауэра с хронологией его жизни и избранным списком публикаций, включая переводы и вторичные источники. Лучший способ узнать больше - прочитать некоторые оригинальные статьи. Английские переводы докторской диссертации Брауэра и других работ, которые первоначально появились на голландском языке, наряду с рядом статей на немецком языке, можно найти в LEJ Brouwer: Collected Works [1975], под редакцией Heyting. Основная книга Бенацеррафа и Патнэма содержит Брауэра [1912] (в переводе на английский), Брауэра [1949] и Дамметта [1975]. В работе Mancosu [1998] представлены английские переводы многих фундаментальных статей Брауэра, Хейтинга, Гливенко и Колмогорова, а также вводный материал В. ван Стигта, чей [1990] является еще одним ценным ресурсом.

Третье издание [1971] классики Хейтинга [1956] является привлекательным введением в интуиционистскую философию, логику и математическую практику. В рамках внушительного проекта по редактированию и изданию Brouwer's Nachlass, van Dalen [1981] дает исчерпывающее представление о собственной интуиционистской философии Брауэра. Английский перевод Ван Хейенурата [1969] Брауэра [1927] (с прекрасным вступлением Парсонса) по-прежнему является неотъемлемой ссылкой на теорию континуума Брауэра. Veldman [1990] и [2005] являются подлинными современными примерами традиционной интуиционистской математической практики. Troelstra [1991] помещает интуиционистскую логику в ее исторический контекст как общую основу конструктивной математики в двадцатом веке. Бежанишвили и де Йонг [2005,Другие интернет-ресурсы] включает последние разработки в интуиционистской логике.

Клини и Весли [1965] дают тщательную аксиоматическую трактовку интуиционистского анализа, доказательство его согласованности относительно классически правильной субтеории и расширенное приложение к теории генераторов вещественных чисел Брауэра. Клини [1969] формализует теорию частично рекурсивных функционалов, позволяя точную формализацию интерпретации реализуемости функции, использованной в [1965], и связанной интерпретации q-реализуемости, которая дает правило Чёрча-Клини для интуитивистского анализа.

Troelstra [1973], Beeson [1985] и Troelstra и van Dalen's [1988] (с исправлениями) выделяются как наиболее всеобъемлющие исследования интуиционистских и полуинтуиционистских формальных теорий, использующих как конструктивные, так и классические методы, с полезными библиографиями. Troelstra и Schwichtenberg [2000] представляют параллельную теорию доказательства классической, интуиционистской и минимальной логики, уделяя особое внимание секвенциальным системам. В работе Troelstra [1998] представлены формулы-как-типы и (Kleene and Aczel) слэш-интерпретации для логики высказываний и предикатов, а также абстрактные и конкретные реализуемости для множества приложений. Конструктивная теория типов Мартина-Лёфа [1984] (см. Раздел 3.4 статьи по конструктивной математике) обеспечивает другую общую структуру, в которой интуиционистские рассуждения продолжают развиваться.

Библиография

  • Aczel, P., 1968, «Насыщенные интуиционистские теории», в работах HA Schmidt, K. Schütte и H.-J. Тиле (ред.), «Вклад в математическую логику», Амстердам: Северная Голландия: 1–11.
  • Артемов С., Иемхофф Р., 2007. «Основная интуиционистская логика доказательств», Журнал Symbol Logic, 72: 439–451.
  • Avigad, J. and Feferman, S., 1998, «Функциональная (« диалектическая ») интерпретация Гёделя», глава V Buss (ed.) 1998: 337–405.
  • Bar-Hillel, Y. (ed.), 1965, логика, методология и философия науки, Амстердам: Северная Голландия.
  • Beeson, MJ, 1985, Основы конструктивной математики, Берлин: Springer.
  • Benacerraf, P. и Hilary Putnam (eds.), 1983, Философия математики: избранные чтения, 2-е издание, Кембридж: издательство Кембриджского университета.
  • Бет, EW, 1956, «Семантическая конструкция интуиционистской логики», Koninklijke Nederlandse Akad. фон Веттенскаппен, 19 (11): 357–388.
  • Брауэр, LEJ, 1907, «Об основах математики», тезис, Амстердам; Английский перевод в Heyting (ed.) 1975: 11–101.
  • –––, 1908, «Ненадежность логических принципов», английский перевод в Heyting (ed.) 1975: 107–111.
  • –––, 1912, «Интуиционизм и формализм», английский перевод А. Дрездена, Бюллетень Американского математического общества, 20 (1913): 81–96, перепечатано в Benacerraf and Putnam (eds.) 1983: 77–89; также перепечатано в Heyting (ed.) 1975: 123–138.
  • –––, 1923 [1954], «О значении принципа исключенного среднего в математике, особенно в теории функций», «Дополнения и исправления» и «Дальнейшие добавления и исправления», английский перевод в van Heijenoort (ed.) 1967: 334–345.
  • –––, 1923C, «Intuitionistische Zerlegung mathematischer Grundbegriffe», Jahresbericht der Deutschen Mathematiker-Vereinigung, 33 (1925): 251-256; перепечатано в Heyting (ed.) 1975, 275-280.
  • –––, 1927, «Интуиционистские размышления о формализме», впервые опубликованный в 1927 году, английский перевод в van Heijenoort (ed.) 1967: 490–492.
  • –––, 1948, «Сознание, философия и математика», первоначально опубликованная (1948), перепечатанная в Benacerraf and Putnam (eds.) 1983: 90–96.
  • Burr, W., 2004, «Интуиционистская арифметическая иерархия», в J. van Eijck, V. van Oostrom и A. Visser (eds.), Logic Colloquium '99 (Конспект лекций в Logic 17), Wellesley, MA: ASL и А. К. Петерс, 51–59.
  • Buss, S. (ed.), 1998, Справочник по теории доказательств, Амстердам и Нью-Йорк: Elsevier.
  • Чен, РМ. и Ратхен, М., 2012. Реализуемость по Лифшицу для интуиционистской теории множеств Цермело-Френкеля, Архив для математической логики, 51: 789–818.
  • Коласито, А., де Йонг, Д. и Варгас, А., 2017, «Субминимальное отрицание», Soft Computing, 21: 165–164.
  • Кроссли Дж. И М. А. Дамметт (ред.), 1965, «Формальные системы и рекурсивные функции», Амстердам: Издательство Северной Голландии.
  • van Dalen, D. (ed.), 1981, Кембриджские лекции Брауэра по интуиционизму, Кембридж: издательство Кембриджского университета.
  • Dummett, M., 1975, «Философские основы интуиционистской логики», первоначально опубликованные (1975), перепечатанные в Benacerraf and Putnam (eds.) 1983: 97–129.
  • Дайсон, В. и Крейзель, Г., 1961, Анализ семантической конструкции Бет интуиционистской логики, Технический отчет № 3, Стэнфорд: Лаборатория прикладной математики и статистики, Стэнфордский университет.
  • Феррейра, Ф., 2008, «Самый художественный пакет беспорядочных идей», Диалектика, 62: 205–222.
  • Фридман, H., 1975, «Свойство дизъюнкции подразумевает свойство числового существования», Труды Национальной академии наук, 72: 2877–2878.
  • Генцен Г., 1934–5, «Untersuchungen Über das logische Schliessen», Mathematische Zeitschrift, 39: 176–210, 405–431.
  • Гиларди, С., 1999, «Объединение в интуиционистской логике», Журнал символической логики, 64: 859–880.
  • Гливенко, В., 1929, «Sur quelques points de la logique де М. Брауэра», Академия Королевства Бельгии, Бюллетени науки, 5 (15): 183–188.
  • Гёдель, К., 1932, «Zum intuitionistischen Aussagenkalkül», Anzeiger der Akademie der Wissenschaften, Wien, 69: 65–66. Воспроизведено и переведено со вступительной запиской А. С. Троельстры в Гёделе 1986: 222–225.
  • –––, 1933e, «Zur intuitionistischen Arithmetik und Zahlentheorie», Ergebnisse eines mathematischen Kolloquiums, 4: 34–38.
  • –––, 1933f, «Eine Interpretation des intuitionistischen Aussagenkalküls», воспроизведенный и переведенный со вступительной запиской А. С. Троельстры в Gödel 1986: 296–304.
  • –––, 1958, «Uber eine bisher noch nich nicht benützte Erweiterung des finiten Standpunktes», Dialectica, 12: 280–287. Воспроизведено с английским переводом в Gödel 1990: 241–251.
  • –––, 1986, Собрание сочинений. I, S. Feferman et al. (ред.), Оксфорд: издательство Оксфордского университета.
  • –––, 1990, Собрание сочинений. II, S. Feferman et al. (ред.), Оксфорд: издательство Оксфордского университета.
  • Гоудсмит, JP, 2015, Интуиционистские правила: допустимые правила промежуточной логики, к.т.н. диссертация, Утрехтский университет.
  • Харроп Р., 1960, «О формулах типов (A / rightarrow B / vee C, A / rightarrow (Ex) B (x)) в интуиционистских формальных системах", Журнал символической логики, 25: 27–32,
  • van Heijenoort, J. (ed.), 1967, от Фреге к Геделю: сборник материалов по математической логике 1879–1931, Кембридж, Массачусетс: издательство Гарвардского университета.
  • Heyting, A., 1930, «Die Formalen Regeln der intuitionistischen Logik», в трех частях, Sitzungsberichte der preussischen Akademie der Wissenschaften: 42–71, 158–169. Английский перевод части I в Mancosu 1998: 311–327.
  • –––, 1956, Интуиционизм: Введение, Амстердам: Издательство Северной Голландии, 3-е пересмотренное издание, 1971.
  • Heyting, A. (ed.), 1975, LEJ Brouwer: Собрание сочинений (том 1: Философия и основы математики), Амстердам и Нью-Йорк: Elsevier.
  • Ховард В. А., 1973, «Наследственно мажорируемые функционалы конечного типа», в Troelstra (ed.) 1973: 454–461.
  • Hyland, JME, 1982, «Эффективный топос», в Troelstra и van Dalen (ed.) 1982: 165–216.
  • Имхофф Р., 2001. «О допустимых правилах интуиционистской логики высказываний», Журнал символической логики, 66: 281–294.
  • –––, 2005, «Промежуточная логика и правила Виссера», Notre Dame Journal of Formal Logic, 46: 65–81.
  • Iemhoff, R. и Metcalfe, G., 2009, «Теория доказательств допустимых правил», Annals of Pure and Applied Logic, 159: 171–186.
  • Янков В. А., 1968. Построение последовательности сильно независимых суперинтуиционистских исчислений высказываний // Советская математика. Doklady, 9: 801–807.
  • Джерабек Э., 2008. «Независимые основы допустимых правил», Logic Journal of IGPL, 16: 249–267.
  • де Йонг, DHJ, 1970, «Максимальность интуиционистского исчисления высказываний по отношению к арифметике Хейтинга», Журнал символической логики, 6: 606.
  • де Йонг, DHJ, и Сморински, C., 1976, «Модели Крипке и интуиционистская теория видов», Анналы математической логики, 9: 157–186.
  • де Йонг, Д., Вербрюгге, Р. и Виссер, А., 2011, «Промежуточная логика и свойство де Йонга», Архив математической логики, 50: 197–213.
  • Kino, A., Myhill, J. and Vesley, RE (eds.), 1970, Интуиционизм и теория доказательств: Материалы летней конференции в Буффало, штат Нью-Йорк, 1968, Амстердам: Северная Голландия.
  • Kleene, SC, 1945, «Об интерпретации интуиционистской теории чисел», Journal of Symbolic Logic, 10: 109–124.
  • –––, 1952, Введение в метаматематику, Принстон: Ван Ностранд.
  • –––, 1962, «Разъединение и существование под влиянием элементарных интуиционистских формализмов», Журнал символической логики, 27: 11–18.
  • –––, 1963, «Приложение», Журнал символической логики, 28: 154–156.
  • –––, 1965, «Классические расширения интуиционистской математики», в Bar-Hillel (ed.) 1965: 31–44.
  • –––, 1969, Формализованные рекурсивные функционалы и формализованная реализуемость, Мемуары Американского математического общества 89.
  • Kleene, SC и Vesley, RE, 1965, Основы интуиционистской математики, особенно в связи с рекурсивными функциями, Амстердам: Северная Голландия.
  • Крейзель Г., 1958, «Элементарные свойства полноты интуиционистской логики с примечанием об отрицаниях формул предынк», Журнал символической логики, 23: 317–330.
  • –––, 1962, «О слабой полноте интуиционистской логики предикатов», Журнал символической логики, 27: 139–158.
  • Крипке С. А., 1965, «Семантический анализ интуиционистской логики», в J. Crossley и MAE Dummett (eds.) 1965: 92–130.
  • Крол, М., 1978, «Топологическая модель интуиционистского анализа с помощью схемы Крипке», Zeitschrift für Math. Logik und Grundlagen der Math. 24: 427–436.
  • Leivant, D., 1979, «Максимум интуиционистской логики», Математический центр Tracts 73, Mathematisch Centrum, Амстердам.
  • –––, 1985, «Синтаксические переводы и доказуемо рекурсивные функции», Журнал символической логики, 50: 682–688.
  • Läuchli, H., 1970, «Абстрактное понятие реализуемости, для которого интуиционистское исчисление предикатов завершено», в A. Kino et al. (ред.) 1965: 227–234.
  • Лифшиц, В., 1979, «CT (_ 0) сильнее, чем CT (_ 0) !,» Труды Американского математического общества, 73 (1): 101–106.
  • Манкосу, П., 1998, от Брауэра до Гильберта: дискуссия об основах математики в 1920-х годах, Нью-Йорк и Оксфорд: издательство Оксфордского университета.
  • Мартин-Лёф, П., 1984, Интуиционистская теория типов, Заметки Джованни Самбина из серии лекций, прочитанных в Падуе, июнь 1980, Неаполь: Библиополис.
  • Минц, Г., 2012, «Перевод Геделя – Тарского интуиционистских пропозициональных формул», в «Правильном рассуждении» (Конспект лекций в области компьютерных наук 7265), Э. Эрдем и соавт. (ред.), Дордрехт: Springer-Verlag: 487–491.
  • Moschovakis, JR, 1971, «Не может быть нерекурсивных функций?», Journal of Symbolic Logic, 36: 309–315.
  • –––, 2003, «Классические и конструктивные иерархии в расширенном интуиционистском анализе», Журнал символической логики, 68: 1015–1043.
  • –––, 2009, «Логика Брауэра и Хейтинга», в «Логике от Рассела до Церкви» («Справочник по истории логики», том 5), Дж. Вудс и Д. Габбей (ред.), Амстердам: Elsevier: 77 -125.
  • –––, 2017, «Интуиционистский анализ и конец времени», Бюллетень символической логики, 23: 279–295.
  • Нельсон Д., 1947, «Рекурсивные функции и интуиционистская теория чисел», Труды Американского математического общества, 61: 307–368.
  • Нисимура И., 1960, «О формулах одной переменной в интуиционистском исчислении высказываний», Журнал символической логики, 25: 327–331.
  • Ван Остен, J., 1991, «Семантическое доказательство теоремы де Йонга», Архив для математической логики, 31: 105–114.
  • –––, 2002, «Реализуемость: исторический очерк», Математические структуры в информатике, 12: 239–263.
  • –––, 2008, Реализуемость: введение в ее категориальную сторону, Амстердам: Elsevier.
  • Плиско В. Е., 1992. Об арифметической сложности некоторых конструктивных логик. Математические заметки (1993): 701–709. В переводе с Математических заметок, 52 (1992): 94–104.
  • Rasiowa, H., 1974, алгебраический подход к неклассической логике, Амстердам: Северная Голландия.
  • Rasiowa, H. и Sikorski, R., 1963, Математика метаматематики, Варшава: Panstwowe Wydawnictwo Naukowe.
  • Ратхен, М., 2006, «Реализуемость для конструктивной теории множеств Цермело-Френкеля», в Logic Colloquium 2003 (лекционные заметки в логике 24), J. Väänänen et al. (ред.), AK Peters 2006: 282–314.
  • –––, 2012, «От слабого к сильному свойству существования», Анналы чистой и прикладной логики, 163: 1400–1418.
  • Роуз, Г. Ф., 1953, «Исчисление высказываний и реализуемость», Труды Американского математического общества, 75: 1–19.
  • Рыбаков В., 1997. Допустимость правил логического вывода. Амстердам: Elsevier.
  • Скотт Д., 1968, «Расширение топологической интерпретации до интуиционистского анализа», Compositio Mathematica, 20: 194-210.
  • Smorynski, CA, 1973, «Применение моделей Крипке», в Troelstra (ed.) 1973: 324–391.
  • Spector, C., 1962, «Обеспечиваемо рекурсивные функционалы анализа: доказательство непротиворечивости анализа путем расширения принципов, сформулированных в современной интуиционистской математике», «Теория рекурсивных функций: материалы симпозиумов по чистой математике», том 5, JCE Dekker (изд.), Providence, RI: Американское математическое общество, 1–27.
  • van Stigt, WP, 1990, Интуиционизм Брауэра, Амстердам: Северная Голландия.
  • Стоун, MH, 1937, «Топологическое представление распределительных решеток и брауверских логик», Casopis Pest. Мат. FYS., 67: 1–25.
  • Тарский А., 1938, «Der Aussagenkalkül und die Topologie», Fundamenta Mathematicae, 31: 103–104.
  • Troelstra, AS, 1991, «История конструктивизма в двадцатом веке», серия публикаций ITLI ML – 1991–05, Амстердам. Окончательный вариант в «Теории множеств, арифметике и основах математики» (Конспект лекций в логике 36), Дж. Кенни и Р. Коссак (ред.), Ассоциация символической логики, Итака, Нью-Йорк, 2011: 150–179.
  • –––, 1998, «Реализуемость», глава VI Buss (ed.), 1998: 407–473.
  • –––, Вводная записка к 1958 и 1972 гг., Gödel, 1990: 217–241.
  • Troelstra, AS (ed.), 1973, Метаматематическое исследование интуиционистской арифметики и анализа (Конспект лекций по математике 344), Берлин: Springer-Verlag. Исправления и дополнения доступны в редакторе.
  • Troelstra, AS и Schwichtenberg, H., 2000, Базовая теория доказательств (Кембриджские трактаты в теоретической информатике: том 43), 2-е издание, Cambridge: Cambridge University Press.
  • Troelstra, AS и van Dalen, D., 1988, Конструктивизм в математике: введение, 2 тома, Амстердам: Издательство Северной Голландии. [См. Также исправления в других интернет-ресурсах.]
  • Troelstra, AS и van Dalen, D. (eds.), 1982, 100-летний симпозиум LEJ Brouwer, Амстердам: Издательство Северной Голландии.
  • Вельдман В., 1976, «Интуиционистская теорема полноты для интуиционистской логики предикатов», Журнал символической логики, 41: 159–166.
  • –––, 1990, «Обзор интуиционистской теории описательного множества», в работе П. П. Петкова (ред.), Математическая логика, Материалы конференции Хейтинга, Нью-Йорк и Лондон: Пленум Пресс, 155–174.
  • –––, 2005, «Два простых набора, которые не являются положительно борелевскими», Annals of Pure и Applied Logic, 135: 151–209.
  • Веслей, RE, 1972, «Последовательности выбора и принцип Маркова», Compositio Mathematica, 24: 33–53.
  • –––, 1970, «Приятная альтернатива схеме Крипке», A. Kino et al. (ред.) 1970: 197 и далее.
  • Visser, A., 1999, «Правила и арифметика», Notre Dame Journal of Formal Logic, 40: 116–140.
  • –––, 2002, «Подстановки предложений (Sigma ^ {0} _1): исследования между интуиционистской логикой высказываний и интуиционистской арифметикой», Анналы чистой и прикладной логики, 114: 227–271.
  • –––, 2006, «Предикатная логика конструктивных арифметических теорий», Журнал символической логики, 72: 1311–1326.

Академические инструменты

значок сеп человек
значок сеп человек
Как процитировать эту запись.
значок сеп человек
значок сеп человек
Предварительный просмотр PDF-версию этой записи в обществе друзей SEP.
значок Inpho
значок Inpho
Посмотрите эту тему в Проекте интернет-философии онтологии (InPhO).
Фил документы
Фил документы
Расширенная библиография для этой записи в PhilPapers со ссылками на ее базу данных.

Другие интернет-ресурсы

  • Бежанишвили Г. и Холлидей В., 2018, «Семантическая иерархия для интуиционистской логики», рукопись, Публикации факультета Калифорнийского университета в Беркли.
  • Бежанишвили Н. и де Йонг, DHJ, 2005, Интуиционистская логика, Конспект лекций, представленный в ESSLLI, Эдинбург.
  • Брауэр, выдержки из лекций Брауэра в Кембридже.
  • Ситкин А., 2016, «Наследственно структурно полные суперинтуиционистские дедуктивные системы», рукопись на arXiv.org.
  • Минц Г., Ольховиков Г., Уркхарт А., 2012. «Отказ интерполяции в интуиционистской логике постоянных областей», рукопись, arXiv.org.
  • Troelstra, AS и JR Moschovakis, 2018, Исправления к А. С. Troelstra и D. van Dalen, 1988, Конструктивизм в математике.
  • Проблемы в логике доказуемости, поддерживаемые Львом Беклемишевым.
  • Реализация Библиография, поддерживается Ларс Биркедал.
  • van Oosten 2000 и другие препринты, связанные с осуществимостью, поддержанные Яапом ван Остеном.

Рекомендуем: