Доказать общезначимость в логике второго порядка

[kernel1983]

Здравствуйте.

Требуется доказать, что формула логики предикатов второго порядка $\exists P \forall x \exists y \neg (P(x) \leftrightarrow Q(x,y))$ общезначима. В силу определения, это означает, что для произвольного предиката $B(x,y)$, определённого на произвольном множестве $M$ ($\mathcal{B} \subseteq M^2$, где $\mathcal{B}$ - множество истинности предиката $B(x,y)$) высказывание $\exists P \forall x \in M \exists y \in M \neg (P(x) \leftrightarrow Q(x,y))$ истинно (при этом предикатная переменная $P$ также определена на множестве $M$). Таким образом, для произвольного предиката $B(x,y)$ нужно указать предикат $A(x)$ (они определены на произвольном множестве $M$), такой, что для произвольной предметной постоянной $a \in M$ cуществует предметная постоянная $b \in M$, такая, что высказывание $\neg (A(a) \leftrightarrow Q(a,b))$ истинно.

Как превратить двухместный предикат в одноместный? Вижу три способа: связать одну из предметных переменных квантором общности или квантором существования, заменить одну из предметных переменных предметной постоянной. Кроме того, при необходимости, на него можно навесить знак отрицания. Я решил поступить так. Рассмотрим предикат $\neg B(x,a)$, где $a \in M$ - произвольная предметная постоянная.Тогда положив $x=y$ (для любого икса нужно указать игрек, очевидно, зависящий от икса) и заменив $x$ на произвольную предметную постоянную $a$ (cмущает то, что это та же произвольная постоянная, что заменяет предметную переменную $y$ в предикате $B$) получим: $\neg ( \neg B(a,a) \leftrightarrow B(a,a))$. Нетрудно показать, что это высказывание истинно.

Не нравится чехарда с предметными постоянными, но подход в целом кажется верным. Как тут лучше поступить?

Спасибо.

[dgwuqtj]

А просто взять $P(x) := \neg Q(x, x)$ нельзя? Вы же это по сути и делаете.

[kernel1983]

dgwuqtj в сообщении #1616236 писал(а):

А просто взять $P(x) := \neg Q(x, x)$ нельзя?

Думал об этом, но это ведь не одноместный предикат, а двухместный с отождествлёнными предметными переменными.

[dgwuqtj]

Пусть у вас есть $n$-местный предикат $P(x_1, \ldots, x_n)$ и термы $t_1(y_1, \ldots, y_m), \ldots, t_n(y_1, \ldots, y_m)$. Тут не обязательно каждый $y_j$ на самом деле явно используется в каждом $t_i$. Тогда $P(t_1, \ldots, t_n)$ будет $m$-местным предикатным символом от переменных $y_1, \ldots, y_m$. Вроде нет понятия "отождествлённые предметные переменные", переменные в предикате по определению различны (это же просто буквы, а не их возможные значения).