Бесконечная логика

Бесконечная логика — это логика , допускающая бесконечно длинные утверждения и/или бесконечно длинные доказательства . ^[1] Эта концепция была представлена Цермело в 1930-х годах. ^[2]

Некоторые бесконечные логики могут иметь свойства, отличные от свойств стандартной логики первого порядка . В частности, бесконечные логики могут не быть компактными или полными . Понятия компактности и полноты, эквивалентные в финитной логике, иногда не являются таковыми в бесконечной логике. Поэтому для инфинитарных логик определены понятия сильной компактности и сильной полноты. В этой статье рассматриваются бесконечные логики гильбертова типа , поскольку они были тщательно изучены и представляют собой наиболее прямое расширение финитной логики. Однако это не единственные бесконечные логики, которые были сформулированы или изучены.

Рассмотрение вопроса о том, является ли некоторая бесконечная логика, называемая Ω-логикой , полной, обещает пролить свет на гипотезу континуума . ^[3]

и аксиоме выбора Несколько слов об обозначениях

Поскольку представлен язык с бесконечно длинными формулами, невозможно записать такие формулы явно. Чтобы обойти эту проблему, используется ряд нотационных удобств, которые, строго говоря, не являются частью формального языка. $\cdots$ используется для обозначения выражения, которое имеет бесконечную длину. Если это неясно, длина последовательности отмечается позже. Если это обозначение становится двусмысленным или запутанным, такие суффиксы, как $\bigvee _{\gamma <\delta }{A_{\gamma }}$ используются для обозначения бесконечной дизъюнкции над набором формул мощности $\delta$ . Те же обозначения могут быть применены к кванторам, например $\forall _{\gamma <\delta }{V_{\gamma }:}$ . Это предназначено для представления бесконечной последовательности кванторов: квантор для каждого $V_{\gamma }$ где $\gamma <\delta$ .

Все случаи использования суффиксов и $\cdots$ не являются частью формальных бесконечных языков.

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

логики гильбертова типа Определение бесконечной

Бесконечный язык первого порядка L _{α , β} , α регулярный , β = 0 или ω ≤ β ≤ α , имеет тот же набор символов, что и финитарная логика, и может использовать все правила формирования формул финитарной логики вместе с некоторые дополнительные:

Учитывая набор формул $A=\{A_{\gamma }|\gamma <\delta <\alpha \}$ затем $(A_{0}\lor A_{1}\lor \cdots )$ и $(A_{0}\land A_{1}\land \cdots )$ являются формулами. (В каждом случае длина последовательности $\delta$ .)
Учитывая набор переменных $V=\{V_{\gamma }|\gamma <\delta <\beta \}$ и формула $A_{0}$ затем $\forall V_{0}:\forall V_{1}\cdots (A_{0})$ и $\exists V_{0}:\exists V_{1}\cdots (A_{0})$ являются формулами. (В каждом случае последовательность кванторов имеет длину $\delta$ .)

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

Теория Т на бесконечном языке $L_{\alpha ,\beta }$ представляет собой набор предложений в логике. Доказательство в бесконечной логике теории T представляет собой (возможно, бесконечную) последовательность утверждений, которая подчиняется следующим условиям: каждое утверждение является либо логической аксиомой, элементом T , либо выводится из предыдущих утверждений с использованием правила вывода. Как и раньше, можно использовать все правила вывода финитной логики вместе с дополнительным:

Учитывая набор утверждений $A=\{A_{\gamma }|\gamma <\delta <\alpha \}$ которые произошли ранее в доказательстве, то утверждение $\land _{\gamma <\delta }{A_{\gamma }}$ можно сделать вывод. ^[4]

Ниже представлены схемы логических аксиом, характерные для бесконечной логики. Глобальные переменные схемы: $\delta$ и $\gamma$ такой, что $0<\delta <\alpha$ .

$((\land _{\epsilon <\delta }{(A_{\delta }\implies A_{\epsilon })})\implies (A_{\delta }\implies \land _{\epsilon <\delta }{A_{\epsilon }}))$
Для каждого $\gamma <\delta$ , $((\land _{\epsilon <\delta }{A_{\epsilon }})\implies A_{\gamma })$
каждого Законы дистрибутивности Чанга (для $\gamma$ ): $(\lor _{\mu <\gamma }{(\land _{\delta <\gamma }{A_{\mu ,\delta }})})$ , где $\forall \mu \forall \delta \exists \epsilon <\gamma :A_{\mu ,\delta }=A_{\epsilon }$ или $A_{\mu ,\delta }=\neg A_{\epsilon }$ , и $\forall g\in \gamma ^{\gamma }\exists \epsilon <\gamma :\{A_{\epsilon },\neg A_{\epsilon }\}\subseteq \{A_{\mu ,g(\mu )}:\mu <\gamma \}$
Для $\gamma <\alpha$ , $((\land _{\mu <\gamma }{(\lor _{\delta <\gamma }{A_{\mu ,\delta }})})\implies (\lor _{\epsilon <\gamma ^{\gamma }}{(\land _{\mu <\gamma }{A_{\mu ,\gamma _{\epsilon }(\mu )})}}))$ , где $\{\gamma _{\epsilon }:\epsilon <\gamma ^{\gamma }\}$ это хорошо упорядоченный $\gamma ^{\gamma }$

Последние две схемы аксиом требуют выбора аксиомы, поскольку определенные множества должны быть хорошо упорядочиваемы . Последняя схема аксиом, строго говоря, не нужна, как это подразумевают законы дистрибутивности Чанга: ^[5] однако он включен как естественный способ допустить естественные ослабления логики.

Полнота, компактность и сильная полнота [ править ]

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

Логика в языке $L_{\alpha ,\beta }$ является полным, если для каждого предложения S, действительного в каждой модели, существует доказательство S . Оно является сильно полным, если для любой теории T для каждого предложения S, действительного в T, существует доказательство S из T . Бесконечная логика может быть полной, но не быть строго полной.

Кардинал $\kappa \neq \omega$ слабо компактна , когда для любой теории T из $L_{\kappa ,\kappa }$ содержащий не более $\kappa$ много формул, если каждое S $\subseteq$ T мощности менее $\kappa$ имеет модель, то T имеет модель. Кардинал $\kappa \neq \omega$ сильно компактен , когда для любой теории T из $L_{\kappa ,\kappa }$ , без ограничения размера, если каждый S $\subseteq$ T мощности менее $\kappa$ имеет модель, то T имеет модель.

Концепции, выражаемые логике в бесконечной

На языке теории множеств следующее утверждение выражает основание :

\forall _{\gamma <\omega }{V_{\gamma }:}\neg \land _{\gamma <\omega }{V_{\gamma +}\in V_{\gamma }}.\,

В отличие от аксиомы основания, это утверждение не допускает нестандартных интерпретаций. Понятие обоснованности может быть выражено только в логике, которая допускает бесконечное количество кванторов в отдельном утверждении. Как следствие, многие теории, включая арифметику Пеано , которая не может быть должным образом аксиоматизирована в финитарной логике, могут находиться в подходящей бесконечной логике. Другие примеры включают теории неархимедовых полей и групп без кручения . ^[6]^{[ нужен лучший источник ]}Эти три теории можно определить без использования бесконечной количественной оценки; только бесконечные соединения ^[7] необходимы.

Предикаты истинности для счетных языков определяются в ${\mathcal {L}}_{\omega _{1},\omega }$ . ^[8]

Полная бесконечная логика [ править ]

Две бесконечные логики выделяются своей полнотой. Это логика $L_{\omega ,\omega }$ и $L_{\omega _{1},\omega }$ . Первая представляет собой стандартную финитную логику первого порядка, а вторая — бесконечную логику, которая допускает только утверждения счетного размера.

Логика $L_{\omega ,\omega }$ также сильно полна, компактна и сильно компактна.

Логика $L_{\omega _{1},\omega }$ не является компактным, но полным (согласно приведенным выше аксиомам). Более того, он удовлетворяет варианту интерполяционного свойства Крейга.

Если логика $L_{\alpha ,\alpha }$ сильно полна (согласно приведенным выше аксиомам), то $\alpha$ сильно компактен (поскольку доказательства в этих логиках не могут использовать $\alpha$ или более данных аксиом).

Ссылки [ править ]

^ Мур, Грегори Х. (1997). «Предыстория бесконечной логики: 1885–1955». В Далла Кьяра, Мария Луиза ; Дотс, Кес; Мундичи, Даниэле; ван Бентем, Йохан (ред.). Структуры и нормы в науке . Springer-Science+Business Media. стр. 105–123. дои : 10.1007/978-94-017-0538-7_7 . ISBN 978-94-017-0538-7 .
^ Канамори, Акихиро (2004). «Цермело и теория множеств» (PDF) . Бюллетень символической логики . 10 (4): 487–553. дои : 10.2178/bsl/1102083759 . Проверено 22 августа 2023 г.
^ Вудин, В. Хью (2011). «Гипотеза континуума, мультивселенная общего положения множеств и гипотеза Ω» . В Кеннеди, Джульетта ; Коссак, Роман (ред.). Теория множеств, арифметика и основы математики: теоремы, философия . Издательство Кембриджского университета. стр. 13–42. дои : 10.1017/CBO9780511910616.003 . ISBN 978-0-511-91061-6 . Проверено 1 марта 2024 г.
^ Карп 1964 , стр. 39–54.
^ Чанг, CC (1957). «О представлении α-полных булевых алгебр» . Труды Американского математического общества . 85 (1): 208–218. дои : 10.1090/S0002-9947-1957-0086792-1 .
^ Розингер, Элемер Э. (2010). «Четыре направления по математике и физике» . arXiv : 1003.0360 . CiteSeerX 10.1.1.760.6726 .
^ Беннетт, Дэвид В. (1980). «Соединения» . Журнал формальной логики Нотр-Дама . 21 (1): 111–118. дои : 10.1305/ndjfl/1093882943 .
^ Погоновский, Ежи (10 июня 2010 г.). «Невыразимая тоска по намеченной модели» (PDF) . Кафедра прикладной логики . Университет Адам Мицкевич в Познани . п. 4 . Проверено 1 марта 2024 г.

Источники [ править ]

Карп, Кэрол Р. (1964). Языки с выражениями бесконечной длины . Издательство Северной Голландии. дои : 10.1016/S0049-237X(08)70423-3 . ISBN 978-0-444-53401-9 .
Барвайз, Джон (1969). «Бесконечная логика и допустимые множества». Журнал символической логики . 34 (2): 226–252. дои : 10.2307/2271099 . JSTOR 2271099 .

[1] Мур, Грегори Х. (1997). «Предыстория бесконечной логики: 1885–1955». В Далла Кьяра, Мария Луиза ; Дотс, Кес; Мундичи, Даниэле; ван Бентем, Йохан (ред.). Структуры и нормы в науке . Springer-Science+Business Media. стр. 105–123. дои : 10.1007/978-94-017-0538-7_7 . ISBN 978-94-017-0538-7 .

[2] Канамори, Акихиро (2004). «Цермело и теория множеств» (PDF) . Бюллетень символической логики . 10 (4): 487–553. дои : 10.2178/bsl/1102083759 . Проверено 22 августа 2023 г.

[3] Вудин, В. Хью (2011). «Гипотеза континуума, мультивселенная общего положения множеств и гипотеза Ω» . В Кеннеди, Джульетта ; Коссак, Роман (ред.). Теория множеств, арифметика и основы математики: теоремы, философия . Издательство Кембриджского университета. стр. 13–42. дои : 10.1017/CBO9780511910616.003 . ISBN 978-0-511-91061-6 . Проверено 1 марта 2024 г.

[FOOTNOTEKarp196439–54-4] Карп 1964 , стр. 39–54.

[5] Чанг, CC (1957). «О представлении α-полных булевых алгебр» . Труды Американского математического общества . 85 (1): 208–218. дои : 10.1090/S0002-9947-1957-0086792-1 .

[6] Розингер, Элемер Э. (2010). «Четыре направления по математике и физике» . arXiv : 1003.0360 . CiteSeerX 10.1.1.760.6726 .

[7] Беннетт, Дэвид В. (1980). «Соединения» . Журнал формальной логики Нотр-Дама . 21 (1): 111–118. дои : 10.1305/ndjfl/1093882943 .

[8] Погоновский, Ежи (10 июня 2010 г.). «Невыразимая тоска по намеченной модели» (PDF) . Кафедра прикладной логики . Университет Адам Мицкевич в Познани . п. 4 . Проверено 1 марта 2024 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]