Неподвижные точки во временных моделях

Алгебра и логика, 43, N 5 (2004), 589—602

УДК 510.64

НЕПОДВИЖНЫЕ ТОЧКИ ВО ВРЕМЕННЫХ МОДЕЛЯХ∗) С. И. МАРДАЕВ Введение

В статье исследуется определимость наименьших неподвижных точек во временной пропозициональной логике, другими словами, во временных моделях Крипке рассматриваются операторы, задаваемые формулами. Ранее был исследован интересный подкласс позитивных временных операторов, а именно позитивные Π-операторы [1]. Для таких операторов в линейных моделях были исследованы определимость одной формулой и определимость конечным числом формул. Условие линейности здесь естественно, так как линейные модели составляют важный класс моделей, а с другой стороны, легко построить примеры классов моделей с неопределимыми точками, в которых длины антицепей в классе не ограничены. Вопрос об определимости в линейных временных моделях наименьших неподвижных точек позитивных операторов оставался открытым. В настоящей работе дается отрицательный ответ на этот вопрос: строятся примеры, показывающие, что наименьшие неподвижные точки позитивных операторов могут быть не определимы в классе конечных линейно упорядоченных и классе конечных строго линейно упорядоченных временных моделей. Эти примеры указывают на различие модального и временного случаев. В модальном случае наименьшие неподвижные точки ∗)

Работа выполнена при финансовой поддержке Российского фонда фундаменталь-

ных исследований, проект N 03-06-80178. c Сибиpский фонд алгебpы и логики, 2004

590

С. И. Мардаев

позитивных операторов определимы в классах конечных частично упорядоченных [2] и строго частично упорядоченных моделей [3], более того, эти классы могут быть существенно расширены с сохранением определимости [4, 5]. Упомянутые примеры основаны на идее препятствия, которая помогает исследовать еще один вопрос: об определимости инфляционных неподвижных точек в модальном случае. Здесь будут построены примеры неопределимых инфляционных точек в классе конечных строго линейно упорядоченных моделей и в классе конечных линейно упорядоченных моделей. Известно, что выразительные силы логик, полученных расширением логики предикатов первого порядка оператором наименьших неподвижных точек и оператором инфляционных неподвижных точек, совпадают (для конечных моделей см. [6], общий случай — [7]). Логика, полученная из модальной добавлением оператора наименьшей неподвижной точки, также исследовалась — это µ-исчисление (заметим, что в этих случаях слово ”оператор“ обозначает оператор создания новых формул с соответствующей семантикой, а не оператор в модели). В [8, 9] введена логика MIC, получающаяся добавлением к модальной логике оператора инфляционной неподвижной точки. Интересен вопрос сравнения выразительных сил логики MIC и µ-исчисления. Там же показано, что MIC обладает большей выразительной силой. Сделано это указанием языка, определимого в MIC, но не определимого в µ-исчислении. В данной статье будут построены примеры, из которых следует, что MIC обладает большей выразительной силой как в классе конечных строго линейно упорядоченных моделей, так и в классе конечных линейно упорядоченных моделей: имеются подмножества в этих моделях, определимые в MIC, но не определимые в µ-исчислении, поскольку в этих классах можно элиминировать µ-оператор, а модальными формулами эти подмножества не определимы. Элиминация возможна из-за того, что наименьшие неподвижные точки позитивных операторов определимы в этих классах с сохранением позитивности параметров [4].

Неподвижные точки во временных моделях

591

Несмотря на полученный отрицательный ответ на общий вопрос об определимости наименьших неподвижных точек позитивных операторов в линейном временном случае, во второй части статьи будет указан еще один, кроме позитивных Π-операторов, подкласс класса временных позитивных операторов с хорошей определимостью наименьших неподвижных точек, а именно подкласс позитивных Σ-операторов. Также будет доказано, что наименьшие неподвижные точки временных позитивных Σоператоров определимы в транзитивных линейных моделях. Значит, для таких операторов определимость наименьших неподвижных точек ведет себя в линейном временном случае примерно так же, как и в общем модальном (в [10] доказано, что наименьшие неподвижные точки модальных позитивных Σ-операторов определимы в транзитивных моделях). Модальные и временные пропозициональные Σ-формулы названы так по аналогии с Σ-формулами из теоремы Р. Ганди [11] в теории допустимых множеств, утверждающей Σ-определимость наименьших неподвижных точек Σ-операторов. Временные формулы составляются из константы ⊥ (ложь) и пропозициональных переменных p, q, r, . . . с помощью бинарных ∧, ∨ и унарных ¬, L , R связок. Будут также использоваться унарные связки ♦L и ♦R , которые представляют собой сокращения соответственно для ¬L ¬ и ¬R ¬. Кроме того, будут применяться обозначения ♦· L α = α ∨ ♦L α, ♦· R α = α ∨ ♦R α, α ↔ β = (α → β) ∧ (β → α), ⊤ = ¬⊥. Временная шкала Крипке h W, R i состоит из непустого множества W и бинарного отношения R на W , временная модель Крипке h W, R, v i — из шкалы Крипке h W, R i и означивания v. Означивание v — это функция, которая каждой переменной q ставит в соответствие подмножество v(q) множества W , это подмножество v(q) называется значением переменной q. Значение переменной qi обозначим соответствующей прописной буквой Qi . Функция v естественным образом продолжается на формулы: константе ⊥ всегда соответствует пустое множество, связкам ¬, ∧, ∨ — дополнение, пересечение, объединение множеств, связкам L , R , ♦L и ♦R — следующие операции на множествах:

592

С. И. Мардаев L A = {x | ∀y(yRx ⇒ y ∈ A)}, R A = {x | ∀y(xRy ⇒ y ∈ A)}, ♦L A = {x | ∃y(yRx ∧ y ∈ A)}, ♦R A = {x | ∃y(xRy ∧ y ∈ A)}.

Значение формулы α(q1 , . . . , qn ) обозначим через α(Q1 , . . . , Qn ). Пусть дана формула ϕ(p, q1 , . . . , qn ) от переменных p, q1 , . . . , qn . Рассмотрим модель h W, R, v i, в которой заданы значения Q1 , . . . , Qn переменных q1 , . . . , qn , а значение переменной p не задано. Формула ϕ(p, q1 , . . . , qn ) определяет на модели h W, R, v i оператор Fϕ (P ) = ϕ(P, Q1 , . . . , Qn ), который каждому множеству P сопоставляет множество ϕ(P, Q1 , . . . , Qn ), т. е. переменной p придается значение P и рассматривается значение формулы ϕ при этом означивании. Такие операторы назовем формульными. Если каждое вхождение переменной p в формулу ϕ(p, q1 , . . . , qn ) позитивное, то эту формулу назовем позитивной по p, а оператор Fϕ — позитивным. Пусть имеется шкала h W, R i. Рассмотрим оператор F , не обязательно формульный, сопоставляющий каждому подмножеству A множества W некоторое подмножество F (A) множества W . Множество P называется неподвижной точкой оператора F , если P = F (P ). Неподвижная точка P оператора F называется наименьшей, если P ⊆P ′ для любой другой неподвижной точки P ′ этого оператора. Если неподвижная точка P совпадает в модели со значением некоторой формулы ω(q1 , . . . , qn ), то эта формула ω определяет неподвижную точку P в данной модели. Определяющая формула ω(q1 , . . . , qn ) сохраняет позитивность параметров, когда для любого параметра qi выполняется следующее условие: если все вхождения qi в ϕ(p, q1 , . . . , qn ) позитивные, то и все вхождения qi в ω(q1 , . . . , qn ) также позитивные. Рассмотрим шкалу h W, R i, оператор F и последовательность множеств P 0 = ∅, P k+1 = F (P k ). Определим последовательность формул ϕ0 (q1 , . . . , qn ) = ⊥, ϕk+1 (q1 , . . . , qn ) = ϕ(ϕk (q1 , . . . , qn ), q1 , . . . , qn ). Ясно, что для всех k множество P k является значением формулы ϕk . Если ϕ позитивна по p и P k = P k+1 для некоторого k (например, в конечной модели такое k всегда найдется), то P k является наименьшей неподвижной точкой оператора Fϕ и определяется формулой ϕk .

Неподвижные точки во временных моделях

b re b e r b e r

ppp

0 1 2 3 s s b r b e r b r b re

ppp

0 1 2 3

re b re b b r b r 2n − 1 2n + 2

ppp

s s r b re b r b r b r b 4n + 5 4n − 1

593

b r b r 4n

ppp

s b r b r 8n + 1

Рис. 1. Временные модели Отношение R на множестве W называется линейным, если для любых различных x, y ∈ W выполняется xRy или yRx. Если частичный порядок линеен, то называем его линейным; если строгий частичный порядок линеен, то называем его строгим линейным.

§ 1. Препятствия в линейных моделях Рассмотрим сначала линейные временные модели и покажем, что в них наименьшие неподвижные точки позитивных операторов могут быть не определимы. Рассмотрим формулу ϕ = q ∧ L L ♦· R p и конечные строго линейно упорядоченные модели 0 < 1 < . . . < 4n (верхняя модель на рис. 1). Значение q состоит из нечетных чисел от 1 до 2n − 1 и четных от 2n + 2 до 4n (отмечены черными кружками). Наименьшая неподвижная точка оператора Fϕ состоит из всех нечетных чисел от 1 до 2n − 1 (отмечены двойными кружками), т. е. она не может преодолеть препятствие из двух идущих подряд элементов 2n и 2n + 1, на которых q ложна. При этом числа подбираются так, что препятствие находится приблизительно посередине модели. Определим модальную глубину временной формулы md(⊥) = md(qi ) = 0, md(¬α) = md(α), md(α ∧ β) = md(α ∨ β) = max(md(α), md(β)), md(L α) = md(R α) = md(♦L α) = md(♦R α) = md(α) + 1. Не существует формулы α(q), определяющей эту точку во всех этих моделях, так как любая такая формула обладает следующим свойством:

594

С. И. Мардаев

пусть md(α(q)) = m, тогда значение формулы α(q) на всех i таких, что 2m 6 i 6 4n − 2m, совпадает со значением q, ¬q, ⊥ либо ⊤ (при этом n выбирается так, что препятствие содержится среди указанных i). Для линейно упорядоченного случая рассмотрим немного более сложную формулу ϕ = s ∧ L (L (L (L (♦R p ∨ ¬q) ∨ q) ∨ ¬q) ∨ q) и конечные линейно упорядоченные модели 0 < 1 < . . . < 8n + 1 (нижняя модель на рис. 1). Значение q состоит из всех нечетных чисел (отмечены черными кружками), значение s состоит из нечетных чисел, взятых через одно от 3 до 4n − 1 и от 4n + 5 до 8n + 1 (на рис. 1 над ними стоит буква s). Пропущенные в значении s два нечетных числа подряд образуют препятствие. Наименьшая неподвижная точка оператора Fϕ состоит из нечетных чисел, взятых через одно от 3 до 4n − 1 (отмечены двойными кружками). Не существует формулы α(q, s), определяющей эту точку во всех этих моделях, так как любая такая формула обладает следующим свойством: пусть md(α(q, s)) = m, тогда значение формулы α(q, s) на всех i таких, что 4m 6 i 6 (8n + 1) − 4m, совпадает со значением q, ¬q, s, ¬s, q ∧ ¬s, ¬q ∨ s, ⊥ либо ⊤. Идея препятствий может быть использована и в модальном случае для построения интересных примеров. В модальном случае вместо L и R используется одна связка , шкалы и модели определяются аналогично, связке  соответствует следующая операция на множествах: A = {x | ∀y(xRy ⇒ y ∈ A)}. Рассмотрим модель, произвольный, не обязательно монотонный оператор F и последовательность множеств P 0 = ∅, P α+1 = P α ∪ F (P α ), а S β P . Заметим, что та же последодля предельного α положим P α = β<α S F (P β ). Эта вательность получится, если для всех α положить P α = β<α

последовательность возрастающих множеств стабилизируется на некотором множестве, которое называется инфляционной неподвижной точкой оператора F . Если оператор F монотонный, то инфляционная точка совпадает с наименьшей неподвижной точкой. Рассмотрим формулу ϕ = (q ∧ p) ∨ (p ∧ ¬p) и конечные строго

Неподвижные точки во временных моделях

c

c

s

c

s

p p p

s

c

s

0 1 2 r s v u v u r s c s c s c s c s

c

595

s 2n

p p p

v u r s v u r s c s c s c s c s 4n − 1

0 1

Рис. 2. Модальные модели

линейно упорядоченные модели 0 < 1 < . . . < 2n (верхняя модель на рис. 2). Значение q состоит из всех четных чисел, кроме 0 (отмечены черными кружками). Инфляционная неподвижная точка состоит из всех элементов модели, кроме 0, т. е. она не может преодолеть препятствие из двух идущих подряд элементов 1 и 0, на которых q ложна. Не существует модальной формулы α(q), определяющей эту точку во всех этих моделях, так как любая такая формула обладает следующим свойством (модальная глубина модальной формулы определяется естественным способом): пусть md(α(q)) = m, тогда значение формулы α(q) на всех i таких, что i 6 2n − 2m, совпадает со значением q, ¬q, ⊥ либо ⊤ (при этом n берется такое, что препятствие содержится среди этих i). Более того, нет и определяющей µ-формулы, поскольку наименьшие неподвижные точки модальных позитивных операторов определимы с сохранением позитивности параметров в конечных строго частично упорядоченных моделях [3] и даже более широком классе моделей [4], поэтому µ-оператор элиминируется, т. е. каждая формула µ-исчисления эквивалентна в этих классах моделей формуле без µ-оператора. Для доказательства этого методом индукции проверяется следующее свойство: для любой переменной q если µ-формула позитивна по q, то эквивалентная ей модальная формула также позитивна по q; здесь используется сохранение позитивности параметров. Теперь рассмотрим формулу

596

С. И. Мардаев

ϕ = (s ∧ (p ∨ q)) ∨ (r ∧ ((p ∨ q) ∨ ¬q) ∧ ¬(p ∨ q)) ∨ (u ∧ (((p ∨ q) ∨ ¬q) ∨ q) ∧ ¬((p ∨ q) ∨ ¬q)) ∨ (v ∧ ((((p ∨ q) ∨ ¬q) ∨ q) ∨ ¬q) ∧ ¬(((p ∨ q) ∨ ¬q) ∨ q)) и конечные линейно упорядоченные модели 0 < 1 < . . . < 4n − 1 (нижняя модель на рис. 2). Значение q состоит из нечетных чисел (отмечены черными кружками). Сверху от элементов указана та из переменных s, r, u или v, которая истинна на этом элементе. На элементах от 4 до 4n − 1 истинность этих переменных идет в порядке v, u, r, s циклами по четыре элемента. Элементы 0, 1, 2, 3 образуют препятствие, поскольку на них порядок истинности другой: r, s, v, u. Инфляционная неподвижная точка состоит из всех элементов модели, кроме 0, 1, 2, 3. Не существует формулы α(q, s, r, u, v), определяющей эту точку во всех этих моделях, так как любая такая формула обладает следующим свойством. Пусть md(α) = m, тогда значение формулы α на всех i таких, что i 6 4n − 1 − 4m, совпадает со значением некоторой булевой комбинации переменных s, r, u и v. Таких комбинаций всего шестнадцать, включая ⊥ и ⊤. Поэтому либо для таких i в каждой идущей подряд четверке 4j, 4j + 1, 4j + 2, 4j + 3 содержится элемент, на котором α истинна, либо α ложна на всех таких i. Значит, α не определяет эту точку. При этом наименьшие неподвижные точки позитивных операторов определимы с сохранением позитивности параметров в конечных частично упорядоченных моделях [2] и более широком классе [4], поэтому µ-оператор также элиминируется.

§ 2. Временные Σ-операторы Временной Σ-формулой называем формулу, составленную с помощью связок ∧, ∨, ♦L , ♦R из формул, не содержащих модальных связок. Другими словами, пусть дана временная формула α(s1 , . . . , sn ), содержащая только связки ∧, ∨, ♦L , ♦R . Возьмем формулы β1 , . . . , βn , не содержащие модальных связок. Подставим эти формулы вместо переменных s1 , . . . , sn в формулу α. Получившаяся формула α(β1 , . . . , βn ) является Σ-формулой.

Неподвижные точки во временных моделях

597

Если формула ϕ(p, q1 , . . . , qn ) является Σ-формулой, то оператор Fϕ называем временным Σ-оператором. ТЕОРЕМА. Для каждого временного позитивного Σ-оператора Fϕ существует число m такое, что формула ϕm определяет наименьшую неподвижную точку оператора Fϕ в любой транзитивной линейной модели Крипке. ДОКАЗАТЕЛЬСТВО. В формуле ϕ вынесем дизъюнкции следующим образом. Рассмотрим вхождение ∨, участвующее в построении ϕ из формул, не содержащих ♦L и ♦R . Заметим, что в любой модели Крипке значения формул ♦L (α ∨ β) и ♦L α ∨ ♦L β совпадают. Аналогичное свойство выполняется для ♦R . Используя эти свойства и дистрибутивность, можно каждое такое вхождение ∨ вынести через ♦L , ♦R и ∧ наружу. Проделав это со всеми такими вхождениями ∨, получим эквивалентную исходной формулу ψ1 ∨ . . . ∨ ψk , где все дизъюнктивные слагаемые составлены с помощью связок ∧, ♦L и ♦R из формул, не содержащих ♦L и ♦R . Для каждого слагаемого ψs обозначим через αs конъюнкцию ее конъюнктивных слагаемых с главной связкой ♦L , через βs — конъюнкцию слагаемых, не содержащих ♦L и ♦R , через γs — конъюнкцию слагаемых с главной связкой ♦R . Если формул какого-то вида нет, то для единообразия обозначений положим αs , βs или γs равным ⊤. Таким образом, формула ϕ преобразована в эквивалентную формулу (α1 ∧ β1 ∧ γ1 ) ∨ . . . ∨ (αk ∧ βk ∧ γk ). Преобразуем формулы αs и γs . Пусть формула αs имеет вид ♦L ψs,1 ∧ ∧ . . . ∧ ♦L ψs,ks . Формулы ψs,1 , . . . , ψs,ks приведем к такому же виду, что и ψs , т. е. выделим подформулы вида α, β и γ. Проделаем это со всеми получившимися подформулами вида α и γ и т. д. В результате получим формулы, не содержащие ♦L и ♦R . Зафиксируем транзитивную линейную модель h W, R, v i. Определим отношение эквивалентности на множестве W следующим образом: элементы x и y попадают в один класс эквивалентности, если x = y или выполняются xRy и yRx. Соответствующие классы эквивалентности называют сгустками. Транзитивная линейная модель состоит из сгустков с естественным линейным отношением.

598

С. И. Мардаев Рассмотрим пошаговый процесс построения множеств P 0 = ∅, P 1 ,

P 2 , . . . . На j-ом шаге значение P j−1 переменной p подставляем в формулу ϕ и получаем новое значение P j . Через Ajs , Bsj , Csj обозначим значения формул αs , βs и γs на j-ом шаге, т. е. после подстановки P j−1 , j > 1. Дадим определение. Предположим, что значения некоторых подформул θ и η формулы ϕ имеют непустое пересечение на некотором шаге. Тогда говорим, что имеет место зацепление формул θ и η на этом шаге. Однажды появившись, зацепление сохраняется на последующих шагах. Идея доказательства состоит в том, что число зацеплений постепенно увеличивается, но т. к. существует лишь конечное число подформул, то этот процесс не может продолжаться бесконечно. При этом ограничен сверху промежуток между шагами, на которых увеличивается число зацеплений. Рассмотрим j + 1-ый шаг, j > k + 1. Имеются два случая. В первом случае на этом шаге значения всех формул αi и γi не изменились для всех тех ψi , значения которых непусты на j + 1-ом шаге. Тогда P j — неподвижная точка. Действительно, пусть x ∈ P j+1 \ P j . Существует s, при котором x не принадлежит значению ψs на j-ом шаге и принадлежит на j + 1-ом шаге (тем самым на этом шаге значение ψs не пусто). Значит, βs стала истинной на x на j + 1-ом шаге. Поскольку βs не содержит ♦L и ♦R , то ее значение на x зависит только от значений переменных на x. Получаем, что при p, ложной на x, формула βs на j-ом шаге дает ложь, а на j + 1-ом — истину, приходим к противоречию. Теперь рассмотрим второй случай: значение некоторой ψi непусто на j + 1-ом шаге и значение αi увеличилось, т. е. Aj+1 строго содержит Aji i (случай, когда увеличивается γi , рассматривается аналогично). Докажем, что выполняется по крайней мере одно из следующих утверждений: 1) на j-ом или j + 1-ом шаге увеличилось число зацеплений; 2) найдется s такое, что значение αs увеличилось на j-ом шаге, а Ajs содержит Aj+1 и поэтому строго содержит Aji (отсюда s 6= i), при этом i значение ψs непусто на j-ом шаге; 3) на j + 1-ом шаге значение ψi из пустого стало непустым. Среди подформул с главной связкой ♦L формулы αi найдем форму-

Неподвижные точки во временных моделях

599

лу, которую обозначим ♦L ψi,∗ , со следующим свойством: значение ♦L ψi,∗ увеличилось на j + 1-ом шаге, а значения всех подформул с главной связl обознакой ♦L (если такие есть) формулы ψi,∗ не изменились. Через Fi,∗ l чим значения формулы ♦· L ψi,∗ на l-ом шаге. Заметим, что множество Fi,∗

всегда содержит Ali .



j+1  j Положим T = Fi,∗ \ Fi,∗ ∪

S

j+1 Ajs ⊂Fi,∗

Ajs ∪

S

j+1 Aj−1 ⊂Fi,∗ s



Asj−1  (здесь сим-

вол ⊂ означает ”строго содержится“). Ясно, что T непусто. Для любого s множество Asj−1 либо не пересекается с T , либо содержит T . То же выполняется для Ajs . Возможны следующие случаи. j , а а) Если для некоторого s множество Csj−1 не пересекается с Fi,∗ j+1 , то на j-ом или j + 1-ом шаге шаCsj имеет непустое пересечение с Fi,∗

ге увеличилось число зацеплений (зацепились γs и ψi,∗ ), т. е. справедливо утверждение 1. б) Пусть для некоторого s такого, что значение ψs непусто на j-ом шаге, множество Asj−1 не пересекается с T , а Ajs содержит T . Тогда на j+1 , поэтому j-ом шаге значение αs увеличилось. При этом Ajs содержит Fi,∗

содержит и Aj+1 , а следовательно, строго содержит Aji . В этом случае i выполняется утверждение 2. Заметим, что случаи ”а“ и ”б“ не исключают друг друга. в) Пусть, наконец, не выполняются условия случаев ”а“ и ”б“. Докажем, что тогда выполняется утверждение 3. Так как условия случая ”а“ не выполняются, то, в частности, для всех s либо множества Csj−1 и Csj не пересекаются с T , либо они содержат T (таким образом, для всех s формулы γs не меняют своих значений на элементах из T на j-ом шаге). Поскольку не выполняются условия случая ”б“, то для всех s, для которых значение ψs непусто на j-ом шаге, либо множества Asj−1 и Ajs не пересекаются с T , либо они содержат T (таким образом, для всех таких s формулы αs не меняют своих значений на j-ом шаге на элементах из T ). Докажем, что на j + 1-ом шаге из пустого стало непустым значение ψi . j Если Fi,∗ пусто, то пусто значение ψi,∗ , а значит, и ♦L ψi,∗ , следо-

600

С. И. Мардаев

j вательно, и значение ψi на j-ом шаге. Предположим, что Fi,∗ непусто, и

докажем, что этот случай невозможен. Формула ψi,∗ стала истинной на j+1-ом шаге на некоторых элементах из T . Пусть ψi,∗ = αr ∧ βr ∧ γr . Значит, одна из формул αr , βr или γr стала истинной на j + 1-ом шаге на некоторых элементах из T . По выбору j ψi,∗ формула αr не изменила своего значения на j + 1-ом шаге. Если Fi,∗

непусто, то формула γr не изменила своего значения на j + 1-ом шаге на элементах из T , она на них истинна. Значит, формула βr стала истинной на j + 1-ом шаге на некоторых элементах из T . Обозначим один из этих элементов через x. Формула βr не содержит ♦L и ♦R , поэтому ее значение на x зависит только от значений переменных на x. Значит, на j-ом шаге p стала истинной на x. Поскольку для всех s, при которых значение ψs непусто на j-ом шаге, на j-ом шаге формулы αs и γs не меняют своих значений на x, то на j-ом шаге некоторая βt стала истинной на x. Значит, при p, ложной на x, формула βt на j − 1-ом шаге дает ложь, а на j-ом — истину. Так как βt не содержит ♦L и ♦R , это невозможно. Отметим, что j > k + 1 > 2, поэтому j − 1-ый шаг существует. Продолжим доказательство теоремы. Пусть выполняется утвеждение 2, т. е. найдется s такое, что значение ψs непусто на j-ом шаге, значение и поэтому строго содерαs увеличилось на j-ом шаге, а Ajs содержит Aj+1 i жит Aji . То же рассуждение, что и выше, применяем к αs на j-ом шаге. При этом получаем, что выполняется по крайней мере одно из условий: 1) на j − 1-ом или j-ом шаге увеличилось число зацеплений; 2) найдется r такое, что значение αr увеличилось на j − 1-ом шаге, а Arj−1 содержит Ajs и поэтому строго содержит Asj−1 , при этом значение ψr непусто на j − 1-ом шаге; 3) на j-ом шаге значение ψs из пустого стало непустым. Если выполняется условие 2, т. е., в частности, найдется r такое, что Arj−1 содержит Ajs , получаем, что Arj−1 содержит Aj+1 и поэтому строго i содержит Aji , а тем более, Aij−1 . Итак, множество Arj−1 строго содержит Asj−1 и Aij−1 (отсюда r 6= s, i). Видим, что увеличилось число формул вида αt , про которые можно сказать, что их значения строго содержат

Неподвижные точки во временных моделях

601

значение αi . Это не может продолжаться более k − 1 раза, так как формул вида αt всего k. Поэтому на некотором l-ом шаге, j − k + 1 6 l 6 j + 1, увеличивается число зацеплений или значение некоторой ψt из пустого становится непустым. Отсюда следует утверждение теоремы, так как зацеплений может быть лишь конечное число и для конечного числа формул их значение из пустого может стать непустым. При этом видно, что можно вычислить не зависящую от модели эффективную верхнюю оценку числа шагов, необходимых для стабилизации. Доказательство завершено. Классом всех транзитивных линейных шкал характеризуется известная временная логика Lin (см. [12]). Из теоремы вытекает СЛЕДСТВИЕ. Для каждой временной Σ-формулы ϕ(p, q1 , . . . , qn ), позитивной по p, существует число m такое, что логика Lin содержит формулу ϕm+1 ↔ ϕm .

ЛИТЕРАТУРА 1. С. И. Мардаев, Неподвижные точки временных операторов, в сб. ”Алгебра и теория моделей 2“, труды 3-ей межд. школы ”Пограничные вопросы теории моделей и универсальной алгебры“, Эрлагол, 21–27 июня 1999, Новосибирск, изд-во НГТУ, 1999, 68—77. 2. С. И. Мардаев, Наименьшие неподвижные точки в логике Гжегорчика и интуиционистской пропозициональной логике, Алгебра и логика, 32, N 5 (1993), 519—536. 3. С. И. Мардаев, Наименьшие неподвижные точки в логике Гёделя–Леба, Алгебра и логика, 32, N 6 (1993), 683—689. 4. S. I. Mardaev, Least fixed points in modal logic, в сб. ”Труды международных конференций по математической логике“ (Proceedings of international conferences on mathematical logic), под ред. С. С. Гончарова и др., Новосибирск, изд-во НГУ, Новосибирск, 2002, 92—103. 5. С. И. Мардаев, Определимость наименьших неподвижных точек, Алгебра и логика, 41, N 4 (2002), 429–458. 6. Y. Gurevich, S. Shelah, Fixed-point extensions of first-order logic, Ann. Pure Appl. Logic, 32, N 3 (1986), 265—280.

602

С. И. Мардаев 7. S. Kreutzer, Expressive equivalence of least and inflationary fixed-point logic, in: Proc. 17th IEEE Symp. Log. Comput. Sci. (LICS), 2002, http://wwwmgi.informatik.rwth-aachen.de/kreutzer/publications/lics02.ps. 8. A. Dawar, E. Gr¨ adel, S. Kreutzer, Inflationary fixed points in modal logic, in: Comput. Sci. Log., 15th Int. Workshop, CSL 2001, 10th Ann. Conf. Eur. Assoc. Comput. Sci. Log. (EACSL), Paris, France, September 10– 13, 2001, L. Fribourg (ed.) (Lect. Notes Comput. Sci., 2142), Berlin, Springer-Verlag, 2001, 277—291 (см. также http://www-mgi.informatik.rwthaachen.de/kreutzer/publications/csl01.ps). 9. A. Dawar, E. Gr¨ adel, S. Kreutzer, Inflationary fixed points in modal logic, subm. to ACM Trans. Comput. Log. (TOCL), 2002 (см. также http://wwwmgi.informatik.rwth-aachen.de/kreutzer/publications/tocl.ps).

10. С. И. Мардаев, Неподвижные точки модальных схем, Алгебра и логика, 31, N 5 (1992), 493—498. 11. R. O. Gandy, Inductive definitions, in: J. E. Fenstad, P. G. Hinman (eds.), Generalized recursion theory (Stud. Logic Found. Math., 79), Amsterdam, NorthHolland Publ. Co., 1974, 265—299. 12. K. Segerberg, Modal logics with linear alternative relations, Theoria, 36, N 3 (1970), 301—322.

Поступило 22 мая 2003 г. Адрес автора: МАРДАЕВ Сергей Ильич, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ. e-mail: [email protected]