Логическая модель

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

Булевозначные модели были представлены Даной Скотт , Робертом М. Соловеем и Петром Вопенкой в ​​1960-х годах, чтобы помочь понять Пола Коэна метод принуждения . Они также связаны с семантикой алгебры Гейтинга в интуиционистской логике .

Определение

Зафиксируйте полную булеву алгебру B и язык первого порядка L ; сигнатура L будет . состоять из набора постоянных символов, функциональных символов и символов отношений

Логическая модель языка L состоит из вселенной M , которая представляет собой набор элементов (или имен ) вместе с интерпретациями символов. В частности, модель должна назначить каждому константному символу L элемент M , а также каждому n -арному функциональному символу f из L и каждому n -кортежу ⟨ a ₀ ,..., a _{n -1} ⟩ элементов M. , модель должна присвоить элемент M термину f ( a ₀ , an _{, ... -1} ).

Интерпретация атомных формул L . более сложна Каждой паре a и b элементов M модель должна присвоить значение истинности ‖ a = b ‖ выражению a = b ; это значение истинности взято из булевой B. алгебры Аналогично, для каждого n -арного символа отношения R из L и каждого n -кортежа ⟨ a ₀ ,..., a _{n -1} ⟩ элементов M модель должна назначить элемент B в качестве значения истинности ‖ R ( а ₀ ,..., а _{n -1} ) ‖.

Интерпретация других формул и предложений

Значения истинности атомарных формул можно использовать для восстановления значений истинности более сложных формул, используя структуру булевой алгебры. Для пропозициональных связок это легко; просто применяются соответствующие логические операторы к значениям истинности подформул. Например, если φ( x ) и ψ( y , z ) являются формулами с одной и двумя свободными переменными соответственно, и если a , b , c являются элементами вселенной модели, которые должны быть заменены вместо x , y и z , тогда истинностное значение

$\phi (a)\land \psi (b,c)$

это просто

$\|\phi (a)\land \psi (b,c)\|=\|\phi (a)\|\ \land \ \|\psi (b,c)\|$

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

$\|\exists x\phi (x)\|=\bigvee _{a\in M}\|\phi (a)\|,$

где правую часть следует понимать как верхнюю границу в B множества всех значений истинности ||φ( a )|| как диапазон над M .

Истинное значение формулы — это элемент полной булевой B. алгебры

Булевозначные модели теории множеств

Дана полная булева алгебра B существует булевозначная модель, обозначаемая V ^Б , который является булевым аналогом вселенной фон Неймана V . (Строго говоря, В. ^Б — это правильный класс , поэтому нам нужно соответствующим образом по-новому интерпретировать, что значит быть моделью . ) Неформально, элементы V ^Б являются «множествами с логическими значениями». Учитывая обычный набор A , каждый набор либо является, либо не является его членом; но если задан набор с логическим значением, каждый набор имеет определенную фиксированную степень членства в A .

Элементы булевого множества, в свою очередь, также являются булевыми множествами, элементы которых также являются булевыми множествами и так далее. Чтобы получить нециклическое определение булевозначного множества, они определяются индуктивно в иерархии, аналогичной кумулятивной иерархии . Для каждого ординала α из V множество V ^Б _α определяется следующим образом.

• V ^Б ₀ — пустое множество.
• V ^Б _{α +1} — множество всех функций из V ^Б _α к Б. ​(Такая функция представляет подмножество V собой ^Б _α ; если f — такая функция, то для любого x ∈ V ^Б _α , значение f ( x ) — это степень членства x в наборе.)
• Если α — предельный ординал, V ^Б _α — объединение V ^Б _β для β < α .

Класс V ^Б определяется как объединение всех множеств V ^Б _а .

Также возможно релятивизировать всю эту конструкцию к некоторой транзитивной модели ( или M ZF иногда ее фрагменту). Булевозначная модель M ^Б получается применением описанной выше конструкции внутри M . Ограничение на транзитивные модели не является серьезным, поскольку теорема о коллапсе Мостовского подразумевает, что каждая «разумная» (хорошо обоснованная, экстенсиональная) модель изоморфна транзитивной. (Если модель M не является транзитивной, все становится еще сложнее, поскольку интерпретация M того, что значит быть «функцией» или «ординалом», может отличаться от «внешней» интерпретации.)

Как только элементы V ^Б определены, как указано выше, необходимо определить B -значные отношения равенства и принадлежности на V ^Б . Здесь B -значное отношение на V ^Б является функцией из V ^Б × V ^Б к Б. ​Чтобы избежать путаницы с обычным равенством и членством, они обозначаются ‖ x = y ‖ и ‖ x ∈ y ‖ для x и y в V ^Б . Они определяются следующим образом:

‖ x ∈ y ‖ определяется как Σ _{t ∈ Dom( y )} ‖ x = t ‖ ∧ y ( t ) (« x находится в y , если он равен чему-то в y »).

‖ x = y ‖ определяется как ‖ x ⊆ y ‖∧‖ y ⊆ x ‖ (« x равно y , если x и y являются подмножествами друг друга»), где

‖ x ⊆ y ‖ определяется как Π _{t ∈ Dom( x )} x ( t ) ⇒ ‖ t ∈ y ‖ (« x является подмножеством y , если все элементы x находятся в y »)

Символы Σ и Π обозначают соответственно операции наименьшей верхней и наибольшей нижней грани в полной булевой алгебре B . На первый взгляд приведенные выше определения кажутся закольцованными: ‖ ∈ ‖ зависит от ‖ = ‖, которое зависит от ‖ ⊆ ‖, которое зависит от ‖ ∈ ‖. Однако внимательное рассмотрение показывает, что определение ‖ ∈ ‖ зависит только от ‖ ∈ ‖ для элементов меньшего ранга, поэтому ‖ ∈ ‖ и ‖ = ‖ являются корректно определенными функциями из V ^Б × V ^Б к Б. ​

Можно показать, что B -значные отношения ‖ ∈ ‖ и ‖ = ‖ на V ^Б сделать V ^Б в булевозначную модель теории множеств. Каждое предложение теории множеств первого порядка без свободных переменных имеет истинностное значение в B ; необходимо показать, что аксиомы равенства и все аксиомы теории множеств ZF (написанные без свободных переменных) имеют значение истинности 1 (наибольший элемент B ). Это доказательство простое, но длинное, поскольку необходимо проверить множество различных аксиом.

Связь с принуждением

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

• синтаксическое принуждение Принуждающее отношение $p\Vdash \phi$ определяется между элементами p частично упорядоченного множества и формулами φ языка принуждения . Это отношение определяется синтаксически и не имеет семантики; то есть ни одна модель никогда не производится. Скорее, начиная с предположения, что ZFC (или какая-либо другая аксиоматизация теории множеств) доказывает независимое утверждение, можно показать, что ZFC также должен быть способен доказать противоречие. Однако воздействие происходит «более V »; то есть нет необходимости начинать со счетной транзитивной модели. См. Кунен (1980) для описания этого метода.
• Счетные транзитивные модели. Начинаем со счетной транзитивной модели M, содержащей столько теории множеств, сколько необходимо для желаемой цели и содержащей ЧУ-множество. Тогда существуют фильтры в ЧУУ, которые являются общими для M ; то есть они соответствуют всем плотным открытым подмножествам ЧУУ, которые также являются элементами M .
• вымышленные общие объекты Обычно теоретики множеств просто делают вид , что ЧУ-множество имеет подмножество, которое является общим для всего V . Этот общий объект в нетривиальных случаях не может быть элементом V и, следовательно, «на самом деле не существует». (Конечно, является предметом философского спора, «существуют ли какие-либо множества на самом деле», но это выходит за рамки текущего обсуждения.) При небольшой практике этот метод полезен и надежен, но может оказаться неудовлетворительным с философской точки зрения.

Логические модели и синтаксическое принуждение

Модели с логическими значениями можно использовать для придания семантики синтаксическому принуждению; заплаченная цена заключается в том, что семантика не является двузначной («истина или ложь»), а присваивает значения истинности из некоторой полной булевой алгебры. Для заданного форсирующего ЧУ множества P существует соответствующая полная булева алгебра B , часто получаемая как совокупность регулярных открытых подмножеств P закрытыми , где топология P нижних определяется путем объявления всех множеств открытыми (и всех верхних множеств ). (Другие подходы к построению B обсуждаются ниже.)

Теперь порядок на B (после удаления нулевого элемента) может заменить P для целей принуждения, и отношение принуждения можно интерпретировать семантически, говоря, что для p - элемента B и φ - формулы языка принуждения,

$p\Vdash \phi \iff p\leq ||\phi ||$

где ||φ|| — истинное значение φ в V ^Б .

Этот подход позволяет присвоить семантику принудительному использованию V, не прибегая к вымышленным родовым объектам. Недостатки заключаются в том, что семантика не является двузначной и что комбинаторика B часто более сложна, чем комбинаторика базового частичного множества P .

Булевы модели и универсальные объекты над

Одна интерпретация принуждения начинается со счетной транзитивной модели M теории множеств ZF, частично упорядоченного множества P и «общего» подмножества G из P и строит новую модель теории множеств ZF из этих объектов. (Условия счетности и транзитивности модели упрощают некоторые технические проблемы, но не являются существенными.) Построение Коэна можно осуществить с использованием булевозначных моделей следующим образом.

• Постройте полную булеву алгебру B как полную булеву алгебру, «порожденную» частично упорядоченным множеством P .
• Постройте ультрафильтр U на B (или, что то же самое, гомоморфизм B в булеву алгебру {true, false}) из общего подмножества G в P .
• Используйте гомоморфизм от B до {true, false}, чтобы превратить булевозначную модель M ^Б раздела выше в обычную модель ZF.

Теперь мы объясним эти шаги более подробно.

Для любого чу-множества P существует полная булева алгебра B и отображение e из P в B. ⁺ (ненулевые элементы B ), такие что изображение плотное, e ( p ) ≤ e ( q ) всякий раз, когда p ≤ q , и e ( p ) e ( q ) = 0 всякий раз, когда p и q несовместимы. Эта булева алгебра единственна с точностью до изоморфизма. Ее можно построить как алгебру регулярных открытых множеств в топологическом пространстве P (с базовым множеством P и базой, заданной множествами U _p элементов q с ​​q ≤ p ).

Отображение частично упорядоченного множества P в полную булеву алгебру B, вообще говоря, не инъективно. Отображение инъективно тогда и только тогда, когда P обладает следующим свойством: если каждый r ⩽ p совместим с q , то p ⩽ q .

Ультрафильтр U на B определяется как набор элементов b из B , которые больше, чем некоторый элемент (образ) G . Учитывая ультрафильтр U на булевой алгебре, мы получаем гомоморфизм {true, false}отображая U в истину, а его дополнение в ложь. И наоборот, при таком гомоморфизме прообраз true является ультрафильтром, поэтому ультрафильтры по сути такие же, как гомоморфизмы {true, false}. (Алгебраисты могут предпочесть использовать максимальные идеалы вместо ультрафильтров: дополнение ультрафильтра является максимальным идеалом, и наоборот, дополнением максимального идеала является ультрафильтр.)

Если g — гомоморфизм булевой алгебры B в булеву алгебру C и M ^Б есть ли какой-нибудь B -значную модель ZF (или любой другой теории в этом отношении) мы можем превратить M ^Б в C -значную модель путем применения гомоморфизма g к значению всех формул. В частности, если C равно {true, false}, мы получаем модель со значением {true, false}. Это почти то же самое, что и обычная модель: фактически мы получаем обычную модель на множестве классов эквивалентности при || = || модели со значением {true, false}. мы получаем обычную модель теории множеств ZF, начиная с M , булевой алгебры B и ультрафильтра U на B. Итак , (Построенная таким образом модель ZF не является транзитивной. На практике применяется теорема о коллапсе Мостовского, чтобы превратить ее в транзитивную модель.)

Мы видели, что форсирование можно выполнить с использованием булевозначных моделей, построив булеву алгебру с ультрафильтром из частично упорядоченного множества с общим подмножеством. Также возможно пойти другим путем: учитывая булеву алгебру B , мы можем сформировать частичное множество P из всех ненулевых элементов B и общий ультрафильтр на B ограничивается общим набором на P. , Таким образом, методы форсирования и булевозначных моделей по сути эквивалентны.

Ссылки

• Белл, Дж. Л. (1985) Булевы модели и доказательства независимости в теории множеств , Оксфорд. ISBN   0-19-853241-5
• Гришин, В.Н. (2001) [1994], «Булевозначная модель» , Энциклопедия Математики , EMS Press
• Джех, Томас (2002). Теория множеств, издание третьего тысячелетия (переработанное и дополненное) . Спрингер. ISBN  3-540-44085-2 . OCLC   174929965 .
• Кунен, Кеннет (1980). Теория множеств: введение в доказательства независимости . Северная Голландия. ISBN  0-444-85401-0 . OCLC   12808956 .
• Кусраев А.Г. и С.С. Кутателадзе (1999). Булевозначный анализ . Академическое издательство Клювер. ISBN  0-7923-5921-6 . OCLC   41967176 . Содержит описание булевозначных моделей и приложений к пространствам Рисса, банаховым пространствам и алгебрам.
• Манин, Ю. И. (1977). Курс математической логики . Спрингер. ISBN  0-387-90243-0 . ОСЛК   2797938 . Содержит описание принудительных и булевых моделей, написанное для математиков, не являющихся теоретиками множеств.
• Россер, Дж. Баркли (1969). Упрощенные доказательства независимости, булевозначные модели теории множеств . Академическая пресса.