Конструктивная теория множеств - Constructive set theory

Конструктивная теория множеств - это подход к математическому конструктивизму, следующий программе аксиоматической теории множеств . Же первый порядок язык с « » и « » из классических теории множеств обычно используется, так что это не следует путать с конструктивными типами сближаться. С другой стороны, некоторые конструктивные теории действительно мотивированы их интерпретируемостью в теориях типов . ${\ displaystyle =}$${\ displaystyle \ in}$

В дополнение к отрицанию закона исключенного среднего ( ), конструктивные теории множеств часто требуют, чтобы некоторые логические кванторы в своих аксиомах были ограничены , мотивированные результатами, привязанными к непредсказуемости . ${\ displaystyle {\ mathrm {LEM}}}$

Вступление

Перспективы

Логика обсуждаемых здесь теорий множеств конструктивна в том смысле , что она отвергает , т. Е. Дизъюнкция автоматически выполняется для всех предложений. Затем это требует отказа от принципов строгого выбора и переформулировки некоторых стандартных аксиом. Например, Аксиома выбора подразумевает формулы в принятой схеме Разделения по теореме Дьяконеску . Аналогичные результаты справедливы для аксиомы регулярности в ее стандартной форме. Как правило, чтобы доказать ту или иную дизъюнкцию , нужно доказать либо , либо . В этом случае один говорит, что дизъюнкция разрешима. В свою очередь, конструктивные теории обычно не допускают многих классических доказательств свойств, которые, например, доказуемо вычислительно неразрешимы . В отличие от более консервативной минимальной логики , здесь лежащая в основе логика допускает исключение двойного отрицания для разрешимых предикатов, а формулировки теорем относительно конечных конструкций обычно не отличаются от их классических аналогов. ${\ displaystyle {\ mathrm {LEM}}}$ ${\ Displaystyle \ фи \ лор \ нег \ фи}$${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle P \ lor \ neg P}$${\ displaystyle P}$${\ displaystyle \ neg P}$

Примечательно, что ограничение конструктивной логики приводит к более строгим требованиям относительно того, какие характеристики набора, включающего неограниченные коллекции, составляют (математическую и, следовательно, всегда подразумевающую итоговую ) функцию. Часто это происходит потому, что предикат в случайном определении может быть неразрешимым. По сравнению с классическим аналогом, как правило, меньше шансов доказать существование отношений, которые не могут быть реализованы. Затем это также влияет на доказуемость утверждений о полных порядках, таких как порядок всех порядковых чисел , выраженных истинностью и отрицанием членов в порядке, определяющем дизъюнкцию . А это, в свою очередь, влияет на теоретическую силу доказательства, определяемую порядковым анализом . ${\ displaystyle f \ subset X \ times Y}$${\ Displaystyle (\ альфа \ в \ бета) \ лор (\ альфа = \ бета) \ лор (\ бета \ в \ альфа)}$

Тем не менее, конструктивные математические теории обычно имеют тенденцию доказывать классически эквивалентные переформулировки классических теорем. Например, в конструктивном анализе нельзя доказать теорему о промежуточном значении в ее учебной формулировке, но можно доказать теоремы с алгоритмическим содержанием, которые, как только предполагается, они сразу же классически эквивалентны классическому утверждению. Разница в том, что конструктивные доказательства найти сложнее. ${\ displaystyle {\ mathrm {LEM}}}$

На моделях

Многие теории, изучаемые в конструктивной теории множеств, являются простыми ограничениями теории множеств Цермело – Френкеля ( ) в${\ displaystyle {\ mathsf {ZF}}}$ отношении их аксиом, а также лежащей в их основе логики. Такие теории также можно интерпретировать в любой модели . Что касается конструктивных реализаций, то существует теория реализуемости, а конструктивная теория Цермело-Френкеля ( ) Акцеля была интерпретирована в теориях типа Мартина-Лёфа , как описано ниже. Таким образом, теоремы теории множеств, доказуемые в и более слабые теории, являются кандидатами для компьютерной реализации. Совсем недавно были введены предпучковые модели для конструктивных теорий множеств. Они аналогичны неопубликованным моделям Прешифа для интуиционистской теории множеств, разработанным Даной Скотт в 1980-х годах. ${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZF}}}$

Обзор

Предмет теории конструктивных множеств (часто " "), начатый работой Джона Майхилла по теории, также называемой теорией нескольких видов и ограниченной квантификацией, с целью обеспечить формальную основу для программы конструктивной математики Эрретта Бишопа . Ниже приводится последовательность теорий, изложенных на том же языке , которые привели к хорошо изученной теории Питера Акзеля и не только. также характеризуется двумя особенностями, присутствующими также в теории Майхилла: с одной стороны, он использует предикативное разделение вместо полной неограниченной схемы разделения, см. также иерархию Леви . Ограниченность может рассматриваться как синтаксическое свойство или, альтернативно, теории могут быть консервативно расширены с помощью более высокого предиката ограниченности и его аксиом. Во-вторых, импредикативная аксиома Powerset отбрасывается, как правило, в пользу связанных, но более слабых аксиом. Сильная форма очень часто используется в классической общей топологии . Добавление к теории даже слабее, чем восстанавливает , как подробно описано ниже. Система, известная как интуиционистская теория множеств Цермело – Френкеля ( ), является сильной теорией множеств без . Он похож на , но менее консервативен или предсказуем . Обозначенная теория является конструктивной версией классической теории множеств Крипке – Платека, в которой даже Аксиома Коллекции ограничена. ${\ displaystyle {\ mathsf {CST}}}$${\ displaystyle {\ mathsf {CST}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZF}}}$ ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {IKP}}}$${\ displaystyle {\ mathsf {KP}}}$

Подтеории ZF

Обозначение

Ниже греческий означает переменную предиката в схемах аксиом и использование или для определенных предикатов. Уникальное существование напр. Средства . Квантификаторы превышают набор, и они обозначаются строчными буквами. ${\ displaystyle \ phi}$${\ displaystyle P}$${\ displaystyle Q}$${\ Displaystyle \ существует! xP (x)}$${\ Displaystyle \ существует x. \ forall y. \ left (y = x \ iff P (y) \ right)}$

Как это часто бывает при изучении теорий множеств, для классов используются нотации построителя множеств , которые в большинстве случаев не являются частью объектного языка, но используются для краткого обсуждения. В частности, можно ввести объявления нотации соответствующего класса через " " с целью выражения as . Логически эквивалентные предикаты могут использоваться для введения одного и того же класса. Также пишется как сокращение для . ${\ Displaystyle А = \ {г \ середина п (г) \}}$${\ Displaystyle P (а)}$${\ displaystyle a \ in A}$${\ Displaystyle \ {Z \ in B \ mid P (z) \}}$${\ Displaystyle \ {г \ середина г \ в В \ земля Р (г) \}}$

Как обычно, можно сократить путем и выражают претензии подкласса , то есть , путем . ${\ displaystyle \ forall z. (z \ in A \ подразумевает P (z))}$${\ Displaystyle \ forall (г \ в А) .P (г)}$${\ Displaystyle \ forall (г \ в А). г \ в В}$${\ displaystyle \ forall z. (z \ in A \ подразумевает z \ in B)}$${\ Displaystyle A \ подмножество B}$

Для собственности , банально . И так далее . ${\ displaystyle P}$${\ displaystyle \ forall z. {\ big (} (z \ in B \ land P (z)) \ подразумевает, что z \ in B {\ big)}}$${\ displaystyle \ {z \ in B \ mid P (z) \} \ подмножество B}$

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

Отправная точка аксиом, которые практически всегда считаются бесспорными и являются частью всех теорий, рассматриваемых в этой статье. ${\ displaystyle {\ mathsf {ZF}}}$

Обозначим утверждением, что два класса имеют точно такие же элементы, т. Е. Или эквивалентно . ${\ Displaystyle A \ simeq B}$${\ Displaystyle \ forall Z. (г \ в А \ тогда и только тогда, когда г \ в В)}$${\ Displaystyle (А \ подмножество В) \ земля (В \ подмножество А)}$

Следующая аксиома дает способ доказать равенство " " двух множеств , так что посредством подстановки любой предикат about переводится в одно из . ${\ displaystyle =}$${\ displaystyle x}$${\ displaystyle y}$

Расширяемость ${\ displaystyle \ forall x. \ forall y. \ \ x \ simeq y \ подразумевает x = y}$

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

В конструктивной интерпретации, элементы подкласса из могут оснащены больше информации , чем те , в том смысле , что , будучи в состоянии судить , в состоянии судить . И (если вся дизъюнкция не следует из аксиом) в интерпретации Брауэра – Гейтинга – Колмогорова это означает доказывать или отвергать ее. Поскольку это может быть не разрешимо для всех элементов в , эти два класса необходимо различать априори. ${\ Displaystyle A = \ {Z \ in B \ mid Q (z) \ lor \ neg Q (z) \}}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle b \ in A}$${\ Displaystyle Q (b) \ lor \ neg Q (b)}$${\ displaystyle Q (b)}$${\ displaystyle Q}$ ${\ displaystyle B}$

Рассмотрим свойство, которое доказуемо выполняется для всех элементов набора , так что , и предположим, что класс в левой части установлен как набор. Обратите внимание, что даже если этот набор слева неофициально также связан с релевантной для доказательства информацией о действительности для всех элементов, аксиома расширенности постулирует, что в нашей теории множеств набор слева оценивается равным значению один с правой стороны. ${\ displaystyle P}$${\ displaystyle y}$${\ Displaystyle \ {г \ ин у \ середина п (г) \} \ simeq у}$${\ displaystyle P}$

Вместо этого современные теории типов могут быть нацелены на определение требуемой эквивалентности " " в терминах функций, см., Например, эквивалентность типов . Соответствующая концепция функции объемности часто не принимается в теории типа. ${\ displaystyle \ simeq}$

Другие структуры конструктивной математики могут вместо этого потребовать определенного правила равенства или обособленности элементов каждого обсуждаемого набора . Даже в этом случае приведенное выше определение можно использовать для характеристики равенства подмножеств и . ${\ Displaystyle г \ в х}$${\ displaystyle x}$ ${\ Displaystyle и \ подмножество х}$${\ Displaystyle v \ подмножество х}$

Две другие основные аксиомы следующие. В первую очередь,

Сопряжение ${\ displaystyle \ forall x. \ forall y. \ \ \ exists p. \ forall z. {\ big (} (z = x \ lor z = y) \ подразумевает z \ in p {\ big)}}$

говоря, что для любых двух наборов и существует хотя бы один набор , который имеет хотя бы эти два набора ( ). ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle p}$${\ displaystyle z}$

А потом,

Союз ${\ Displaystyle \ forall x. \ \ \ exists u. \ forall y. {\ big (} (\ exists zy \ in z \ land z \ in x) \ подразумевает y \ in u {\ big)}}$

Говоря, что в любом наборе есть по крайней мере один набор , который содержит все члены , of members . ${\ displaystyle x}$${\ displaystyle u}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle z}$

Две аксиомы также могут быть сформулированы сильнее в терминах « », например, в контексте с Разделением, в этом нет необходимости. ${\ Displaystyle \ iff}$${\ displaystyle {\ mathsf {BCST}}}$

Вместе эти две аксиомы подразумевают существование бинарного объединения двух классов и когда они были установлены как множества, и это обозначается или . Определите обозначение класса для конечных элементов с помощью дизъюнкций, например, говорит , и определите последующий набор как . Это своего рода смесь спаривания и союза, аксиома, более связанная с преемником, - это аксиома присоединения . Это актуально для стандартного моделирования отдельных ординалов Неймана . Эту аксиому также легко принять, но она не имеет отношения к более сильным аксиомам, приведенным ниже. Обозначим стандартную модель упорядоченной пары . ${\ displaystyle a}$${\ displaystyle b}$${\ Displaystyle \ bigcup \ {а, б \}}$${\ displaystyle a \ cup b}$${\ displaystyle c \ in \ {a, b \}}$${\ Displaystyle (с = а) \ лор (с = Ь)}$ ${\ displaystyle Sx}$${\ Displaystyle х \ чашка \ {х \}}$${\ Displaystyle \ langle х, у \ rangle}$${\ Displaystyle \ {\ {х \}, \ {х, у \} \}}$

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

${\ displaystyle \ существует x. \ forall y. \, \ neg (y \ in x)}$

BCST

Далее используются схемы аксиом, то есть аксиомы для некоторого набора предикатов. Обратите внимание, что некоторые из установленных схем аксиом также часто представлены с заданными параметрами , то есть варианты с дополнительными универсальными замыканиями , так что символы могут зависеть от параметров. ${\ displaystyle v}$${\ displaystyle \ forall v}$${\ displaystyle \ phi}$

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

Схема аксиом предикативного разделения : для любого ограниченного предиката с not free в нем ${\ displaystyle \ phi}$${\ displaystyle y}$ ${\ Displaystyle \ forall y. \ \ \ существует s. \ forall x. {\ Big (} x \ in s \ iff {\ big (} x \ in y \ land \ phi (x) {\ big)} { \Большой )}}$

Аксиома сводится к постулированию существования множества, полученного пересечением любого множества и любого предикативно описанного класса . Когда предикат берется как для доказано, что множество, получается двоичное пересечение множеств и записи . ${\ displaystyle s}$${\ displaystyle y}$${\ Displaystyle \ {х \ середина \ фи (х) \}}$${\ displaystyle x \ in z}$${\ displaystyle z}$${\ displaystyle s = y \ cap z}$

Схема также называется ограниченным разделением, как в разделе Разделение только для ограниченных набором кванторов . Это схема аксиом, которая ссылается на синтаксические аспекты предикатов. Ограниченные формулы, также обозначаются в множестве теоретической иерархии Леви, по аналогии в арифметической иерархии . (Обратите внимание, однако, что арифметическая классификация иногда выражается не синтаксически, а в терминах подклассов натуральных чисел. Кроме того, нижний уровень имеет несколько общих определений, некоторые из которых не позволяют использовать некоторые общие функции. Различие не имеет отношения к уровню или Ограничение в этой аксиоме - это также импредикативные определения, связанные с контролем : в лучшем случае не следует заявлять о существовании объектов, которые не подлежат явному описанию, или чье определение включает в себя самих себя или ссылку на соответствующий класс, например, когда проверяемое свойство включает универсальный квантор. Таким образом, в конструктивной теории без аксиомы набора мощности не следует ожидать класс, определяемый как ${\ displaystyle \ Delta _ {0}}$${\ displaystyle \ Delta _ {0} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle s}$

${\ Displaystyle \ {х \ in y \ mid \ forall (t \ in {\ mathcal {P}} y) .Q (x, t) \}}$

т.е.

${\ displaystyle \ {x \ in y \ mid \ forall t. {\ big (} \ forall (z \ in t). (z \ in y) \ подразумевает Q (x, t) {\ big)} \} }$

быть множеством, где обозначает некоторый 2-арный предикат. Обратите внимание, что если этот подкласс является доказуемым набором, то термин, определенный таким образом, также находится в неограниченной области действия переменной term и выполняет заключенный в скобки предикат in , используемый для определения самого себя. Хотя предикативное разделение приводит к меньшему количеству заданных определений классов, являющихся наборами, следует подчеркнуть, что многие определения классов, которые являются классически эквивалентными, не являются таковыми, если ограничиваться конструктивной логикой. Таким образом, можно конструктивно получить более широкую теорию. Из-за потенциальной неразрешимости общих предикатов понятие подкласса более разработано в конструктивных теориях множеств, чем в классических. ${\ displaystyle Q}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle t}$

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

В силу чисто логической теоремы , строительство Рассела показывает , что предикативный Разделение в одиночку подразумевает , что . В частности, универсального набора не существует. ${\ displaystyle \ forall x. {\ big (} xRs \ Leftrightarrow (xRy \ land \ neg xRx) {\ big)} \ подразумевает \ neg sRy}$${\ displaystyle \ {x \ in y \ mid x \ notin x \} \ notin y}$

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

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

Схема преобразования : Для любого предиката , ${\ displaystyle \ phi}$ ${\ displaystyle \ forall d. \ \ \ forall (x \ in d). \ exists! y. \ phi (x, y) \ подразумевает, что \ существует r. \ forall y. {\ big (} y \ in r \ если и только если \ существует (x \ in d). \ phi (x, y) {\ big)}}$

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

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

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

В , замена главным образом важно , чтобы доказать существование множеств высокого ранга , а именно с помощью экземпляров схемы аксиом , где относится сравнительно небольшой набор для более крупных, . ${\ displaystyle {\ mathsf {ZF}}}$${\ Displaystyle \ фи (х, у)}$${\ displaystyle x}$${\ displaystyle y}$

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

Замещение можно рассматривать как форму понимания. Только предполагая, что замена уже подразумевает полное разделение. ${\ displaystyle {\ mathrm {LEM}}}$

ECST

Обозначим индуктивным свойством, например . С точки зрения предиката, лежащего в основе класса, это можно было бы перевести как . Здесь обозначает переменную общего набора. Пишите для . Определите класс . ${\ Displaystyle \ mathrm {Инд} (А)}$${\ displaystyle 0 \ in A \ land \ forall (п \ in A) .Sn \ in A}$${\ displaystyle P}$${\ Displaystyle P (0) \ land \ forall n. {\ big (} P (n) \ подразумевает P (Sn) {\ big)}}$${\ displaystyle n}$${\ displaystyle \ bigcap A}$${\ displaystyle \ {x \ mid \ forall y. (y \ in A \ подразумевает x \ in y) \}}$${\ displaystyle \ omega = \ bigcap \ {x \ mid \ mathrm {Ind} (x) \}}$

Для некоторого фиксированного предиката утверждение выражает, что это наименьший набор среди всех наборов, для которых верно. Элементарная конструктивная теория множеств имеет аксиому, а также ${\ displaystyle P}$${\ Displaystyle P (a) \ land \ forall xP (x) \ подразумевает \ подмножество x}$${\ displaystyle a}$${\ displaystyle x}$${\ Displaystyle P (x)}$${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle {\ mathsf {BCST}}}$

Сильная бесконечность ${\ Displaystyle \ существует w. {\ Big (} \ mathrm {Ind} (w) \, \ land \, {\ big (} \ forall x. \ mathrm {Ind} (x) \ подразумевает w \ subset x { \большой большой )}}$

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

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

${\ Displaystyle \ существует w. \ forall m. {\ Big (} m \ in w \ iff {\ big (} m = 0 \ lor (\ exists n \ in w). \ forall k. (k \ in m \ iff k \ in n \ lor k = n) {\ big)} {\ Big)}}$

который также можно записать более кратко, используя . Постулируемое таким образом существующее множество обычно обозначается наименьшим бесконечным ординалом фон Неймана . Для элементов этого множества утверждение разрешимо. ${\ displaystyle S}$${\ displaystyle \ omega}$${\ displaystyle n, m}$${\ Displaystyle п = м}$

Этим доказывается индукция для всех предикатов, заданных ограниченными формулами. Две из пяти аксиом Пеано относительно нуля и одна относительно замкнутости относительно, достаточно непосредственно следуют из аксиом бесконечности. Наконец, можно доказать, что это инъективная операция. ${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle S}$${\ displaystyle \ omega}$${\ displaystyle S}$

Натуральные числа различимы, что означает, что их равенство (и, следовательно, неравенство) разрешимо. Базовый порядок фиксируется членством в этой модели. Для стандартных обозначений, пусть обозначает начальный сегмент натуральных чисел для любых , включая пустое множество. ${\ Displaystyle \ {0,1, \ точки, п-1 \}}$${\ Displaystyle \ {к \ ин \ омега \ середина к <п \}}$${\ displaystyle k \ in \ omega}$

Функции

Естественно, логический смысл утверждений о существовании представляет интерес для интуиционистской логики. Здесь основное внимание уделяется отношениям в целом .

Исчисление доказательств в конструктивной математической структуре таких утверждений, как

${\ Displaystyle \ forall (а \ в А). \ существует (с \ в С). Р (а, с)}$

могут быть созданы с точки зрения программ на представленных доменах и, возможно, должны быть свидетелями иска. Это следует понимать в смысле, неформально говоря, где обозначает ценность программы, как упомянуто, но это касается вопросов теории реализуемости . Для более сильного контекста, если и когда утверждение верно, то требование, чтобы это всегда было возможно с реализуемой некоторой тотальной рекурсивной функцией, является возможным постулатом тезиса Чёрча, принятым, следовательно, в строго неклассическом русском конструктивизме . В предыдущем абзаце «функцию» нужно понимать в вычислимом смысле теории рекурсии - эта случайная двусмысленность также должна быть учтена ниже. ${\ Displaystyle \ forall (а \ в А) .P (а, с_ {а})}$${\ displaystyle c_ {a}}$${\ Displaystyle А = С = \ омега}$${\ Displaystyle а \ mapsto c_ {а}}$

В связи с этим рассмотрим арифметику Робинсона , которая является классической арифметической теорией, которая заменяет полную математическую схему индукции утверждением о существовании предшествующего числа. Теорема гласит, что эта теория представляет в точности рекурсивные функции в смысле определения предикатов , которые доказуемо являются полными функциональными отношениями, ${\ displaystyle P}$

${\ displaystyle \ forall (а \ in {\ mathbb {N}}). \ существует! (c \ in {\ mathbb {N}}). P (a, c)}$.

Теперь в текущем теоретико-множественном подходе мы определяем свойство, включающее скобки приложения функции , as и говорим о функции, когда доказуемо ${\ Displaystyle f (а) = с}$${\ displaystyle \ langle a, c \ rangle \ in f}$${\ displaystyle f \ subset A \ times C}$

${\ Displaystyle \ forall (а \ в А). \, \ существует! (с \ в С). f (а) = с}$,

т.е.

${\ Displaystyle \ forall (а \ в A). \, \ существует (с \ в C). \, \ forall (c '\ in C). {\ big (} c' = c \ iff \ langle a, c '\ rangle \ in f {\ big)}}$,

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

Примечательно, что общий класс мог бы выполнять вышеуказанный предикат, не являясь подклассом продукта , то есть свойство выражает не больше или не меньше функциональных возможностей по отношению к входным данным . Если домен и codomain являются наборами, то указанный выше предикат включает только ограниченные кванторы. Следует проявлять осторожность с номенклатурой «функция», которая используется в большинстве математических структур, еще и потому, что некоторые связывают сам термин функции с конкретным кодоменом. Также были определены варианты определения функционального предиката с использованием отношений обособленности на сетоидах . ${\ displaystyle A \ times C}$${\ displaystyle A}$

Пусть (также написано ) обозначает класс таких функций множества. Используя стандартную терминологию классов, можно свободно использовать функции, если их предметной областью является набор. Функции в целом будут заданы, если их кодомен равен. Когда функции понимаются как просто функциональные графики, как указано выше, предложение принадлежности также записывается . Ниже можно написать для того, чтобы отличить его от порядкового возведения в степень. ${\ displaystyle C ^ {A}}$${\ displaystyle {} ^ {A} C}$${\ displaystyle f \ in C ^ {A}}$${\ displaystyle f \ двоеточие от A \ до C}$${\ Displaystyle от х \ до у}$${\ Displaystyle у ^ {х}}$

Разделение позволяет использовать вырезанные подмножества продуктов , по крайней мере, когда они описаны ограниченным образом. Пишите для . Учитывая любой , теперь можно рассуждать о таких классах, как ${\ displaystyle A \ times C}$${\ displaystyle 1}$${\ displaystyle S0}$${\ Displaystyle B \ подмножество A}$

${\ Displaystyle \ {\ langle x, y \ rangle \ in A \ times \ {0,1 \} \ mid (x \ in B \ land y = 1) \ lor (\ neg (x \ in B) \ land y = 0) \}.}$

Булевозначные характеристические функции относятся к таким классам. Но имейте в виду, что это может быть неразрешимым . Другими словами, при отсутствии каких-либо неконструктивных аксиом дизъюнкция может быть недоказуемой, поскольку требуется явное доказательство любой дизъюнкции. Когда ${\ displaystyle \ chi _ {B} \ двоеточие A \ to \ {0,1 \}}$${\ displaystyle a \ in B}$${\ displaystyle a \ in B \ lor a \ notin B}$

${\ Displaystyle \ существует (y_ {a} \ in \ {0,1 \}). f (a) = y_ {a}}$

не может быть засвидетельствовано для всех , или уникальность термина не может быть доказана, тогда нельзя конструктивно судить осмысленную коллекцию как работоспособную. ${\ displaystyle a \ in A}$${\ displaystyle y_ {a}}$

Для и любого натурального , есть ${\ Displaystyle I = \ {п \ в \ омега \ середина Q (п) \}}$${\ displaystyle n \ in \ omega}$

${\ Displaystyle Q (n) \ lor \ neg Q (n) \ подразумевает n \ in I \ lor n \ notin I}$.

Итак, в классической теории множеств, где, согласно , предложения в определении разрешимы, также является подклассом членство. Если набор не является конечным, последовательное "перечисление" всех чисел путем простого пропуска числа с классически составляет возрастающую сюръективную последовательность . Там можно получить биективную функцию . Таким образом, классический класс функций доказуемо богат, поскольку он также содержит объекты, которые выходят за рамки того, что мы знаем как эффективно вычислимые или программно перечисляемые на практике. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle Q}$${\ displaystyle I}$${\ Displaystyle п \ notin I}$${\ displaystyle a: \ omega \ twoheadrightarrow I}$

В противоположность этому , для справки, в теории вычислимости , то вычисляемые множества являются диапазоны неубывающая общие функции (в рекурсивном смысле), на уровне в арифметической иерархии , а не выше. Выбор предиката на этом уровне сводится к решению задачи по поиску сертификата, который либо проверяет, либо отклоняет членство. Поскольку не каждый предикат вычислимо разрешим, теория сама по себе не будет утверждать (доказывать), что все бесконечные являются диапазоном некоторой биективной функции с областью определения . ${\ displaystyle \ Sigma _ {1} ^ {0} \ cap \ Pi _ {1} ^ {0} = \ Delta _ {1} ^ {0}}$${\ displaystyle Q}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle I \ subset \ omega}$${\ displaystyle \ omega}$

Конечность означает, что существует биективная функция натурального. Быть субконечным означает быть подмножеством конечного множества. Утверждение, что быть конечным множеством эквивалентно субконечному, эквивалентно . ${\ displaystyle {\ mathrm {LEM}}}$

Но, будучи совместимым с , развитие в этом разделе также всегда позволяет интерпретировать «функцию на » как объект, не обязательно заданный как закономерную последовательность. В общих моделях можно найти приложения для утверждений о вероятности, например, в утверждениях, включающих понятие «дано» бесконечной случайной последовательности подбрасываний монеты. ${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle \ omega}$

Выбор

• Аксиома счетного выбора : если , можно сформировать множество отношений «один ко многим» . Аксиома счетного выбора допускает, что всякий раз , когда можно сформировать функцию, отображающую каждое число в уникальное значение. Счетный выбор также может быть дополнительно ослаблен, например, путем ограничения возможных мощностей множеств в диапазоне или путем ограничения задействованного определения по их месту в синтаксических иерархиях.${\ displaystyle g \ двоеточие \ omega \ to z}$${\ displaystyle \ {\ langle n, u \ rangle \ mid n \ in \ omega \ land u \ in g (n) \}}$${\ Displaystyle \ forall (п \ в \ омега). \ существует иу \ в г (п)}$${\ displaystyle g}$

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

• Релятивизированный зависимый выбор: более сильный принцип релятивизированного зависимого выбора является его вариантом - схемой, включающей дополнительную переменную предиката. Принимая это только для ограниченных формул в , теория уже доказывает - индукцию , которая обсуждается ниже.${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$

• Аксиома выбора : аксиома выбора, касающаяся функций в общих областях. Подразумевает зависимый выбор.

Чтобы подчеркнуть силу полного выбора и его связь с вопросами Интенциональности , следует рассмотреть субконечные классы

${\ displaystyle x = \ {u \ in \ {0,1 \} \ mid u = 0 \ lor (u = 1 \ land P) \}}$

${\ displaystyle y = \ {u \ in \ {0,1 \} \ mid u = 1 \ lor (u = 0 \ land P) \}}$

Здесь и так же условны, как и предикаты, участвующие в их определении. Теперь предположим, что контекст, в котором они установлены как множества, тоже есть. Здесь Axiom of Choice затем разрешает существование карты с на различимые элементы. Теперь это фактически подразумевает это . Таким образом, утверждение о существовании общих функций выбора неконструктивно. Чтобы лучше понять этот феномен, нужно рассмотреть случаи логических выводов, такие как , и так далее. Разница между дискретной областью некоторых натуральных чисел и областью состоит в том, что о последних априори известно мало. Это тот случай, и , независимо от того , возможно создание претендента на функцию выбора. Но в случае , как следует из доказуемости , имеется так, что существует только одна возможная функция, входящая в функцию выбора выбора, теперь с справедливыми функциями выбора может быть или . Таким образом, при рассмотрении функционального назначения безоговорочное объявление не будет согласованным. Выбор может быть не принят в другой сильной теории множеств, потому что простое утверждение о существовании функции не реализует конкретную функцию. Понимание подкласса (используемое для их отделения и от , т. Е. Для их определения) связывает участвующие в нем предикаты, чтобы установить равенство описанным способом, и это относится к информации о функциях. ${\ displaystyle x}$${\ displaystyle y}$${\ Displaystyle \ {х, у \}}$${\ Displaystyle е \ двоеточие \ {х, у \} \ к \ {0,1 \}}$${\ Displaystyle е (г) \ в г}$ ${\ Displaystyle P \ lor \ neg P}$${\ displaystyle P \ подразумевает x = y}$${\ Displaystyle \ {х, у \}}$${\ displaystyle 0 \ in x}$${\ displaystyle 1 \ in y}$${\ displaystyle P}$${\ displaystyle \ {\ langle x, 0 \ rangle, \ langle y, 1 \ rangle \}}$${\ displaystyle x = y}$${\ displaystyle P}$${\ Displaystyle \ {х, у \} = \ {х \}}$${\ Displaystyle \ {х \} \ к \ {0,1 \}}$${\ Displaystyle \ {\ langle х, 0 \ rangle \}}$${\ Displaystyle \ {\ langle х, 1 \ rangle \}}$${\ displaystyle f (x) = 0}$${\ displaystyle f (y) = 1}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle \ {0,1 \}}$

Конструктивное развитие часто происходит независимо от обсуждаемых принципов выбора.

Арифметика

Предположения, необходимые для получения теории арифметики, тщательно изучаются в теории доказательств . Для контекста, здесь параграф о классификации в нем: Классические теории, начинающиеся с ограниченной арифметики, принимают различные схемы консервативной индукции и могут добавлять символы для определенных функций, что приводит к теориям между арифметикой Робинсона и Пеано . Однако большинство таких теорий относительно слабы в отношении доказательства тотальности для некоторых более быстрорастущих функций . Некоторые из самых основных примеров включают арифметику элементарных функций с порядковым номером теории доказательства (наименее доказуемо рекурсивным хорошим порядком ) из . имеет порядковый номер , то есть теория позволяет один закодировать ординал слабее (в этом смысле порядкового анализа) теории (скажем , в установленных сроках теории) как рекуррентное соотношение на только натуралы, . Схема -индукция, как, например, подразумевается релятивизированным зависимым выбором, означает индукцию для тех подклассов натуральных чисел, вычислимых посредством конечного поиска с неограниченным (конечным) временем выполнения. Схема также эквивалентна схеме -induction. Обозначается относительно слабая классическая арифметика первого порядка, которая принимает эту схему . -Induction также принял классическую второго порядка обратной математики базовой системы . Эта теория второго порядка является консервативной по сравнению с примитивной рекурсивной арифметикой , поэтому доказывает, что все примитивно рекурсивные функции являются общими. Все последние упомянутые арифметические теории имеют порядковые номера . Упомянутая арифметика высшего порядка является релевантной точкой отсчета в этом обсуждении, поскольку ее язык не просто выражает арифметические множества , в то время как все наборы натуральных чисел, существование которых доказывает теория, являются просто вычислимыми множествами . ${\ displaystyle {\ mathsf {PA}}}$ ${\ displaystyle {\ mathsf {EFA}}}$${\ displaystyle \ omega ^ {3}}$${\ displaystyle {\ mathsf {PA}}}$${\ displaystyle \ varepsilon _ {0}}$${\ displaystyle \ langle \ omega ^ {3}, \ in \ rangle}$${\ displaystyle \ langle \ omega, E \ rangle}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathsf {I \ Sigma}} _ {1}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle \ Pi _ {2} ^ {0}}$ ${\ displaystyle {\ mathsf {PRA}}}$${\ displaystyle \ omega ^ {\ omega}}$

При этом теория множеств фактически даже не интерпретирует полную примитивную рекурсию. В самом деле, несмотря на наличие аксиомы замены, теория не доказывает, что функция сложения является функцией множества. С другой стороны, многие утверждения могут быть доказаны для отдельного набора в этой теории (в отличие от выражений, включающих универсальный квантор, например, доступных с принципом индукции), и объекты, представляющие математический интерес, могут быть использованы на уровне класса на уровне класса. индивидуальная основа. Таким образом, перечисленных до сих пор аксиом достаточно в качестве основной рабочей теории для значительной части базовой математики. Выходя за рамки арифметики, необходимо добавить аксиому, дающую определение функций множеств через функции множеств итераций. Что необходимо, так это теоретический эквивалент объекта натуральных чисел . Затем это дает интерпретацию гейтинговых арифметики , . Таким образом, можно определить арифметику рациональных чисел и доказать ее свойства, такие как единственность и счетность. Теория множеств с этим также докажет, что для любых натуральных чисел и функциональные пространства ${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle {\ mathsf {HA}}}$${\ displaystyle {\ mathbb {Q}}}$${\ displaystyle n}$${\ displaystyle m}$

${\ Displaystyle {\ {0,1, \ точки, n-1 \}} \ to {\ {0,1, \ dots, m-1 \}}}$

есть наборы.

И наоборот, доказательство принципа искомой итерации может быть основано на наборе функций, которые можно было бы записать как, и существование этого подразумевается, если предположить, что отдельные функциональные пространства в конечных областях в наборах сами образуют множества. Это замечание должно мотивировать принятие аксиомы, имеющей более выраженный теоретический оттенок, вместо того, чтобы просто встраивать арифметические принципы в нашу теорию. Однако принцип итерации, полученный с помощью следующей, более теоретической аксиомы множеств, все еще не доказывает полную математическую схему индукции . ${\ Displaystyle \ чашка _ {п \ ин \ омега} у ^ {\ {0,1, \ точки, п-1 \}}}$${\ displaystyle y}$

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

Ослабленная форма схемы разделения уже была принята, и большее количество стандартных аксиом будет ослаблено для более предсказательной и конструктивной теории. Первой из них является аксиома Powerset , которая, по сути, принята для разрешимых подмножеств теории. ${\ displaystyle {\ mathsf {ZF}}}$

Характеристика класса всех подмножеств множества включает неограниченную универсальную квантификацию, а именно . Здесь было определено в терминах предиката членства выше. Заявление само по себе является . Таким образом, в рамках математической теории множеств класс мощности определяется не путем построения снизу вверх из его составляющих (как алгоритм в списке, который, например, отображает ), а через понимание всех множеств. ${\ Displaystyle {\ mathcal {P}} х}$${\ displaystyle x}$${\ displaystyle \ forall uu \ subset x \ iff u \ in {\ mathcal {P}} x}$${\ displaystyle \ subset}$${\ displaystyle \ in}$${\ Displaystyle у = {\ mathcal {P}} х}$${\ displaystyle \ Pi _ {1}}$${\ displaystyle \ langle a, b \ rangle \ mapsto \ langle \ langle \ rangle, \ langle a \ rangle, \ langle b \ rangle, \ langle a, b \ rangle \ rangle}$

Богатство степенного класса в теории без исключенного среднего лучше всего можно понять, рассматривая небольшие классически конечные множества. Для любой формулы класс равен 0, когда он может быть отклонен, и 1, когда может быть доказан, но также может быть вообще не разрешимым. С этой точки зрения, класс мощности одноэлементного элемента , то есть класс , или суггестивно " ", и обычно обозначаемый , называется алгеброй истинностного значения. В значных функций на множестве впрыснуть в и , таким образом , соответствуют его разрешимых подмножеств. ${\ displaystyle P}$${\ Displaystyle \ {х \ мид (х = 0) \ земля P \}}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ Displaystyle \ {0 \} = 1}$${\ Displaystyle {\ mathcal {P}} 1}$${\ Displaystyle \ {0, \ точки, 1 \}}$${\ displaystyle \ Omega}$${\ displaystyle \ {0,1 \}}$${\ displaystyle x}$${\ displaystyle \ Omega ^ {x}}$

Итак, теперь рассмотрим аксиому . ${\ displaystyle {\ mathrm {Exp}}}$

Возведение в степень ${\ Displaystyle \ forall x. \ forall y. \ \ \ exists hh = y ^ {x}}$

Формулировка здесь использует удобные обозначения для функциональных пространств. В противном случае аксиома более длинная, включая квантор, ограниченный, и предикат полной функции. На словах аксиома гласит, что для данных двух наборов класс всех функций, по сути, также является набором. Это, безусловно, требуется, например, для формализации карты объектов внутреннего гом-функтора типа . Использование аксиом возведения в степень проистекает из того факта, что функциональные пространства, являющиеся наборами, означают, что количественная оценка их функций является ограниченным понятием, позволяющим использовать разделение. Это имеет важные последствия: его принятие означает, что количественная оценка элементов определенных классов функций становится ограниченным понятием, даже когда функциональные пространства даже классически несчетны . Например, набор всех функций , то есть набор точек, лежащих в основе пространства Кантора , неисчислим, согласно диагональному аргументу Кантора , и в лучшем случае может считаться субсчетным . (В этом разделе мы начинаем использовать символ для полукольца натуральных чисел в таких выражениях, как or write, чтобы избежать смешения кардинального и порядкового возведения в степень.) ${\ Displaystyle х \ раз у}$${\ displaystyle x, y}$${\ Displaystyle у ^ {х}}$${\ Displaystyle {\ mathrm {hom}} ({\ mathbb {N}}, -)}$${\ displaystyle \ forall f}$${\ Displaystyle е \ двоеточие \ омега \ к \ {0,1 \}}$${\ Displaystyle \ {0,1 \} ^ {\ mathbb {N}}}$${\ Displaystyle у ^ {\ mathbb {N}}}$${\ displaystyle \ omega \ to y}$

Теория множеств с возведением в степень теперь также доказывает существование любой примитивной рекурсивной функции на натуральных числах в качестве функций множества в множестве . Соответственно, получить порядковое экспоненциальное число , которое можно охарактеризовать как . Говоря более широко, возведение в степень доказывает, что объединение всех конечных последовательностей над счетным множеством является счетным множеством. И действительно, объединение диапазонов любого счетного семейства счетных функций счетно. ${\ displaystyle \ omega}$${\ displaystyle \ omega \ to \ omega}$${\ displaystyle \ omega ^ {\ omega}}$${\ Displaystyle \ bigcup _ {п \ ин \ омега} \ омега ^ {п}}$

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

Возвращаясь к исходному рассмотрению класса мощности: предполагая, что все формулы разрешимы, т.е. предполагая , можно показать не только то, что становится набором, но более конкретно, что это набор из двух элементов. В предположении ограниченных формул Separation позволяет продемонстрировать, что любой powerclass является набором. В качестве альтернативы полный набор мощности эквивалентен простому предположению, что класс всех подмножеств образует набор. Полное разделение эквивалентно предположению, что каждый отдельный подкласс является набором. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle \ Omega}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle 1}$${\ displaystyle 1}$

Теоретические понятия категорий и типов

Таким образом, в этом контексте с возведением в степень функциональные пространства более доступны, чем классы подмножеств, как в случае с экспоненциальными объектами, соответственно. подобъекты в теории категорий. В категории теоретических терминах, теория по существу соответствует конструктивно хорошо заостренному декартово замкнутой гейтинговы предварительно топосы с (когда Бесконечность принимается) на природный объект номера . Существование powerset - вот что превратило бы претопы Гейтинга в элементарные топосы . Каждый такой топос, который интерпретирует, конечно, является моделью этих более слабых теорий, но локально были определены декартовы закрытые претопозы, которые, например, интерпретируют теории с возведением в степень, но отвергают полное разделение и набор степеней. ${\ displaystyle {\ mathsf {BCST}} + {\ mathrm {Exp}}}$ ${\ displaystyle {\ mathsf {ZF}}}$

В теории типов выражение " " существует само по себе и обозначает функциональные пространства , примитивное понятие. Эти типы (или, в теории множеств, классы или множества) естественным образом появляются, например, как тип сопоставления каррирования между и , присоединения . Типичная теория типов с общими возможностями программирования - и, конечно, те, которые могут моделировать , что считается конструктивной теорией множеств - будет иметь тип целых чисел и функциональных пространств, представляющих , и, как таковые, также включать типы, которые не являются счетными. Это просто подразумевает и означает, что среди функциональных терминов ни один не обладает свойством быть взаимно однозначным. ${\ Displaystyle от х \ до у}$${\ Displaystyle (г \ раз х) \ к у}$${\ Displaystyle г \ к у ^ {х}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathbb {Z}} \ to {\ mathbb {Z}}}$${\ displaystyle f \ двоеточие {\ mathbb {Z}} \ to ({\ mathbb {Z}} \ to {\ mathbb {Z}})}$

Теории конструктивных множеств также изучаются в контексте прикладных аксиом .

Анализ

В этом разделе уточняется сила . Для контекста упоминаются возможные дополнительные принципы, которые не обязательно являются классическими и также обычно не считаются конструктивными. Здесь уместно сделать общее предупреждение: читая утверждения об эквивалентности предложений в вычислимом контексте, нужно всегда знать, какие принципы выбора , индукции и понимания подразумеваются. См. Также связанные Конструктивный анализ и Вычислимый анализ . ${\ displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$

К реалам

Возведение в степень подразумевает принципы рекурсии, и поэтому можно рассуждать о последовательностях или об сокращении интервалов в, и это также позволяет говорить о последовательностях Коши и их арифметике. Любое действительное число Коши представляет собой набор последовательностей, то есть подмножество набора функций на . Требуется больше аксиом, чтобы всегда обеспечивать полноту классов эквивалентности таких последовательностей, и необходимо постулировать строгие принципы, подразумевающие существование модуля сходимости для всех последовательностей Коши. Слабый счетный выбор обычно является контекстом для доказательства уникальности вещественных чисел Коши как полного (псевдо) упорядоченного поля. «Псевдо» здесь подчеркивает, что порядок в любом случае не всегда будет конструктивно разрешимым. ${\ displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ displaystyle \ omega \ to {\ mathbb {Q}}}$${\ displaystyle \ omega \ to ({\ mathbb {Q}} \ times {\ mathbb {Q}})}$${\ displaystyle \ omega}$

Как и в классической теории, сечения Дедекинда характеризуются с помощью подмножеств алгебраических структур, таких как : свойства обитаемости, численно ограниченные сверху, «замкнутость вниз» и «открытость вверх» - все ограниченные формулы по отношению к данному множеству, лежащему в основе алгебраической состав. Стандартный пример разреза, первый компонент, действительно демонстрирующий эти свойства, представляет собой представление, заданное формулой ${\ displaystyle {\ mathbb {Q}}}$${\ displaystyle {\ sqrt {2}}}$

${\ displaystyle {\ big \ langle} \ {x \ in {\ mathbb {Q}} \ mid x <0 \ lor x ^ {2} <2 \}, \, \ {x \ in {\ mathbb {Q }} \ mid 0 <x \ land 2 <x ^ {2} \} {\ big \ rangle} \, \ \ in \, \ {{\ mathcal {P}} {\ mathbb {Q}}} \ раз {{\ mathcal {P}} {\ mathbb {Q}}}}$

(В зависимости от соглашения для разрезов, любая из двух частей или ни одна из них, как здесь, может использовать знак .) ${\ displaystyle \ leq}$

Теория, данная аксиомами, пока подтверждает, что псевдоупорядоченное поле , которое также является полным Архимеда и Дедекинда , если оно вообще существует, таким образом характеризуется однозначно, с точностью до изоморфизма. Однако существование только функциональных пространств, таких как не может быть набором, и поэтому ни один класс из всех подмножеств не выполняет названные свойства. Что требуется для того, чтобы класс действительных чисел Дедекинда был множеством, так это аксиома о существовании множества подмножеств. ${\ Displaystyle \ {0,1 \} ^ {\ mathbb {Q}}}$${\ Displaystyle {{\ mathcal {P}} {\ mathbb {Q}}}}$${\ displaystyle {\ mathbb {Q}}}$

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

Конструктивные школы

Неконструктивные утверждения, ценные при изучении конструктивного анализа , обычно формулируются как относящиеся ко всем двоичным последовательностям, то есть функциям . То есть количество заявлений оценивается в . ${\ Displaystyle е \ двоеточие \ омега \ к \ {0,1 \}}$${\ Displaystyle \ forall (е \ в \ {0,1 \} ^ {\ mathbb {N}})}$

Наиболее ярким примером является ограниченный принцип всеведения , постулирующий дизъюнктивное свойство, например, на уровне предложений или функций. ( Примеры функций могут быть построены в исходном виде , так что, если они непротиворечивы, конкурирующие дизъюнкты недоказуемы.) Принцип не зависит, например, от введенного ниже. В этой конструктивной теории множеств подразумевается ее «меньшая» версия, обозначаемая как ограниченный вариант закона Де Моргана . Более того, из этого следует принцип Маркова , форма доказательства от противного и -версия теоремы о веере . Упоминание о таких принципах , занимающих по -sentences как правило , намекают на эквивалентных формулировок в терминах последовательностей, решив обособленность из действительных чисел. В контексте конструктивного анализа со счетным выбором это, например, эквивалентно утверждению, что каждое действительное либо рационально, либо иррационально - опять же без требования свидетельствовать о дизъюнкции. ${\ displaystyle {\ mathrm {LPO}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathsf {PA}}}$${\ displaystyle {\ mathsf {PA}}}$${\ displaystyle {\ mathsf {PA}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathrm {LPO}}}$${\ Displaystyle {\ mathrm {LLPO}}}$ ${\ displaystyle {\ mathrm {MP}}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathrm {LPO}}}$

Таким образом, для некоторых утверждений, используемых в теориях конструктивного анализа, которые не могут быть доказаны с использованием простой интуиционистской логики, см. Или даже неклассический конструктивный тезис Черча или некоторые его следствия на стороне рекурсивной математики ( или ), а также схему Крипке. (превращение всех подклассов в счетные), индукция стержня , теорема о разрешимом веере или даже неклассический принцип непрерывности, определяющий функции на бесконечных последовательностях через конечные начальные отрезки на стороне Брауэра, интуиционистской ( ). Обе школы противоречат друг другу , так что принятие таких законов делает теорию несовместимой с теоремами классического анализа. ${\ displaystyle {\ mathrm {MP}}}$ ${\ Displaystyle {\ mathrm {CT}}}$${\ displaystyle {\ mathsf {RUSS}}}$${\ displaystyle {\ mathsf {CRM}}}$${\ displaystyle \ omega}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$ ${\ displaystyle {\ mathsf {INT}}}$${\ displaystyle {\ mathrm {LPO}}}$

Бесконечные деревья

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

${\ displaystyle T \, \ subset \, \ cup _ {n \ in \ omega} \ {0,1 \} ^ {\ {0,1, \ dots, n-1 \}}}$,

с разрешимым членством, и тогда эти деревья могут содержать элементы произвольного большого конечного размера. Лемма Слабого Кёнигса утверждает: для таких всегда существует бесконечный путь в , т. Е. Бесконечная последовательность, такая, что все ее начальные сегменты являются частью дерева. В обратной математике арифметика второго порядка не работает . Чтобы понять это, обратите внимание, что существуют вычислимые деревья, для которых не существует вычислимого такого пути через них. Чтобы доказать это, нужно перечислить частично вычислимые последовательности, а затем диагонализовать все полные вычислимые последовательности в одной частично вычислимой последовательности . Затем можно развернуть определенное дерево , точно совместимое с все еще возможными значениями везде, которое по построению несовместимо с каким-либо полным вычислимым путем. ${\ displaystyle {\ mathrm {WKL}}}$${\ displaystyle T}$${\ Displaystyle \ омега \ к \ {0,1 \}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle {\ mathrm {WKL}}}$${\ displaystyle K}$${\ displaystyle d}$${\ displaystyle K}$${\ displaystyle d}$

В , принцип подразумевает неконструктивный менее ограниченный принцип всеведения . В более консервативном контексте они эквивалентны при условии - (очень слабый счетный выбор). Это также эквивалентно теореме Брауэра о неподвижной точке и другим теоремам относительно значений непрерывных функций на вещественных числах. Теорема о неподвижной точке, в свою очередь, подразумевает теорему о промежуточном значении , но имейте в виду, что классические теоремы могут быть переведены в различные варианты, если они выражены в конструктивном контексте. ${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathrm {WKL}}}$ ${\ Displaystyle {\ mathrm {LLPO}}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathrm {AC}} _ ​​{\ omega, 2}}$

Это касается бесконечных графов, и поэтому его противоположность дает условие конечности. По классической арифметической теории это дает эквивалентность борелевской компактности относительно конечных подпокрытий вещественного единичного интервала. Тесно связанным утверждением о существовании конечных последовательностей в бесконечном контексте является теорема о разрешимом веере . На самом деле они эквивалентны. В тех различны, но опять же при условии какого - то выбора, подразумевает . ${\ displaystyle {\ mathrm {WKL}}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathrm {WKL}}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$

Ограничение функциональных пространств

В следующем замечании функции и утверждения о них снова подразумеваются в смысле теории вычислимости. Оператор μ включает все частично общерекурсивные функции (или программы в том смысле, что они вычислимы по Тьюрингу), включая такие, например, не примитивные, но -общие, такие как функция Аккермана . Определение оператора включает предикаты над натуральными числами, поэтому теоретический анализ функций и их совокупности зависит от имеющейся формальной основы. В любом случае те натуральные числа, которые в теории вычислимости рассматриваются как индексы для вычислимых функций, являющихся полными, находятся в арифметической иерархии . То есть это все еще подкласс натуралов. И здесь тотальность как предикат всех программ, как известно, вычислимо неразрешима . ${\ displaystyle {\ mathrm {PA}}}$${\ displaystyle \ Pi _ {2} ^ {0}}$

Неклассический конструктивный тезис Чёрча , согласно предположению в его предшественнике, касается определений предикатов (и, таким образом, здесь функций множества), которые явно являются полными, и постулирует, что они соответствуют вычислимым программам. Принятие постулата превращает множество в «разреженное» с точки зрения классической теории множеств. См. Субсчетность . ${\ Displaystyle {\ mathrm {CT}}}$${\ displaystyle \ omega \ to \ omega}$

Постулат по-прежнему является последовательной интуиционистской арифметикой или выбором. Но это противоречит классически действующим принципам, таким как и , которые являются одними из самых слабых, часто обсуждаемых принципов. ${\ Displaystyle {\ mathrm {CT}}}$${\ Displaystyle {\ mathrm {LLPO}}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$

Индукция

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

В предыдущих разделах ограниченное разделение уже установило справедливость индукции для ограниченных определений. В устоявшемся языке принципы индукции могут читаться с предшествующим определением, как описано выше. Поучительно отметить, что предложение в консеквенте , например , здесь выражено с использованием нотации классов, включающей подкласс, который может не составлять набор - это означает, что многие аксиомы не будут применяться, - и простая формулировка - это всего лишь два способа сформулировать одно и то же желаемое утверждение ( -индексированное соединение утверждений здесь, в частности.) Таким образом, теоретико-множественная структура с только ограниченным разделением может быть усилена с помощью схем арифметической индукции для неограниченных предикатов. ${\ displaystyle \ mathrm {Ind} (A) \ подразумевает \ omega \ subset A}$ ${\ Displaystyle \ mathrm {Инд} (А)}$${\ displaystyle \ omega \ subset \ {n \ in \ omega \ mid y ^ {\ {0,1, \ dots, n-1 \}} {\ text {это набор}} \}}$${\ displaystyle \ forall (п \ in \ omega) .y ^ {\ {0,1, \ dots, n-1 \}} {\ text {это набор}}}$${\ displaystyle n}$

Принцип итерации для функций множества, упомянутый ранее, в качестве альтернативы возведению в степень, также подразумевается полной схемой индукции над структурой, моделирующей натуральные числа (например ). Это также арифметический принцип первого порядка, который доказывает, что всего функций больше, чем есть. Часто это формулируется непосредственно в терминах предикатов следующим образом. Рассмотрим схему - : ${\ displaystyle \ omega}$${\ displaystyle {\ mathsf {PRA}}}$${\ displaystyle \ omega}$${\ displaystyle {\ mathrm {Ind}}}$

Схема аксиом полной математической индукции : для любого предиката on , ${\ displaystyle \ phi}$${\ displaystyle \ omega}$ ${\ displaystyle {\ Big (} \ phi (0) \ \ land \ \ forall (k \ in \ omega). {\ big (} \ phi (k) \ подразумевает \ phi (Sk) {\ big)} { \ Big)} \ подразумевает \ forall (n \ in \ omega). \ Phi (n)}$

Здесь 0 обозначает то же, что и выше, а набор обозначает последующий набор , с . Согласно Аксиоме Бесконечности, приведенной выше, он снова является членом . ${\ Displaystyle \ {\}}$${\ displaystyle Sn}$${\ displaystyle n \ in \ omega}$${\ displaystyle n \ in Sn}$${\ displaystyle \ omega}$

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

Чтобы доказать существование транзитивного замыкания для каждого набора относительно, требуется по крайней мере схема ограниченной итерации. Стоит отметить, что в программе предикативной арифметики полная схема математической индукции подвергалась критике как возможно не предикативная , когда натуральные числа определены как объект, который выполняет эту схему. ${\ displaystyle \ in}$

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

Индукция полного набора доказывает полную математическую индукцию по натуральным числам. Действительно, он дает индукцию по порядковым числам и порядковой арифметике. Замена не требуется, чтобы доказать индукцию по множеству натуральных чисел, но она предназначена для их арифметики, моделируемой в рамках теории множеств. ${\ displaystyle {\ mathsf {ECST}}}$

Более сильная аксиома - тогда гласит: ${\ displaystyle \ in}$${\ displaystyle {\ mathrm {Ind}}}$

Аксиома схема Set индукции : Для любого предиката , ${\ displaystyle \ phi}$ ${\ Displaystyle {\ Big (} \ forall s. \, {\ big (} \ forall (x \ in s). \ \ phi (x) {\ big)} \ подразумевает \ phi (s) {\ Big) } \ подразумевает \ forall y. \ phi (y)}$

Здесь выполняется тривиально и соответствует «нижнему случаю» в стандартной структуре. Вариант аксиомы только для ограниченных формул также изучается независимо и может быть выведен из других аксиом. ${\ displaystyle \ forall x \ in \ {\}. \ phi (x)}$

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

Аксиома Равномерности с ограниченной / неограниченной Separation предполагает Установить Induction , но и ограниченной / неограниченно , так Регулярность неконструктивно. И наоборот, вместе с Set Induction подразумевает Регулярность. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathrm {LEM}}}$

Metalogic

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

Теория не превосходит силы последовательности арифметики Гейтинга, но добавление на этом этапе привело бы к теории, превосходящей силу типичной теории типов : если предположить разделение в неограниченной форме, а затем добавить к, получится теория, доказывающая те же теоремы, что и минус регулярность! Таким образом, добавление Разделения и Регулярности к этой структуре дает полноту, а добавление к ней Выбор дает . ${\ displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {ZFC}}}$

Дополнительная теоретико-доказательная сила, достигаемая с помощью индукции в конструктивном контексте, является значительной, даже если отказ от регулярности в контексте не снижает теоретико-доказательной силы. Акзель был также одним из основных разработчиков необоснованной теории множеств , которая отвергает эту последнюю аксиому. ${\ displaystyle {\ mathsf {ZF}}}$

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

Со всеми ослабленными аксиомами, а теперь выходящими за рамки этих аксиом, также наблюдаемых в типизированном подходе Майхилла, рассмотрим теорию с возведением в степень, усиленную схемой коллекции . Это касается свойства отношений, порождающего несколько повторяющийся формат в его формулировке первого порядка. ${\ displaystyle {\ mathsf {ZF}}}$

Аксиома схема Strong Collection: Для любого предиката , ${\ displaystyle \ phi}$ ${\ Displaystyle \ forall a. \ \ {\ Big (} \ forall (x \ in a). \ exists y. \ phi (x, y) {\ Big)} \ подразумевает \ существует b. {\ Big (} \ forall (x \ in a). \ exists (y \ in b). \ phi (x, y) \ \ land \ \ forall (y \ in b). \ exists (x \ in a). \ phi ( х, у) {\ Big)}}$

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

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

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

Metalogic

Эта теория без безграничного разделения и «наивного» набора власти обладает множеством хороших свойств. Например, у него есть свойство существования : если для какого-либо свойства теория доказывает, что существует набор, обладающий этим свойством, то есть если теория доказывает утверждение , тогда также существует свойство, которое однозначно описывает такой экземпляр набора. То есть теория тогда и подтверждается . Это можно сравнить с арифметикой Гейтинга, где теоремы реализуются конкретными натуральными числами и обладают этими свойствами. В теории множеств роль играют определенные множества. Для контраста напомним, что из аксиомы выбора следует теорема о хорошем порядке , так что формально доказано существование полных порядков с наименьшим элементом для подмножеств подобных множеств , даже если доказуемо невозможно описать такой порядок. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle \ Phi}$${\ Displaystyle \ существует х. \ Phi (х)}$${\ displaystyle \ Psi}$${\ Displaystyle \ существует! х. \ пси (х) \ земля \ фи (х)}$${\ displaystyle {\ mathsf {ZFC}}}$${\ Displaystyle \ mathbb {R}}$

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

Можно подойти к множеству Power и дальше, не теряя теоретико-типовой интерпретации. Теория, известная как аксиомы выше, плюс более сильная форма возведения в степень. Это достигается путем принятия следующей альтернативы, которую снова можно рассматривать как конструктивную версию аксиомы множества Пауэр : ${\ displaystyle {\ mathsf {CZF}}}$

Аксиома схема подмножества Коллекция: Для любого предиката , ${\ displaystyle \ phi}$ ${\ Displaystyle \ forall a. \ forall b. \ \ \ exists u. \ forall z. {\ big (} \ forall (x \ in a). \ exists (y \ in b). \ phi (x, y) , z) {\ big)} \ подразумевает, что \ существует (v \ in u). {\ big (} \ forall (x \ in a). \ exists (y \ in v). \ phi (x, y, z ) \; \ земля \; \ forall (y \ in v). \ exists (x \ in a). \ phi (x, y, z) {\ big)}}$

Эта схема аксиомы Коллекции Подмножеств эквивалентна единственной и несколько более ясной альтернативной Аксиоме Полноты. Для этого пусть - класс всех полных отношений между a и b , этот класс задается как ${\ displaystyle a \ Sigma {b}}$

${\ displaystyle r \ in a \ Sigma {b} \ iff {\ big (} \ forall (x \ in a). \ exists (y \ in b). \ langle x, y \ rangle \ in r {\ big )} \, \ земля \, {\ big (} \ forall (p \ in r). \ exists (x \ in a). \ exists (y \ in b) .p = \ langle x, y \ rangle { \большой )}}$

При этом укажите альтернативу Subset Collection. Это гарантирует, что существует хотя бы какой-то набор, содержащий достаточное количество желаемых отношений. Более конкретно, между любыми двумя наборами и существует набор, который содержит общее подотношение для любого общего отношения от до . ${\ displaystyle {\ mathrm {Полнота}}}$${\ displaystyle c \ subset a \ Sigma {b}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle s}$${\ displaystyle r}$${\ displaystyle a}$${\ displaystyle b}$

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

${\ Displaystyle \ forall a. \ forall b. \ \ \ exists (c \ subset a \ Sigma {b}). \ forall (r \ in a \ Sigma {b}). \ exists (s \ in c). s \ подмножество r}$

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

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

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

Metalogic

В этой теории отсутствует свойство существования из-за схемы, но в 1977 году Акцель показал, что это все еще может быть интерпретировано в теории типов Мартина-Лёфа (с использованием подхода пропозиций как типов ), обеспечивая то, что сейчас рассматривается как стандартная модель в теории типов. . Это делается в терминах образов его функций, а также в виде довольно прямого конструктивного и предикативного обоснования, сохраняя при этом язык теории множеств. Эта субсчетная модель подтверждает многие принципы выбора . С теоретико-типовой моделью имеет скромную теоретическую силу доказательства, см . : Порядковый номер Бахмана – Ховарда . ${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZF}}}$ ${\ displaystyle {\ mathsf {IKP}}}$

NB: разрыв с ZF

Можно также добавить неклассическое утверждение, что все множества субсчетны, как аксиома. Тогда это набор (по бесконечности и возведению в степень), в то время как класс или даже не является набором по диагональному аргументу Кантора . Таким образом, эта теория логически отвергает Powerset и . ${\ displaystyle \ omega \ to \ omega}$${\ displaystyle {\ mathcal {P}} \ omega}$${\ Displaystyle {\ mathcal {P}} \ {0 \}}$${\ displaystyle {\ mathrm {LEM}}}$

В 1989 году Ингрид Линдстрем показал , что , не вполне обоснованные наборы , полученные путем замены эквивалент Axiom Фонда (Induction) в с анти-фундаментной аксиомой Aczél в ( ) также может быть интерпретировано в теории типа Мартин-LOF. ${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZFA}}}$

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

Теория - со стандартным набором разделения и питания . ${\ displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathsf {CZF}}}$

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

Аксиома схемы сбора : Для любого предиката , ${\ displaystyle \ phi}$ ${\ displaystyle \ forall z. {\ big (} \ forall (x \ in z). \ exists y. \ phi (x, y) {\ big)} \ подразумевает \ существует w. \ forall (x \ in z ). \ существует (y \ in w). \ phi (x, y)}$

В то время как аксиома замены требует, чтобы отношение было функциональным на множестве (например, для каждого in там ассоциируется ровно один ), Аксиома Коллекции этого не делает. Он просто требует, чтобы был ассоциирован по крайней мере один , и он утверждает существование набора, который собирает по крайней мере один такой для каждого такого . вместе с Сборником подразумевает Замену. ${\ displaystyle \ phi}$${\ displaystyle z}$${\ displaystyle x}$${\ displaystyle z}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle {\ mathrm {LEM}}}$

Таким образом, его можно рассматривать как наиболее простой вариант без него . ${\ displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathrm {LEM}}}$

Теория согласуется с будучи subcountable , а также с тезисом Черча для теории чисел функций. Но, как подразумевается выше, свойство субсчетности не может быть принято для всех множеств, учитывая, что теория оказывается множеством. ${\ displaystyle \ omega \ to \ omega}$${\ displaystyle {\ mathcal {P}} \ omega}$

Metalogic

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

Даже без , в доказательство теоретической прочности на равных , что из . ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathsf {ZF}}}$

Хотя он основан на интуиционистской, а не на классической логике, он считается непредикативным . Это позволяет формировать множества с использованием аксиомы разделения с любым предложением, включая те, которые содержат кванторы, которые не ограничены. Таким образом, новые наборы могут быть сформированы в терминах вселенной всех наборов. Кроме того, аксиома набора мощности подразумевает существование набора значений истинности . При наличии исключенного мидла этот набор существует и состоит из двух элементов. При его отсутствии набор значений истинности также считается непредикативным. ${\ displaystyle {\ mathsf {ZF}}}$

История

В 1973 году Джон Майхилл предложил систему теории множеств, основанную на интуиционистской логике, взяв наиболее общий фундамент и отбросив аксиому выбора и закон исключенного третьего , оставив все остальное как есть. Однако различные формы некоторых аксиом, которые эквивалентны в классическом контексте, не эквивалентны в конструктивном контексте, а некоторые формы подразумевают . В этих случаях для конструктивной теории множеств были приняты интуиционистски более слабые формулировки. ${\ displaystyle {\ mathsf {ZFC}}}$${\ displaystyle {\ mathsf {ZFC}}}$${\ displaystyle {\ mathrm {LEM}}}$

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

Снова на более слабой стороне, как и в случае с ее историческим аналогом теории множеств Цермело , можно обозначить интуиционистской теорией, построенной как, но без Замены, Коллекции или Индукции. ${\ displaystyle {\ mathsf {IZ}}}$${\ displaystyle {\ mathsf {IZF}}}$

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

Отметим еще одну очень слабую теорию, которая была исследована, а именно интуиционистскую (или конструктивную) теорию множеств Крипке – Платека . Теория имеет не только Разделение, но и Ограничение Коллекции, то есть она аналогична, но с Индукцией вместо полной Замены. Особенно слаба она при изучении без бесконечности. Теория не вписывается в иерархию, представленную выше, просто потому, что она с самого начала имеет схему аксиомы индукции множеств . Это позволяет использовать теоремы, включающие класс ординалов. ${\ displaystyle {\ mathsf {IKP}}}$${\ displaystyle {\ mathsf {BCST}}}$

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

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

В его представлении система Майхилла - это теория, использующая конструктивную логику первого порядка с идентичностью и тремя видами , а именно множествами, натуральными числами , функциями . Его аксиомы: ${\ displaystyle {\ mathsf {CST}}}$

• Обычная аксиома расширяемости для множеств, а также аксиома для функций и обычная аксиома объединения .
• Аксиома ограниченного или предикативного разделения , которая является ослабленной формой аксиомы разделения из классической теории множеств, требующей, чтобы любые количественные характеристики были ограничены другим множеством, как обсуждалось.
• Форма аксиомы бесконечности, утверждающая, что набор натуральных чисел (для которого он вводит константу ) на самом деле является набором.${\ displaystyle \ omega}$
• Аксиома возведения в степень, утверждающая, что для любых двух наборов существует третий набор, который содержит все (и только) функции, домен которых является первым набором, а диапазон - вторым набором. Это сильно ослабленная форма аксиомы власти, установленная в классической теории множеств, против которой Майхилл, среди прочих, возражал на основании ее непредсказуемости .

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

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

При сравнении с предыдущими разделами можно приблизительно определить силу этой теории с помощью конструктивных подтеорий . ${\ displaystyle {\ mathsf {ZF}}}$

И наконец теория принимает

• Аксиома зависимого выбора , который намного слабее обычной аксиома выбора .

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

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

В этом контексте было разработано много анализа и теории модулей .

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

Не во всех формальных логических теориях множеств необходимо напрямую аксиомизировать бинарный предикат членства " ". И элементарная теория категорий набора ( ), например, захват пар составных отображений между объектами, также может быть выражена с помощью конструктивной фоновой логики ( ). Теорию категорий можно представить как теорию стрел и объектов, хотя аксиоматизация первого порядка возможна только в терминах стрелок. ${\ displaystyle \ in}$${\ displaystyle {\ mathsf {ETCS}}}$${\ displaystyle {\ mathsf {CETCS}}}$

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

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

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

• Конструктивная математика
• Интуиционистская теория типов
• Порядковый анализ
• Непредсказуемость
• Собственность существования
• Закон исключенного среднего
• Субсчетность

использованная литература

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

• Троэльстра, Энн ; ван Дален, Дирк (1988). Конструктивизм в математике, Vol. 2 . Исследования по логике и основам математики. п. 619 . ISBN 978-0-444-70358-3.
• Aczel, P. и Rathjen, M. (2001). Заметки по конструктивной теории множеств . Технический отчет 40, 2000/2001. Институт Миттаг-Леффлера, Швеция.

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

• Лаура Кросилла, Теория множеств: конструктивный и интуиционистский ZF , Стэнфордская энциклопедия философии , 20 февраля 2009 г.
• Бенно ван ден Берг, Конструктивная теория множеств - обзор , слайды из Heyting dag, Амстердам, 7 сентября 2012 г.