WikiDer > Теорема Крейгса - Википедия

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

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

Позволять ${ 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.