2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 11  След.
 
 Математическая логика (по Мендельсону)
Сообщение08.04.2011, 20:38 
Заслуженный участник
Аватара пользователя


04/04/09
1351
«(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$). Итак, где опечатка у Мендельсона или у меня в голове?

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение08.04.2011, 21:30 
Аватара пользователя


18/10/08
454
Омск
У Мендельсона всё верно.

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

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение08.04.2011, 21:58 
Заслуженный участник
Аватара пользователя


04/04/09
1351
Нас страницах 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$ отношение. В дальнейших изданиях обозначение изменено, но смысл остался тот же.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение09.04.2011, 00:49 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение09.04.2011, 09:26 
Аватара пользователя


18/10/08
454
Омск
Виктор Викторов в сообщении #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-й компонентой.


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

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение09.04.2011, 17:10 
Заслуженный участник
Аватара пользователя


04/04/09
1351
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-й компонентой.

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

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

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение09.04.2011, 17:39 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение11.05.2011, 00:45 
Заслуженный участник
Аватара пользователя


04/04/09
1351
«Терм $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$ входит не свободно.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение11.05.2011, 04:24 
Заслуженный участник
Аватара пользователя


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

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

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

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

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

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

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение11.05.2011, 18:38 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Виктор Викторов в сообщении #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$-ок.
Лично я не вижу ничего страшного в том, что говорится «Отношение истинно/ложно на наборе», если понятно, что это значит.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение11.05.2011, 23:02 
Заслуженный участник
Аватара пользователя


04/04/09
1351
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{.}$» Поэтому, как мне кажется, ничего (кроме напоминания об определении) нам не дает. Я, конечно, понимаю, что Мендельсон не бурбаковская «Теория множеств», но это тоже формализм и хотелось бы понимать текст дословно. Хотя смысл-то ясен.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение13.05.2011, 02:14 
Заслуженный участник
Аватара пользователя


04/04/09
1351
Поскольку с помощью 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)$»

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение13.05.2011, 11:53 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Виктор Викторов в сообщении #445277 писал(а):
Вопрос первый: Интерпретация чего? Ответ: Интерпретация символов, входящих в формулы. Есть ли какое-нибудь обобщающее название этих формул? Это ли потом будет интепретацией теории?
Интерпретация сигнатуры(алфавита). То есть мы пока сопоставляем значение только символам. Потом определяется выполнимости формулы при конкретных значениях переменных и общезначимости формулы, а потом уже можно говорить об интерпретации теории - это такая интерпретация, в которой общезначимы все формулы, выводимые в этой теории.

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

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

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение13.05.2011, 16:59 
Заслуженный участник
Аватара пользователя


04/04/09
1351
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{?}$ Вот я спрашиваю: имеется ли в виду только такое множество пар, в которое, добавив ещё одну пару, мы «выпадаем из выполнимости»? В Вашем определении жестче. У Вас появилось «тогда и только тогда». В этом случае мой вопрос отпадает. Но у Мендельсона нет этого вполне логичного здесь «тогда и только тогда».

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение13.05.2011, 19:31 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Виктор Викторов в сообщении #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$»

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 157 ]  На страницу 1, 2, 3, 4, 5 ... 11  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group