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

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

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

Введение

Конструктивный взгляд

Предварительные сведения об использовании интуиционистской логики

Логика обсуждаемых здесь теорий множеств конструктивна в том смысле, что она отвергает принцип исключенного среднего. ${\mathrm {PEM} }$, т.е. что дизъюнкция $\phi \lor \neg \phi$ автоматически выполняется для всех предложений $\phi$. Это также часто называют законом исключенного третьего ( ${\mathrm {LEM} }$) в контекстах, где это предполагается. Конструктивно, как правило, для доказательства исключенного третьего в предложении. $P$, т.е. доказать частную дизъюнкцию $P\lor \neg P$, или $P$ или $\neg P$ необходимо явно доказать. Когда любое из таких доказательств установлено, говорят, что предложение разрешимо, и тогда это логически подразумевает, что дизъюнкция имеет место. Аналогично и чаще всего предикат $Q(x)$ для $x$ в домене $X$ называется разрешимым, если более сложное утверждение $\forall (x\in X).{\big (}Q(x)\lor \neg Q(x){\big )}$ доказуемо. Неконструктивные аксиомы могут позволить получить доказательства, формально претендующие на разрешимость таких аксиом. $P$ (и/или $Q$) в том смысле, что они оказываются исключенными средними для $P$ (соответственно утверждение с использованием приведенного выше квантора) без демонстрации истинности какой-либо стороны дизъюнкции. Это часто бывает в классической логике. Напротив, аксиоматические теории, считающиеся конструктивными, как правило, не допускают многих классических доказательств утверждений, включающих свойства, которые, как доказано, неразрешимы с помощью вычислений .

Закон непротиворечия представляет собой частный случай пропозициональной формы modus ponens . Использование первого с любым отрицательным утверждением $\neg P$, один действительный закон Де Моргана, таким образом, подразумевает $\neg \neg (P\lor \neg P)$ уже в более консервативной минимальной логике . На словах интуиционистская логика по-прежнему утверждает: невозможно одновременно исключить предложение и исключить его отрицание, и, таким образом, отказ от любого конкретизированного исключенного среднего утверждения для отдельного предложения непоследовательен. Здесь двойное отрицание означает, что утверждение о дизъюнкции теперь уже доказано никогда не может быть исключено или отвергнуто, даже в тех случаях, когда дизъюнкция не может быть доказуема (например, путем демонстрации одного из дизъюнктов, тем самым решая $P$) из принятых аксиом.

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

Интуиционистская логика, лежащая в основе обсуждаемых здесь теорий множеств, в отличие от минимальной логики, по-прежнему допускает устранение двойного отрицания для отдельных предложений. $P$ для которого исключено среднее. В свою очередь, формулировки теорем относительно конечных объектов, как правило, не отличаются от своих классических аналогов. Учитывая модель всех натуральных чисел, эквивалент предикатов, а именно принцип Маркова , не выполняется автоматически, но может рассматриваться как дополнительный принцип.

В обитаемой области и при помощи взрыва дизъюнкция $P\lor \exists (x\in X).\neg Q(x)$ подразумевает утверждение о существовании $\exists (x\in X).(Q(x)\to P)$, что, в свою очередь, подразумевает ${\big (}\forall (x\in X).Q(x){\big )}\to P$. Классически эти последствия всегда обратимы. Если одно из первых классически справедливо, возможно, стоит попытаться обосновать его во второй форме. Для особого случая, когда $P$ отвергается, мы имеем дело с утверждением о существовании контрпримера $\exists (x\in X).\neg Q(x)$, что обычно конструктивно сильнее, чем заявление об отказе $\neg \forall (x\in X).Q(x)$: Пример $t$ такой, что $Q(t)$ противоречиво, конечно, означает, что это не так $Q$ держится для всех возможных $x$. Но можно также продемонстрировать, что $Q$ держась за всех $x$ логически привело бы к противоречию без помощи конкретного контрпримера, да еще и при невозможности его построить. В последнем случае конструктивно здесь не оговаривается утверждение существования.

Наложенные ограничения на теорию множеств

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

Металогика

уже возникают вычислимо неразрешимые предложения Поскольку в арифметике Робинсона , даже простое предикативное разделение позволяет легко определить неуловимые подмножества. В отличие от классической концепции, конструктивные теории множеств могут быть замкнутыми согласно правилу, согласно которому любое свойство, разрешимое для всех множеств, уже эквивалентно одному из двух тривиальных: $\top$ или $\bot$. Также в этом смысле действительную линию можно считать неразложимой . Неразрешимость дизъюнкций также влияет на утверждения о полных порядках, таких как порядок всех порядковых числительных , что выражается в доказуемости и отклонении положений в порядке, определяющем дизъюнкцию. $(\alpha \in \beta )\lor (\alpha =\beta )\lor (\beta \in \alpha )$. Это определяет, является ли отношение трихотомическим . Ослабленная теория ординалов, в свою очередь, влияет на силу теории доказательства, определенную в ординальном анализе .

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

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

${\mathsf {T}}\vdash \exists x.\phi (x)\implies {\mathsf {T}}\vdash \exists !x.\phi (x)\land \psi (x)$

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

Некоторые теории с классическим пониманием существования на самом деле также могут быть ограничены, чтобы продемонстрировать свойство сильного существования. В теории множеств Цермело–Френкеля, где все множества считаются порядково определяемыми , теория обозначается ${\mathsf {ZF}}+({\mathrm {V} }={\mathrm {HOD} })$, множеств без такой определимости не существует. Это свойство также реализуется через постулат конструируемой вселенной в ${\mathsf {ZF}}+({\mathrm {V} }={\mathrm {L} })$.Для контраста рассмотрим теорию ${\mathsf {ZFC}}$ данный ${\mathsf {ZF}}$ плюс полный аксиомы выбора постулат существования : Напомним, что этот набор аксиом доказывает теорему о хорошем порядке , подразумевающую, что хороший порядок существует для любого множества. В частности, это означает, что отношения $W\subset {\mathbb {R} }\times {\mathbb {R} }$ формально существуют, которые устанавливают упорядоченность ${\mathbb {R} }$ (т.е. теория утверждает существование наименьшего элемента для всех подмножеств ${\mathbb {R} }$ в отношении этих отношений). И это несмотря на то, что определимость такого упорядочения, как известно зависит , не от ${\mathsf {ZFC}}$. Последнее означает, что ни для какой конкретной формулы $\psi$ Говоря языком теории, доказывает ли теория, что соответствующее множество является хорошо упорядоченным отношением действительных чисел. Так ${\mathsf {ZFC}}$ формально доказывает существование подмножества $W\subset {\mathbb {R} }\times {\mathbb {R} }$ обладающий свойством быть вполне упорядоченным отношением, но в то же время не имеющим определенного множества $W$ для которого свойство может быть проверено, возможно, может быть определено.

Антиклассические принципы

Как уже говорилось выше, конструктивная теория ${\mathsf {T}}$ может проявлять свойство числового существования, ${\mathsf {T}}\vdash \exists e.\psi (e)\implies {\mathsf {T}}\vdash \psi ({\underline {\mathrm {e} }})$, для некоторого числа ${\mathrm {e} }$ и где ${\underline {\mathrm {e} }}$ обозначает соответствующую цифру в формальной теории. Здесь необходимо тщательно различать доказуемые импликации между двумя утверждениями: ${\mathsf {T}}\vdash P\to Q$и свойства теории вида ${\mathsf {T}}\vdash P\implies {\mathsf {T}}\vdash Q$. Когда металогически установленная схема последнего типа принимается в качестве правила вывода исчисления доказательств и ничего нового доказать невозможно, говорят, что теория ${\mathsf {T}}$ закрыто по этому правилу.

Вместо этого можно рассмотреть присоединение к правилу, соответствующему метатеоретическому свойству, как импликацию (в смысле « $\to$") к ${\mathsf {T}}$в виде схемы аксиом или в количественной форме. Обычно изучается ситуация с фиксированным ${\mathsf {T}}$ демонстрирующее метатеоретическое свойство следующего типа: для примера из некоторого набора формул определенной формы, зафиксированного здесь с помощью $\phi$ и $\psi$, установлено существование ряда ${\mathrm {e} }$ так что ${\mathsf {T}}\vdash \phi \implies {\mathsf {T}}\vdash \psi ({\underline {\mathrm {e} }})$. Тогда можно постулировать $\phi \to \exists (e\in {\mathbb {N} }).\psi (e)$, где граница $e$ — числовая переменная на языке теории. Например, правило Чёрча является допустимым правилом в арифметике Гейтинга первого порядка. ${\mathsf {HA}}$ и, кроме того, соответствующий тезисный принцип Чёрча ${\mathrm {CT} }_{0}$ может быть последовательно принята как аксиома. Новая теория с добавленным принципом является антиклассической, поскольку она, возможно, больше не будет последовательной, если принять также ${\mathrm {PEM} }$. Аналогично, присоединение к принципу исключенного третьего ${\mathrm {PEM} }$ к некоторой теории ${\mathsf {T}}$, полученная таким образом теория может доказать новые, строго классические положения, а это может испортить некоторые метатеоретические свойства, ранее установленные для ${\mathsf {T}}$. Таким образом, ${\mathrm {CT} }_{0}$ не может быть принят в ${\mathsf {HA}}+{\mathrm {PEM} }$, также известная как арифметика Пеано ${\mathsf {PA}}$.

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

$\forall (f\in {\mathbb {N} }^{\mathbb {N} }).\exists (e\in {\mathbb {N} }).{\Big (}\forall (n\in {\mathbb {N} }).\exists (w\in {\mathbb {N} }).T(e,n,w)\land U(w,f(n)){\Big )}$

Предикат Клини T вместе с извлечением результата выражает, что любое входное число $n$ отображается в число $f(n)$ есть, через $w$, засвидетельствованное как вычислимое отображение. Здесь ${\mathbb {N} }$ теперь обозначает модель теории множеств стандартных натуральных чисел и $e$ — индекс относительно фиксированного перечисления программы. Были использованы более сильные варианты, которые распространяют этот принцип на функции. $f\in {\mathbb {N} }^{X}$ определено в доменах $X\subset {\mathbb {N} }$ низкой сложности. Принцип отвергает разрешимость предиката. $Q(e)$ определяется как $\exists (w\in {\mathbb {N} }).T(e,e,w)$, выражая это $e$ — индекс вычислимой функции, останавливающейся на собственном индексе. Можно также рассмотреть более слабые формы принципа с двойным отрицанием, которые не требуют существования рекурсивной реализации для каждого $f$, но которые по-прежнему делают несовместимыми принципы, утверждающие существование функций, которые, как доказано, не имеют рекурсивной реализации. Некоторые формы тезиса Чёрча как принципа даже согласуются с классической, слабой, так называемой второго порядка . арифметической теорией ${\mathsf {RCA}}_{0}$, подсистема двусортной теории первого порядка ${\mathsf {Z}}_{2}$.

Совокупность вычислимых функций классически подсчетна , что в классическом смысле то же самое, что быть счетной. Но классические теории множеств обычно утверждают, что ${\mathbb {N} }^{\mathbb {N} }$ содержит и другие функции, кроме вычислимых. Например, есть доказательство ${\mathsf {ZF}}$ что полные функции (в смысле теории множеств) действительно существуют, которые не могут быть уловлены машиной Тьюринга .Если серьезно отнестись к вычислимому миру как к онтологии, то ярким примером антиклассической концепции, связанной с марковской школой, является разрешенная подсчетность различных несчетных коллекций. При принятии счетности совокупности всех бесконечных последовательностей натуральных чисел ( ${\mathbb {N} }^{\mathbb {N} }$) как аксиома в конструктивной теории, «малость» (в классических терминах) этого набора в некоторых теоретических реализациях уже фиксируется самой теорией.Конструктивная теория может также не принимать ни классических, ни антиклассических аксиом и, таким образом, оставаться агностиком в отношении любой из возможностей.

Конструктивные принципы уже доказывают $\forall (x\in X).\neg \neg {\big (}Q(x)\lor \neg Q(x){\big )}$ для любого $Q$. И так для любого данного элемента $x$ из $X$, соответствующее исключенное среднее высказывание для предложения не может быть отвергнуто. Действительно, для любого данного $x$, по непротиворечивости нельзя исключить $Q(x)$ и исключить его отрицание одновременно, и соответствующее правило Де Моргана применяется, как указано выше. Но в некоторых случаях теория может также допускать заявление об отказе. $\neg \forall (x\in X).{\big (}Q(x)\lor \neg Q(x){\big )}$. Принятие этого не требует предоставления специального $t\in X$ свидетельствовать о неудаче исключенного третьего для конкретного предложения $Q(t)$, то есть свидетельствовать о противоречивом $\neg {\big (}Q(t)\lor \neg Q(t){\big )}$. Предикаты $Q(x)$ на бесконечном домене $X$ соответствуют решению проблем . Руководствуясь доказанно вычислимо неразрешимыми проблемами , можно отвергнуть возможность разрешимости предиката, не делая при этом никаких утверждений о существовании предиката. $X$.Другой пример: такая ситуация реализуется в интуиционистском анализе Брауэра в случае, когда квантор распространяется на бесконечное множество бесконечных двоичных последовательностей и $Q(x)$ утверждает, что последовательность $x$ везде равен нулю. Что касается этого свойства окончательной идентификации как вечно постоянной последовательности, принятие принципа непрерывности Брауэра строго исключает возможность доказать, что это разрешимое явление для всех последовательностей.

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

История и обзор

Исторически предметом конструктивной теории множеств (часто также « ${\mathsf {CST}}$») началось с работы Джона Майхилла над теориями, также называемыми ${\mathsf {IZF}}$ и ${\mathsf {CST}}$. В 1973 году он предложил первую теорию множеств первого порядка, основанную на интуиционистской логике и взяв наиболее общий фундамент. ${\mathsf {ZFC}}$ и отбросив Аксиому выбора, а также принцип исключенного третьего, изначально оставив все остальное как есть. Однако различные формы некоторых из ${\mathsf {ZFC}}$ аксиомы, которые эквивалентны в классической ситуации, неэквивалентны в конструктивной ситуации, а некоторые формы подразумевают ${\mathrm {PEM} }$, как будет показано. В этих случаях последовательно принимались интуиционистски более слабые формулировки. Гораздо более консервативная система ${\mathsf {CST}}$ также является теорией первого порядка, но нескольких видов и с ограниченной количественной оценкой, стремящейся обеспечить формальную основу для Эрретта Бишопа программы конструктивной математики .

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

Модели

Многие теории, изучаемые в конструктивной теории множеств, являются простыми ограничениями теории множеств Цермело – Френкеля ( ${\mathsf {ZF}}$) относительно их аксиомы, а также лежащей в их основе логики. Такие теории затем можно интерпретировать в любой модели ${\mathsf {ZF}}$.

Арифметика Пеано ${\mathsf {PA}}$ биинтерпретируема данной с теорией, ${\mathsf {ZF}}$ минус бесконечность и отсутствие бесконечных множеств, плюс существование всех транзитивных замыканий . (Последнее также подразумевается после продвижения схемы «Регулярность для установки индукции» , которая обсуждается ниже.) Аналогично, конструктивная арифметика также может быть принята как апология большинства аксиом, принятых в ${\mathsf {CZF}}$: Приветствующая арифметика ${\mathsf {HA}}$ биинтерпретируема со слабой конструктивной теорией множеств, как также описано в статье о ${\mathsf {HA}}$. Можно арифметически охарактеризовать отношение принадлежности». $\in$" и с его помощью докажите - вместо существования множества натуральных чисел $\omega$ - что все множества в его теории находятся в биекции с (конечным) естественным фон Нейманом , принцип, обозначаемый ${\mathrm {V} }={\mathrm {Fin} }$. Этот контекст дополнительно проверяет экстенсиональность, спаривание, объединение, двоичное пересечение (которое связано со схемой аксиомы предикативного разделения ) и схемой индукции множеств. Взятые в качестве аксиом, вышеупомянутые принципы составляют теорию множеств, которая уже идентична теории, данной ${\mathsf {CZF}}$ минус существование $\omega$ цель больше ${\mathrm {V} }={\mathrm {Fin} }$ как аксиома. Все эти аксиомы подробно обсуждаются ниже.Соответственно, ${\mathsf {CZF}}$ также доказывает, что наследственно конечные множества удовлетворяют всем предыдущим аксиомам. Это результат, который сохраняется при переходе к ${\mathsf {PA}}$ и ${\mathsf {ZF}}$ минус бесконечность.

Что касается конструктивных реализаций, то существует соответствующая теория реализуемости . Соответственно, теория Акцеля конструктивна Цермело-Френкелю. ${\mathsf {CZF}}$ интерпретировался в теориях типа Мартина-Лёфа , как это показано в разделе, посвященном ${\mathsf {CZF}}$. Таким образом, теоремы, доказуемые в этой и более слабых теориях множеств, являются кандидатами на компьютерную реализацию.

предпучковые Также были представлены модели для конструктивных теорий множеств. Они аналогичны моделям предпучков интуиционистской теории множеств, разработанной Даной Скотт в 1980-х годах. Модели реализуемости ${\mathsf {CZF}}$ внутри эффективных топосов были идентифицированы, которые, скажем, сразу обосновывают полное разделение, релятивизированный зависимый выбор. ${\mathrm {RDC} }$, независимость помещения ${\mathrm {IP} }$ для множеств, но и счетность всех множеств, принцип Маркова ${\mathrm {MP} }$ и диссертация Чёрча ${\mathrm {CT} _{0}}$ в формулировке для всех предикатов.

Обозначения

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

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

Язык

Пропозициональные связочные символы, используемые для образования синтаксических формул, стандартны. Аксиомы теории множеств дают средство доказать равенство ». $=$«множеств, и этот символ может, злоупотребляя обозначениями , использоваться для классов. Множество, в котором предикат равенства разрешим, также называется дискретным . Отрицание» $\neg$«равенство иногда называют отрицанием равенства и обычно пишут « $\neq$Однако в контексте отношений обособленности , например, при работе с последовательностями, последний символ также иногда используется для чего-то другого.

Общая трактовка, также принятая здесь, формально лишь расширяет лежащую в основе логику одним примитивным бинарным предикатом теории множеств». $\in$«.Как и равенство, отрицание стихийности» $\in$"часто пишут" $\notin$".

Переменные

Ниже греческого $\phi$ обозначает переменную предложения или предиката в схемах аксиом и $P$ или $Q$ используется для конкретных таких предикатов. Слово «предикат» иногда используется как синоним слова «формулы», даже в унарном случае .

Кванторы всегда варьируются только по множествам, и они обозначаются строчными буквами.Как обычно, для выражения предикатов можно использовать скобки аргументов, чтобы выделить определенные свободные переменные в их синтаксическом выражении, как в « $Q(z)$". Уникальное существование $\exists !x.Q(x)$ здесь означает $\exists x.\forall y.{\big (}y=x\leftrightarrow Q(y){\big )}$.

Классы

используется нотация компоновщика множеств Как обычно, для классов , которая в большинстве контекстов не является частью объектного языка, а используется для краткого обсуждения. В частности, можно ввести объявления обозначений соответствующего класса через " $A=\{z\mid Q(z)\}$", с целью выражения какого-либо $Q(a)$ как $a\in A$. Для представления одного и того же класса можно использовать логически эквивалентные предикаты.Еще один пишет $\{z\in B\mid Q(z)\}$ как сокращение для $\{z\mid z\in B\land Q(z)\}$. Например, можно рассмотреть $\{z\in B\mid z\notin C\}$ и это также обозначается $B\setminus C$.

Один сокращает $\forall z.{\big (}z\in A\to Q(z){\big )}$ к $\forall (z\in A).Q(z)$ и $\exists z.{\big (}z\in A\land Q(z){\big )}$ к $\exists (z\in A).Q(z)$. Синтаксическое понятие ограниченной количественной оценки в этом смысле может играть роль в формулировке схем аксиом, как видно из обсуждения аксиом ниже. Выразить подкласса утверждение $\forall (z\in A).z\in B$, то есть $\forall z.(z\in A\to z\in B)$, к $A\subset B$.Для предиката $Q$, тривиально $\forall z.{\big (}(z\in B\land Q(z))\to z\in B{\big )}$. И отсюда следует, что $\{z\in B\mid Q(z)\}\subset B$.Понятие кванторов, ограниченных подмножеством, как в $\forall (z\subset A).z\in B$, также использовался в теоретических исследованиях множеств, но здесь не будет далее освещаться.

Если доказано, что существует набор, то есть внутри класса $\exists z.(z\in A)$, то его называют обитаемым . Можно также использовать количественную оценку в $A$ выразить это как $\exists (z\in A).(z=z)$. Класс $A$ тогда доказано, что это не пустое множество, представленное ниже. Хотя это классически эквивалентно, конструктивно непустое понятие является более слабым и имеет два отрицания, и его следует называть необитаемым . К сожалению, слово, обозначающее более полезное понятие «обитаемый», редко используется в классической математике.

Два способа выразить, что классы не пересекаются , действительно отражают многие интуиционистски допустимые правила отрицания: ${\big (}\forall (x\in A).x\notin B{\big )}\leftrightarrow \neg \exists (x\in A).x\in B$. Используя приведенные выше обозначения, это чисто логическая эквивалентность, и в этой статье предложение, кроме того, будет выражаться как $A\cap B=\{\}$.

Подкласс $A\subset B$ называется отделяемым от $B$ если релятивизированный предикат принадлежности разрешим, т. е. если $\forall (x\in B).x\in A\lor x\notin A$ держит. Его еще называют разрешимым, если суперкласс ясен из контекста — часто это набор натуральных чисел.

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

Обозначим через $A\simeq B$ утверждение, выражающее, что два класса имеют одни и те же элементы, т.е. $\forall z.(z\in A\leftrightarrow z\in B)$или эквивалентно $(A\subset B)\land (B\subset A)$. Это не следует путать с понятием равночисленности, которое также используется ниже.

С $A$ стоящий за $\{z\mid Q(z)\}$, удобное обозначение между $x\in A$ и $Q(x)$, аксиомы вида $\exists a.\forall z.{\big (}z\in a\leftrightarrow Q(z){\big )}$ постулировать, что класс всех множеств, для которых $Q$ Hold фактически образует набор . Менее формально это можно выразить как $\exists a.a\simeq A$. Аналогично, предложение $\forall a.(a\simeq A)\to P(a)$ передает " $P(A)$ когда $A$ входит в число множеств теории». Для случая, когда $P$ является тривиально ложным предикатом, то предложение эквивалентно отрицанию предыдущего утверждения о существовании, выражающему несуществование $A$ как набор.

Дальнейшие расширения обозначений понимания классов, приведенные выше, обычно используются в теории множеств, придавая смысл таким утверждениям, как « $\{f(z)\mid Q(z)\}\simeq \{\langle x,y,z\rangle \mid T(x,y,z)\}$", и так далее.

Синтаксически более общий набор $w$ также можно охарактеризовать с помощью другого 2-арного предиката $R$ впадина $\forall x.x\in w\leftrightarrow R(x,w)$, где правая часть может зависеть от фактической переменной $w$и, возможно, даже о членстве в $w$ сам.

Подтеории ZF

Здесь представлен ряд знакомых аксиом или их небольшие переформулировки. Подчеркивается, что отсутствие ${\mathrm {PEM} }$ в логике затрагивается то, что доказуемо, и выделяется, какие неклассические аксиомы, в свою очередь, непротиворечивы.

Равенство

Используя введенные выше обозначения, следующая аксиома дает возможность доказать равенство: $=$" из двух множеств , так что посредством замены любой предикат о $x$ переводится как один из $y$.В силу логических свойств равенства обратное направление постулируемой импликации выполняется автоматически.

Экстенсиональность $\forall x.\forall y.\ \ x\simeq y\to x=y$

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

Рассмотрим предикат $Q$ что доказано справедливо для всех элементов множества $y$, так что $y\simeq \{z\in y\mid Q(z)\}$и предположим, что класс в правой части установлен как множество. Обратите внимание, что даже если этот набор справа неформально также связан с релевантной для доказательства информацией о достоверности $Q$ аксиома экстенсиональности постулирует, что для всех элементов в нашей теории множеств множество в правой части считается равным множеству в левой части.Приведенный выше анализ также показывает, что утверждение вида $\forall (x\in w).Q(x)$, что в неформальной нотации класса может быть выражено как $w\subset \{x\mid Q(x)\}$, тогда эквивалентно выражается как $\{x\in w\mid Q(x)\}=w$. Это означает, что установление такого $\forall$-теоремы (например, доказуемые с помощью полной математической индукции) позволяют заменить подкласс $w$ в левой части равенства для всего $w$, в любой формуле.

Обратите внимание, что принятие " $=$«как символ в теории логики предикатов делает равенство двух членов выражением, свободным от кванторов.

Альтернативные подходы

Хотя эта аксиома часто принимается, она подвергается критике в конструктивной мысли, поскольку она эффективно разрушает по-разному определенные свойства или, по крайней мере, множества, рассматриваемые как расширение этих свойств, понятие Фрега .

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

Вместо этого другие концепции конструктивной математики могут требовать особого правила равенства или обособленности элементов. $z\in x$ из каждого набора $x$ обсуждалось. Но и в подходе к множествам, подчеркивающим обособленность, можно использовать приведенное выше определение в терминах подмножеств для характеристики понятия равенства». $\simeq$" из этих подмножеств.Соответственно, расплывчатое представление о дополнении двух подмножеств $u\subset x$ и $v\subset x$ дается, когда любые два члена $s\in u$ и $t\in v$ доказуемо отделены друг от друга. Коллекция дополняющих пар. $\langle u,v\rangle$ хорошо себя ведет алгебраически .

Объединение наборов

Определите обозначение класса для соединения нескольких заданных элементов посредством дизъюнкций. Например $z\in \{a,b\}$ это утверждение без кванторов $(z=a)\lor (z=b)$, и аналогично $z\in \{a,b,c\}$ говорит $(z=a)\lor (z=b)\lor (z=c)$, и так далее.

Два других основных постулата существования при наличии других наборов заключаются в следующем. Во-первых,

Сопряжение $\forall x.\forall y.\ \ \exists p.\{x,y\}\subset p$

Учитывая приведенные выше определения, $\{x,y\}\subset p$ расширяется до $\forall z.(z=x\lor z=y)\to z\in p$, так что здесь используется равенство и дизъюнкция. Аксиома гласит, что для любых двух множеств $x$ и $y$, есть хотя бы один набор $p$, которые содержат по крайней мере эти два набора.

С ограниченным разделением ниже также класс $\{x,y\}$ существует как множество. Обозначим через $\langle x,y\rangle$ стандартная упорядоченной пары модель $\{\{x\},\{x,y\}\}$, так что, например, $q=\langle x,y\rangle$ обозначает другую ограниченную формулу на формальном языке теории.

А затем, используя экзистенциальную квантификацию и союз,

Союз $\forall x.\ \ \exists u.\forall z.{\Big (}{\big (}\exists (y\in x).z\in y{\big )}\to z\in u{\Big )}$

говоря, что для любого набора $x$, есть хотя бы один набор $u$, который содержит все члены $z$, из $x$члены $y$.Минимальным таким набором является объединение .

Две аксиомы обычно формулируются более строго: $\leftrightarrow$"вместо просто" $\to$", хотя это технически избыточно в контексте ${\mathsf {BCST}}$: Поскольку приведенная ниже аксиома разделения сформулирована как « $\leftrightarrow$", для заявлений $\exists t.\forall z.\phi (z)\to z\in t$ эквивалентность может быть получена, если теория допускает разделение с помощью $\phi$. В случаях, когда $\phi$ является экзистенциальным утверждением, как здесь, в аксиоме объединения, есть и другая формулировка, использующая квантор универсальности.

Также при использовании ограниченного разделения две только что сформулированные аксиомы подразумевают существование бинарного объединения двух классов. $a$ и $b$, когда установлено, что они являются множествами, обозначаемыми $\bigcup \{a,b\}$ или $a\cup b$. Для фиксированного набора $z$, чтобы подтвердить членство $z\in a\cup b$ в объединении двух данных множеств $y=a$ и $y=b$, необходимо подтвердить $z\in y$ часть аксиомы, что можно сделать путем проверки дизъюнкции предикатов, определяющих множества $a$ и $b$, для $z$. С точки зрения связанных множеств это делается путем проверки дизъюнкции $z\in a\lor z\in b$.

Объединение и другие обозначения, образующие множества, также используются для классов. Например, предложение $z\in A\land z\notin C$ написано $z\in A\setminus C$. Пусть сейчас $B\subset A$. Данный $z\in A$, разрешимость принадлежности к $B$, т.е. потенциально независимое утверждение $z\in B\lor z\notin B$, также может быть выражено как $z\in B\cup (A\setminus B)$. Но, что касается любого исключенного среднего утверждения, двойное отрицание последнего справедливо: этот союз не населен не $z$. Это показывает, что секционирование также является более сложным понятием с конструктивной точки зрения.

Установить существование

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

Аксиома пустого множества : $\exists x.\forall y.\,\neg (y\in x)$

Введение символа $\{\}$ (как сокращенное обозначение выражений с использованием характеризующих свойств) оправдано, поскольку уникальность этого набора может быть доказана. Как $y\in \{\}$ ложно для любого $y$, аксиома тогда читается $\exists x.x\simeq \{\}$.

Писать $1$ для $S0$, что равно $\{\{\}\}$, то есть $\{1\}$. Аналогично, напишите $2$ для $S1$, что равно $\{\{\},\{\{\}\}\}$, то есть $\{0,1\}$. Тогда простым и заведомо ложным утверждением будет, например, $\{\}\in \{\}$, соответствующий $0<0$ в стандартной арифметической модели.Опять же, здесь такие символы, как $\{\}$ рассматриваются как удобные обозначения, и любое предложение действительно преобразуется в выражение, использующее только « $\in$» и логические символы, включая кванторы. В сопровождении метаматематического анализа того, что возможности новых теорий эффективно эквивалентны, формальные расширения с помощью таких символов, как $0$ также можно рассмотреть.

В более общем случае для набора $x$, определите набор преемников $Sx$ как $x\cup \{x\}$. Взаимодействие операции-преемника с отношением членства имеет рекурсивное предложение в том смысле, что $(y\in Sx)\leftrightarrow (y\in x\lor y=x)$. В силу рефлексивности равенства, $x\in Sx$, и в частности $Sx$ всегда заселен.

БЦСТ

Далее используются схемы аксиом , т.е. аксиомы для некоторого набора предикатов.Некоторые из заявленных схем аксиом также должны допускать любой набор заданных параметров (то есть любые конкретные именованные переменные). $v_{0},v_{1},\dots ,v_{n}$). То есть допускаются экземпляры схемы, в которых предикат (некоторый конкретный $\phi$) также зависит от ряда дополнительных переменных множества, и утверждение аксиомы понимается с соответствующими дополнительными внешними универсальными замыканиями (как в $\forall v_{0}.\forall v_{1}.\cdots \forall v_{n}.$).

Разделение

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

Схема аксиом разделения предикатов : для любого ограниченного предиката $\phi$, с параметрами и с заданной переменной $y$ не свободен в этом, $\forall y.\,\exists s.\forall x.{\big (}x\in s\,\leftrightarrow \,(x\in y\land \phi (x)){\big )}$

Эта аксиома сводится к постулированию существования множества $s$ получается пересечением любого множества $y$ и любой предикативно описанный класс $\{x\mid \phi (x)\}$.Для любого $z$ оказывается множеством, когда предикат принимается как $\phi (x):=x\in z$, получаем бинарное пересечение множеств и записываем $s=y\cap z$. Пересечение соответствует соединению аналогично тому, как объединение соответствует дизъюнкции.

Когда предикат принимается как отрицание $\phi (x):=x\notin z$, получается разностный принцип, допускающий существование любого множества $y\setminus z$. Обратите внимание, что наборы типа $y\setminus y$ или $\{x\in y\mid \neg (x=x)\}$ всегда пусты. Итак, как отмечалось, из разделения и существования хотя бы одного множества (например, Бесконечности ниже) будет следовать существование пустого множества. $\{\}$ (также обозначается $0$).В этом консервативном контексте ${\mathsf {BCST}}$, схема предикативного разделения фактически эквивалентна пустому множеству плюс существование двоичного пересечения для любых двух множеств. Последний вариант аксиоматизации не использует схему-формулу.

Предикативное разделение — это схема, которая учитывает синтаксические аспекты предикатов, определяющих множество, с точностью до доказуемой эквивалентности. Разрешенные формулы обозначаются $\Delta _{0}$, самый низкий уровень в теоретической иерархии Леви . Общие предикаты в теории множеств никогда не ограничиваются таким образом синтаксически, и поэтому на практике родовые подклассы множеств все еще являются частью математического языка. Поскольку область действия подклассов, которые являются доказуемыми множествами, чувствительна к тому, какие множества уже существуют, эта область действия расширяется при добавлении дополнительных постулатов существования множеств.

Для предложения $P$, повторяющимся приемом в конструктивном анализе теории множеств является рассмотрение предиката $x=0\land P$ как подкласс $B:=\{x\in 1\mid P\}$ второго ординала $1:=S0=\{0\}$. Если доказано, что $P$ держится, или $\neg P$, или $\neg \neg P$, затем $B$ является обитаемым, или пустым (необитаемым), или непустым (необитаемым) соответственно.Четко, $P$ эквивалентно как предложению $0\in B$, а также $B=1$. Так же, $\neg P$ эквивалентно $B=0$ и, что то же самое, также $\neg (0\in B)$. Итак, здесь, $B$ будучи отделяемым от $1$ именно означает $P\lor \neg P$.В модели натуральных чисел, если $B$ это число, $0\in B$ также выражает это $0$ меньше, чем $B$. Объединение, которое является частью приведенного выше определения операции-преемника, может использоваться для выражения исключенного среднего оператора как $0\in SB$. Другими словами, $P$ разрешима тогда и только тогда, когда преемник $B$ больше наименьшего порядкового номера $0$. Предложение $P$ решается в любом случае путем установления того, как $0$ меньше: по $0$ уже меньше, чем $B$или по $0$ существование $SB$прямой предшественник. Еще один способ выразить исключенное среднее для $P$ это существование наименьшего числа членов обитаемого класса $b:=B\cup \{1\}$.

Если аксиома разделения допускает разделение с $P$, затем $B$ представляет собой подмножество , , которое можно назвать значением истинности связанным с $P$. Два значения истинности можно доказать равными как множества, доказав эквивалентность. В терминах этой терминологии совокупность доказательных значений априори можно понимать как богатую. Неудивительно, что разрешимые предложения имеют один из двоичных наборов истинностных значений. Исключенная средняя дизъюнкция для этого $P$ тогда также подразумевается глобальным утверждением $\forall b.(0\in b)\lor (0\notin b)$.

Нет универсального набора.

При использовании неформальной терминологии классов любое множество также считается классом. В то же время возникают так называемые собственные классы, которые не могут иметь расширения как множество. Когда в теории есть доказательство $\neg \exists x.A\subset x$, затем $A$ должно быть правильно. (Если рассматривать точку зрения ${\mathsf {ZF}}$ В теории множеств, которая имеет полное разделение, подходящие классы обычно считаются классами, которые «слишком велики», чтобы быть множеством. Говоря более технически, они являются подклассами совокупной иерархии , выходящей за пределы любых порядковых границ.)

Согласно замечанию в разделе о слиянии множеств, набор не может быть последовательно исключен как член класса вида $A\cup \{x\mid x\notin A\}$. Конструктивное доказательство того, что он принадлежит к этому классу, содержит информацию. Теперь, если $A$ это множество, то класс $\{x\mid x\notin A\}$ является доказуемо правильным. Нижеследующее демонстрирует это в частном случае, когда $A$ пусто, т.е. когда правая часть представляет собой универсальный класс. Будучи отрицательными результатами, это читается как в классической теории.

Для любого отношения справедливо следующее $E$. Это дает чисто логическое условие, что два члена $s$ и $y$ не может быть $E$- связанные друг с другом.

${\big (}\forall x.xEs\leftrightarrow (xEy\land \neg xEx){\big )}\to \neg (yEs\lor sEs\lor sEy)$

Самое главное здесь — отказ от окончательного дизъюнкта, $\neg sEy$. Выражение $\neg (x\in x)$ не предполагает неограниченной количественной оценки и поэтому допускается при разделении. Конструкция Рассела, в свою очередь, показывает, что $\{x\in y\mid x\notin x\}\notin y$. Итак, для любого набора $y$Само по себе предикативное разделение подразумевает, что существует множество, которое не является членом $y$. В частности, никакого универсального множества в этой теории не может существовать .

В теории, далее принимающей аксиому регулярности , например ${\mathsf {ZF}}$, доказано $x\in x$ ложно для любого набора $x$. Тогда это означает, что подмножество $\{x\in y\mid x\notin x\}$ равно $y$ сам по себе, и что класс $\{x\mid x\in x\}$ пустое множество.

Для любого $E$ и $y$, особый случай $s=y$ в приведенной выше формуле дает

$\neg {\big (}\forall x.xEy\leftrightarrow \neg xEx{\big )}$

Это уже подразумевает, что подкласс $\{x\mid x\notin x\}$ универсального класса также является правильным. Но даже в ${\mathsf {ZF}}$ без регулярности логично существование собственного класса одиночных элементов, каждый из которых содержит в точности самих себя.

Кроме того, в теории со стратификацией, такой как «Интуиционистские новые основания» , синтаксическое выражение $x\in x$ может быть запрещен при разделении. В свою очередь, приведенное выше доказательство отрицания существования универсального множества в этой теории невозможно.

Предикативность

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

Эта схема также является способом, которым Мак Лейн ослабляет систему, близкую к теории множеств Цермело. ${\mathsf {Z}}$, для математических основ , связанных с теорией топоса . Он также используется при изучении абсолютности и является частью формулировки теории множеств Крипке-Платека .

Ограничением аксиомы также являются непредикативные определения привратника: в лучшем случае не следует утверждать о существовании объектов, которые не поддаются явному описанию или чье определение включает в себя самих себя или ссылку на соответствующий класс, например, когда проверяемое свойство включает в себя квантор универсальности. . Итак, в конструктивной теории без аксиомы степенного множества , когда $R$ обозначает некоторый 2-арный предикат, обычно не следует ожидать подкласса $s$ из $y$ быть множеством, если оно определено, например, как в

$\{x\in y\mid \forall t.{\big (}(t\subset y)\to R(x,t){\big )}\}$,

или через аналогичные определения, включающие любую количественную оценку наборов $t\subset y$. Обратите внимание: если этот подкласс $s$ из $y$ доказано, что это множество, то само это подмножество также находится в неограниченной области действия переменной set. $t$. Другими словами, как свойство подкласса $s\subset y$ выполняется, именно этот набор $s$, определяемый с помощью выражения $R(x,s)$, будет играть роль в его собственной характеристике.

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

Замена

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

Схема аксиом замены : для любого предиката $\phi$ с заданной переменной $r$ не свободен в этом, $\forall d.\ \ \forall (x\in d).\exists !y.\phi (x,y)\to \exists r.\forall y.{\big (}y\in r\leftrightarrow \exists (x\in d).\phi (x,y){\big )}$

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

Через замену существование любой пары $\{x,y\}$ также следует из результатов любой другой конкретной пары, например $\{0,1\}=2=SS0$. Но поскольку бинарное объединение, используемое в $S$ уже использовал аксиому спаривания, этот подход затем требует постулировать существование $2$ над тем из $0$. В теории с непредикативной аксиомой Powerset существование $2\subset {\mathcal {P}}{\mathcal {P}}0$ также можно продемонстрировать с помощью разделения.

С помощью схемы замены изложенная до сих пор теория доказывает, что классы эквивалентности или индексированные суммы являются множествами. В частности, декартово произведение , содержащее все пары элементов двух множеств, является множеством. В свою очередь, для любого фиксированного числа (в метатеории) соответствующее выражение произведения, скажем $x\times x\times x\times x$, можно построить как множество. Аксиоматические требования к множествам, рекурсивно определенным в языке, обсуждаются ниже. Набор $x$ дискретно, т.е. равенство элементов внутри множества $x$ разрешимо, если соответствующее отношение как подмножество $x\times x$ разрешимо.

Замена важна для понимания функции и может рассматриваться как форма понимания в более общем плане. Только при условии ${\mathrm {PEM} }$ Замена уже подразумевает полное Разделение. В ${\mathsf {ZF}}$Замена наиболее важна для доказательства существования множеств высокого ранга , а именно с помощью примеров схемы аксиом, где $\phi (x,y)$ относится к относительно небольшому набору $x$ к более крупным, $y$.

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

Если $i_{X}$ доказано является функцией $X$ и он оснащен кодоменом $Y$ (подробно все описано ниже), изображение затем $i_{X}$ является подмножеством $Y$. В других подходах к концепции множества понятие подмножеств определяется таким образом в терминах «операций».

Наследственно конечные множества

Подвески элементов класса наследственно конечных множеств $H_{\aleph _{0}}$ может быть реализован на любом распространенном языке программирования. Обсуждаемые выше аксиомы абстрагируются от общих операций над заданным типом данных : Спаривание и Объединение связаны с вложением и сглаживанием или, вместе взятыми, конкатенацией. Замена связана с пониманием , а разделение связано с часто более простой фильтрацией . Замены вместе с индукцией множеств (представленной ниже) достаточно, чтобы аксиомизировать $H_{\aleph _{0}}$ конструктивно и эта теория изучается и без Бесконечности.

Своего рода смесь спаривания и союза, аксиома, которую легче отнести к преемнику, — это аксиома присоединения . Такие принципы актуальны для стандартного моделирования отдельных ординалов Неймана . Также существуют формулировки аксиом, в которых объединение и замена объединены в одно. Хотя постулирование замены не является необходимостью при разработке слабой конструктивной теории множеств, которая двояко интерпретируется арифметикой Гейтинга ${\mathsf {HA}}$, это некая форма индукции. Для сравнения рассмотрим очень слабую классическую теорию, называемую общей теорией множеств , которая интерпретирует класс натуральных чисел и их арифметику посредством только экстенсиональности, присоединения и полного разделения.

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

ЭКСТ

Для некоторого фиксированного предиката $I$ и набор $a$, заявление $I(a)\land {\big (}\forall y.I(y)\to a\subset y{\big )}$ выражает это $a$ является наименьшим (в смысле " $\subset$") среди всех наборов $y$ для чего $I(y)$ верно, и что это всегда подмножество таких $y$. Цель аксиомы бесконечности состоит в том, чтобы в конечном итоге получить уникальное наименьшее индуктивное множество .

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

$\exists z.(z\in A)\land \forall (x\in A).\exists (s\in A).x\in s$.

Более конкретно, обозначим через $\mathrm {Ind} _{A}$ индуктивное свойство,

$(0\in A)\land \forall (x\in A).Sx\in A$.

С точки зрения предиката $Q$ лежащий в основе класса, так что $\forall x.(x\in A)\leftrightarrow Q(x)$, последнее переводится как $Q(0)\land \forall x.{\big (}Q(x)\to Q(Sx){\big )}$.

Писать $\bigcap B$ для общего перекрестка $\{x\mid \forall (y\in B).x\in y\}$. (Можно рассмотреть вариант этого определения, требующий $\cap B\subset \cup B$, но мы используем это понятие только для следующего вспомогательного определения.)

Обычно определяют класс $\omega =\bigcap \{y\mid \mathrm {Ind} _{y}\}$, пересечение всех индуктивных множеств. (Варианты этой обработки могут работать по формуле, которая зависит от заданного параметра $w$ так что $\omega \subset w$.) Класс $\omega$ точно все держит $x$ выполнение неограниченного свойства $\forall y.\mathrm {Ind} _{y}\to x\in y$. Идея состоит в том, что если индуктивные множества вообще существуют, то класс $\omega$ делит с ними каждое общее натуральное число, а затем предложение $\omega \subset A$по определению " $\subset$", подразумевает, что $Q$ справедливо для каждого из этих натуральных чисел. Хотя ограниченного разделения недостаточно для доказательства $\omega$ Чтобы быть желаемым набором, язык здесь формирует основу для следующей аксиомы, допускающей индукцию натуральных чисел для предикатов, составляющих набор.

Элементарная конструктивная теория множеств ${\mathsf {ECST}}$ имеет аксиому ${\mathsf {BCST}}$ а также постулат

Сильная бесконечность $\exists w.{\Big (}\mathrm {Ind} _{w}\,\land \,{\big (}\forall y.\mathrm {Ind} _{y}\to w\subset y{\big )}{\Big )}$

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

Символы, называемые нулем и преемником, находятся в подписи теории Пеано . В ${\mathsf {BCST}}$, определенный выше преемник любого числа также находится в классе $\omega$ следуют непосредственно из характеристики природных явлений нашей моделью фон Неймана. Поскольку преемник такого набора содержит самого себя, также обнаруживается, что ни один преемник не равен нулю. Итак, две аксиомы Пеано , касающиеся символов нуля, и аксиома, касающаяся замкнутости символов. $S$ прийти легко. В-четвертых, в ${\mathsf {ECST}}$, где $\omega$ это набор, $S$ на $\omega$ можно доказать, что это инъективная операция.

Для некоторого предиката множеств $P$, заявление $\forall S.(S\subset \omega \to P(S))$ претензии $P$ справедливо для всех подмножеств множества натуральных чисел. И теперь аксиома доказывает, что такие множества действительно существуют. Такая количественная оценка возможна и в арифметике второго порядка .

Парный порядок" $<$"натуралы фиксируются их отношением членства" $\in$". Теория доказывает, что порядок, а также отношение равенства на этом множестве разрешимы. Мало того, что не существует числа, меньшего, чем $0$, but induction implies that among subsets of $\omega$, it is exactly the empty set which has no least member. The contrapositive of this proves the double-negated least number existence for all non-empty subsets of $\omega$. Another valid principle also classically equivalent to it is least number existence for all inhabited detachable subsets. That said, the bare existence claim for the inhabited subset $b:=\{z\in 1\mid P\}\cup \{1\}$ of $\omega$ is equivalent to excluded middle for $P$, and a constructive theory will therefore not prove $\omega$ быть упорядоченным .

Weaker formulations of infinity

Should it need motivation, the handiness of postulating an unbounded set of numbers in relation to other inductive properties becomes clear in the discussion of arithmetic in set theory further below. But as is familiar from classical set theory, also weak forms of Infinity can be formulated. For example, one may just postulate the existence of some inductive set, $\exists y.\mathrm {Ind} _{y}$ - such an existence postulate suffices when full Separation may then be used to carve out the inductive subset $w$ of natural numbers, the shared subset of all inductive classes. Alternatively, more specific mere existence postulates may be adopted. Either which way, the inductive set then fulfills the following $\Delta _{0}$ predecessor existence property in the sense of the von Neumann model:

$\forall m.(m\in w)\leftrightarrow {\big (}m=0\lor \exists (p\in w).Sp=m{\big )}$

Without making use of the notation for the previously defined successor notation, the extensional equality to a successor $Sp=m$ is captured by $\forall n.(n\in m)\leftrightarrow (n=p\lor n\in p)$. This expresses that all elements $m$ are either equal to $0$ or themselves hold a predecessor set $p\in w$ which shares all other members with $m$.

Observe that through the expression "$\exists (p\in w)$" on the right hand side, the property characterizing $w$ by its members $m$ here syntactically again contains the symbol $w$ itself. Due to the bottom-up nature of the natural numbers, this is tame here. Assuming $\Delta _{0}$-set induction on top of ${\mathsf {ECST}}$, no two different sets have this property.Also note that there are also longer formulations of this property, avoiding "$\exists (p\in w)$" in favor unbounded quantifiers.

Number bounds

Adopting an Axiom of Infinity, the set-bounded quantification legal in predicates used in $\Delta _{0}$-Separation then explicitly permits numerically unbounded quantifiers - the two meanings of "bounded" should not be confused.With $\omega$ at hand, call a class of numbers $I\subset \omega$ bounded if the following existence statement holds

$\exists (m\in \omega ).\forall (n\in \omega ).(n\in I\to n<m)$

This is a statements of finiteness, also equivalently formulated via $m\leq n\to n\notin I$. Similarly, to reflect more closely the discussion of functions below, consider the above condition in the form $\exists (m\in \omega ).\forall (n\in I).(n<m)$.For decidable properties, these are $\Sigma _{2}^{0}$-statements in arithmetic, but with the Axiom of Infinity, the two quantifiers are set-bound.

For a class $C$, the logically positive unboundedness statement

$\forall (k\in \omega ).\exists (j\in \omega ).(k\leq j\land j\in C)$

is now also one of infinitude. It is $\Pi _{2}^{0}$ in the decidable arithmetic case. To validate infinitude of a set, this property even works if the set holds other elements besides infinitely many of members of $\omega$.

Moderate induction in ECST

In the following, an initial segment of the natural numbers, i.e. $\{n\in \omega \mid n<m\}$ for any $m\in \omega$ and including the empty set, is denoted by $\{0,1,\dots ,m-1\}$. This set equals $m$ and so at this point "$m-1$" is mere notation for its predecessor (i.e. not involving subtraction function).

It is instructive to recall the way in which a theory with set comprehension and extensionality ends up encoding predicate logic. Like any class in set theory, a set can be read as corresponding to predicates on sets. For example, an integer is even if it is a member of the set of even integers, or a natural number has a successor if it is a member of the set of natural numbers that have a successor. For a less primitive example, fix some set $y$ and let $Q(n)$ denote the existential statement that the function space on the finite ordinal into $y$ exist. The predicate will be denoted $\exists h.h\simeq y^{\{0,1,\dots ,n-1\}}$ below, and here the existential quantifier is not merely one over natural numbers, nor is it bounded by any other set. Now a proposition like the finite exponentiation principle $\forall (n\in \omega ).Q(n)$ and, less formally, the equality $\omega =\{n\in \omega \mid Q(n)\}$ are just two ways of formulating the same desired statement, namely an $n$-indexed conjunction of existential propositions where $n$ ranges over the set of all naturals. Via extensional identification, the second form expresses the claim using notation for subclass comprehension and the bracketed object on the right hand side may not even constitute a set. If that subclass is not provably a set, it may not actually be used in many set theory principles in proofs, and establishing the universal closure $\forall (n\in \omega ).Q(n)$ as a theorem may not be possible. The set theory can thus be strengthened by more set existence axioms, to be used with predicative bounded Separation, but also by just postulating stronger $\forall$-statements.

The second universally quantified conjunct in the strong axiom of Infinity expresses mathematical induction for all $y$ in the universe of discourse, i.e. for sets. This is because the consequent of this clause, $\omega \subset y$, states that all $n\in \omega$ fulfill the associated predicate. Being able to use predicative separation to define subsets of $\omega$, the theory proves induction for all predicates $\phi (n)$ involving only set-bounded quantifiers. This role of set-bounded quantifiers also means that more set existence axioms impact the strength of this induction principle, further motivating the function space and collection axioms that will be a focus of the rest of the article. Notably, ${\mathsf {ECST}}$ already validates induction with quantifiers over the naturals, and hence induction as in the first-order arithmetic theory ${\mathsf {HA}}$. The so called axiom of full mathematical induction for any predicate (i.e. class) expressed through set theory language is far stronger than the bounded induction principle valid in ${\mathsf {ECST}}$. The former induction principle could be directly adopted, closer mirroring second-order arithmetic. In set theory it also follows from full (i.e. unbounded) Separation, which says that all predicates on $\forall$ are sets. Mathematical induction is also superseded by the (full) Set induction axiom.

Warning note: In naming induction statements, one must take care not to conflate terminology with arithmetic theories. The first-order induction schema of natural number arithmetic theory claims induction for all predicates definable in the language of first-order arithmetic, namely predicates of just numbers. So to interpret the axiom schema of ${\mathsf {HA}}$, one interprets these arithmetical formulas. In that context, the bounded quantification specifically means quantification over a finite range of numbers.One may also speak about the induction in the first-order but two-sorted theory of so-called second-order arithmetic ${\mathsf {Z}}_{2}$, in a form explicitly expressed for subsets of the naturals. That class of subsets can be taken to correspond to a richer collection of formulas than the first-order arithmetic definable ones. In the program of reverse mathematics, all mathematical objects discussed are encoded as naturals or subsets of naturals. Subsystems of ${\mathsf {Z}}_{2}$ with very low complexity comprehension studied in that framework have a language that does not merely express arithmetical sets, while all sets of naturals particular such theories prove to exist are just computable sets. Theorems therein can be a relevant reference point for weak set theories with a set of naturals, predicative separation and only some further restricted form of induction. Constructive reverse mathematics exists as a field but is less developed than its classical counterpart. ${\mathsf {Z}}_{2}$ shall moreover not be confused with the second-order formulation of Peano arithmetic ${\mathsf {PA}}_{2}$. Typical set theories like the one discussed here are also first-order, but those theories are not arithmetics and so formulas may also quantify over the subsets of the naturals. When discussing the strength of axioms concerning numbers, it is also important to keep in mind that the arithmetical and the set theoretical framework do not share a common signature. Likewise, care must always be taken with insights about totality of functions. In computability theory, the μ operator enables all partial general recursive functions (or programs, in the sense that they are Turing computable), including ones e.g. non-primitive recursive but ${\mathsf {PA}}$-total, such as the Ackermann function. The definition of the operator involves predicates over the naturals and so the theoretical analysis of functions and their totality depends on the formal framework and proof calculus at hand.

Functions

General note on programs and functions

Naturally, the meaning of existence claims is a topic of interest in constructivism, be it for a theory of sets or any other framework.Let $R$ express a property such that a mathematical framework validates what amounts to the statement

$\forall (a\in A).\exists (c\in C).R(a,c)$

A constructive proof calculus may validate such a judgement in terms of programs on represented domains and some object representing a concrete assignment $a\mapsto c_{a}$, providing a particular choice of value in $C$ (a unique one), for each input from $A$. Expressed through the rewriting $\forall (a\in A).R(a,c_{a})$, this function object maybe be understood as witnessing the proposition. Consider for example the notions of proof in through realizability theory or function terms in a type theory with a notion of quantifiers. The latter captures proof of logical proposition through programs via the Curry–Howard correspondence.

Depending on the context, the word "function" may be used in association with a particular model of computation, and this is a priori narrower than what is discussed in the present set theory context. One notion of program is formalized by partial recursive "functions" in computability theory. But beware that here the word "function" is used in a way that also comprises partial functions, and not just "total functions". The scare quotes are used for clarity here, as in a set theory context there is technically no need to speak of total functions, because this requirement is part of the definition of a set theoretical function and partial function spaces can be modeled via unions. At the same time, when combined with a formal arithmetic, partial function programs provides one particularly sharp notion of totality for functions. By Kleene's normal form theorem, each partial recursive function on the naturals computes, for the values where it terminates, the same as $a\mapsto U(\mu w.T_{1}(e,a,w))$, for some partial function program index $e\in {\mathbb {N} }$, and any index will constitute some partial function. A program can be associated with a $e$ and may be said to be $T_{1}$-total whenever a theory proves $\forall a.\exists w.T_{1}(e,a,w)$, where $T_{1}$ amounts to a primitive recursive program and $w$ is related to the execution of $e$. Kreisel proved that the class of partial recursive functions proven $T_{1}$-total by ${\mathsf {HA}}$ is not enriched when ${\mathrm {PEM} }$ is added. As a predicate in $e$, this totality constitutes an undecidable subset of indices, highlighting that the recursive world of functions between the naturals is already captured by a set dominated by ${\mathbb {N} }$. As a third warning, note that this notion is really about programs and several indices will in fact constitute the same function, in the extensional sense.

A theory in first-order logic, such as the axiomatic set theories discussed here, comes with a joint notion of total and functional for a binary predicate $R$, namely $\forall a.\exists !c.R(a,c)$. Such theories relate to programs only indirectly. If $S$ denotes the successor operation in a formal language of a theory being studied, then any number, e.g. ${\mathrm {SSS0} }$ (the number three), may metalogically be related to the standard numeral, e.g. ${\underline {\mathrm {SSS0} }}=SSS0$. Similarly, programs in the partial recursive sense may be unrolled to predicates and weak assumptions suffice so that such a translation respects equality of their return values. Among finitely axiomizable sub-theories of ${\mathsf {PA}}$, classical Robinson arithmetic ${\mathsf {Q}}$ exactly fulfills this. Its existence claims are intended to only concern natural numbers and instead of using the full mathematical induction schema for arithmetic formulas, the theories' axioms postulate that every number is either zero or that there exists a predecessor number to it. Focusing on $T_{1}$-total recursive functions here, it is a meta-theorem that the language of arithmetic expresses them by $\Sigma _{1}$-predicates $G$ encoding their graph such that ${\mathsf {Q}}$ represents them, in the sense that it correctly proves or rejects $G({\underline {\mathrm {a} }},{\underline {\mathrm {c} }})$ for any input-output pair of numbers $\mathrm {a}$ and $\mathrm {c}$ in the meta-theory. Now given a correctly representing $G$, the predicate $G_{\mathrm {least} }(a,c)$ defined by $G(a,c)\land \forall (n<c).\neg G(a,n)$ represents the recursive function just as well, and as this explicitly only validates the smallest return value, the theory also proves functionality for all inputs ${\mathrm {a} }$ in the sense of ${\mathsf {Q}}\vdash \exists !c.G_{\mathrm {least} }({\underline {\mathrm {a} }},c)$. Given a representing predicate, then at the cost of making use of ${\mathrm {PEM} }$, one can always also systematically (i.e. with a $\forall a.$) prove the graph to be total functional.

Which predicates are provably functional for various inputs, or even total functional on their domain, generally depends on the adopted axioms of a theory and proof calculus. For example, for the diagonal halting problem, which cannot have a $T_{1}$-total index, it is ${\mathsf {HA}}$-independent whether the corresponding graph predicate on ${\mathbb {N} }\times \{0,1\}$ (a decision problem) is total functional, but ${\mathrm {PEM} }$ implies that it is. Proof theoretical function hierarchies provide examples of predicates proven total functional in systems going beyond ${\mathsf {PA}}$.Which sets proven to exist do constitute a total function, in the sense introduced next, also always depends on the axioms and the proof calculus. Finally, note that the soundness of halting claims is a metalogical property beyond consistency, i.e. a theory may be consistent and from it one may prove that some program will eventually halt, despite this never actually occurring when said program is run. More formally, assuming consistency of a theory does not imply it is also arithmetically $\Sigma _{1}$-sound.

Total functional relations

In set theory language here, speak of a function class when $f\subset A\times C$ and provenly

$\forall (a\in A).\,\exists !(c\in C).\langle a,c\rangle \in f$.

Notably, this definition involves quantifier explicitly asking for existence - an aspect which is particularly important in the constructive context. In words: For every $a$, it demands the unique existence of a $c$ so that $\langle a,c\rangle \in f$. In the case that this holds one may use function application bracket notation and write $f(a)=c$. The above property may then be stated as $\forall (a\in A).\,\exists !(c\in C).f(a)=c$. This notation may be extended to equality of function values. Some notational conveniences involving function application will only work when a set has indeed been established to be a function.Let $C^{A}$ (also written $^{A}C$) denote the class of sets that fulfill the function property. This is the class of functions from $A$ to $C$ in a pure set theory. Below the notation $x\to y$ is also used for $y^{x}$, for the sake of distinguishing it from ordinal exponentiation. When functions are understood as just function graphs as here, the membership proposition $f\in C^{A}$ is also written $f\colon A\to C$. The Boolean-valued $\chi _{B}\colon A\to \{0,1\}$ are among the classes discussed in the next section.

By construction, any such function respects equality in the sense that $(x=y)\to f(x)=f(y)$, for any inputs from $A$. This is worth mentioning since also more broader concepts of "assignment routines" or "operations" exist in the mathematical literature, which may not in general respect this. Variants of the functional predicate definition using apartness relations on setoids have been defined as well. A subset of a function is still a function and the function predicate may also be proven for enlarged chosen codomain sets. As noted, care must be taken with nomenclature "function", a word which sees use in most mathematical frameworks. When a function set itself is not tied to a particular codomain, then this set of pairs is also member of a function space with larger codomain. This do not happen when by the word one denotes the subset of pairs paired with a codomain set, i.e. a formalization in terms of $(A\times C)\times \{C\}$. This is mostly a matter of bookkeeping, but affects how other predicates are defined, question of size. This choice is also just enforced by some mathematical frameworks. Similar considerations apply to any treatment of partial functions and their domains.

If both the domain $A$ and considered codomain $C$ are sets, then the above function predicate only involves bounded quantifiers. Common notions such as injectivity and surjectivity can be expressed in a bounded fashion as well, and thus so is bijectivity. Both of these tie in to notions of size. Importantly, injection existence between any two sets provides a preorder. A power class does not inject into its underlying set and the latter does not map onto the former. Surjectivity is formally a more complex definition. Note that injectivity shall be defined positively, not by its contrapositive, which is common practice in classical mathematics. The version without negations is sometimes called weakly injective. The existence of value collisions is a strong notion of non-injectivity. And regarding surjectivity, similar considerations exist for outlier-production in the codomain.

Whether a subclass (or predicate for that matter) can be judged to be a function set, or even total functional to begin with, will depend on the strength of the theory, which is to say the axioms one adopts. And notably, a general class could also fulfill the above defining predicate without being a subclass of the product $A\times C$, i.e. the property is expressing not more or less than functionality w.r.t. the inputs from $A$.Now if the domain is a set, the function comprehension principle, also called axiom of unique choice or non-choice, says that a function as a set, with some codomain, exists well. (And this principle is valid in a theory like ${\mathsf {CZF}}$. Also compare with the Replacement axiom.) That is, the mapping information exists as set and it has a pair for each element in the domain. Of course, for any set from some class, one may always associate unique element of the singleton $1$, which shows that merely a chosen range being a set does not suffice to be granted a function set.It is a metatheorem for theories containing ${\mathsf {BCST}}$ that adding a function symbol for a provenly total class function is a conservative extension, despite this formally changing the scope of bounded Separation.In summary, in the set theory context the focus is on capturing particular total relations that are functional. To delineate the notion of function in the theories of the previous subsection (a 2-ary logical predicate defined to express a functions graph, together with a proposition that it is total and functional) from the "material" set theoretical notion here, one may explicitly call the latter graph of a function, anafunction or set function. The axiom schema of Replacement can also be formulated in terms of the ranges of such set functions.

Finitude

One defines three distinct notions involving surjections. For a general set to be (Bishop-)finite shall mean there is a bijective function to a natural. If the existence of such a bijection is proven impossible, the set is called non-finite. Secondly, for a notion weaker than finite, to be finitely indexed (or Kuratowski-finite) shall mean that there is a surjection from a von Neumann natural number onto it. In programming terms, the element of such a set are accessible in a (ending) for-loop, and only those, while it may not be decidable whether repetition occurred. Thirdly, call a set subfinite if it is the subset of a finite set, which thus injects into that finite set. Here, a for-loop will access all of the set's members, but also possibly others. For another combined notion, one weaker than finitely indexed, to be subfinitely indexed means to be in the surjective image of a subfinite set, and in ${\mathsf {ETCS}}$ this just means to be the subset of a finitely indexed set, meaning the subset can also be taken on the image side instead of the domain side. A set exhibiting either of those notions can be understood to be majorized by a finite set, but in the second case the relation between the sets members is not necessarily fully understood. In the third case, validating membership in the set is generally more difficult, and not even membership of its member with respect to some superset of the set is necessary fully understood.The claim that being finite is equivalent to being subfinite, for all sets, is equivalent to ${\mathrm {PEM} }$.More finiteness properties for a set $X$ can be defined, e.g. expressing the existence of some large enough natural such that a certain class of functions on the naturals always fail to map to distinct elements in $X$. One definition considers some notion of non-injectivity into $X$. Other definitions consider functions to a fixed superset of $X$ with more elements.

Terminology for conditions of finiteness and infinitude may vary. Notably, subfinitely indexed sets (a notion necessarily involving surjections) are sometimes called subfinite (which can be defined without functions). The property of being finitely indexed could also be denoted "finitely countable", to fit the naming logic, but is by some authors also called finitely enumerable (which might be confusing as this suggest an injection in the other direction). Relatedly, the existence of a bijection with a finite set has not established, one may say a set is not finite, but this use of language is then weaker than to claim the set to be non-finite. The same issue applies to countable sets (not proven countable vs. proven non-countable), et cetera. A surjective map may also be called an enumeration.

Infinitude

The set $\omega$ itself is clearly unbounded. In fact, for any surjection from a finite range onto $\omega$, one may construct an element that is different from any element in the functions range. Where needed, this notion of infinitude can also be expressed in terms of an apartness relation on the set in question. Being not Kuratowski-finite implies being non-finite and indeed the naturals shall not be finite in any sense. Commonly, the word infinite is used for the negative notion of being non-finite. Further, observe that $\omega$, unlike any of its members, can be put in bijection with some of its proper unbounded subsets, e.g. those of the form $w_{m}:=\{k\in \omega \mid k>m\}$ for any $m\in \omega$. This validates the formulations of Dedekind-infinite. So more generally than the property of infinitude in the previous section on number bounds, one may call a set infinite in the logically positive sense if one can inject $\omega$ into it. A set that is even in bijection with $\omega$ may be called countably infinite. A set is Tarski-infinite if there is a chain of $\subset$-increasing subsets of it. Here each set has new elements compared to its predecessor and the definition does not speak of sets growing rank. There are indeed plenty of properties characterizing infinitude even in classical ${\mathsf {ZF}}$ and that theory does not prove all non-finite sets to be infinite in the injection existence sense, albeit it there holds when further assuming countable choice. ${\mathsf {ZF}}$ without any choice even permits cardinals aside the aleph numbers, and there can then be sets that negate both of the above properties, i.e. they are both non-Dedekind-infinite and non-finite (also called Dedekind-finite infinite sets).

Call an inhabited set countable if there exists a surjection from $\omega$ onto it and subcountable if this can be done from some subset of $\omega$. Call a set enumerable if there exists an injection to $\omega$, which renders the set discrete. Notably, all of these are function existence claims. The empty set is not inhabited but generally deemed countable too, and note that the successor set of any countable set is countable. The set $\omega$ is trivially infinite, countable and enumerable, as witnessed by the identity function. Also here, in strong classical theories many of these notions coincide in general and, as a result, the naming conventions in the literature are inconsistent. An infinite, countable set is equinumeros to $\omega$.

There are also various ways to characterize logically negative notion. The notion of uncountability, in the sense of being not countable, is also discussed in conjunction with the exponentiation axiom further below. Another notion of uncountability of $X$ is given when one can produce a member in the compliment of any of $X$'s countable subsets. More properties of finiteness may be defined as negations of such properties, et cetera.

Characteristic functions

Separation lets us cut out subsets of products $A\times C$, at least when they are described in a bounded fashion. Given any $B\subset A$, one is now led to reason about classes such as

$X_{B}:={\big \{}\langle x,y\rangle \in A\times \{0,1\}\mid (x\in B\land y=1)\lor (x\notin B\land y=0){\big \}}.$

Since $\neg (0=1)$, one has

${\big (}a\in B\ \leftrightarrow \,\langle a,1\rangle \in X_{B}{\big )}\,\land \,{\big (}a\notin B\ \leftrightarrow \,\langle a,0\rangle \in X_{B}{\big )}$

and so

${\big (}a\in B\lor a\notin B{\big )}\ \leftrightarrow \ \exists !(y\in \{0,1\}).\langle a,y\rangle \in X_{B}$.

But be aware that in absence of any non-constructive axioms $a\in B$ may in generally not be decidable, since one requires an explicit proof of either disjunct. Constructively, when $\exists (y\in \{0,1\}).\langle x,y\rangle \in X_{B}$ cannot be witnessed for all the $x\in A$, or uniqueness of the terms $y$ associated with each $x$ cannot be proven, then one cannot judge the comprehended collection to be total functional.Case in point: The classical derivation of Schröder–Bernstein relies on case analysis - but to constitute a function, particular cases shall actually be specifiable, given any input from the domain. It has been established that Schröder–Bernstein cannot have a proof on the base of ${\mathsf {IZF}}$ plus constructive principles. So to the extent that intuitionistic inference does not go beyond what is formalized here, there is no generic construction of a bijection from two injections in opposing directions.

But being compatible with ${\mathsf {ZF}}$, the development in this section still always permits "function on $\omega$" to be interpreted as a completed object that is also not necessarily given as lawlike sequence. Applications may be found in the common models for claims about probability, e.g. statements involving the notion of "being given" an unending random sequence of coin flips, even if many predictions can also be expressed in terms of spreads.

If indeed one is given a function $\chi _{B}\colon A\to \{0,1\}$, it is the characteristic function actually deciding membership in some detachable subset $B\subset A$ and

$B=\{n\in \omega \mid \chi _{B}(n)=1\}.$

Per convention, the detachable subset $B$, $\chi _{B}$ as well as any equivalent of the formulas $n\in B$ and $\chi _{B}(n)=1$ (with $n$ free) may be referred to as a decidable property or set on $A$.

One may call a collection $A$ searchable for $\chi _{B}$ if existence is actually decidable,

$\exists (x\in A).\chi _{B}(x)=1\ \lor \ \forall (x\in A).\chi _{B}(x)=0.$

Now consider the case $A=\omega$. If $\chi _{B}(0)=0$, say, then the range $\{0\}\subset R\subset \{0,1\}$ of $\chi _{B}$ is an inhabited, counted set, by Replacement. However, the $R$ need not be again a decidable set itself, since the claim $R=\{0\}$ is equivalent to the rather strong $\forall n.\chi _{B}(n)=0$. Moreover, $R=\{0\}$ is also equivalent to $B=\{\}$ and so one can state undecidable propositions about $B$ also when membership in $B$ is decidable.This also plays out like this classically in the sense that statements about $B$ may be independent, but any classical theory then nonetheless claims the joint proposition $B=\{\}\lor \neg (B=\{\})$. Consider the set $B$ of all indices of proofs of an inconsistency of the theory at hand, in which case the universally closed statement $B=\{\}$ is a consistency claim. In terms of arithmetic principles, assuming decidability of this would be $\Pi _{1}^{0}$-${\mathrm {PEM} }$ or arithmetic $\forall$-${\mathrm {PEM} }$. This and the stronger related ${\mathrm {LPO} }$, or arithmetic $\exists$-${\mathrm {PEM} }$, is discussed below.

Witness of apartness

If there is a predicate $P$ that distinguishes two terms $x$ and $y$ in the sense that $P(x)\land \neg P(y)$, then the identity of indiscernibles principle implies that the two do not coincide. This notion may be expressed set theoretically: $x,y\in A$ may be deemed apart if there exists a subset $B\subset A$ such that one is a member and the other is not. Restricted to detachable subsets, this may be formulated concisely via quantification over functions $\chi _{B}\in 2^{A}$. Indeed, $x=y$ is already rejected once it is established that not all functions $f$ respect $f(x)=f(y)$. In that spirit, one may on any set $A$ define the logically positive apartness relation

$x\,\#_{A}\,y\,:=\,\exists (f\in {\mathbb {N} }^{A}).f(x)\neq f(y)$.

As the naturals are discrete, the above here manifests in the theorem

$\neg \neg (x\,\#_{A}\,y)\to \neg (x=y)$.

Computable sets

Going back to more generality, given a general predicate $Q$ on the numbers (say one defined from Kleene's T predicate), let again

$B:=\{n\in \omega \mid Q(n)\}.$

Given any natural $n\in \omega$, then

${\big (}Q(n)\lor \neg Q(n){\big )}\leftrightarrow {\big (}n\in B\lor n\notin B{\big )}.$

In classical set theory, $\forall (n\in \omega ).Q(n)\lor \neg Q(n)$ by ${\mathrm {PEM} }$ and so excluded middle also holds for subclass membership. If the class $B$ has no numerical bound, then successively going through the natural numbers $n$, and thus "listing" all numbers in $B$ by simply skipping those with $n\notin B$, classically always constitutes an increasing surjective sequence $b\colon \omega \twoheadrightarrow B$. There, one can obtain a bijective function. In this way, the class of functions in typical classical set theories is provenly rich, as it also contains objects that are beyond what we know to be effectively computable, or programmatically listable in praxis.

In computability theory, the computable sets are ranges of non-decreasing total functions in the recursive sense, at the level $\Sigma _{1}^{0}\cap \Pi _{1}^{0}=\Delta _{1}^{0}$ of the arithmetical hierarchy, and not higher. Deciding a predicate at that level amounts to solving the task of eventually finding a certificate that either validates or rejects membership.As not every predicate $Q$ is computably decidable, also the theory ${\mathsf {CZF}}$ alone will not claim (prove) that all unbounded $B\subset \omega$ are the range of some bijective function with domain $\omega$. See also Kripke's schema.Note that bounded Separation nonetheless proves the more complicated arithmetical predicates to still constitute sets, the next level being the computably enumerable ones at $\Sigma _{1}^{0}$.

There is a large corpus of computability theory notions regarding how general subsets of naturals relate to one another. For example, one way to establish a bijection of two such sets is by relating them through a computable isomorphism, which is a computable permutation of all the naturals. The latter may in turn be established by a pair of particular injections in opposing directions.

Boundedness criteria

Any subset $B\subset \omega$ injects into $\omega$. If $B$ is decidable and inhabited with $y_{0}\in B$, the sequence

$q:={\big \{}\langle x,y\rangle \in \omega \times B\mid (x\in B\land y=x)\lor (x\notin B\land y=y_{0}){\big \}}$

i.e.

$q(x):={\begin{cases}x&x\in B\\y_{0}&x\notin B\\\end{cases}}$

is surjective onto $B$, making it a counted set. That function also has the property $\forall (x\in B).q(x)=x$.

Now consider a countable set $R\subset \omega$ that is bounded in the sense defined previously. Any sequence taking values in $R$ is then numerically capped as well, and in particular eventually does not exceed the identity function on its input indices. Formally,

$\forall (r\colon \omega \to R).\exists (m\in \omega ).\forall (k\in \omega ).k>m\to r(k)<k$

A set $I$ such that this loose bounding statement holds for all sequences taking values in $I$ (or an equivalent formulation of this property) is called pseudo-bounded. The intention of this property would be to still capture that $I\subset \omega$ is eventually exhausted, albeit now this is expressed in terms of the function space $I^{\omega }$ (which is bigger than $I$ in the sense that $I$ always injects into $I^{\omega }$). The related notion familiar from topological vector space theory is formulated in terms of ratios going to zero for all sequences (${\tfrac {r(k)}{k}}$ in the above notation). For a decidable, inhabited set, validity of pseudo-boundedness, together with the counting sequence defined above, grants a bound for all the elements of $I$.

The principle that any inhabited, pseudo-bounded subset of $\omega$ that is just countable (but not necessarily decidable) is always also bounded is called $\mathrm {BD}$-${\mathbb {N} }$. The principle also holds generally in many constructive frameworks, such as the Markovian base theory ${\mathsf {HA}}+{\mathrm {ECT} }_{0}+{\mathrm {MP} }$, which is a theory postulating exclusively lawlike sequences with nice number search termination properties. However, $\mathrm {BD}$-${\mathbb {N} }$ is independent of ${\mathsf {IZF}}$.

Choice functions

Not even classical ${\mathsf {ZF}}$ proves each union of a countable set of two-element sets to be countable again. Indeed, models of ${\mathsf {ZF}}$ have been defined that negate the countability of such a countable union of pairs. Assuming countable choice rules out that model as an interpretation of the resulting theory. This principle is still independent of ${\mathsf {ZF}}$ - A naive proof strategy for that statement fails at the accounting of infinitely many existential instantiations.

A choice principle postulates that certain selections can always be made in a joint fashion in the sense that they are also manifested as a single set function in the theory. As with any independent axiom, this raises the proving capabilities while restricting the scope of possible (model-theoretic) interpretations of the (syntactic) theory. A function existence claim can often be translated to the existence of inverses, orderings, and so on. Choice moreover implies statements about cardinalities of different sets, e.g. they imply or rule out countability of sets. Adding full choice to ${\mathsf {ZF}}$ does not prove any new $\Pi _{4}^{1}$-theorems, but it is strictly non-constructive, as shown below. The development here proceeds in a fashion agnostic to any of the variants described next.

• Axiom of countable choice ${\mathrm {AC} _{\omega }}$ (or ${\mathrm {CC} }$): If $g\colon \omega \to z$, one can form the one-to-many relation-set $\{\langle n,u\rangle \mid n\in \omega \land u\in g(n)\}$. The axiom of countable choice would grant that whenever $\forall (n\in \omega ).\exists u.u\in g(n)$, one can form a function mapping each number to a unique value. The existence of such sequences is not generally provable on the base of ${\mathsf {ZF}}$ and countable choice is not $\Sigma _{4}^{1}$-conservative over that theory. Countable choice into general sets can also be weakened further. One common consideration is to restrict the possible cardinalities of the range of $g$, giving the weak countable choice into countable, finite or even just binary sets (${\mathrm {AC} _{\omega ,2}}$). One may consider the version of countable choice for functions into $\omega$ (called ${\mathrm {AC} _{\omega ,\omega }}$ or ${\mathrm {AC} _{00}}$), as is implied by the constructive Church's thesis principle, i.e. by postulating that all total arithmetical relations are recursive. ${\mathrm {CT} _{0}}$ in arithmetic may be understood as a form of choice axiom. Another means of weakening countable choice is by restricting the involved definitions w.r.t. their place in the syntactic hierarchies (say $\Pi _{1}^{0}$-${\mathrm {AC} _{\omega ,2}}$). The weak Kőnig's lemma ${\mathrm {WKL} }$, which breaks strictly recursive mathematics as further discussed below, is stronger than $\Pi _{1}^{0}$-${\mathrm {AC} _{\omega ,2}}$ and is itself sometimes viewed as capturing a form of countable choice. In the presence of a weak form of countable choice, the lemma becomes equivalent to the non-constructive principle of more logical flavor, ${\mathrm {LLPO} }$. Constructively, a weak form of choice is required for well-behaved Cauchy reals. Countable choice is not valid in the internal logic of a general topos, which can be seen as models of constructive set theories.
• Axiom of dependent choice ${\mathrm {DC} }$: Countable choice is implied by the more general axiom of dependent choice, extracting a sequence in an inhabited $z$, given any entire relation $R\subset z\times z$. In set theory, this sequence is again an infinite set of pairs, a subset of $\omega \times z$. So one is granted to pass from several existence statements to function existence, itself granting unique-existence statements, for every natural. An appropriate formulation of dependent choice is adopted in several constructive frameworks, e.g., by some schools that understand unending sequences as ongoing constructions instead of completed objects. At least those cases seem benign where, for any $x\in z$, next value existence $\exists (y\in z).xRy$ can be validated in a computable fashion. The corresponding recursive function $\omega \to z$, if it exists, is then conceptualized as being able to return a value at infinitely many potential inputs $n\in \omega$, but these do not have to be evaluated all together at once. It also holds in many realizability models. In the condition of the formally similar recursion theorem, one is already given a unique choice at each step, and that theorem lets one combine them to a function on $\omega$. So also with ${\mathrm {DC} }$ one may consider forms of the axiom with restrictions on $R$. Via the bounded separation axiom in ${\mathsf {ECST}}$, the principle also is equivalent to a schema in two bounded predicate variables: Keeping all quantifiers ranging over $z$, one may further narrow this set domain using a unary $\Delta _{0}$-predicate variable, while also using any 2-ary $\Delta _{0}$-predicate instead of the relation set $R$.
• Relativized dependent choice ${\mathrm {RDC} }$: This is the schema just using two general classes, instead of requiring $z$ and $R$ be sets. The domain of the choice function granted to exist is still just $\omega$. Over ${\mathsf {ECST}}$, it implies full mathematical induction, which, in turn allows for function definition on $\omega$ through the recursion schema. When ${\mathrm {RDC} }$ is restricted to $\Delta _{0}$-definitions, it still implies mathematical induction for $\Sigma _{1}$-predicates (with an existential quantifier over sets) as well as ${\mathrm {DC} }$. In ${\mathsf {ZF}}$, the schema ${\mathrm {RDC} }$ is equivalent to ${\mathrm {DC} }$.
• $\Pi \Sigma$-$\mathrm {AC}$: A family of sets is better controllable if it comes indexed by a function. A set $b$ is a base if all indexed families of sets $i_{s}\colon b\to s$ over it, have a choice function $f_{s}$, i.e. $\forall (x\in b).f_{s}(x)\in i_{s}(x)$. A collection of sets holding $\omega$ and its elements and which is closed by taking indexed sums and products (see dependent type) is called $\Pi \Sigma$-closed. While the axiom that all sets in the smallest $\Pi \Sigma$-closed class are a base does need some work to formulate, it is the strongest choice principle over ${\mathsf {CZF}}$ that holds in the type theoretical interpretation ${\mathsf {ML_{1}V}}$.
• Axiom of choice ${\mathrm {AC} }$: This is the "full" choice function postulate concerning domains that are general sets $\{z,\dots \}$ containing inhabited sets, with the codomain given as their general union. Given a collection of sets such that the logic allows to make a choice in each, the axiom grants that there exists a set function that jointly captures a choice in all. It is typically formulated for all sets but has also been studied in classical formulations for sets only up to any particular cardinality. A standard example is choice in all inhabited subsets of the reals, which classically equals the domain ${\mathcal {P}}_{\mathbb {R} }\setminus 1$. For this collection there can be no uniform element selection prescription that provably constitutes a choice function on the base of ${\mathsf {ZF}}$. Also, when restricted to the Borel algebra of the reals, ${\mathsf {ZF}}$ alone does not prove the existence of a function selecting a member from each non-empty such Lebesgue-measurable subset. (The set ${\mathcal {B}}({\mathbb {R} })$ is the σ-algebra generated by the intervals $I:=\{(x,y\,]\mid x,y\in {\mathbb {R} }\}$. It strictly includes those intervals, in the sense of $I\subsetneq {\mathcal {B}}({\mathbb {R} })\subsetneq {\mathcal {P}}_{\mathbb {R} }$, but in ${\mathsf {ZF}}$ also only has the cardinality of the reals itself.) Striking existence claims implied by the axiom are abound. ${\mathsf {ECST}}$ proves $\omega$ exists and then the axiom of choice also implies dependent choice. Critically in the present context, it moreover also implies instances of ${\mathrm {PEM} }$ via Diaconescu's theorem. For ${\mathsf {ECST}}$ or theories extending it, this means full choice at the very least proves ${\mathrm {PEM} }$ for all $\Delta _{0}$-formulas, a non-constructive consequence not acceptable, for example, from a computability standpoint. Note that constructively, Zorn's lemma does not imply choice: When membership in function domains fails to be decidable, the extremal function granted by that principle is not provably always a choice function on the whole domain.

Diaconescu's theorem

To highlight the strength of full Choice and its relation to matters of intentionality, one should consider the classes

$a=\{u\in \{0,1\}\mid (u=0)\lor P\}$

$b=\{u\in \{0,1\}\mid (u=1)\lor P\}$

from the proof of Diaconescu's theorem. They are as contingent as the proposition $P$ involved in their definition and they are not proven finite. Nonetheless, the setup entails several consequences. Referring back to the introductory elaboration on the meaning of such convenient class notation, as well as to the principle of distributivity, $t\in a\leftrightarrow {\big (}t=0\lor (t=1\land P){\big )}$. So unconditionally, $0\in a$ as well as $1\in b$, and in particular they are inhabited. As $\neg (0=1)$ in any model of Heyting arithmetic, using the disjunctive syllogism both $0\in b$ and $1\in a$ each imply $P$. The two statements are indeed equivalent to the proposition, as clearly $P\to (a=\{0,1\}\land b=\{0,1\})$. The latter also says that validity of $P$ means $a$ and $b$ share all members, and there are two of these. As $a$ are $b$ are then sets, also $P\to (a=b\land \{a,b\}=\{a\})$ by extensionality. Conversely, assuming they are equal means $x\in a\leftrightarrow x\in b$ for any $x$, validating all membership statements. So both the membership statements as well as the equalities are found to be equivalent to $P$. Using the contrapositive results in the weaker equivalence of disjuncts $(P\lor \neg P)\leftrightarrow (a=b\lor \neg (a=b))$. Of course, explicitly $\neg P\to (a=\{0\}\land b=\{1\})$ and so one actually finds in which way the sets can end up being different. As functions preserves equality by definition, $\neg {\big (}g(a)=g(b){\big )}\to \neg P$ indeed holds for any $g$ with domain $\{a,b\}$.

In the following assume a context in which $a,b$ are indeed established to be sets, and thus subfinite sets. The general axiom of choice claims existence of a function $f\colon \{a,b\}\to a\cup b$ with $f(z)\in z$. It is important that the elements $a,b$ of the function's domain are different than the natural numbers $0,1$ in the sense that a priori less is known about the former. When forming then union of the two classes, $u=0\lor u=1$ is a necessary but then also sufficient condition. Thus $a\cup b=\{0,1\}$ and one is dealing with functions $f$ into a set of two distinguishable values. With choice come the conjunction $f(a)\in a\land f(b)\in b$ in the codomain of the function, but the possible function return values are known to be just $0$ or $1$. Using the distributivity, there arises a list of conditions, another disjunction. Expanding what is then established, one finds that either both $P$ as well as the sets equality holds, or that the return values are different and $P$ can be rejected. The conclusion is that the choice postulate actually implies $P\lor \neg P$ whenever a Separation axiom allows for set comprehension using undecidable proposition $P$.

Analysis of Diaconescu's theorem

So full choice is non-constructive in set theory as defined here. The issue is that when propositions are part of set comprehension (like when $P$ is used to separate, and thereby define, the classes $a$ and $b$ from $\{0,1\}$), the notion of their truth values are ramified into set terms of the theory. Equality defined by the set theoretical axiom of extensionality, which itself is not related to functions, in turn couples knowledge about the proposition to information about function values. To recapitulate the final step in terms function values: On the one hand, witnessing $f(a)=1$ implies $P$ and $a=b$ and this conclusion independently also applies to witnessing $f(b)=0$. On the other hand, witnessing $f(a)=0\land f(b)=1$ implies the two function arguments are not equal and this rules out $P$. There are really only three combinations, as the axiom of extensionality in the given setup makes $f(a)=1\land f(b)=0$ inconsistent. So if the constructive reading of existence is to be preserved, full choice may be not adopted in the set theory, because the mere claim of function existence does not realize a particular function.

To better understand why one cannot expect to be granted a definitive (total) choice function with domain $\{a,b\}$, consider naive function candidates. Firstly, an analysis of the domain is in order. The surjection $\{\langle 0,a\rangle ,\langle 1,b\rangle \}$ witnesses that $\{a,b\}$ is finitely indexed. It was noted that its members are subfinite and also inhabited, since regardless of $P$ it is the case that $0\in a$ and $1\in b$. So naively, this would seem to make $f=\{\langle a,0\rangle ,\langle b,1\rangle \}$ a contender for a choice function. When $P$ can be rejected, then this is indeed the only option. But in the case of provability of $P$, when $\{a,b\}=\{a\}$, there is extensionally only one possible function input to a choice function. So in that situation, a choice function would explicitly have type $f\colon \{a\}\to \{0,1\}$, for example $f=\{\langle a,0\rangle \}$ and this would rule out the initial contender. For general $P$, the domain of a would-be choice function is not concrete but contingent on $P$ and not proven finite. When considering the above functional assignment $f(a)=0$, then neither unconditionally declaring $f(b)=1$ nor $f(b)=0$ is necessarily consistent. Having identified $1$ with $\{0\}$, the two candidates described above can be represented simultaneously via $f=\{\langle a,0\rangle ,\langle b,B_{\neg }\rangle \}$ (which is not proven finite either) with the subfinite "truth value of $\neg P$" given as $B_{\neg }:=\{u\in \{0\}\mid \neg P\}$. As $(P\to (B_{\neg }=0))\land (\neg P\to (B_{\neg }=1))$, postulating $P$, or $\neg P$, or the classical principle $P\lor \neg P$ here would indeed imply that $B_{\neg }$ is a natural, so that the latter set $f$ constitutes a choice function into $\{0,1\}$. And as in the constructive case, given a particular choice function - a set holding either exactly one or exactly two pairs - one could actually infer whether $P$ or whether $\neg P$ does hold. Vice versa, the third and last candidate $f=\{\langle b,1\rangle \}$ can be captured as part of $f=\{\langle a,B\rangle ,\langle b,1\rangle \}$, where $B:=\{u\in \{0\}\mid P\}$. Such a $B$ had already been considered in the early section on the axiom of separation. Again, the latter $f$ here is a classical choice function either way also, where $P$ functions as a (potentially undecidable) "if-clause". Constructively, the domain and values of such $P$-dependent would-be functions are not understood enough to prove them to be a total functional relation into $\{0,1\}$.

For computable semantics, set theory axioms postulating (total) function existence lead to the requirement for halting recursive functions. From their function graph in individual interpretations, one can infer the branches taken by the "if-clauses" that were undecided in the interpreted theory. But on the level of the synthetic frameworks, when they broadly become classical from adopting full choice, these extensional set theories theories contradict the constructive Church's rule.

Regularity implies PEM

The axiom of choice grants existence a function associated with every set-sized collection of inhabited elements $s$, with which one can then at once pick unique elements $t$.The axiom of regularity states that for every inhabited set $s$ in the universal collection, there exists an element $t$ in $s$, which shares no elements with $s$. This formulation does not involve functions or unique existence claims, but instead directly guarantees sets $t\in s$ with a specific property.As the axiom correlates membership claims at different rank, the axiom also ends up implying ${\mathrm {PEM} }$:

The proof from Choice above had used $1:=\{0\}$ and a particular set $\{a,b\}$. The proof in this paragraph also assumes Separation applies to $P$ and uses $b$, for which $\{0\}\in b$ by definition. It was already explained that $P\leftrightarrow 0\in b$ and so one may prove excluded middle for $P$ in the form $0\in b\lor 0\notin b$. Now let $t\in b$ be the postulated member with the empty intersection property. The set $b$ was defined as a subset of $\{0,1\}$ and so any given $t\in b$ fulfills the disjunction $t=0\lor t=1$. The left clause $t=0$ implies $0\in b$, while for the right clause $t=1$ one may use that the special non-intersecting element $t$ fulfills $(t=\{0\})\leftrightarrow (0\notin b)$.

Demanding that the set of naturals is well-ordered with respect to it standard order relation imposes the same condition on the inhabited set $b\subset \omega$. So the least number principle has the same non-constructive implication.As with the proof from Choice, the scope of propositions for which these results hold is governed by one's Separation axiom.

Arithmetic

The four Peano axioms for $0$ and $S$, characterizing the set $\omega$ as a model of the natural numbers in the constructive set theory ${\mathsf {ECST}}$, have been discussed. The order "$<$" of natural numbers is captured by membership "$\in$" in this von Neumann model and this set is discrete, i.e. also $\phi (n,m):=(n=m)$ is decidable.

As discussed, induction for arithmetic formulas is a theorem. However, when not assuming full mathematical induction (or stronger axioms like full Separation) in a set theory, there is a pitfall regarding the existence of arithmetic operations. The first-order theory of Heyting arithmetic ${\mathsf {HA}}$ has the same signature and non-logical axioms as Peano arithmetic ${\mathsf {PA}}$. In contrast, the signature of set theory does not contain addition "$+$" or multiplication "$\times$". ${\mathsf {ECST}}$ does actually not enable primitive recursion in $\omega$ for function definitions of what would be $h\colon (x\times \omega )\to y$ (where "$\times$" here denotes the Cartesian product of set, not to be confused with multiplication above). Indeed, despite having the Replacement axiom, the theory does not prove there to be a set capturing the addition function $+\colon (\omega \times \omega )\to \omega$. In the next section, it is clarified which set theoretical axiom may be asserted to prove existence of the latter as a function set, together with their desired relation to zero and successor.

Far beyond just the equality predicate, the obtained model of arithmetic then validates

${\mathsf {HA}}\vdash \forall n.\forall m.{\big (}\phi (n,m)\lor \neg \phi (n,m){\big )}$

for any quantifier-free formula. Indeed, ${\mathsf {PA}}$ is $\Pi _{2}^{0}$-conservative over ${\mathsf {HA}}$ and double-negation elimination is possible for any Harrop formula.

Arithmetic functions from recursion

Going a step beyond ${\mathsf {ECST}}$, the axiom granting definition of set functions via iteration-step set functions must be added: For any set $y$, set $z\in y$ and $f\colon y\to y$, there must also exist a function $g\colon \omega \to y$ attained by making use of the former, namely such that $g(0)=z$ and $g(Sn)=f(g(n))$. This iteration- or recursion principle is akin to the transfinite recursion theorem, except it is restricted to set functions and finite ordinal arguments, i.e. there is no clause about limit ordinals. It functions as the set theoretical equivalent of a natural numbers object in category theory.This then enables a full interpretation of Heyting arithmetic ${\mathsf {HA}}$ in our set theory, including addition and multiplication functions.

With this, ${\mathbb {N} }$ and ${\mathbb {Z} }$ are well-founded, in the sense of the inductive subsets formulation. Further, arithmetic of rational numbers ${\mathbb {Q} }$ can then also be defined and its properties, like uniqueness and countability, be proven.

Recursion from set theory axioms

Recall that $h\simeq y^{x}$ is short for $\forall f.{\big (}f\in h\leftrightarrow f\in y^{x}{\big )}$, where $f\in y^{x}$ is short for the total function predicate, a proposition in terms of uses bounded quantifiers. If both sides are sets, then by extensionality this is also equivalent to $h=y^{x}$. (Although by slight abuse of formal notation, as with the symbol "$\in$", the symbol "$=$" is also commonly used with classes anyhow.)

A set theory with the ${\mathsf {HA}}$-model enabling recursion principle, spelled out above, will also prove that, for all naturals $n$ and $m$, the function spaces

${\{0,1,\dots ,n-1\}}\to {\{0,1,\dots ,m-1\}}$

are sets. Indeed, bounded recursion suffices, i.e. the principle for $\Delta _{0}$-defined classes.

Conversely, the recursion principle can be proven from a definition involving the union of recursive functions on finite domains. Relevant for this is the class of partial functions on $\omega$ such that all of its members have a return values only up to some natural number bound, which may be expressed by $\cup _{n\in \omega }y^{\{0,1,\dots ,n-1\}}$. Existence of this as a set becomes provable assuming that the individual function spaces $y^{n}$ all form sets themselves. To this end

Exponentiation for finite domains $\forall (n\in \omega ).\forall y.\ \ \exists h.h\simeq y^{n}$

With this axiom, any such space is now a set of subsets of $n\times y$ and this is strictly weaker than full Separation. Notably, adoption of this principle has genuine set theoretical flavor, in contrast to a direct embedding of arithmetic principles into our theory. And it is a modest principle insofar as these function spaces are tame: When instead assuming full induction or full exponentiation, taking $y$ to function spaces $y^{n}$, or to n-fold Cartesian products, provably does preserve countability.

In ${\mathsf {ECTS}}$ plus finite exponentiation, the recursion principle is a theorem. Moreover, enumerable forms of the pigeon hole principle can now also be proven, e.g. that on a finitely indexed set, every auto-injection is also a surjection. As a consequence, the cardinality of finite sets, i.e. the finite von Neumann ordinal, is provably unique. The finitely indexed discrete sets are just the finite sets. In particular, finitely indexed subsets of $\omega$ are finite. Taking quotients or taking the binary union or Cartesian product of two sets preserve finiteness, sub-finiteness and being finitely indexed.

The set theory axioms listed so far incorporates first-order arithemtic and suffices as formalized framework for a good portion of common mathematics. The restriction to finite domains is lifted in the strictly stronger exponentiation axiom below. However, also that axiom does not entail the full induction schema for formulas with unbound quantifiers over the domain of sets, nor a dependent choice principle. Likewise, there are Collection principles that are constructively not implied by Replacement, as discussed further below. A consequence of this is that for some statements of higher complexity or indirection, even if concrete instances of interest may well be provable, the theory may not prove the universal closure.Stronger than this theory with finite exponentiation is ${\mathsf {ECTS}}$ plus full induction. It implies the recursion principle even for classes and such that $g$ is unique. Already that recursion principle when restricted to $\Delta _{0}$ does prove finite exponentiation, and also the existence of a transitive closure for every set with respect to $\in$ (since union formation is $\Delta _{0}$). With it more common constructions preserve countability. General unions over a finitely indexed set of finitely indexed sets are again finitely indexed, when at least assuming induction for $\Sigma _{1}$-predicates (with respect to the set theory language, and this then holds regardless of the decidability of their equality relations.)

Induction without infinite sets

Before discussing even classically uncountable sets, this last section takes a step back to a context more akin to ${\mathsf {BCST}}$. The addition of numbers, considered as relation on triples, is an infinite collection, just like collection of natural numbers themselves. But note that induction schemas may be adopted (for sets, ordinals or in conjunction with a natural number sort), without ever postulating that the collection of naturals exists as a set. As noted, Heyting arithmetic ${\mathsf {HA}}$ is bi-interpretable with such a constructive set theory, in which all sets are postulated to be in bijection with an ordinal. The BIT predicate is a common means to encode sets in arithmetic.

This paragraph lists a few weak natural number induction principles studied in the proof theory of arithmetic theories with addition and multiplication in their signature. This is the framework where these principles are most well understood. The theories may be defined via bounded formulations or variations on induction schemas that may furthermore only allow for predicates of restricted complexity. On the classical first-order side, this leads to theories between the Robinson arithmetic ${\mathsf {Q}}$ and Peano arithmetic ${\mathsf {PA}}$: The theory ${\mathsf {Q}}$ does not have any induction. ${\mathsf {PA}}$ has full mathematical induction for arithmetical formulas and has ordinal $\varepsilon _{0}$, meaning the theory lets one encode ordinals of weaker theories as recursive relation on just the naturals. Theories may also include additional symbols for particular functions.Many of the well studied arithmetic theories are weak regarding proof of totality for some more fast growing functions. Some of the most basic examples of arithmetics include elementary function arithmetic ${\mathsf {EFA}}$, which includes induction for just bounded arithmetical formulas, here meaning with quantifiers over finite number ranges. The theory has a proof theoretic ordinal (the least not provenly recursive well-ordering) of $\omega ^{3}$.The $\Sigma _{1}^{0}$-induction schema for arithmetical existential formulas allows for induction for those properties of naturals a validation of which is computable via a finite search with unbound (any, but finite) runtime. The schema is also classically equivalent to the $\Pi _{1}^{0}$-induction schema.The relatively weak classical first-order arithmetic which adopts that schema is denoted ${\mathsf {I\Sigma }}_{1}$ and proves the primitive recursive functions total. The theory ${\mathsf {I\Sigma }}_{1}$ is $\Pi _{2}^{0}$-conservative over primitive recursive arithmetic ${\mathsf {PRA}}$.Note that the $\Sigma _{1}^{0}$-induction is also part of the second-order reverse mathematics base system ${\mathsf {RCA}}_{0}$, its other axioms being ${\mathsf {Q}}$ plus $\Delta _{1}^{0}$-comprehension of subsets of naturals. The theory ${\mathsf {RCA}}_{0}$ является $\Pi _{1}^{1}$-conservative over ${\mathsf {I\Sigma }}_{1}$. Все последние упомянутые арифметические теории имеют порядковый номер. $\omega ^{\omega }$.

Отметим еще один шаг за пределы $\Sigma _{1}^{0}$-индукционная схема. Отсутствие более сильных схем индукции означает, например, что некоторые неограниченные версии принципа ячейки недоказуемы. Одно из относительно слабых утверждений — утверждение типа теоремы Рамсея, выраженное здесь следующим образом: для любого $m>0$ и кодирование карты-раскраски $f$, связывая каждый $n\in \omega$ с цветом $\{0,1,\dots ,m-1\}$, это не тот случай, когда для каждого цвета $c<m$ существует пороговый входной номер $n_{c}$ за пределами которого $c$ больше никогда не является возвращаемым значением сопоставления. (В классическом контексте и в терминах множеств это утверждение о раскраске можно сформулировать положительно, как утверждая, что всегда существует хотя бы одно возвращаемое значение. $k$ такое, что, по сути, для некоторой неограниченной области $K\subset \omega$ он утверждает, что $\forall (n\in K).f(n)=k$. На словах, когда $f$ предоставляет бесконечные перечисляемые присваивания, каждое из которых относится к одному из $m$ различных возможных цветов, утверждается, что конкретный $k$ раскраска бесконечного числа чисел всегда существует и что таким образом набор можно указать, даже не проверяя свойства $f$. При конструктивном чтении хотелось бы $k$ Чтобы формально переформулировать такое отрицание (утверждение типа теоремы Рамсея в исходной формулировке выше) и доказать его, необходима более высокая косвенность, чем при индукции для простых экзистенциальных утверждений. А именно переформулировать проблему в терминах отрицания существования одного совместного порогового числа, зависящего от всех гипотетических $n_{c}$s, после чего функция все равно должна будет получить некоторое значение цвета. Более конкретно, сила требуемого ограничивающего принципа находится строго между схемой индукции в ${\mathsf {I\Sigma }}_{1}^{0}$ и ${\mathsf {I\Sigma }}_{2}^{0}$.Для свойств с точки зрения возвращаемых значений функций в конечных областях проверка методом грубой силы путем проверки всех возможных входных данных требует вычислительных затрат, которые больше для больших областей, но всегда конечны. Принятие индукционной схемы, как в ${\mathsf {I\Sigma }}_{2}^{0}$ подтверждает первый так называемый принцип бесконечной ячейки, который касается неограниченных областей и, следовательно, касается отображений с бесконечным количеством входных данных.

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

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

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

Обсуждались возможные принципы выбора, уже была принята ослабленная форма схемы разделения и больше стандартных ${\mathsf {ZFC}}$ аксиомы должны быть ослаблены для более предикативной и конструктивной теории. Первой из них является аксиома Powerset, принятая в виде пространства характеристических функций. Следующая аксиома ${\mathrm {Exp} }$ строго сильнее, чем его подвеска для конечных областей, обсуждавшихся выше:

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

В формулировке здесь снова используются удобные обозначения функциональных пространств, как обсуждалось выше. На словах аксиома гласит, что даны два множества $x,y$, класс $y^{x}$ всех функций, по сути, тоже множество.Это, безусловно, необходимо, например, для формализации карты объекта внутреннего hom-функтора типа ${\mathrm {hom} }({\mathbb {N} },-).$

Приняв такое утверждение о существовании, можно также определить количественную оценку. $\forall f$ над элементами определенных классов (всего) функций теперь распространяются только на множества. Рассмотрим набор пар $\langle a,b\rangle \in x\times x$ проверка отношения обособленности $\exists (f\in {\mathbb {N} }^{x}).f(a)\neq f(b)$. Через ограниченное разделение теперь это подмножество $x\times x$. Эти примеры показывают, что аксиома возведения в степень не только напрямую обогащает область множеств, но посредством разделения также позволяет получить еще больше множеств, что, кроме того, также усиливает другие аксиомы.

Примечательно, что эти ограниченные кванторы теперь распространяются на функциональные пространства, которые доказуемо неисчислимы и, следовательно, даже классически неисчислимы. Например, совокупность всех функций $f\colon \omega \to 2$ где $2:=SS0=\{0,1\}$, то есть набор $2^{\mathbb {N} }$ точек, лежащих в основе пространства Кантора , несчетно в силу диагонального аргумента Кантора и в лучшем случае может считаться подсчетным множеством. В этой теории теперь можно также количественно оценивать подпространства таких пространств, как $2^{\mathbb {N} }$, что является понятием третьего порядка натуральных чисел. (В этом разделе и далее используется символ полукольца натуральных чисел в таких выражениях, как $y^{\mathbb {N} }$ используется или пишется $\omega \to y$, просто чтобы избежать смешения кардинального- с порядковым возведением в степень.)Грубо говоря, классически несчетные множества, такие как, например, эти функциональные пространства, как правило, не имеют вычислимо разрешимого равенства.

Подняв общий профсоюз над $x$-индексированное семейство $\{y_{i}\}_{i}$, а также зависимый или индексированный продукт, написанный $\Pi _{i\in x}\,y_{i}$, теперь является набором. Для постоянного $y_{i}$, это снова сводится к функциональному пространству $y^{x}$.И принимая общее объединение над самими функциональными пространствами, всякий раз, когда класс мощности $x$ это набор, то также надмножество $\cup _{s\subset x}y^{s}$ из $y^{x}$ теперь является набором, дающим возможность говорить о пространстве частичных функций на $x$.

Союзы и счетность

С помощью возведения в степень теория доказывает существование любой примитивно-рекурсивной функции в $x\times \omega \to y$, и в частности в несчетных функциональных пространствах из $\omega$. Действительно, используя функциональные пространства и конечные ординалы фон Неймана в качестве областей, мы можем моделировать ${\mathsf {HA}}$ как обсуждалось, и, таким образом, кодируют порядковые номера в арифметике. Кроме того, можно получить степень порядковое число, возведенное в $\omega ^{\omega }$ как совокупность, которую можно охарактеризовать как $\cup _{n\in \omega }\omega ^{n}$, подсчитанный набор слов в бесконечном алфавите . Объединение всех конечных последовательностей на счетном множестве теперь является счетным множеством. Кроме того, для любого счетного семейства считающих функций вместе с их диапазонами теория доказывает, что объединение этих диапазонов счетно. Напротив, не предполагая счетного выбора, даже ${\mathsf {ZF}}$ согласовано с несчетным множеством ${\mathbb {R} }$ является объединением счетного множества счетных множеств.

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

Наконец, с возведением в степень любое конечно индексированное объединение семейства субконечно индексированных соотв. подсчетные множества сами по себе субконечно индексированы, соответственно. также счетно.Теория также доказывает совокупность всех счетных подмножеств любого множества. $x$ быть самим набором. Что касается этого подмножества класса мощности ${\mathcal {P}}_{x}$, некоторые вопросы естественной мощности также классически могут быть решены только с помощью выбора, по крайней мере, для несчетных чисел. $x$.

Класс всех подмножеств множества

Учитывая последовательность наборов, можно определить новые такие последовательности, например, в $\langle a,b\rangle \mapsto \langle \langle \rangle ,\langle a\rangle ,\langle b\rangle ,\langle a,b\rangle \rangle$. Но примечательно, что в рамках математической теории множеств совокупность всех подмножеств множества определяется не восходящим построением из его составляющих, а посредством понимания всех множеств в области дискурса. Стандартная автономная характеристика класса мощности набора. $x$ предполагает неограниченную универсальную количественную оценку, а именно $\forall u.\left(u\in {\mathcal {P}}_{x}\leftrightarrow u\subset x\right)$, где $\subset$ ранее было определено также в терминах предиката членства $\in$. Здесь утверждение, выраженное как $\forall (u\in {\mathcal {P}}_{x}).Q(x)$ априори следует принять за $\forall u.{\big (}u\subset x\to Q(x){\big )}$ и не эквивалентно ограниченному множеству высказыванию. Действительно, заявление $y={\mathcal {P}}_{x}$ сам по себе $\Pi _{1}$. Если ${\mathcal {P}}_{x}$ представляет собой набор, то определяющая количественная оценка даже варьируется в пределах ${\mathcal {P}}_{x}$, что делает аксиому powerset недопустимой .

Напомним, что член множества характеристических функций $2^{x}$ соответствует предикату, разрешимому на множестве $x$, что, таким образом, определяет отделяемое подмножество $s\subset x$. В свою очередь, класс ${\mathcal {D}}_{x}\subset {\mathcal {P}}_{x}$ всех отделяемых подмножеств $x$ теперь тоже в комплекте, через замену. Однако, ${\mathcal {D}}_{x}$ может не иметь желаемых свойств, например, быть замкнутым при бесконечных операциях, таких как объединения над счетными бесконечными наборами индексов: для счетной последовательности $u_{n}\in {\mathcal {D}}_{x}$, подмножество $U:=\cup _{k\in \omega }u_{k}$ из $x$ проверка $(a\in U)\leftrightarrow \exists (m\in \omega ).a\in u_{m}$ для всех $a\in x$ существует как набор. Но он может оказаться неотделимым и, следовательно, не обязательно сам по себе является доказуемо членом ${\mathcal {D}}_{x}$. Между тем, согласно классической логике, все подмножества множества $x$ являются тривиально отделяемыми, то есть ${\mathcal {D}}_{x}={\mathcal {P}}_{x}$ а потом ${\mathcal {D}}_{x}$ конечно, содержит любое подмножество. Кроме того, в классической логике это означает, что возведение в степень превращает класс мощности в набор.

Перевод результатов математических теорий, основанных на теории множеств, таких как топология множества точек или теория меры, в конструктивную структуру — это тонкая процедура взад и вперед. Например, в то время как ${\mathcal {D}}_{x}$ является полем множеств , для того чтобы оно образовало σ-алгебру по определению, также требуется упомянутая выше замкнутость относительно объединений. Но хотя область подмножеств может не проявлять конструктивного свойства замыкания, классическая мера $\mu$ является непрерывным снизу , и поэтому его значение в бесконечном объединении в любом случае может быть выражено без ссылки на этот набор как на вход функции, а именно как $\lim _{n\to \infty }$ растущей последовательности $\mu (\cup _{k\leq n}u_{k})$ значений функции в конечных объединениях.

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

Богатство полного степенного класса в теории без исключенного третьего лучше всего можно понять, рассматривая небольшие классически конечные множества. Для любого предложения $P$, рассмотрим подкласс $B:=\{x\in 1\mid P\}$ из $1$ (т.е. $\{0\}$ или $S0$). Это равно $B=0$ когда $P$ можно отклонить и оно равно $B=1$ (т.е. $B=S0$), когда $P$ можно доказать. Но $P$ может быть вообще неразрешимой. Рассмотрим три различных неразрешимых утверждения, ни одно из которых с доказанной точностью не подразумевает другое. Их можно использовать для определения трех подклассов синглтона. $1$, ни один из которых не является доказанно одинаковым. С этой точки зрения класс мощности ${\mathcal {P}}_{1}$ синглтона, обычно обозначаемого $\Omega$, называется истинностного значения алгеброй и не обязательно состоит только из двух элементов.

С возведением в степень, классом мощности синглтона, ${\mathcal {P}}_{1}$, будучи набором, уже подразумевает Powerset для наборов в целом. Доказательство проводится путем замены ассоциации $f\in {{\mathcal {P}}_{1}}^{x}$ к $\{z\in x\mid 0\in f(z)\}\in {\mathcal {P}}_{x}$и аргумент, почему охватываются все подмножества. Набор $2^{x}$ вводит в функциональное пространство ${{\mathcal {P}}_{1}}^{x}$ также.

Если теория подтвердится $B$ выше набора (например, ${\mathsf {IZF}}$ безусловно делает), то подмножество $b:=\{\langle 0,B\rangle \}$ из $1\times {\mathcal {P}}_{1}$ это функция $b\colon 1\to {\mathcal {P}}_{1}$ с ${\big (}b(0)=1{\big )}\leftrightarrow P$. Утверждать, что ${\mathcal {P}}_{1}=2$ состоит в том, чтобы утверждать, что исключенное среднее справедливо для $P$.

Было отмечено, что пустое множество $0$ и набор $1$ само по себе, конечно, представляет собой два подмножества $1$, значение $2\subset {\mathcal {P}}_{1}$. Также ли ${\mathcal {P}}_{1}\subset 2$ истинность теории зависит от простой дизъюнкции:

${\big (}\forall (x\in {\mathcal {P}}_{1}).(0\in x\lor 0\notin x){\big )}\to \,{\mathcal {P}}_{1}\subset 2$.

Итак, предполагая ${\mathrm {PEM} }$ для просто ограниченных формул предикативное разделение позволяет продемонстрировать, что степенной класс ${\mathcal {P}}_{1}$ это набор. Итак, в этом контексте полный выбор также подтверждает Powerset. (В контексте ${\mathsf {IZF}}$, ограниченное исключенное среднее фактически уже превращает теорию множеств в классическую, как обсуждается ниже.)

Полное разделение эквивалентно простому предположению, что каждый отдельный подкласс $1$ это набор. Если предположить полное разделение, то и полный выбор, и закономерность окажутся ${\mathrm {PEM} }$.

Предполагая ${\mathrm {PEM} }$ в этой теории индукция множества становится эквивалентной регулярности, а замена становится способной доказать полное разделение.

Обратите внимание, что кардинальные отношения, включающие несчетные множества, также неуловимы в ${\mathsf {ZFC}}$, где характеристика несчетности упрощается до $|\omega |<|x|$. Например, относительно несчетной степени $2^{|\omega |}$, от этой классической теории не зависит, все ли такие $x$ иметь $2^{|\omega |}\leq |x|$и это не доказывает, что $2^{|\omega |}<2^{|x|}$. См. гипотезу континуума и связанную с ней теорему Истона .

Понятия теории категорий и типов

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

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

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

Металогика

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

Представленная теория не доказывает функциональное пространство типа ${\mathbb {N} }^{\mathbb {N} }$ быть неисчислимым, в смысле инъекций из него. Без дальнейших аксиом интуиционистская математика имеет модели в виде рекурсивных функций, а также формы гипервычислений .

Анализ

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

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

Топология

Независимо от выбора модели, характерный оттенок конструктивной теории чисел можно объяснить с помощью независимого утверждения. $P$. Рассмотрим контрпример к конструктивной доказуемости упорядоченности натуральных чисел, но теперь встроенных в действительные числа. Сказать

$M:=\{x\in {\mathbb {R} }\mid (x=0\land P)\lor (x=1)\}$.

Минимальное метрическое расстояние между некоторой точкой и таким подмножеством, которое можно выразить как $\rho (0,M)$ например, может конструктивно не доказуемо существовать. В более общем смысле, это свойство локализации подмножеств определяет хорошо разработанную теорию конструктивного метрического пространства.

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

Последовательности Коши

Возведение в степень подразумевает принципы рекурсии и так далее. ${\mathsf {ECST}}+{\mathrm {Exp} }$, можно спокойно рассуждать о последовательностях $s\colon \omega \to {\mathbb {Q} }$, их свойства регулярности, такие как $|s_{n}-s_{m}|\leq {\tfrac {1}{n}}+{\tfrac {1}{m}}$, или о сокращении интервалов в $\omega \to ({\mathbb {Q} }\times {\mathbb {Q} })$. Это позволяет говорить о последовательностях Коши и их арифметике. Такой подход к анализу принят и в ${\mathsf {Z}}_{2}$.

Реалы Коши

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

Даже в сильной теории ${\mathsf {IZF}}$ с усиленной формой Коллекции действительные числа Коши ведут себя плохо, когда не принимают форму счетного выбора , и ${\mathrm {AC} _{\omega ,2}}$ достаточно для большинства результатов. Речь идет о полноте классов эквивалентности таких последовательностей, эквивалентности всего множества числам Дедекинда, существовании модуля сходимости для всех последовательностей Коши и сохранении такого модуля при переходе к пределам. Альтернативный подход, который немного лучше, состоит в том, чтобы объединить набор действительных чисел Коши с выбором модуля, то есть не только с действительными числами, но с набором пар или даже с фиксированным модулем, общим для всех действительных чисел.

На пути к реалам Дедекинда

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

${\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} }}\times {{\mathcal {P}}_{\mathbb {Q} }}$

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

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

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

Большинство школ конструктивного анализа подтверждают некоторый выбор, а также $\mathrm {BD}$- ${\mathbb {N} }$, как определено во втором разделе, посвященном границам чисел. Вот некоторые другие положения, используемые в теориях конструктивного анализа, которые невозможно доказать, используя только базовую интуиционистскую логику:

• Что касается рекурсивной математики («русская» или «марковская» конструктивная основа со многими сокращениями, например ${\mathsf {RUSS}}$), первый имеет принцип Маркова ${\mathrm {MP} }$, которое представляет собой форму доказательства от противного, мотивированную вычислимым поиском (неограниченная емкость памяти). Это оказывает заметное влияние на утверждения о реальных числах, о которых говорится ниже. В этой школе присутствует даже антиклассический конструктивный принцип Церкви. ${\mathrm {CT} }$, обычно принимаемый для теоретико-числовых функций. Тезисный принцип Чёрча, выраженный на языке теории множеств и сформулированный для функций множеств, постулирует, что все они соответствуют вычислимым программам, которые в конечном итоге останавливаются при любом аргументе. В теории вычислимости натуральные числа, соответствующие индексам кодов вычислимых функций, которые являются тотальными, равны $\Pi _{2}^{0}$ в арифметической иерархии , что означает, что принадлежность к любому индексу подтверждается проверкой $\forall x\,\exists y$ предложение. Это означает, что такой набор функций по-прежнему является просто подклассом натуральных чисел и поэтому, если рассматривать его по отношению к некоторым классическим функциональным пространствам, концептуально мал. В этом смысле принятие ${\mathrm {CT} }$ постулат делает $\omega \to \omega$ в «разреженное» множество, с точки зрения классической теории множеств. Счетность множеств можно постулировать и независимо.
• Итак, с другой стороны, со стороны брауэрианских интуиционистов ( ${\mathsf {INT}}$), существуют барная индукция , разрешимая теорема веера ${\mathrm {FAN} }_{\Delta }$ утверждая, что разрешимые полосы однородны, что является одним из самых слабых часто обсуждаемых принципов, схема Крипке (со счетным выбором, превращающим все подклассы $\omega$ счетный), или даже антиклассический принцип непрерывности Брауэра, определяющий возвращаемые значения того, что устанавливается функцией на бесконечных последовательностях уже через только конечные начальные сегменты.

Некоторые законы обеих этих школ противоречат друг другу. ${\mathrm {WLPO} }$, так что принятие всех принципов любой школы опровергает теоремы классического анализа. ${\mathrm {CT} }_{0}$ все еще соответствует некоторому выбору, но противоречит классической ${\mathrm {WKL} }$ и ${\mathrm {LLPO} }$, объяснено ниже. Независимость правила посылок от посылок существования множеств до конца не понята, но как принцип теории чисел она в некоторых концепциях противоречит аксиомам русской школы. Примечательно, ${\mathrm {CT} }_{0}$ также противоречит ${\mathrm {FAN} }_{\Delta }$То есть конструктивные школы также не могут быть полностью объединены. Некоторые принципы не могут быть конструктивно объединены до такой степени, что вместе они предполагают формы ${\mathrm {PEM} }$ - например ${\mathrm {MP} }$ плюс счетность всех подмножеств натуральных чисел. Эти комбинации, естественно, также не согласуются с дальнейшими антиклассическими принципами.

Неразложимость

Обозначим класс всех множеств через ${\mathcal {V}}$. Разрешимость принадлежности к классу $R$ может быть выражено как членство в $R\cup ({\mathcal {V}}\setminus R)$. Отметим также, что по определению два экстремальных класса ${\mathcal {V}}$ и $\{\}$ тривиально разрешимы. Членство в этих двух эквивалентно тривиальным утверждениям $x=x$ соотв. $\neg (x=x)$.

Позвонить в класс $R$ неразложимый или связный, если для любого предиката $\chi$,

${\big (}\forall (x\in R).\chi (x)\lor \neg \chi (x){\big )}\to {\Big (}{\big (}\forall (x\in R).\chi (x){\big )}\lor {\big (}\forall (x\in R).\neg \chi (x){\big )}{\Big )}$

Это означает, что единственные свойства, разрешимые на $R$ являются тривиальными свойствами. Это хорошо изучено в интуиционистском анализе.

Так называемая схема неразложимости. ${\mathrm {UZ} }$ (Unzerlegbarkeit) для теории множеств — это возможный принцип, который утверждает, что весь класс ${\mathcal {V}}$ является неразложимым. Говоря в более широком смысле, ${\mathrm {UZ} }$ постулирует, что два тривиальных класса — единственные классы, разрешимые относительно класса всех множеств. В качестве простого мотивирующего предиката рассмотрим членство $x\in 1$ в первом нетривиальном классе, то есть свойство $x=\{\}$ быть пустым. Это свойство нетривиально, поскольку оно разделяет некоторые множества: пустое множество является членом $1$по определению, хотя доказано, что множество множеств не являются членами $1$. Но, используя разделение, можно, конечно, также определить различные множества, для которых пустота вообще неразрешима в конструктивной теории, т.е. принадлежность к $1\cup ({\mathcal {V}}\setminus 1)$ доказуемо не для всех множеств. Таким образом, здесь свойство пустоты не разделяет заданную теоретическую область дискурса на две разрешимые части. Для любого такого нетривиального свойства противоположность ${\mathrm {UZ} }$ говорит, что оно не может быть разрешимо во всех множествах.

${\mathrm {UZ} }$ подразумевается принципом единообразия ${\mathrm {UP} }$, что соответствует ${\mathsf {CZF}}$ и обсуждается ниже.

Неконструктивные принципы

Конечно ${\mathrm {PEM} }$ и многие принципы, определяющие промежуточную логику , неконструктивны. ${\mathrm {PEM} }$ и ${\mathrm {WPEM} }$, что ${\mathrm {PEM} }$ для только что отрицаемых предложений можно представить как правила Де Моргана . Более конкретно, этот раздел будет посвящен утверждениям в терминах предикатов - особенно более слабым, выраженным в терминах нескольких кванторов над множествами поверх разрешимых предикатов над числами. Возвращаясь к разделу о характеристических функциях, можно назвать коллекцию $A$ доступен для поиска, если он доступен для поиска по всем его отделяемым подмножествам, что само по себе соответствует $\{0,1\}^{A}$. Это форма $\exists$- ${\mathrm {PEM} }$ для $A$. Обратите внимание, что в контексте возведения в степень такие предложения о множествах теперь привязаны к множествам.

Особую ценность при изучении конструктивного анализа представляют неконструктивные утверждения, обычно формулируемые в терминах совокупности всех бинарных последовательностей и характеристических функций. $f$ в арифметической области $A=\omega$ хорошо изучены. Здесь $f({\underline {\mathrm {n} }})=0$ является разрешимым предложением для каждой цифры ${\mathrm {n} }$, но, как было показано ранее, количественные утверждения с точки зрения $f$ может быть и нет. Как известно из теоремы о неполноте и ее вариаций, уже в арифметике первого порядка примерные функции на ${\mathbb {N} }$ можно охарактеризовать так, что если ${\mathsf {PA}}$ является последовательным, конкурирующим $\exists$- ${\mathrm {PEM} }$ каждый из дизъюнктов низкой сложности ${\mathsf {PA}}$- недоказуемый (даже если ${\mathsf {PA}}$ аксиоматически доказывает их дизъюнкция.)

В более общем плане арифметика $\exists$- ${\mathrm {PEM} }$Наиболее известное неконструктивное, по существу логическое утверждение носит название ограниченного принципа всеведения. ${\mathrm {LPO} }$. В конструктивной теории множеств ${\mathsf {CZF}}$ представленное ниже, это подразумевает ${\mathrm {BD} }$- ${\mathbb {N} }$, ${\mathrm {MP} }$, $\Pi _{1}^{0}$-версия теоремы веера, но и ${\mathrm {WKL} }$ обсуждается ниже. Вспомните примеры известных предложений, которые можно записать в $\Pi _{1}^{0}$-мода, то есть типа Гольдбаха: гипотеза Гольдбаха , последняя теорема Ферма , а также гипотеза Римана среди них . Предполагая релятивизированный зависимый выбор ${\mathrm {RDP} }$ и классический ${\mathrm {LPO} }$ над ${\mathsf {CZF}}$ не позволяет доказать более $\Pi _{0}^{2}$-заявления. ${\mathrm {LPO} }$ постулирует дизъюнктивное свойство, как и более слабое утверждение о разрешимости для постоянных функций ( $\Pi _{1}^{0}$-предложения) ${\mathrm {WLPO} }$, арифметика $\forall$- ${\mathrm {PEM} }$. Эти два связаны таким же образом, как и ${\mathrm {PEM} }$ против ${\mathrm {WPEM} }$ и они существенно отличаются ${\mathrm {MP} }$. ${\mathrm {WLPO} }$ в свою очередь подразумевает так называемую «меньшую» версию ${\mathrm {LLPO} }$. Это (арифметика) $\exists$-версия неконструктивного правила Де Моргана для отрицательного союза. Существуют, например, модели сильной теории множеств. ${\mathsf {IZF}}$ которые разделяют такие утверждения в том смысле, что они могут подтвердить достоверность ${\mathrm {LLPO} }$ но отвергнуть ${\mathrm {WLPO} }$.

Дизъюнктивные принципы о $\Pi _{1}^{0}$-предложения обычно намекают на эквивалентные формулировки, определяющие обособленность в анализе в контексте с мягким выбором или ${\mathrm {MP} }$. Претензия, высказанная ${\mathrm {LPO} }$ перевод в действительные числа эквивалентен утверждению, что равенство или раздельность любых двух действительных чисел разрешимы (фактически это решает трихотомию). В таком случае это также эквивалентно утверждению, что всякое реальное либо рационально, либо иррационально - без требования или построения свидетеля для любого дизъюнкта. Аналогичным образом, утверждение, высказанное ${\mathrm {LLPO} }$ для действительных чисел эквивалентно упорядочиванию $\leq$ любых двух вещественных чисел разрешима (дихотомия). Тогда это также эквивалентно утверждению, что если произведение двух действительных чисел равно нулю, то любое из вещественных чисел равно нулю - опять же без свидетеля. Действительно, каждая формулировка трех принципов всеведения в таком случае эквивалентна теоремам обособленности, равенства или порядка двух вещественных чисел. Еще больше можно сказать о последовательностях Коши, дополненных модулем сходимости.

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

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

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

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

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

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

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

Индукция

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

Было замечено, что на общепринятом языке принципы индукции можно прочитать $\mathrm {Ind} _{A}\to \omega \subset A$, с предшествующим $\mathrm {Ind} _{A}$ определяется, как указано выше, и с $\omega \subset A$ значение $\forall (n\in \omega ).n\in A$ где набор $\omega$ всегда обозначает стандартную модель натуральных чисел. Благодаря сильной аксиоме Бесконечности и предикативному Разделению справедливость индукции для ограниченных множеством или $\Delta _{0}$-определения уже установлены и тщательно обсуждены. Для тех предикатов, включающих только кванторы над $\omega$, это подтверждает индукцию в смысле теории арифметики первого порядка. В контексте теории множеств, где $\omega$ является множеством, этот принцип индукции можно использовать для доказательства предикативно определенных подклассов $\omega$ быть набором $\omega$ сам. Так называемая схема полной математической индукции теперь постулирует равенство множеств $\omega$ всем . его индуктивным подклассам Как и в классической теории, это подразумевается и при переходе к непредикативной схеме полного разделения. Как указано в разделе «Выбор», подобные принципы индукции также подразумеваются различными формами принципов выбора.

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

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

Формулы предикатов, используемые в схеме, следует понимать как формулы теории множеств первого порядка. Ноль $0$ обозначает множество $\{\}$ как указано выше, и набор $Sn$ обозначает последующий набор $n\in \omega$, с $n\in Sn$. Согласно Аксиоме Бесконечности, приведенной выше, он снова является членом $\omega$. Помните, что в отличие от арифметической теории, натуральные числа здесь являются не абстрактными элементами в области дискурса, а элементами модели. Как было отмечено в предыдущих обсуждениях, при принятии ${\mathsf {ECST}}$, даже для всех предикативно определенных множеств равенство такому конечному ординалу фон Неймана не обязательно разрешимо.

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

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

Схема аксиом индукции множества : для любого предиката $\phi$, ${\Big (}\forall x.\,{\big (}\forall (y\in x).\ \phi (y){\big )}\to \phi (x){\Big )}\to \forall z.\phi (z)$

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

В ${\mathsf {ECST}}$, аксиома доказывает индукцию в транзитивных множествах и, в частности, также для транзитивных множеств транзитивных множеств. Последнее тогда является адекватным определением ординалов и даже $\Delta _{0}$-формулировка. Индукция множеств, в свою очередь, обеспечивает порядковую арифметику в этом смысле. Кроме того, он позволяет определять функции класса с помощью трансфинитной рекурсии . Изучение различных принципов, которые дают определения множеств посредством индукции, то есть индуктивных определений, является основной темой в контексте конструктивной теории множеств и ее сравнительно слабых сторон . Это справедливо и для их аналогов в теории типов. Замена не требуется для доказательства индукции по множеству натуральных чисел из индукции множеств, но эта аксиома необходима для их арифметики, моделируемой в рамках теории множеств.

Аксиома регулярности — это единственное утверждение с квантором универсальности над множествами, а не схема. Как показано, это подразумевает ${\mathrm {PEM} }$, и поэтому неконструктивно. Теперь о $\phi$ считается отрицанием некоторого предиката $\neg S$ и писать $\Sigma$ для класса $\{y\mid S(y)\}$, индукция читает

$\forall (x\in \Sigma ).\neg (x\cap \Sigma =\{\})\,\,\leftrightarrow \,\,\Sigma =\{\}$

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

Металогика

Сформулированную выше теорию можно выразить как ${\mathsf {CZF}}$ с его набором аксиом, отброшенных в пользу более слабых аксиом замены и возведения в степень. Это доказывает, что действительные числа Коши являются множеством, а не классом действительных чисел Дедекинда.

Сам ординал назовем трихотомическим, если иррефлексивное отношение принадлежности $\in$«среди своих членов является трихотомическим . Как и аксиома регулярности, индукция множеств ограничивает возможные модели» $\in$Но конструктивная теория здесь не доказывает трихотомию для всех ординалов, в то время как трихотомические ординалы не очень хорошо ведут себя по отношению к понятию преемника и классифицировать.

Дополнительная сила теории доказательств, достигаемая с помощью индукции в конструктивном контексте, значительна, даже если отказаться от регулярности в контексте ${\mathsf {ZF}}$ не снижает теоретическую силу доказательства.Даже без возведения в степень настоящая теория с индукцией множеств имеет ту же теоретическую силу доказательства, что и ${\mathsf {CZF}}$ и доказывает рекурсивность тех же функций. с точки зрения теории доказательств В частности, его большой счетный ординал - это ординал Бахмана – Ховарда . Это также ординал классической или интуиционистской теории множеств Крипке – Платека .Это согласуется даже с ${\mathsf {IZF}}$ предположить, что класс трихотомических ординалов образует множество. Современная теория, дополненная этим постулатом существования порядкового множества, доказывает непротиворечивость ${\mathsf {CZF}}$.

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

Отношение к ZF

Теория также представляет собой изложение теории множеств Цермело – Френкеля. ${\mathsf {ZF}}$ в том смысле, что присутствуют варианты всех его восьми аксиом. Экстенсиональность, Спаривание, Союз и Замена действительно идентичны. Разделение принимается в слабой предикативной форме, тогда как Бесконечность утверждается в сильной формулировке. Как и в классической формулировке, эта аксиома разделения и существование любого множества уже доказывают аксиому пустого множества. Возведение в степень для конечных областей и полная математическая индукция также подразумеваются их более сильными принятыми вариантами. Без принципа исключенного третьего теория в своей классической форме лишена полного разделения, набора сил, а также регулярности. Принятие ${\mathrm {PEM} }$ теперь точно ведет к классической теории.

Ниже представлены различные прочтения формальной теории. Позволять $\mathrm {CH}$ обозначают гипотезу континуума и $B:=\{z\in 1\mid \mathrm {CH} \}$ так что $0\in B\leftrightarrow \mathrm {CH}$. Затем $b:=B\cup \{1\}$ населён $1$ и любое множество, которое установлено как член $b$ либо равно $0$ или $1$. Индукция включена $\omega$ подразумевает, что нельзя последовательно отрицать, что $b$ имеет некоторый член с наименьшим натуральным числом. Можно показать, что значение такого члена не зависит от таких теорий, как ${\mathsf {ZFC}}$. Тем не менее, любая классическая теория множеств, такая как ${\mathsf {ZFC}}$ также доказывает, существует что такое число .

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

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

Итак, во-первых, можно поразмышлять о силе аксиомы замены , в том числе и в контексте классической теории множеств. Для любого набора $y$ и любые натуральные $n$, существует произведение $y^{n}$ рекурсивно заданный $y^{n-1}\times y$, которые имеют все более глубокий ранг . Индукция несвязанных предикатов доказывает, что эти множества существуют для всех бесконечно многих натуральных чисел. Замена "на $n\mapsto y^{n}$«Более того, теперь утверждается, что этот бесконечный класс продуктов можно превратить в бесконечное множество, $\{p\mid \exists (n\in \omega ).p=y^{n}\}$. Это также не является подмножеством какого-либо ранее установленного набора.

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

Схема аксиом сильной коллекции: для любого предиката. $\phi$, $\forall a.\ \ {\Big (}\forall (x\in a).\exists y.\phi (x,y){\Big )}\to \exists b.{\Big (}\forall (x\in a).\exists (y\in b).\phi (x,y)\ \land \ \forall (y\in b).\exists (x\in a).\phi (x,y){\Big )}$

Другими словами, для каждого тотального отношения существует набор образов. $b$ так что отношение является полным в обоих направлениях. Выражение этого через необработанную формулировку первого порядка приводит к несколько повторяющемуся формату. Антецедент утверждает, что рассматривается отношение $\phi$ между сетами $x$ и $y$ которые являются общими для определенного набора доменов $a$, то есть, $\phi$ имеет хотя бы одно «значение изображения» $y$ для каждого элемента $x$ в домене. Это более общее явление, чем условие обитания. $x\in y$ в наборе аксиом теоретического выбора, но также более общем, чем условие Замены, которое требует уникального существования $\exists !y$. В консеквенте, во-первых, аксиомы утверждают, что тогда существует множество $b$ который содержит хотя бы одно значение «изображения» $y$ под $\phi$, для каждого элемента домена. Во-вторых, в этой формулировке аксиомы, кроме того, утверждается, что только такие образы $y$ являются элементами этого нового набора кодоменов $b$. Это гарантия того, что $b$ не выходит за пределы кодомена $\phi$ и, таким образом, аксиома также выражает некоторую силу, подобную процедуре разделения. Этот принцип можно использовать при конструктивном исследовании больших множеств, выходящих за рамки повседневной необходимости анализа.

Металогика

Эта теория без ${\mathrm {PEM} }$, без неограниченного разделения и без «наивного» силового множества, обладает различными приятными свойствами. Например, в отличие от ${\mathsf {CZF}}$ со схемой коллекции подмножеств, представленной ниже, он имеет свойство существования .

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

Бинарное уточнение

Так называемая аксиома бинарного уточнения гласит, что для любого $a$ существует набор ${\mathcal {B}}_{a}\subset {\mathcal {P}}_{a}$ такая, что для любого покрытия $a=x\cup y$, набор ${\mathcal {B}}_{a}$ содержит два подмножества $c\subset x$ и $d\subset y$ которые также выполняют эту работу по прикрытию, $a=c\cup d$. Это самая слабая форма аксиомы набора степеней, лежащая в основе некоторых важных математических доказательств.Полнота ниже для отношений между множеством $a$ и конечное $\{0,1\}$, подразумевает, что это действительно возможно.

Сделав еще шаг назад, ${\mathsf {ECST}}$ Плюс рекурсия и плюс двоичное уточнение уже доказывают, что существует архимедово, дедекиндово полное псевдоупорядоченное поле. Эта теория множеств также доказывает, что класс левых дедекиндовых разрезов является множеством, не требующим индукции или сбора. Более того, это доказывает, что функциональные пространства, разбитые на дискретные множества, являются множествами (там, например, $\omega \to \omega$), не предполагая ${\mathrm {Exp} }$. Уже над слабой теорией ${\mathsf {BCST}}$ (то есть без бесконечности) доказывает ли бинарное уточнение, что функциональные пространства, разбитые на дискретные множества, являются множествами и, следовательно, например, существование всех характеристических функциональных пространств $\{0,1\}^{a}$.

Коллекция подмножеств

Теория, известная как ${\mathsf {CZF}}$ принимает аксиомы предыдущих разделов плюс более сильную форму возведения в степень. Это происходит путем принятия следующей альтернативы возведению в степень, которую снова можно рассматривать как конструктивную версию аксиомы набора степеней :

Схема аксиом коллекции подмножеств: для любого предиката. $\phi$, $\forall a.\forall b.\ \ \exists u.\forall z.{\big (}\forall (x\in a).\exists (y\in b).\phi (x,y,z){\big )}\to \exists (v\in u).{\big (}\forall (x\in a).\exists (y\in v).\phi (x,y,z)\;\land \;\forall (y\in v).\exists (x\in a).\phi (x,y,z){\big )}$

Альтернатива, не являющаяся схемой, подробно описана ниже.

Полнота

Для данного $a$ и $b$, позволять ${\mathcal {R}}_{ab}$ быть классом всех полных отношений между $a$ и $b$. Этот класс задается как

$r\in {\mathcal {R}}_{ab}\leftrightarrow {\Big (}{\big (}\forall (x\in a).\exists (y\in b).\langle x,y\rangle \in r{\big )}\,\land \,{\big (}\forall (p\in r).\exists (x\in a).\exists (y\in b).p=\langle x,y\rangle {\big )}{\Big )}$

В отличие от определения функции, в ней нет уникального квантора существования. $\exists !(y\in b)$. Класс ${\mathcal {R}}_{ab}$ представляет собой пространство «неоднозначных функций» или « многозначных функций » из $a$ к $b$, а как набор отдельных пар с правой проекцией в $b$. Во втором пункте говорится, что речь идет только об этих отношениях, а не о тех, которые тотальны по отношению к другим. $a$ но и расширить свою сферу деятельности за пределы $a$.

Никто не постулирует ${\mathcal {R}}_{ab}$ быть множеством, поскольку при Замене можно использовать эту совокупность отношений между множеством $a$ и конечное $b=\{0,1\}$, то есть «двузначные функции на $a$", чтобы извлечь набор ${\mathcal {P}}_{a}$ всех его подмножеств. Другими словами ${\mathcal {R}}_{ab}$ быть набором означало бы аксиому Powerset.

Над ${\mathsf {ECTS}}+{\text{Strong Collection}}$, существует единственная, несколько более ясная альтернативная аксиома схеме коллекции подмножеств . Он постулирует существование достаточно большого множества ${\mathcal {S}}_{ab}$ совокупных отношений между $a$ и $b$.

Аксиома полноты: $\forall a.\forall b.\ \exists {\mathcal {S}}_{ab}.\,({\mathcal {S}}_{ab}\subset {\mathcal {R}}_{ab})\,\land \,\forall (r\in {\mathcal {R}}_{ab}).\exists (s\in {\mathcal {S}}_{ab}).s\subset r$

Это говорит о том, что для любых двух множеств $a$ и $b$, существует набор ${\mathcal {S}}_{ab}\subset {\mathcal {R}}_{ab}$ которое среди своих членов находится в еще тотальном отношении $s\in {\mathcal {S}}_{ab}$ для любого данного полного отношения $r\in {\mathcal {R}}_{ab}$.

На заданном домене $a$, функции представляют собой в точности самые разреженные полные отношения, а именно однозначнозначные. Следовательно, из аксиомы следует, что существует множество, в котором находятся все функции. Таким образом, Полнота подразумевает Возведение в степень. Это далее подразумевает бинарное уточнение, уже более ${\mathsf {BCST}}$.

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

Металогика CZF

${\mathsf {CZF}}$ обладает свойством числового существования и свойством дизъюнктивности , но есть уступки: ${\mathsf {CZF}}$ отсутствует свойство существования из-за схемы коллекции подмножеств или аксиомы полноты. Схема также может быть препятствием для моделей реализуемости. Свойство существования присутствует, когда вместо него принимается более слабое возведение в степень или более сильная, но непредикативная аксиома Powerset. Последнее вообще лишено конструктивной интерпретации.

Недоказуемые утверждения

Теория согласуется с некоторыми антиклассическими утверждениями, но сама по себе не доказывает ничего, что не было бы доказуемо. ${\mathsf {ZF}}$. Некоторые известные утверждения, не подтвержденные ни теорией (ни ${\mathsf {IZF}}$, если уж на то пошло) являются частью принципов, перечисленных выше, в разделах о конструктивных школах анализа, о конструкции Коши и о неконструктивных принципах. Нижеследующее касается установленных теоретических концепций:

Ограниченное понятие транзитивного множества транзитивных множеств — хороший способ определения ординалов и возможность индукции по ординалам. Но примечательно, что это определение включает в себя некоторые $\Delta _{0}$-подмножества в ${\mathsf {CZF}}$. Итак, если предположить, что членство $0$ разрешимо во всех последующих ординалах $S\alpha$ доказывает ${\mathrm {PEM} }$ для ограниченных формул в ${\mathsf {CZF}}$. Кроме того, в этой теории невозможно вывести ни линейность ординалов . , ни существование степенных множеств конечных множеств, поскольку предположение любого из них подразумевает степенное множество То обстоятельство, что ординалы ведут себя лучше в классическом, чем в конструктивном контексте, проявляется в различных постулатах теории существования больших множеств.

Рассмотрим функции, областью определения которых является $\omega$ или некоторые $n\in \omega$. Это последовательности, а их диапазоны представляют собой наборы. Обозначим через $C$ класс, характеризуемый как наименьший кодомен, такой, что диапазоны вышеупомянутых функций в $C$ также сами являются членами $C$. В ${\mathsf {ZF}}$, это набор $H_{\aleph _{1}}$ и наследственно счетных множеств имеет порядковый ранг не более $\omega _{2}$. В ${\mathsf {ZF}}$, он несчетен (так как содержит также все счетные ординалы, мощность которых обозначается $\aleph _{1}$), но его мощность не обязательно равна мощности ${\mathbb {R} }$. Тем временем, ${\mathsf {CZF}}$ не доказывает $C$ даже представляет собой множество, даже если счетный выбор предполагается .

Наконец, теория не доказывает, что все функциональные пространства образованы из множеств в конструируемой вселенной. $L$ установлены внутри $L$, и это справедливо даже при использовании Powerset вместо более слабой аксиомы возведения в степень. Итак, это конкретное утверждение, предотвращающее ${\mathsf {CZF}}$ от доказательства класса $L$ быть образцом ${\mathsf {CZF}}$.

Порядковый анализ

принимая ${\mathsf {CZF}}$ и отказ от индукции множеств дает теорию, консервативную по ${\mathsf {HA}}$ для арифметических утверждений в том смысле, что он доказывает одни и те же арифметические утверждения для своих ${\mathsf {HA}}$-модель $\omega$. Добавление только математической индукции дает теорию с теоретико-доказательным порядковым номером. $\varphi (\varepsilon _{0},0)$, которая является первой общей неподвижной точкой функций Веблена $\varphi _{\beta }$ для $\beta <\varepsilon _{0}$. Это тот же порядковый номер, что и для ${\mathsf {ML_{1}}}$ и находится ниже ординала Фефермана – Шютте. $\Gamma _{0}$.Демонстрируя типовую теоретическую модель, полную теорию ${\mathsf {CZF}}$ выходит за рамки $\Gamma _{0}$, его порядковый номер по-прежнему остается скромным порядковым номером Бахмана – Говарда.Если предположить, что класс трихотомических ординалов представляет собой множество, это повышает теоретическую силу доказательства ${\mathsf {CZF}}$ (но не из ${\mathsf {IZF}}$).

Будучи связанной с индуктивными определениями или барной индукцией , аксиома регулярного расширения ${\mathrm {REA} }$ повышает теоретическую силу доказательства ${\mathsf {CZF}}$. Эта аксиома большого множества, допускающая существование определенных хороших надмножеств для каждого множества, доказывается ${\mathsf {ZFC}}$.

Модели

Категория множеств и функций ${\mathsf {CZF}}+{\mathrm {REA} }$ это $\Pi W$-претопос. Не углубляясь в теорию топоса , некоторые расширили такие $\Pi W$-претопы содержат модели ${\mathsf {CZF}}+{\mathrm {REA} }$. Эффективный топос содержит модель этого ${\mathsf {CZF}}+{\mathrm {REA} }$ на основе карт, характеризующихся некоторыми хорошими свойствами счетности.

Разделение, излишне сформулированное в классическом контексте, конструктивно не подразумевается Заменой. До сих пор дискуссия сводилась только к предикативно оправданному ограниченному разделению. Обратите внимание, что полное разделение (вместе с ${\mathrm {RDC} }$, ${\mathrm {MP} }$ а также ${\mathrm {IP} }$ для множеств) подтверждается в некоторых эффективных топосных моделях, а это означает, что аксиома не портит краеугольные камни школы ограничительной рекурсии.

С этим связаны теоретические интерпретации типов.В 1977 году Аксель показал, что ${\mathsf {CZF}}$ все еще можно интерпретировать в теории типов Мартина-Лёфа , используя подход «предложения как типы» . Более конкретно, здесь используется одна вселенная и $W$-типы, обеспечивающие то, что сейчас рассматривается как стандартная модель ${\mathsf {CZF}}$ в ${\mathsf {ML_{1}V}}$. Это делается через образы ее функций и имеет достаточно прямое конструктивное и предикативное обоснование, сохраняя при этом язык теории множеств. Грубо говоря, есть два «больших» типа. $U,V$, все наборы даются через любые $f\colon A\to V$ на некоторых $A\colon U$и членство в $x$ в наборе определено, что оно выполняется, когда $\exists (a\colon A).f(a)=x$.Наоборот, ${\mathsf {CZF}}$ интерпретирует ${\mathsf {ML_{1}V}}$.Все утверждения, подтвержденные в счетной модели теории множеств, могут быть точно доказаны с помощью ${\mathsf {CZF}}$ плюс принцип выбора $\Pi \Sigma$- $\mathrm {AC}$, указано далее выше.Как уже отмечалось, такие теории, как ${\mathsf {CZF}}$, а также вместе с выбором обладают свойством существования для широкого класса множеств в общей математике.Теории типа Мартина-Лёфа с дополнительными принципами индукции подтверждают соответствующие аксиомы теории множеств.

корректности и полноте Теоремы о ${\mathsf {CZF}}$, относительно реализуемости , установлены.

Разрыв с ZF

Можно, конечно, добавить тезис Чёрча.

Можно постулировать счетность всех множеств. Это уже справедливо для теоретико-типовой интерпретации и модели эффективного топоса. По бесконечности и возведению в степень, $\omega \to \omega$ является несчетным множеством, а класс ${\mathcal {P}}_{\omega }$ или даже ${\mathcal {P}}_{1}$ тогда доказано, что это не множество, согласно диагональному аргументу Кантора . Таким образом, эта теория затем логически отвергает Powerset и, конечно же, ${\mathrm {PEM} }$.Счетность также противоречит различным аксиомам больших множеств . (С другой стороны, также используя ${\mathsf {CZF}}$, некоторые такие аксиомы предполагают непротиворечивость таких теорий, как ${\mathsf {ZF}}$ и сильнее.)

По правилу вывода ${\mathsf {CZF}}$ замкнуто согласно общему единообразию Трульстры для обоих $z=\omega$ и $z=\{0,1\}$. Ее можно принять как антиклассическую схему аксиом, принцип единообразия, который можно обозначить как ${\mathrm {UP} }$,

$\forall z.{\big (}\forall x.\exists (y\in z).\phi (x,y){\big )}\to \exists (y\in z).\forall x.\phi (x,y)$

Это также несовместимо с аксиомой powerset. Этот принцип также часто формулируется для $z=\omega$. Теперь о двоичном наборе меток $z=\{0,1\}$, ${\mathrm {UP} }$ подразумевает схему неразложимости ${\mathrm {UZ} }$, как было отмечено.

В 1989 году Ингрид Линдстрём показала, что необоснованные множества также можно интерпретировать в теории типов Мартина-Лёфа, которые получаются заменой индукции множеств в ${\mathsf {CZF}}$ с антифундаментальной аксиомой Акселя . Полученная теория ${\mathsf {CZFA}}$ можно изучить, также добавив обратно $\omega$-индукционная схема или релятивизированный зависимый выбор , а также утверждение, что каждое множество является членом транзитивного множества .

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

Теория ${\mathsf {IZF}}$ является ${\mathsf {CZF}}$ приняв как стандартное разделение, так и набор мощности , и, как в ${\mathsf {ZF}}$, можно условно сформулировать теорию с помощью Сборника ниже. Как таковой, ${\mathsf {IZF}}$ можно рассматривать как самый простой вариант ${\mathsf {ZF}}$ без ПЕМ .Итак, как было отмечено, в ${\mathsf {IZF}}$, вместо замены можно использовать

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

В то время как аксиома замены требует, чтобы отношение φ было функциональным на множестве z (например, каждому x в z соответствует ровно один y ), аксиома коллекции этого не делает.Он просто требует, чтобы был связан хотя бы один y , и утверждает существование набора, который собирает по крайней мере один такой y для каждого такого x .В классическом ${\mathsf {ZFC}}$Схема Коллекции подразумевает схему Аксиомы замены . При использовании Powerset (и только тогда) можно показать, что они классически эквивалентны.

Пока ${\mathsf {IZF}}$ основана на интуиционистской, а не классической логике, она считается импредикативной .Он позволяет формировать множества с помощью операции над набором степеней и использовать общую аксиому разделения с любыми предложениями, включая те, которые содержат кванторы неограниченные . Таким образом, новые множества могут быть сформированы в терминах вселенной всех множеств, дистанцируя теорию от конструктивной перспективы снизу вверх. Таким образом, еще проще определить множества $\{x\in B\mid Q(x)\}$ с неразрешимым членством, а именно за счет использования неразрешимых предикатов, определенных на множестве.Аксиома набора степеней далее подразумевает существование набора значений истинности . При наличии исключенного третьего это множество имеет два элемента. При его отсутствии набор истинностных значений также считается непредикативным. Аксиомы ${\mathsf {IZF}}$ достаточно сильны, так что полный PEM уже подразумевается PEM для ограниченных формул. См. также предыдущее обсуждение в разделе, посвященном аксиоме возведения в степень. И при обсуждении Разделения это, таким образом, уже подразумевается конкретной формулой $\forall x.{\big (}0\in x\lor 0\notin x{\big )}$принцип, согласно которому знание о членстве в $0$ всегда должна быть разрешима, независимо от набора.

Металогика

Как подразумевалось выше, свойство подсчетности не может быть принято для всех множеств, если теория доказывает ${\mathcal {P}}_{\omega }$ быть набором.Теория обладает многими замечательными свойствами числового существования и, например, согласуется с тезисом Чёрча, а также с $\omega \to \omega$ будучи счетным. Он также обладает дизъюнктивным свойством.

${\mathsf {IZF}}$ с заменой вместо коллекции обладает общим свойством существования, даже если вдобавок ко всему принимается релятивизированный зависимый выбор. Но просто ${\mathsf {IZF}}$ в формулировке нет. Совмещение схем, включая полное разделение, портит его.

Даже без PEM доказательства теоретическая сила ${\mathsf {IZF}}$ равен значению ${\mathsf {ZF}}$. И ${\mathsf {HA}}$ доказывает их эквисовместимость, и они доказывают одно и то же $\Pi _{1}^{0}$-предложения.

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

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

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

Упомянем еще одну очень слабую теорию, которая была исследована, а именно интуиционистскую (или конструктивную) теорию множеств Крипке–Платека. ${\mathsf {IKP}}$.Он имеет не только разделение, но и сбор, ограниченный $\Delta _{0}$-формулы, т.е. аналогично ${\mathsf {BCST}}$ но с Индукцией вместо полной замены. Теория не вписывается в иерархию, представленную выше, просто потому, что она имеет схему аксиом индукции множеств с самого начала . Это позволяет использовать теоремы, включающие класс ординалов. Теория обладает свойством дизъюнкции.Конечно, более слабые версии ${\mathsf {IKP}}$ получаются путем ограничения схемы индукции более узкими классами формул, скажем $\Sigma _{1}$. Теория особенно слаба, если изучать ее без Бесконечности.

Сортированные теории

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

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

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

И еще:

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

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

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

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

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

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

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

Теории категорий

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

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

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

См. также

• Схема аксиом предикативного разделения
• Конструктивная математика
• Конструктивный анализ
• Правило и принцип тезиса Конструктивной Церкви
• Вычислимое множество
• Теорема Диаконеску
• Свойства дизъюнкции и существования
• Эпсилон-индукция
• Наследственно конечное множество
• Хейтинговая арифметика
• Непредикативность
• Интуиционистская теория типов
• Закон исключенного третьего
• Порядковый анализ
• Теория множеств
• Субсчетность

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

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

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

• Кросилла, Лаура (13 февраля 2019 г.). «Теория множеств: конструктивный и интуиционистский ZF» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• Ван ден Берг, Бенно (7 сентября 2012 г.). «Конструктивная теория множеств – обзор» (PDF) . Слайды из Heyting dag, Амстердам