Неразрешимость логики первого порядка

а это предложение является описанием времени s + 1.

Если имеется стрелка типа (в), то одна из формул множества Д есть

"x "y "t ((t Qi x' t Aj x') → (t' Qk x (t A0 y → t' A0 y) … (t An y → t' An y)))

Тогда существует такой символ aq, что из последней формулы, объединенной с (5), (6), (8), следует

0(s+1)Qi0(p-1) 0(s+1) … 0(s+1)Aj 0(p-1) … 0(s+1) "y

((y y 0(p-1) … y) → 0(s+1)A0 y)

а это предложение является описанием времени s + 1.

Во всех трех случаях множество Д имеет следствием некоторое описание времени s + 1, и тем самым неразрешимость логики первого порядка доказана.

Доказательство неразрешимости логики первого порядка методом Геделя

Для доказательства неразрешимости логики первого порядка достаточно продемонстрировать, как по данной машине Т с входным значением n (то есть когда машина находится на самой левой единице в сплошной последовательности из n единиц при пустых символах в остальных клетках ленты) построить такие предложение I и конечное множество предложений Г, что машина Т при входном значении останавливается тогда и только тогда, когда Г ├ I.

Не существует эффективной процедуры, позволяющей решать, останавливается ли произвольная машина Тьюринга Т при произвольном входном значении n и по данной машине Тьюринга Т можно построить примитивно рекурсивную функцию g, обладающую следующим свойством: какое бы n мы не взяли, g (n, t) = 0 в точности тогда, когда t – номер шага, более позднего, чем тот, на котором машина T останавливается, если ее запустить при входном значении n. (по определению функции g, если шаг t не таков, то g (x, t) = <a, b, c> = для некоторых a, b, c и потому g (x, t) > 0. Если же t – такой шаг, то g (x, t) = 0.

Таким образом, если дана машина Т, то можно эффективно построить некоторую конечную последовательность q0, q1, …, qr примитивно рекурсивных функций, удовлетворяющую двум условиям: 1) каждая функция gi либо является базисной функцией, либо получается из некоторых предыдущих функций с помощью композиции или примитивной рекурсии и 2) для всякого n машина T, запущенная на входном значении n, в конце концов останавливается тогда и только тогда, когда gr(n, t) = 0 для некоторого t.

Построим теперь по данной T последовательность примитивно рекурсивных функций, удовлетворяющую условиям 1) и 2). Каждой функции gi поставим в соответствие свой функциональный символ gi с тем же числом аргументов, что и gi. Пусть g0 = '. Используя эти символы, выпишем для каждого gi одну или две очевидные формулы, определяющие функцию gi Например,

если gi = z, то "x gi(x) = 0

если gi = s, то "x gi(x) = x'

если gi = , то "x1 … "xm … "xn gi(x1, …, xm, …, xn) = xm

Если gi получается из предшествующих ей функций gj и gk c помощью примитивной рекурсии, то "x gi(x, 0) =gj(x) и "x "y gi(x, y') =gk(x, y, gi(x, y))

Если же gi получается из предшествующих ей функций gо и путем композиции, то "x gi(x) =gj (для краткости заменили здесь x1, x2, …, xn на x, a "x1, "x2, …, "xn на "x)

Запишем также формулы "x x ' ≠ 0 и "x "y (x ' = y ' → x = y). Обозначим теперь через Г множество всех этих формул, а через I – формулу .

Утверждение. Машина T при входном значении останавливается тогда и только тогда, когда Г ├ I.

«Тогда». Пусть Г ├ I. Обозначим через модель, областью которой служит множество натуральных чисел и которая интерпретирует символ 0 как 0, а функциональные символы gi – как . Все предложения из Г истинны в . Поскольку Г ├ I, предложение I истинно также. Следовательно, для некоторого справедливо . Согласно 2), T останавливается на .

«Только тогда». Предположим, что Т останавливается при входном значении . Для доказательства соотношения Г ├ I предположим, что – произвольная модель, в которой все предложения из Г истинны, и покажем, что из этого предположения следует истинность в . Пусть теперь – интерпретация символа 0 в модели , a – при всяком – интерпретация в символа gi. Пусть, далее, (так что – интерпретация в символа ), и пусть . Так как формулы и истинны в , функция , для которой и , является изоморфизмом множества {0, 1, 2,…} натуральных чисел на множество N. Таким образом, можно считать, что N и является в действительности множеством натуральных чисел, , ограничение функции на множество N есть , а потому всякий нумерал е обозначает число в .

 Скачать реферат