Математическая логика (по Мендельсону)

[Виктор Викторов]

Спасибо.

Xaositect в сообщении #445472 писал(а):

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

Вот эта фраза мне и была нужна.

[Виктор Викторов]

Ещё один вопрос, но здесь и формализм и суть дела.

Виктор Викторов в сообщении #432876 писал(а):

mkot в сообщении #432751 писал(а):

Виктор Викторов в сообщении #432704 писал(а):

«(iv) Формула $\forall x_i\mathcal{A}$ выполнена на $s$ тогда и только тогда, когда формула $\mathcal{A}$ выполнена на любой последовательности из $\sum $, отличающейся от $s$ не более чем своей i-й компонентой.» Стр.59. Почему на последовательности? Тогда уж на совокупности последовательностей отличающихся друг от друга не более чем своей i-й компонентой.

А в чём разница?

Речь-то всё-таки идёт о множестве последовательностей, а не о последовательности.

Вот к чему приводят недовыясненные отношения. Та же проблема вылезла вновь в новом обличии, да и старая проблема готова повернуться новой стороной.
«(ii) $\exists x_i\mathcal{A}$ выполнено на $s$ тогда и только тогда, когда $\mathcal{A}$ выполнено хотя бы на одной последовательности $s'{,}$ отличающейся от $s$ не более чем одной только i-й компонентой.» Страница 60.
Сначала по странице 60. Рассмотрим простой пример $\exists x_1(x_1>3){.}$ Область интерпретации множество всех натуральных чисел. Выполнено ли $\exists x_1(x_1>3)$ на последовательности $(2, 2, 2, \dots){?}$ Согласно следствию (ii) выполнено. Почему? А потому, что существует последовательность $(5, 2, 2, \dots){,}$ отличающаяся от первоначальной только первой компонентой. Мне этот результат не менее странен, чем и поставленный вопрос «Выполнено ли $\exists x_1(x_1>3)$ на последовательности $(2, 2, 2, \dots){?}$» Мне кажется, как я уже и писал, что свойство (и соответствующее определение) должно звучать как-то так: $\exists x_i\mathcal{A}$ выполнено на совокупности последовательностей $\left\{s\right\}{,}$ которые отличаются друг от друга не более чем одной только i-й компонентой, тогда и только тогда, когда $\mathcal{A}$ выполнено хотя бы на одной последовательности из этой совокупности. Подозреваю, что прав Мендельсон, а не я, но не вижу как.
В случае квантора всеобщности пример аналогичен. Достаточно выбрать последовательность, на которой $\mathcal{A}$ не выполняется, но $\mathcal{A}$ выполняется для все последовательностей, отличающихся от данной только i-й компонентой. И опять же вопрос: «Почему на последовательности? Тогда уж на совокупности последовательностей, отличающихся друг от друга не более чем своей i-й компонентой.»

[Xaositect]

Во-первых, я не понимаю, откуда Вы взяли "выполнено на совокупности последовательностей", если у нас определяется только выполнимость на последовательности.
У нас в языке есть счетное кол-во переменных $x_1,x_2,\dots$. После того, как мы фиксировали интерпретацию, мы хотим определить, будет ли формула истинной (выполненной) на каких-то конкретных значениях этих $x_i$. То есть мы фиксируем некоторую последовательность значений $s_i\in D$ и определяем выполненность на ней формулы.
Для этого мы сначала определяем оценку термов (стр. 58, определение $\mathrm{s}^*$) индукцией по структуре терма. Если терм - переменная, то мы уже приписали ему значение, оно находится на соответствующем месте в последовательности $s_i$. Если терм - константа, то берем ее значение из интерпретации. Если терм - функциональное выражение, то мы вычисляем соответствующую функцию (заданную интерпретацией) на соответствующих значениях (определенных по индукции)
Далее, мы определяем выполненность формулы на последовательности (т.е., будет ли формула истинной при заданных значениях переменной). Если формула элементарная, мы проверяем соответсвующее отношение на оценке термов. Связки переводятся тоже просто.
Теперь о кванторах. Что мы хотим от выполнимости $\forall x_i \mathcal{A}$? Мы хотим, чтобы эта формула была выполнена т. и т. т., когда $\mathcal{A}$ выполнена при любом значении $x_i$. То есть: у нас есть последовательность значений переменных. Но переменная $x_i$ связана, и для того, чтобы проверить выполнимость, ее нужно менять. То есть мы приходим к определению: $\forall x_i \mathcal{A}$ выполнена на последовательности $s$ тогда и только тогда, когда $\mathcal{A}$ выполнена на любой последовательности $s'$ вида $(s_1,s_2,\dots, s_{i-1},s'_i, s_{i+1},\dots)$.
С существованием аналогично.

[Виктор Викторов]

Xaositect в сообщении #445722 писал(а):

Во-первых, я не понимаю, откуда Вы взяли "выполнено на совокупности последовательностей", если у нас определяется только выполнимость на последовательности.

Я и рассматриваю разумность введения для формулы $\forall x_i \mathcal{A}$ понятия «выполнимость на последовательности» и ставлю вопрос может быть нужно ввести понятие «выполнено на совокупности последовательностей».

Теперь вопросы по Вашему определению (а оно отличается от определения Мендельсона).

Xaositect в сообщении #445722 писал(а):

... формула была выполнена т. и т. т., когда $\mathcal{A}$ выполнена при любом значении $x_i$. То есть: у нас есть последовательность значений переменных. Но переменная $x_i$ связана, и для того, чтобы проверить выполнимость, ее нужно менять. То есть мы приходим к определению: $\forall x_i \mathcal{A}$ выполнена на последовательности $s$ тогда и только тогда, когда $\mathcal{A}$ выполнена на любой последовательности $s'$ вида $(s_1,s_2,\dots, s_{i-1},s'_i, s_{i+1},\dots)$.

Есть последовательность $s{.}$ У этой последовательности есть i-ая компонента. Вы справедливо пишете «Но переменная $x_i$ связана, и для того, чтобы проверить выполнимость, ее нужно менять.» А что значит менять $x_i{?}$ Это и значит рассматривать совокупность последовательностей вида $(s_1,s_2,\dots, s_{i-1},s'_i, s_{i+1},\dots)$ Теперь с позиции примера: Выполнено ли $\forall x_1(x_1>3)$ на последовательности $(5, 2, 2, \dots){?}$ Получается, что проблема на одной последовательности, а чтобы ответить на этот вопрос надо привлекать все последовательности вида $( s'_1, 2, 2, \dots){,}$ где $s'_1$ пробегает всю область интерпретации. Последняя фраза возвращает нас к определению Мендельсона: «(iv) Формула $\forall x_i\mathcal{A}$ выполнена на $s$ тогда и только тогда, когда формула $\mathcal{A}$ выполнена на любой последовательности из $\sum $, отличающейся от $s$ не более чем своей i-й компонентой.» Стр.59. Здесь не говорится о всех последовательностях вида $(s_1,s_2,\dots, s_{i-1},s'_i, s_{i+1},\dots)$. Речь идет о последовательностях, отличающихся от $s$ не более чем своей i-й компонентой. Т. е. сама последовательность $s$ (в разрез с Вашим определением) в эти «отличающиеся» последовательности не входит. Следовательно это "не более чем" надо понимать как сама последовательность $s$ и все последовательности, отличающиеся от неё только i-й компонентой.

[Xaositect]

Виктор Викторов в сообщении #445816 писал(а):

Следовательно это "не более чем" надо понимать как сама последовательность $s$ и все последовательности, отличающиеся от неё только i-й компонентой.

А как иначе можно понимать здесь оборот "не более чем"? Отличается не более чем в $i$-й компоненте $\Leftrightarrow$ отличается в $i$-й компоненте или вообще не отличается.

[Виктор Викторов]

Xaositect в сообщении #445832 писал(а):

Виктор Викторов в сообщении #445816 писал(а):

Следовательно это "не более чем" надо понимать как сама последовательность $s$ и все последовательности, отличающиеся от неё только i-й компонентой.

А как иначе можно понимать здесь оборот "не более чем"? Отличается не более чем в $i$-й компоненте $\Leftrightarrow$ отличается в $i$-й компоненте или вообще не отличается.

Нельзя понимать иначе. Но, я-то это понял только, когда писал комментарий. Мне всё мерещилось, что "не более чем" не включает саму последовательность. Таким образом Ваше определение и определение Мендельсона совпадают.

Остается вопрос на чем определять формулу $\forall x_i \mathcal{A}$ на последовательности или на совокупности последовательностей?

[Виктор Викторов]

Так как мой вопрос не лучше ли определять выполнимость формулы $\forall x_i \mathcal{A}$ на совокупности последовательностей вместо последовательности не вызвал комментариев, то мне пришлось разбираться с этим самому. Мои соображения «выдаю» в два приема.
Сначала Мендельсон разъясняет, что такое предикатная буква $A_j^n$ и дает примеры $A_1^1{,}$ $A_2^1$ и т. д. Пишет, что «Верхний индекс предикатной или функциональной буквы указывает число аргументов, а нижний индекс служит для различения букв с одним и тем же числом аргументов.» Затем «Предикатные буквы, примененные к термам, порождают элементарные формулы, ... $A_j^n(t_1, \dots, t_n)$ — элементарная формула.» И после ещё ряда определений переходит к индуктивному определению «... что значит, что формула $\mathcal{A}$ выполнена на последовательности $s=(b_1,b_2,\dots)$ из $\sum$ при данной интерпретации.»
В определении четыре индуктивных шага. Первые три говорят о выполненности тех или иных формул при подстановке символов, представляющих элементы последовательности на места свободных вхождений предметных переменных. А четвертый шаг я уже цитировал: «(iv) Формула $\forall x_i\mathcal{A}$ выполнена на $s$ тогда и только тогда, когда формула $\mathcal{A}$ выполнена на любой последовательности из $\sum $, отличающейся от $s$ не более чем своей i-й компонентой.» Я не стал бы цитировать это предложение опять, если бы не комментарий, резюмирующий эти четыре шага, немедленно следующий за ним: «Иначе говоря, формула $\mathcal{A}$ выполнена на последовательности $s=(b_1,b_2,\dots)$ тогда и только тогда, когда подстановка при каждом $i$ символа, представляющего $b_i{,}$ на места всех свободных вхождений $x_i$ в $\mathcal{A}$ приводит к истинному в данной интерпретации предложению.» Этот комментарий по отношению к четвертому шагу можно «прокомментировать» известной фразой «Вас здесь не стояло».
Но нестыковки только начались. Дальше идут следствия из этого определения. И среди них следствие «(VII) Всякий частный случай всякой тавтологии истинен во всякой интерпретации.» А откуда здесь взялись тавтологии? У нас формулы, выполненные или нет, на некоторой последовательности в данной интерпретации. А тавтология это: «Пропозициональная форма, которая истинна независимо от того, какие значения принимают встречающиеся в ней пропозициональные буквы, называется тавтологией.» Страница 24. Дело, конечно, можно поправить, если объявить предикатной буквой символ $A_j^0{.}$ Но я именно по этому и показал, что у Мендельсона $n$ начинается с $1{.}$ Т. е. в формулы исчисления предикатов хорошо бы включить и пропозициональные формы (так, мне кажется, и делают ряд авторов. Не ошибаюсь?) т. е. высказывания. Интересно, что ряд высказываний является формулами по определению -- это формулы с только связанными переменными. Но, если некоторые пропозициональные формы (тавтологии) истинны в любой интерпретации, то возникает вопрос, а есть ли формулы с только связанными переменными истинные в любой интерпретации? Об этом чуть позже.

[Xaositect]

Частный случай тавтологии - это результат замены пропозициональных букв на произвольные формулы.
Напр., $A^1(x)\to (\forall x \exists y B^2(x, y) \to A^1(x))$ является частным случаем тавтологии $A\to(B\to A)$

[Виктор Викторов]

Xaositect в сообщении #446129 писал(а):

Частный случай тавтологии - это результат замены пропозициональных букв на произвольные формулы. Напр., $A^1(x)\to (\forall x \exists y B^2(x, y) \to A^1(x))$ является частным случаем тавтологии $A\to(B\to A)$

Xaositect! Спасибо.

В связи уточнением Xaositect, вопрос о необходимости «нулевой» предикатной буквы попал под сомнение. Но без сомнения формулы только со связанными переменными являются высказываниями. Я что-то не помню размышлений на тему: а чем высказывания без связных переменных отличаются от высказываний со связными переменными.
Одно различие мне бросилось в глаза. Если высказывание без связных переменных истинно, то оно истинно в каждой интерпретации. Действительно подставлять-то нечего и некуда. А формула со связными переменными может быть выполнена в одной интерпретации и не выполнена в другой. Например, формула $\exists x_1(x_1>3)$ выполнена на любой последовательности в интерпретации с областью $\left\{4, 5\right\}$ и не выполнена на каждой последовательности в интерпретации с областью $\left\{2, 3\right\}{.}$ Все это тем более интересно поскольку введено понятие замыкания формулы, т. е. приписывания квантора всеобщности ко всем свободным переменным. Возвращаюсь к вопросу не лучше ли определять выполнимость формулы $\forall x_i \mathcal{A}$ на совокупности последовательностей вместо последовательности. Дело в том, что «Формула $\mathcal{A}$ называется истинной (в данной интерпретации) тогда и только тогда, когда она выполнена на всякой последовательности из $\sum{.}$» И я думаю, что, если определить не на последовательности, а на совокупности последовательностей, то такое определение потащило бы за собой и дополнительное определение истинности на совокупности последовательностей и, видимо, ещё много чего. С другой стороны, совокупность последовательностей все равно смотрит из-за угла, а то, что формула $\exists x_1(x_1>3)$ выполнена на последовательности $(2, 2, 2, \dots)$ с областью интерпретации натуральные числа, можно пережить.

(Оффтоп)

Когда вижу странные словосочетания всегда успокаиваю себя тем, что пользуемся же мы словосочетанием «свобода выбора» и ничего.

И ещё одна деликатная проблема. На странице 60 дан пример замыкания формулы $A_1^2(x_2, x_5) \to \neg\exists x_2 A_1^3(x_1, x_2, x_3){,}$ но сделано это весьма кокетливо: формула обозвана $\mathcal{A}$ и соответственно замыканием будет формула $\forall x_5 \forall x_3 \forall x_2 \forall x_1 \mathcal{A}{.}$ А меня интересует переменная $x_2{.}$ Она имеет, как свободные вхождения, так и связанные. Выглядеть это должно так: $\forall x_5 \forall x_3 \forall x_2 \forall x_1 (A_1^2(x_2, x_5) \to \neg\exists x_2 A_1^3(x_1, x_2, x_3)){,}$ но как быть с $x_2{?}$ По определению нужно связывать только свободную её часть, но как это практически записать?

[Xaositect]

Виктор Викторов в сообщении #446222 писал(а):

Если высказывание без связных переменных истинно, то оно истинно в каждой интерпретации.

Неверно.
Высказывание $x>0$ истинно(т.е., выполнимо на всех последовательностях), если за $D$ взять положительные числа, и не истинно, если взять, допустим, все действительные, с соответствующими отношениями для $>$.
Другое дело, что замкнутая формула всегда либо истинна, либо ложна, а вот для незамкнутых может быть промежуточный вариант.

Виктор Викторов в сообщении #446222 писал(а):

И ещё одна деликатная проблема.

Ну так каждое вхождение связывается самым внутренним квантором. Т.е. второе вхождение $x_2$ связано квантором $\exists x_2$, и в исходной формуле, и в замыкании. А первое в исходной формуле свободно, а в замыкании связано квантором всеобщности.
То есть, если мы захотим, допустим, переименовать связанную переменную квантора $\forall x_2$, то первое вхождение надо заменить, а второе-нет, т.к. оно связано другим квантором.

[Виктор Викторов]

Xaositect в сообщении #446385 писал(а):

Виктор Викторов в сообщении #446222 писал(а):

Если высказывание без связных переменных истинно, то оно истинно в каждой интерпретации.

Неверно.
Высказывание ${x>0}$ истинно(т.е., выполнимо на всех последовательностях), если за $D$ взять положительные числа, и не истинно, если взять, допустим, все действительные, с соответствующими отношениями для $>$.
Другое дело, что замкнутая формула всегда либо истинна, либо ложна, а вот для незамкнутых может быть промежуточный вариант.

Вопрос терминологии. Я понимал, что под высказыванием понимается пропозициональная форма (вообще без переменных) и формулы с только связанными переменными (свободные переменные отсутствуют). Тогда высказывание «13 есть четное число» истинно или ложно в любой интерпретации. Но ${x>0}$ не является высказыванием, а является формулой с одной свободной переменной и, конечно, её выполнимость во весь рост зависит от интерпретации. Xaositect! Буду Вам признателен, если Вы проясните для меня вопросы терминологии. Можно ли называть формулой пропозициональную форму (вообще без переменных)? И вроде бы из Вашего комментария высвечивается, что формулы с переменными можно называть высказываниями? Мне казалось, что они (формулы) становятся высказываниями после подстановки вместо каждой свободной переменной соответствующего символа из последовательности, на которой мы рассматриваем выполнимость данной формулы.

[Xaositect]

Я, знаете ли, читал разную литературу и давно (лет 5 назад в основном), поэтому с терминологией могу путаться.
Высказыванием я назвал $x>0$ неправильно. Но и формулу логики предикатов $\forall x (x > 0)$ или $\exists x (x > 0)$ тоже высказыванием называть некорректно. Высказыванием (proposition) называется формула исчисления высказываний (и соответствующий неформальный объект), а замкнутая (без свободных переменных) формула исчисления предикатов называется предложением (stаtement).

[Виктор Викторов]

Xaositect в сообщении #446783 писал(а):

Я, знаете ли, читал разную литературу и давно (лет 5 назад в основном), поэтому с терминологией могу путаться.
Высказыванием я назвал $x>0$ неправильно. Но и формулу логики предикатов $\forall x (x > 0)$ или $\exists x (x > 0)$ тоже высказыванием называть некорректно. Высказыванием (proposition) называется формула исчисления высказываний (и соответствующий неформальный объект), а замкнутая (без свободных переменных) формула исчисления предикатов называется предложением (stаtement).

(Оффтоп)

Самыми деликатными считаются вопросы крови (кто кому родственник). Предлагаю вопросы терминологии поставить вторыми в этом ряду по деликатности.

С удивлением обнаружил, что Мендельсон даже не описывает, что такое высказывание. (Определения, как я понимаю, и быть не может.) Слово «высказывание» на странице 19 во втором английском издании «sentence» страница 19.
Дальше ещё веселее. «Для данной интерпретации всякая формула без свободных переменных (или, иначе, замкнутая формула) представляет собой высказывание, которое истинно или ложно, а всякая формула со свободными переменными выражает некоторое отношение на области интерпретации; это отношение может быть выполнено (истинно) для одних значений переменных из области интерпретации и не выполнено (ложно) для других.» Страница 57.
«For a given interpretation, a wf without free variables (called a closed wf or a sentence) represents a proposition which is true or false, whereas a wf with free variables stands for a relation on the domain of the interpretation which may be satisfied (true) for some values in the domain of the free variables and not satisfied (false) for the others.» Второе английское издание страница 50.
Получается, что всякая замкнутая формула и «sentence» и «proposition» одновременно. При этом «мудро» избегается вопрос: Что же «выполнено (истинно)» или «не выполнено (ложно)»? Т. е. как получившееся называется? Кстати, в русском языке формула (а речь идет именно о формуле) не может быть выполнено. Формула может быть только выполнена. Там ещё есть слово "отношение". Оно, конечно, выполнено. Правда, получается, что отношение и формула одно и то же? Но кроме, терминологии существует ещё и суть. Явно интересно, сравнить замкнутые формулы и такие образования, как «13 есть четное число» т. к. и те и другие либо истинны либо ложны. И также договориться во что превращается «формула со свободными переменными» после подстановки.

[Виктор Викторов]

Терминология терминологией. Но есть ещё и суть дела. После определения выполнимости формулы на последовательности идут 11 следствий из этого определения. И тут стало тесно от ошибок переводчика.

1. «(VIII) Пусть свободные переменные (если таковые имеются) формулы $\mathcal{A}$ содержатся среди переменных $x_{i_1},\cdots , x_{i_n}{.}$ Тогда если у последовательностей $s$ и $s'$ компоненты с номерами $i_1,\cdots , i_n$ совпадают, то формула $\mathcal{A}$ выполнена на $s$ тогда и только тогда, когда она выполнена на $s'{.}$»

Очевидно, что в такой форме это ошибка. Лезем в английский оригинал там вместо «свободные переменные» стоит «the free variables». Определённый артикль в английском языке штука коварная. В данном случае он должен быть переведен как «все». Поэтому, следствие VIII должно выглядеть так: «(VIII) Пусть [все] свободные переменные (если таковые имеются) формулы $\mathcal{A}$ содержатся среди переменных $x_{i_1}, \cdots , x_{i_n}{.}$ Тогда если у последовательностей $s$ и $s'$ компоненты с номерами $i_1, \cdots , i_n$ совпадают, то формула $\mathcal{A}$ выполнена на $s$ тогда и только тогда, когда она выполнена на $s'{.}$»

2. «(XI) Если формула $\mathcal{A}$ не содержит $x_i$ в качестве свободной переменной, то формула

$$\forall x_i (\mathcal{A} \to \mathcal{B})\to (\mathcal{A} \to \forall x_i \mathcal{B})$$

истинна во всякой интерпретации.»

Перевод следствия XI прекрасен. Но затем идет интересное доказательство и тут две ошибки переводчика. «Допустим, что (XI) неверно. Это значит, что при некоторых $\mathcal{A}$ и $\mathcal{B}$ формула $\forall x_i (\mathcal{A} \to \mathcal{B})\to (\mathcal{A} \to \forall x_i \mathcal{B})$ не истинна в некоторой интерпретации. Согласно пункту (iii) последнего определения, должна существовать последовательность $s{,}$ на которой $\forall x_i (\mathcal{A} \to \mathcal{B})$ выполнено, а $(\mathcal{A} \to \forall x_i \mathcal{B})$ не выполнено. Тогда опять по тому же пункту (iii) на этой последовательности $s$ выполнено $\mathcal{A}$ и не выполнено $\forall x_i \mathcal{B}{.}$ Следовательно, в силу пункта (iv) того же определения, существует последовательность $s'{,}$ быть может, отличающаяся от $s$ одной лишь i-й компонентой, на которой не выполнено $\mathcal{B}{.}$» и так далее.

Причем здесь «... при некоторых $\mathcal{A}$ и $\mathcal{B}$...»? Смотрится бессмысленно. Полез в оригинал там никаких «$\mathcal{A}$ и $\mathcal{B}$» просто нет. Фраза должна выглядеть так: «Это значит, что формула $\forall x_i (\mathcal{A} \to \mathcal{B})\to (\mathcal{A} \to \forall x_i \mathcal{B})$ не истинна в некоторой интерпретации.»
«... существует последовательность $s'{,}$ быть может, отличающаяся от $s$ одной лишь i-й компонентой, ...» или быть может, ещё чем либо. Бессмыслица. В оригинале «at most», т. е. «наибольшее», а в данном контексте лучше сказать «не более чем». Звучать это должно так: «Следовательно, в силу пункта (iv) того же определения, существует последовательность $s'{,}$ отличающаяся от $s$ не более чем одной лишь i-й компонентой, на которой не выполнено $\mathcal{B}{.}$»

[Виктор Викторов]

«Множество всех n-ок $(b_{i_1},\cdots , b_{i_n})$ элементов области $D$ таких, что формула $\mathcal{A}$ выполнена на всякой последовательности $s{,}$ у которой $i_1$-я, ..., $i_n$-я компоненты совпадают соответственно с $b_{i_1},\cdots , b_{i_n}{,}$ называется отношением (или свойством) интерпретации, соответствующим формуле $\mathcal{A}{.}$» Страница 61.
Опять проблема. У нас уже было это определение. И, что такое n-местное отношение мы знаем. И предикатной букве «относили» n-местное отношение. Зачем ещё раз? Вглядевшись, (а у меня новые очки) увидел так, да не так. Вместо конечной последовательности подпоследовательность т. е. ещё и индексы проиндексированы. Сразу подозрение: «может быть, автор хочет отделить свободные переменные от связанных?». Полез в оригинал. И опять нашёл, что искал. Должно быть:
«Множество всех k-ок $(b_{i_1},\cdots , b_{i_k})$ элементов области $D$ таких, что формула $\mathcal{A}{,}$ имеющая своими своими свободными переменными только $x_{i_1},\cdots , x_{i_k}{,}$ выполнена на всякой последовательности $s{,}$ у которой $i_1$-я, ..., $i_k$-я компоненты совпадают соответственно с $b_{i_1},\cdots , b_{i_k}{,}$ называется отношением (или свойством) интерпретации, соответствующим формуле $\mathcal{A}{.}$»
Кроме, добавленных свободных переменных («имеющая своими своими свободными переменными только $x_{i_1},\cdots , x_{i_k}$»), n-ки изменены на k-ки, чтобы подчеркнуть, что в общем случае из-за связанных переменных $n$ может быть и больше чем $k{.}$