Логика, дружественная к независимости

Логика, дружественная к независимости ( логика ЕСЛИ ; предложена Яакко Хинтиккой и Габриэлем Санду в 1989 году) является расширением классической логики первого порядка (ЛОЛ) посредством косых кванторов вида $(\exists v/V)$ и $(\forall v/V)$, где $V$ является конечным набором переменных. Предполагаемое прочтение $(\exists v/V)$ это «есть $v$ который функционально независим от переменных в $V$". Логика ЕСЛИ позволяет выражать более общие закономерности зависимости между переменными, чем те, которые неявно подразумеваются в логике первого порядка. Этот более высокий уровень общности приводит к фактическому увеличению выразительной силы; набор предложений ЕСЛИ может характеризовать одни и те же классы структур как экзистенциальная логика второго порядка ( $\Sigma _{1}^{1}$).

Например, он может выражать предложения -квантификаторы ветвления , такие как формула $\exists c\forall x\exists y\forall z(\exists w/\{x,y\})((x=z\leftrightarrow y=w)\land y\neq c)$ который выражает бесконечность в пустой подписи; это невозможно сделать в ВОЛС. Следовательно, логика первого порядка не может, вообще говоря, выразить эту модель зависимости, при которой $y$ зависит только от $x$ и $c$, и $w$ зависит только от $z$ и $c$. Логика IF является более общей, чем кванторы ветвления , например, в том, что она может выражать нетранзитивные зависимости, например, в префиксе квантора. $\forall x\exists y(\exists z/\{x\})$, что выражает то, что $y$ зависит от $x$, и $z$ зависит от $y$, но $z$ не зависит от $x$.

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

Логика, дружественная к независимости, эквивалентна переводу на уровне предложений ряду других логических систем, основанных на командной семантике, таких как логика зависимости , логика, дружественная к зависимости, логика исключения и логика независимости; За исключением последней, логика ЕСЛИ, как известно, эквивалентна этим логикам и на уровне открытых формул. Однако логика ЕСЛИ отличается от всех вышеупомянутых систем отсутствием локальности : смысл открытой формулы не может быть описан только через свободные переменные формулы; вместо этого оно зависит от контекста, в котором встречается формула.

Логика, дружественная к независимости, разделяет ряд металогических свойств с логикой первого порядка, но есть некоторые различия, в том числе отсутствие замыкания при (классическом, противоречивом) отрицании и более высокая сложность определения достоверности формул. Расширенная логика ЕСЛИ решает проблему замыкания, но ее теоретико-игровая семантика более сложна, и такая логика соответствует более крупному фрагменту логики второго порядка, собственному подмножеству логики второго порядка. $\Delta _{2}^{1}$.

Хинтикка утверждал что ЕСЛИ и расширенная ЕСЛИ-логика должны использоваться в качестве основы для основ математики ; это предложение было встречено в некоторых случаях со скептицизмом.

Синтаксис

В литературе появилось несколько несколько разных представлений логики, способствующей независимости; здесь мы следуем Манну и др. (2011).

Термины и атомарные формулы

Для фиксированной сигнатуры σ термины и атомарные формулы определяются точно так же, как в логике первого порядка с равенством .

формулы ЕСЛИ

Формулы логики ПЧ определяются следующим образом:

1. Любая атомарная формула $\varphi$ это формула ЕСЛИ.
2. Если $\varphi$ является формулой ЕСЛИ, то $\lnot \varphi$ это формула ЕСЛИ.
3. Если $\varphi$ и $\psi$ являются формулами ЕСЛИ, то $\phi \wedge \psi$ и $\phi \vee \psi$ являются формулами ЕСЛИ.
4. Если $\varphi$ это формула, $v$ является переменной, и $V$ — конечное множество переменных, то $(\exists v/V)\varphi$ и $(\forall v/V)\varphi$ также являются формулами ЕСЛИ.

Свободные переменные

Набор ${\mbox{Free}}(\varphi )$ свободных переменных формулы ЕСЛИ $\varphi$ определяется индуктивно следующим образом:

1. Если $\varphi$ атомная формула, то ${\mbox{Free}}(\varphi )$ — множество всех переменных, входящих в него.
2. ${\mbox{Free}}(\lnot \varphi )={\mbox{Free}}(\varphi )$;
3. ${\mbox{Free}}(\varphi \vee \psi )={\mbox{Free}}(\varphi )\cup {\mbox{Free}}(\psi )$;
4. ${\mbox{Free}}((\exists v/V)\varphi )={\mbox{Free}}((\forall v/V)\varphi )=({\mbox{Free}}(\varphi )\backslash \{v\})\cup V$.

Последнее предложение - единственное, которое отличается от предложений для логики первого порядка, с той разницей, что переменные в наборе косой черты также $V$ считаются свободными переменными.

ЕСЛИ предложения

Формула ЕСЛИ $\varphi$ такой, что ${\mbox{Free}}(\phi )=\emptyset$ это предложение ЕСЛИ .

Семантика

Для определения семантики логики IF были предложены три основных подхода. Первые два, основанные соответственно на играх с несовершенной информацией и на сколемизации, в основном используются при определении только ЕСЛИ-предложений. Первый обобщает аналогичный подход для логики первого порядка, которая вместо этого была основана на играх с совершенной информацией.Третий подход, командная семантика , представляет собой композиционную семантику в духе семантики Тарского. Однако эта семантика не определяет, что означает, что формула удовлетворяется присваиванием (скорее, набором присваиваний ).Первые два подхода были развиты в более ранних публикациях по логике; третий Ходжес в 1997 году.

В этом разделе мы различаем три подхода, записывая отдельные педики, как в $\models _{GTS},\models _{Sk},\models$. Поскольку три подхода принципиально эквивалентны, только символ $\models$ будет использоваться в оставшейся части статьи.

Теоретико-игровая семантика

Теоретико-игровая семантика присваивает значения истинности предложениям ЕСЛИ в соответствии со свойствами некоторых игр для двух игроков с несовершенной информацией. Для удобства изложения игры удобно связывать не только с предложениями, но и с формулами. Точнее, определяют игры $G(\varphi ,{\mathcal {M}},s)$ для каждой тройки, образованной формулой ЕСЛИ $\varphi$, структура ${\mathcal {M}}$и задание $s:U\supseteq {\mbox{Free}}(\varphi )\rightarrow {\mathcal {M}}$.

Игроки

Семантическая игра $G(\varphi ,{\mathcal {M}},s)$ есть два игрока, которых зовут Элоиза (или Верификатор) и Абеляр (или Фальсификатор).

Правила игры

Разрешенные ходы в смысловой игре $G(\varphi ,{\mathcal {M}},s)$ определяются синтаксической структурой рассматриваемой формулы.Для простоты сначала предположим, что $\varphi$ находится в нормальной форме отрицания, причем символы отрицания встречаются только перед атомарными подформулами.

1. Если $\varphi$ является литералом, игра заканчивается, и, если $\varphi$ верно в ${\mathcal {M}}$ (в смысле первого порядка), тогда побеждает Элоиза; в противном случае побеждает Абеляр.
2. Если $\varphi =\psi _{1}\land \psi _{2}$, то Абеляр выбирает одну из подформул $\psi _{i}$, и соответствующая игра $G(\psi _{i},{\mathcal {M}},s)$ играется.
3. Если $\varphi =\psi _{1}\lor \psi _{2}$, то Элоиза выбирает одну из подформул $\psi _{i}$, и соответствующая игра $G(\psi _{i},{\mathcal {M}},s)$ играется.
4. Если $\varphi =(\forall v/V)\psi$, то Абеляр выбирает элемент $a$ из ${\mathcal {M}}$и игра $G(\psi ,{\mathcal {M}},s(a/v))$ играется.
5. Если $\varphi =(\exists v/V)\psi$, то Элоиза выбирает элемент $a$ из ${\mathcal {M}}$и игра $G(\psi ,{\mathcal {M}},s(a/v))$ играется.

В более общем смысле, если $\varphi$ не находится в нормальной форме отрицания, мы можем утверждать, как правило для отрицания, что, когда игра $G(\lnot \varphi ,{\mathcal {M}},s)$ достигнуто, игроки начинают вести двойную игру $G^{*}(\varphi ,{\mathcal {M}},s)$ в котором меняются роли Верификаторов и Фальсификаторов.

Истории

Неформально, последовательность ходов в игре. $G(\varphi ,{\mathcal {M}},s)$ это история. В конце каждой истории $h$, какая-то подигра $G(\psi _{h},{\mathcal {M}},s_{h})$ играется; мы звоним $s_{h}$ задание , связанное с $h$, и $\psi _{h}$ появление подформулы , связанное с $h$. Игрок , связанный с $h$ это Элоиза в случае, если это самый внешний логический оператор в $\psi _{h}$ является $\lor$ или $\exists$, и Абеляр, если это так $\land$ или $\forall$.

Набор $h$ разрешенных ходов в истории $h$ является ${\mathcal {M}}$ если самый внешний оператор $\psi _{h}$ является $\exists$ или $\forall$; это $\{L,R\}$ ( $L,R$ любые два различных объекта, символизирующие «лево» и «право») в случае, если самый внешний оператор $\psi _{h}$ является $\lor$ или $\land$.

Даны два задания $s,t$ того же домена и $V\subseteq dom(s)$ мы пишем $s\sim _{V}t$ если $s(w)=t(w)$ по любой переменной $w\in dom(s)\setminus V$.

Несовершенная информация вводится в игры, оговаривая, что определенные истории неразличимы для соответствующего игрока; Говорят, что неразличимые истории образуют «информационный набор». Интуитивно, если история $h$ находится в информационном наборе $I$, игрок, связанный с $h$ не знает, находится ли он в $h$ или в какой-то другой истории $I$.Рассмотрим две истории $h,h'$ такой, что связанный $\psi _{h},\psi _{h'}$ являются идентичными вхождениями подформулы вида $(Qv/V)\chi$ ( $Q=\exists$ или $\forall$); если кроме того $s_{h}\sim _{V}s_{h'}$, мы пишем $h\sim _{\exists }h'$ (в случае $Q=\exists$) или $h\sim _{\forall }h'$ (в случае $Q=\forall$), чтобы указать, что эти две истории неразличимы для Элоизы, соотв. для Абеляра. Мы также оговариваем, вообще говоря, рефлексивность этого отношения: если $\psi =\chi _{1}\lor \chi _{2}$, затем $h\sim _{\exists }h'$; и если $\psi =\chi _{1}\land \chi _{2}$, затем $h\sim _{\forall }h'$.

Стратегии

Для фиксированной игры $G(\varphi ,{\mathcal {M}},s)$, писать $H_{\exists }$ для набора историй, с которыми связана Элоиза, и аналогичным образом $H_{\forall }$ для сборника историй Абеляра.

Стратегия Элоизы в игре $G(\varphi ,{\mathcal {M}},s)$ — это любая функция, которая назначает любой возможной истории, в которой наступает очередь Элоизы, допустимый ход; точнее любая функция $\sigma :H_{\exists }\rightarrow \prod _{h\in H_{\exists }}A(h)$ такой, что $\sigma (h)\in A(h)$ для каждой истории $h\in H_{\exists }$. Стратегии Абеляра можно определить двояко.

Стратегия Элоизы является однородной , если и когда бы то ни было. $h\sim _{\exists }h'$, $\sigma (h)=\sigma (h')$; для Абеляра, если $h\sim _{\forall }h'$ подразумевает $\sigma (h)=\sigma (h')$.

Стратегия $\sigma$ ибо Элоиза выигрывает , если Элоиза выигрывает в каждой истории терминала, в которую можно попасть, играя в соответствии с $\sigma$. То же и с Абеляром.

Истина, ложь, неопределенность

Предложение ЕСЛИ $\varphi$ верно в структуре ${\mathcal {M}}$ ( ${\mathcal {M}}\models _{GTS}^{+}\varphi$) если у Элоизы единая выигрышная стратегия в игре $G(\varphi ,{\mathcal {M}},\emptyset )$. Это неверно ( ${\mathcal {M}}\models _{GTS}^{-}\varphi$), если у Абеляра есть выигрышная стратегия.Неизвестно , есть ли у Элоизы и Абеляра выигрышная стратегия.

Консервативность

Определенная таким образом семантика логики ЕСЛИ является консервативным расширением семантики первого порядка в следующем смысле. Если $\varphi$ является предложением ЕСЛИ с пустыми наборами косых черт, свяжите с ним формулу первого порядка $\varphi '$ который идентичен ему, за исключением того, что каждый квантор ЕСЛИ $(Qv/\emptyset )$ заменяется соответствующим квантором первого порядка $Qv$. Затем ${\mathcal {M}}\models _{GTS}^{+}\varphi$ если только ${\mathcal {M}}\models \varphi '$ в смысле Тарского; и ${\mathcal {M}}\models _{GTS}^{-}\varphi$ если только ${\mathcal {M}}\not \models \varphi '$ в смысле Тарского.

Открытые формулы

Можно использовать более общие игры, чтобы придать значение (возможно, открытым) формулам ЕСЛИ; точнее, можно определить, что это означает для формулы ЕСЛИ $\varphi$ быть удовлетворенным, по структуре ${\mathcal {M}}$, командой $X$ (набор присвоений общей переменной области $dom(X)$ и кодомен ${\mathcal {M}}$).Сопутствующие игры $G(\varphi ,M,X)$ начать со случайного выбора задания $s\in X$; после этого первого хода игра $G(\varphi ,M,s)$ играется. Существование выигрышной стратегии для Элоизы определяет положительное удовлетворение ( $M,X\models _{GTS}^{+}\varphi$), а существование выигрышной стратегии для Абеляра определяет отрицательное удовлетворение ( $M,X\models _{GTS}^{-}\varphi$).На этом уровне общности теоретико-игровую семантику можно заменить алгебраическим подходом, командной семантикой (определенной ниже).

Шолемская семантика

Альтернативно, определение истинности предложений ЕСЛИ может быть дано посредством перевода в экзистенциальную логику второго порядка. Перевод обобщает процедуру сколемизации логики первого порядка. Ложность определяется с помощью двойственной процедуры, называемой крейзелизацией.

сколемизация

Учитывая формулу ЕСЛИ $\varphi$, мы сначала определим его сколемизацию, релятивизированную к конечному множеству $U\supseteq {\mbox{Free}}(\varphi )$ переменных. Для каждого квантора существования $(\exists v/V)$ происходит в $\varphi$, позволять $f_{v}$ быть новым функциональным символом («функция Скулема»). Мы пишем $Subst(\varphi ,v,t)$ для формулы, которая получается заменой в $\varphi$, все свободные вхождения переменной $v$ с термином $t$. Сколемизация $\varphi$ относительно $U$, обозначенный ${\mbox{Sk}}_{U}(\varphi )$, определяется следующими индуктивными предложениями:

1. $\operatorname {Sk} _{U}(\varphi )=\varphi$ если $\varphi$ является буквальным.
2. $\operatorname {Sk} _{U}(\psi \lor \chi )=\operatorname {Sk} _{U}(\psi )\lor \operatorname {Sk} _{U}(\chi )$.
3. $\operatorname {Sk} _{U}(\psi \land \chi )=\operatorname {Sk} _{U}(\psi )\land \operatorname {Sk} _{U}(\chi )$.
4. $\operatorname {Sk} _{U}((\forall v/V)\psi )=\forall v\operatorname {Sk} _{U\cup \{v\}}(\psi )$.
5. $\operatorname {Sk} _{U}((\exists v/V)\psi )=Subst(\operatorname {Sk} _{U\cup \{v\}}(\psi ),v,f_{v}(y_{1},...,y_{n}))$, где $y_{1},...,y_{n}$ представляет собой список переменных в $U\setminus V$.

Если $\varphi$ является предложением ЕСЛИ, его (нерелятивизированная) сколемизация определяется как ${\mbox{Sk}}(\varphi )={\mbox{Sk}}_{\varnothing }(\varphi )$.

Крейселизация

Учитывая формулу ЕСЛИ $\varphi$, ассоциировать с каждым квантором всеобщности $(\forall v/V)$ в нем появляется новый функциональный символ $g_{v}$ («функция гироскопа»). Затем гироскопизация ${\mbox{Kr}}_{U}(\varphi )$ из $\varphi$ относительно конечного набора переменных $U\supseteq {\mbox{Free}}(\varphi )$, определяется следующими индуктивными предложениями:

1. $\operatorname {Kr} _{U}(\varphi )=\lnot \varphi$ если $\varphi$ является буквальным.
2. $\operatorname {Kr} _{U}(\psi \land \chi )=\operatorname {Kr} _{U}(\psi )\lor \operatorname {Kr} _{U}(\chi )$.
3. $\operatorname {Kr} _{U}(\psi \lor \chi )=\operatorname {Kr} _{U}(\psi )\land \operatorname {Kr} _{U}(\chi )$.
4. $\operatorname {Kr} _{U}((\forall v/V)\psi )=Subst(\operatorname {Kr} _{U\cup \{v\}}(\psi ),v,g_{v}(y_{1},...,y_{n}))$, где $y_{1},...,y_{n}$представляет собой список переменных в $U\setminus V$.
5. $\operatorname {Kr} _{U}((\exists v/V)\psi )=\forall v\operatorname {Kr} _{U\cup \{v\}}(\psi )$

Если $\varphi$ является предложением ЕСЛИ, его (нерелятивизированная) крейселизация определяется как ${\mbox{Kr}}(\varphi )={\mbox{Kr}}_{\varnothing }(\varphi )$.

Истина, ложь, неопределенность

Учитывая предложение ЕСЛИ $\varphi$ с $n$ кванторы существования, структура ${\mathcal {M}}$и список ${\vec {f}}$из $n$ функции соответствующей арности обозначим как $({\mathcal {M}},{\vec {f}})$ расширение ${\mathcal {M}}$ который присваивает функции ${\vec {f}}$ как интерпретации скулемовских функций $\varphi$.

Предложение IF истинно для структуры ${\mathcal {M}}$, написано ${\mathcal {M}}\models _{\mbox{Sk}}^{+}\varphi$, если есть кортеж ${\vec {f}}$ функций таких, что $({\mathcal {M}},{\vec {f}})\models {\mbox{Sk}}(\varphi )$.Сходным образом, ${\mathcal {M}}\models _{\mbox{Sk}}^{-}\varphi$ если есть кортеж ${\vec {f}}$ функций таких, что $({\mathcal {M}},{\vec {f}})\models {\mbox{Kr}}(\varphi )$; и ${\mathcal {M}}\models _{\mbox{Sk}}^{0}\varphi$ тогда и только тогда, когда ни одно из предыдущих условий не выполняется.

Для любого предложения IF Skolem Semantics возвращает те же значения, что и теоретико-игровая семантика.

Семантика команды

С помощью командной семантики можно дать композиционное описание семантики логики ЕСЛИ. Истина и ложь основываются на понятии «выполнимости формулы командой».

Команды

Позволять ${\mathcal {M}}$ быть структурой и пусть $V=\{v_{1},\ldots ,v_{n}\}$ быть конечным набором переменных. Затем команда закончилась ${\mathcal {M}}$ с доменом $V$ это набор заданий ${\mathcal {M}}$ с доменом $V$, то есть набор функций $s$ от $V$ к ${\mathcal {M}}$.

Дублирование и дополнение команд

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

1. Учитывая команду $X$ над структурой ${\mathcal {M}}$ и переменная $v$, дублирующая команда $X[{\mathcal {M}}/v]$ это команда $\{s(a/v)|s\in X,a\in {\mathcal {M}}\}$.
2. Учитывая команду $X$ над структурой ${\mathcal {M}}$, функция $F:X\rightarrow {\mathcal {M}}$ и переменная $v$, дополняющая команда $X[F/v]$ это команда $\{s(F(s)/v)|s\in X\}$.

Повторные применения этих двух операций принято заменять более краткими обозначениями, такими как $X[{\mathcal {M}}F/uv]$ для $(X[{\mathcal {M}}/u])[F/v]$.

Единые функции в командах

Как и выше, даны два задания $s,t$ с той же переменной областью, мы пишем $s\sim _{V}t$ если $s(w)=t(w)$ для каждой переменной $w\in dom(s)\setminus V$.

Учитывая команду $X$ на структуре ${\mathcal {M}}$ и конечное множество $V$ переменных, мы говорим, что функция $F:X\rightarrow {\mathcal {M}}$ является $V$-равномерный, если $F(s)=F(t)$ в любое время $s\sim _{V}t$.

Семантические предложения

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

Положительное удовлетворение:

1. $\!{\mathcal {M}},X\models ^{+}Rt_{1}\ldots t_{n}$ тогда и только тогда, когда для каждого задания $s\in X$, $\!{\mathcal {M}},s\models Rt_{1}\ldots t_{n}$ в смысле логики первого порядка (т.е. кортеж $\!(s(t_{1})\ldots s(t_{n}))$ есть в интерпретации $R^{\mathcal {M}}$ из $R$).
2. $\!{\mathcal {M}},X\models ^{+}t_{1}=t_{2}$ тогда и только тогда, когда для каждого задания $s\in X$, $\!{\mathcal {M}},s\models t_{1}=t_{2}$ в смысле логики первого порядка (т. $s(t_{1})=s(t_{2})$).
3. $\!{\mathcal {M}},X\models ^{+}\lnot \phi$ тогда и только тогда, когда $\!{\mathcal {M}},X\models ^{-}\phi$.
4. $\!{\mathcal {M}},X\models ^{+}\varphi \wedge \psi$ тогда и только тогда, когда $\!{\mathcal {M}},X\models ^{+}\varphi$ и $\!{\mathcal {M}},X\models ^{+}\psi$.
5. $\!{\mathcal {M}},X\models ^{+}\varphi \vee \psi$ тогда и только тогда, когда существуют команды $\!Y$ и $\!Z$ такой, что $X=Y\cup Z$ и $\!{\mathcal {M}},Y\models ^{+}\varphi$ и $\!{\mathcal {M}},Z\models ^{+}\psi$.
6. $\!{\mathcal {M}},X\models ^{+}(\forall v/V)\varphi$ тогда и только тогда, когда $\!{\mathcal {M}},X[M/v]\models ^{+}\varphi$.
7. $\!{\mathcal {M}},X\models ^{+}(\exists v/V)\varphi$ тогда и только тогда, когда существует $V$-однородная функция $F:X\rightarrow M$такой, что $\!{\mathcal {M}},X[F/v]\models ^{+}\phi$.

Отрицательное удовлетворение:

1. $\!{\mathcal {M}},X\models ^{-}Rt_{1}\ldots t_{n}$ тогда и только тогда, когда для каждого задания $s\in X$, кортеж $\!(s(t_{1})\ldots s(t_{n}))$ нет в интерпретации $R^{\mathcal {M}}$ из $R$.
2. $\!{\mathcal {M}},X\models ^{-}t_{1}=t_{2}$ тогда и только тогда, когда для каждого задания $s\in X$, $s(t_{1})\neq s(t_{2})$.
3. $\!{\mathcal {M}},X\models ^{-}\lnot \phi$ тогда и только тогда, когда $\!{\mathcal {M}},X\models ^{+}\phi$.
4. $\!{\mathcal {M}},X\models ^{-}\varphi \wedge \psi$ тогда и только тогда, когда существуют команды $\!Y$ и $\!Z$ такой, что $X=Y\cup Z$ и $\!{\mathcal {M}},Y\models ^{-}\varphi$ и $\!{\mathcal {M}},Z\models ^{-}\psi$.
5. $\!{\mathcal {M}},X\models ^{-}\varphi \vee \psi$ тогда и только тогда, когда $\!{\mathcal {M}},X\models ^{-}\varphi$ и $\!{\mathcal {M}},X\models ^{-}\psi$.
6. $\!{\mathcal {M}},X\models ^{-}(\forall v/V)\varphi$ тогда и только тогда, когда существует $V$-однородная функция $F:X\rightarrow M$такой, что $\!{\mathcal {M}},X[F/v]\models ^{-}\phi$.
7. $\!{\mathcal {M}},X\models ^{-}(\exists v/V)\varphi$ тогда и только тогда, когда $\!{\mathcal {M}},X[M/v]\models ^{-}\varphi$.

Истина, ложь, неопределенность

Согласно командной семантике, предложение IF $\varphi$ говорят, что это правда( ${\mathcal {M}}\models ^{+}\varphi$) на конструкции ${\mathcal {M}}$ если оно удовлетворено ${\mathcal {M}}$ от команды синглтона $\{\emptyset \}$, в символах: ${\mathcal {M}},\{\emptyset \}\models ^{+}\varphi$. Сходным образом, $\varphi$ говорят, что это ложь( ${\mathcal {M}}\models ^{-}\varphi$) на ${\mathcal {M}}$ если ${\mathcal {M}},\{\emptyset \}\models ^{-}\varphi$; говорят, что оно неопределенное ( ${\mathcal {M}}\models ^{0}\varphi$) если ${\mathcal {M}},\{\emptyset \}\not \models ^{+}\varphi$ и ${\mathcal {M}},\{\emptyset \}\not \models ^{-}\varphi$.

Связь с теоретико-игровой семантикой

Для любой команды $X$ на структуре ${\mathcal {M}}$и любая формула ЕСЛИ $\varphi$, у нас есть: ${\mathcal {M}},X\models ^{+}\varphi$ если только ${\mathcal {M}},X\models _{GTS}^{+}\varphi$и ${\mathcal {M}},X\models ^{-}\varphi$ если только ${\mathcal {M}},X\models _{GTS}^{-}\varphi$.

Отсюда сразу следует, что для предложений $\varphi$, ${\mathcal {M}}\models ^{+}\varphi \Leftrightarrow {\mathcal {M}}\models _{GTS}^{+}\varphi$, ${\mathcal {M}}\models ^{-}\varphi \Leftrightarrow {\mathcal {M}}\models _{GTS}^{-}\varphi$ и ${\mathcal {M}}\models ^{0}\varphi \Leftrightarrow {\mathcal {M}}\models _{GTS}^{0}\varphi$.

Понятия эквивалентности

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

Эквивалентность формул

Позволять $\varphi ,\psi$ две формулы ЕСЛИ.

$\varphi \models ^{+}\psi$ ( $\varphi$ истина влечет за собой $\psi$) если ${\mathcal {M}},X\models ^{+}\varphi \Rightarrow {\mathcal {M}},X\models ^{+}\psi$ для любой структуры ${\mathcal {M}}$ и любая команда $X$ такой, что $dom(X)\supseteq {\mbox{Free}}(\varphi )\cup {\mbox{Free}}(\psi )$.

$\varphi \equiv ^{+}\psi$ ( $\varphi$ эквивалентна истинность ​ $\psi$) если $\varphi \models ^{+}\psi$ и $\psi \models ^{+}\varphi$.

$\varphi \models ^{-}\psi$ ( $\varphi$ ложь влечет за собой $\psi$) если ${\mathcal {M}},X\models ^{-}\psi \Rightarrow {\mathcal {M}},X\models ^{-}\varphi$ для любой структуры ${\mathcal {M}}$ и любая команда $X$ такой, что $dom(X)\supseteq {\mbox{Free}}(\varphi )\cup {\mbox{Free}}(\psi )$.

$\varphi \equiv ^{-}\psi$ ( $\varphi$ является ложностью эквивалентной $\psi$) если $\varphi \models ^{-}\psi$ и $\psi \models ^{-}\varphi$.

$\varphi \models \psi$ ( $\varphi$ решительно влечет за собой $\psi$) если $\varphi \models ^{+}\psi$ и $\varphi \models ^{-}\psi$.

$\varphi \equiv \psi$ ( $\varphi$ эквивалентно сильно ​ $\psi$) если $\varphi \equiv ^{+}\psi$ и $\varphi \equiv ^{-}\psi$.

Эквивалентность предложений

Приведенные выше определения специализируются на предложениях IF следующим образом.Два предложения ЕСЛИ $\varphi ,\psi$ если истинно эквивалентны, они истинны в одних и тех же структурах; они эквивалентны ложности , если они ложны в одних и тех же структурах; они сильно эквивалентны, если они эквивалентны как истинности, так и ложности.

Интуитивно, использование сильной эквивалентности означает рассмотрение логики ЕСЛИ как 3-значной (истина/неопределенность/ложь), в то время как эквивалентность истинности рассматривает предложения ЕСЛИ так, как если бы они были 2-значными (истина/неправда).

Эквивалентность относительно контекста

Многие логические правила логики ЕСЛИ могут быть адекватно выражены только в терминах более ограниченных понятий эквивалентности, которые принимают во внимание контекст, в котором может появиться формула.

Например, если $U$ представляет собой конечный набор переменных и $U\supseteq {\mbox{Free}}(\varphi )\cup {\mbox{Free}}(\psi )$, можно сказать, что $\varphi$ эквивалентна истинность $\psi$ относительно $U$ ( $\varphi \equiv _{U}\psi$) в случае ${\mathcal {M}},X\models ^{+}\psi \Leftrightarrow {\mathcal {M}},X\models ^{+}\varphi$ для любой структуры ${\mathcal {M}}$ и любая команда $X$ домена $U$.

Теоретико-модельные свойства

Уровень предложения

ЕСЛИ-предложения могут быть переведены сохраняющим истину способом в предложения (функциональной) экзистенциальной логики второго порядка ( $\Sigma _{1}^{1}$) с помощью процедуры сколемизации (см. выше). И наоборот, каждый $\Sigma _{1}^{1}$ может быть переведено в предложение ЕСЛИ с помощью варианта процедуры перевода Уоко-Эндертона для частично упорядоченных кванторов ( ). Другими словами, ЕСЛИ логика и $\Sigma _{1}^{1}$ экспрессивно эквивалентны на уровне предложений. Эту эквивалентность можно использовать для доказательства многих следующих свойств; они унаследованы от $\Sigma _{1}^{1}$ и во многих случаях аналогичны свойствам ВОЛС.

Обозначим через $T$ (возможно, бесконечный) набор предложений ЕСЛИ.

• Свойство Левенхайма-Сколема: если $T$ имеет бесконечную модель или сколь угодно большие конечные модели, чем имеет модели любой бесконечной мощности.
• Экзистенциальная компактность: если каждое конечное $T_{0}\subseteq T$ есть модель, то также $T$ есть модель.
• Недостаток дедуктивной компактности: существуют $T,\varphi$ такой, что $T\models \varphi$, но $T_{0}\not \models \varphi$ для любого конечного $T_{0}\subset T$. В этом отличие от ФОЛ.
• Теорема разделения: если $\varphi ,\psi$ являются взаимно несовместимыми предложениями ЕСЛИ, то существует предложение ВОЛ $\theta$ такой, что $\varphi \models ^{+}\theta$ и $\psi \models ^{+}\lnot \theta$. Это следствие интерполяционной теоремы Крейга для ВОЛС.
• Теорема Берджесса: если $\varphi ,\psi$ являются взаимно несовместимыми предложениями ЕСЛИ, то существует предложение ЕСЛИ $\theta$ такой, что $\varphi \equiv ^{+}\theta$ и $\psi \equiv ^{+}\lnot \theta$ (за исключением, возможно, одноэлементных конструкций). В частности, эта теорема показывает, что отрицание логики ЕСЛИ не является семантической операцией относительно истинностной эквивалентности (истинно-эквивалентные предложения могут иметь неэквивалентные отрицания).
• Определимость истины: есть предложение ЕСЛИ $TRUE(c)$, на языке арифметики Пеано, такой, что для любого предложения ЕСЛИ $\varphi ,$, $\mathbb {N} \models \varphi \Leftrightarrow \mathbb {N} \models TRUE(\ulcorner \varphi \urcorner )$ (где $\ulcorner \urcorner$ обозначает нумерацию Гёделя). Более слабое утверждение справедливо и для нестандартных моделей арифметики Пеано ( ).

Уровень формулы

Понятие выполнимости командой обладает следующими свойствами:

• Закрытие вниз: если ${\mathcal {M}},X\models ^{\pm }\varphi$ и $Y\subseteq X$, затем ${\mathcal {M}},Y\models ^{\pm }\varphi$.
• Последовательность: ${\mathcal {M}},X\models ^{+}\varphi$ и ${\mathcal {M}},X\models ^{-}\varphi$ тогда и только тогда, когда $X=\emptyset$.
• Нелокальность: есть ${\mathcal {M}},X,\varphi$ такой, что ${\mathcal {M}},X\models \varphi \not \Leftrightarrow M,X_{\upharpoonright {\mbox{Free}}(\varphi )}\models \varphi$.

Поскольку формулы IF выполняются командами, а формулы классической логики выполняются заданиями, очевидного взаимного перевода между формулами IF и формулами некоторой классической логической системы не существует. Однако существует процедура перевода. ЕСЛИ в предложения относительной формул $\Sigma _{1}^{1}$ (фактически, один отличный перевод $\tau _{U,R}$ для каждого конечного $U\supseteq {\mbox{Free}}(\varphi )$ и для каждого выбора предикатного символа $R$ арности $card(U)$). В этом виде перевода дополнительный n-арный символ предиката $R$ используется для представления команды с n переменными $X$. Это мотивировано тем, что как только заказ $v_{1}\dots v_{n}$ переменных $dom(X)$ исправлено, можно связать отношение $Rel_{v_{1}\dots v_{n}}(X)=\{(s(v_{1}),\dots ,s(v_{n}))|s\in X\}$ команде $X$. Согласно этим соглашениям, формула ЕСЛИ связана с ее переводом следующим образом:

${\mathcal {M}},X\models \varphi \Leftrightarrow ({\mathcal {M}},Rel_{v_{1}\dots v_{n}}(X))\models \tau _{dom(X),R}(\varphi )$

где $(M,Rel_{v_{1}\dots v_{n}}(X))$ это расширение ${\mathcal {M}}$ который назначает $Rel_{v_{1}\dots v_{n}}(X)$ как интерпретация предиката $R$.

Благодаря этой корреляции можно сказать, что о структуре ${\mathcal {M}}$, формула ЕСЛИ $\varphi$ из n свободных переменных определяет семейство n-арных отношений над ${\mathcal {M}}$ (семья отношений $Rel_{v_{1}\dots v_{n}}(X)$ такой, что ${\mathcal {M}},X\models \varphi$).

В 2009 году Континен и Вяэнянен показал с помощью процедуры частичного обратного перевода, что семейства отношений, определяемые логикой ЕСЛИ, являются в точности теми, которые непусты, замкнуты вниз и определимы в реляционной логике. $\Sigma _{1}^{1}$ с дополнительным предикатом $R$ (или, что то же самое, непустой и определяемый $\Sigma _{1}^{1}$ предложение, в котором $R$ происходит только отрицательно).

Расширенная логика ЕСЛИ

ЕСЛИ-логика не замкнута при классическом отрицании. Логическое замыкание логики ЕСЛИ известно как расширенная логика ЕСЛИ и эквивалентно правильному фрагменту логики ЕСЛИ. $\Delta _{2}^{1}$ (Фигейра и др., 2011). Хинтикка (1996, стр. 196) утверждал, что «практически вся классическая математика в принципе может быть выполнена в расширенной ЕСЛИ-логике первого порядка».

Свойства и критика

Ряд свойств логики IF следует из логической эквивалентности с $\Sigma _{1}^{1}$ и приблизить ее к логике первого порядка , включая теорему о компактности , теорему Левенхайма-Скулема и интерполяционную теорему Крейга . (Вяэнянен, 2007, стр. 86). Однако Вяэнянен (2001) доказал, что набор чисел Гёделя действительных предложений логики ЕСЛИ с хотя бы одним двоичным кодомсимвол-предикат (набор, обозначенный Val _IF ) рекурсивно изоморфен соответствующему набору чисел Гёделя действительных (полных) предложений второго порядка в словаре, который содержит один двоичный символ-предикат (набор, обозначенный Val ² ). Более того, Вяэнянен показал, что Вал ² — полное Π ₂ -определимое множество целых чисел и что оно Val ² не в $\Sigma _{n}^{m}$ для любых конечных m и n . Вяэнянен (2007, стр. 136–139) резюмирует результаты сложности следующим образом:

Проблема	логика первого порядка	Логика IF/зависимости/ESO
Решение	$\Sigma _{1}^{0}$ ( ре )	$\Pi _{2}$
Недействительность ​	$\Pi _{1}^{0}$ ( основной )	$\Sigma _{2}$
Последовательность	$\Pi _{1}^{0}$	$\Pi _{1}^{0}$
непоследовательность	$\Sigma _{1}^{0}$	$\Sigma _{1}^{0}$

Феферман (2006) цитирует результат Вяэнянена 2001 года, утверждая (вопреки Хинтикке), что, хотя выполнимость может быть вопросом первого порядка, вопрос о том, существует ли выигрышная стратегия для Verifier над всеми структурами в целом, «прямо приводит нас к полной логике второго порядка». (курсив Фефермана). Феферман также раскритиковал заявленную полезность расширенной логики ЕСЛИ, поскольку предложения в $\Pi _{1}^{1}$ не допускают теоретико-игровой интерпретации.

См. также

• Семантика игры
• Кванторы ветвления
• Логика зависимости

Ссылки

• Берджесс, Джон П., « Замечание о предложениях Хенкина и их противоположностях », Notre Dame Journal of Formal Logic 44 (3): 185–188 (2003).
• Кэмерон, Питер и Ходжес, Уилфрид (2001), « Некоторые комбинаторики несовершенной информации ». Журнал символической логики 66: 673-684.
• Эклунд, Матти и Колак, Дэниел, « Является ли логика Хинтикки первым порядком? » Synthese , 131(3): 371-388, июнь 2002 г., [1] .
• Эндертон, Герберт Б., « Конечные частично упорядоченные кванторы », Mathematical Logic Quarterly Volume 16, Issue 8 1970, страницы 393–397.
• Феферман, Соломон , «Какая логика является логикой, дружественной независимости?», в « Философии Яакко Хинтикки » (Рэндалл Э. Осье и Льюис Эдвин Хан, ред.); Библиотека живых философов, том. 30, Открытый суд (2006), 453-469, http://math.stanford.edu/~feferman/papers/hintikka_iia.pdf .
• Фигейра, Сантьяго, Горин, Дэниел и Гримсон, Рафаэль «О выразительной силе ЕСЛИ-логики с классическим отрицанием», материалы WoLLIC 2011, стр. 135–145, ISBN   978-3-642-20919-2 , [2] .
• Хинтикка, Яакко (1996), «Возвращение к принципам математики», Cambridge University Press, ISBN   978-0-521-62498-5 .
• Хинтикка, Яакко, «Гиперклассическая логика (также известная как логика ЕСЛИ) и ее последствия для логической теории», Бюллетень символической логики 8, 2002, 404-423 http://www.math.ucla.edu/~asl/bsl/0803/0803 -004.пс.
• Хинтикка, Яакко и Санду, Габриэль (1989), «Информационная независимость как семантическое явление», в книге «Логика, методология и философия науки VIII» (Дж. Э. Фенстад и др., ред.), Северная Голландия, Амстердам, дои : 10.1016/S0049-237X(08)70066-1 .
• Хинтикка, Яакко и Санду, Габриэль, « Теоретико-игровая семантика », в Справочнике по логике и языку , изд. Дж. ван Бентем и А. тер Меулен , Elsevier, 1996 (1-е изд.), Обновлено во 2-м втором издании книги (2011 г.).
• Ходжес, Уилфрид (1997), « Композиционная семантика языка несовершенной информации ». Журнал IGPL 5: 539–563.
• Ходжес, Уилфрид, «Некоторые странные квантификаторы», в конспектах лекций по информатике 1261:51-65, январь 1997 г.
• Янссен, Тео М.В., «Независимый выбор и интерпретация логики ЕСЛИ». Журнал логики, языка и информации , том 11, выпуск 3, лето 2002 г., стр. 367–387. два : 10.1023/A:1015542413718 [3] .
• Колак, Дэниел, Он Хинтикка , Бельмонт: Уодсворт, 2001 г. ISBN   0-534-58389-X .
• Колак, Дэниел и Саймонс, Джон, «Результаты: объем и значение философии Хинтикки» в книге Дэниела Колака и Джона Саймонса , ред., Кванторы, вопросы и квантовая физика. Очерки философии Яакко Хинтикки , Springer 2004, стр. 205–268. ISBN   1-4020-3210-2 , дои : 10.1007/978-1-4020-32110-0_11 .
• Континен, Юха и Вяэнянен, Йоуко, «Об определимости в логике зависимости» (2009), Journal of Logic, Language and Information 18 (3), 317–332.
• Манн, Аллен Л., Санду, Габриэль и Севенстер, Мерлин (2011) Логика, дружественная независимости. Теоретико-игровой подход , Издательство Кембриджского университета, ISBN   0521149347 .
• Санду, Габриэль, « Если-логика и определение истины », Журнал философской логики, апрель 1998 г., том 27, выпуск 2, стр. 143–164.
• Санду, Габриэль, « О логике информационной независимости и ее применениях », Journal of Philosophical Logic Vol. 22, № 1 (февраль 1993 г.), стр. 29–60.
• Вяэнянен, Йоуко , 2007, «Логика зависимости — новый подход к логике, дружественной к независимости», Cambridge University Press, ISBN   978-0-521-87659-9 , [4] .
• Уолко, Уилбур Джон младший, « Конечная частично упорядоченная количественная оценка », Журнал символической логики, том. 35, № 4 (декабрь 1970 г.), стр. 535–555.

Внешние ссылки

• Туленхеймо, Теро. «Логика, дружественная независимости» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• Ходжес, Уилфрид. «Логика и игры» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• ЕСЛИ логика на Planet Math