Квантификация многоместных предикатов

[kernel1983]

У меня возникли проблемы с пониманием сущности операций квантификации применительно к предикатам с количеством предметных переменных более одной. Если предметная переменная одна, то всё ясно: высказывание $\forall x A(x)$ истинно тогда и только тогда, когда предикат $A(x)$ тождественно истинен, а высказывание $\exists x A(x)$ ложно тогда и только тогда, когда предикат $A(x) $ тождественно ложен. Отсюда легко понять, что первое высказывание ложно тогда и только тогда, когда соответствующий предикат опровержим, а второе высказывание истинно, если и только если предикат выполним. Рассмотрим предикат $A(x_1,x_2, \ldots , x_n)$, где $x_i \in M_i, \ i =1,2, \ldots , n$, $M_i$ - некоторые множества. Верно ли, что предикат $\forall x_1 A(x_1, \ldots , x_n)$ тождественно истинен, если предикат $P(x_1, a_2 , \ldots , a_n)$ тождественно истинен для любых $a_2 \in M_2, \ldots , a_n \in M_n$, и опровержим, если существуют такие $a_2 \in M_2, \ldots , a_n \in M_n$, что предикат $P(x_1, a_2 , \ldots , a_n)$ опровержим? Аналогично: верно ли, что предикат $\exists x_1 A(x_1, \ldots , x_n)$ тождественно ложен, если предикат $P(x_1, a_2 , \ldots , a_n)$ тождественно ложен для любых $a_2 \in M_2, \ldots , a_n \in M_n$, и выполним, если существуют такие $a_2 \in M_2, \ldots , a_n \in M_n$, что предикат $P(x_1, a_2 , \ldots , a_n)$ выполним?
Спасибо всем, кто поможет разобраться.

-- 14.03.2017, 19:10 --

Вот что написано на эту тему у Игошина:





Никак не соображу, это то же, что и у меня, или нет?

[arseniiv]

Есть куда более аккуратное описание всего этого, но да.

[kernel1983]

arseniiv в сообщении #1200384 писал(а):

более аккуратное описание всего этого

Спасибо. А не подскажете, где почитать об этом, кроме Игошина? Просмотрел уже десятки книг по матлогике, но в большинстве из них просто упоминается возможность навешивания кванторов на многоместные предикаты, но подробно это не описывается.

[arseniiv]

Подробно это описывается в главах, посвящённых интерпретации (и истинности в интерпретации). Может, упускали их из виду.

Можете, например, посмотреть Верещагина, Шеня «Языки и исчисления», Мендельсона «Введение в математическую логику» (у этой книги есть совсем недавние издания на английском, но перевода нет), Манина «Доказуемое и недоказуемое». Вообще книг действительно много.

[kernel1983]

Спасибо. Но про квантификацию многоместных предикатов нашёл только у Игошина (не совсем понимаю его определение).
Можно ли определить так?

Предикат $\forall x_1 A(x_1,x_2, \ldots , x_n)$ тождественно истинен тогда и только тогда, когда тождественно истинен предикат $A(x_1,x_2, \ldots , x_n)$.

Предикат $\exists x_1 A(x_1,x_2, \ldots , x_n)$ тождественно ложен тогда и только тогда, когда тождественно ложен предикат $A(x_1,x_2, \ldots , x_n)$.

[arseniiv]

kernel1983 в сообщении #1201069 писал(а):

Но про квантификацию многоместных предикатов нашёл только у Игошина

Ну как же так — во всех трёх книгах есть квантификация, просто там немного другой подход к именованию и обозначению вещей (по-моему, более логичный) — отдельные предикаты с конкретными наборами параметров никак не выделяются среди всех формул, и квантификацией любой формулы мы получим опять же формулу — даже если навесим квантор по переменной, которая была уже и так связанной и параметром формулы не являлась. Дальше, при интерпретации, определяется, какое значение будет иметь такая формула $\forall x\varphi$/$\exists x\varphi$, если мы знаем значение формулы $\varphi$. И вот там вся техническая точность, которую я имел в виду, упрятана. Посмотрите, пожалуйста, ещё раз. Раздел «языки первого порядка».

-- Пт мар 17, 2017 13:09:25 --

kernel1983 в сообщении #1201069 писал(а):

Можно ли определить так?

Предикат $\forall x_1 A(x_1,x_2, \ldots , x_n)$ тождественно истинен тогда и только тогда, когда тождественно истинен предикат $A(x_1,x_2, \ldots , x_n)$.

Предикат $\exists x_1 A(x_1,x_2, \ldots , x_n)$ тождественно ложен тогда и только тогда, когда тождественно ложен предикат $A(x_1,x_2, \ldots , x_n)$.

Так-то можно, но как вы будете судить о тождественной истинности второго и тождественной ложности первого?

[kernel1983]

arseniiv в сообщении #1201120 писал(а):

Так-то можно, но как вы будете судить о тождественной истинности второго и тождественной ложности первого?

По определению тождественной истинности и тождественной ложности предиката.

$(n-1)$-местный предикат $\exists x_1 A(x_1,x_2, \ldots, x_n)$ тождественно истинен тогда и только тогда, когда для любых значений $a_2, \ldots, a_n$ предметных переменных $x_2, \ldots , x_n$ высказывание $\exists x_1 A(x_1,a_2, \ldots, a_n)$ истинно.

$(n-1)$-местный предикат $\forall x_1 A(x_1,x_2, \ldots, x_n)$ тождественно ложен тогда и только тогда, когда для любых значений $a_2, \ldots, a_n$ предметных переменных $x_2, \ldots , x_n$ высказывание $\forall x_1 A(x_1,a_2, \ldots, a_n)$ ложно.

P.S. А нужно ли вообще определять операцию квантификации для $n$-местных предикатов, где $n \ge 2$? Или можно ограничиться определениями для одноместных предикатов?

[arseniiv]

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

kernel1983 в сообщении #1201927 писал(а):

P.S. А нужно ли вообще определять операцию квантификации для $n$-местных предикатов, где $n \ge 2$? Или можно ограничиться определениями для одноместных предикатов?

Ну вот в подходе, где

arseniiv в сообщении #1201120 писал(а):

отдельные предикаты с конкретными наборами параметров никак не выделяются среди всех формул, и квантификацией любой формулы мы получим опять же формулу — даже если навесим квантор по переменной, которая была уже и так связанной и параметром формулы не являлась

вообще не нужно говорить о местности предикатов — всё определяется безотносительно к тому, сколько у квантифицируемых формул параметров.

[kernel1983]

arseniiv в сообщении #1201946 писал(а):

вставлять в формулы

У меня пока не формулы, а просто предикаты. Формулы определяются позже.

[arseniiv]

Ну это как-то неудобно — вам дальше придётся всё переопределять и для формул тогда.

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

[maximav]

kernel1983 в сообщении #1201927 писал(а):

$(n-1)$-местный предикат $\exists x_1 A(x_1,x_2, \ldots, x_n)$ тождественно истинен тогда и только тогда, когда ...
$(n-1)$-местный предикат $\forall x_1 A(x_1,x_2, \ldots, x_n)$ тождественно ложен ...

Если здесь многоместность несущественна, то дает ли что переконвертация $\exists \rightleftarrows\forall$, т.е. тождество $\big(\exists x,P(x)\big)=\big(\sim(\forall x, \sim P(x)) \big)$?

[arseniiv]

maximav
Нет бы по-человечески написать $\forall x\,\varphi$ и $\neg\exists x\,\neg\varphi$… Кстати, нет, ничего нового эта логическая эквивалентность тут не даёт. Она и доказывается-то из определений, и уже после введения этой самой эквивалентности, которое нельзя сделать до определения значений формул, в чём здесь и был вопрос.