Теорема Крейгса - Craigs theorem - Wikipedia

В математическая логика, Теорема Крейга заявляет, что любой рекурсивно перечислимый набор из правильные формулы из язык первого порядка является (примитивно) рекурсивно аксиоматизируемый. Этот результат не имеет отношения к известному Крейг интерполяция теорема, хотя оба результата названы в честь одного и того же логика, Уильям Крейг.

Рекурсивная аксиоматизация

Позволять ${\displaystyle A_{1},A_{2},\dots }$ - перечисление аксиом рекурсивно перечислимого множества T формул первого порядка. Построим еще одно множество T *, состоящее из

${\displaystyle \underbrace {A_{i}\land \dots \land A_{i}} _{i}}$

для каждого положительного целого числа я. В дедуктивные замыкания из T * и T, таким образом, эквивалентны; доказательство покажет, что T * - рекурсивное множество. Процедура принятия решения для T * поддается следующей неофициальной аргументации. Каждый член T * либо ${\displaystyle A_{1}}$ или формы

${\displaystyle \underbrace {B_{j}\land \dots \land B_{j}} _{j}.}$

Поскольку каждая формула имеет конечную длину, можно проверить, является ли она ${\displaystyle A_{1}}$ или указанной формы. Если он имеет указанную форму и состоит из j конъюнкты, он находится в T *, если (повторяющийся) конъюнкт ${\displaystyle A_{j}}$; в противном случае его нет в T *. Опять же, можно проверить, действительно ли конъюнкт ${\displaystyle A_{n}}$ пройдя через перечисление аксиом T и затем проверяя символ за символом, идентичны ли выражения.

Примитивные рекурсивные аксиоматизации

Приведенное выше доказательство показывает, что для каждого рекурсивно перечислимого набора аксиом существует рекурсивный набор аксиом с таким же дедуктивным замыканием. Набор аксиом примитивно рекурсивный если есть примитивная рекурсивная функция, которая определяет принадлежность к набору. Чтобы получить примитивную рекурсивную аксиматизацию, вместо замены формулы ${\displaystyle A_{i}}$ с

${\displaystyle \underbrace {A_{i}\land \dots \land A_{i}} _{i}}$

один вместо этого заменяет его на

${\displaystyle \underbrace {A_{i}\land \dots \land A_{i}} _{f(i)}}$ (*)

куда ж(Икс) - функция, которая, учитывая я, возвращает историю вычислений, показывающую, что ${\displaystyle A_{i}}$ находится в исходном рекурсивно перечислимом наборе аксиом. Примитивная рекурсивная функция может анализировать выражение формы (*), чтобы получить ${\displaystyle A_{i}}$ и j. Тогда, потому что T-предикат Клини примитивно рекурсивно, примитивно рекурсивная функция может проверить, что j действительно история вычислений по мере необходимости.

Философские последствия

Если ${\displaystyle T}$ является рекурсивно аксиоматизируемой теорией, и мы разделим ее предикаты на два непересекающихся множества ${\displaystyle V_{A}}$ и ${\displaystyle V_{B}}$, то теоремы ${\displaystyle T}$ что есть в словарном запасе ${\displaystyle V_{A}}$ рекурсивно перечислимы и, следовательно, на основании теоремы Крейга аксиоматизируемы. Карл Г. Хемпель на основании этого утверждал, что, поскольку все научные предсказания находятся в словаре терминов наблюдения, теоретический словарь науки в принципе устраним. Он сам выдвинул два возражения против этого аргумента: 1) новые аксиомы науки практически не поддаются контролю, и 2) наука использует индуктивные рассуждения, и устранение теоретических терминов может изменить индуктивные отношения между предложениями наблюдения. Хилари Патнэм утверждает, что этот аргумент основан на неправильном представлении о том, что единственная цель науки - успешное предсказание. Он предполагает, что основная причина, по которой нам нужны теоретические термины, заключается в том, что мы хотим говорить о теоретических сущностях (таких как вирусы, радиозвезды и элементарные частицы).

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

• Уильям Крейг. «Об аксиоматизируемости внутри системы», Журнал символической логики, Vol. 18, № 1 (1953), стр. 30-32.
• Хилари Патнэм. "Теорема Крейга", Журнал Философии, Vol. 62, No. 10 (1965), pp. 251.260.