Site blog

Anyone in the world

Нестандартные кванторы и аксиомы равенства



Логика первого порядка \( \mathfrak{L}_{\omega \omega } \)  в качестве кванторов использует квантор существования \(\exists\) (и двойственный для него квантор всеобщности \(\forall\)), устроенный крайне просто. Связывание переменной в формуле квантором содержательно означает наличие хотя бы одного элемента модели, для которого справедлива формула, получающаяся из исходной подстановкой вместо переменной этого элемента модели. Однако, если перейти к обобщениям логики первого порядка, в которых вместо кванторов существования и всеобщности используются более сложные кванторы, то единственным разумным способом определения таких нестандартных кванторов оказывается использование совокупностей подмножество модели, то есть переход на более высокий уровень абстракции для определения выполнимости предложений логики на моделях. 

Именно, рассмотрим логику \( \mathfrak{L}_{\omega 0 } \), формулами которой являются бескванторные формулы логики первого порядка. Пусть далее \(Q\) - новый унарный квантор и \( \mathfrak{L}_{\omega \omega }(Q) \) - результат расширения синтаксиса бескванторной логики \( \mathfrak{L}_{\omega 0 } \) при помощи связывания свободных переменных с помощью нового квантора \(Q\). Для определения семантики нового квантора для каждой модели \(\mathfrak{A}=<A, P^{\mathfrak{A}}>\)  с унарным предикатным символом \(P\) в сигнатуре модели определим множество подмножеств в \(A\): \(Q^{\mathfrak{A}} \subseteq \wp(A)\), где \(\wp(A)\) - множество всех подмножеств множества \(A\). Тогда 

\( \mathfrak{A} \models_{\mathfrak{L}_{\omega \omega }(Q)} QxP(x) \Leftrightarrow  \{a \in A | <A, P^{\mathfrak{A}}, a>  \models_{\mathfrak{L}_{\omega \omega }(Q)} P(a) \} \in Q^{\mathfrak{A}}\)

В частности, для случая \(Q=\exists \) имеем для любой модели \(\mathfrak{A} \)  \(Q^{\mathfrak{A}}=\{X\subseteq A | X \neq \varnothing\}\)

Для стандартных кванторов существования (и всеобщности) легко формулируются аксиомы равенства, позволяющие интерпретировать (двухместный) предикат равенства как тождественное совпадение элементов модели. Для произвольной сигнатуры \(\tau\) определим её расширение \(\tau^{=} = \tau \cup \{=\}\) . Аксиомами равенства в сигнатуре  \(\tau^{=} \)  называется совокупность формул следующих видов: 
  • \(\forall x (x=x)\);
  • \(\forall x \forall y ((x=y) \rightarrow  (y=x))\);
  • \(\forall x \forall y \forall z ((x=y) \& (y=z) \rightarrow  (x=z))\);
  • Для каждого функционального символа  из исходной сигнатуры   \(\tau\) формулируем свою аксиому равенства, которая говорит, что его значение не меняется, если аргументы заменить на равные. Например, для функционального символа \(f\) арности 2 формируем аксиому вида \(\forall x_1  \forall y_1 \forall x_2 \forall y_2 ((x_1=x_2) \& (y_1=y_2) \rightarrow  (f(x_1, y_1)=f(x_2, y_2)))\);
  • Для каждого предикатного символа  из исходной сигнатуры   \(\tau\) формулируем свою аксиому равенства, которая говорит, что истинностное значение предиката не меняется, если аргументы заменить на равные. Например, для предикатного символа \(P\) арности 2 формируем аксиому вида \(\forall x_1  \forall y_1 \forall x_2 \forall y_2 ((x_1=x_2) \& (y_1=y_2) \& P(x_1, y_1)  \rightarrow  P(x_2, y_2))\).

Аксиомы равенства отлично подходят для работ в рамках обычной логики первого порядка, но, как только возникает необходимость работы с нестандартными кванторами, даже очень простыми и явно выразимыми через стандартные \(\exists\) и  \(\forall\), возникают проблемы концептуального характера. Действительно, рассмотрим логику с нестандартным квантором \(\exists_2\), говорящего, что существует не менее двух различных элементов, удовлетворяющих условию: 

\( \mathfrak{A} \models_{\mathfrak{L}}\exists _2xP(x)  \Leftrightarrow card(\{a \in A |  \mathfrak{A} \models_{\mathfrak{L}}P(a))\geqslant 2\)

Но как в новой логике \( \mathfrak{L}=\mathfrak{L}_{\omega \omega }(\exists_2) \)  выразить утверждение о существовании двух различных множеств мощности не менее 2, элементы которых удовлетворяют \(P(x)\)? Рассмотрим такое предложение: 

(*)           \(\varphi_1 =  \exists_2 x \exists_2 y (P(x) \& P(y)) = \exists_2 x \exists_2 y (A_P(x,y)) \)

Если предложение (*) выполняется на некоторой модели \( \mathfrak{L}\), то это означает лишь, что найдутся минимум два различных элемента в \(A\), удовлетворяющие \(P(\cdot ) \), поскольку никто не запрещает нам подставлять в формулу \( A_P(x,y)=(P(x) \& P(y))  \) одинаковые элементы. Это не совсем то, чего мы могли бы ожидать в связи с введением в рассмотрение нестандартного квантора. Попробуем теперь воспользоваться для совершенствования формулы (*)  отношением равенства, удовлетворяющего всем аксиомам равенства из списка выше. Рассмотрим формулу

(**)           \( \varphi_2=\exists_2 x \exists_2 y (P(x) \& P(y) \& \neg (x=y))= \exists_2 x \exists_2 y (A_P(x,y) \& \neg (x=y)) \)

Однако для любой модели данная формула будет интерпретироваться несколько неожиданно: она будет справедлива, если в модели будет существовать по меньшей мере три различных элемента, удовлетворяющих \(P(\cdot) \). В самом деле, пусть \( \{a_1, a_2, a_3 \}\) - эти элементы в модели \(\mathfrak{A} \). Тогда, очевидно,  что

\(\mathfrak{A} \models_{\mathfrak{L}} [A_P(a_1, a_2) \& A_P(a_1, a_3) \& \neg(a_2=a_3)] \).

Следовательно, \(\mathfrak{A} \models_{\mathfrak{L}} \exists_2 y[A_P(a_1, y)] \). Но аналогично \(\mathfrak{A} \models_{\mathfrak{L}} \exists_2 y[A_P(a_2, y)] \) - здесь вместо \(y\) следует подставлять элементы \(a_1\) и \(a_3\). Но это означает, что \(\mathfrak{A} \models_{\mathfrak{L}} \exists x \exists y [A_P(x,y) \& \neg (x=y))] \)

По сути, мы получили весьма тривиальный результат - для любой модели \(\mathfrak{A}\) предложение  \( \varphi_2\) выполняется на  \(\mathfrak{A}\) тогда и только тогда, когда в носителе модели \(A\) найдутся три или более различных элемента  таких, что на них выполняется \(P\). Другими словами

\(\mathfrak{A} \models_{\mathfrak{L}} [\varphi_2]  \Leftrightarrow  \mathfrak{A} \models_{\mathfrak{L_3}} \exists_3 z[P(z)] \), где \( \mathfrak{L_3}=\mathfrak{L}_{\omega \omega }(\exists_3) \).

Таким образом, конструкция вида (**) фактически позволила нам выполнить переход от предложений одной логики к предложениям другой логики, с совсем другими кванторами. А ведь мы только немного подкорректировали условие в формуле вида (*). Не трудно заметить, что добавляя и видоизменяя условия на переменные в формуле \( A_P(x,y)=(P(x) \& P(y))  \) , можно построить довольно сложные выражения, содержательный смысл которых может оказаться довольно неожиданным. Вся сложность скрывается в разумном связывании нескольких идущих друг за другом кванторов, причем здесь, в отличие от стандартной логики первого порядка, сделать это можно довольно разнообразными способами. 

Если же посмотреть на формальное определение логики с нестандартными кванторами (унарными), то бросается в глаза, что условия на переменные совсем не обязаны формулироваться в терминах логики первого порядка, естественным подходом будет использование выражений, связанных с анализом подмножество в \(\wp(A)\). Чтобы показать это, перепишем условие (**), используя условия, работающие с подмножествами. Для каждой формулы \(P(x)\) в синтаксисе \(\mathfrak{L}\) , определим \([P(x_1, \cdots, x_k)]^{\mathfrak{A}} = \{<b_1, \cdots, b_k> \in A^k | (\mathfrak{A}, b_1, \cdots, b_k)  \models_{\mathfrak{L}} P(b_1, \cdots, b_k)\}\). Вспомним также, что с точки зрения теоретико-множественного подхода 

(***)      \(QxP(x) \Leftrightarrow_{def}  \{b \in A | (\mathfrak{A}, b)  \models_{\mathfrak{L}} P(b) \} \in Q^{\mathfrak{A}}\).

Пусть также \(\Phi(X,Y)\) - отношение на \(\wp(A) \times  \wp(A)\). Определим тогда связку двух кванторов \(Q_1\) и \(Q_2\) через отношение \(\Phi(X,Y)\) следующим образом: 

(****)   \(Q_1xQ_2yA(x,y) \Leftrightarrow_{def}  \exists U_1 \forall a\in U_1 \exists U_a [ \forall y \in U_a A(a,y) \& \Phi(U_1, U_a)]\)

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

1.   \( \exists_2 x \exists_2 y (A(x,y)) \Leftrightarrow \exists U_1 \exists U_2 [U_1 \in (\exists_2)^{\mathfrak{A}}  \&  U_2 \in  (\exists_2)^{\mathfrak{A}}  \& \forall x \in U_1 \forall y \in U_2[A(x,y))  \)

для варианта (*), в котором фактически отсутствовали какие-либо ограничения на связи между элементами модели для подстановки в формулу \(A(x,y) \);

2.  \(  \exists_2 x \exists_2 y (A(x,y)) \Leftrightarrow  \exists U_1 \forall a \in U_1 \exists U_a  [ U_1 \in (\exists_2)^{\mathfrak{A}}  \&  U_a \in  (\exists_2)^{\mathfrak{A}}  \& \forall y \in U_a  A(a,y) \& (U_1 \setminus U_a) \neq \varnothing) \& (U_a \setminus U_1 \neq \varnothing)]\)

для ситуации, когда подразумевается существование различных (находящихся в общем положении) множество мощности не менее 2, удовлетворяющих заданной формуле. 

Получается, что использование аксиом равенства и построение сложных логических конструкций на их базе возможно обойти, используя конструкции вида (***). Более того, подход с использованием множеств для нестандартных кванторов является более многообещающим, поскольку предикаты, определенные на множествах, позволяют описывать значительно большее число вариантов объединения подряд идущих кванторов, нежели только конструкции, работающие с элементами множеств, как в логике первого порядка. Фактический переход к логике второго порядка позволяет строить и исследовать сложные соотношения между нестандартными кванторами в формулах логики на основе исчисления высказываний, но уже без обязательной опоры на аксиомы равенства. 
Также хотелось бы заметить, что для большинства объединений цепочек кванторов на основе предикатов вида \(\Phi(X_1, \cdots, X_k)\) как отношений на \(\wp(A)^k\) результат может существенно зависеть от порядка объединения предикатов. Отношения на \(\wp(A)^k\), которые дают такой эффект, на первый взгляд выглядят несколько странными и вопрос целесообразности их исследований  является открытым. Но можно заметить, что "естественные" предикаты \(\Phi(X_1, \cdots, X_k)\) , подобные тем, которые были определены в соотношениях 1. и 2. выше,  делают определение объединения цепочек кванторов независимым от порядка объединения (фактически, операция объединения цепочек кванторов оказывается ассоциативной). Можно надеяться, что все содержательные операции объединения кванторов через предикаты на множествах, также будут обладать таким естественным для нас свойством ассоциативности.

[ Modified: Monday, 1 March 2021, 1:44 PM ]