Cтраница 1
Генцен [ ОепГгеп и ] ЗМ. [1]
Генцен употребляет Sequenz, что переводится по-английски sequent, так как английское слово sequence занято под обозначение произвольной последовательности предметов, чему по-немецки соответствует Folge. [2]
Генцен доказал, что трансфинитная индукция до любого е-числа не сводима к обычной индукции, и поэтому теорема об убывающей последовательности орд. [3]
Генцен продемонстрировал применение своей обобщенной основной теоремы, получив с ее помощью результаты о непротиворечивости, сходные с теми, которые раньше были получены Аккерманом, Нейманом и Эрбраном. [4]
Генцен пользуется системами своего типа с секвенциями, но эти системы эквивалентны системам гильбертовского типа. [5]
Генцен, ни разу не был упомянут) Этот недостаток отчасти восполняется примечаниями редактора и Дополнением А, содержащим, в частности, эскиз идейного развития области, включая объяснение сути генценовских методов. Дополнение А ( и отчасти В) содержит также информацию о другом методе автоматического доказательства теорем, появившемся одновременно с методом резолюций. [6]
Однако когда Генцен показал, что с помощью некоторого обобщения методов теории доказательств - а именно, при использовании обобщенной индукции до первого е-числа - может быть доказана непротиворечивость арифметического формализма, Ак-керман обнаружил, что связанный с гильбертовским подходом метод при соответствующем расширении этого метода также может дать полное доказательство непротиворечивости. [7]
Основная теорема Генцена, или теорема о нормальной форме ( теорема 48 ниже), утверждает, что сечения всегда можно устранить из доказательства любой секвенции, в которой никакая переменная не встречается одновременно и в свободном и в связанном виде. [8]
Как известно, Генцен в своей классической работе [1] предложил формулировку классического и интуиционистского исчисления предикатов в форме исчисления секвенций и доказал, что каждый вывод в этом исчислении может быть приведен к так называемой нормальной форме, не содержащей правила сечения. Фактически Генцен предлагает некоторую конкретную и весьма естественную систему редукций выводов и показывает, что для каждого вывода можно подобрать конечную последовательность редукций из этой системы, приводящую первоначальный вывод в вывод с той же последней секвенцией, но уже без сечений. Таким образом, описывается некоторый способ приведения каждого вывода к нормальной форме, отличный от тривиального перебора. [9]
В другом варианте [1936 ] Генцен рассматривал только секвенции, имеющие в точности одну сукцедентную формулу. [10]
В то же время работы Генцена и других авторов ( Аккер-1 мац, Шютте, о Торенцен, Спектор) выявили существование методов, близких к финитным и позволяющих все же обосновать непротиворечивость ряда формализованных теорий, не поддающихся финитным методам. [11]
Исчисление G0 является частью исчисления G, предложенного Генценом. Исчисления генценовского типа по сравнению с изученными нами Исчислениями являются более удобными при анализе и поиске формальных доказательств. Это объясняется основной особенностью этих исчислений, которая, грубо говоря, состоит в том, что сложность формул при применении правил может только возрастать. Здесь мы лишь применим отмеченное выше свойство исчисления G0 для получения непротиворечивости ИВ, не прибегая к понятию интерпретации исчисления. В самом деле, рассмотрим секвенцию - Qo Индукцией по высоте легко заметить, что если D - доказательство секвенции S в исчислении GO и существует вхождение формулы в D, содержащее логическую связку Л или, то эта логическая связка обязана входить в S. Поэтому, если секвенция ( - Q0 доказуема в G0, то она может быть получена из аксиомы с помощью только правил 5) - 8), что очевидным образом невозможно. Применяя предложения 1 - 4, получаем непротиворечивость ИВ. [12]
Кальмар использует для этого рассуждение, с помощью которого Генцен в его работе: Qentzen G. [13]
Только что изложенные доказательства менее элементарны чем те, которые основаны на теореме Генцена о нормальной форме, но они помогают вникнуть в то, как работает интуиционистская логика в качестве орудия арифметических рассуждений. [14]
Исчисление GHPC ( интуиционистское исчисление предикатов в форме исчисления секвенций, исчисление предикатов в стиле Генцена) приспособлено для вывода секвенций. Оно содержит аксиомы следующих двух видов: ( рТ - Ду. [15]