Cтраница 2
Для арифметической формальной системы, если Г - Е классически, то Г - Е интуиционистски ( Генцен [ 1936, стр. [16]
При построении системы мы использовали следующие работы: Гильберт и Аккерман [1928], Гильберт и Бернайс [1934, 1939], Генцен [1934-35], Бернайс [1936] и некоторые другие не столь явные источники. [17]
При некоторых специальных предположениях о форме конечной секвенции может быть получена дальнейшая нормализация доказательств, как в следующей обобщенной основной теореме, которую Генцен [1934-35] дал для своей классической системы. Как заметил Генцен, доказательство этой теоремы иллюстрирует возможности перестановок выводов в его системах. [18]
Для секвенций стандартного вида ( того самого, приведение к которому предполагается методом резолюций) не составляет труда извлечь из второй формы теоремы Эрбрана следующий частный случай теоремы Генцена. [19]
Как известно, Генцен в своей классической работе [1] предложил формулировку классического и интуиционистского исчисления предикатов в форме исчисления секвенций и доказал, что каждый вывод в этом исчислении может быть приведен к так называемой нормальной форме, не содержащей правила сечения. Фактически Генцен предлагает некоторую конкретную и весьма естественную систему редукций выводов и показывает, что для каждого вывода можно подобрать конечную последовательность редукций из этой системы, приводящую первоначальный вывод в вывод с той же последней секвенцией, но уже без сечений. Таким образом, описывается некоторый способ приведения каждого вывода к нормальной форме, отличный от тривиального перебора. [20]
Рассуждения Генцена относятся к некоторому специальному исчислению - исчислению секвенций. То, что его рассмотрения равным образом могут быть осуществлены и средствами нашего исчисления формул, было показано К. [21]
При некоторых специальных предположениях о форме конечной секвенции может быть получена дальнейшая нормализация доказательств, как в следующей обобщенной основной теореме, которую Генцен [1934-35] дал для своей классической системы. Как заметил Генцен, доказательство этой теоремы иллюстрирует возможности перестановок выводов в его системах. [22]
Это не значит, что нельзя найти другие пути доказательства непротиворечивости арифметики. И действительно, Генцен 10 доказал ее, но его методы основаны на трансфинитной индукции. Я не стану объяснять здесь, что это такое, но вопрос о непротиворечивости самой трансфинитной индукции остается открытым. [23]
При желании1) случай а 0, для которого множество чисел р пусто, можно было бы рассматривать отдельно в качестве базиса. Для основной теоремы Генцена рассуждение состоит в том, что если теорема верна для всех доказательств с индукционными числами ( а, Ь, с) р а ( ш8), то она верна и для доказательств с ( а, Ь, с) а. Индукционное число а ( а, Ь, с) вполне упорядочивает случаи теоремы в том порядке, в котором они доказываются, так же как и натуральное число, являющееся индукцонным числом в обыкновенной индукции. [24]
Так же как трансфинитная индукция до ш8, может быть сведена к обыкновенной индукции и индукция до е 1) - это было проделано формально Гильбертом и Бернайсом [ 1939, стр. В последней своей статье [1943] Генцен доказывает несводимость индукции до е0 прямо, а не косвенно с помощью теоремы Геделя и своего доказательства непротиворечивости. [25]
Если а и а - т доказуемы по Бету, то а и а - т логически истинны, следовательно, т также логически истинно ( почему. Этот метод применяется в теореме Генцена, однако его доказательство выходит за рамки этой книги. [26]
Аккерман намеревается применить трансфинитную индукцию в виде, использованном Генценом, для распространения своего прежнего, изложенного в гл. [27]
Такое же открытие вскоре после этого было сделано и Генценом. Сходное утверждение содержится уже в опубликованной в 1925 г. работе: Колмогоров А. Н. О принципе tertium non datur - Матем. [28]
Кальмар использует для этого рассуждение, с помощью которого Генцен в его работе: Qentzen G. Сам Генцен тоже ссылается на это рассуждение в своем более позднем доказательстве непротиворечивости, однако здесь он говорит об этом способе обоснования как о предварительном, с намерением когда-нибудь вернуться к рассмотрению этого вопроса. [29]
Мы начинаем с неформального обсуждения интуиционистской логики и семантики. Далее приводятся две формы интуиционистского исчисления предикатов. Наконец, формулируется исчисление предикатов в форме исчисления секвенций Генцена и затем, доказав допустимость в этой системе правила сечения, мы устанавливаем его эквивалентность с первоначальными исчислениями. Это позволяет получить первые точные результаты относительно интуиционистской логики: невыводимость закона исключенного третьего, свойства дизъюнктивности и экзистенциальности. [30]