Undecidable indirectly reflexive sentences.pdf Формула языка теории первого порядка T называется неразрешимой в T, еслини сама формула, ни её отрицание не являются теоремами этой теории. Таким об-разом, теория T неполна тогда и только тогда, когда существуют неразрешимыеформулы в этой теории.Если предполагать, что теория формальной арифметики S º-непротиворечива,то можно построить неразрешимое в этой теории предложение. Впервые это про-делал К. Гёдель с помощью процедуры, которая в честь него называется гёдели-зацией.Гёделизацией теории формальной арифметики S называется функция g, ото-бражающая инъективно множество всех термов, формул и конечных последова-тельностей формул во множество целых положительных чисел. При этом требу-ется: (i) чтобы значение функции g можно было вычислить с помощью некоторо-го алгоритма, (ii) чтобы существовал алгоритм, позволяющий для каждого целогоm определить, является ли m значением функции g, и в случае, если является, топостроить тот объект x, для которого m = g(x). Значение функции g для терма(формулы, последовательности формул) называется гёделевым номером соответ-ствующего объекта. Функцию g можно определить стандартным образом (см., на-пример, [1, с. 151, 152; 2, с. 229, 230]).Для каждого n ¶ N терм n определяется как соответствующий нумерал в тео-рии S. Если M является выражением с гёделевым номером n, то определим ⎡M⎤как нумерал n.В данной работе изучаются косвенно самоссылочные предложения в S (впредположении, что данная теория º-непротиворечива), «говорящие» о доказуе-мости и/или опровержимости. Рассматриваются некоторые совокупности такихпредложений и доказывается, что среди них существуют неразрешимые предло-жения. Предварительно доказывается обобщение на случай косвенной рефлексииизвестной леммы о диагонализации (о рефлексии). Кроме того, показывается, каксуществование неразрешимых предложений приводит к парадоксам, если дока-зуемость и опровержимость заменить истиной и ложью.22 В.М. ЗюзьковКосвенная рефлексия в формальной арифметикеПусть m - целое положительное число и B1, B2, …, Bm - формулы теории S сосвободными переменными x1, x2, …, xm. Назовем m-местной диагонализациейсписка формул B1, B2, …, Bm список формулCi — f x1, x2, …, xm (x1 = ⎡B1⎤ & x2 = ⎡B2⎤ & … & xm = ⎡Bm⎤ & Bi)для всех i = 1, 2, …, m.Если m=1, то получаем известное определение диагонализации формулы.Лемма 1. Существуют вычислимые функции d1(x1, x2, …, xm), d2(x1, x2, …, xm),…, dm(x1, x2, …, xm), такие, что если n1, n2, …, nm - гёделевы номера формул B1, B2,…, Bm, то d1(n1, n2, …, nm), d2(n1, n2, …, nm), …, dm(n1, n2, …, nm) - соответственногёделевы номера формул C1, C2, …, Cm.Доказательство. Для произвольных натуральных чисел n1, n2, …, nm и длякаждого i = 1, 2, …, m определим di(x1, x2, …, xm) как гёделевый код формулыf x1, x2, …, xm (x1 = n1 & x2 = n2 & … & xm = nm & Bi).Функции di вычислимы. Действительно, зная n1, n2, …, nm, можно алгоритми-чески проверить, являются ли данные числа гёделевыми номерами формул. Еслиэто так, то можно построить соответствующие формулы B1, B2, …, Bm и алгорит-мическим способом отыскать свободные переменные в этих формулах и убедить-ся, что они суть x1, x2, …, xm. После этого, в соответствии с имеющейся гёделевойнумерацией можно вычислить код Ci.Детали используемых алгоритмов зависят от конкретной гёделизации. Функ-ция di не определена в тех случаях, когда какое-то nk не является гёделевым номе-ром формулы со свободными переменными x1, x2, …, xm. Так как вычислимые функции d1, d2, …, dm представимы в теории S, то сущест-вуют формулы D1(x1, x2, …, xm, y), D2(x1, x2, …, xm, y), …, Dm(x1, x2, …, xm, y), такие,что если для любых i (1 „ i „ m), n1, n2, …, nm и ki имеем di(n1, n2, …, nm) = k, то|- ey (Di(n1, n2, …, nm, y) ~ y = ki)в теории S.Теорема 1 (о косвенной рефлексии). Пусть m - целое положительное числои B1, B2, …, Bm - формулы теории S со свободными переменными x1, x2, …, xm. То-гда существуют такие формулы G1, G2, …, Gm, что|- G1 ~ B1(⎡G1⎤, ⎡G2⎤, …, ⎡Gm⎤),|- G2 ~ B1(⎡G1⎤, ⎡G2⎤, …, ⎡Gm⎤),…|- Gm ~ B1(⎡G1⎤, ⎡G2⎤, …, ⎡Gm⎤)в теории S.Доказательство. Для всех i = 1, 2, …, m определим формулыFi(x1, x2, …, xm) — f y1, y2, …, ym (D1(x1, x2, …, xm, y1) & D2(x1, x2, …, xm, y2) & ... && Dm(x1, x2, …, xm, ym) & Bi(y1, y2, …, ym)).Пусть ni - гёделев номер формулы Fi соответственно. Для всех i = 1, 2, …, mопределим формулыGi — f x1, x2, …, xm (x1 = n1 & x2 = n2 & ... xm = nm & Fi(x1, x2, …, xm)).Так как Gi логически эквивалентноf y1, y2, …, ym (D1(n1, n2, …, nm, y1) & D2(n1, n2, …, nm, y2) & ... && Dm(n1, n2, …, nm, ym) & Bi(y1, y2, …, ym)),Неразрешимые косвенно рефлексивные предложения 23то имеем|- Gi ~ f y1, y2, …, ym (D1(n1, n2, …, nm, y1) & D2(n1, n2, …, nm, y2) & ...&& Dm(n1, n2, …, nm, ym) & Bi(y1, y2, …, ym)).Формулы G1, G2, …, Gm образуют m-местную диагонализацию формул F1, F2,…, Fm. Пусть ki - гёделев номер формулы Gi, соответственно. Для всех i = 1, 2,…, m имеем|- ey (Di(n1, n2, …, nm, y) ~ y = ki).Значит,|- Gi ~ f y1, y2, …, ym (y1 = k1 & y2 = k2 & ... & ym = km & Bi(y1, y2, …, ym)).Следовательно,|- Gi ~ Bi(k1, k2, …, km)).Т. е. для всех i = 1, 2, …, m имеем|- Gi ~ Bi(⎡G1⎤, ⎡G2⎤, …, ⎡Gm⎤). Замечание 1. Если m = 1, то получаем известную теорему о диагонализации (орефлексии). Пусть B(x) произвольная формула формальной арифметики, имеющаяединственную свободную переменную x. Тогда можно построить замкнутуюформулу G, такую, что |- G ~ B(⎡G⎤). Формула G «говорит о себе», что она обла-дает свойством B.Замечание 2. Некоторые из формул Bi могут не содержать всех переменныхx1, x2, …, xm. Соответствующее утверждение остается в силе и при этих допуще-ниях. В частности, справедливо следующее утверждение: пусть B1(x) и B2(x) - двеформулы с единственной свободной переменной х. Тогда существуют формулыG1 и G2, такие, что выполнено |- G1 ~ B1(⎡G2⎤) и |- G2 ~ B2(⎡G1⎤).Будем предполагать, что теория S в стандартной интерпретации непротиворе-чива. Это означает, что любая замкнутая формула является либо истинной, либоложной в стандартной интерпретации.Как известно [1], отношение Provable(n, m): «формула с гёделевым номером nявляется выводимой (доказуемой) в S и ее доказательство имеет номер m», воз-можно выразить в S некоторой формулой Pr(x, y), т.е.1) если Provable(n, m) истинно, то |- Pr(n, m),2) если Provable(n, m) ложно, то |- ¬ Pr(n, m).Формула P(n) — fy Pr(n, y) выражает свойство «формула с гёделевым номеромn является выводимой (доказуемой) в S».Замечание 3. Описанную выше гёделеву нумерацию можно провести такимобразом, чтобы для любой формулы A элементарной арифметики из |- A следова-ло |- P(⎡A⎤) [3, с. 27].Определение º-непротиворечивости. Говорят, что формальная арифметикаявляется º-непротиворечивой, если следующие два условия не выполняются вме-сте ни для какой формулы ϕ:(i) |- fy ϕ(y);(ii) |- ¬ϕ (0), |- ¬ϕ (1), |- ¬ϕ (2), …Лемма 2. Пусть формальная арифметика º-непротиворечива, тогда для любойформулы A отношения |- P(⎡A⎤) и |- A равносильны.Доказательство. В силу замечания 3 осталось доказать только, что для любойформулы A отношение |- P(⎡A⎤) влечет |- A. Докажем от противного. Пусть имеем|- P(⎡A⎤) и не выполнено |- A. Положим ϕ(y) — Pr(⎡A⎤, y). Так как P(⎡A⎤) — fy ϕ(y),24 В.М. Зюзьковто имеем |- fy ϕ(y). Так как не выполнено |- A, то ни для какого натуральногочисла m доказательство с номером m не является доказательством формулы A.Поэтому для любого m имеем |- ¬Pr(⎡A⎤, m), или в других обозначениях |- ¬ϕ (m).Таким образом, одновременно выполнено|- fy ϕ(y);|- ¬ϕ (0), |- ¬ϕ (1), |- ¬ϕ (2), …,что означает º-противоречивость формальной арифметики. Отметим, что из леммы 2 не следует |- A ~ P(⎡A⎤).В дальнейшем будем использовать символ «d» как обозначение слов «тогда итолько тогда, когда», в частности, лемма 2 утверждает, что |- P(⎡A⎤) d |- A.Свойство |- ¬A будем обозначать словами «формула A опровержима». Поэто-му для любой формулы A её доказуемость логически равносильна опровержимо-сти ¬A. Далее, соответствие ⎡A⎤ ¬ ⎡¬A⎤ очевидным образом является взаимно-однозначным и вычислимым. Следовательно, обозначение R(⎡ A⎤) для формулыP(⎡¬A⎤) не является двусмысленным.Поэтому, если теория формальной арифметики S является º-непротиворе-чивой, то в силу леммы 2 выражение «A доказуема» одновременно означает |- A и|- P(⎡A⎤), а выражение «A опровержима» одновременно означает как |- ¬A, так иR(⎡A⎤).Далее в статье рассматриваются формулы вида С(x), где формула C совпадаетс одной из формул P, R, ¬P и ¬R. В зависимости от выбора C замкнутая формулаС(⎡A⎤) «утверждает» доказуемость (опровержимость, недоказуемость, неопровер-жимость) формулы A.Утверждения, аналогичные лемме 2, но относящиеся к формулам ¬P и ¬R, неимеют места. Точнее, логические равносильности |- ¬P(⎡A⎤) d |- ¬A, |- ¬P(⎡A⎤)d «не |- A» и |- ¬R(⎡A⎤) d «не |- ¬A» не выполняются в общем случае. Поэтомуупотреблять такие выражения, как «формула A недоказуема» и «формула A неоп-ровержима», следует с осторожностью. Например, «формула A недоказуема» оз-начает |- ¬P(⎡A⎤) или «не |- A»? Условимся о следующем: когда предложение A1,«говорит» о другом предложении A2, что оно недоказуемо или неопровержимо, товсегда подразумевается соответственно |- A1 ~ ¬P(⎡A2⎤) или |- A1 ~ ¬R(⎡A2⎤). В ос-тальных случаях слова «формула A недоказуема» означает ложность |- A (истин-ность «не |- A»).Существование неразрешимых предложенийДалее всюду предполагается, что теория формальной арифметики S являетсяº-непротиворечивой.Будем рассматривать различные группы предложений, «косвенно говорящих»о своей доказуемости или опровержимости. Теорема о косвенной рефлексии ут-верждает, что такие предложения выразимы соответствующими формулами втеории S.Нам понадобится в дальнейшем ряд лемм.Лемма 3. Если формулы £ и ¤ таковы, что выполнено |- £ ~ ¤ и формула £ не-разрешима, то формула ¤ также неразрешима.Доказательство. Если |- ¤, то из |- £ ~ ¤ следует |- £. Кроме того, из |- £ ~ ¤следует |- ¬£ ~ ¬¤, поэтому из |- ¬¤ получаем |- ¬£. Полученное противоречиедоказывает лемму. Неразрешимые косвенно рефлексивные предложения 25Лемма 4. A. Если формулы £ и ¤ таковы, что выполнено |- £ ~ P(⎡¤⎤), то|- £ d |- ¤.B. Если формулы £ и ¤ таковы, что выполнено |- £ ~ ¬P(⎡¤⎤), то |- ¬£ d |- ¤.Доказательство. A. Пусть |- £, тогда |- P(⎡¤⎤), и по лемме 2 имеем |- ¤. Еслиже формула £ недоказуема, то недоказуема формула P(⎡¤⎤) и снова по лемме 2недоказуема формула ¤.B. Из |- £ ~ ¬P(⎡¤⎤) следует |- ¬£ ~ P(⎡¤⎤) и поэтому по первой части леммыполучаем |- ¬£ d |- ¤. Лемма 5. A. Если формулы £ и ¤ таковы, что выполнено |- £ ~ R(⎡¤⎤), то|- £ d |- ¬¤.B. Если формулы £ и ¤ таковы, что выполнено |- £ ~ ¬R(⎡¤⎤), то |- ¬£ d |- ¬¤.Доказательство. A. Формула R(⎡¤⎤) по определению означает P(⎡¬¤⎤), и по-этому утверждение данной леммы следует из леммы 4(A).B. Если |- £ ~ ¬R(⎡¤⎤), то отсюда следует |- ¬£ ~ R(⎡¤⎤), и теперь по первойчасти леммы имеем |- ¬£ тогда и только тогда, когда |- ¬¤ Лемма 6. Пусть формулы £, ¤ и ¥ таковы, что выполнено |- £ d |- ¬¤ и |- ¤d |- ¬¥. Тогда 1) ¤ или ¥ неразрешима или 2) |- £ d |- ¥.Доказательство. Рассмотрим два случая: формула £ доказуема и недоказуе-ма. Пусть выполнено |- £, тогда |- ¬¤, следовательно, ¤ недоказуема, и поэтому¬¥ также недоказуема. Если |- ¥, то формулы £ и ¥ доказуемы вместе. Если жеформула ¥ недоказуема, то формулы ¬¥ и ¥ недоказуемы вместе, т.е. в этом случаеформула ¥ неразрешима.Пусть теперь £ недоказуема, тогда и формула ¬¤ недоказуема. Если же фор-мула ¤ недоказуема, то он разрешима. Поэтому пусть ¤ доказуема, тогда |- ¬¥ и,следовательно, ¥ недоказуема. Таким образом, в этом случае формулы £ и ¥ недо-казуемы вместе. Лемма 7. Пусть формулы £, ¤ и ¥ таковы, что выполнено |- ¬£ d |- ¤ и |- ¬¤d |- ¥. Тогда 1) £ или ¤ неразрешима или 2) |- £ d |- ¥.Доказательство. Перепишем условие леммы в другом порядке |- ¥ d |- ¬¤ и|- ¤ d |- ¬£ Теперь видим, с точностью до замены обозначений, что выполняет-ся условие леммы 6, откуда и следует требуемое заключение. Первое неразрешимое предложение появилось в знаменитой теореме КуртаГёделя о неполноте (см., например, [4]).Теорема 2a (по Гёделю). Если формула G такова, что |- G ~ ¬P(⎡G⎤), то фор-мулы G и P(⎡G⎤) неразрешимы.Доказательство. Лемма 4(B) говорит, что |- ¬G тогда и только тогда, когда|- G. Это не будет противоречием, если формула G неразрешима. Неразрешимостьформулы P(⎡G⎤) тогда следует из неразрешимости G по лемме 3. Известно также [4], что для существования неразрешимого предложения вме-сто свойства недоказуемости можно взять свойство опровержимости. Рассмотре-ние вопроса о связи неразрешимости и опровержимости достаточно полно прове-дено в книге Раймонда Смаллиана [5].Теорема 2b (по Смаллиану). Если формула L такова, что |- L ~ R(⎡L⎤), то фор-мулы L и R(⎡L⎤) неразрешимы.Доказательство. Лемма 5(A) говорит, что |- L тогда и только тогда, когда|- ¬L. Это не будет противоречием, если формула L неразрешима. Неразреши-мость формулы R(⎡L⎤) следует из неразрешимости L по лемме 3. 26 В.М. ЗюзьковТеперь перейдем к косвенной рефлексии.Теорема 3a. Пусть даны предложения (n > 1) со косвенной самоссылочностью:A1: «Предложение A2 доказуемо»;A2: «Предложение A3 доказуемо»;A3: «Предложение A4 доказуемо»;…An-1: «Предложение An доказуемо»;An: «Предложение A1 опровержимо».Тогда предложение A1 неразрешимо.Доказательство. Условие теоремы означает, что множество формул {A1, A2,…, An} обладает следующими свойствами:|- A1 ~ P(⎡A2⎤),|- A2 ~ P(⎡A3⎤),…|- An-1 ~ P(⎡An⎤),|- An ~ R(⎡A1⎤).По леммам 4(A) и 5(A) получаем логическую эквивалентность утверждений:|- ¬A1 d |- A2,|- ¬A2 d |- A3,…|- ¬An-1 d |- An,|- An d |- ¬A1.Получаем цепь утверждений |- A1 d |- A2 d … d |- An. Имеем отношения: од-новременно выполняются |- A1 d |- An и |- An d |- ¬A1. Полученный результатне будет противоречием, если формула A1 неразрешима. Теорема 3b. Пусть даны предложения с косвенной самоссылочностью:B1: «Предложение B2 неопровержимо»;B2: «Предложение B3 неопровержимо»;…Bn-1: «Предложение Bn неопровержимо»;Bn: «Предложение B1 опровержимо».Тогда предложение Bn неразрешимо.Доказательство. Условие теоремы означает, что множество формул {B1, B2,…, Bn} обладает следующими свойствами:|- B1 ~ ¬R(⎡B2⎤),|- B2 ~ ¬R(⎡B3⎤),…|- Bn-1 ~ ¬R(⎡Bn⎤),|- Bn ~ R(⎡B1⎤).По лемме 5 получаем логическую эквивалентность утверждений:|- ¬B1 d |- ¬B2,|- ¬B2 d |- ¬B3,…|- ¬Bn-1 d |- ¬Bn,|- Bn d |- ¬B1.Получаем цепь утверждений |- ¬B1 d |- ¬B2 d … d |- ¬Bn. Получили отно-шения: одновременно имеем |- ¬B1 d |- ¬Bn и |- Bn d |- ¬B1. Полученный ре-зультат не будет противоречием, если формула Bn неразрешима. Неразрешимые косвенно рефлексивные предложения 27Теорема 4a. Рассмотрим предложения с косвенной самоссылочностью:C1: «Предложение C2 недоказуемо»,C2: «Предложение C3 недоказуемо»,…Cn: «Предложение C1 недоказуемо».Если n нечетно, то среди предложений C1, C3, C4, …, Cn имеется неразреши-мое предложение.Доказательство. Условие теоремы означает, что множество формул {C1, C2,…, Cn} обладает следующими свойствами:|- C1 ~ ¬P(⎡C2⎤),|- C2 ~ ¬P(⎡C3⎤),…|- Cn ~ ¬P(⎡C1⎤).Случай n = 1 доказан в теореме 2a, в этом случае неразрешимой является фор-мула C1. Поэтому будем предполагать, что n…3. По лемме 4(B) имеем логическуюэквивалентность утверждений:|- ¬ C1 d |- C2,|- ¬ C2 d |- C3,…|- ¬ Cn d |- C1,Множество всех эквивалентностей, за исключением первой, разобьем на под-ряд идущие пары вида|- ¬ Ci d |- Ci+1,|- ¬ Ci+1 d |- Ck,где i пробегает множество 2, 4, …, n-2 и для всех пар, за исключением послед-ней, k обозначает i+2, а для последней пары k есть 1. Пусть в каждой такой пареформулы Ci+1 и Ci+2 разрешимы, тогда по лемме 7 имеем |- Ci d |- Ck. Когда i про-бегает четные значения 2, 4, …, n- 2, получаем цепь |- C2 d |- C4 d … d |- Cn.Отсюда следует |- C2 d |- Cn d |- C1. Получили отношения: одновременно имеем|- C2 d |- C1 и |- ¬C1 d |- C2. Полученный результат не будет противоречием,если формула C1 неразрешима. А если это не так, то среди формул C3, C4, …, Cnимеется неразрешимая формула. Теорема 4b. Рассмотрим предложения с косвенной самоссылочностью:D1: «Предложение D2 опровержимо»;D2: «Предложение D3 опровержимо»;…Dn: «Предложение D1 опровержимо».Если n нечетно, то среди предложений D2, D3, D4, …, Dn имеется неразреши-мое предложение.Доказательство. Условие теоремы означает, что множество формул {D1, D2,…, Dn} обладает следующими свойствами:|- D1 ~ R(⎡D2⎤),|- D2 ~ R(⎡D3⎤),…|- Dn ~ R(⎡D1⎤).Случай n = 1 доказан в теореме 2b, в этом случае неразрешимой является фор-мула Dn. Поэтому будем предполагать, что n…3. По лемме 5(A) имеем логическуюэквивалентность утверждений:28 В.М. Зюзьков|- D1 d |- ¬ D2,|- D2 d |- ¬ D3,…|- Dn d |- ¬ D1.Множество всех эквивалентностей, за исключением первой, разобьем на под-ряд идущие пары вида|- Di d |- ¬ Di+1,|- Di+1 d |- ¬ Dk,где i пробегает множество 2, 4, …, n-2 и для всех пар, за исключением послед-ней, k обозначает i+2, а для последней пары k есть 1. Пусть в каждой такой пареформулы Di+1 и Dk разрешимы, тогда по лемме 6 имеем |- Di d |- Dk. Когда iпробегает четные значения 2, 4, …, n-2, получаем цепь |- D2 d |- D4 d … d |- Dn.Отсюда следует |- D2 d |- Dn d |- D1. Получили отношения: одновременно имеем|- D2 d |- D1 и |- D1 d |- ¬ D2. Полученный результат не будет противоречием,если формула D2 неразрешима. А если это не так, то среди формул D3, D4, …, Dnимеется неразрешимая формула. Теорема 5a. Пусть даны предложения (n>1) с косвенной самоссылочностью:E1: «Предложение E2 доказуемо»;E2: «Предложение E3 доказуемо»;…En-1: «Предложение En доказуемо»;En: «Предложение E1 недоказуемо».Тогда предложение En неразрешимо.Доказательство. Условие теоремы означает, что множество формул {E1, E2,…, En} обладает следующими свойствами:|- E1 ~ P(⎡E2⎤),|- E2 ~ P(⎡E3⎤),…|- En-1 ~ P(⎡En⎤),|- En ~ ¬P(⎡E1⎤).Первые n-1 отношения по лемме 4(A) дают |- E1 d |- E2 d … d |- En. Из по-следнего отношения по лемме 4(B) получаем |- E1 d |- ¬En. Полученный резуль-тат не будет противоречием, если формула En неразрешима. Теорема 5b. Пусть даны предложения с косвенной самоссылочностью:F1: «Предложение F2 неопровержимо»;F2: «Предложение F3 неопровержимо»;…Fn-1: «Предложение Fn неопровержимо»;Fn: «Предложение F1 недоказуемо».Тогда предложение Fn неразрешимо.Доказательство. Условие теоремы означает, что множество формул {F1, F2,…, Fn} обладает следующими свойствами:|- F1 ~ ¬R(⎡F2⎤),|- F2 ~ ¬R(⎡F3⎤),…|- Fn-1 ~ ¬R(⎡Fn⎤),|- Fn ~ ¬P(⎡F1⎤).По леммам 4 и 5 получаем логическую эквивалентность утверждений:Неразрешимые косвенно рефлексивные предложения 29|- ¬F1 d |- ¬F2,|- ¬F2 d |- ¬F3,…|- ¬Fn-1 d |- ¬Fn,|- ¬Fn d |- F1.Получаем цепь утверждений |- ¬F1 d |- ¬F2 d … d |- F1. Получили отноше-ние |- ¬F1 d |- F1. Полученный результат не будет противоречием, если формулаF1 неразрешима. Теорема 6a. Рассмотрим предложения с косвенной самоссылочностью:H1: «Предложение H2 недоказуемо»,H2: «Предложение H3 недоказуемо»,…Hn-1: «Предложение Hn недоказуемо»,Hn: «Предложение H1 доказуемо».Если n четно, то среди предложений H2, H3, …, Hn имеется неразрешимоепредложение.Доказательство. Точно также как при доказательствах предыдущих теорем,получаем логическую эквивалентность утверждений:|- ¬ H1 d |- H2,|- ¬ H2 d |- H3,…|- ¬ Hn-1 d |- Hn,|- Hn d |- H1.Случай n = 2 доказан в теореме 5a, при этом формула H2 неразрешима.При n>2 разбиваем эти эквивалентности, за исключением первой и последней,на подряд идущие пары. Предполагаем, что все формулы H3, H4, …, Hn разреши-мы, тогда получаем цепь |- H2 d |- H4 d … d |- Hn. Отсюда следует |- H2 d |- Hnd |- H1. Получили отношения: одновременно имеем |- H2 d |- H1 и |- H1 d|- ¬H2. Полученный результат не будет противоречием, если формула H2 нераз-решима. А если это не так, то среди формул H3, H4, …, Hn имеется неразрешимаяформула. Теорема 6b. Рассмотрим предложения с косвенной самоссылочностью:J1: «Предложение J2 недоказуемо»,J2: «Предложение J3 недоказуемо»,…Jn-1: «Предложение Jn недоказуемо»,Jn: «Предложение J1 неопровержимо».Если n четно, то среди предложений J2, J3, …, Jn имеется неразрешимое пред-ложение.Доказательство. Случай n = 2 доказан в теореме 5b. При этом неразрешимымпредложением будет J2.При n>2 по лемме 4(B) получаем логическую эквивалентность утверждений:|- ¬J1 d |- J2,|- ¬J2 d |- J3,…|- ¬Jn-1 d |- Jn,к которым добавляется (по лемме 5(B)) ещё одна эквивалентность|- ¬Jn d |- ¬J1.30 В.М. ЗюзьковДалее, разбиваем эти эквивалентности, за исключением первой и последней,на подряд идущие пары. Предполагаем, что все формулы J3, J4, …, Jn разреши-мы, тогда по лемме 6 получаем цепь |- J2 d |- J4 d … d |- Jn. Отсюда следует|- J2 d |- Jn. Применим лемму 7 к данной и последней эквивалентности |- ¬Jn d|- ¬J1. Если J2 неразрешима, то доказывать нечего. Поэтому остается вариант, ко-гда J2 разрешима, тогда по лемме 7 получаем |- ¬J2 d |- ¬J1. Учитывая первуюэквивалентность |- ¬J1 d |- J2, получаем |- ¬J2 d |- J2, что противоречит разре-шимости J2. Следовательно, J2 неразрешима. А если это не так, то среди формулJ3, J4, …, Jn имеется неразрешимая формула. Теорема 7a. Рассмотрим предложения с косвенной самоссылочностью:K1: «Предложение K2 опровержимо»;K2: «Предложение K3 опровержимо»;K3: «Предложение K4 опровержимо»;…Kn-1: «Предложение Kn опровержимо»;Kn: «Предложение K1 доказуемо».Если n четно, то среди предложений K1, K2, …, Kn имеется неразрешимоепредложение.Доказательство. Случай n = 2 доказан в теореме 3a. При n > 2 по лемме 5 по-лучаем логическую эквивалентность утверждений:|- K1 d |- ¬ K2,|- K2 d |- ¬ K3,…|- Kn-1 d |- ¬ Kn,|- Kn d |- K1.И так же, как и ранее, разбиваем эти эквивалентности, за исключением первойи последней, на подряд идущие пары. Предполагаем, что все формулы K3, K4, …,Kn разрешимы, тогда получаем цепь|- K2 d |- K4 d … d |- Kn.Отсюда следует |- K2 d |- Kn d |- K1. Получили отношения: одновременноимеем |- K2 d |- K1 и |- K1 d |- ¬K2. Полученный результат не будет противоре-чием, если формула K2 неразрешима. А если это не так, то среди формул K3, K4,…, Kn имеется неразрешимая формула. Теорема 7b. Рассмотрим предложения с косвенной самоссылочностью:M1: «Предложение M2 опровержимо»;M2: «Предложение M3 опровержимо»;…Mn- 1: «Предложение Mn опровержимо»;Mn: «Предложение M1 неопровержимо».Если n четно, то среди предложений M1, M2, …, Mn имеется неразрешимоепредложение.Доказательство. Случай n = 2 доказан в теореме 3b. При этом неразрешимымпредложением будет M1.При n>2 по лемме 5 получаем логическую эквивалентность утверждений:|- M1 d |- ¬M2,|- M2 d |- ¬M3,…|- Mn-1 d |- ¬Mn,Неразрешимые косвенно рефлексивные предложения 31|- ¬Mn d |- ¬M1.Разбиваем эти эквивалентности, за исключением первой и последней, на под-ряд идущие пары. Предполагая, что все формулы M3, M4, …, Mn разрешимы, по-лучаем цепь |- M2 d |- M4 d … d |- Mn. Отсюда следует |- M2 d |- Mn. Применимлемму 7 к данной и последней эквивалентности |- ¬Mn d |- ¬M1. Предполагая,что формулы M2 и Mn разрешимы, получаем |- ¬M2 d |- ¬M1.Полученный результат вместе с первой эквивалентностью |- M1 d |- ¬M2 небудет противоречием, если формула M1 неразрешима. А если это не так, то средиформул M2, M3, …, Mn имеется неразрешимая формула. Теорема 8a. Рассмотрим предложения с косвенной самоссылочностью:N1: «Предложение N2 недоказуемо»;N2: «Предложение N3 недоказуемо»;…Nn-1: «Предложение Nn недоказуемо»;Nn: «Предложение N1 опровержимо».Если n нечетно, то среди предложений N1, N2, …, Nn имеется неразрешимоепредложение.Доказательство. Условие теоремы означает, что множество формул {N1, N2,…, Nn} обладает следующими свойствами:|- N1 ~ ¬P(⎡N2⎤),|- N2 ~ ¬P(⎡N3⎤),…|- Nn-1 ~ ¬P(⎡Nn⎤),|- Nn ~ R(⎡N1⎤).Случай n = 1 доказан в теореме 2b, в этом случае неразрешимой является фор-мула N1. Поэтому будем предполагать, что n…3. По леммам 4(B) и 5(A) имеем ло-гическую эквивалентность утверждений:|- ¬ N1 d |- N2,|- ¬ N2 d |- N3,…|- Nn-1 d |- Nn,|- Nn d |- ¬N1.Множество первых n-1 эквивалентностей разобьем на подряд идущие парывида|- ¬ Ni d |- Ni+1,|- ¬ Ni+1 d |- Ni+2.Пусть в каждой такой паре формулы Ni+1 и Ni+2 разрешимы, тогда по лемме 7имеем |- Ni d |- Ni+2. Когда i пробегает нечетные значения 1, 3, …, n-2, получаемцепь |- N1 d |- N3 d … d |- Nn. Учитывая последнюю эквивалентность, получаем|- N1 d |- Nn d |- ¬N1. Полученный результат не будет противоречием, если фор-мула N1 неразрешима. А если это не так, то среди формул N2, N3, …, Nn имеетсянеразрешимая формула. Теорема 8b. Рассмотрим предложения с косвенной самоссылочностью:O1: «Предложение O2 опровержимо»;O2: «Предложение O3 опровержимо»;…On-1: «Предложение On опровержимо»;On: «Предложение O1 недоказуемо».32 В.М. ЗюзьковЕсли n нечетно, то среди предложений O1, O 2, …, On имеется неразрешимоепредложение.Доказательство. Условие теоремы означает, что множество формул {O1, O2,…, On} обладает следующими свойствами:|- O1 ~ R(⎡O2⎤),|- O2 ~ R(⎡O3⎤),…|- On-1 ~ R(⎡On⎤),|- On ~ ¬P(⎡O1⎤).Случай n = 1 доказан в теореме 2a, в этом случае неразрешимой является фор-мула O1. Поэтому будем предполагать, что n…3. По леммам 5(A) и 4(B) имеем ло-гическую эквивалентность утверждений:|- O1 d |- ¬O2,|- O2 d |- ¬O3,…|- On-1 d |- ¬On,|- ¬On d |- O1.Множество первых n-1 эквивалентностей разобьем на подряд идущие парывида|- Oi d |- ¬Oi+1,|- Oi+1 d |- ¬Oi+2.Пусть в каждой такой паре формулы Oi+1 и Oi+2 разрешимы, тогда по лемме 6имеем |- Oi d |- Oi+2. Когда i пробегает нечетные значения 1, 3, …, n-2, получаемцепь |- O1 d |- O3 d … d |- On. Учитывая последнюю эквивалентность, получаем|- On d |- O1 d |- ¬On. Полученный результат не будет противоречием, если фор-мула On неразрешима. А если это не так, то среди формул O2, O3, …, On-1 имеетсянеразрешимая формула. Рассмотрим теперь связь неразрешимых предложений с парадоксами. Дока-занные теоремы при нумерации разбиты на пары. Теоремы с одинаковыми номе-рами, но отличающиеся буквами a или b, аналогичны по доказательству. Но у нихесть и аналогия в формулировках теорем. Переформулируем все теоремы от 2a до8b следующим образом. Заменим в условиях теорем слова доказуемо и неопро-вержимо словом истинно, а слова опровержимо и недоказуемо словом ложно.Заключением теорем теперь при прежних ограничениях на количество предложе-ний n будет утверждение, что соответствующие предложения образуют парадокс.То, что при такой замене действительно получаются парадоксы, легко проверить(конечно, теперь мы не проводим рассуждение в рамках какой-либо формальнойсистемы).Так, теоремы 2a и 2b дают парадокс лжеца:A: «Предложение A ложно».Теоремы 3a и 3b при n = 2 приводят к парадоксу о Сократе и Платоне:Сократ: «То, что сказал Платон, есть ложь»,Платон: «Сократ говорит только правду».Теоремы 4a и 4b при n = 3 приводят к парадоксу Альберта Саксонского:Q1: «Предложение Q2 ложно»;Q2: «Предложение Q3 ложно»;Q3: «Предложение Q1 ложно».Неразрешимые косвенно рефлексивные предложения 33Таким образом, теоремы из каждой пары при указанной выше нумерации даютодин и тот же парадокс. Но всего получаем 4 различных парадокса. При n = 1имеем парадокс лжеца. А при n > 1 оставшиеся 6 пар теорем приводят только ктрем различным парадоксам (пары 3 и 5 дают одинаковый парадокс, пары 4 и 8дают одинаковый парадокс и, наконец, пары 6 и 7 дают одинаковый парадокс).

Скачать электронную версию публикации