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

[beroal]

(Оффтоп)

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

Так как тег не позволяет использовать кириллицу, то букву «Г» я везде заменяю на «G».

$\Gamma$ Кириллицу они не используют, дальше по алфавиту идёт $\Delta$.

-- Fri May 27, 2011 22:05:55 --

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

Ещё один вопрос. «Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации.» Страница 62. Если какой-нибудь универсум, из которого мы черпаем область интерпретации?

На странице 57 написано, что такое интерпретация. Это ещё называется структура=structure.

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

beroal в сообщении #450961 писал(а):

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

Ещё один вопрос. «Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации.» Страница 62. Если какой-нибудь универсум, из которого мы черпаем область интерпретации?

На странице 57 написано, что такое интерпретация. Это ещё называется структура=structure.

Что такое интерпретация очевидно. Вопрос где берут то самое непустое множество $D$ -- область интепретации. Ведь чтобы быть истинным в каждой интерпретации, мы должны знать какие множества проверять.

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

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

Ещё один вопрос. «Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации.» Страница 62. Если какой-нибудь универсум, из которого мы черпаем область интерпретации?

Вопрос разрешён. Доказывая на странице 71, что «Во всяком исчислении предикатов первого порядка всякая теорема является логически общезначимой.» Мендельсон говорит об общезначимости первых трех аксиом. При таком подходе становится ясным, что значит для области интерпретации быть любой.

Правда это интересное высказывание соседствует со странной фразой «В силу свойств (X) (следствие) и (XI), логически верны аксиомы, порождаемые схемами (4) — (5).» Что значит, что аксиомы «логически верны»? Тем более, что перед этой фразой написано: «... аксиомы, задаваемые схемами (1) — (3), логически общезначимы.» Это опять проблемы перевода в оригинале написано «logically valid», что значит «логически общезначимы» в обоих случаях. Таким образом, текст должен быть таким: «... аксиомы, задаваемые схемами (1) — (3), логически общезначимы. В силу свойств (X) (следствие) и (XI), логически общезначимы аксиомы, порождаемые схемами (4) — (5).»

[beroal]

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

beroal в сообщении #450961 писал(а):

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

Ещё один вопрос. «Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации.» Страница 62. Если какой-нибудь универсум, из которого мы черпаем область интерпретации?

На странице 57 написано, что такое интерпретация. Это ещё называется структура=structure.

Что такое интерпретация очевидно. Вопрос где берут то самое непустое множество $D$ -- область интепретации. Ведь чтобы быть истинным в каждой интерпретации, мы должны знать какие множества проверять.

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

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

beroal в сообщении #451063 писал(а):

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

Речь шла не о «размере», а о том, «чтобы на нём [множестве] можно было задать функции и отношения». Мне стало ясно, что это зависит от соотношений, а не от множества. Вот простой пример: $A(x)\to (B(x)\to A(x))$. Можно ли рассмотреть область интерпретации, состоящую из лошади и коровы? Да, конечно, можно. Как Вы и написали, достаточно задать соответствующие функции. Т. е. вопрос решается на уровне структуры формулы для любой интерпретации. В этом и есть смысл логической общезначимости формул.

-- Сб май 28, 2011 09:50:15 --

Чем больше я вчитываюсь в Мендельсона, тем больше выползает вопросов. Вот ещё один:
«Формула $\mathscr A$ называется следствием множества формул Г в $\mathscr G$ тогда и только тогда, когда существует такая последовательность формул $\mathscr A_1, \cdots, \mathscr A_n,$ что $\mathscr A_n$ есть $\mathscr A$, и для любого $i$ $\mathscr A_i$ есть либо аксиома, либо элемент Г, либо непосредственное следствие некоторых предыдущих формул по одному из правил вывода.» Страница 37.
«Формула $\mathscr A$ теории $\mathscr G$ называется теоремой теории $\mathscr G$, [?] если существует вывод в $\mathscr G$, в котором последней формулой является $\mathscr A$; такой вывод называется выводом формулы $\mathscr A$.» Страница 36.
Ясно, что определение «следствия» от «теоремы» отличает наличие гипотез в определении «следствия». Но почему в определении «теоремы» выпали слова «тогда и только тогда»? Причем это уже проблемы оригинала.

[Xaositect]

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

Ясно, что определение «следствия» от «теоремы» отличает наличие гипотез в определении «следствия». Но почему в определении «теоремы» выпали слова «тогда и только тогда»? Причем это уже проблемы оригинала.

В определениях и так, и так пишут. Подразумевается, разумеется, тогда и только тогда.

По поводу класса интерпретаций - он, разумеется, является собственным классом, но с утверждениями типа "в любой интерпретации" ничего страшеного не происходит. Точно так же, как можно говорить "Для всех множеств".

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

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

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

Ясно, что определение «следствия» от «теоремы» отличает наличие гипотез в определении «следствия». Но почему в определении «теоремы» выпали слова «тогда и только тогда»? Причем это уже проблемы оригинала.

В определениях и так, и так пишут. Подразумевается, разумеется, тогда и только тогда.

Конечно. Но здесь на расстоянии в полстраницы!

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

По поводу класса интерпретаций - он, разумеется, является собственным классом, но с утверждениями типа "в любой интерпретации" ничего страшеного не происходит. Точно так же, как можно говорить "Для всех множеств".

Да, но я это не сразу понял!

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

(Оффтоп)

Если бы я был писателем, то написал бы роман под названием: «Эти две страницы (36 и 37)».

(i) $G \vdash \mathscr A$ тогда и только тогда, когда в $G$ существует конечное подмножество $\Delta$, для которого $\Delta \vdash \mathscr A$.
(ii) Если $\Delta\subseteq G$ и $\Delta\vdash \mathscr A$, то $ G\vdash\mathscr A$.
(iii) Если $G\vdash \mathscr B$ для любого $\mathscr B$ из множества $\Delta$ и $\Delta \vdash\mathscr A$, то $G\vdash \mathscr A$.

Я изменил порядок и переобозначил кое-какие буквы в свойствах понятия выводимости на странице 37. Стало ясно видно, что (ii) это слегка ограниченное «тогда» в (i), а (iii) слегка расширенное «тогда» из (i).

[beroal]

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

Стало ясно видно, что (ii) это слегка ограниченное «тогда» в (i), а (iii) слегка расширенное «тогда» из (i).

Так ещё красивее:
(i) $\forall \Gamma \mathscr A. (\exists \Delta\subseteq \Gamma. \Delta \vdash \mathscr A \land finite(\Delta)) \leftrightarrow \Gamma\vdash \mathscr A$
(ii) $\forall\Gamma\mathscr A. (\exists \Delta\subseteq \Gamma. \Delta\vdash\mathscr A) \to \Gamma\vdash\mathscr A$
Я бы сказал, что (ii) — это более сильное утвеждение, чем импликация слева направо в (i).

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

beroal в сообщении #451489 писал(а):

(i) $\forall \Gamma \mathscr A. (\exists \Delta\subseteq \Gamma. \Delta \vdash \mathscr A \land finite(\Delta)) \leftrightarrow \Gamma\vdash \mathscr A$
(ii) $\forall\Gamma\mathscr A. (\exists \Delta\subseteq \Gamma. \Delta\vdash\mathscr A) \to \Gamma\vdash\mathscr A$

Теперь я знаю как пишется в теге $\Gamma$. К сожалению, не понимаю смысл самих формул, так как не знаю, что обозначает в данном контексте точка.

Что же касается трех формул:
(i) $ \Gamma \vdash \mathscr A$ тогда и только тогда, когда в $\Gamma $ существует конечное подмножество $\Delta$, для которого $\Delta \vdash \mathscr A$.
(ii) Если $\Delta\subseteq \Gamma$ и $\Delta\vdash \mathscr A$, то $\Gamma \vdash\mathscr A$.
(iii) Если $\Gamma \vdash \mathscr B$ для любого $\mathscr B$ из множества $\Delta$ и $\Delta \vdash\mathscr A$, то $\Gamma \vdash \mathscr A$.

Свойство (ii) не есть в чистом виде «тогда» свойства (i) поскольку $\Delta$ может быть и бесконечным множеством, но в $\Delta$ по свойству (i) «сидит» конечное подмножество из которого существует вывод $\mathscr A$. И из этого уже в одну строчку выводится свойство (ii).
Аналогично со свойством (iii). Если любая формула $\mathscr B$ из множества $\Delta$ выводима из множества $\Gamma$, то частным случаем этого свойства будет случай, когда каждая формула $\mathscr B$ принадлежит множеству $\Gamma$. И опять мы попадаем в круг свойств (ii) и (i).

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

Есть такая «Лемма 1.12. Пусть $\mathscr A$ есть формула, а $B_1, \cdots, B_k$ — пропозициональные буквы, входящие в $\mathscr A$, и пусть задано некоторое распределение истинностных значений для $B_1, \cdots, B_k$. Пусть тогда $B'_i$ есть $B_i$, если $B_i$ принимает значение И, и $\neg B_i$, если $B_i$ принимает значение Л, и пусть, наконец, $\mathscr A'$ есть $\mathscr A$, если при этом распределении $\mathscr A$ принимает значение И, и $\neg \mathscr A$, если $\mathscr A$ принимает значении Л. Тогда $B'_1, \cdots, B'_k\vdash \mathscr A'$.» Страница 43.
Эта лемма часть доказательства того факта, что «... формула теории L тогда и только тогда является теоремой этой теории, когда она есть тавтология.» Но с другой стороны из этой леммы видно, что каждой пропозициональной форме в исчислении высказываний неким естественным образом соответствует множество тавтологий. Точнее говоря, каждой пропозициональной форме соответствует ровно столько тавтологий сколько строк в истинностной таблице этой пропозициональной формы. Например, высказыванию $A\to B$ соответствуют четыре тавтологии:

$$A\to (B\to (A\to B))$$

$$A\to (\negB\to \neg (A\to B))$$

$$\neg A\to (B\to (A\to B))$$

$$\neg A\to (\neg B\to (A\to B))$$

и самый простой пример: высказыванию $A$ соответствуют две тавтологии:

$$A\to A$$

$$\neg A\to \neg A$$

[beroal]

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

К сожалению, не понимаю смысл самих формул, так как не знаю, что обозначает в данном контексте точка.

Точка просто отделяет переменные, которые связывает квантор, от всего остального.

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

beroal в сообщении #451825 писал(а):

Точка просто отделяет переменные, которые связывает квантор, от всего остального.

Спасибо. Дошло.

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

Свожу воедино, что такое терм и зачем это понятие нужно:
«(1) Задано некоторое счетное множество символов — символов теории $\mathscr G$. Конечные последовательности символов теории $\mathscr G$ называются выражениями теории $\mathscr G$.
(2) Имеется подмножество выражений теории $\mathscr G$, называемых формулами теории $\mathscr G$.» Страница 36.

«...предметные (индивидные) переменные $x_1, x_2, \cdots, x_n, \cdots$,
предметные (индивидные) константы $a_1, a_2, \cdots, a_n, \cdots$,
предикатные буквы $A_1^1, A_1^2, \cdots, A_k^j, \cdots$, и
функциональные буквы $f_1^1, f_1^2, \cdots, f_k^j, \cdots$.
...
(a) всякая предметная переменная или предметная константа есть терм;
(b) если $f_k^j$ — функциональная буква и $t_1, t_2, \cdots, t_n$ — термы, то $f_k^j(t_1, t_2, \cdots, t_n)$ есть терм;
(c) выражение является термом только в том случае, если это следует из правил (a) и (b).» Страница 54.

Итак, предметная переменная $x_n$ — символ (причём единый). Т. е. надо признать, что речь идет о выражении — конечной последовательности длины один. Причем $x_n$ не формула, т. к. формула должна начинаться с предикатной буквы. Точно тоже нужно сказать о предметной константе. Различаться переменная и константа будут только в интерпретации. Пока переменные берутся с конца латинского алфавита, а константы с его начала. Чуть хуже с пунктом (b). Здесь терм это выражение — конечная последовательность из $n+3$ символов, где первый символ функциональная буква, второй круглая скобка, затем $n$ термов и ещё одна скобка. Здесь всё было бы хорошо, но не возникает ли ситуация, где мы определяем понятие через само себя? А если мы захотим, чтобы один из $n$ термов был ровно тот, который мы определяем? Всё это нам нужно, чтобы отделить предметы (элементы множеств) от тех «коробочек», в которые мы эти предметы по строго регламентированным правилам будем подставлять. Иначе, все операции придется каждый раз описывать заново для новой последовательности элементов.

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

Следующий этап заключается в том, чтобы подставлять термы в термы и элементы области интерпретации в термы. Обе эти проблемы решены Мендельсоном с блеском, но доведены до читателя без блеска. Я уже страдал по поводу терма, свободного для переменной в формуле. А дело-то весьма простое. Можно подставить терм в формулу вместо свободного вхождения другого терма. Но, в подставляемом терме могу быть свои свободные переменные. И, конечно, хочется, чтобы эти свободные переменные не оказались связанными в формуле, в которую они попали. Всё весьма просто. Но на это неформальное объяснение автора не хватило.
Теперь, о подстановке элементов области определения интерпретации в терм. Здесь имеет место быть изрядная путаница.
«Таким образом, $s^*$ — это функция, определяемая последовательностью $s$ и отображающая множество всех термов в D. Если говорить неформально, то для любой последовательности $s = (b_i, b_2, \cdots)$ и для любого терма $t$ $s^*(t)$ есть элемент множества $D$, который получается в результате подстановки при каждом $i$ элемента $b_i$ на места всех вхождений переменной $x_i$ в терм $t$ и затем выполнения всех операций интерпретации, соответствующих функциональным буквам терма $t$.» Страница 58.
Это просто ошибка. Таким образом отображаются только переменные. Переменные действительно определяются на последовательности $s$. И если взять другую последовательность, то функция будет другая. Но есть ещё и константы и они для всех последовательностей одинаковы в данной интерпретации. Т. е. константы зависят только от «соответствия, относящего ... каждой предметной постоянной $a_i$ — некоторый элемент из $D$.»