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

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

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

Введение [ править ]

Outlook [ править ]

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

На моделях [ править ]

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

Обзор [ править ]

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

Подтеории ZF [ править ]

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

Обозначение [ править ]

Ниже мы используем греческий язык как переменную-предикат в схемах аксиом и используем или для определенных предикатов.${\ displaystyle \ phi}$${\ displaystyle P}$${\ displaystyle Q}$

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

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

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

Общие аксиомы [ править ]

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

Обозначим утверждением, что два класса имеют точно такие же элементы, т. Е. Или эквивалентно . ${\displaystyle A\simeq B}$${\displaystyle \forall z.(z\in A\iff z\in B)}$${\displaystyle (A\subset B)\land (B\subset A)}$

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

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

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

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

и

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

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

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

BCST [ править ]

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

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

также называется ограниченным разделением, т. е. разделением только для ограниченных кванторов. Это равносильно постулированию существования набора, полученного пересечением любого набора и любого предикативно описанного класса . Когда предикат берется как для доказано, что множество, получается двоичное пересечение множеств и записи . Ограничение в аксиоме - это также непредикативные определения. Например, без аксиомы набора мощности не следует ожидать, что класс, определенный как набор, где обозначает некоторый двузначный предикат. Обратите внимание: если этот подкласс доказуемо является набором, то термин${\displaystyle s}$${\displaystyle y}$${\displaystyle \{x\mid \phi (x)\}}$${\displaystyle x\in z}$${\displaystyle z}$${\displaystyle s=y\cap z}$${\displaystyle s}$${\displaystyle \{x\in y\mid \forall (t\in {\mathcal {P}}y).Q(x,t)\}}$${\displaystyle Q}$${\displaystyle s}$определенное таким образом, также входит в объем терминологической переменной, используемой для его определения.${\displaystyle t}$

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

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

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

Далее мы рассматриваем

где означает единственное существование. Он предоставляет существование в виде наборов ряда функционально-подобных предикатов, полученных через их домены.${\displaystyle \exists !}$

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

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

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

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

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

Функции [ править ]

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

${\displaystyle \forall (a\in A).\exists !(c\in C).P(a,c)}$

может быть настроен в терминах программ в представленных областях и, возможно, должен быть свидетелем утверждения (в смысле, неформально говоря , где обозначает ценность программы, как упомянуто, но это затрагивает вопросы теории реализуемости ). Теперь в текущем обсуждении мы хотим говорить о полной функциональной связи, когда доказуемо${\displaystyle \forall (a\in A).P(a,c_{a})}$${\displaystyle c_{a}}$${\displaystyle f\subset A\times C}$

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

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

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

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

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

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

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

ECST [ править ]

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

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

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

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

${\displaystyle \exists w.\forall m.{\Big (}m\in w\iff {\big (}m=0\lor (\exists n\in w).\forall k.(k\in m\iff k\in n\lor k=n){\big )}{\Big )}}$

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

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

Выбор [ править ]

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

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

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

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

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

Тем не менее, здесь полная аксиома выбора, допускающая существование отображения на различимые элементы (равенство на кодобласти разрешимо), подразумевает это . Таким образом, утверждение о существовании общих функций выбора с неконструктивно. Чтобы лучше понять это явление, обратите внимание на такие последствия, как . Таким образом, Аксиома разделения связывает предикаты для установления равенства и, в свою очередь, с информацией о функциях. Разница между дискретной областью натуральных чисел и областью состоит в том, что о последней априори мало что известно. У нас есть и вне зависимости от того . Но в случае с расширением существует только одна возможная функция, входящая в функцию выбора выбора.${\displaystyle f\colon \{x,y\}\to \{0,1\}}$ ${\displaystyle P\lor \neg P}$${\displaystyle f(z)\in z}$${\displaystyle P\implies x=y}$${\displaystyle \{x,y\}}$${\displaystyle 0\in x}$${\displaystyle 1\in y}$${\displaystyle P}$${\displaystyle x=y}$${\displaystyle f}$, поэтому при рассмотрении функционального назначения безоговорочное объявление не будет согласованным.${\displaystyle f(x)=0}$${\displaystyle f(y)=1}$

Арифметика [ править ]

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

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

${\displaystyle y^{\{0,1,\dots ,n\}}}$

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

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

Возведение в степень [ править ]

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

Теперь рассмотрим аксиому :${\displaystyle {\mathrm {Exp} }}$

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

Для любой формулы класс равен, когда можно отклонить, а когда можно доказать, но также может быть и вовсе не разрешимым. С этой точки зрения класс мощности одноэлементного элемента , т. Е. Или неформально и обычно обозначаемый как , называется алгеброй истинностного значения. Предполагая, что все формулы разрешимы, т. Е. Предполагая , что можно показать не только то, что является набором, но более конкретно, что это этот набор из двух элементов. В предположении ограниченных формул Separation позволяет продемонстрировать, что любой powerclass является набором. В качестве альтернативы полный набор мощности эквивалентен простому предположению, что класс всех подмножеств${\displaystyle \phi }$${\displaystyle \{x\mid (x=0)\land \phi \}}$${\displaystyle 0}$${\displaystyle \phi }$${\displaystyle 1}$${\displaystyle \phi }$${\displaystyle \phi }$${\displaystyle \{0\}}$${\displaystyle {\mathcal {P}}1}$${\displaystyle \{0,\dots ,1\}}$${\displaystyle \Omega }$${\displaystyle {\mathrm {LEM} }}$${\displaystyle \Omega }$${\displaystyle {\mathrm {LEM} }}$${\displaystyle 1}$образует набор. Полное разделение эквивалентно предположению, что каждый подкласс является набором.${\displaystyle 1}$

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

Навстречу реальностям [ править ]

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

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

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

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

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

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

Индукция [ править ]

Математическая индукция [ править ]

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

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

Аксиома индукции подразумевается полной схемой разделения. Можно увидеть, что это связано с тем, что индукция приводит к заключению о классе .${\displaystyle \{n\in \omega \mid \phi (n)\}}$

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

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

Установить индукцию [ править ]

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

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

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

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

Metalogic [ править ]

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

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

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

Сильная коллекция [ править ]

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

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

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

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

Metalogic [ править ]

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

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

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

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

${\displaystyle r\in a\Sigma {b}\iff {\big (}\forall (x\in a).\exists (y\in b).\langle x,y\rangle \in r{\big )}\,\land \,{\big (}\forall (p\in r).\exists (x\in a).\exists (y\in b).p=\langle x,y\rangle {\big )}}$

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

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

${\displaystyle \forall a.\forall b.\ \ \exists (c\subseteq a\Sigma {b}).\forall (r\in a\Sigma {b}).\exists (s\in c).s\subseteq r}$

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

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

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

Metalogic [ править ]

Эта теория не обладает свойством существования из - за схемы, но в 1977 году Ацель показал , что все еще может быть интерпретировано в теории типа Мартин-LOF , ^[4] ( с помощью предложения-как-типы подход) при условии , что в настоящее время рассматривается стандартная модель в теории типов. ^[5] Это делается в терминах образов его функций, а также достаточно прямого конструктивного и предикативного обоснования, сохраняя при этом язык теории множеств. Таким образом, имеет скромную теоретическую силу доказательства, см . : ординал Бахмана – Ховарда .${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$ I K P {\displaystyle {\mathsf {IKP}}}

Разрыв с ZF [ править ]

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

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

Интуиционистский Цермело – Френкель [ править ]

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

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

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

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

Metalogic [ править ]

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

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

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

История [ править ]

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

Интуиционистский Z [ править ]

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

Интуиционистский КП [ править ]

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

Сортированные теории [ править ]

Конструктивная теория множеств [ править ]

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

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

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

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

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

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

Категории теорий [ править ]

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

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

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

См. Также [ править ]

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

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

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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