WikiDer > Конструктивная теория множеств

Constructive set theory

Конструктивная теория множеств - это подход к математический конструктивизм следуя программе аксиоматическая теория множеств.Такой же первый заказ язык с "" и ""классической теории множеств", поэтому не следует путать конструктивные типы С другой стороны, некоторые конструктивные теории действительно мотивированы их интерпретируемостью в теориях типов.

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

Обзор

Логика обсуждаемых здесь теорий такова: конструктивный в этом он отвергает , т.е. что дизъюнкция автоматически выполняется для всех предложений. Это требует отказа от строгих принципов выбора и переформулировки некоторых стандартных аксиом. Например, Аксиома выбора подразумевает для формул в принятой схеме разделения, Теорема Диаконеску. Аналогичные результаты справедливы для Аксиома регулярности в его стандартной форме. В свою очередь, конструктивные теории часто не допускают доказательств свойств, доказуемо вычислительно неразрешимый а также обычно не доказывают существование отношений, которые не могут быть реализованы. Это также влияет на доказуемость утверждений о полных порядках, таких как порядок всех порядковые номера, выражается истинностью и отрицанием членов в порядке, определяющем дизъюнкцию . Это, в свою очередь, влияет на теоретическую силу доказательства, определенную в порядковый анализ. Тем не менее, теории без стремятся доказать классически эквивалентные переформулировки классических теорем. Например, в Конструктивный анализ нельзя доказать теорема о промежуточном значении в его учебной формулировке, но можно доказать теоремы с алгоритмическим содержанием, которые, как только предполагается, сразу классически эквивалентны классическому утверждению. Разница в том, что конструктивные доказательства найти сложнее.

Предмет конструктивной теории множеств, начатый Джон Майхиллработает над теория множеств, теория нескольких видов и ограниченной количественной оценки, целью которой является обеспечение формальной основы для Эрретт Бишоппрограмма конструктивной математики. Ниже мы перечислим последовательность теорий на том же языке, что и , ведущих к Питер Акзельхорошо изучен конструктивная Цермело-Френкель,[1] и дальше. также характеризуется двумя особенностями, присутствующими также в теории Майхилла: с одной стороны, он использует Предикативное разделение вместо полной, неограниченной схемы разделения. Ограниченность может рассматриваться как синтаксическое свойство или, альтернативно, теории могут быть консервативно расширены с помощью более высокого предиката ограниченности и его аксиом. Во-вторых, непредсказуемый Аксиома Powerset отбрасывается, как правило, в пользу связанных, но более слабых аксиом. Сильная форма очень случайно используется в классический общая топология. Конструктивные теории также предъявляют более строгие требования к тому, какие множества составляют функцию. Добавление теории даже слабее, чем восстанавливает , как подробно описано ниже. Система, известная как интуиционистская теория множеств Цермело – Френкеля, , является сильной теорией множеств без . Это похоже на , но менее консервативны или предикативныйТеория обозначила конструктивная версия , классический Теория множеств Крипке – Платека. где даже Аксиома Коллекции ограничена.

Многие теории, изучаемые конструктивной теорией множеств, являются простыми ограничениями по отношению к их аксиомам, а также лежащей в их основе логике. Теория множеств Цермело – Френкеля (). Такие теории также могут быть интерпретированы в любой модели Что касается конструктивных реализаций, то здесь осуществимость теория и Aczel's был истолкован в Теории типа Мартина Лёфа, как описано ниже. Таким образом, теоремы теории множеств доказуемы в а более слабые теории - кандидаты для компьютерной реализации. предпучка были введены модели для конструктивных теорий множеств. Они аналогичны неопубликованным моделям Preheaf для интуиционистской теории множеств, разработанным Дана Скотт в 1980-е гг.[2][3]

Подтеории ZF

В этом разделе мы обсуждаем общие кандидаты в аксиомы, которые составляют структуру, в которой все доказательства также являются доказательствами в .

Обозначение класса

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

Квантификаторы превышают набор, и они обозначаются строчными буквами. Как это часто бывает при изучении теории множеств, для обозначения классы, которые в большинстве случаев не являются частью объектного языка, но используются для краткого обсуждения. В частности, можно ввести объявления обозначений соответствующего класса через "", чтобы выразить в качестве . Логически эквивалентные предикаты могут использоваться для введения одного и того же класса. Еще один пишет как сокращение для .

Как обычно, мы можем сокращать к и выражает требование подкласса , т.е. , к . Для собственности , банально . Отсюда следует, что .

Обратите внимание, что в конструктивной интерпретации элементы подкласса из может содержать больше информации, чем . Также, как может быть не разрешимым для всех элементов в , эти два класса необходимо различать априори.

Общие аксиомы

Начнем с аксиомы, которые практически всегда считаются бесспорными и являются частью всех теорий, рассматриваемых в этой статье.

Обозначим через утверждение, выражающее, что два класса имеют точно такие же элементы, т.е. , или эквивалентно . Следующая аксиома дает возможность доказать равенство ""двух множеств, так что при подстановке любой предикат о переводится как один из .

Расширяемость

По логическим свойствам равенства обратное направление выполняется автоматически.

Рассмотрим недвижимость что доказуемо справедливо для всех элементов множества , так что , и предположим, что левая часть установлена ​​как множество. Обратите внимание, что даже если этот набор слева неофициально также связан с релевантной для доказательства информацией о действительности для всех элементов аксиома Extensionality постулирует, что в нашей теории множеств набор в левой части оценивается равным множеству в правой части.

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

Сопряжение

и

Союз

Эти две аксиомы также можно сформулировать сильнее в терминах «", например, в контексте в этом нет необходимости.

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

Свойство, которое является ложным для любого набора, соответствует пустому классу, обозначенному или же . То, что это набор, легко следует из других аксиом, таких как Аксиома бесконечности ниже. Но если, например, кто-то явно заинтересован в исключении бесконечных множеств из своих исследований, на этом этапе можно принять

Пустой набор

BCST

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

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

Схема аксиом предикативного разделения: Для любого ограниченного предиката с не бесплатно в нем,

также называется ограниченным разделением, т.е. Разделение только для ограниченных кванторов. Это равносильно постулированию существования множества полученный пересечением любого множества и любой предикативно описанный класс . Когда предикат принимается как за доказано, что это множество, получается двоичное пересечение множеств и записывается . Ограничение в аксиоме - это тоже привратник. непредсказуемый определения. Например, без Аксиома власти, не стоит ожидать класса определяется как быть набором, где обозначает некоторый 2-арный предикат. Обратите внимание: если этот подкласс доказуемо является множеством, то термин таким образом определенное также находится в области переменной термина используется для его определения.

Хотя, таким образом, предикативное разделение приводит к тому, что меньшее количество заданных определений классов является наборами, необходимо подчеркнуть, что многие определения классов, которые классически эквивалентны, не являются таковыми, если ограничиваться конструктивной логикой. Таким образом, можно получить более богатую конструктивную теорию множеств. неразрешимость Что касается общих предикатов, то понятие подмножества гораздо более разработано в конструктивных теориях множеств, чем в классических, как мы увидим.

Как отмечалось, из Разделения и существования любого набора (например, Бесконечности ниже) и предиката, который является ложным для любого набора, будет следовать существование пустого набора.

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

Далее рассмотрим

Схема аксиомы замены: Для любого предиката ,

куда обозначает уникальное существование. Он предоставляет существование в виде наборов ряда функционально-подобных предикатов, полученных через их домены.

С помощью схемы замены эта теория доказывает, что классы эквивалентности или же индексированные суммы есть наборы. В частности, Декартово произведение, содержащий все пары элементов двух наборов, является набором.

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

В , Замена наиболее важна, чтобы доказать наличие набора высокой классифицировать, а именно через экземпляры схемы аксиом где относится относительно небольшой набор к большим, .

Конструктивные теории множеств обычно имеют схему аксиом замены, иногда ограниченную ограниченными формулами. Однако, когда отбрасываются другие аксиомы, эта схема на самом деле часто усиливается - не более того. , но вместо этого просто чтобы вернуть некоторую силу доказуемости.

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

Функции

Мы можем говорить о общий функционал связь когда

,

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

Позволять (также написано ) обозначают класс таких функций множества.Когда функции понимаются как просто функциональные графики, как указано выше, утверждение принадлежности также написано . В теории типов выражение ""существует сам по себе и означает функциональные пространствапримитивное понятие. Эти классы естественно появляются, например, как тип карри взаимное соответствие между и , примыкание. Теории конструктивных множеств также изучаются в контексте аппликативные аксиомы.

Написать за . Учитывая любые , теперь мы пришли к рассуждению о таких классах, как

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

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

ECST

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

Для некоторого фиксированного предиката , заявление заявляет, что это самый маленький набор среди всех наборов для которого Элементарная конструктивная теория множеств имеет аксиому а также

Сильная бесконечность

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

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

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

С этим, доказывает индукция для всех предикатов, задаваемых ограниченными формулами. Двое из пяти Аксиомы Пеано касательно и один о закрытии относительно справедливо следуют непосредственно из аксиом бесконечности. Ну наконец то, можно доказать, что это инъективная операция.

Выбор

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

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

В заключение мы сделаем замечание, чтобы подчеркнуть силу выбора и его связь с вопросами Преднамеренность.Рассмотрим субконечные множества

Полная Аксиома Выбора, разрешающая существование карты на различимые элементы, подразумевает, что . Таким образом, утверждение о существовании общих функций выбора в образ функции с разрешимым равенством (исключенное среднее выполняется в области) неконструктивно. Мы знаем, что по крайней мере и , невзирая на . Также обратите внимание, что у нас есть . Таким образом, Separation связывает предикаты для установления равенства и, в свою очередь, с информацией о функциях. Обратите внимание: если мы обнаружим, что , то есть только один возможный вход функции в . Итак, при рассмотрении функционального назначения , то безоговорочно заявляя или выводя, что не будет последовательным. Конечно, здесь слишком мало известно о домене , в отличие от дискретной области натуральных чисел.

Арифметика

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

Однако теория до сих пор не интерпретирует полную примитивная рекурсия. В самом деле, несмотря на наличие аксиомы замены, теория до сих пор не доказывает, что добавление является функцией множества. С этой целью аксиома предоставление определения функций набора через функции набора шагов итерации должны быть добавлены. Мы хотели бы, чтобы теория интерпретировала Пеано арифметика или, точнее, Арифметика Гейтинга , то есть четыре правила сложения и умножения. Для этого необходим итерационный принцип, который является теоретическим эквивалентом объект натуральных чисел. Принцип подразумевается, если предположить, что класс функций

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

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

Возведение в степень

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

Теперь рассмотрим аксиому :

Возведение в степень

На словах аксиомы говорят, что для двух наборов , класс всех функций, по сути, тоже есть набор. Такие импликации, безусловно, необходимы, например, для формализации карты объектов внутреннего hom-функтор подобно .

Для любой формулы , класс равно когда могут быть отклонены и когда можно доказать, но также может быть вообще не разрешимой. С этой точки зрения класс мощности синглтона , т.е. или неофициально и обычно обозначается , называется алгеброй истинностных значений. Предполагая, что все формулы разрешимы, т.е. , можно показать не только то, что - это набор, а точнее, это двухэлементный набор. Предполагая для ограниченных формул Separation позволяет продемонстрировать, что любой powerclass является набором. В качестве альтернативы, полный набор мощности эквивалентен простому предположению, что класс всех подмножеств образует набор. Полное разделение эквивалентно предположению, что каждый подкласс это набор.

Таким образом, в этом контексте функциональные пространства более доступны, чем классы подмножества, как и в случае с экспоненциальные объекты соотв. подобъекты в теории категорий. В теоретическая категория термины, теория по существу соответствует конструктивно четко обозначенный Декартово закрыто Heyting предварительнотопы с (всякий раз, когда принимается Infinity) a объект натуральных чисел. Существование powerset - вот что могло бы превратить претензии Гейтинга в элементарные топосы. Каждый такой топос, который интерпретирует является, конечно, моделью этих более слабых теорий, но были определены локально декартовы замкнутые претопозы, например интерпретировать но отвергайте полное разделение и набор степеней. Возведение в степень не подразумевает полной математической индукции.

К реальному

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

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

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

Теория, данная аксиомами, пока подтверждает, что псевдо-упорядоченное поле это также Архимедов и Дедекинд полный, если он вообще существует, таким образом характеризуется однозначно с точностью до изоморфизма. «Псевдо-» здесь подчеркивает, что порядок в любом случае не всегда будет конструктивно разрешим. Однако существование только функциональных пространств, таких как не дает быть набором, и поэтому ни один из классов не может быть которые действительно выполняют названные свойства. Что требуется для того, чтобы класс действительных чисел Дедекинда был множеством, так это аксиома о существовании множества подмножеств.

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

Индукция

Математическая индукция

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

Схема аксиомы полного математическая индукция: Для любого предиката на ,

Здесь обозначает и набор обозначает последовательный набор , с . Согласно Аксиоме Бесконечности, приведенной выше, он снова является членом .

Аксиома индукции подразумевается полной схемой разделения. Можно увидеть, что это связано с тем, что индукция приводит к выводу о классе .

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

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

Установить индукцию

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

Аксиома читается следующим образом

Схема аксиом индукции Сета: Для любого предиката ,

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

В Аксиома регулярности вместе с (ограниченным) разделением подразумевает индукцию множества, но также (ограниченное) , поэтому регулярность неконструктивна. Наоборот, вместе с Set Induction подразумевает Регулярность.

Metalogic

Теперь это охватывает варианты всех восьми аксиом Цермеоло-Френкеля. Расширение, соединение, объединение и замена действительно идентичны. Бесконечность выражена в сильной формулировке и подразумевает набор пустоты, как в классическом случае. Разделение, в классическом изложении избыточно, конструктивно не подразумевается заменой. Без Закон исключенного среднего, теории здесь не хватает полного разделения, Powerset, а также регулярности в ее обычной форме.

Теория не сильнее чем Арифметика Гейтинга но добавление на этом этапе приведет к теории, выходящей за рамки типичных теория типов: Предполагая разделение в неограниченной форме, затем добавляя к дает теорию, доказывающую те же теоремы, что и минус Регулярность! Таким образом, добавляя к этой структуре дает и добавление к нему выбора дает .

Дополнительная теоретическая сила доказательства, достигаемая с помощью индукции в конструктивном контексте, является значительной, даже если отбросить регулярность в контексте не снижает доказательственно-теоретической прочности. Обратите внимание, что Aczel также был одним из основных разработчиков или Необоснованная теория множеств, который отвергает эту последнюю аксиому.

Сильная коллекция

Со всеми ослабленными аксиомами и теперь, выходя за рамки этих аксиом, также замеченных в типизированном подходе Майхилла, теория, названная (теория с возведением в степень) усиливает схему сбора следующим образом:

Схема аксиом сильной коллекции: для любого предиката ,

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

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

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

Metalogic

Эта теория без , безграничное разделение и «наивный» набор Power обладает множеством приятных свойств. Например, в нем Собственность существования: Если для любого свойства , теория доказывает, что существует множество, обладающее этим свойством, т. е. если теория доказывает утверждение , то есть еще свойство который однозначно описывает такой набор экземпляров. т.е. теория тогда также доказывает Это можно сравнить с арифметикой Гейтинга, где теоремы осуществленный конкретными натуральными числами и обладают этими свойствами. В теории множеств роль играют определенные множества. Для контраста напомним, что в , из Аксиомы выбора следует Теорема о хорошем порядке, так что общие порядки с наименьшим элементом для множеств типа формально доказано существование, даже если доказуемо невозможно описать такой порядок.

Конструктивный Цермело – Френкель

Можно подойти к множеству Power и дальше, не теряя теоретической интерпретации типов. Теория, известная как является плюс более сильная форма возведения в степень. Это путем принятия следующей альтернативы, которую снова можно рассматривать как конструктивную версию Аксиома силового набора:

Схема аксиом коллекции подмножеств: для любого предиката ,

Эта схема аксиомы Коллекции Подмножеств эквивалентна единственной и несколько более ясной альтернативной Аксиоме Полноты. С этой целью пусть это класс всех тотальных отношений между а и б, этот класс задается как

При этом мы можем заявить , альтернатива Subset Collection. Гарантирует, что существует хоть какой-то набор сохраняю хорошее количество желаемых отношений. Более конкретно, между любыми двумя наборами и , есть набор который содержит полное отношение для любого общего отношения из к .

Аксиома полноты:

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

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

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

Metalogic

В этой теории отсутствует свойство существования из-за схемы, но в 1977 году Акцель показал, что все еще можно интерпретировать в Теория типа Мартина-Лёфа,[4] (с использованием предложения как типы подход), предоставляя то, что сейчас рассматривается как стандартная модель в теории типов.[5]Это делается в терминах образов его функций, а также в виде достаточно прямого конструктивного и предикативного обоснования, сохраняя при этом язык теории множеств. В качестве таких, имеет скромную теоретическую силу доказательства, см. : Порядковый номер Бахмана – Ховарда.

Разрыв с ZF

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

В 1989 году Ингрид Линдстрем показала, что необоснованные множества полученный заменой эквивалента Аксиома Основания (Индукция) в с Антиосновная аксиома Акзеля () также можно интерпретировать в теории типа Мартина-Лёфа.[6]

Интуиционистский Цермело – Френкель

Теория является со стандартом Разделение и Набор мощности.

Здесь вместо Схема аксиомы замены, мы можем использовать

Схема аксиомы коллекции: Для любого предиката ,

В то время как аксиома замены требует соотношения быть функциональный по набору (например, для каждого в связан ровно один ), Аксиома Коллекции - нет, она просто требует, чтобы был ассоциирован хотя бы один , и он утверждает существование набора, который собирает хотя бы один такой для каждого такого . вместе с Сборником подразумевает Замена.

В качестве таких, можно рассматривать как наиболее простой вариант без .

Metalogic

Изменив схему аксиомы Замены на схему аксиомы Коллекции, полученная теория будет иметь Собственность существования.

Даже без , то доказательство теоретической силы из равен тому из .

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

История

В 1973 г. Джон Майхилл предложил систему теории множеств, основанную на интуиционистская логика[7] взяв самый обычный фундамент, , и выбросив Аксиома выбора и закон исключенного среднего, оставив все остальное как есть. Однако разные формы некоторых аксиомы, эквивалентные в классическом контексте, не эквивалентны в конструктивном контексте, а некоторые формы подразумевают . В этих случаях для конструктивной теории множеств были приняты интуиционистски более слабые формулировки.

Интуиционистский Z

Снова на более слабом конце, как и в случае с его историческим аналогом Теория множеств Цермело, можно обозначить через интуиционистская теория, созданная как но без замены, сбора или индукции.

Интуиционистский КП

Отметим еще одну очень слабую теорию, которая была исследована, а именно интуиционистскую (или конструктивную) Теория множеств Крипке – Платека. Теория имеет не только Разделение, но и Ограничение Коллекции, т.е. но с индукцией вместо полной замены. Она особенно слаба при изучении без бесконечности. теория не вписывается в иерархию, представленную выше, просто потому, что она имеет Схема аксиом индукции множеств от начала. Это позволяет использовать теоремы, включающие класс ординалов.

Отсортированные теории

Конструктивная теория множеств

В его представлении система Майхилла конструктивная логика первого порядка с идентичностью и тремя сортирует, а именно множества, натуральные числа, функции:

И, кроме того:

Теория множеств стиля епископа

Теория множеств во вкусе Эрретт БишопКонструктивистская школа России является зеркальным отражением школы Майхилла, но построена таким образом, что наборы снабжены отношениями, которые регулируют их дискретность. Обычно применяется зависимый выбор.

Категории теории

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

Кроме того, топои также имеют внутренние языки которые сами могут быть интуитивными и улавливать понятие множеств.

Смотрите также

Рекомендации

  1. ^ Питер Акзель и Майкл Ратьен, Заметки по теории конструктивных множеств, Reports Institut Mittag-Leffler, Mathematical Logic - 2000/2001, No. 40
  2. ^ Гамбино, Н. (2005). «МОДЕЛИ ПРЕДШЕФОВ ДЛЯ КОНСТРУКТИВНЫХ ТЕОРИЙ МНОЖЕСТВА» (PDF). В Лаура Кросилья и Питер Шустер (ред.). От множеств и типов к топологии и анализу (PDF). С. 62–96. Дои:10.1093 / acprof: oso / 9780198566519.003.0004. ISBN 9780198566519.
  3. ^ Скотт, Д. С. (1985). Теоретико-категориальные модели интуиционистской теории множеств. Рукописные слайды выступления в Университете Карнеги-Меллона
  4. ^ Aczel, Peter: 1978. Теоретико-типовая интерпретация конструктивной теории множеств. В: A. MacIntyre et al. (ред.), Logic Colloquium '77, Amsterdam: North-Holland, 55–66.
  5. ^ Ратиен, М. (2004), «Предикативность, цикличность и антифундамент» (PDF), в Link, Годехард (ред.), Сто лет парадокса Рассела: математика, логика, философия, Вальтер де Грюйтер, ISBN 978-3-11-019968-0
  6. ^ Линдстрем, Ингрид: 1989. Построение необоснованных множеств в рамках теории типов Мартина-Лёфа. Журнал символической логики 54: 57–64.
  7. ^ Myhill, "Некоторые свойства интуиционистской теории множеств Цермело-Френкеля", Труды Кембриджской летней школы по математической логике 1971 г. (Конспект лекций по математике 337) (1973), стр. 206-231

дальнейшее чтение

внешняя ссылка