<<

§1. Семантика неопределенности

В предыдущей главе с содержательной точки зрения были проанализированы рассуждения в условиях неопределенности, связанной с течением времени и, в частности, с изменением свойств предикации в отношении объектов и событий прошлого.

На самом деле неопределенность такого рода возникает в более обширном классе ситуаций. В заключительной главе, которая носит технический характер, мы построим формальную семантическую теорию неопределенности и продемонстрируем аксиоматизируемость свойства «быть общезначимой формулой» в этой семантике.

Пусть L — язык исчисления предикатов первого порядка произвольной сигнатуры, не содержащий функциональных констант148 . Будем обозначать символом Lh язык, отличающийся от L лишь наличием формул вида нА, где «н» — новый одноместный логический оператор.

Структурой для языка Lh назовем пару Мн=(и,{Рі} іє J), где J — множество индексов, такую, что:

а) |J| gt; 1;

б) Fi^Fj, если Щ;

в) каждое Мі=(и, Fi) является структурой149 для языка L;

г) если с — индивидная константа, то Fi^^Fj^) для всех j J.

Областью определения всех функций интерпретации Fi (іє J) является множество дескриптивных символов языка Lh, а области значений различаются для каждой функции. Неформально говоря, структура для языка Lh — это не менее, чем двухэлементное множество стандартных структур для языка L, имеющих один и тот же универсум и отличающихся друг от друга интерпретацией хотя бы одного предикатного (но не индивидного) символа языка L.

Оценка f определяется обычным образом: это отображение множества индивидных переменных языка L в универсум U. Если А — формула языка L, то определение выполнимости А в структуре (U, Fi) при оценке f стандартное. Расширим его на случай формул вида нА: формула нА выполнена в структуре (U, Fi) при оценке f, если существуют j,k є J такие, что А выполнена в (U, Fj) при ^ А не выполнена в (U, Fk) при f.

Формула А в структуре Мі = (U, Fi) принимает значение 1 (0), если А (не) выполнена в Мі при любых f.

Каждую структуру Мі = (U, Fi) из структуры Мн = (U, {Fi} іє J) будем называть возможным миром из Мн, поскольку эти структуры попарно отличаются интерпретацией хотя бы одной предикатной (но не индивидной) константы.

Формула А в структуре Мн=(и,^і} iєJ) принимает значение 1 (0), если А принимает значение 1 (0) в каждом из возможных миров; если же А принимает значение 1 в одних возможных мирах и значение 0 во всех остальных возможных мирах, то А принимает значение 1/0 в Мн. Значение 1 отождествляется с истинностью, значение 0 — с ложностью, а значение 1/0 — с неопределенностью.

Иначе говоря, в структуре Мн = (U, {Fi} іє J) формула А истинна (принимает значение 1), если для всех іє J А истинна (принимает значение 1) в (U,Fi); Аложна (принимает значение 0), если для всех іє J А ложна (принимает значение 0) в (U,Fi); наконец, А неопределенна (принимает значение 1/0), если существуют j,k є J такие, что А истинна (принимает значение 1) в (U, Fj) и А ложна (принимает значение 0) в (U, Fk), и при этом для каждого іє J либо А истинна (принимает значение 1) в (U,Fi), либо А ложна (принимает значение 0) в (U,Fi).

Пусть Т — множество формул языка Ьн и Мн — структура для Ьн. Назовем Мн моделью Т, если все формулы из Т истинны в Мн. Если Т одноэлементное множество, будем говорить о модели соответствующей формулы.

В классической логике введение новых предикатных констант в исходный язык L не расширяет существенным образом класс моделей для формулы А языка L: если LcL' и М'= (U, F) — структура для L', являющаяся моделью А, то пара М = (U, F), полученная сужением функции F' на L, будет структурой для языка L в том же самом универсуме U, также являющейся моделью А. В построенной н-семантике ситуация иная. Пусть, например, язык Lh содержит единственную одноместную предикатную константу Р, а L'h, наряду с Р, одноместную предикатную константу Q (так что Lh c L'h).

Положим U={u}, F'0(P)=U, F'1(P)=U, F'0(Q)=U, F'1(Q) =0. Пара М'н=(U,{F'i} іє{0,1}) будет структурой для L'h и моделью формулы Р(х). Однако сужение Fi интерпретации F'i на Lh ни к чему хорошему не приведет: пара Мн^^^і} іє {0,1}) не только не будет моделью формулы Р(х), но даже не будет структурой для языка Lh, поскольку в любой структуре Мн для Lh с одноэлементным универсумом U в силу пункта (б) определения структуры интерпретация единственного предикатного символа Р должна быть разной в разных мирах. Но для этого есть лить две возможности: либо Р = U, либо Р = 0. В первом случае формула Р(х) будет выполнена при любой оценке f, во втором — не выполнена при всех f. Поэтому формула Р(х) примет значение 1/0 в любой структуре Мн для Ьн с одноэлементным универсумом U.

Отмеченное обстоятельство заставляет принимать во внимание не только язык, на котором записана некоторая формула, но и расширения этого языка. Заметим также, что подобно тому, как формула со свободными переменными может не быть ни истинной, ни ложной в классической структуре М, такая формула может не быть ни истинной, ни ложной, ни неопределенной в структуре Мн. Однако для замкнутых формул150 гарантировано определенное истинностное значение в любых структурах, содержащих интерпретацию соответствующих дескриптивных символов.

Предложение 1. Если А — замкнутая формула языка Ьн, Ьн с Ь’н и Мн — структура для Ь’н, то А принимает в Мн только одно из трех значений: либо значение 1, либо значение 0, либо значение 1/0.

Доказательство очевидным образом вытекает из определений. В самом деле, индуктивное определение выполнимости формулы А в структуре (U, Fi) при оценке f позволяет однозначным образом решить вопрос о выполнимости формул любого вида в каждом из возможных миров. Для предложения А в силу тех же причин, что и в случае классической логики, выполнимость в мире w либо будет иметь место для всех оценок (тогда A будет истинно в w), либо ни для одной из них (тогда A будет ложно в w). Остается посмотреть, будет ли предложение A истинно во всех возможных мирах, ложно в каждом из них, либо же окажется в одних мирах истинным, а в других — ложным.

Предложение 1 показывает, что мы не нуждаемся в понятии выполнимости в структуре Мн для определения истинностных значений замкнутых формул.

Будем называть логическую связку табличной, если она может быть представлена функцией из {0, 1/0, 1} в {0, 1/0, 1}.

Предложение 2. а) унарные связки — и н табличны; б) бинарные связки не табличны.

а)              Пусть А и В — формулы языка Ьн, принимающие одно из трех истинностных значений в Мн, являющейся структурой для Ьн. Покажем, что связки — и н могут быть представлены следующими табличными функциями.

А —А нА
1 0 0
1/0 1/0 1
0 1 0

Действительно, если А приняла в Мн значение 1 (0), то А истинна (ложна) в каждом из возможных миров. Тогда ее отрицание —А будет ложно (истинно) в каждом из миров и —А получит значение 0 (1) в Мн. Если А имеет в Мн значение 1/0, то А истинна в одних возможных мирах и ложна во всех других. Следовательно, —А будет ложна в первых мирах и истинна во вторых, откуда в Мн —А примет значение 1/0.

Если А приняла в Мн значение 1 или 0, то А в каждом из возможных миров примет одно и то же истинностное значение: либо 1, либо 0. Стало быть, при всех оценках f не существуют j,k є J такие, что А выполнена в (U, Fj) при ^ Ане выполнена в (U, Fk) при f — и формула нА не будет выполнена ни в одном из возможных миров при всех f, то есть будет ложной в каждом из миров и тем самым окажется ложной в Мн. Если же А истинна в одних мирах и ложна во всех других, то формула нА будет выполнена в каждом из миров при всех оценках f, то есть окажется истинной в Мн.

б). Возьмем предложения Р(а) и Р(Ъ), где а и Ъ — индивидные константы. Рассмотрим структуру Мн = (U, {F1, F2}) и структуру М'н = (U, {F1, F }), где U = {1, 2}, Ц(Р) = F^Р) = {1}, F^) = F^) = {2}, F1(a) = F2(b) = 1 (так как индивидные константы по определению интерпретируются одинаково во всех возможных мирах, из последнего равенства сразу следует, что F1(b) = F2(a) = 1), F' 1(а) = 1, F' 2(b) = 2 (вновь отсюда получаем F' 1(Ъ) = 2, F' 2(а) = 1).

Вычислим истинностное значение предложений Р(а) и Р(Ъ) в Мн. В мире (U, F1) формула Р(а) истинна, поскольку F1(a) є F 1(Р), но в мире (U, F2) Р(а) ложна, так как F2(a) g F2^). Следовательно, Р(а) принимает значение 1/0 в Мн. Аналогичным путем убеждаемся, что Р(Ъ) принимает значение 1/0в Мн: F1(b) є F 1(Р), F2(b) g Р2(Р).

Дизъюнкция Рф) v Р(Ъ) истинна в (U, F1), поскольку Р(a) истинна. Но в (U, F2) формула Р(а) v Р(Ъ) ложна ввиду ложности и Р(а), и Р(Ъ). Отсюда получаем, что истинностное значение формулы Р(а) v Р(Ъ) в структуре Мн равно 1/0.

Истинностное значение предложений Р(а) и Р(Ъ) в М'н вновь оказывается равным 1/0, так как F' 1(a) є F' 1(Р), F' 2(a) g F' 2(Р) и F' 1(b) g F' 1(Р), F' 2(b) є F' 2(Р). Проверим истинностное значение дизъюнкции Р(а) v P(b) в структуре М'н. Р(а) v P(b) истинна в мире (U, F' 1), так как Р(а) истинна в (U, F' 1). Далее, Р(а) v P(b) истинна в мире (U, F' 2), так как P(b) истинна в нем. Следовательно, дизъюнкция Р(а) v P(b) принимает в М' н значение 1.

Таким образом, зная о том, что значение А равно 1/0 и значение В равно 1/0, невозможно в общем случае ответить на вопрос об истинностном значении дизъюнкции А v В, так что оператор дизъюнкции v не является табличным. Аналогичным образом, подбирая простые структуры, можно показать, что остальные бинарные булевы связки также не являются табличными. В этом одно из отличий предлагаемой семантики от обычных семантических конструкций для модальных логик, в которых все булевы связки табличны.

Пусть # — произвольная (возможно, пустая) комбинация знаков —, н и кванторов.

Предложение 3. Для каждой оценки f формула вида #нВ языка Ьн либо выполнена во всех мирах при f, либо не выполнена во всех мирах при f в любой структуре Мн для языка Ь' н такого, что Ьн с Ь'н.

Из определений вытекает, что если формула нВ выполнена в структуре (U, Fi) при оценке f, то для любого j є J формула нВ будет выполнена в структуре (U, Fj) при f. И наоборот, если нВ не выполнена в структуре (U, Fi) при оценке f, то для любого j є J формула нВ не будет выполнена в структуре (U, Fj) при f. Отсюда если формула нВ (не) выполнена хотя бы в одной структуре при всех оценках f, то она (не) будет выполнена во всех структурах при всех f. Таким образом, формула вида нВ либо выполнена во всех мирах при оценке f, либо не выполнена во всех мирах при f, какова бы ни была оценка f. Покажем, что навешивание на нВ отрицаний, знаков неопределенности и кванторов сохраняет свойство формулы выполняться или не выполняться во всех мирах. Рассмотрим формулу #нВ в предположении, что формула _#hB, где через _# обозначена последовательность, получающаяся из комбинации # стиранием ее левого знака (если таковой имеется), обладает требуемым свойством.

Навешивание отрицания на _#нВ изменит «знак» выполнимости _#нВ на противоположный, но также во всех мирах. Предположим, введение квантора всеобщности привело к тому, что формула Ух_#нВ выполнена в мире v при ^ не выполнена в мире w при f. Это означает, что формула _#нВ выполнена в v при любой оценке, отличающейся от f самое большее значением на х, и не выполнена в w при некоторой оценке g, также отличающейся от f самое большее значением на х. Тогда _#нВ выполнена в v при g и не выполнена в w при g, в противоречии с допущением индукции. Рассмотрим формулу Зх_#нВ. Допустим, что она выполнена в мире v при ^ не выполнена в мире w при f. Следовательно, существует оценка g, отличающаяся от f самое большее значением на х, такая, что _#нВ выполнена в v при g, и не существует оценки, отличающейся от f самое большее значением на х, которая выполняла бы _#нВ в w, что вновь противоречит индуктивному допущению. Отсюда вытекает, что формула вида Кх_#нВ (где К есть либо У, либо З) сохраняет свойство выполняться или не выполняться во всех мирах. Остался случай формулы вида н_#нВ, но он сводится к базисному: пусть С есть _#нВ, и тогда н_#нВ есть просто нС.

Таким образом, при любой оценке f формула вида #нВ либо выполняется во всех мирах, либо не выполняется во всех мирах.

Следствие. Если все предикатные символы формулы В находятся в области действия оператора н, то любая формула вида н#В является ложной в каждой структуре Мн для языка L'h такого, что Lh c L'h.

Рассмотрим формулу #В, все предикатные символы которой находятся в области действия по крайней мере одного оператора н. Значит, #В можно представить в виде булевой комбинации подформул типа #1нС1, #2нС2,..., #пнСп, каждая из которых, по только что доказанному, либо выполняется во всех мирах, либо не выполняется во всех мирах. Отсюда и #В либо выполняется во всех мирах, либо не выполняется во всех мирах при любой оценке f. Поэтому формула н#В окажется ложной во всякой структуре Мн.

В частности, любая формула языка Lh вида н#нВ является ложной в каждой структуре Мн для языка L'h такого, что Lh с L'h. Иными словами, комбинация двух и более операторов «и», с возможно находящимися между ними знаками отрицания или кванторами, ведет себя как оператор ложности.

Назовем формулу А языка Lh L'H-общезначимой, если А принимает значение 1 во всех структурах Мн языка Lh. Назовем формулу А языка Lh н-общезначимой, если каков бы ни был язык L'h такой, что Lh с L'h, А принимает значение 1 во всех структурах Мн языка L'h.

В классической логике, если формула А языка L принимает значение 1 во всех структурах этого языка, то А принимает значение 1 и во всех структурах любого языка L' такого, что L c L'.

Поэтому разницы между L-общезначимостью и общезначимостью в классической логике нет. В рассматриваемой н-семантике положение сложнее. Разумеется, каждая н-общезначимая формула является и LH-общезначимой, однако не наоборот.

Предложение 4. Существуют Lh-общезначимые, но не н-об- щезначимые формулы.

Пусть, например, Lh содержит одноместный предикатный символ Р и не имеет других предикатных констант. Тогда в любой структуре Мн языка Lh формула ЗхнР(х) будет принимать значение 1, то есть будет LH-общезначимой, так как в силу пунктов (а) и (б) определения структуры для языка Lh хотя бы один предикатный символ должен быть проинтерпретирован по-разному в каждой структуре этого языка. Но в данном случае предикат Р единственный, поэтому он получит различные интерпретации в любом из возможных миров в каждой структуре Мн рассматриваемого языка Lh. Следовательно, найдется индивид u из универсума структуры такой, что u обладает свойством Р в некотором мире и не обладает этим свойством в каком-либо другом мире. В соответствии с определениями это означает, что формула ЗхнР(х) будет истина во всех структурах Мн языка Lh, то есть будет LH-общезначимой. Но она не является н-общезначимой. Например, в структуре Мн=Ш, {F1, F2}) для языка L'h = {Р, Q} такой, что F1(Q) ф F2(Q), но F^) = F2^), предложение ЗхнР(х) оказывается ложным.

Аналогичным образом для любого языка Lh, содержащего лить конечное число предикатных символов {Р1, Р2,..., Рт} формула Зх1Зх2... Зхп1нР1(х1, х2,..., хп1) v Зх1Зх2... Зхп2нР2(х1, х2,..., хп2) v... v Зх1Зх2... ЗхптнРт(х1, х2,..., хпт) (где значение ni соответствует количеству мест у предиката Р.) будет LH-общезначимой. Содержательный смысл этой формулы заключается в указании на то, что по крайней мере какой-либо один предикат должен быть проинтерпретирован неоднозначно (или, как мы предпочитаем говорить, неопределенным образом) в каждой структуре Мн языка Lh. И вновь формула Зх1Зх2... Зхп1 нР1(х1, х2,..., хп1) v Зх1Зх2... Зхп2нР2(х1, х2,..., х.) v... v Зх,Зх,... Зх нР (х, х,..., х ) не обязанабыть истинной в

п27              1              2              пт mv 1’ z’ ’ пт7

структуре Мн для языка L’ = {Р1, Р2,..., Рт+1}. Зато Ь’н-общезначи- мой будет формула Зх1Зх2... Зхп1нР1(х1, х2,..., хп1) v Зх1Зх2... Зхп2нР2(х1, х,..., х ,) v... v Зх Зх... Зх нР (х, х,..., х ) v Зх Зх...

2* ’ п27              12              пт т4- 1’ 2’ ’ пт              1              2

Зх Зх ,,нР ,,(х, х,..., х , х ,,), которая снова не является н-

пт пт+1 т+1ч 1’ 2’ ’ пт пт+17’              ^

общезначимой.

Между тем н-общезначимые формулы в рассматриваемой семантике существуют, как это вытекает из следующего утверждения.

Предложение 5. Множество Ьн-общезначимых формул является консервативным расширением множества общезначимых формул языка Ь.

Общезначимая формула языка Ь — это общезначимая формула классической логики предикатов. Связки «н» она не содержит. В любой структуре М = (U, F) для языка Ь', если Ь с Ь', такая формула истинна. Стало быть, общезначимая формула языка Ь будет истинна в каждой структуре Мі=(^ Fi) для языка Ь' из структуры HH=(U,{Fi} іє J) для языка Ь'н (см. пункт (в) определения структуры), причем Ьн с Ь'н. Таким образом, всякая общезначимая формула языка Ь является н-общезначимой формулой языка Ьн и тем более Ьн-общезначимой (поскольку, как было отмечено выше, класс н-общезначимых формул языка Ьн содержится в классе Ьн- общезначимых формул). Следовательно, мы имеем дело с расширением класса общезначимых формул языка Ь.

Покажем теперь, что это расширение консервативно. Допустим, напротив, что формула А языка Ь Ьн-общезначима, но не общезначима в смысле классической логики предикатов (это допущение уместно, поскольку А не содержит вхождений связки «н»). Тогда существует структура М=(^ F) и оценка f такие, что А не выполнена в М при f. Пусть, далее, Р — какой-либо предикатный символ, содержащийся в А. Построим структуру Мн^^ {F, F' }) для языка Ьн такую, что F совпадает с F' во всем, за исключением интерпретации предиката Р: F(P) a F' (P). В этой структуре формула А либо не выполнена в М=(^ F) при оценке f и выполнена в М'=(U, F') при f, либо не выполнена как в М=(^ F) при f, так и в М'=(U, F' ) при f. В любом случае формула А не примет значения 1 в структуре Мн для языка Ьн, что противоречит допущению о ее Ьн-общезначимости.

Следствие. Множество н-общезначимых формул языка Ьн является консервативным расширением множества общезначимых формул языка Ь.

Так как множество н-общезначимых формул является подмножеством множества Ьн-общезначимых формул, сформулированное утверждение немедленно следует из предложения 5.

Только что доказанное предложение и его следствие позволяют оставить привычное обозначение |=А для н-общезначимых формул, а через Ьн |=А будем обозначать Ьн-общезначимость формулы А.

По определению Ln-теория — это произвольное подмножество множества предложений языка Lh. Чтобы указать, что теория Т является LH-теорией в тех случаях, когда точная фиксация ее языка не существенна или очевидна, будем использовать запись «Тн» или выражение «н-теория».

LH-теории оказываются существенно неконструктивными (или антиконструктивными) в следующем смысле.

Предложение 6. Существует LH-теория Т такая, что а) (Рс v —Рс) є T, б) ЗхРх є T, в) T имеет модель; но LH-теории Ти{Ра}, Ти{ — Pa} не имеют моделей, какова бы ни была индивидная константа а є Lh.

Пусть Lh={P, с}, где Р — одноместный предикатный символ, а с — индивидная константа, и Мн=({а,Ъ}, {Fi} і є {0,1}), FAAFAAa, F0(P)={a}, F1(P)={b}. Ясно, что Мн — модель LH- теории Т={(Рс v —Рс), ЗхРх, УхнРх}. Но ни Ти{Рс}, ни Tu{—Рс} моделей не имеют, как бы мы ни определяли значение Fi(^ в произвольной структуре Мн для языка Lh.

Действительно, истинность предложения УхнРх в модели Мн^^^і} іє J) теории Т влечет, что УхнРх выполнена в Мі=(^ Fi) для каждого іє J при всех оценках f. Но выполненность УхнРх в Мі=(^ Fi) при всех f означает, что нР(х) выполнено в Мі=(^ Fi) при всех f. Следовательно, при любой оценке f найдутся j,k є J такие, что формула Р(х) выполнена в (U, Fj) при f и Р(х) не выполнена в (U, Fk) при f. Отсюда получаем, что какова бы ни была интерпретация индивидной константы с, найдутся индексы j,k, для которых предложение Р(с) будет выполнено в (U, Fj) и не выполнено в (U, Fk), то есть Р(с) будет истинно в (U, Fj) и ложно в (U, Fk). Значит, в любой модели теории Т истинным будет предложение нР(с), а предложение Р(с) получит неопределенную оценку 1/0. Таккакдлявсякого Аоценка 1/0влечетпринягиезначения 1/0 и для —А, ясно, что предложение —Р(с) также не может быть истинным ни в какой модели теории Т, что и требовалось доказать.

Предложение 7. Существует LH-теория Т, не имеющая модели, тогда как каждое ее собственное подмножество имеет модель.

Пусть алфавит языка Lh не содержит других предикатных символов, кроме Р1, Р2,..., Рп, и пусть Т={УхР1х, УхР2х,..., УхРпх}. Тогда Т — искомая теория. В самом деле, каждое предложение УхРк будет истинным в возможном мире jє J в том и только в том случае, если интерпретация F^P) совпадает с универсумом модели U. Но пункт (б) определения структуры требует, чтобы для любых двух различных возможных миров v и w произвольной структуры Мн языка Ьн нашелся по крайней мере один предикатный символ, интерпретация которого в мире v отличалась бы от его интерпретации в мире w. Следовательно, для некоторого i будет либо Fv(Pj) = U и Fw(Pj) a U, либо Fv(P) a U и Fw(P) = U, либо (что возможно при |U| gt; 1) Fv(Pj) a U и Fw(P) a U. В первом случае предложение VxPx будет ложным в мире w, во втором в мире v, а в третьем — и в v, и в w. Значит, в любом случае VxPx не будет истинным в рассматриваемой структуре Мн. Теперь удалим какое-нибудь конкретное предложение VxPkx из теории Т. Полученная теория Т' уже имеет модель. Возьмем непустое множество U и положим М'н = (U,{F0,F1}), причем для всех i F0(Pj) = U, но F1(Pi) = U только в том случае, если iAk. А F1(Pk) пусть равно 0. Очевидно, что построенная структура М'н языка Ьн является моделью теории Т': все предложения VxP^x, кроме VxPkx, будут истинны в М' н, а это в точности все предложения из Т'.

Таким образом, теорема компактности не верна для рассматриваемой семантики. В доказательстве данного факта использовалось свойство формул вида VxPx иметь не более одной модели (в смысле классической теории моделей) в каждом универсуме. Уточним сказанное. Назовем формулу А языка Ь классического исчисления предикатов абсолютно категоричной, если а) теория {А} имеет модель; б) для любых двух структур М^^^) и М2=^^) языка Ь таких, что FaG, либо А ложно и в М1, и в М2, либо А истинно в точности в одной из этих структур.

Пусть язык Ь классического исчисления предикатов первого порядка содержит двухместный предикатный символ R и не содержит других предикатных и функциональных символов и индивидных констант. Тогда верен следующий факт.

Предложение 8. Множество абсолютно категоричных замкнутых формул языка Ь неразрешимо151.

Возьмем произвольное множество формул Г языка Ьн и формулу А этого же языка. Если для любой структуры Мн языка Ьн и любой оценки f выполнимость всех формул из Г в каждом возможном мире из Мн при f влечет, что А также выполнена в каждом возможном мире из Мн при f, то А будем называть следствием Г (или говорить, что из Г следует А) и использовать привычную запись Г |=А. Применительно к теориям это означает, что формула А следует из Ьн-теории Т языка Ьн, если А принимает значение 1 во всех моделях теории Т.

Вновь в соответствии с обычной практикой будем рассматривать записи вида Т |— А как указание на то, что существует (в некотором исчислении) конечная последовательность формул, называемая выводом формулы А в теории Т. В классической логике предикатов первого порядка имеет место следующая теорема: если Т |= A, то Т |— А. Имея в виду финитное отношение выводимости, будем говорить, что отношение выводимости |— формализует отношение логического следования |=, если верна упомянутая теорема.

Предложение 9. Определенное в н-семантике отношение логического следования 1= не формализуемо.

Докажем это утверждение. Рассмотрим язык L0, содержащий только следующие одноместные предикатные символы: Р0, Р1,..., Рп,... И язык L1, который содержит только двухместный предикатный символ R. Пусть оба языка не содержат других символов, кроме указанных, а также классических логических связок, кванторов, индивидных переменных и технических символов. Положим Lh = L0 uL1 и {н}. Построим в языке Lh теорию Т следующего вида: УхР0х о А0,

УхР1х о А1,

УхР2х о А2,

УхР x о А ,

пп

где все формулы Аі сформулированы в языке L1. Отметим, что хотя в действительности теория Т содержит только формулы классического исчисления предикатов первого порядка, мы считаем ее LH-теорией и будем пытаться строить для Т соответствующие неклассические модели. Для LH-теории Т возможны три исхода: а) Т не имеет модели; б) Т имеет модель и для всех i,j за единственным исключением k выполняется АоА^ в) остальные случаи, которые не представляют для нас интереса.

Покажем, что исходы (а) и (б) возможны. Для первой ситуации просто: если каждая формула Аі логически общезначима, то мы имеем дело с уже рассматривавшимся случаем (см. утверждение о некомпактности).

Пусть теперь все формулы Аі общезначимы за исключением одной формулы Ак, которая ложна в бесконечном универсуме при некоторой интерпретации F. Возьмем бесконечный универсум U. Так как модель для Т должна быть Мн-структурой, осуществим «раздвоение» интерпретации F на F1 и F2 следующим образом.

Пусть F(R)=F1(R)=F2(R). Истинность эквивалентностей УхРк о А при iфk обеспечить несложно: достаточно проинтерпретировать предикатный символ Р на всем универсуме U, приняв равенство F^P^F^P^U. Рассмотрим теперь эквивалентность УхРкх о Ак. Положим F^P^C и F^^'y^U, VcU, УфС. Структура Мн=(U, {F1,F2}) будет моделью теории Т.

В самом деле, УхРк истинно как в (U, F1), так и в (U, F2) для iфk. Точно так же А истинно и в (U, F1), и в (U, F2), поскольку А логически общезначима. Следовательно, для iфk истинна эквивалентность УхРк о А.

Рассмотрим теперь оставшуюся эквивалентность УхРкх оАк. По построению формула Ак ложна как в (U, F1), так и в (U, F2). Точно так же УхРкх ложна и в (U, F1), и в (U, F2), откуда истинна эквивалентность УхРкх оАк.

Таким образом, Мн является моделью теории Т. В этой модели истинна формула ЗхнРкх, поскольку в (U, F1) формула ЗхРкх ложна, тогда как в (U, F2) она истинна. Более того, ЗхнРкх истинна во всякой модели (U, {Fi} іє J) LH-теории Т, поскольку только лишь для предикатного символа Рк возможна различная интерпретация в (U, Fi) и (U, Fj) при некоторых ^J (какова бы ни была мощность множества индексов J), необходимая для построения модели. Но различная интерпретация приводит к неопределенности по крайней мере для одного индивида а є U: найдутся i,j є J такие, что либо а є Fi(PJ и а g Fj(PJ, либо, наоборот, а g Fi(PJ и а є Fj(PJ, что влечет истинность формулы ЗхнРкх.

Получаем, таким образом, Т |= ЗхнРкх. При этом существенно, что все формулы А, кроме Ак, общезначимы. Ведь если заменить какую-нибудь формулу УхРх о А. при jфk на формулу УхРх о Ак, из получившейся теории т'предложение ЗхнРкх уже не слЄ- дует, как не следует и предложение ЗхнРх. Действительно, построенную выше модель для Т легко превратить в следующие две модели для Т'. Первая модель М1 получается из Мн заменой равенств F^P^V и F^P.^F^P^U на равенства F2(PJ=C и F^P.^C, F2(P.)=V, где Уф^ VcU, УфС. При этом сохраняется равенство F1(Pk)=C, так что формула ЗхнРкх окажется ложной в М1, но формула ЗхнРх будет истинной. Вторая модель М2 получается из Мн заменой равенств F1(P.)=F2(P.)=U на равенства F1(Pj)= F2(P.) =C. Теперь ЗхнР.х ложна, а ЗхнРкх истинна. Итак, если в моделях для Т лишь один предикат Рк должен был интерпретироваться неопределенным способом, то в моделях для Т' такую интерпретацию получают либо Pk, либо P., либо оба они вместе, откуда имеем следование Т' |= (3xHPkx v 3xhP.x).

Итак, чтобы убедиться в наличии следования Т |= 3xHPkx, необходимо установить, что имеется в точности одна необщезначимая формула Аг Однако построить за конечное число шагов вывод о том, что все формулы А, за исключением одной, являются общезначимыми, невозможно. Поэтому невозможно формализовать отношение логического следования: Т |= 3xHPkx не влечет Т |— 3xHPkx, каково бы ни было финитное отношение |—.

Аналогичным образом в случае (а) невозможно за конечное число шагов установить, что все формулы А логически общезначимы и, следовательно, что Ьн-теория Т не имеет моделей.

Оба последних факта отличаются от положения дел в классической логике предикатов первого порядка. Там Т |=A влечет Т |— A, т.е. логическое следование преобразуется в конечный вывод, и отсутствие модели у теории Т доказуемо за конечное число шагов (отсутствие модели в классике равнозначно противоречивости, а противоречие выводится за конечное число шагов, коль скоро оно имеется).

Итак, отношение логического следования в построенной н- семантике неформализуемо и эта семантика неполна относительно отношения выводимости.

Пусть П обозначает произвольную бинарную булеву связку. Тогда верно следующее утверждение.

Предложение 10. |=(н(А П В) ^ (нА v нВ)).

Предположим, н-общезначимости нет, то есть в некоторой структуре Мн формула н(А П В) выполнена при оценке f, а формула (нА v нВ) не выполнена в Мн при f. Отсюда ни нА, ни нВ не выполнены в Мн при f. Значит, Алибо выполнено во всех возможных мирах из Мн при f, либо не выполнено в каждом из миров при ґ,иВ также либо выполнено во всех возможных мирах из Мн при f, либо не выполнено в каждом из миров при f. Тогда булева комбинация (АП В) либо будет выполнена во всех мирах при f, либо не будет выполнена во всех мирах при f. В любом случае формула н(АП В) окажется не выполненной в Мн при f в противоречии с предположением.

<< |
Источник: Анисов А.М.. Темпоральный универсум и его познание. — М.,2000. — 208 с.. 2000

Еще по теме §1. Семантика неопределенности:

  1. Глава 9. Логика неопределенности
  2. §' 170. Неопределенные местоимения
  3. Диктатура «неопределенного субъекта»
  4. §1. Проблема временной неопределенности
  5. 8.3 Трансляционная и теоретико-модельная семантика
  6. РАЗДЕЛ 3. Неопределенность равновесия
  7. 8.4 Теоретико-игровая семантика Я.Хинтикки
  8. 19. Все более высокие — неопределенные.
  9. НЕ и НИ в отрицательных и неопределенных местоимениях и наречиях
  10. 8.2 Инструменталистская семантика (М.Даммит, Г.Кастаньеда)
  11. Неопределенность размеров новых состояний
  12. 8.1 Стандартная семантика Д.Дэвидсона
  13. Глава вторая ПОРОЖДЕНИЕ «ЗНАЧЕНИЯ». СИСТЕМАТИЧЕСКАЯ ГЕНЕАЛОГИЯ ИНДИЙСКОЙ СЕМАНТИКИ
  14. Три измерения знаковой теории. Синтактика, семантика и прагматика
  15. §2. Неэффективная вычислимость. Синтаксис и семантика языка ABT
  16. 3. Трактат «Нирукта»: узел семантико-этимологических проблем