Матлог. Свойство из Мендельсона для выполненности формулы

[ignat.fugasov]

Хочу доказать 8-ое свойство из прараграфа про истинность(Гл.2 Теории первого порядка, параграф 2): Пусть все свободные переменные (если таковые имеются) формулы $\mathcal{A}$ содержатся среди переменных $x_{i_1},...,x_{i_n}$. Тогда если у последовательностей $s$ и $s$' компоненты с номерами $i_1,...,i_n$ совпадают, то формула $\mathcal{A}$ выполнена на s тогда и только тогда, когда она выполнена на $s$'.
В указании рекомендуется использовать индукцию по числу связок и кванторов. Собственно как должно выглядеть индуктивное предположение? Предположить что, если формула(или две формулы , если мы хотим доказывать утверждение для связок а не кванторов) выполнена на s тогда и только тогда, когда она выполнена на $s$', то тоже самое выполнено и для её "усложнения" не получится, ибо в общем случае нельзя гарантировать что предикатная буква выполнена на $s$, тогда и только тогда, когда она выполнена на $s$'. Попытки рассмотреть частные случаи оказались тщетны.

[gefest_md]

ignat.fugasov в сообщении #1363304 писал(а):

Предположить что, если формула(или две формулы , если мы хотим доказывать утверждение для связок а не кванторов) выполнена на s тогда и только тогда, когда она выполнена на $s$', то тоже самое выполнено и для её "усложнения"

Надо предположить предложение вида $(\text{Если }A_1 \text{ и }A_2),\text{ то }(A_3\text{ равносильно }A_4)$. Вы предположили только $A_3\text{ равносильно }A_4$.

[ignat.fugasov]

gefest_md
Тут я писал предположение для формы только с квантором, а не связкой. Например если для $\mathcal{B}$ имеет место равносильность выполненности на последовательностях, то и для $\forall x_k\mathcal{B}$ то же самое. Вы указали как должно оно выглядеть для связок. Но суть в том, что как мне видеться, такое предположение нельзя делать, ведь база индукции вообще говоря не верна.

[gefest_md]

ignat.fugasov в сообщении #1363316 писал(а):

Тут я писал предположение для формы только с квантором, а не связкой.

Передумали? «Формула или две формулы». Я сформулировал выше свойство $P$ из следующего предложения: Для каждой формулы $\mathcal{A}$ и любых $s$, $s\prime$ имеет место $P(\mathcal{A},s,s\prime)$. Чтобы это доказать, досточно доказать несколько пунктов. Некоторые пункты будут импликациями. Например, один пункт будет таким

Если

для любых $s$, $s\prime$ имеет место $P(\mathcal{B},s,s\prime)$

и

для любых $s$, $s\prime$ имеет место $P(\mathcal{C},s,s\prime)$,

то

для любых $s$, $s\prime$ имеет место $P(\mathcal{B\vee C},s,s\prime)$.

[ignat.fugasov]

gefest_md
В вашем ответе полагаю $s\text{ и }s\prime$ это произвольные последовательности удовлетворяющие условию из первого сообщения. Свойство $P(\mathcal{A},s,s\prime)$ - "$\mathcal{A}$ выполнено на $s$ тогда и только тогда, когда $\mathcal{A}$ выполнено на $s\prime$ ". Положим я все пункты со всеми кванторами и связками доказал. Но как из этого следует, что для любой $\mathcal{A}$ выполнено $P(\mathcal{A},s,s\prime)$? Для этого необходимо что бы наше свойство было выполнено и для предикатных букв из $\mathcal{A}$(база индукции).
Пример: $\mathcal{A}$ это $\forall x_1\exists x_2A_1^3(x_1,x_2,x_3)$ Пусть в данной интерпритации $A_1^3(x_1,x_2,x_3)$ выполнена на $s=(e,f,g,...)$ и не выполнена на $s\prime =(a,b,g,...)$. Свойство $P(A_1^3(x_1,x_2,x_3),s,s\prime)$ не выполняется, следовательно мы не можем доказать, что$P(\mathcal{A},s,s\prime)$.

[gefest_md]

ignat.fugasov,
Через $P$ обозначил «Если $\mathcal{A}$ содержит переменные ... и последовательности $s$, $s\prime$ совпадают по компонентам ..., то $\mathcal{A}$ выполнено на $s$ тогда и только тогда, когда оно выполнено на $s\prime$».

[ignat.fugasov]

Для тех кто будет просматривать тему.
Вернулся к теореме и доказал. "Индуктивное" свойство выглядит так: "Формула $\mathcal{A}$ выполнена на $s_1$ тогда и только тогда, когда формула $\mathcal{A}$ выполнена на $s_2$, где $s_1$ и $s_2$ - произвольные последовательности, все компоненты, по номерам которых переменные свободны, совпадают. Для предикатных букв понадобится, что для произвольного терма t из данной буквы $s_2^*(t)=s_1^*(t)$