Теория на множествата: Конструктивна и интуиционистична ZF

Съдържание:

Теория на множествата: Конструктивна и интуиционистична ZF
Теория на множествата: Конструктивна и интуиционистична ZF

Видео: Теория на множествата: Конструктивна и интуиционистична ZF

Видео: Теория на множествата: Конструктивна и интуиционистична ZF
Видео: Теория множеств. Что такое множество 2024, Март
Anonim

Навигация за влизане

  • Съдържание за участие
  • библиография
  • Академични инструменти
  • Friends PDF Preview
  • Информация за автора и цитирането
  • Върнете се в началото

Теория на множествата: Конструктивна и интуиционистична ZF

Публикувана за първи път пет февруари 2009 г.; съществена ревизия сря 13 февруари 2019 г.

Конструктивни и интуиционистични теории за множествата на Цермело-Френкел са аксиоматични теории за множества в стила на теорията за множествата на Zermelo-Fraenkel (ZF), които се основават на интуиционистичната логика. Те са въведени през 70-те години на миналия век и представляват формален контекст, в който да се кодифицира математиката, базирана на интуиционистичната логика (виж вписването за конструктивната математика). Те са формулирани на стандартния език от първи ред на теорията на множествата на Zermelo-Fraenkel и не използват пряко използваните по своята същност конструктивни идеи. Работейки в конструктивен и интуиционистичен ZF, можем по някакъв начин да разчитаме на познанието си с ZF и неговата евристика.

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

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

  • 1. Същността на конструктивната и интуиционистична теория на множествата

    • 1.1 Аксиоматична свобода
    • 1.2 Конструктивна срещу интуиционистична теория на множествата
    • 1.3 Предсказуемост в теорията на конструктивните множества

      • 1.3.1. Непреодолимост на разделянето
      • 1.3.2 Непреодолимост на Powerset
      • 1.3.3 Конструктивната вселена на множествата
  • 2. Произход на конструктивните и интуиционистични теории на множествата
  • 3. Axioms Systems CZF и IZF
  • 4. Принципи на конструктивен избор
  • 5. Теория на доказване и семантика на конструктивното и интуиционистичното ZF

    • 5.1 Доказателно-теоретична сила
    • 5.2 Големи комплекти в конструктивен и интуиционистичен ZF
    • 5.3 Метаматематични свойства на конструктивни и интуиционистични ZF и семантични техники

      • 5.3.1 Свойства на дизъюнкцията и съществуването на конструктивния и интуиционистичния ZF
      • 5.3.2 Реализируемост
      • 5.3.3 Крипке модели и семантика с стойност на Хейтинг
      • 5.3.4 Категорични модели на конструктивна и интуиционистка теория на множествата
      • 5.4 Варианти на конструктивни и интуиционистични теории от множества: Теории на множествата с уременции и неекстензионни теории от множества
  • библиография
  • Академични инструменти
  • Други интернет ресурси
  • Свързани записи

1. Същността на конструктивната и интуиционистична теория на множествата

Конструктивни и интуиционистични теории на множеството Цермело-Френкел се основават на интуиционистична, а не на класическа логика и представляват естествена среда, в която да се кодифицира и изучава математика, базирана на интуиционистичната логика. За конструктивната ZF основният акцент е бил да представя математическата практика на Bishop (Bishop 1967, Bishop and Bridges 1985).

За основните понятия и движещите идеи на интуиционистичната логика, конструктивната математика и интуиционизма читателят може да пожелае да се консултира със следните записи:

  • интуиционистка логика,
  • развитието на интуиционистичната логика,
  • конструктивна математика,
  • интуиционизъм във философията на математиката,
  • Луицен Егбертус Ян Брауер.

За класическата теория на множествата вижте записа в теорията на множествата.

Конструктивната и интуиционистичната ZF се основават на същия език от първи ред като класическата теория на множествата на ZF, който има само бинарен предикат символ (in) (членство) като нелогичен символ. Тоест, те са формулирани въз основа на интуиционистичната логика от първи ред с равенство плюс двоичния символ на предикат (в). По този начин можем да се възползваме от простотата на теоретично зададения език и от нашето запознаване с него (Myhill 1975). Както и в конструктивната математика в стил Бишоп, Конструктивната и интуиционистичната ZF са съвместими с класическата традиция, в смисъл, че всички техни теореми са класически верни. Всъщност двете официални системи, които ще разгледаме, Конструктивна Цермело-Френкел (CZF) и Интуиционистична Цермело-Френкел (IZF),пораждат пълен класически ZF чрез простото добавяне на принципа на изключената средна.

1.1 Аксиоматична свобода

Класическата теория на множествата Zermelo-Fraenkel се основава на класическата предикатна логика от първи ред с равенство. На върха на логическите принципи са аксиоми и схеми, които описват понятието за зададена теория, кодифицираща. Тези принципи могат да бъдат класифицирани в три вида. Първо, има принципи, които ни позволяват да формираме нови набори от дадените. Например, аксиомата на двойката ни позволява да формираме набор, който е двойката от две дадени множества. Второ, има принципи, които установяват свойства на зададената теоретична структура. Например, аксиомата на разширяването идентифицира всички множества, които имат едни и същи елементи. Трето, и накрая, съществуват аксиоми, които твърдят съществуването на конкретни множества. Така аксиомата на безкрайността гласи, че има безкрайно множество. Всички тези принципи обикновено се наричат теоретично зададени принципи.

При въвеждането на версии на ZF, базирани на интуиционистична логика, първата стъпка е да се премахне от логиката принципа на изключената средна (EM). Следващата стъпка е да се избере добър запас от теоретично зададени принципи, които вярно представляват желаната представа за конструктивно множество. Тези задачи се оказват по-трудни, отколкото може да се очаква в началото. Всъщност, както е добре известно, системите, базирани на „по-слаба“логика, имат способността да разграничават изявления, които са еквивалентни от гледна точка на „по-силна“логика. В случай на теория на множествата някои от аксиомите или схемите на ZF често се представят от една от многото класически еквивалентни формулировки. Класически е само въпрос на удобство кой да се използва в определено време. Когато работите на базата на интуиционистичната логика обаче,различни формулировки на класическа аксиома могат да се окажат различни (нееквивалентни). Всъщност може да се предвидят нови изявления, които са класически еквивалентни на аксиома ZF, но интуиционистично отделени от нея (например аксиомата за събиране на подмножество на CZF (Aczel 1978)).

Що се отнася до първата стъпка, която се състои в премахване на принципа на изключване на средата от логиката, се оказва, че просто изгонването на този принцип от основната логика е недостатъчно; това означава, че не е достатъчно да вземем за своя основа интуиционистичното, а не класическото предикатно смятане. Трябва също така да гарантираме, че зададените теоретични аксиоми не внасят в нашата теория нежелани форми на изключена среда. Например, както отбелязва Myhill (1973), имаме нужда от допълнителни грижи при избора на подходящо изложение за аксиомата на основата. Фондацията се въвежда в теорията на множествата, за да се изключат множества, които са членове на себе си и по този начин (в) - вериги от множества. Обичайната формулировка на основата твърди, че всеки обитаем набор (набор с поне един елемент) има най-малко елемент по отношение на членското отношение. Това твърдение обачеможе да се покаже, че дава конструктивно неприемливи случаи на изключена среда въз основа на скромни теоретични предположения. Следователно обичайната формулировка на основата трябва да бъде пропусната от теорията на множествата, базирана на интуиционистичната логика. За доказателство вижте допълнителния документ:

Задачи-теоретични принципи, несъвместими с интуиционистичната логика.

Типичният ход при формулирането на теории от множества, базирани на интуиционистична логика, е след това да се замени основата с класически еквивалентната схема на зададена индукция, която няма същите „странични ефекти“, но има сходни последици. [1]

Що се отнася до втората стъпка, свързана с подбора на добър запас от теоретично зададени принципи, схемите за подмяна и разделяне и аксиомата на силата на множеството привличат най-голямо внимание. За точната формулировка на тези принципи вижте допълнителния документ:

Аксиоми на CZF и IZF.

Тук по-долу е типичен сценарий. Като се има предвид това, което са класически два варианта на един теоретичен набор от принципи, тяхното класическо доказателство за еквивалентност изисква в определен момент инстанция на изключената средна. Но като цяло това доказателство за еквивалентност няма да се пренесе в интуиционистичен контекст и следователно това, което са класически две форми на един принцип, може да доведе до два различни принципа, когато се работи интуиционистично. Следователно изборът на единия, а не на другия може да повлияе на понятието за набор, което така дефинираме. В контекста на теории за конструктивни множества като CZF, мощност и разделяне се заменят от интуиционистично по-слаби принципи. Една от причините за това е, че пълната сила на мощността и пълното разделяне се разглеждат като ненужни,тъй като по-слабите им заместители изглежда са достатъчни за провеждането на конструктивна математика. Друга причина е, че те се разглеждат като философски проблематични, тъй като те могат да въведат форми на непредсказуемост в теорията на множествата (вижте раздела за предсказуемостта в теорията на конструктивните множества). Случаят със замяна срещу събиране е някак по-сложен (виж например статиите (Friedman and Scedrov 1985), (Rathjen 2005) и (Rathjen 2012)). Струва си да се подчертае, че докато възприемането на обичайната формулировка на фондацията противоречи на самото предположение за интуиционистичната логика като основна логика, принципите на раздяла и мощност нямат никаква несъвместимост с интуиционистичната логика, дотолкова, че те са неразделна част от интуиционистка теория на множествата IZF (Friedman 1973a). Друга причина е, че те се разглеждат като философски проблематични, тъй като те могат да въведат форми на непредсказуемост в теорията на множествата (вижте раздела за предсказуемостта в теорията на конструктивните множества). Случаят със замяна срещу събиране е някак по-сложен (виж например статиите (Friedman and Scedrov 1985), (Rathjen 2005) и (Rathjen 2012)). Струва си да се подчертае, че докато възприемането на обичайната формулировка на фондацията противоречи на самото предположение за интуиционистичната логика като основна логика, принципите на раздяла и мощност нямат никаква несъвместимост с интуиционистичната логика, дотолкова, че те са неразделна част от интуиционистка теория на множествата IZF (Friedman 1973a). Друга причина е, че те се разглеждат като философски проблематични, тъй като те могат да въведат форми на непредсказуемост в теорията на множествата (вижте раздела за предсказуемостта в теорията на конструктивните множества). Случаят със замяна срещу събиране е някак по-сложен (виж например статиите (Friedman and Scedrov 1985), (Rathjen 2005) и (Rathjen 2012)). Струва си да се подчертае, че докато възприемането на обичайната формулировка на фондацията противоречи на самото предположение за интуиционистичната логика като основна логика, принципите на раздяла и мощност нямат никаква несъвместимост с интуиционистичната логика, дотолкова, че те са неразделна част от интуиционистка теория на множествата IZF (Friedman 1973a).тъй като те могат да въведат форми на непредсказуемост в теорията на множествата (виж раздела за предсказуемостта в конструктивната теория на множествата). Случаят със замяна срещу събиране е някак по-сложен (виж например статиите (Friedman and Scedrov 1985), (Rathjen 2005) и (Rathjen 2012)). Струва си да се подчертае, че докато възприемането на обичайната формулировка на фондацията противоречи на самото предположение за интуиционистичната логика като основна логика, принципите на раздяла и силата нямат никаква несъвместимост с интуиционистичната логика, дотолкова, че те са неразделна част от интуиционистка теория на множествата IZF (Friedman 1973a).тъй като те могат да въведат форми на непредсказуемост в теорията на множествата (виж раздела за предсказуемостта в конструктивната теория на множествата). Случаят със замяна срещу събиране е някак по-сложен (виж например статиите (Friedman and Scedrov 1985), (Rathjen 2005) и (Rathjen 2012)). Струва си да се подчертае, че докато възприемането на обичайната формулировка на фондацията противоречи на самото предположение за интуиционистичната логика като основна логика, принципите на раздяла и силата нямат никаква несъвместимост с интуиционистичната логика, дотолкова, че те са неразделна част от интуиционистка теория на множествата IZF (Friedman 1973a). Струва си да се подчертае, че докато възприемането на обичайната формулировка на фондацията противоречи на самото предположение за интуиционистичната логика като основна логика, принципите на раздяла и силата нямат никаква несъвместимост с интуиционистичната логика, дотолкова, че те са неразделна част от интуиционистка теория на множествата IZF (Friedman 1973a). Струва си да се подчертае, че докато възприемането на обичайната формулировка на фондацията противоречи на самото предположение за интуиционистичната логика като основна логика, принципите на раздяла и силата нямат никаква несъвместимост с интуиционистичната логика, дотолкова, че те са неразделна част от интуиционистка теория на множествата IZF (Friedman 1973a).

В обобщение, при формулирането на теория на множествата, базирана на интуиционистичната логика, първата задача е да се изгони принципът на изключената средна част, включително онези нейни случаи, които могат да бъдат скрити в познати формулировки на теоретично зададени аксиоми. Следващата задача е да изберете една версия на всеки класически принцип, която най-добре характеризира желаната представа за набор. Това отваря редица възможности за избор, тъй като множество интуиционистични принципи могат да съответстват на един класически принцип. Трябва да се подчертае, че от конструктивна гледна точка това множество от опции (и по този начин системи), а не причинява безпокойство, е изключително желана ситуация, тъй като представлява форма на „аксиоматична свобода“. Например, тя ни позволява да разграничаваме редица математически понятия, като по този начин по-добре улавяме интуициите си за тях като отделни. Освен това ни дава свобода да избираме понятията и теориите, които най-добре отговарят на даден контекст. В допълнение, чрез възприемане на интуиционистичната логика ние можем да включим в нашите теории принципи, които са класически много силни, без да се налага да се ангажират с класическата си сила. Например, човек може да добави понятие за недостъпно множество към слаба теория на конструктивните множества и да получи теория за предикативност, докато същата концепция, вградена в класически контекст, става изключително силна (вижте разделите „Предсказуемост в теорията на конструктивните множества“и „Големите множества в конструктивната“и интуиционистичен ZF). И накрая, естествено възниква богата област на (мета-теоретично) изследване на отношенията между произтичащите различни теоретично зададени системи. Както можеше да се очаква, тази свобода също има цена,като високо техническо проучване на аксиоматичните теории може да е необходимо, за да се разграничат техните принципи, както и да се разкрият някои от техните тънкости. Това отново може да се разглежда като предимство, тъй като ни принуждава към по-задълбочен и ясен анализ на включените математически понятия и ни подтиква да разработим нови сложни инструменти.

1.2 Конструктивна срещу интуиционистична теория на множествата

Въпреки че има много системи от групи, базирани на интуиционистична логика, можем да различим две основни тенденции в литературата. Според първия, ние приемаме всичко, което е налично в класическата теория на множествата ZF, и модифицираме само онези принципи, като фундамент, които имат явна несъвместимост с интуиционистичната логика. Това поражда зададени теории като интуиционистичен Zermelo-Fraenkel, IZF, вариант на който е въведен още през (Friedman 1973a). (Виж Beeson 1985, глави 8 и 9 и Scedrov 1985 за две проучвания на IZF.) Основанието на тези теории изглежда е да се даде на математика възможно най-мощните инструменти, стига да се запази съвместимостта с интуиционистичната логика. Според втория подход,в допълнение към придържането към интуиционистичната логика, ние въвеждаме и ограничения върху приетите теоретично зададени принципи, доколкото получената система отговаря на конструктивната математическа практика. Теории от този втори вид могат да се разглеждат като резултат от двоен процес на ограничение по отношение на класическия ZF. Първо има ограничение на интуиционистката логика, след това се налага ограничение на разрешените теоретично зададени конструкции. Последното е мотивирано от (1) наблюдението, че по-слабите принципи изглеждат достатъчни за конструктивната математическа практика и (2) желанието да се придържат към форма на предикативност (вж. Следващия раздел за изясняване на това понятие за предикативност). Парадигматични примери за последния вид системи са теорията за конструктивните множества на Myhill (Myhill 1975),Система B на Фридман (Friedman 1977) и Конструктивна теория на множествата Zermelo-Fraenkel на Aczel CZF (Aczel 1978; 1982; 1986; Aczel & Rathjen 2001; Aczel & Rathjen 2010, Други интернет ресурси). Можем също да кажем, че при този втори подход основополагащата мотивация влияе на практиката в по-висока степен.

По-нататък ние използваме конвенция, която често се прилага днес, според която прилагателното „интуиционистично“се отнася до онези теории за множеството, като IZF, които са непредсказуеми, а „конструктивни“се отнася до теории на множеството, като CZF, които отговарят на форма на предикативност. Имайте предвид обаче, че тази конвенция не винаги се спазва в литературата. Всъщност прилагателното „конструктивно“също се използва за обозначаване на непредсказуеми теории, а „интуиционистично“за обозначаване на предикативни основополагащи теории като теорията на типа Мартин-Льоф (Martin-Löf 1975; 1984). Също така си струва да се отбележи, че настоящата конвенция за използването на думите „конструктивен“и „интуиционистичен“се различава от тази, направена в контекста на конструктивната математика (виж например вписването за конструктивна математика, а също и „Бриджис и Ричман 1987“),

1.3 Предсказуемост в теорията на конструктивните множества

Предикативизмът има своето начало в съчиненията на Поанкаре и Ръсел, които реагират на парадоксите, открити в теориите на Кантор и Фреге в началото на 20 век. Впоследствие Уейл прави фундаментален принос за изучаването на предикативната математика (Weyl 1918, вж. Също Feferman 1988). Според едно понятие определението е непредсказуемо, ако дефинира обект чрез позоваване на цялост, която включва обекта, който трябва да бъде дефиниран. Със своя принцип на порочния кръг (VCP), Ръсел възнамерява да премахне кръговото в математиката, което произтича от такива непредсказуеми определения. Ръсел даде различни формулировки на VCP, една от които е:

Това, което съдържа видима променлива, не трябва да бъде възможна стойност на тази променлива (Russell 1908, в Van Heijenoort 1967, 163).

Основополагащият анализ на предикативността на Поанкаре, Ръсел и Уейл проправи пътя за различни логически анализи на понятието. Най-често приетият анализ се дължи на Feferman и Schütte (независимо), следващи линии, посочени от Kreisel (Kreisel 1958, Feferman 1964 и Schütte 1965; 1965a). Тук теорията на доказването е играла основна роля. В много груб смисъл идеята беше да се обособи колекция от теории (трансфинитна прогресия на системи от разклонена аритметика от втори ред, индексирана с наредби), чрез която да се характеризира определено понятие за предсказателна порядъчна. Теоретичният анализ на Feferman и Schütte на тези теории е идентифицирал един порядък, който обикновено се нарича (Gamma_0), което е най-малкото непредсказуемо разпореждане според тази представа. Една формална система се счита за предсказуемо оправдана, ако е теоретично сведена до система от разклонен артрит от втори ред, индексирана с порядък по-малък от (Gamma_0). Следователно в теорията на доказателствата (Gamma_0) обикновено се счита за представляваща границата на предикативността. (Вижте Feferman 2005 за по-точна неформална информация за това понятие за предикативност и за по-нататъшни справки. Вижте също Crosilla 2017. Читателят може също да се консултира с раздела за предикативизма във философията на математиката и статията за парадоксите и съвременната логика),(Вижте Feferman 2005 за по-точна неформална информация за това понятие за предикативност и за по-нататъшни справки. Вижте също Crosilla 2017. Читателят може също да се консултира с раздела за предикативизма във философията на математиката и статията за парадоксите и съвременната логика),(Вижте Feferman 2005 за по-точна неформална информация за това понятие за предикативност и за по-нататъшни справки. Вижте също Crosilla 2017. Читателят може също да се консултира с раздела за предикативизма във философията на математиката и статията за парадоксите и съвременната логика),

За конструктивни основополагащи теории е предложен по-„либерален“подход към предикативизма, като се започне от работата в Лоренцен, Михил и Ванг в края на 50-те години (вж. Например Lorenzen и Myhill 1959). Основната идея е, че т. Нар. Индуктивни дефиниции трябва да бъдат разрешени в сферата на конструктивната математика. Интуитивната обосновка на индуктивните дефиниции е свързана с факта, че те могат да бъдат изразени с помощта на ограничени правила по начин „отдолу нагоре“. Доказателствената сила на теориите на индуктивните дефиниции надхвърля границата на Феферман и Шют (Buchholz, Feferman, Pohlers и Sieg 1981). Така сравнително силните теории се смятат за предикативни в днешните основи на конструктивната математика. Тази по-либерална представа за предикативност често се нарича генерализирана предикативност. В този запис просто пишем предикативност за обобщена предикативност и наричаме предикативност, като се имат предвид естествените числа по-известната форма на предикативност, която възниква в класическия контекст и е анализирана от Kreisel, Feferman и Schütte.

Пример за предикативна теория в този смисъл е конструктивната теория на множествата CZF, тъй като нейната доказателствено-теоретична сила е същата като тази на теория на една индуктивна дефиниция, известна като ID (_ 1). Вместо това системата IZF е непредсказуема, тъй като нейната доказателствено-теоретична сила се равнява на тази на целия класически ZF (Friedman 1973a).

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

1.3.1. Непреодолимост на разделянето

Схемата на разделяне ни позволява да формираме подмножество от даден набор, чиито елементи удовлетворяват дадено свойство (изразено с формула на езика на теорията на множествата). Като се има предвид набор (B) и формула (phi (X)), разделянето ни позволява да изградим нов набор, множеството от онези елементи (X) на (B), за които (phi) важи. Това обикновено е неофициално представено като: ({X / в B: / phi (X) }). Разделянето може да доведе до непредсказуемост, в случай че формулата (phi) съдържа неограничени квантори, разположени в цялата вселена от множества; в действителност, при определянето на новия набор чрез разделяне можем да се позовем на този много набор, противоречащ на VCP на Ръсел. Например, ако определим набор (C) чрез разделяне като ({X / в B: / forall Y / psi (X, Y) }), тогава (C) е сред (Y), които трябва да бъдат проверени за свойството (psi). Тази форма на непредсказуемост се избягва в теорията на конструктивните множества чрез ограничаване на схемата за разделяне: чрез изискване всички квантори, които се срещат във формула (phi), да бъдат обхванати само за „предварително конструирани“множества. Синтактично това означава, че при зададен набор (B), можем да образуваме нов набор ({X / в B: / phi (X) }) чрез разделяне само ако всички количествени характеристики в (phi) са ограничени; тоест, само ако всички количествени характеристики в (phi) са във формата (forall X (X / в Y / rightarrow / ldots)) или (съществува X (X / в Y / клин / ldots)), за някакъв набор (Y).\ phi (X) }) чрез разделяне, само ако всички количествени характеристики в (phi) са ограничени; тоест, само ако всички количествени характеристики в (phi) са във формата (forall X (X / в Y / rightarrow / ldots)) или (съществува X (X / в Y / клин / ldots)), за някакъв набор (Y).\ phi (X) }) чрез разделяне, само ако всички количествени характеристики в (phi) са ограничени; тоест, само ако всички количествени характеристики в (phi) са във формата (forall X (X / в Y / rightarrow / ldots)) или (съществува X (X / в Y / клин / ldots)), за някакъв набор (Y).

Можем да видим, че ограничаването на разделянето по този начин избягва непредсказуемостта, като наблюдаваме, че доказаната теоретична сила на CZF, която има само ограничено разделяне, е в границите на предикативността. Въпреки това, чрез добавяне на пълно разделяне към CZF човек получава непредсказуема теория, всъщност такава със същата доказателствено-теоретична сила като пълната аритметика от втори ред (Lubarsky 2006). Вижте също раздел 5 за обсъждане на ролята на теорията на доказването при анализа на конструктивните и интуиционистичните теории на множествата.

1.3.2 Непреодолимост на Powerset

Аксиомата за набор от мощност ни позволява да формираме набор от всички подмножества на даден набор. Пример за непредсказуемо използване на множеството мощност е дадено от дефиницията на подмножество от естествените числа, (N), както следва: (B: = {n / в N: / forall C / subseteq N / phi (n, C) }), където (phi) може да се приеме като ограничена формула. Форма на циркулярност възниква тук, тъй като самият (B) е сред подмножествата на (N), които трябва да бъдат проверени за (phi). Както е подчертано от Myhill (1975, 354), наборът на мощност е трудно да се обоснове от конструктивна гледна точка: той събира всички подмножества на даден набор, но не предписва правило, което "конструира" набора от предварително даден набори, както изглежда прогнозирането.

Myhill пише:

Наборът на мощност изглежда особено неконструктивен и непредсказуем в сравнение с другите аксиоми: той не включва, както правят другите, комбиниране или разделяне на множества, които единият вече е изградил, а по-скоро избиране от съвкупността на всички множества тези, които стоят във връзката на включване в даден набор. (Myhill 1975, 351).

Наборът на мощност изглежда особено проблематичен в случай на безкрайни множества, тъй като ние нямаме представа какво е произволен подмножество на безкраен набор; няма начин да ги генерираме всички и така нямаме начин да формираме множеството от всички тях “(Myhill 1975, 354). В резултат на това изглежда няма начин да се даде конструктивен смисъл на множеството на всички подмножества на безкраен набор.

Майхил категорично отбелязва, че наборът на мощност не е необходим за конструктивна математика в стил Бишоп, тъй като може да бъде заменен с едно от последствията от него. Това често се нарича аксиома на експозицията на Михил и гласи, че можем да формираме набор от всички функции от един зададен набор в друг. Тази аксиома е ясно еквивалентна на мощност, зададена в класически контекст, където подмножествата на даден набор могат да бъдат представени от характерни функции. При липсата на принципа на изключена среда обаче, силовата настройка и експоненцията не са равностойни. Основното наблюдение на Майхил е, че експонирането е достатъчно, за да се изпълни математиката на (Бишоп 1967); например, тя позволява изграждането на (Коши) реални числа в рамките на конструктивната теория на множествата. Майхил твърди, че експоненцията е конструктивно смислена, защото функцията е правило,краен обект, който действително може да бъде даден.

Той също така пише, че случаят на зададена сила е различен от този на експоненцията като:

дори в случай на безкрайни множества (A) и (B) имаме представа за произволно картографиране от (A) в (B). Произволно картографиране от (mathbf {Z}) в (mathbf {Z}) е частична рекурсивна функция, заедно с доказателство, че изчислението винаги се прекратява; подобна сметка може да се даде на произволна реална функция. Няма съответно обяснение на „произволно подмножество“. (Myhill 1975, 354).

Аксиомата на експозицията на Михил вече е част от всички основни системи на теорията на конструктивните множества. В случай на CZF, всъщност човек има засилване на експоненцията, известно като събиране на подмножества, което също е отслабване на зададената мощност. Обобщение на експоненцията може да се намери и в теорията на конструктивния тип.

В случая на CZF твърдението, че добавянето на аксиома на зададената мощност предизвиква форма на непредсказуемост, може да бъде обосновано с технически резултат. Rathjen (2012b) показва, че CZF, увеличен от аксиомата на множеството на мощността, надвишава силата на класическата теория на множествата Zermelo и по този начин добавянето на аксиомата на мощност към CZF ни води до напълно непредсказуема теория. Това показва също, че въздействието от мощност, зададена към събирането на подмножество, не може да бъде обърнато, тъй като доказателствената теоретична сила на CZF е далеч под тази на теорията на множеството на Zermleo. С други думи, аксиомата на зададената мощност е много по-силна от експоненцията и събирането на подмножества.

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

След като въведохме подходящи ограничения за установяване на мощност и разделяне, сега можем да се изправим пред съществено възражение. Конструктивните и интуиционистични теории от множества могат да се разглеждат като модификации на класическата теория на множествата на ZF, които се получават чрез: (1) заместване на класическото с интуиционистичната логика и (2) прецизно избиране между различни класически еквивалентни принципи тези, които изглеждат по-подходящи за дадени цели, Например, можем да изберем принципи, които са достатъчни, за да представят определена математическа практика, като например математиката в стил Бишоп. Получената представа за множеството обаче може да стане неясна и изборът на теоретично настроените принципи може да изглежда до известна степен като произволен. В случай на интуиционистичен ZF, човек може да обоснове избора на теоретично настроените принципи, като разгледа неговите семантични интерпретации, т.е.като Хейтинг семантика или като погледнем категоричните му модели. В случай на конструктивна теория на множествата, за да възпрепятства този вид възражение, Aczel е дал интерпретация на CZF във версия на теорията на типа Мартин-Льоф (Aczel 1978). Твърдението е, че по този начин на понятието CZF за зададено ядро се придава ясно конструктивно значение, като се разгледа неговото значение в теорията на типа Мартин-Льоф, тъй като последната обикновено се счита за представляваща точна и напълно мотивирана формулировка на конструктивно понятие за множеството. Тълкуването на CZF на Aczel в теорията на конструктивния тип е дадено чрез интерпретиране на множества като дървета в теорията на типа. Тоест, в теорията на конструктивния тип вселената от множества от CZF е представена от тип V от итеративни множества, изградени над Вселената, U, от малки типове (Aczel 1978; Martin-Löf 1984). Тази интерпретация ясно подчертава (обобщената) предикативност на CZF, чиито множества могат да се разглеждат като дървета, изградени индуктивно, и чиято теоретично настроена вселена също има ясна индуктивна структура.

Предсказуемостта на CZF и свързаните с нея системи е в съответствие с философски позиции, които често са свързани с използването на интуиционистична логика. По-специално, изглежда, че ако конструираме математическите обекти, например, ако математическите обекти са ментални конструкции от някакъв вид, тогава прибягването до непредсказуеми определения би довело до нежелана форма на кръгообразност. Това ясно контрастира с гледна точка, често свързана с класическата теория на множествата, за която нашата математическа дейност може да се разглежда като постепенно разкриване на свойствата на вселената на множествата, чието съществуване е независимо от нас. Такъв възглед обикновено е обвързан с използването на класическата логика и непредсказуемостта при изучаване на теоретично настроената вселена. Предсказуемостта също често се разглежда като свързана с разчитаното във времето разграничение между действителната и потенциалната безкрайност. Предикативните (и по-специално конструктивните) теории често се разглеждат като избягване на позоваване на действителната безкрайност и ангажиране само с потенциална безкрайност (Dummett 2000, Fletcher 2007). Това отново изглежда особено в хармония с онези философски позиции, които подчертават човешкото измерение на нашата математическа дейност, виждайки например математическите обекти и истинността на твърденията за тях като зависими от нас. Друг свързан аспект често се разглежда като отнасящ се до предикативността: ако вселената на множествата е изградена на етапи от нашата собствена математическа дейност, тогава би било естествено и да го разглеждаме като отворен край. Поради тази причина в конструктивен контекст,където отхвърлянето на класическата логика отговаря на изискването за предикативност, Вселената на множествата често се описва като отворена концепция, вселена „в огън“. Тази идея е особено добре изразена в теорията на конструктивния тип, където понятието за теоретично тип на Вселената е умишлено оставено отворено от Пер Мартин-Льоф (като не се поставят конкретни правила за елиминиране за нея). Отворената природа на вселената на множествата проправи пътя за разширяването й чрез принципите на размисъл. Те са изследвани както в теорията на типа, така и в конструктивната теория на множествата. Вижте (Rathjen 2005a) за изследване на резултатите и основополагаща дискусия, а също и раздел 5.2. За официален анализ на конструктивната вселена на множествата и сравнение с йерархията на Фон Нойман вижте (Ziegler 2014). Вселената на множествата често се описва като отворена концепция, вселена „в огън“. Тази идея е особено добре изразена в теорията на конструктивния тип, където понятието за теоретично тип на Вселената е умишлено оставено отворено от Пер Мартин-Льоф (като не се поставят конкретни правила за елиминиране за нея). Отворената природа на вселената на множествата проправи пътя за разширяването й чрез принципите на размисъл. Те са изследвани както в теорията на типа, така и в конструктивната теория на множествата. Вижте (Rathjen 2005a) за изследване на резултатите и основополагаща дискусия, а също и раздел 5.2. За официален анализ на конструктивната вселена на множествата и сравнение с йерархията на Фон Нойман вижте (Ziegler 2014). Вселената на множествата често се описва като отворена концепция, вселена „в огън“. Тази идея е особено добре изразена в теорията на конструктивния тип, където понятието за теоретично тип на Вселената е умишлено оставено отворено от Пер Мартин-Льоф (като не се поставят конкретни правила за елиминиране за нея). Отворената природа на вселената на множествата проправи пътя за разширяването й чрез принципите на размисъл. Те са изследвани както в теорията на типа, така и в конструктивната теория на множествата. Вижте (Rathjen 2005a) за изследване на резултатите и основополагаща дискусия, а също и раздел 5.2. За официален анализ на конструктивната вселена на множествата и сравнение с йерархията на Фон Нойман вижте (Ziegler 2014).където понятието теоретично тип на Вселената е умишлено оставено отворено от Пер Мартин-Льоф (като не постулира конкретни правила за елиминиране за него). Отворената природа на вселената на множествата проправи пътя за разширяването й чрез принципите на размисъл. Те са изследвани както в теорията на типа, така и в конструктивната теория на множествата. Вижте (Rathjen 2005a) за изследване на резултатите и основополагаща дискусия, а също и раздел 5.2. За официален анализ на конструктивната вселена на множествата и сравнение с йерархията на Фон Нойман вижте (Ziegler 2014).където понятието теоретично тип на Вселената е умишлено оставено отворено от Пер Мартин-Льоф (като не постулира конкретни правила за елиминиране за него). Отворената природа на вселената на множествата проправи пътя за разширяването й чрез принципите на размисъл. Те са изследвани както в теорията на типа, така и в конструктивната теория на множествата. Вижте (Rathjen 2005a) за изследване на резултатите и основополагаща дискусия, а също и раздел 5.2. За официален анализ на конструктивната вселена на множествата и сравнение с йерархията на Фон Нойман вижте (Ziegler 2014). Те са изследвани както в теорията на типа, така и в конструктивната теория на множествата. Вижте (Rathjen 2005a) за изследване на резултатите и основополагаща дискусия, а също и раздел 5.2. За официален анализ на конструктивната вселена на множествата и сравнение с йерархията на Фон Нойман вижте (Ziegler 2014). Те са изследвани както в теорията на типа, така и в конструктивната теория на множествата. Вижте (Rathjen 2005a) за изследване на резултатите и основополагаща дискусия, а също и раздел 5.2. За официален анализ на конструктивната вселена на множествата и сравнение с йерархията на Фон Нойман вижте (Ziegler 2014).

2. Произход на конструктивните и интуиционистични теории на множествата

Интуиционистичните версии на теориите за набор на Zermelo-Fraenkel са въведени в началото на 70-те от Friedman и Myhill. Във (Friedman 1973) авторът представя изследване на формалните свойства на различни интуиционистични системи и въвежда за тях разширение на метода на реализируемост на Kleene. Техниката за реализируемост е приложена в (Myhill 1973), за да се покаже свойството за съществуване на версия на интуиционистичната теория на множествата на Zermelo-Fraenkel (със замяна на мястото на събиране). В друг основен принос Фридман разширява превода за двойно отрицание на интуитонистичната логика, за да свърже класическите и интуиционистичните теории за множеството (Friedman 1973a). Тези първи доклади вече разглеждат връзката между някои основни интуиционистични теории на множеството и класическите ZF. Те изясняват и ключова характеристика на теорията на множествата, базирана на интуиционистичната логика,главно, че подлежи на мощни конструктивни семантични интерпретации, като осъществимост. Тези техники се прилагат за изследване на ключови метатеоретични свойства, които са характерни за конструктивния подход и които се ползват от някои теории за конструктивното множество (вижте раздела за семантичните техники). Тази новаторска работа е напълно експлоатирана и съществено разширена в работата на Бийсън и Маккарти (виж Beeson 1985; McCarty 1984). Тази новаторска работа е напълно експлоатирана и съществено разширена в работата на Бийсън и Маккарти (виж Beeson 1985; McCarty 1984). Тази новаторска работа е напълно експлоатирана и съществено разширена в работата на Бийсън и Маккарти (виж Beeson 1985; McCarty 1984).

Теорията на конструктивните множества от самото начало има по-отличително основополагащо призвание и е обвързана с математиката на Бишоп. Всъщност през 1967 г. Бишъп публикува книгата „Основи на конструктивния анализ“(Bishop 1967), която открива нова ера за математика, основана на интуиционистичната логика (виж записа на конструктивната математика). Монографията стимулира нови опити на логическата общност да изясни и официално да представи принципите, използвани от Бишоп, макар и само на неформално ниво. Първите опити на Гудман и Михил (Goodman и Myhill 1972) използват версии на системата на Gödel T (виж също (Bishop 1970) за подобен опит). Myhill обаче стигна до извода, че получената формализация е твърде сложна и изкуствена (Myhill 1975, 347). Вместо това Михил предложи система, която е по-близка до неформалната представа за набор, първоначално използван от Бишоп, а също и по-близка до теоретично настроената традиция. Myhill пише (1975, 347):

Ние отказваме да вярваме, че нещата трябва да са толкова сложни - аргументацията на (епископ 1967 г.) изглежда много гладка и сякаш спада директно от определена концепция за това какво са множествата, функциите и т.н., и искаме да открием формализъм, който изолира принципите, залегнали в основата на това схващане, по същия начин, по който теорията на множествата на Цермело-Френкел изолира принципите, залегнали в основата на класическата (неконструктивна) математика. Искаме тези принципи да бъдат такива, че да направят процеса на формализиране напълно тривиален, както е в класическия случай.

Тук наблюдаваме, че теорията на конструктивните множества на Михил е разграничила понятията за функция, естествено число и множество; по този начин тя отблизо представлява конструктивна традиция, в която функциите и естествените числа са концептуално независими от множествата. Друга фундаментална стъпка в развитието на теорията на конструктивните множества е „Структурно-теоретичните основи на конструктивния анализ на Фридман“(Friedman 1977). Тук, сред другите системи, се определя система, наречена B, която има допълнителни ограничения върху теоретично зададените принципи в сравнение с тези на Myhill (по-специално тя няма зададена индукция). Той също има ограничена форма на аксиомата на зависимия избор. Системата Б е показана достатъчно изразителна, за да представи конструктивния анализ на Бишоп (1967), като същевременно е теоретично доказана много слаба (поради липсата на зададена индукция). Система В е всъщност консервативно разширение на аритметиката (следователно е доста под границата на предикативността, като се имат предвид накратко припомнените естествени числа в раздел 1.3). Системите на Myhill и Friedman впоследствие бяха модифицирани от Aczel, за да се получи система CZF (Constructive Zermelo-Fraenkel), която е напълно съвместима с езика на ZF (Aczel 1978, 1982, 1986; Aczel и Rathjen 2001; 2010). CZF също не включва принципи за избор. Аксел даде интерпретация на CZF в теорията на типа Мартин-Льоф с цел да потвърди конструктивния характер на теорията на множествата. Той също така засили някои от принципите на системата на Myhill (а именно събиране и експониране) на основание, че по-силните версии все още са утвърдени от интерпретацията в теорията на типа.

Други основополагащи системи за конструктивна математика в стил Бишоп са въведени в началото на 70-те години. Например: изрична математика от С. Феферман (Feferman 1975) и споменатата вече теория на интуиционистичния тип (Martin-Löf 1975; 1984). Теорията на конструктивния тип обикновено се счита за най-задоволителната основа за конструктивна математика в стил Бишоп. Както теорията на типа, така и явната математика могат да се разглеждат като изразяващи по-пряко изчислителното съдържание на конструктивната математика. По-специално теорията на типовете може да се чете като много общ и експресивен програмен език. Конструктивните и интуиционистични теории от множества показват изчислителното им съдържание само косвено чрез семантичните им интерпретации (виж например (Aczel 1977), (Lipton 1995) и раздела за семантичните техники).

3. Axioms Systems CZF и IZF

За читател, който вече е запознат с теорията на множествата ZF, сега накратко си припомняме аксиомите на системите CZF и IZF. За пълен списък и обяснение на техните аксиоми визираме вместо допълнителния документ:

Аксиоми на CZF и IZF.

CZF и IZF са формулирани на базата на интуиционистична логика от първи ред с равенство, като имат само (in) (членство) като допълнителен нелогичен двоичен предикатен символ. Техните зададени теоретични аксиоми са както следва.

(Mathbf {IZF}) (Mathbf {CZF})
Extensionality (същото)
двойка (същото)
съюз (същото)
безкрайност (същото)
раздяла Ограничено разделяне
колекция Силна колекция
Powerset Колекция подмножества
Задаване на индукция (същото)

Обърнете внимание, че в IZF схемата на разделяне е неограничена. В CZF колекцията е засилена, за да компенсира ограниченото разделяне. Подмножеството колекция е засилване на аксиомата на експониране на Myhill, като по този начин замества Powerset на ZF.

4. Принципи на конструктивен избор

Когато се обсъжда ролята на класическата теория на множествата като основа за математиката, обикновено се разглежда теорията ZFC, тоест аксиома система ZF плюс аксиома на избор (AC). Следователно може да се чуди какъв е статуса на аксиомата на избор в интуиционистичните настройки. Въпросът е особено важен, тъй като при първата си поява аксиомата на избора често се разглежда като противоречива и силно неконструктивна. В конструктивен контекст обаче човек е свидетел на своеобразно явление. Обичайната форма на избраната аксиома се утвърждава от теории от типове като теорията на типа Мартин-Льоф, където има кореспонденцията на Кури-Хоуърд (виж раздел 3.4 от записа на Конструктивна математика). От друга страна, предположението за аксиомата на избор поражда случаи на изключена среда в контекстите на разширението, т.е.където също е налице форма на отделяне. Такъв е случаят например с конструктивен и интуиционистичен ZF. (За доказателството вижте допълнителния документ за теоретично зададени принципи, несъвместими с интуиционистичната логика.) Доказателство за несъвместимостта на променливотока с разширените теории на множеството, основани на интуиционистичната логика, изглежда първо се появява в (Diaconescu 1975) в категоричен контекст. Гудман и Михил дават аргумент за зададени теории, базирани на интуиционистична логика (Goodman and Myhill 1978).) Доказателство за несъвместимостта на AC с теории за разширения на базата на интуиционистична логика изглежда за пръв път се появява в (Diaconescu 1975) в категоричен контекст. Гудман и Михил дават аргумент за зададени теории, базирани на интуиционистична логика (Goodman and Myhill 1978).) Доказателство за несъвместимостта на AC с теории за разширения на базата на интуиционистична логика изглежда за пръв път се появява в (Diaconescu 1975) в категоричен контекст. Гудман и Михил дават аргумент за зададени теории, базирани на интуиционистична логика (Goodman and Myhill 1978).

Въпреки че аксиомата на избора е несъвместима както с конструктивния, така и с интуиционистичния ZF, към основните системи могат да се добавят други принципи за избор, без да се получават същите нежелани резултати. Например може да се добави принципът на избор на счет (AC (_ 0)) или принцип на зависимия избор (DC). Всъщност и двамата често са били използвани в конструктивната математическа практика. (За тяхната точна формулировка вижте допълнителния документ за аксиомите на CZF и IZF.)

В (Aczel 1978) авторът също така обмисля принцип на избор, наречен Prexation Axiom, който твърди, че всеки набор е сюжективният образ на така наречената основа. Базата е набор, да речем (B), така че всяка връзка с домейн (B) разширява функция с домейн (B).

Съвместимостта на всички тези форми на избор с конструктивната теория на множествата е доказана от Aczel чрез разширяване на неговата интерпретация на CZF в теорията на типа Мартин-Льоф (Aczel 1982). Rathjen (2006) също е разгледал различни принципи за конструктивен избор и техните взаимни отношения.

Последна забележка: въпреки че конструктивните и интуиционистични теории на множествата са съвместими с току-що споменатите принципи за избор, зададените теории често са дефинирани без принципи за избор. Това има за цел да даде възможност за „плуралистичен“основополагащ подход. По-специално, човек би искал да получи основополагаща теория, съвместима с тези контексти (напр. Категорични модели на теорията на множествата), в която дори тези по-слаби принципи на избор може да не бъдат утвърдени. За подобни идеи в контекста на теорията на конструктивния тип вижте (Maietti и Sambin 2005, Maietti 2009). Тук искаме да споменем и апела на Ричман за конструктивна математика, която не използва принципите на избор (Richman 2000; 2001).

5. Теория на доказване и семантика на конструктивното и интуиционистичното ZF

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

5.1 Доказателно-теоретична сила

Основна тема в теорията на доказателствата (по-специално в отрасъла на тази дисциплина, известна като порядъчен анализ) е класификацията на теориите с помощта на трансфинитни наредби, които измерват тяхната "сила на съгласуваност" и "изчислителна сила". Тези наредби показват колко силна е теорията и затова предлагат начин за сравняване на различни теории. Например, порядковата (varepsilon_0) е теоретично доказателствената порядъчна стойност на Peano Aithmetic и е много по-малка от ординарната (Gamma_0), обикновено наричана "границата на предикативността" (виж раздел 1.3 по-горе). Това е показателно, че има предположително предположителни теории, които са много по-силни от аритметиката на Peano.

Както беше обсъдено в раздел 1, стъпката от класическия ZF към неговите интуиционистични варианти изисква да изберем подходяща формулировка за всяка теоретично зададена аксиома: една класическа аксиома може да има редица интуиционистични варианти, които се оказват нееквивалентни една на друга, Това понякога се отразява от доказателствената теоретична сила на получените теории, която може да варира в зависимост от това кои принципи избираме. Например, вече отбелязахме, че в CZF нямаме пълно разделяне и мощност, които се заменят съответно от предикативно приемливите принципи на ограничено разделяне и събиране на подмножество. Ако обаче добавим към CZF някой от тези принципи, получаваме непредсказуеми теории. Непредсказуемостта на получените теории е засвидетелствана от факта, че тяхната доказателствено-теоретична сила силно надхвърля тази на CZF.

Не е изненадващо, че изследванията върху доказателствената теоретична сила на конструктивните и интуиционистичните теории на множеството са били решаващ мета-теоретичен инструмент за разбиране на тези теории и техните взаимоотношения помежду си. Изследванията върху доказателствената сила на една теория са богати и информативни. По-специално, Feferman (1993) твърди, че доказателствено-теоретичният анализ може да ни помогне да установим дали определена теория съответства на дадена философска рамка: например анализът може да разкрие, че теорията е предикативна или финистична и т.н. Освен това, като страничен продукт от доказателствено-теоретичния анализ понякога получаваме прости доказателства за независимост. Всъщност можем да покажем, че една теория не може да докаже конкретен принцип, тъй като добавянето й към теорията би увеличило доказателствената сила на теорията. Например,CZF не доказва аксиомата на захранването, тъй като добавянето на powerset към CZF поражда много по-силна теория. Използвани са и теоретично-теоретични интерпретации за сравняване на конструктивни и интуиционистични теории за задаване на ZF помежду си, както и с техните класически колеги, а също и с други основополагащи системи за конструктивна математика, като например теория на конструктивния тип и явна математика (виж например, Griffor and Rathjen 1994, Tupailo 2003). За определение на понятието доказателствена теоретична сила и за проучвания върху теорията на доказателството вижте например (Rathjen 1999, 2006b).както и с техните класически колеги, а също и с други основополагащи системи за конструктивна математика, като теория на конструктивния тип и явна математика (виж например, Griffor and Rathjen 1994, Tupailo 2003). За определение на понятието доказателствена теоретична сила и за проучвания върху теорията на доказателството вижте например (Rathjen 1999, 2006b).както и с техните класически колеги, а също и с други основополагащи системи за конструктивна математика, като теория на конструктивния тип и явна математика (виж например, Griffor and Rathjen 1994, Tupailo 2003). За определение на понятието доказателствена теоретична сила и за проучвания върху теорията на доказателството вижте например (Rathjen 1999, 2006b).

Въпреки че CZF и IZF са най-широко изучаваните системи, в литературата досега са разгледани множество други системи за конструктивна и интуиционистка теория на множествата. Теоретичната сила на редица конструктивни и интуиционистични теории на множествата е установена от различни инструменти, като например разширение за теория на множеството на интерпретацията на двойното отрицание (произхожда от (Friedman 1973a)) и разнообразие на други доказателствено-теоретични интерпретации, често произтичащи от внимателна комбинация от семантични и доказателствени теоретични техники. В много случаи доказателствената теоретична сила на дадена система се определя от верига от интерпретации между конструктивна и класическа система и чрез използване на различни инструменти, от достъпност до по-"традиционни" теоретични теоретични техники, като порядъчен анализ (виж,например Beeson 1985; Griffor and Rathjen 1994; Rathjen 2012b). По-специално, реализируемостта се оказа много полезна, поради своята гъвкавост. Що се отнася до резултатите от тези проучвания, някои от анализираните системи се оказват толкова слаби, колкото аритметичните, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0). Beeson 1985; Griffor and Rathjen 1994; Rathjen 2012b). По-специално, реализируемостта се оказа много полезна, поради своята гъвкавост. Що се отнася до резултатите от тези проучвания, някои от анализираните системи се оказват толкова слаби, колкото аритметичните, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0). Beeson 1985; Griffor and Rathjen 1994; Rathjen 2012b). По-специално, реализируемостта се оказа много полезна, поради своята гъвкавост. Що се отнася до резултатите от тези проучвания, някои от анализираните системи се оказват толкова слаби, колкото аритметичните, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0). Rathjen 2012b). По-специално, реализируемостта се оказа много полезна, поради своята гъвкавост. Що се отнася до резултатите от тези проучвания, някои от анализираните системи се оказват толкова слаби, колкото аритметичните, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0). Rathjen 2012b). По-специално, реализируемостта се оказа много полезна, поради своята гъвкавост. Що се отнася до резултатите от тези проучвания, някои от анализираните системи се оказват толкова слаби, колкото аритметичните, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0).реализируемостта се оказа много полезна, поради своята гъвкавост. Що се отнася до резултатите от тези проучвания, някои от анализираните системи се оказват толкова слаби, колкото аритметичните, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0).реализируемостта се оказа много полезна, поради своята гъвкавост. Що се отнася до резултатите от тези проучвания, някои от анализираните системи се оказват толкова слаби, колкото аритметичните, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0).някои от анализираните системи се оказват също толкова слаби като аритметика, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0).някои от анализираните системи се оказват също толкова слаби като аритметика, като например системата B на Фридман (Friedman 1977); другите системи са толкова силни, колкото и напълно класическият ZF, както и IZF (Friedman 1973a). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0). Съществуват и системи с междинна якост, като CZF. Силата на последната теория всъщност се равнява на теорията на едно индуктивно определение, известно като ID (_ 1). Фактът, че CZF има същата сила като ID (_ 1), се приема, за да се потвърди (обобщената) предиктивност на теорията на множествата и да се докаже, че тя надвишава границата на предикативност, като се имат предвид естествените числа, тъй като ID (_ 1) теоретичният порядък на доказателството е много над (Gamma_0).

Като последна забележка: докато силата на CZF е доста по-ниска от тази на аритметика от втори ред, простото добавяне на изключен среден към CZF ни дава (пълен) ZF. Това трябва да се контрастира с IZF, който вече има силата на ZF (Friedman 1973a). Ограничената доказателствена теоретична сила на CZF в сравнение с IZF често се счита за едно от основните предимства на конструктивната пред интуиционистичната теория на множествата. В известен смисъл изглежда, че CZF се възползва максимално от интуиционистичната логика, тъй като характеризира понятие за (обобщен) предикативен набор, който е достатъчно силен за развитието на голяма част от конструктивната математика, но и достатъчно слаб, за да се избегне непредсказуемостта. Интересното е, че когато към конструктивната теория на множествата се добавят някои големи аксиоми от множество, се появи подобен модел, т.е.тъй като силата на получената теория е много под силата на съответната класическа теория.

5.2 Големи комплекти в конструктивен и интуиционистичен ZF

Видна област на изследване в класическата теория на множествата е тази на големите кардинали (виж вписването на теорията на множествата). В конструктивен контекст наредбите не са линейно подредени. (За понятието конструктивна порядъчна и кратко обсъждане на нейните свойства вижте допълнителния документ на тема: Набор-теоретични принципи, несъвместими с интуиционистичната логика.) Вследствие на това, кардиналните числа не играят същата роля, както в класическата обстановка.

Въпреки това може да се проучи въздействието на „принципите на размисъл“под формата на големи зададени аксиоми. Например, човек може да добави към конструктивните и интуиционистични теории на множествата аксиома, която твърди съществуването на недостъпни множества. [2] Добавянето на големи множествени аксиоми към интуиционистичния ZF е предложено за първи път от Фридман и Щедров (Friedman and Scedrov 1984). Една от целите им беше да хвърлят светлина върху съответните класически представи; друго е да се проучи влиянието на тези принципи върху метатеоретичните свойства на първоначалните теории на множеството. Фридман и Щедров показаха например, че добавянето на големи множествени аксиоми не компрометира валидността на свойствата на дизъюнкцията и численото съществуване за IZF.

В контекста на теорията на конструктивните множества от Aczel са въведени големи множества под формата на така наречени редовни множества, които позволяват индуктивни дефиниции на множествата (Aczel 1986). Rathjen и Crosilla са считали за недостъпни набори (Rathjen al. 1998; Crosilla and Rathjen 2001) и Mahlo множества (Rathjen 2003a). Независимо от това може да се повдигне възражение срещу разширения на теорията на конструктивните множества чрез големи множествени аксиоми. В класическата теория на множествата големите кардинали могат да се разглеждат като въплъщение на по-висока безкрайност. Как да оправдаем тези принципи конструктивно? Конструктивната обосновка на тези понятия отново опира до теоретичното тълкуване на типа. Добавянето на тези принципи всъщност съответства на това на вселените и (W) - типове в рамките на конструктивната теория на типа. Обосновката на разширенията от големи множества е свързана с въпроса за границите на теорията на типа Мартин-Льоф (Rathjen 2005). Отбелязваме също, че добавянето на непристъпни зададени аксиоми към слаба подсистема на CZF (без зададена индукция) произвежда теория за силата (Gamma_0), порядъчната, обозначена от Feferman и Schütte като граница на предикативността, предвид естествената числа (Crosilla и Rathjen 2001; вж. също раздел 1.3). Това е свидетел на факта, че като работим в конструктивен, предикативен контекст, можем да укротим традиционно силни теоретично зададени теории.последователността, обозначена от Feferman и Schütte като граница на предикативност, предвид естествените числа (Crosilla and Rathjen 2001; вж. също раздел 1.3). Това е свидетел на факта, че като работим в конструктивен, предикативен контекст, можем да укротим традиционно силни теоретично зададени теории.последователността, обозначена от Feferman и Schütte като граница на предикативност, предвид естествените числа (Crosilla and Rathjen 2001; вж. също раздел 1.3). Това е свидетел на факта, че като работим в конструктивен, предикативен контекст, можем да укротим традиционно силни теоретично зададени теории.

Теорията на множеството на Кросила и Ратиен с непристъпни множества (но без индукция на множеството) е теоретично доказателство, доста слабо, но математически доста изразително. Например, той е бил използван за проверка, че добавянето на универсалентната аксиома на Воеводски към теорията на типа Мартин-Льоф не поражда непредсказуемост (Rathjen 2017). Аксиомата на Univalence е въведена от Воеводски като част от неговата програма Univalent Foundation (Voevodsky 2015). (За Univalent Foundation, вижте записите за теорията на типа и за интуиционистичната теория на типа). Воеводски даде модел на конструктивна теория на типа с аксиомата на универсалността, която се основава на опростени множества на Кан (виж Kapulkin & Lumsdaine 2012, Други интернет ресурси). Опростеният модел на теорията на конструктивния тип с едноличност, разработен в горната статия, се осъществява в рамките на разширение на ZFC с недостъпни кардинали. Това предизвика въпроса дали човек може да даде по-конструктивен модел на този тип теория и по-специално дали теорията на типа е предикативна. Bezem, Coquand и Huber (2014) наскоро предложиха модел на този тип теория в кубични множества, който е изчислителен и „може да се изрази в конструктивна металогика“. Rathjen (2017) потвърди, че този нов модел може да бъде кодифициран в подходящо разширение на CZF чрез недостъпни множества, което е много по-слабо от класическата теория на множествата с недостъпни кардинали. Всъщност се оказва, че ако вземем за отправна точка сравнително слаба теория от типа, т.е. такава без W-типове, и я разширим чрез аксиомата на универсалност,получената теория има доказателствена теоретична сила (Gamma_0), като порядковата обикновено се приема за представяне на границата на предсказуемостта, като се имат предвид естествените числа (Rathjen 2017). За да покажем това, се доказва, че кубическият модел от Bezem, Coquand и Huber може да бъде осъществен в разширение на системата, въведена в Crosilla и Rathjen (2001) чрез (ограничен) релативизиран зависим избор. От (Crosilla and Rathjen 2001) и (Rathjen 2003) следва, че последната има теоретична доказателствена порядкова (Gamma_0). Coquand и Huber могат да бъдат осъществени в разширение на системата, въведена в Crosilla и Rathjen (2001) чрез (ограничен) релативизиран зависим избор. От (Crosilla and Rathjen 2001) и (Rathjen 2003) следва, че последната има теоретична доказателствена порядкова (Gamma_0). Coquand и Huber могат да бъдат осъществени в разширение на системата, въведена в Crosilla и Rathjen (2001) чрез (ограничен) релативизиран зависим избор. От (Crosilla and Rathjen 2001) и (Rathjen 2003) следва, че последната има теоретична доказателствена порядкова (Gamma_0).

5.3 Метаматематични свойства на конструктивни и интуиционистични ZF и семантични техники

Разнообразие от интерпретации за интуиционистична логика са разширени до интуиционистични и конструктивни теории на множеството, като реализируемост, модели на Крипке и семантика с стойност на Хейтинг. Всички тези техники са приложени за получаване на метаматематични резултати за зададените теории.

5.3.1 Свойства на дизъюнкцията и съществуването на конструктивния и интуиционистичния ZF

Някои интуиционистични теории на множеството удовлетворяват определени „отличителни“метаматематически свойства, като дизъюнкцията и свойствата на съществуването. Може да се покаже, че те съответстват на добавянето на принципи, които надхвърлят онова, което обикновено считаме за конструктивно. Сред тях са например църковната теза и принципа на Марков. За описание на тези принципи в контекста на интуиционистичната логика, читателят може да пожелае да се консултира с раздели 4.2 и 5.2 от статията за интуиционистичната логика или книгата „Конструктивизъм в математиката на Троелстра и Ван Дален“(Troelstra and van Dalen 1988).

Тук си припомняме свойствата на дизъюнкцията и съществуването, формулирани за теория на множествата (T). Неформалната мотивация за дизъюнкцията и свойствата на съществуването се основава на нашето разбиране за конструктивните доказателства за дизюнктивни и екзистенциални твърдения (съответно). Всъщност изглежда разумно да се очаква, че ако конструктивно докажем раздвоение (phi / vee / psi), тогава също би трябвало да можем да докажем (phi) или да докажем (psi). По същия начин, ако докажем екзистенциално твърдение, тогава би трябвало да можем да докажем, че свидетел на това твърдение може да се определи в рамките на нашата теория.

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

Нека (T) е теория, чийто език (L (T)) обхваща езика на теорията на множествата. Освен това, за простота, ще приемем, че (L (T)) има константа (omega), обозначаваща множеството от естествени числа на фон Нойман, а за всяко (n) константа (c_n) обозначаваща (n) -тият елемент на (omega).

Теория (T) има свойството на дизъюнкция (DP), ако винаги, когато (T) докаже ((phi / vee / psi)) за изречения (phi) и (psi) на (L (T)), тогава (T) доказва (phi) или (T) доказва (psi).

Най- имота съществуване има две различни версии в контекста на теория: на цифров съществуване собственост (НЕП) и съществуване собственост (ЕП). Нека (theta (x)) е формула с най-много (x) свободна. Ние казваме, че:

(1) (T) има NEP, ако винаги, когато (T) докаже (съществува x / в / omega / theta (x)), тогава за някакво естествено число (n, T) се докаже (тета (c_n)).

(2) (T) има EP, ако винаги, когато (T) докаже (съществува x / theta) (x), тогава има формула (phi (x)) с точно (x) безплатно, така че (T) доказва (съществува! x (phi (x) wedge / theta (x))).

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

5.3.2 Реализируемост

Реализуемостта е един от първите и основни инструменти в изследванията около множеството теории, базирани на интуиционистична логика, като се започне от ранните приноси на Фридман и Михил (Friedman 1973, Myhill 1973). Семантика за реализируемост за интуиционистична аритметика е предложена за първи път от Kleene (Kleene 1945) и разширена до по-висок ред Heyting аритметика от Kreisel и Troelstra (Kreisel и Troelstra 1970). За определението за реализируемост на аритметиката вижте раздел 5.2 от записа на интуиционистичната логика. Реализируемост, подобна на Kreisel и Troelstra, беше приложена към системи от аритметика от по-висок ред от Фридман (Friedman 1973). Myhill въведе вариант на тази реализируемост, който наподобява наклона на Kleene (Myhill 1973; Kleene 1962, 1963). Така той доказа, че версия на IZF със замяна на мястото на събиране (наречена IZF (_ {Rep})) има DP, NEP и EP. Тези резултати са допълнително разширени през (Myhill 1975; Friedman and Scedrov 1983). Докато Фридман и Майхил дават модели за реализируемост на теории за разширени набори, Бийсън разработва понятие за реализируемост за теории за неразширени набори. След това той изучава метатеоретичните свойства на теориите за разширения набор чрез интерпретация в техните неекстензионни колеги. Така той доказа, че IZF (с колекция) има DP и NEP (Beeson 1985). Впоследствие Маккарти въвежда реализируемост за IZF директно за теория на разширените множества (McCarty 1984; 1986). Семантиката за реализируемост на варианти на CZF е разгледана например в (Crosilla и Rathjen 2001; Rathjen 2006a). Реализуемостта в последната статия е вдъхновена от McCarty's и има важната характеристика, че както McCarty за IZF, това е самоутвърждаваща семантика за CZF (тоест, това понятие за реализируемост може да бъде формализирано в CZF и всяка теорема на CZF е реализирана доказано в CZF). Rathjen се възползва от това понятие за реализируемост, за да покаже, че CZF (и редица разширения от него) имат DP и NEP (Rathjen 2005b).

Друг вид реализируемост, който се оказа много полезен, е реализируемостта на Lifschitz. Lifschitz (1979) въведе модификация на осъществимостта на Kleene за аритметика на Heyting, която има особеността да утвърждава слабата форма на тезата на Църквата (CT) с уникално условие, но не и самата CT. Реализируемостта на Лифшиц беше разширена до аритметика от втори ред от Ван Оостен (1990). Впоследствие той бе разширен до пълния IZF от Ченг и Ратижен, които го използваха, за да получат редица резултати за независимост, както и за валидиране на така наречения Малък ограничен принцип на всезнанието (LLPO) (за LLPO вижте записа за конструктивна математика).

Въпросът кои теории за задаване удовлетворяват свойството за съществуване се оказа особено труден за решаване. (Friedman and Scedrov 1985) използваха крипке модели, за да покажат, че IZF (тоест системата с колекция) няма EP, докато както бе споменато по-горе, системата IZF (_ {Rep}) (която има заместване на мястото си на колекция) има ЕП. Това подтикна Бийсън да постави въпроса [Beeson 1985, IX]:

Има ли някаква разумна теория на множествата с колекцията да има свойството за съществуване?

Първият отговор на въпроса на Бийсън дойде с (Rathjen 2012), където авторът въвежда понятието за слабо съществуване: фокусът тук е намирането на очевидно определен набор от свидетели за всяка екзистенциална теорема. След това той въвежда форма на реализируемост, основана на общо зададени рекурсивни функции, където реализатор за екзистенциално изявление предоставя набор от свидетели за екзистенциалния количествен показател, а не за един свидетел. Rathjen комбинира това понятие за осъществимост с истината, за да се получи, че редица теории със събиране се радват на слабото съществуване (докато IZF не). По-специално, теорията CZF без събиране на подмножество плюс аксиома на експозицията на Myhill, CZF (_ {Exp}). Всъщност Ратижен твърди, че като комбинира тези резултати с по-нататъшната работа, която е извършил,той може да покаже, че CZF (_ {Exp}) (и редица други теории) имат свойството за съществуване. Впечатляващо наблюдение е, че тези теории са формулирани с колекция; следователно отказът на съществуващото свойство в случай на IZF не може да се отдаде само на събирането, но и на взаимодействието между тази схема и неограниченото разделяне.

Що се отнася до важния въпрос дали самата CZF има свойството за съществуване, това е решено в негативен от Swan (2014). Там авторът се възползва от три добре разработени модела за реализиране и вграждания между тях, за да покаже, че дори и слабата собственост на съществуване не успява за CZF. По този начин той също показа, че виновникът е схемата за събиране на подмножество на CZF. Както ясно се подчертава в (Swan 2014) фактът, че CZF няма ЕП, не показва известна слабост в CZF като конструктивна теория. Дори ако Суон доказа по същество, че CZF твърди съществуването на математически обекти, които не знае как да конструира, все пак CZF има естествени интерпретации, в които тези обекти могат да бъдат конструирани, като например интерпретацията на Aczel в теория на типовете (Aczel 1978), За проучване на резултатите в интуиционистичната теория на множествата вижте (Beeson 1985, глава IX). За съответните развития в CZF вижте (Rathjen 2005b, 2006, 2012) и (Swan 2014).

5.3.3 Крипке модели и семантика с стойност на Хейтинг

Моделите на Крипке за теории за интуитивно настроение са използвани (Friedman and Scedrov 1985), за да покажат, че IZF няма EP (и комбинирайки това с резултатите от (Myhill 1973), ние имаме IZF (_ {Rep}) не доказват IZF). Крипке моделите наскоро се прилагат за изясняване на връзката между конструктивните заместители на аксиомата на зададената мощност: аксиомата на експозицията на Myhill и схемата за събиране на подмножество на Aczel. Ясно е, че аксиомата на зададената мощност предполага и двата принципа и че събирането на подмножества предполага експоненция. От друга страна, всеки от последните два принципа не предполага мощност, тъй като теорията CZF с мощност, зададена на мястото на събиране на подмножество, е много по-силна от CZF и CZF (_ {Exp}) (Rathjen 2012b). Всъщност CZF и CZF (_ {Exp}) имат една и съща доказателствена теоретична сила (Griffor and Rathjen 1994);следователно, за да се изследва връзката между събирането на подмножество и експоненцирането в теорията на конструктивните множества, една от които е необходима за разработване на инструменти, различни от доказателствени теоретични методи. Lubarsky (2005) използва Крипке модели, за да покаже, че аксиомата на експониране на Myhill не предполага колекция от подмножества на Aczel (въз основа на CZF минус колекция от подмножества плюс пълно разделение). В (Lubarsky and Rathjen 2007) авторите са приложили техниката на крипке моделите, за да покажат, че последствията от теориите CZF и CZF (_ {Exp}) са различни. Aczel и Rathjen (2001) показаха, че класът реални числа Dedekind образува набор в CZF, като използва колекция от подмножества. Lubarsky and Rathjen (2007) показаха, че CZF (_ {Exp}) не е достатъчен, за да докаже същото твърдение. За по-нататъшното приложение на моделите на Крипке за разделяне на ключови конструктивни представи вижте напр(Diener and Lubarsky 2013).

Гейтсън (Грейсън 1979) е получена от Хейтънс ценовата семантика за интуиционистични теории на множествата като аналог на булевите модели за класическата теория на множествата. Те са обобщени особено чрез категорична семантика (за въведение вж. MacLane и Moerdijk 1992). Хейтинговата семантика намери приложение за резултатите от независимостта през (Scedrov 1981; 1982). Конструктивно лечение е дадено през (Gambino 2006). Вижте също (Lubarsky 2009). Вижте също Ziegler (2012) за обобщение на реализуемостта и модели на Heyting за конструктивна теория на множествата.

5.3.4 Категорични модели на конструктивна и интуиционистка теория на множествата

Категоричните модели на конструктивни и интуиционистични теории на множествата процъфтяват през годините. Представите за топоса и снопа играят съществена роля тук (вж. Например Fourman 1980 и Fourman и Scott 1980). За преглед на основните понятия вижте записа на теорията на категориите и референциите, предоставени там (вижте по-специално допълнението Ръководство за програмно четене). За последните разработки, които се отнасят по-конкретно към теориите за конструктивни множества, вижте например (Simpson 2005) и (Awodey 2008), както и уеб страницата: алгебраична теория на множествата.

5.4 Варианти на конструктивни и интуиционистични теории от множества: Теории на множествата с уременции и неекстензионни теории от множества

Понякога системите на интуиционистичната и конструктивна теория на множествата се представят с естествените числа като отделен вид урелементи, тоест примитивни обекти без елементи (Friedman 1977; Myhill 1975; Beeson 1985). Конструктивно това е естествен избор, който е в съгласие с идеите, изразени например от Бишоп (1967) (между другото). В монографията на Бишоп естествените числа са взети като основна концепция, на която се основават всички останали математически концепции. От техническа гледна точка, ако естествените числа се приемат като примитивни и се отличават от техните теоретично представени множества, аксиомата на безкрайността след това придобива формата: „има набор от естествени числа (като урелементи)“. По-общата форма на урелементи в конструктивните теории на множествата е разгледана в (Cantini и Crosilla 2008). Тук е предложен вариант на конструктивна теория на множествата, който съчетава интензивна и частична представа за работа с разширената представа на CZF за множеството (виж също Cantini и Crosilla 2010).

Аксиомата на разширяването е обща черта на всички обсъждани досега системи. Въпреки това, в контекст, в който изчислителното съдържание на изявление се счита за решаващо, интензивната теория може да бъде по-подходяща. Например теорията на конструктивния тип и явната математика капсулират някаква форма на интензивност. В литературата са разгледани интуиционистичните теории на множествата без разширеност (Friedman 1973a, Beeson 1985). Тяхната мотивация обаче не е изчислителна, а техническа по своя характер, поради трудностите, които разширяването създава при изучаване на метаматематическите свойства на интуиционистичните теории на множествата.

библиография

  • Aczel, P., 1978, „Типовата теоретична интерпретация на теорията на конструктивните множества“, в Logic Colloquium '77, A. MacIntyre, L. Pacholski, J. Paris (ред.), Амстердам и Ню Йорк: Северна Холандия, pp 55–66.
  • –––, 1982, „Типово теоретично тълкуване на теорията на конструктивните множества: принципи на избора“, в LEJ Brouwer Centenary Symposium, AS Troelstra и D. van Dalen (ред.), Амстердам и Ню Йорк: North-Holland, pp. 1-40.
  • –––, 1986, „Типово теоретично тълкуване на теорията на конструктивните множества: индуктивни дефиниции“, в логиката, методологията и философията на науката VII, RB Marcus, GJ Dorn и GJW Dorn (ред.), Амстердам и Ню Йорк: Северна Холандия, стр. 17–49.
  • –––, 1988, Недостатъчни комплекти (бележки към лекциите на CSLI 14), Станфорд: CSLI.
  • Aczel, P. и Rathjen, M., 2001, „Бележки за теорията на конструктивните множества“, Доклад № 40, 2000/2001, Djursholm: Institut Mittag-Leffler, [достъпно онлайн]
  • Aczel, P., and Gambino, N., 2002, "Принципи на събиране в теорията на зависимите типове", в Типове за доказателства и програми (Бележки от лекции по компютърни науки 2277), P. Callaghan, Z. Luo, J. McKinna и Р. Поллак (ред.), Берлин: Спрингер, с. 1–23.
  • Awodey, S., 2008, „Кратко въведение в теорията на алгебраичните множества“, Информационен бюлетин, 14 (3): 281–298.
  • Barwise, J., and Moss, L., 1996, Vicious Circles (CSLI Lecture Notes 60), Stanford: CSLI.
  • Бийсън, М., 1985, Основи на конструктивната математика, Берлин: Спрингер.
  • Bezem, M., Thierry, C. and Huber, S., 2014, „Модел на теорията на типа в кубични множества“, в 19-та Международна конференция за типове доказателства и програми (TYPES 2013), Matthes, R. and Schubert, A. (изд.), Dagstuhl: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, стр. 107–128.
  • Бишоп, Е., 1967 г., Основи на конструктивен анализ, Ню Йорк: МакГрау-Хил.
  • –––, 1970 г., „Математиката като числов език“, в интуиционизма и теорията на доказателствата, А. Кино, Дж. Майхил и РЕ Весли (ред.), Амстердам: Северна Холандия, стр. 53–71.
  • Bishop, E. and Bridges, D., 1985, Constructive Analysis, Berlin and Heidelberg: Springer.
  • Бриджи, Д. и Ричман, Ф., 1987, Разновидности на конструктивната математика, Кеймбридж: Cambridge University Press.
  • Buchholz, W., Feferman, S., Pohlers, W. и Sieg, W., 1981, Iterated Inductive Definitions and Podystems of Analysis, Berlin: Springer.
  • Cantini, A. и Crosilla, L., 2008, „Теория на конструктивните множества с операции“, в A. Andretta, K. Kearnes, D. Zambella (ред.), Logic Colloquium 2004 (Бележки от лекции в Logic 29), Cambridge: Cambridge University Press, стр. 47–83.
  • Cantini, A. и Crosilla, L., 2010, „Изрична теория на оперативните множества“, в R. Schindler (ed.), Ways of Teore Theory, Frankfurt: Ontos, pp. 199-240.
  • Chen, R.-M. and Rathjen, M., 2012, „Lifschitz Realizability for Inuitionistic Zermelo-Fraenkel Theory Set“, Архив за математическа логика, 51: 789–818.
  • Crosilla, L., 2017, „Предсказуемост и феферман“, в G. Jäger и W. Sieg (изд.), Feferman on Фондации (изключителен принос към логиката: том 13), Cham: Springer, стр. 423–447.
  • Crosilla, L. и Rathjen, M., 2001, „Недостъпните зададени аксиоми могат да имат малка якост на консистенция“, Annals of Pure and Applied Logic, 115: 33–70.
  • Diaconescu, R., 1975, „Аксиома на избор и допълване“, Proceedings of the American Mathematical Society, 51: 176–178.
  • Diener, H. и Lubarsky, R., 2013, „Разделяне на теорията на вентилатора и нейните отслабвания“, в SN Artemov и A. Nerode (ред.), Proceedings of LFCS '13 (Бележки за лекции в Computer Science 7734), Dordrecht: Спрингер, с. 280–295.
  • Дамет, М., 2000, Елементи на интуиционизма, второ издание, (Оксфордски логически пътеводители 39), Ню Йорк: Oxford University Press.
  • Feferman, S., 1964, „Системи на предикативния анализ“, Journal of Symbolic Logic, 29: 1–30.
  • –––, 1975, „Език и аксиоми за явна математика“, в Алгебра и логика (Бележки за лекции по математика 450), J. Crossley (съст.), Берлин: Springer, стр. 87–139.
  • –––, 1988, „Weyl обоснован: Das Kontinuum седемдесет години по-късно“, в Temi e prospect della logica e della scienza съвременник, C. Cellucci и G. Sambin (ред.), Стр. 59–93.
  • –––, 1993, „Какво се опира на какво? Теоретично-теоретичният анализ на математиката”, в„ Философия на математиката”, част I, Протоколи от 15-ия международен симпозиум на Витгенщайн. Виена: Verlag Hölder-Pichler-Tempsky.
  • –––, 2005, „Предсказуемост“, в Наръчник по философия на математиката и логиката, С. Шапиро (съст.), Оксфорд: Оксфордски университет прес.
  • Флетчър, П., 2007, „Безкрайност“, в Наръчник на философията на логиката, Д. Жакет (съст.), Амстердам: Elsevier, стр. 523–585.
  • Fourman, MP, 1980, „Модели на снопове за теория на множествата“, Journal of Pure Applied Algebra, 19: 91–101.
  • Fourman, MP и Scott, DS, 1980, „Снопи и логика“, в „Приложения на снопове“(Бележки за лекции по математика 753), MP Fourman, CJ Mulvey и DS Scott (ред.), Берлин: Springer, стр. 302– 401.
  • Friedman, H., 1973, „Някои приложения на методите на Kleene за интуиционистични системи“, в Proceedings of Summer Cambridge Summer School of Mathematical Logic от 1971 г. (Бележки от лекции по математика 337), ARD Mathias и H. Rogers (ред.), Берлин: Спрингер, стр. 113–170.
  • –––, 1973a, „Съгласуваността на класическата теория на множествата по отношение на теорията на множествата с интуиционистката логика“, Journal of Symbolic Logic, 38: 315–319.
  • –––, 1977 г., „Теоретични основи за конструктивен анализ“, Анали на математиката, 105: 1–28.
  • Фридман, Х., Щедров, А., 1983, „Задаване на свойството на съществуването за интуиционистични теории с зависим избор“, Анали на чистата и приложна логика, 25: 129–140.
  • –––, 1984, „Големи множества в интуиционистичната теория на множествата“, Анали на чистата и приложна логика, 27: 1–24.
  • –––, 1985, „Липсата на подлежащи на определяне свидетели и доказано рекурсивни функции в интуиционистичната теория на множествата“, Напредъци в математиката, 57: 1–13.
  • Гамбино, Н., 2006, „Хейтинг-ценни интерпретации за теория на конструктивните множества“, Анали на чистата и приложна логика, 137: 164–188.
  • Goodman, ND и Myhill, J., 1972, „Официализацията на конструктивната математика на Бишоп“, в „Топос“, Алгебраична геометрия и логика (Бележки от лекции по математика 274), FW Lawvere (съст.), Берлин: Springer, стр. 83 -96.
  • Goodman, ND, и Myhill, J., 1978, „Изборът предполага изключен среден“, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 24 (5): 461.
  • Грейсън, Дж. Дж., 1979, „Хейтинг-ценни модели за теория на интуиционистичните множества“, в „Приложения на снопове“(Бележки от лекции по математика 753), MP MPman, CJ Mulvey и DS Scott (ред.), Берлин: Springer, стр. 402 -414.
  • Griffor, E. и Rathjen, M., 1994, "Силата на някои теории на Мартин-Льоф", Архив Математическа логика, 33: 347–385.
  • van Heijenoort, J., 1967, От Frege до Gödel. Източник Книга по математическа логика 1879–1931, Кеймбридж: Харвард Унив. Натиснете.
  • Kleene, SC, 1945, „За интерпретацията на теорията на интуиционистичните числа“, Journal of Symbolic Logic, 10: 109–124.
  • –––, 1962, „Съединение и съществуване под влияние на елементарни интуиционистични формализми“, сп. „Символична логика“, 27: 11–18.
  • –––, 1963 г., „Допълнение“, сп. „Символична логика“, 28: 154–156.
  • Kreisel, G., 1958, „Обикновена логика и характеризиране на неформални концепции за доказване“, Proceedings of the International Congress of Mathematicians (14–21 август 1958 г.), Париж: Gauthier-Villars, стр. 289-299.
  • Kreisel, G. и Troelstra, A., S., 1970, „Формални системи за някои клонове на интуиционистичния анализ“, Annals of Mathematical Logic, 1: 229–387.
  • Lifschitz, V., 1979, „CT (_ 0) е по-силен от CT (_ 0)!“, Proceedings of the American Mathematical Society, 73 (1): 101–106.
  • Lindström, I., 1989, „Конструкция на необосновани множества в рамките на теорията на типа Мартин-Льоф“, Journal of Symbolic Logic, 54: 57–64.
  • Липтън, Дж., 1995, „Реализируемост, теория на множествата и термично извличане“, в Изоморфизма на Къри-Хоуърд (Cahiers du Center de Logique de l’Universite Catholique de Louvain 8), Louvain-la-Neuve: Academia, стр. 257 -364.
  • Lorenzen, P. и Myhill, J., 1959, „Конструктивно определение на определени аналитични набори от числа“, Journal of Symbolic Logic, 24: 37–49.
  • Lubarsky, R., 2005, „Резултатите от независимостта около конструктивната ZF“, Annals of Pure and Applied Logic, 132: 209–225.
  • –––, 2006 г., „CZF и аритметика от втори ред“, Анали на чистата и приложна логика, 141: 29–34.
  • –––, 2009, „Топологична принудителна семантика с уреждане”, в С. Н. Артемов и А. Нероде (изд.), Сборник от LFCS '09 (Бележки за лекции в компютърните науки 5407), Дордрехт: Спрингер, стр. 309–322.
  • Lubarsky, R., and Rathjen, M., 2007, „За конструктивните дедекински реалности“, в SN Artemov и A. Nerode (ред.), Proceedings of LFCS 2007 (Бележки за лекции по компютърни науки 4514), Dordrecht: Springer, с. 349–362.
  • MacLane, S. и Moerdijk, I., 1992, "Снопи в геометрията и логиката", Ню Йорк: Спрингер.
  • Maietti, ME, Sambin, G., 2005, „Към минималистична фондация за конструктивна математика“, в „От набори и типове към топология и анализ: към практически основи за конструктивна математика (Оксфордски логически пътеводители 48), L. Crosilla и P Шустер (ред.), Оксфорд: University Oxford Press.
  • Майет, ME, 2009, „Минималистична основа на две нива за конструктивна математика“, Анали на чистата и приложна логика, 160 (3): 319–354.
  • Martin-Löf, P., 1975, „Интуиционистична теория за типовете: предикативна част“, в Н. Е. Роуз и Дж. Шепърдсън (ред.), Логически колоквиум '73, Амстердам: Северна Холандия, с. 73–118.
  • –––, 1984, „Интуиционистична теория на типа“, Неапол: Библиополис.
  • McCarty, DC, 1984, „Реализируемост и рекурсивна математика“, D. Phil. Дисертация, Философия, Оксфордски университет.
  • –––, 1986, „Теория за реализируемост и рекурсивна съвкупност“, Анали на чистата и приложна логика, 32: 153–183.
  • Myhill, J., 1973, „Някои свойства на интуиционистичната теория на множествата Zermelo-Fraenkel“, в Proceedings of Summer Cambridge Summer School of Mattematic Logic от 1971 г. (Бележки от лекции по математика 337), ARD Mathias и H. Rogers (ред.), Берлин: Спрингер, стр. 206–231.
  • –––, 1975 г., „Теория на конструктивните множества“, сп. „Символична логика“, 40: 347–382.
  • van Oosten, J., 1990, „Реализируемостта на Лифшиц“, The Journal of Symbolic Logic, 55: 805–821.
  • Пауъл, У., 1975, „Разширяване на отрицателната интерпретация на Гьодел към ZF“, Journal of Symbolic Logic, 40: 221–229.
  • Ратижен, М., Грифор, Е. и Палмгрен, Е., 1998, „Недостъпност в конструктивната теория на множествата и теорията на типа“, Анали на чистата и приложна логика, 94: 181–200.
  • Rathjen, М., 1999, „Царството на порядковия анализ“, в „Набори и доказателства“(Записки на лекциите на Лондонското математическо общество 258), Cambridge: Cambridge University Press, стр. 219–279.
  • –––, 2003, „Аксиомата против основите в теориите за конструктивни множества“, в игри, логика и конструктивни набори (CSLI Lecture Notes 161), Stanford: CSLI Publication, стр. 87–108.
  • –––, 2003a, „Реализиране на теорията на множествата на Mahlo в теорията на типа“, Архив за математическа логика, 42: 89–101.
  • –––, 2004, „Предсказуемост, кръгова способност и анти-основа“, в сто години от парадокса на Ръсел (Логика и приложенията му 6), G. Link (съст.), Берлин: de Gruyter, стр. 191–219,
  • –––, 2005, „Замяна срещу колекция и свързани теми в конструктивната теория на множествата на Зермело-Френкел“, Анали на чистата и приложна логика, 136: 156–174.
  • –––, 2005a, „Конструктивната програма на Хилберт и границите на теорията на типа Мартин-Льоф“, Synthese, 147: 81–120.
  • –––, 2005b, „Дисюнкцията и свързаните свойства за конструктивната теория на множествата на Zermelo-Fraenkel“, Journal of Symbolic Logic, 70 (4): 1232–1254.
  • –––, 2006 г., „Принципи на избор в теории на конструктивните и класическите множества“, Логически колоквиум '02 (Бележки от лекции в логиката 27), Z. Chatzidakis, P. Koepke и W. Pohlers (ред.), Wellesley, Massachusetts: AK Peters, 299–326.
  • –––, 2006a, „Реализируемост на конструктивната теория на множествата на Зермело-Френкел“, в Logic Colloquium '03 (Бележки от лекции в логиката 24), V. Stoltenberg-Hansen и J. Väänänen (ред.), Wellesley, Massachusets: AK Peters, с. 282–314.
  • –––, 2006b, „Теории и наредби в теорията на доказателствата“, Synthese, 148 (3): 719–743.
  • –––, 2008, „Естествените числа в теорията на конструктивните множества“, Математическа логика, Квартал, 54: 287–312.
  • –––, 2012, „От слабото към силното съществуване”, Анали на чистата и приложна логика, 163: 1400–1418.
  • –––, 2012b, „Конструктивна теория на множествата на Зермело-Френкел, теоретичен набор и изчисление на конструкциите“, в „Епистемология срещу онтологията: есета за философията и основите на математиката в чест на Пер Мартин-Льоф“(Логика, епистемология и серията „Съединение на науката“, П. Dybjer, S. Lindström, E. Palmgren и G. Sundhölm (ред.), Ню Йорк и Дордрехт: Springer Verlag.
  • –––, 2017, „Теория на доказателствата на конструктивните системи: индуктивни типове и едноличие“, в G. Jäger и W. Sieg (ред.), Feferman on Funditions (Изключителен принос към логиката: том 13), Cham: Springer, с. 385–419.
  • Ричман, Ф., 2000, „Основната теорема за алгебрата: конструктивно развитие без избор“, Pacific Journal of Mathematics, 196: 213–230.
  • –––, 2001, „Конструктивна математика без избор“, в „Съединяване на антиподите: конструктивни и нестандартни възгледи на континуума“(Синтезна библиотека 306), P. Schuster и др. (изд.), Dordrecth: Kluwer, стр. 199–205.
  • Ръсел, Б., 1908, „Математическа логика, основана на теорията на типовете“, American Journal of Mathematics, 30: 222–262. Препечатано в Van Heijenoort (1967), 150–182.
  • Щедров, А., 1981, „Последователност и независимост води до интуиционистична теория на множествата“в Конструктивна математика (Бележки от лекции по математика 873), Ф. Ричман (съст.), Берлин: Спрингер, с. 54–86.
  • –––, 1982 г., „Независимост на теоремата на вентилатора при наличието на принципи за приемственост“в Симпозиума за столетни периоди от LEJ Brouwer, AS Troelstra и D. van Dalen (ред.), Амстердам: Северна Холандия, стр. 435–442,
  • –––, 1985, „Интуиционистична теория на множествата“в изследванията на Харви Фридман за основите на математиката, LA Garrubgtib et al. (ред.), Амстердам: Elsevier.
  • Schütte, K., 1965, „Предсказуеми поредни поредици“, във „Формални системи и рекурсивни функции“, J. Crossley и M. Dummett (ред.), Амстердам: Северна Холандия, с. 279–302.
  • –––, 1965a, „Eine Grenze für die Beweisbarkeit der Transfiniten Induktion in der verzweigten Typenlogik“, Archiv für matematiche Logik und Grundlagenforschung, 7: 45–60.
  • Симпсън, А., 2005, „Теории за конструктивни множества и техните теоретично-теоретични модели за категорията“, в „От набори и типове до топология и анализ: към практически основи за конструктивна математика (Оксфордски логически пътеводители 48“), Л. Кросила и П. Шустер (изд.), Оксфорд: University of Oxford.
  • Swan, AW, 2014, „CZF няма свойството за съществуване“, Annals of Pure and Applied Logic, 165: 1115–1147.
  • Troelstra, AS и van Dalen, D., 1988, Конструктивизъм в математиката (два тома), Амстердам: Северна Холандия.
  • Tupailo, S., 2003, „Реализиране на теорията на конструктивните множества в явната математика: долна граница за непредсказуема Mahlo вселена“, Annals of Pure and Applied Logic, 120: 165–196.
  • Воеводски, В., 2015, „Експериментална библиотека от формализирана математика, основана на еднолични основи“, Математически структури в компютърните науки, 25: 1278–1294.
  • Weyl, H., 1918, “Das Kontinuum. Kritische Untersuchungen über die Grundlagen der Analysis”, Veit, Лайпциг.
  • Ziegler, Albert, 2012, „Обобщаване на реализуеми и хейтинг модели за теория на конструктивните множества“, Annals of Pure and Applied Logic, 163 (2): 175–184.
  • –––, 2014, „Кумулативна йерархия от множества за теория на конструктивните множества“, Математическа логика, Квартал, 60 (1-2): 21–30.

Академични инструменти

сеп човек икона
сеп човек икона
Как да цитирам този запис.
сеп човек икона
сеп човек икона
Вижте PDF версията на този запис в Дружеството на приятелите на SEP.
inpho икона
inpho икона
Разгледайте тази тема за вписване в интернет философския онтологичен проект (InPhO).
Фил хартия икона
Фил хартия икона
Подобрена библиография за този запис в PhilPapers, с връзки към неговата база данни.

Други интернет ресурси

  • Aczel, P. and M. Rathjen, 2010, Бележки за теорията на конструктивните множества, чернова на книги, достъпна онлайн.
  • Kapulkin, C. и PL Lumsdaine, 2012, „Опростен модел на еднолични основи (след Воеводски)“, предпечат на arXiv.org.
  • Теория на алгебраичните множества, от С. Аудей (Карнеги Мелън).

[Моля, свържете се с автора с допълнителни предложения.]

Препоръчано: