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

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

«Предложение 2.7. Во всяком исчислении предикатов первого порядка всякая теорема является логически общезначимой.
Доказательство. В силу свойства (VII) понятия истинной формулы (см. стр. 60), аксиомы, задаваемые схемами (1) — (3), логически общезначимы. В силу свойств (X) (следствие) и (XI), логически верны аксиомы, порождаемые схемами (4) — (5). В силу (III) и (VI), правила вывода МР и Gen сохраняют свойство логической общезначимости. Таким образом, всякая теорема любого исчисления предикатов логически общезначима.»

Пополним список переводческих ляпов. Что значит «логически верны»? Задавать этот вопрос Мендельсону бессмысленно у него во всех трех случаях написано «logically valid» т. е. в русской терминологии «логически общезначимы».

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

Несколько странных странностей.

Странность 1. «Всякое предложение какого-нибудь формального или естественного языка называется логически истинным (в исчислении предикатов), если оно является частным случаем некоторой логически общезначимой формулы, и называется логически ложным (в исчислении предикатов), если оно есть частный случай некоторого противоречия (в исчислении предикатов).» Страница 63.
Или в оригинале: «Any sentence of a formal or natural language which is an instance of a logically valid wf is called logically true, and an instance of a contradictory wf is said to be logically false.»

Прежде чем разбирать этот отрывок, я хотел бы понять, что значит для предложения быть «частным случаем некоторой логически общезначимой формулы». Есть только определение частного случая пропозициональной формы. Страница 60. Причем этот отрывок отсутствует в четвертом и пятом изданиях. Я бы не привязывался к этому отрывку. Он стоит особняком и не мешает пониманию текста.
Но,
Странность 2. В доказательстве того факта, что каждая теорема исчисления первого порядка является логически общезначимой (стр. 71), используется такой оборот: «В силу свойства (VII) понятия истинной формулы (см. стр. 60), ...». Или в оригинале: «By property (VII) of the notion of truth (cf. page 53), ...». Но на странице 60 в свойстве (VII) нет ничего об истинной формуле. Там речь идет о формуле, истинной в данной интерпретации (определение на странице 59).
Вообще говоря, вся фраза: «В силу свойства (VII) понятия истинной формулы (см. стр. 60), аксиомы, задаваемые схемами (1) — (3), логически общезначимы.» не пострадает (и станет более осмысленной), если кусок «понятия истинной формулы» просто выкинуть: «В силу свойства (VII) [...] аксиомы, задаваемые схемами (1) — (3), логически общезначимы.» Так как схемы (1) — (3) действительно логически общезначимы как частные случаи тавтологий.

(Оффтоп)

Но некоторые свойства моего характера (склочность) заставляют меня спросить: может быть, я что-то не понял?

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

(Оффтоп)

Продолжаю неделю переводчика.

«2. Если формула $\mathscr A$ не содержит кванторов и доказуема в исчислении предикатов, ...» Страница 72. А что значит «формула доказуема»? Лезем в оригинал. Там напечатано «provable». Вроде бы правильно. Но... переводчик на странице 36 перевел «proof» как «вывод». Поэтому, конечно, должно быть «2. Если формула $\mathscr A$ не содержит кванторов и выводима в исчислении предикатов, ...» Но это мелочь. Вот более таинственная история.

«Лемма 2.10. Множество всех выражений всякой теории первого порядка счетно (следовательно, счетны в частности: множество всех термов, множество всех формул, множество всех замкнутых формул).
Доказательство. Отнесем каждому символу $u$ нечетное число $g(u)$ по следующему правилу: $ g( ( )=3$, $g( ) ) = 5$, $g(,) = 7$, $g(\neg) = 9$, $g(\to) = 11$, $g(x_k)=5+8k$, $g(a_k)=7+8k$ , $g(f_k^n) =9+ 8\cdot (2^{n} \cdot 3^{n})$, $g(A_k^n) =11+ 8\cdot (2^{n} \cdot 3^{n})$ [; при этом полагаем $g(\forall x_i)=g((x_i))$]. Теперь выражению $u_0u_1\cdots u_r$ отнесем число $2^{g(u_0)}3^{g(u_1)}\cdots p_r^{g(u_r)}$, Где $p_i$ — $i$-e простое число.»

Что значит "при этом полагаем $g(\forall x_i)=g((x_i))$"? Я поставил этот кусок в квадратные скобки т. к. его нет в первом русском издании 1971 года. Он появился во втором русском издании 1976 года. Как я уже и писал в первых изданиях оригинала забыли ввести в символы теории К символ квантора $\forall$. Здесь же он явно нужен так как нужно значение $g(\forall)$. Что такое $g(\forall x_i)$ вообще тайна, ведь функция $g$ требует в качестве аргумента только один символ, а здесь их сразу два ($ x_i$ рассматривается как единый символ). Еще большую таинственность предает этой истории факт, что во втором английском издании выражение $\forall x_i$ обозначается как $(x_i)$.

В пятом английском издании в символы теории К введен символ $\forall$. И доказательство переделано так: «First assign a distinct positive integer $g(u)$ to each symbol $u$ as follows: $g( ( )=3$, $g( ) ) = 5$, $g(,) = 7$, $g(\neg) = 9$, $g(\to) = 11$, $g(\forall) =13$, $g(x_k)=13+8k$, $g(a_k)=7+8k$ , $g(f_k^n) =1+ 8\cdot (2^{n} \cdot 3^{n})$, $g(A_k^n) =3+ 8\cdot (2^{n} \cdot 3^{n})$. Then, to an expression $u_0u_1\cdots u_r$, associate the number $2^{g(u_0)}3^{g(u_1)}\cdots p_r^{g(u_r)}$, where $p_j$ is the $j$th prime number, starting with $p_0=2$.»

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

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

Есть такая «Лемма 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.

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

...каждой пропозициональной форме соответствует ровно столько тавтологий сколько строк в истинностной таблице этой пропозициональной формы.

Есть и соответствующее доказательство. Но меня заинтересовал вопрос: как это продемонстрировать? Вот к чему я пришел.
Пусть у нас есть формула $\mathscr A$. Это любое высказывание может быть тавтология, а может быть и нет. И пусть все пропозициональные буквы этого высказывания: $A_1, A_2, \cdots, A_i, \cdots, A_n$. Тогда существуют ровно столько «выводимостей», ассоциированных с формулой $\mathscr A$, сколько строк у таблицы истинности этой формулы. И все они выглядят так: $?A_1, ?A_2, \cdots, ?A_i, \cdots, ?A_n\vdash ? \mathscr A$. Надо только правильно вместо знака «?» поставить символ $\neg$ или оставить это место пустым. Формула $?A_1, ?A_2, \cdots, ?A_i, \cdots, ?A_n\vdash ? \mathscr A$ после использования теоремы дедукции приводит к $\vdash ?A_1\wedge ?A_2\wedge \cdots\wedge ?A_i\wedge \cdots\wedge ?A_n\to ?\mathscr A$ . Это импликация и её посылкой является конъюнкция. А конъюнкция почти всегда ложна и поэтому данная импликация почти всегда истинна. Но что будет, когда это «почти всегда» не срабатывает, и конъюнкция истинна? Тогда все члены этой конъюнкции истинны. Вот тут-то и срабатывает «правильное» распределение символа $\neg$. Что это за случай когда все члены конъюнкции истинны? Посмотрим на строку распределения истинностных значений: там где стоит «истина» мы просто убираем знак вопроса, а там где стоит «ложь» заменяем знак вопроса на символ $\neg$. Это единственный способ получить истинную конъюнкцию. Вот теперь осторожно! Импликация может оказаться ложной! Но и мы настороже. Опять смотрим на строку распределения истинностных значений. Если высказывание $\mathscr A$ истинно, то проблем нет. А если оно ложно, то поставим перед ним символ $\neg$ и сделаем его истинным. Таким образом, единственный «подозрительный» случай тоже дает истинностное значение «истина» и высказывание $?A_1\wedge ?A_2\wedge \cdots\wedge ?A_i\wedge \cdots\wedge ?A_n\to ?\mathscr A$ -- тавтология.

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

В седьмом томе Большого академического словаря русского языка слово «интерпретация» описано как «истолкование, разъяснение смысла, значения чего-л.» (стр. 329).
Понадобилось мне лезть в этот словарь потому, что в математической логике дается определение термина «интерпретация» а как быть, если я хочу использовать слово «интерпретация» не в смысле этого определения мне не было ясно. Поэтому я пришёл к компромиссному решению: в этом случае я буду писать «истолкование (интерпретация)». Теперь к делу.

«Формулы имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Под интерпретацией мы будем понимать всякую систему, состоящую из непустого множества $D{,}$ называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве $A_j^n$ некоторое n-местное отношение в $D{,}$ каждой функциональной букве $f_j^n$ — некоторую n-местную операцию в $D$ (т. е. функцию, отображающую $D^n$ в $D$) и каждой предметной постоянной $a_i$ — некоторый элемент из $D{.}$» Страница 57.

И хотя первая и вторая фразы этого текста в пятом издании разделены разными разностями, но все равно меня этот текст удивляет. Вторая фраза дает определение интерпретации, и получается, что без, скажем, области интерпретации и разговаривать не о чем. Но вернем в первой фразе обычный смысл слову «интерпретация»: Формулы имеют смысл только тогда, когда имеется какое-нибудь истолкование (интерпретация) входящих в нее символов. Разве обязательно истолковывать эту фразу только в смысле определения данного дальше? Очевидно, что нет.

«... для логики предикатов синтаксический метод теорий первого порядка равносилен семантическому методу, использующему понятия интерпретации, модели, логической общезначимости и т. п.» Страница 79.

Вот теперь всё на своих местах. Определение интерпретации имеет смысл только для семантического метода. А при применении синтаксического метода теорий первого порядка нужно только истолкование (интерпретация) сигнатуры. Жить только с синтаксическим методом, конечно, не очень удобно (и это мягко сказано), но речь-то идет о принципе.

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

Одним из важных результатов пятого параграфа «Теоремы о полноте» является теорема Гёделя:
«Следствие 2.14. (Теорема Гёделя [1930] о полноте.) Во всяком исчислении предикатов первого порядка теоремами являются все те и только те формулы, которые логически общезначимы.» Страница 78.
Но почему она названа теоремой о полноте? Речь идет о «всяком исчислении предикатов первого порядка».

[Xaositect]

Есть два понятия полноты - дедуктивная и семантическая.
Дедуктивная - это когда для любой формулы $F$ выводима $F$ или $\neg F$
Семантическая - это когда все формулы, истинные в некотором класса интерпретаций, выводимы.
Теорема Геделя о полноте утверждает полноту исчисления предикатов первого порядка относительно класса всех возможных интерпретаций.

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

Спасибо. Первое понятие я знал, а второе - нет.

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

«Предложение 2.12*). Всякая непротиворечивая теория первого порядка имеет счетную модель (т. е. модель со счетной областью).» Страница 75. После этого следует интересное доказательство этого предложения на три страницы, включая следующее определение: «Назовем замкнутым термом всякий терм, не содержащий переменных.» Страница 76.

К пятому изданию это предложение было разбито на три части (по моему к лучшему) и добавилось одно экзотическое определение.
«DEFINITI0NS
1. A closed term is a term without variables.
2. A theory K is a scapegoat theory if, for any wf $\mathscr B(x)$ that has $x$ as its only free variable, there is a closed term $t$ such that

$$\vdash_K (\exists x)\neg \mathscr B(x)\Rightarrow \neg \mathscr B(t)$$

LEMMA 2.15 Every consistent theory K has a consistent extension K' such that K' is a scapegoat theory and K' contains denumerably many closed terms.» Страницы 80-81.

«LEMMA 2.16 Let $J$ be a consistent, complete scapegoat theory. Then $J$ has a model M whose domain is the set $D$ of closed terms of $J$.» Страница 82.

«PROPOSITION 2.17* Every consistent theory K has a denumerable model.» Страница 83.

В моем несовешенном переводе:
Определения.
1. Назовем замкнутым термом каждый терм, не содержащий переменных.
2. Назовем теорию K теорией козла отпущения, если для каждой формулы $\mathscr B(x)$, содержащей $x$ в качестве своей единственной свободной переменной, существует замкнутый терм $t$ такой, что

$$\vdash_K (\exists x)\neg \mathscr B(x)\Rightarrow \neg \mathscr B(t)$$

Лемма 2.15 Каждая непротиворечивая теория K имеет непротиворечивое расширение K' такое, что K' -- теория козла отпущения и K' содержит счетное множество замкнутых термов.
Лемма 2.16 Пусть $J$ непротиворечивая полная теория козла отпущения. Тогда $J$ имеет модель M, чьей областью является множество $D$ всех замкнутых термов теории $J$.
Предложение 2.17* Всякая непротиворечивая теория K имеет счетную модель.

[epros]

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

Теорема Геделя о полноте утверждает полноту исчисления предикатов первого порядка относительно класса всех возможных интерпретаций.

Ой, а напомните пожалуйста: Что именно является "истинным в классе всех возможных интерпретаций" (т.е. "логически общезначимым")? Вопрос в том, что предложение в языке исчисления предикатов можно сформулировать только тогда, когда определён хотя бы один функциональный символ и хотя бы один - предикатный. Т.е. мы должны считать, что определено столько функциональных и предикатных символов, а также переменных, сколько нам нужно (хотя прикладных аксиом в системе нет)?

P.S. Я раньше уже где-то получал ответ на этот вопрос, но, сорри, подзабыл...

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

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

[epros]

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

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

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

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

epros в сообщении #463007 писал(а):

Что именно является "истинным в классе всех возможных интерпретаций" (т.е. "логически общезначимым")?

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

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

epros в сообщении #463063 писал(а):

Это-то понятно.

Этот вопрос разрешён.
Теперь по поводу теории и «голого исчисления предикатов» по Мендельсону. На странице 66 дается определение: «Теория первого порядка, не содержащая собственных аксиом, называется исчислением предикатов первого порядка.» Но... «в исчислении предикатов» появляется раньше (например на странице 62). Я проверил второе английское издание. Никакого исчисления предикатов, появляющегося без всякого определения, начиная со страницы 54 русского издания, там просто нет. У меня есть пять изданий Мендельсона и мне жаль 15-ти долларов на первое английское издание (с которого и сделан русский перевод). Что касается «Проблема в том, что без предикатных и функциональных символов нельзя записать ни одной формулы», то, по моему, срабатывает импликация с ложной посылкой.

[epros]

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

На странице 66 дается определение: «Теория первого порядка, не содержащая собственных аксиом, называется исчисление предикатов первого порядка.»

Ага, понятно. Значит, мы можем смело считать "логически общезначимыми", например, такие вещи, как:
$\forall x,y,z ~ (x+y=z \to x+y=z)$,
не смущаясь тем, что мы не позаботились предварительно определить переменные $x$, $y$ и $z$, а также двухместный функциональный символ $+$ и двухместный предикатный символ $=$.

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

Что касается «Проблема в том, что без предикатных и функциональных символов нельзя записать ни одной формулы», то по моему срабатывает импликация с ложной посылкой.

В смысле? Раз не существует ни одной формулы, то импликация, содержащая в посылке "если формула истинна в любой интерпретации", истинна?
Какое-то тогда содержание у понятия "логической общезначимости" получается ... гхм ... юридически ничтожным...

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

epros в сообщении #463118 писал(а):

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

На странице 66 дается определение: «Теория первого порядка, не содержащая собственных аксиом, называется исчисление предикатов первого порядка.»

Ага, понятно. Значит, мы можем смело считать "логически общезначимыми", например, такие вещи, как:
$\forall x,y,z ~ (x+y=z \to x+y=z)$,
не смущаясь тем, что мы не позаботились предварительно определить переменные $x$, $y$ и $z$, а также двухместный функциональный символ $+$ и двухместный предикатный символ $=$.

(Оффтоп)

Ваш комментарий напоминает анекдот: «Дайте водицы напиться, а то негде переночевать».

Ещё раз: слова в скобках во фразе «Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации» скорее всего домыслы переводчика. Во втором издании эта фраза звучит так: «Формула $\mathscr A$ называется логически общезначимой, если она истинна в каждой интерпретации.» Логическая общезначимость не существует без интерпретации. А где «проживают» формулы хорошо сказал Xaositect:

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

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

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

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

В Вашем же комментарии нужны ещё и собственные аксиомы.

(Оффтоп)

Лучше не смешивать котлеты с мухами.

-- Вт июн 28, 2011 10:52:34 --

epros в сообщении #463118 писал(а):

Раз не существует ни одной формулы, то импликация, содержащая в посылке "если формула истинна в любой интерпретации", истинна?

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

(Оффтоп)

epros в сообщении #463118 писал(а):

Какое-то тогда содержание у понятия "логической общезначимости" получается ... гхм ... юридически ничтожным...

Уже нанял адвоката.