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

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

«(i) Если $\mathcal{A}$ есть элементарная формула $A_j^n(t_1, \dots, t_n)$ и $B_j^n $ есть соотвествующее ей отношение в интерпретации, то формула $\mathcal{A}$ считается выполненной на последовательности $s$ в том и только в том случае, когда $B_j^n(s^*(t_1), \dots, s^*(t_n)){,}$ то есть если n-ка $(s^*(t_1), \dots, s^*(t_n))$ принадлежит отношению $B_j^n{.}$» Эллиот Мендельсон «Введение в математическую логику» Стр.59.

«...когда $B_j^n(s^*(t_1), \dots, s^*(t_n)){,}$» Что это значит? Во-первых, мне здесь не хватает глагола, во-вторых, что такое $B_j^n(s^*(t_1), \dots, s^*(t_n)){?}$
$B_j^n $ -- отношение, т. е. множество n-к. Каких n-к? Тех которые относятся к $A_j^n(t_1, \dots, t_n)$ (иначе говоря, при подстановке такой n-ки в $A_j^n(t_1, \dots, t_n)$ формула становится истинной). Поэтому мне кажется, что здесь опечатка. Должно быть: «...когда $A_j^n(s^*(t_1), \dots, s^*(t_n)){,}$» и дальше нужен глагол. По смыслу «есть истинно», но это выражение использовать нельзя. (Нужно сказать, что эта n-ка относится к предикатной букве $A_j^n$). Итак, где опечатка у Мендельсона или у меня в голове?

[mkot]

У Мендельсона всё верно.

Выражение 'когда $R(x, y)$' означает, 'когда $(x, y) \in R$', где $R$ -- отношение.

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

Нас страницах 12 и 13 такого нет. '$(x, y) \in R$' есть, а '$R(x, y)$' я не вижу. Ткните, пожалуйста, пальцем. Тут некоторые странности. По терминологии Мендельсона $B_j^n(s^*(t_1), \dots, s^*(t_n))$ - формула, а $B_j^n$ предикатная буква. А тут он пишет, что $B_j^n$ отношение. В дальнейших изданиях обозначение изменено, но смысл остался тот же.

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

Ещё пару языковых проблем в Мендельсоне. На странице 54 определены предикатная буква $A_j^n$ и функциональная буква $f_j^n$, но тут же говорится просто о предметных (индивидных) переменных и константах. Логичнее было бы назвать их буквами.

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

[mkot]

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

Нас страницах 12 и 13 такого нет. '$(x, y) \in R$' есть, а '$R(x, y)$' я не вижу. Ткните, пожалуйста, пальцем. Тут некоторые странности. По терминологии Мендельсона $B_j^n(s^*(t_1), \dots, s^*(t_n))$ - формула, а $B_j^n$ предикатная буква. А тут он пишет, что $B_j^n$ отношение. В дальнейших изданиях обозначение изменено, но смысл остался тот же.

Я понимаю, что нет, я говорю что это одно удобное обозначение для '(x, y) \in R'.
Могу сослаться на Алгебраические системы Мальцева, где на странице 17 написано:

"Если $(a, b ) \in \alpha$, то говорят, что элемент $a$ находится в отношении $\alpha$ к элементу $b$ или что отношение $\alpha$ для $a$, $b$ истинно. Вместо
$(a, b) \in \alpha$ пишут $a\alpha b$ или $\alpha(a, b)$".

А у Мендельсона и правда, про это ничего не сказано.

но $B_j^n(s^*(t_1), \dots, s^*(t_n))$ это никаким образом не формула. Это как раз запись того что набор элементов $(s^*(t_1), \dots, s^*(t_n))$ находится в отношении $B_j^n$.

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

Ещё пару языковых проблем в Мендельсоне. На странице 54 определены предикатная буква $A_j^n$ и функциональная буква $f_j^n$, но тут же говорится просто о предметных (индивидных) переменных и константах. Логичнее было бы назвать их буквами.

Я привык вообще к названиям 'функциональный символ', 'предикатный символ', 'константный символ' и 'переменная'. Но ничё не поделаешь как написано, так написано.

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

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

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

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

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

А у Мендельсона и правда, про это ничего не сказано.

но $B_j^n(s^*(t_1), \dots, s^*(t_n))$ это никаким образом не формула. Это как раз запись того что набор элементов $(s^*(t_1), \dots, s^*(t_n))$ находится в отношении $B_j^n$.

На том и порешили. Но запись двусмысленная. Кстати, это почувствовал и сам Мендельсон в последующих изданиях он заменил $B_j^n$ на $(A_j^n)^M$ при том интерпретация получила имя $M{.}$ В итоге формула стала выглядеть $$(A_j^n)^M(s^*(t_1), \dots, s^*(t_n))$

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

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

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

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

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

[mkot]

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

На том и порешили. Но запись двусмысленная. Кстати, это почувствовал и сам Мендельсон в последующих изданиях он заменил $B_j^n$ на $(A_j^n)^M$ при том интерпретация получила имя $M{.}$ В итоге формула стала выглядеть $$(A_j^n)^M(s^*(t_1), \dots, s^*(t_n))$

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

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

«Терм $t$ называется свободным для переменной $x_i$ в формуле $\mathcal{A}{,}$ если никакое свободное вхождение $x_i$ в $\mathcal{A}$ не лежит в области действия никакого квантора $\forall x_j{,}$ где $x_j$ — переменная, входящая в $t{.}$» Страница 56.
Все понятно. Хочется, чтобы, вставляя какой-либо терм вместо переменной, не получить внутри связанную переменную. Фраза чуть ниже вроде бы подтверждает эту мысль: «(c) Терм $t$ свободен для любой переменной в формуле $\mathcal{A}{,}$ если никакая переменная терма $t$ не является связанной переменной в $\mathcal{A}{.}$»
И вдруг ещё чуть ниже: «(d) $x_i$ свободно для $x_i$ в любой формуле.» Это как? $x_i$ свободно для $x_i$ в $\forall x_iA_1^1(x_i){?}$
И ещё ниже: «(e) Всякий терм свободен для $x_i$ в $\mathcal{A}{,}$ если $\mathcal{A}$ не содержит свободных вхождений $x_i{.}$» И опять тот же пример $x_i$ свободно для $x_i$ в $\forall x_iA_1^1(x_i){?}$ Здесь $x_i$ входит не свободно.

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

Страница 57. «Для данной интерпретации всякая формула без свободных переменных (или, иначе, замкнутая формула) представляет собой высказывание, которое истинно или ложно,» В этой половине фразы все понятно.

Вот вторая половина той же фразы: «а всякая формула со свободными переменными выражает некоторое отношение на области интерпретации; это отношение может быть выполнено (истинно) для одних значений переменных из области интерпретации и не выполнено (ложно) для других.»
А со второй половиной этой же фразы проблемы. Смысл ясен. Существует множество n-ок, подставляя которые в формулу получаем истинное высказывание и существует множество n-ок, подставляя которые в формулу получаем ложное высказывание. А больше никаких n-ок нет.

Проблема, в том КАК эта мысль выражена. «всякая формула со свободными переменными выражает некоторое отношение на области интерпретации;» Пусть у нас есть область интерпретации $D{.}$ Согласно определению на странице 12 «Под n-местным отношением (отношением с n аргументами) на множестве $X$ мы понимаем всякое подмножество множества $X^n{,}$ т. е. всякое множество n-ок элементов $X{.}$» Т. е. с нашей формулой ассоциируется некоторое n-местное отношение (подмножество множества $D^n{).}$ Пока всё понятно.

Идем дальше: «это отношение может быть выполнено (истинно) для одних значений переменных из области интерпретации и не выполнено (ложно) для других.» А вот тут всё в дыму.

Первый вопрос: Как отношение может быть выполнено(истинно)? Отношение – это множество. Как множество может быть истинным или выполненным? (Повторяю: вопрос чисто формальный, я понимаю, что речь идет о том, что для n-ок из этого отношения формула превращается в истинное высказывание).

Второй вопрос: Но дальше ещё стрёмнее: А как тоже самое отношение может быть ложным? Как множество может быть ложным?

[Xaositect]

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

«Терм $t$ называется свободным для переменной $x_i$ в формуле $\mathcal{A}{,}$ если никакое свободное вхождение $x_i$ в $\mathcal{A}$ не лежит в области действия никакого квантора $\forall x_j{,}$ где $x_j$ — переменная, входящая в $t{.}$» Страница 56.
Все понятно. Хочется, чтобы, вставляя какой-либо терм вместо переменной, не получить внутри связанную переменную. Фраза чуть ниже вроде бы подтверждает эту мысль: «(c) Терм $t$ свободен для любой переменной в формуле $\mathcal{A}{,}$ если никакая переменная терма $t$ не является связанной переменной в $\mathcal{A}{.}$»
И вдруг ещё чуть ниже: «(d) $x_i$ свободно для $x_i$ в любой формуле.» Это как? $x_i$ свободно для $x_i$ в $\forall x_iA_1^1(x_i){?}$
И ещё ниже: «(e) Всякий терм свободен для $x_i$ в $\mathcal{A}{,}$ если $\mathcal{A}$ не содержит свободных вхождений $x_i{.}$» И опять тот же пример $x_i$ свободно для $x_i$ в $\forall x_iA_1^1(x_i){?}$ Здесь $x_i$ входит не свободно.

Беглым просмотром не нашел определения подстановки у Мендельсона, но подозреваю, что подстановка идет только на свободные вхождения, а для связанных допускается только переименование.
Тогда, соответственно, любая подстановка в формулу $\forall x P(x)$ оставит ее такой, какой есть, и риска связывания свободной переменной нет. Соответственно, любой терм является свободным для $x$.
И с определением это согласуется: «Терм $t$ называется свободным для переменной $x_i$ в формуле $\mathcal{A}{,}$ если никакое свободное вхождение $x_i$ в $\mathcal{A}$ не лежит в области действия никакого квантора $\forall x_j{,}$ где $x_j$ — переменная, входящая в $t{.}$»

-- Ср май 11, 2011 18:47:51 --

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

Первый вопрос: Как отношение может быть выполнено(истинно)? Отношение — это множество. Как множество может быть истинным или выполненным? (Повторяю: вопрос чисто формальный, я понимаю, что речь идет о том, что для n-ок из этого отношения формула превращается в истинное высказывание).

Второй вопрос: Но дальше ещё стрёмнее: А как тоже самое отношение может быть ложным? Как множество может быть ложным?

Там перед этим некоторое пояснение есть («Напомним, что всякое $n$-местное отношение в $D$ может рассматриваться...») Т.е. есть неформальное понятие отношения (объекты находятся в некотором отношении, отношение истинно/ложно на некотором наборе объектов) и есть его формализация — отношение как множество $n$-ок.
Лично я не вижу ничего страшного в том, что говорится «Отношение истинно/ложно на наборе», если понятно, что это значит.

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

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

Беглым просмотром не нашел определения подстановки у Мендельсона, но подозреваю, что подстановка идет только на свободные вхождения, а для связанных допускается только переименование.

Если не вру, то подстановка термов у Мендельсона на второй половине страницы 58.

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

если никакое свободное вхождение $x_i$ в $\mathcal{A}$

Всю жизнь – проблема со слонами. Слона, выделенного жирным шрифтом, я и не приметил. Спасибо.

-- Ср май 11, 2011 16:24:35 --

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

Там перед этим некоторое пояснение есть («Напомним, что всякое $n$-местное отношение в $D$ может рассматриваться...») Т.е. есть неформальное понятие отношения (объекты находятся в некотором отношении, отношение истинно/ложно на некотором наборе объектов) и есть его формализация — отношение как множество $n$-ок.
Лично я не вижу ничего страшного в том, что говорится «Отношение истинно/ложно на наборе», если понятно, что это значит.

Тут дело несколько хуже. Фраза: «Напомним, что всякое n-местное отношение в $D$ может рассматриваться как некоторое подмножество $D^n$ всех n-ок элементов из $D{.}$» всего лишь калька с определения на странице 12: «Под n-местным отношением (отношением с n аргументами) на множестве $X$ мы понимаем всякое подмножество множества $X^n{,}$ т. е. всякое множество n-ок элементов $X{.}$» Поэтому, как мне кажется, ничего (кроме напоминания об определении) нам не дает. Я, конечно, понимаю, что Мендельсон не бурбаковская «Теория множеств», но это тоже формализм и хотелось бы понимать текст дословно. Хотя смысл-то ясен.

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

Поскольку с помощью Xaositect и некоторой собственной настойчивости мне удалось слегка продвинуться в Мендельсоне и даже найти опечатку, то появились новые вопросы. Итак, страница 57: «Формулы имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Под интерпретацией мы будем понимать всякую систему, состоящую из непустого множества $D{,}$ называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве $A_j^n$ некоторое n-местное отношение в $D{,}$ каждой функциональной букве $f_j^n$ — некоторую n-местную операцию в $D$ (т. е. функцию, отображающую $D^n$ в $D{)}$ и каждой предметной постоянной $a_i$ — некоторый элемент из $D{.}$»
Итак, интерпретация – это система, состоящая из двух элементов множества $D$ и соответствия (естественно это тоже множество). Назовем соответствие $S{.}$ Таким образом интерпретация – это пара $\left\{D, S\right\}{.}$

Вопрос первый: Интерпретация чего? Ответ: Интерпретация символов, входящих в формулы. Есть ли какое-нибудь обобщающее название этих формул? Это ли потом будет интепретацией теории?

Вопрос второй: «... соответствия, относящего ... каждой предметной постоянной $a_i$ — некоторый элемент из $D{.}$» Правильно ли я понимаю, что, отнеся хотя бы одной предметной постоянной другой элемент из $D{,}$ получаем другую интерпретацию?

Вопрос третий: все таже проблема с истинным отношением, но слегка с другой стороны: «... соответствия, относящего ... каждой функциональной букве $f_j^n$ — некоторую n-местную операцию в $D$ (т. е. функцию, отображающую $D^n$ в $D{)}$» -- с функциональной буквой все чисто, правда, подстановка термов (стр. 58) делается по весьма строгим правилам функция, упомянутая в скобках не есть та самая функциональная буква $f{,}$ а совсем другая функция $g{.}$ Но зато всё понятно. А вот с предикатной буквой всё ещё проблемы (старые и новые). «... соответствия, относящего каждой предикатной букве $A_j^n$ некоторое n-местное отношение в $D{,}$» Воспользовавшись намеком Xaositect «Там перед этим некоторое пояснение есть («Напомним, что всякое $n$-местное отношение в $D$ может рассматриваться...»)», я увидел, что неформально речь идет о некотором условии, соответствующем отношению, но формально не обнаружил и намека на это условие. К тому же «...предикатной букве $A_j^n$ некоторое n-местное отношение в $D{,}$» -- это максимальное отношение на котором эта формула выполнима или нет? По смыслу должно быть максимальное, но в формализованых ситуациях додумывать опасно.

И, наконец, опечатка на странице 57. Напечатано: «iii $\exists x_2\forall x_1A_1^2(x_2, x_1)$» и как водится перепутан порядок индексов. Нужно: «iii $\exists x_1\forall x_2A_1^2(x_1, x_2)$»

[Xaositect]

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

Вопрос первый: Интерпретация чего? Ответ: Интерпретация символов, входящих в формулы. Есть ли какое-нибудь обобщающее название этих формул? Это ли потом будет интепретацией теории?

Интерпретация сигнатуры(алфавита). То есть мы пока сопоставляем значение только символам. Потом определяется выполнимости формулы при конкретных значениях переменных и общезначимости формулы, а потом уже можно говорить об интерпретации теории - это такая интерпретация, в которой общезначимы все формулы, выводимые в этой теории.

Второй вопрос - да.

Третий - ответ на этот вопрос дается определением выполнимости. Формула $A_j^n(t_1,\dots t_n)$ будет выполнима (в некоторой интерпретации, на некоторой последовательности значений переменных) тогда и только тогда, когда соответствующее ей отношение выполняется на наборе соответствующих значений $t_i$. То есть это именно то отношение, на котором формула выполнима. Оно единственно.

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

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

Третий - ответ на этот вопрос дается определением выполнимости. Формула $A_j^n(t_1,\dots t_n)$ будет выполнима (в некоторой интерпретации, на некоторой последовательности значений переменных) тогда и только тогда, когда соответствующее ей отношение выполняется на наборе соответствующих значений $t_i$. То есть это именно то отношение, на котором формула выполнима. Оно единственно.

Вот тут я запутался окончательно (формально, конечно). Поэтому пример (на той же странице 57). «Если мы берем в качестве области множество целых положительных чисел и интерпретируем $A_1^2(y, z)$ как $y\leq x{,}$ то $A_1^2(x_1, x_2)$ представляет отношение $y\leq x{,}$ которое выполнено для всех упорядоченных пар $(a, b)$ целых положительных чисел таких, что $a\leq b{;}$»
Есть формула: $y\leq x{.}$ Есть область интепретации: множество всех целых положительных чисел. И есть соответствие, относящее предикатной букве $A_1^2$ $2$-местное отношение в множестве всех целых положительных чисел. Это $2$-местное отношение – множество пар $(a, b)$ где $a\leq b{.}$ Но, где сказано, что это множество всех таких пар? Почему нельзя «отнести» только, скажем, пары с чётным $b{?}$ Вот я спрашиваю: имеется ли в виду только такое множество пар, в которое, добавив ещё одну пару, мы «выпадаем из выполнимости»? В Вашем определении жестче. У Вас появилось «тогда и только тогда». В этом случае мой вопрос отпадает. Но у Мендельсона нет этого вполне логичного здесь «тогда и только тогда».

[Xaositect]

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

Но у Мендельсона нет этого вполне логичного здесь "тогда и только тогда".

Есть. Формальное определение выполнимости — 59 страница сверху: «(i) Если $\mathcal{A}$ есть элементарная формула $A^n_j(t_1,\dots,t_n)$ и $B_j^n$ есть соответствующее ей отношение в интерпретации, то формула $\mathcal{A}$ является выполненной на последовательности $\mathrm{s}^*$ в том и только в том случае, когда $B_j^n(\mathrm{s}^*(t_1),\dots,\mathrm{s}^*(t_n))$, то есть $n$-ка $(\mathrm{s}^*(t_1),\dots,\mathrm{s}^*(t_n))$ принадлежит отношению $B_j^n$»

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