Teorie De Seturi: ZF Constructiv și Intuițional

Cuprins:

Teorie De Seturi: ZF Constructiv și Intuițional
Teorie De Seturi: ZF Constructiv și Intuițional

Video: Teorie De Seturi: ZF Constructiv și Intuițional

Video: Teorie De Seturi: ZF Constructiv și Intuițional
Video: Albert Visser. What is Goedel’s Second Incompleteness Theorem? 2024, Martie
Anonim

Navigare la intrare

  • Cuprins de intrare
  • Bibliografie
  • Instrumente academice
  • Prieteni PDF Previzualizare
  • Informații despre autor și citare
  • Inapoi sus

Teorie de seturi: ZF constructiv și intuițional

Publicat pentru prima dată vineri 20 februarie 2009; revizuire de fond miercuri, 13 februarie 2019

Teoriile constructive și intuiționale ale seturilor Zermelo-Fraenkel sunt teorii axiomatice ale mulțimilor în stilul teoriei seturilor Zermelo-Fraenkel (ZF), care se bazează pe logica intuiționalistă. Acestea au fost introduse în anii 1970 și reprezintă un context formal în cadrul căruia se pot codifica matematica bazată pe logica intuiționalistă (a se vedea intrarea despre matematica constructivă). Acestea sunt formulate pe limbajul standard de prim ordin al teoriei seturilor Zermelo-Fraenkel și nu folosesc în mod direct ideile constructive inerente. Lucrând în ZF constructiv și intuițional, ne putem baza astfel într-o oarecare măsură pe familiaritatea noastră cu ZF și cu euristica sa.

În pofida asemănărilor cu teoria clasică a seturilor, conceptele de set definite de teoriile de seturi constructive și intuiționale diferă considerabil de cea a tradiției clasice; se deosebesc și ele unul de celălalt. Tehnicile utilizate pentru a lucra în cadrul acestora, precum și pentru a obține rezultate metamatematice despre ele, de asemenea, se abateră din anumite aspecte de tradiția clasică datorită angajamentului lor pentru logica intuiționalistă. De fapt, așa cum este obișnuit în setările intuiționale, o multitudine de metode semantice și de probă teoretică sunt disponibile pentru studiul teoriilor de seturi constructive și intuiționale.

Această intrare prezintă principalele caracteristici ale teoriilor de seturi constructive și intuiționale. Pe măsură ce domeniul se extinde într-un ritm rapid, nu putem decât să amintim pe scurt câteva aspecte cheie ale rezultatelor și tehnicilor disponibile. Ne concentrăm mai mult pe teoria constructivă a seturilor pentru a evidenția probleme fundamentale importante care apar în cadrul acesteia. Rețineți că omitem o parte vizibilă a literaturii despre ZF constructiv și intuițional, care se referă la interpretările lor categorice. Acest domeniu a cunoscut evoluții majore de-a lungul anilor, atât de mult încât un tratament adecvat al acestui progres ar necesita o extindere substanțială a acestei intrări. Cititorul interesat ar putea dori să consulte rubrica despre teoria categoriilor și referințele sale (a se vedea, de asemenea, suplimentul Ghidului de lectură programatică).

  • 1. Esența teoriei seturilor constructive și intuiționale

    • 1.1 Libertatea axiomatică
    • 1.2 Teorie de seturi constructive versus intuitiviste
    • 1.3 Predicativitatea în teoria constructivă a seturilor

      • 1.3.1 Impredicativitatea separării
      • 1.3.2 Impredicativitatea puterii
      • 1.3.3 Universul constructiv al seturilor
  • 2. Origini ale teoriilor de seturi constructive și intuiționale
  • 3. Sistemele Axioms CZF și IZF
  • 4. Principiile de alegere constructivă
  • 5. Teoria probei și semantica ZF constructiv și intuițional

    • 5.1 Puterea teoretică a probei
    • 5.2 Seturi mari în ZF constructiv și intuițional
    • 5.3 Proprietăți metamatematice ale ZF constructive și intuiționale și tehnici semantice

      • 5.3.1 Proprietățile de disjuncție și existență ale ZF constructive și intuiționale
      • 5.3.2 Realizare
      • 5.3.3 Modele Kripke și semantică apreciată de Heyting
      • 5.3.4 Modele categorice ale teoriei de seturi constructive și intuiționale
      • 5.4 Variante de teorii de seturi constructive și intuiționale: teorii de set cu corelații și teorii de seturi care nu sunt extensibile
  • Bibliografie
  • Instrumente academice
  • Alte resurse de internet
  • Intrări conexe

1. Esența teoriei seturilor constructive și intuiționale

Teoriile de seturi constructive și intuiționale Zermelo-Fraenkel sunt bazate pe logica intuiționalistă decât pe cea clasică și reprezintă un mediu natural în care să codificăm și studiem matematica bazată pe logica intuiționalistă. Pentru ZF constructiv, principalul obiectiv a fost reprezentarea practicii matematice a Bishop (Bishop 1967, Bishop and Bridges 1985).

Pentru conceptele de bază și ideile motrice ale logicii intuiționale, matematicii constructive și intuiționismului, cititorul poate dori să consulte următoarele intrări:

  • logică intuiționalistă,
  • dezvoltarea logicii intuiționale,
  • matematica constructiva,
  • intuiționismul în filozofia matematicii,
  • Luitzen Egbertus Jan Brouwer.

Pentru teoria seturilor clasice, a se vedea intrarea pe teoria seturilor.

ZF constructiv și intuiționalist se bazează pe același limbaj de prim ordin ca teoria clasică a seturilor ZF, care are doar simbolul predicatului binar (in) (apartenența) ca simbol non-logic. Adică sunt formulate pe baza unei logici intuitiviste de prim ordin cu egalitate, plus simbolul predicatului binar (in). Putem profita astfel de simplitatea limbajului teoretic și de familiaritatea cu acesta (Myhill 1975). Ca și în cazul matematicii constructive în stil episcop, ZF constructiv și intuiționalist sunt compatibile cu tradiția clasică, în sensul că toate teoremele lor sunt adevărate clasic. De fapt, cele două sisteme formale pe care le vom avea în vedere, Constructive Zermelo-Fraenkel (CZF) și Intuționist Zermelo-Fraenkel (IZF),da naștere la ZF complet clasic prin adăugarea simplă a principiului mijlocului exclus.

1.1 Libertatea axiomatică

Teoria seturilor clasice Zermelo-Fraenkel se bazează pe logica predicatelor clasice de prim ordin cu egalitatea. Pe deasupra principiilor logice se află axiomele și schemele care descriu noțiunea de set pe care codifica teoria. Aceste principii pot fi clasificate în trei tipuri. În primul rând, există principii care ne permit să formăm seturi noi din cele date. De exemplu, axioma perechei ne permite să formăm un set care este perechea a două seturi date. În al doilea rând, există principii care stabilesc proprietățile structurii teoretice stabilite. De exemplu, axioma extensionalității identifică toate seturile care au aceleași elemente. În al treilea rând, și în sfârșit, există axiome care afirmă existența unor seturi specifice. Astfel, axioma infinitului afirmă că există un set infinit. Toate aceste principii sunt de obicei numite principii teoretice.

Atunci când introducem versiuni de ZF bazate pe logica intuiționalistă, primul pas este eliminarea din logică a principiului mijlocului exclus (EM). Următorul pas este alegerea unui stoc bun de principii teoretice, care să reprezinte fidel noțiunea dorită de ansamblu constructiv. Aceste sarcini se dovedesc a fi mai provocatoare decât s-ar fi putut aștepta la început. De fapt, după cum se știe, sistemele bazate pe o logică „mai slabă” au capacitatea de a distinge între enunțuri echivalente din punctul de vedere al unei logici „mai puternice”. În cazul teoriei de seturi, unele dintre axiomele sau schemele ZF sunt adesea prezentate de una dintre multe formulări clasice echivalente. În mod clasic, este doar o problemă de comoditate pe care să o utilizați la un moment dat. Când lucrați pe baza logicii intuiționale,diverse formulări ale unui axiom clasic se pot dovedi a fi distincte (neechivalente). De fapt, se pot avea în vedere noile afirmații care sunt în mod clasic echivalente cu un axiom ZF, dar care se separă intuițional de acesta (de exemplu, axioma de colecție a subseturilor CZF (Aczel 1978)).

În ceea ce privește primul pas, constând în eliminarea principiului de mijloc exclus din logică, se dovedește că pur și simplu evacuarea acestui principiu din logica de bază este insuficientă; adică nu este suficient să luăm baza noastră intuiționalistul decât calculul predicatului clasic. De asemenea, trebuie să ne asigurăm că axiomele teoretice stabilite nu aduc forme nedorite ale mijlocului exclus înapoi în teoria noastră. De exemplu, după cum a menționat Myhill (1973), avem nevoie de o grijă suplimentară în alegerea unei afirmații adecvate pentru axioma fondării. Fundația este introdusă în teoria seturilor pentru a exclude seturile care sunt membre ale lor și astfel (in) - lanțuri de seturi. Formularea obișnuită a fundației afirmă că fiecare set locuit (un set cu cel puțin un element) are cel puțin un element în ceea ce privește relația de membru. Această afirmație, cu toate acestea,poate fi arătat că dă cazuri constructive inacceptabile de mijloc exclus pe baza unor ipoteze modeste-teoretice. Prin urmare, formularea obișnuită a fundației trebuie omisă dintr-o teorie de seturi bazată pe logica intuiționalistă. Pentru o dovadă, consultați documentul suplimentar:

Principii teoretice stabilite incompatibile cu logica intuiționalistă.

Mișcarea tipică în formularea teoriilor setului bazate pe logica intuiționalistă este apoi să înlocuim fundația cu schema clasică echivalentă a inducției setate, care nu are aceleași „efecte secundare”, dar are consecințe similare. [1]

În ceea ce privește cel de-al doilea pas, legat de selecția unui bun stoc de principii teoretice stabilite, schemele de înlocuire și separare și axiomul setului de putere au atras cea mai mare atenție. Pentru formularea exactă a acestor principii, a se vedea documentul suplimentar:

Axiomele CZF și IZF.

Aici următorul este un scenariu tipic. Având în vedere care sunt în mod clasic două variante ale unui singur principiu teoretic de set, dovada lor de echivalență clasică necesită la un moment dat o instanță a mijlocului exclus. Cu toate acestea, în general, această dovadă a echivalenței nu va duce la un context intuițional și, prin urmare, ceea ce sunt clasic două forme ale unui singur principiu poate rezulta în două principii distincte atunci când lucrează intuițional. Alegerea unuia decât a celuilalt poate influența deci noțiunea de set pe care o definim astfel. În contextul teoriilor de seturi constructive precum CZF, setul de putere și separarea sunt înlocuite de principii mai slab intuițional. Un motiv pentru acest lucru este că forța deplină a setului de putere și separarea completă sunt considerate inutile,întrucât înlocuitorii lor mai slabi par să fie suficienți pentru efectuarea unei matematici constructive. Un alt motiv este acela că sunt văzuți ca fiind filozofici, deoarece pot introduce forme de impredicativitate în teoria seturilor (vezi secțiunea despre Predicativitate în teoria constructivă a seturilor). Cazul înlocuirii versus colecția este oarecum mai complex (a se vedea, de exemplu, articolele (Friedman și Scedrov 1985), (Rathjen 2005) și (Rathjen 2012)). Merită subliniat faptul că, deși adoptăm formularea obișnuită a fundației, este contrar asumării logicii intuiționale ca logică de fundal, principiile separării și setului de putere nu au deloc incompatibilitate cu logica intuițională, atât de mult încât fac parte integrantă a teoria intuiționalistă a seturilor IZF (Friedman 1973a). Un alt motiv este acela că sunt văzuți ca fiind filozofici, deoarece pot introduce forme de impredicativitate în teoria seturilor (vezi secțiunea despre Predicativitate în teoria constructivă a seturilor). Cazul înlocuirii versus colecția este oarecum mai complex (a se vedea, de exemplu, articolele (Friedman și Scedrov 1985), (Rathjen 2005) și (Rathjen 2012)). Merită subliniat faptul că, deși adoptăm formularea obișnuită a fundației, este contrar asumării logicii intuiționale ca logică de fundal, principiile separării și setului de putere nu au deloc incompatibilitate cu logica intuițională, atât de mult încât fac parte integrantă a teoria intuiționalistă a seturilor IZF (Friedman 1973a). Un alt motiv este acela că sunt văzuți ca fiind filozofici, deoarece pot introduce forme de impredicativitate în teoria seturilor (vezi secțiunea despre Predicativitate în teoria constructivă a seturilor). Cazul înlocuirii versus colecția este oarecum mai complex (a se vedea, de exemplu, articolele (Friedman și Scedrov 1985), (Rathjen 2005) și (Rathjen 2012)). Merită subliniat faptul că, deși adoptăm formularea obișnuită a fundației, este contrar asumării logicii intuiționale ca logică de fundal, principiile separării și setului de putere nu au deloc incompatibilitate cu logica intuițională, atât de mult încât fac parte integrantă a teoria intuiționalistă a seturilor IZF (Friedman 1973a).deoarece pot introduce forme de impredicativitate în teoria seturilor (vezi secțiunea despre Predicativitate în teoria constructivă a seturilor). Cazul înlocuirii versus colecția este oarecum mai complex (a se vedea, de exemplu, articolele (Friedman și Scedrov 1985), (Rathjen 2005) și (Rathjen 2012)). Merită subliniat faptul că, deși adoptăm formularea obișnuită a fundației, este contrar asumării logicii intuiționale ca logică de fundal, principiile separării și setului de putere nu au deloc incompatibilitate cu logica intuițională, atât de mult încât fac parte integrantă a teoria intuiționalistă a seturilor IZF (Friedman 1973a).deoarece pot introduce forme de impredicativitate în teoria seturilor (vezi secțiunea despre Predicativitate în teoria constructivă a seturilor). Cazul înlocuirii versus colecția este oarecum mai complex (a se vedea, de exemplu, articolele (Friedman și Scedrov 1985), (Rathjen 2005) și (Rathjen 2012)). Merită subliniat faptul că, deși adoptăm formularea obișnuită a fundației, este contrar asumării logicii intuiționale ca logică de fundal, principiile separării și setului de putere nu au deloc incompatibilitate cu logica intuițională, atât de mult încât fac parte integrantă a teoria intuiționalistă a seturilor IZF (Friedman 1973a). Merită subliniat faptul că, deși adoptăm formularea obișnuită a fundației, este contrar asumării logicii intuiționale ca logică de fundal, principiile separării și setului de putere nu au deloc incompatibilitate cu logica intuițională, atât de mult încât fac parte integrantă a teoria intuiționalistă a seturilor IZF (Friedman 1973a). Merită subliniat faptul că, deși adoptăm formularea obișnuită a fundației, este contrar presupunerii logicii intuiționale ca logică de fundal, principiile separării și setului de putere nu au deloc incompatibilitate cu logica intuiționalistă, atât de mult încât fac parte integrantă a teoria intuiționalistă a seturilor IZF (Friedman 1973a).

Pentru a rezuma, formulând o teorie de seturi bazată pe logica intuiționalistă, prima sarcină este de a expulza principiul mijlocului exclus, inclusiv acele cazuri ale acestuia care ar putea fi ascunse în formulări familiare ale axiomelor teoretice. Următoarea sarcină este alegerea unei versiuni a fiecărui principiu clasic care caracterizează cel mai bine noțiunea dorită de set. Aceasta deschide o serie de alegeri pe care le puteți face, deoarece o multitudine de principii intuiționale pot corespunde unui singur principiu clasic. Trebuie subliniat că, din punct de vedere constructiv, această multitudine de opțiuni (și astfel sisteme), mai degrabă decât să provoace neliniște, este o situație extrem de dorită, deoarece constituie o formă de „libertate axiomatică”. De exemplu, ne permite să diferențiem între o serie de noțiuni matematice, astfel captând mai bine intuițiile noastre despre ele ca fiind distincte. De asemenea, ne oferă libertatea de a alege noțiunile și teoriile care se potrivesc cel mai bine unui context dat. În plus, adoptând logica intuiționalistă, putem include în teoriile noastre principii care sunt foarte puternice din punct de vedere clasic, fără a fi nevoie să ne angajăm în puterea lor clasică. De exemplu, se poate adăuga o noțiune de set inaccesibil unei teorii de seturi constructive slabe și se poate obține o teorie predicativă, în timp ce aceeași noțiune încorporată într-un context clasic devine extrem de puternică (vezi secțiunile despre Predicativitate în teoria constructivă a seturilor și seturi mari în constructive și intuițional ZF). În cele din urmă, apare o zonă bogată de studiu (meta-teoretic) al relațiilor dintre sistemele-teoretice distincte rezultate. După cum ne-am putea aștepta, această libertate are și un preț,deoarece un studiu extrem de tehnic al teoriilor axiomatice ar putea fi necesar pentru a distinge principiile lor, precum și pentru a dezvălui unele dintre subtilitățile lor. Acest lucru poate fi din nou văzut ca un avantaj, deoarece ne obligă la o analiză mai profundă și mai clară a noțiunilor matematice implicate și ne invită să dezvoltăm noi instrumente sofisticate.

1.2 Teorie de seturi constructive versus intuitiviste

Deși există multe sisteme de seturi bazate pe logica intuiționalistă, putem distinge două tendințe principale din literatura de specialitate. Conform primului, luăm tot ce este disponibil în teoria clasică a seturilor ZF și modificăm doar acele principii, cum ar fi fundamentul, care au o incompatibilitate clară cu logica intuiționalistă. Acest lucru dă naștere la teorii setate, cum ar fi Intuționistul Zermelo-Fraenkel, IZF, a cărui variantă a fost introdusă încă din (Friedman 1973a). (A se vedea Beeson 1985, Capitolele 8 și 9 și Scedrov 1985 pentru două sondaje asupra IZF.) Motivul din spatele acestor teorii pare să fie acordarea matematicianului a celor mai puternice instrumente posibile, atât timp cât se păstrează compatibilitatea cu logica intuiționalistă. Conform celei de-a doua abordări,Pe lângă aderarea la logica intuiționalistă, introducem și restricții la principiile teoretice stabilite admise, în măsura în care sistemul rezultat se conformează practicii matematice constructive. Astfel, teoriile de acest fel pot fi văzute ca rezultatul unui dublu proces de restricție în ceea ce privește ZF clasic. Mai întâi există o restricție la logica intuiționalistă, apoi o restricție este impusă construcțiilor teoretice permise. Acesta din urmă este motivat de (1) observația că principiile mai slabe par suficiente pentru practica matematică constructivă și (2) dorința de a adera la o formă de predicativitate (vezi secțiunea următoare pentru o clarificare a acestei noțiuni de predicativitate). Exemple paradigmatice de sisteme din urmă sunt teoria constructivă a lui Myhill (Myhill 1975),Sistemul B al lui Friedman (Friedman 1977) și Teoria de seturi constructivă a lui Aczel Zermelo-Fraenkel CZF (Aczel 1978; 1982; 1986, Aczel și Rathjen 2001; Aczel și Rathjen 2010, Alte resurse de internet). Putem spune, de asemenea, că în această a doua abordare motivația fundamentală influențează practica într-un grad mai mare.

În cele ce urmează, folosim o convenție care este adesea în vigoare astăzi, conform căreia adjectivul „intuiționalist” se referă la acele teorii stabilite, cum ar fi IZF, care sunt impredicative, în timp ce „constructiv” se referă la teorii stabilite, cum ar fi CZF, care respectă o formă de predicativitate. Rețineți, însă, că această convenție nu este întotdeauna urmată în literatura de specialitate. De fapt, adjectivul „constructiv” a fost folosit și pentru a denumi teoriile impredicative și „intuiționist” pentru a se referi la teorii fundamentale predicative, cum ar fi teoria tipului Martin-Löf (Martin-Löf 1975; 1984). De remarcat, de asemenea, că prezenta convenție privind utilizarea cuvintelor „constructiv” și „intuiționalist” diferă de cea făcută în contextul matematicii constructive (a se vedea, de exemplu, intrarea despre matematica constructivă și, de asemenea, Bridges și Richman, 1987).

1.3 Predicativitatea în teoria constructivă a seturilor

Predicativismul își are originea în scrierile lui Poincaré și Russell, care au răspuns la paradoxurile care au fost descoperite în teoriile de set ale lui Cantor și Frege la începutul secolului XX. Ulterior, Weyl a adus contribuții fundamentale la studiul matematicii predicative (Weyl 1918, vezi și Feferman 1988). Conform unei noțiuni, o definiție este impredicativă dacă definește un obiect prin referire la o totalitate care include obiectul care trebuie definit. Cu Principiul său Vicious Circle (VCP), Russell a intenționat să elimine circularitatea în matematică care rezultă din astfel de definiții impredicative. Russell a prezentat diverse formulări ale VCP, dintre care una este:

Orice conține o variabilă aparentă nu trebuie să fie o valoare posibilă a acestei variabile (Russell 1908, în van Heijenoort 1967, 163).

Analiza fundamentală a predicativității lui Poincaré, Russell și Weyl a deschis calea pentru o varietate de analize logice ale noțiunii. Analiza cea mai frecvent acceptată se datorează Feferman și Schütte (în mod independent) urmând liniile indicate de Kreisel (Kreisel 1958, Feferman 1964 și Schütte 1965; 1965a). Aici teoria probelor a jucat un rol esențial. În termeni foarte grosolani, ideea era să deslușească o colecție de teorii (o progresie transfinită a sistemelor de aritmetică ramificată de ordinul doi indexate de ordinale) prin intermediul căreia să caracterizezi o anumită noțiune de predicativ ordinal. Analiza teoretică a acestor teorii a lui Feferman și Schütte a identificat un ordinal, denumit în mod obișnuit (Gamma_0), care este cel mai puțin predicativ ordinal conform acestei noțiuni. Un sistem formal este considerat predicativ justificabil dacă este teoretic reductibil la un sistem de ramificată artimetică de ordinul secundar indexat de un ordinal mai puțin de (Gamma_0). Prin urmare, în teoria probelor (Gamma_0) este de obicei considerat ca reprezentând limita predicativității. (Vedeți Feferman 2005 pentru o prezentare informală mai exactă a acestei noțiuni de predicativitate și pentru alte referințe. A se vedea și Crosilla 2017. Cititorul poate consulta și secțiunea despre predicativism în intrarea despre filosofia matematicii și intrarea despre paradoxuri și logică contemporană).(Vedeți Feferman 2005 pentru o prezentare informală mai exactă a acestei noțiuni de predicativitate și pentru alte referințe. A se vedea și Crosilla 2017. Cititorul poate consulta și secțiunea despre predicativism în intrarea despre filosofia matematicii și intrarea despre paradoxuri și logică contemporană).(Vedeți Feferman 2005 pentru o prezentare informală mai exactă a acestei noțiuni de predicativitate și pentru alte referințe. A se vedea și Crosilla 2017. Cititorul poate consulta și secțiunea despre predicativism în intrarea despre filosofia matematicii și intrarea despre paradoxuri și logică contemporană).

Pentru teoriile fundamentale constructive a fost sugerată o abordare mai „liberală” a predicativismului, pornind de la lucrarea de la sfârșitul anilor 1950 la Lorenzen, Myhill și Wang (vezi de exemplu Lorenzen și Myhill 1959). Ideea motrice este că așa-numitele definiții inductive ar trebui să fie permise pe tărâmul matematicii constructive. Justificarea intuitivă a definițiilor inductive este legată de faptul că acestea pot fi exprimate prin reguli finite, într-un mod „de jos în sus”. Puterea teoretică a teoriilor definițiilor inductive depășește cu mult Feferman și legătura lui Schütte (Buchholz, Feferman, Pohlers și Sieg 1981). Astfel, teoriile relativ puternice sunt considerate predicative în fundamentele de astăzi ale matematicii constructive. Această noțiune mai liberală de predicativitate a fost adesea denumită predicativitate generalizată. În această intrare scriem pur și simplu predicativitate pentru predicativitate generalizată și numim predicativitate având în vedere numerele naturale forma mai cunoscută de predicativitate care apare în contextul clasic și a fost analizată de Kreisel, Feferman și Schütte.

Un exemplu de teorie predicativă în acest sens este teoria constructivă a seturilor CZF, întrucât puterea sa teoretică este aceeași cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Sistemul IZF, în schimb, este impredicativ, întrucât puterea sa teoretică este echivalentă cu cea a întregului ZF clasic (Friedman 1973a).

În teoriile de seturi bazate pe logica intuiționalistă, predicativitatea se realizează, de regulă, prin restrângerea principiilor de separare și set de putere, întrucât acestea par a fi principalele surse de impredicativitate (atunci când se presupune axiomul infinit).

1.3.1 Impredicativitatea separării

Schema de separare ne permite să formăm un subset al unui set dat ale cărui elemente satisfac o proprietate dată (exprimată de o formulă în limbajul teoriei de seturi). Având în vedere un set (B) și o formulă (phi (X)), separarea ne permite să construim un set nou, setul de elemente (X) din (B) pentru care (phi) deține. Aceasta este de obicei reprezentată informal ca: ({X / in B: / phi (X) }). Separarea poate duce la impredicativitate în cazul în care formula (phi) conține cantificatori nelimitați care se întind pe întregul univers de seturi; de fapt, în definirea noului set prin separare, ne putem referi la acest set, contrazicând VCP-ul lui Russell. De exemplu, dacă definim un set (C) prin separare ca ({X / in B: / forall Y / psi (X, Y) }), atunci (C) se află printre (Y) este necesar să fie verificat pentru proprietatea (psi). Această formă de impredicativitate este evitată în teoria constructivă a seturilor prin restrângerea schemelor de separare: prin necesitatea ca toate cantificatoarele care apar în formula (phi) să se extindă numai pe seturi „construite anterior”. Din punct de vedere sintactic, acest lucru înseamnă că, dat fiind un set (B), putem forma un set nou ({X / in B: / phi (X) }) prin separare numai dacă toți cuantificatorii din (phi) sunt delimitate; adică numai dacă toți cantificatorii din (phi) au forma (forall X (X / in Y / rightarrow / ldots)) sau (există X (X / in Y / wedge / ldots)), pentru un set (Y).\ phi (X) }) prin separare numai dacă toți cuantificatorii din (phi) sunt delimitați; adică numai dacă toți cantificatorii din (phi) au forma (forall X (X / in Y / rightarrow / ldots)) sau (există X (X / in Y / wedge / ldots)), pentru un set (Y).\ phi (X) }) prin separare numai dacă toți cuantificatorii din (phi) sunt delimitați; adică numai dacă toți cantificatorii din (phi) au forma (forall X (X / in Y / rightarrow / ldots)) sau (există X (X / in Y / wedge / ldots)), pentru un set (Y).

Putem vedea că constrângerea separării în acest fel evită impredicativitatea, observând că dovada puterii teoretice a CZF, care are doar separare restricționată, se încadrează în domeniul predicativității. Cu toate acestea, prin adăugarea unei separații complete la CZF, se obține o teorie impredicativă, de fapt, una cu aceeași rezistență teoretică a probelor ca și aritmetica de ordinul II complet (Lubarsky 2006). A se vedea, de asemenea, secțiunea 5 pentru o discuție despre rolul teoriei dovezilor în analiza teoriilor de seturi constructive și intuiționale.

1.3.2 Impredicativitatea puterii

Axioma setului de putere ne permite să formăm un set de toate subseturile unui set dat. Un exemplu de utilizare impredicativă a setului de putere este dat de definiția unui subset al numerelor naturale, (N), după cum urmează: (B: = {n / in N: / forall C / subseteq N / phi (n, C) }), unde (phi) poate fi considerată o formulă delimitată. Aici apare o formă de circularitate, deoarece (B) în sine se numără printre subseturile (N) care trebuie verificate pentru (phi). După cum subliniază Myhill (1975, 354), setul de putere este greu de justificat din punct de vedere constructiv: adună toate ansamblurile unui set dat, dar nu prescrie o regulă care „construiește” setul dat anterior. seturi, după cum pare să necesite predicativitatea.

Myhill scrie:

Setul de puteri pare mai ales neconstructiv și impredicativ în comparație cu celelalte axiome: nu implică, așa cum fac și ceilalți, unirea sau desprinderea unor seturi pe care unul le-a construit deja, ci mai degrabă selectarea din totalitatea tuturor seturilor pe cele care stau în relația de includere într-un set dat. (Myhill 1975, 351).

Setul de puteri pare deosebit de problematic în cazul seturilor infinite, întrucât „nu avem nici o idee despre ce este un subset arbitrar al unui set infinit; nu există nici o modalitate de a le genera pe toate și, prin urmare, nu avem nicio modalitate de a forma setul tuturor ei”(Myhill 1975, 354). În consecință, pare să nu existe o modalitate de a da un sens constructiv ansamblului tuturor subseturilor unui set infinit.

Myhill observă crucial că setul de putere nu este necesar pentru matematica constructivă în stil episcop, deoarece poate fi înlocuit cu una dintre consecințele sale. Acesta este adesea numit axiom de exponențiere al lui Myhill și afirmă că putem forma un set de funcții de la un set dat la altul. Acest axiom este în mod clar echivalent cu puterea setată într-un context clasic, unde subseturile unui set dat pot fi reprezentate de funcții caracteristice. În absența principiului mijlocului exclus, totuși, setul de putere și exponențiarea nu sunt echivalente. Observația fundamentală a lui Myhill este că exponenția este suficientă pentru a efectua matematica lui (Bishop 1967); de exemplu, permite construirea numerelor reale (Cauchy) în cadrul teoriei constructive a seturilor. Myhill susține că exponențiarea este semnificativă din punct de vedere constructiv, deoarece o funcție este o regulă,un obiect finit care poate fi dat de fapt.

De asemenea, el scrie că cazul setului de putere este diferit de cel al exponențierii, deoarece:

chiar și în cazul seturilor infinite (A) și (B) avem o idee a unei mapări arbitrare de la (A) în (B). O mapare arbitrară de la (mathbf {Z}) în (mathbf {Z}) este o funcție recursivă parțială împreună cu o dovadă că calculul se termină întotdeauna; un cont similar poate fi dat de o funcție reală arbitrară. Nu există nicio explicație corespunzătoare a „subsetului arbitrar”. (Myhill 1975, 354).

Axiomul de exponențiere al lui Myhill face parte acum din toate sistemele majore ale teoriei constructive a seturilor. În cazul CZF, de fapt, unul are o întărire a exponențierii, cunoscută sub denumirea de colectare subset, ceea ce reprezintă și o slăbire a setului de putere. O generalizare a exponențierii poate fi întâlnită și în teoria tipului constructiv.

În cazul CZF, afirmația potrivit căreia adăugarea axiomului setului de putere induce o formă de impredicativitate poate fi demonstrată printr-un rezultat tehnic. Rathjen (2012b) arată că CZF augmentat de axiomul setului de putere depășește puterea teoriei clasice a seturilor Zermelo și astfel adăugarea axiomului setului de putere la CZF ne aduce la o teorie complet impredicativă. Acest lucru arată, de asemenea, că implicația de la setul de putere la colectarea subsetului nu poate fi inversată, deoarece puterea teoretică a CZF este mult mai mică decât cea a set-setului Zermleo. În alți termeni, axiomul setului de putere este mult mai puternic decât exponenția și colectarea subsetului.

1.3.3 Universul constructiv al seturilor

După ce am introdus constrângeri adecvate pentru setarea și separarea puterii, am putea acum să ne confruntăm cu o obiecție substanțială. Teoriile de seturi constructive și intuiționale pot fi văzute ca modificări ale teoriei de seturi clasice ZF care sunt obținute prin: (1) înlocuirea clasicii cu logica intuiționalistă și (2) alegerea cu exactitate, între diverse principii echivalente clasic, pe cele care par mai potrivite pentru scopuri date. De exemplu, am putea alege principii care să fie suficiente pentru a reprezenta o anumită practică matematică, cum ar fi, de exemplu, matematica în stilul episcopului. Noțiunea rezultată de set, însă, ar putea deveni obscură și alegerea principiilor teoretice ale setului ar putea părea într-o anumită măsură ca fiind arbitrară. În cazul ZF intuiționist, se poate justifica alegerea principiilor teoretice stabilite prin examinarea interpretărilor sale semantice,ca semantică Heyting, sau analizând modelele sale categorice. În cazul teoriei constructive a seturilor, pentru a împiedica acest tip de obiecții, Aczel a oferit o interpretare a CZF într-o versiune a teoriei de tip Martin-Löf (Aczel 1978). Afirmația este aceea că un sens clar constructiv este astfel atribuit noțiunii CZF de set, analizând sensul acesteia în teoria tipului Martin-Löf, deoarece acesta din urmă este de obicei considerat ca reprezentând o formulare exactă și complet motivată a unei noțiuni constructive de set. Interpretarea lui Aczel a CZF în teoria tipului constructiv este dată de seturile de interpetare ca arbori din teoria tipurilor. Adică, în teoria constructivă a tipului, universul seturilor de CZF este reprezentat de un tip V, de seturi iterative construite peste univers, U, de tipuri mici (Aczel 1978; Martin-Löf 1984). Această interpretare evidențiază clar predicativitatea (generalizată) a CZF, ale cărei mulțimi pot fi văzute ca arbori construiți inductiv și al căror univers teoretic are și o structură inductivă clară.

Predicativitatea CZF și a sistemelor conexe este în concordanță cu pozițiile filosofice care sunt adesea asociate cu utilizarea logicii intuiționale. În special, s-ar părea că dacă am construi obiectele matematice, de exemplu, dacă obiectele matematice sunt construcții mentale de un fel, atunci recurgerea la definiții impredicative ar produce o formă nedorită de circularitate. Acest lucru contrastează clar cu o vedere adesea asociată cu teoria clasică a seturilor, pentru care activitatea noastră matematică poate fi văzută ca o dezvăluire treptată a proprietăților universului de seturi, a căror existență este independentă de noi. O astfel de viziune este de obicei legată de utilizarea logicii clasice și a impredicativității în studierea universului set-teoretic. Predicativitatea este adesea văzută ca fiind legată de distincția respectată de timp între infinitul real și potențial. Teoriile predicative (și deci, în special, constructive) sunt adesea văzute ca evitând trimiterea la infinitul real și se angajează doar la infinitul potențial (Dummett 2000, Fletcher 2007). Acest lucru pare din nou în particular în armonie cu acele poziții filozofice care evidențiază dimensiunea umană a activității noastre matematice, văzând, de exemplu, obiectele matematice și adevărul afirmațiilor despre ele ca fiind dependente de noi. Un alt aspect legat este adesea privit de predicativitate: dacă universul mulțimilor este construit pe etape de propria noastră activitate matematică, atunci ar fi firesc să o vedem și ca fiind încheiată. Din acest motiv, într-un context constructiv,unde respingerea logicii clasice îndeplinește cerința predicativității, universul seturilor este adesea descris ca un concept deschis, un univers „in fieri”. Această idee este foarte bine exemplificată în special în teoria constructivă a tipului, în care noțiunea de univers teoretic de tip a fost lăsată în mod deliberat deschisă de Per Martin-Löf (prin nu a postulat reguli specifice de eliminare pentru aceasta). Natura deschisă a universului seturilor a deschis calea extinderii acestuia prin principii de reflecție. Acestea au fost cercetate atât în teoria tipului, cât și în teoria constructivă a seturilor. A se vedea (Rathjen 2005a) pentru o anchetă a rezultatelor și o discuție bazată pe teme, precum și secțiunea 5.2. Pentru o analiză formală a universului constructiv al seturilor și o comparație cu ierarhia Von Neumann, a se vedea (Ziegler 2014).universul seturilor este adesea descris ca un concept deschis, un univers „in fieri”. Această idee este foarte bine exemplificată în special în teoria constructivă a tipului, în care noțiunea de univers teoretic de tip a fost lăsată în mod deliberat deschisă de Per Martin-Löf (prin nu a postulat reguli specifice de eliminare pentru aceasta). Natura deschisă a universului seturilor a deschis calea extinderii acestuia prin principii de reflecție. Acestea au fost cercetate atât în teoria tipului, cât și în teoria constructivă a seturilor. A se vedea (Rathjen 2005a) pentru o anchetă a rezultatelor și o discuție bazată pe teme, precum și secțiunea 5.2. Pentru o analiză formală a universului constructiv al seturilor și o comparație cu ierarhia Von Neumann, a se vedea (Ziegler 2014).universul seturilor este adesea descris ca un concept deschis, un univers „in fieri”. Această idee este foarte bine exemplificată în special în teoria constructivă a tipului, în care noțiunea de univers teoretic de tip a fost lăsată în mod deliberat deschisă de Per Martin-Löf (prin nu a postulat reguli specifice de eliminare pentru aceasta). Natura deschisă a universului seturilor a deschis calea extinderii acestuia prin principii de reflecție. Acestea au fost cercetate atât în teoria tipului, cât și în teoria constructivă a seturilor. A se vedea (Rathjen 2005a) pentru o anchetă a rezultatelor și o discuție bazată pe teme, precum și secțiunea 5.2. Pentru o analiză formală a universului constructiv al seturilor și o comparație cu ierarhia Von Neumann, a se vedea (Ziegler 2014).unde noțiunea de univers teoretic de tip a fost lăsată în mod deliberat deschisă de Per Martin-Löf (prin a nu postula reguli specifice de eliminare pentru el). Natura deschisă a universului seturilor a deschis calea extinderii acestuia prin principii de reflecție. Acestea au fost cercetate atât în teoria tipului, cât și în teoria constructivă a seturilor. A se vedea (Rathjen 2005a) pentru o anchetă a rezultatelor și o discuție bazată pe teme, precum și secțiunea 5.2. Pentru o analiză formală a universului constructiv al seturilor și o comparație cu ierarhia Von Neumann, a se vedea (Ziegler 2014).unde noțiunea de univers teoretic de tip a fost lăsată în mod deliberat deschisă de Per Martin-Löf (prin a nu postula reguli specifice de eliminare pentru el). Natura deschisă a universului seturilor a deschis calea extinderii acestuia prin principii de reflecție. Acestea au fost cercetate atât în teoria tipului, cât și în teoria constructivă a seturilor. A se vedea (Rathjen 2005a) pentru o anchetă a rezultatelor și o discuție bazată pe teme, precum și secțiunea 5.2. Pentru o analiză formală a universului constructiv al seturilor și o comparație cu ierarhia Von Neumann, a se vedea (Ziegler 2014). Acestea au fost cercetate atât în teoria tipului, cât și în teoria constructivă a seturilor. A se vedea (Rathjen 2005a) pentru o anchetă a rezultatelor și o discuție bazată pe teme, precum și secțiunea 5.2. Pentru o analiză formală a universului constructiv al seturilor și o comparație cu ierarhia Von Neumann, a se vedea (Ziegler 2014). Acestea au fost cercetate atât în teoria tipului, cât și în teoria constructivă a seturilor. A se vedea (Rathjen 2005a) pentru o anchetă a rezultatelor și o discuție bazată pe teme, precum și secțiunea 5.2. Pentru o analiză formală a universului constructiv al seturilor și o comparație cu ierarhia Von Neumann, a se vedea (Ziegler 2014).

2. Origini ale teoriilor de seturi constructive și intuiționale

Versiunile intuiționale ale teoriilor setului Zermelo-Fraenkel au fost introduse la începutul anilor ’70 de Friedman și Myhill. În (Friedman 1973) autorul prezintă un studiu al proprietăților formale ale diferitelor sisteme intuiționale și introduce pentru ele o extensie a metodei de realizabilitate a lui Kleene. Tehnica de realizabilitate este aplicată în (Myhill 1973) pentru a arăta proprietatea existenței pentru o versiune a teoriei intuitive a setului de seturi Zermelo-Fraenkel (cu înlocuire în locul colecției). Într-o altă contribuție fundamentală, Friedman extinde traducerea dublei negații a logicii intuitonistice pentru a relaționa teoriile seturilor clasice și intuiționale (Friedman 1973a). Aceste primele lucrări abordează deja relația dintre unele teorii importante ale intuiției și ZF clasic. De asemenea, aceștia clarifică o caracteristică cheie a teoriei de seturi bazată pe logica intuiționalistă,în principal că este susceptibil de interpretări semantice constructive puternice, precum realizabilitatea. Aceste tehnici sunt aplicate studiului proprietăților metateoretice cruciale, care sunt tipice abordării constructive și de care se bucură unele teorii de seturi constructive (vezi secțiunea despre tehnici semantice). Această lucrare innovantă a fost complet exploatată și extinsă în mod substanțial în activitatea lui Beeson și McCarty (vezi Beeson 1985; McCarty 1984). Această lucrare innovantă a fost complet exploatată și extinsă în mod substanțial în activitatea lui Beeson și McCarty (vezi Beeson 1985; McCarty 1984). Această lucrare innovantă a fost complet exploatată și extinsă în mod substanțial în activitatea lui Beeson și McCarty (vezi Beeson 1985; McCarty 1984).

Teoria constructivă a seturilor de la început are o vocație fundamentală mai distinctivă și este legată de matematica episcopului. De fapt, în 1967, Bishop a publicat cartea „Fundamentele analizei constructive” (Bishop 1967), care a deschis o nouă eră pentru matematică bazată pe logica intuiționalistă (vezi intrarea despre matematica constructivă). Monografia a stimulat încercările proaspete din comunitatea logică de a clarifica și reprezenta formal principiile care au fost folosite de Bishop, deși numai la nivel informal. Primele încercări ale lui Goodman și Myhill (Goodman și Myhill 1972) au folosit versiuni ale sistemului T de Gödel (a se vedea și (Bishop 1970) pentru o încercare similară). Myhill a ajuns însă la concluzia că formalizarea rezultată a fost prea complexă și artificială (Myhill 1975, 347). Myhill a propus în schimb un sistem care să fie mai aproape de noțiunea informală de set folosită inițial de Bishop și mai apropiată de tradiția teoretică. Myhill scrie (1975, 347):

Refuzăm să credem că lucrurile trebuie să fie atât de complicate - argumentarea lui (Bishop 1967) pare foarte lină și pare să se încadreze direct dintr-un anumit concept despre ce sunt seturile, funcțiile, etc. și dorim să descoperim un formalism care izolează principiile care stau la baza acestei concepții în același mod în care teoria seturilor Zermelo-Fraenkel izolează principiile care stau la baza matematicii clasice (neconstructive). Ne dorim ca aceste principii să fie astfel încât să facă procesul de formalizare complet banal, așa cum este în cazul clasic.

Observăm aici că teoria constructivă a seturilor Myhill a avut noțiuni distincte de funcție, număr natural și set; astfel a reprezentat îndeaproape o tradiție constructivă în care funcțiile și numerele naturale sunt conceptual independente de seturi. Un alt pas fundamental în dezvoltarea teoriei constructive a seturilor a fost „Bazele teoretice ale setului pentru analiza constructivă” a lui Friedman (Friedman 1977). Aici, printre alte sisteme, este definit un sistem numit B, care are restricții suplimentare asupra principiilor teoretice, comparativ cu Myhill (în special, nu are o inducție setată). De asemenea, are o formă restrânsă a axiomului alegerii dependente. Sistemul B se dovedește a fi suficient de expresiv pentru a reprezenta analiza constructivă a lui Bishop (1967), în același timp fiind teoretic foarte slab (din cauza absenței inducției stabilite). Sistemul B este de fapt o extensie conservatoare a aritmeticii (deci este mult sub limita predicativității, date fiind numerele naturale amintite pe scurt în secțiunea 1.3). Sistemele Myhill și Friedman au fost ulterior modificate de Aczel, pentru a obține un sistem, CZF (Constructive Zermelo-Fraenkel), care este complet compatibil cu limbajul ZF (Aczel 1978, 1982, 1986; Aczel și Rathjen 2001; 2010). De asemenea, CZF nu a inclus principii de alegere. Aczel a interpretat CZF în teoria tipului Martin-Löf cu scopul de a corobora natura constructivă a teoriei de seturi. El a consolidat, de asemenea, unele dintre principiile sistemului Myhill (și anume, colectarea și exponențiarea) pe motiv că versiunile mai puternice sunt încă validate de interpretarea în teoria tipurilor.

Alte sisteme fundamentale pentru matematica constructivă în stilul episcopului au fost introduse la începutul anilor '70. De exemplu: matematica explicită de S. Feferman (Feferman 1975) și teoria deja menționată a tipului intuițional (Martin-Löf 1975; 1984). Teoria constructivă a tipului este considerată de obicei baza cea mai satisfăcătoare pentru matematica constructivă în stil episcop. Atât teoria tipului, cât și matematica explicită pot fi văzute ca exprimând mai direct conținutul de calcul al matematicii constructive. Teoria tipurilor, în special, poate fi citită ca un limbaj de programare foarte general și expresiv. Teoriile de seturi constructive și intuiționale își afișează conținutul computațional doar indirect prin interpretările lor semantice (vezi de exemplu (Aczel 1977), (Lipton 1995) și secțiunea despre tehnici semantice).

3. Sistemele Axioms CZF și IZF

Pentru un cititor care este deja familiarizat cu teoria seturilor ZF, amintim acum axiomele sistemelor CZF și IZF. Pentru o listă completă și o explicație a axiomelor lor, ne referim în schimb la documentul suplimentar:

Axiomele CZF și IZF.

CZF și IZF sunt formulate pe baza unei logici intuiționale de prim ordin cu egalitate, având doar (in) (apartenență) ca un simbol suplimentar non-logic predicat binar. Axiomele lor set-teoretice sunt următoarele.

(Mathbf {IZF}) (Mathbf {CZF})
Extensionality (la fel)
Pereche (la fel)
Uniune (la fel)
Infinit (la fel)
Separare Separare restricționată
Colectie Colecție puternică
Powerset Colecția de subseturi
Set Inducție (la fel)

Rețineți că în IZF schema de separare nu este restricționată. În CZF, Colecția este consolidată pentru a compensa separarea restricționată. Colecția de subseturi este o întărire a axiomului de exponenție a lui Myhill, înlocuind astfel Powerset-ul lui ZF.

4. Principiile de alegere constructivă

Atunci când discutăm rolul teoriei claselor de set ca bază pentru matematică, de obicei se consideră teoria ZFC, adică sistemul de axiome ZF plus axioma de alegere (AC). Prin urmare, s-ar putea întreba care este starea axiomului ales în setări intuiționale. Întrebarea este deosebit de semnificativă, deoarece la prima apariție axioma de alegere a fost adesea văzută ca fiind controversată și extrem de neconstructivă. Cu toate acestea, în contexte constructive, se observă un fenomen particular. Forma obișnuită a axiomului de alegere este validată de teorii de tipuri precum teoria tipului Martin-Löf, unde există corespondența Curry-Howard (a se vedea secțiunea 3.4 din rubrica „Matematică constructivă”). Pe de altă parte, asumarea axiomului de alegere dă naștere unor cazuri de mijloc exclus în contexte extensive,unde este disponibilă și o formă de separare. Acesta este cazul, de exemplu, al ZF constructiv și intuiționalist. (Pentru dovadă, a se vedea documentul suplimentar despre Principiile teoretice incompatibile cu logica intuițională.) O dovadă a incompatibilității AC cu teoriile setului extensional bazate pe logica intuiționalistă pare să fi apărut pentru prima dată în (Diaconescu 1975) într-un context categoric. Goodman și Myhill oferă un argument pentru teoriile setate bazate pe logica intuiționalistă (Goodman și Myhill 1978).) O dovadă a incompatibilității AC cu teoriile seturilor extensionale bazate pe logica intuiționalistă pare să fi apărut pentru prima dată în (Diaconescu 1975) într-un context categoric. Goodman și Myhill oferă un argument pentru teoriile setate bazate pe logica intuiționalistă (Goodman și Myhill 1978).) O dovadă a incompatibilității AC cu teoriile seturilor extensionale bazate pe logica intuiționalistă pare să fi apărut pentru prima dată în (Diaconescu 1975) într-un context categoric. Goodman și Myhill oferă un argument pentru teoriile setate bazate pe logica intuiționalistă (Goodman și Myhill 1978).

Deși axioma de alegere este incompatibilă atât cu ZF constructiv, cât și cu intuiționalist, alte sisteme de alegere pot fi adăugate la sistemele de bază fără a produce aceleași rezultate nedorite. De exemplu, s-ar putea adăuga principiul alegerii contabile (AC (_ 0)) sau cel al alegerii dependente (DC). De fapt, ambele au fost deseori angajate în practica matematică constructivă. (Pentru formularea lor exactă, a se vedea documentul suplimentar despre Axiomele CZF și IZF.)

În (Aczel 1978) autorul a considerat de asemenea un principiu de alegere numit Axiomul de prezentare, care afirmă că fiecare set este imaginea surjectivă a unei așa-numite baze. O bază este un set, să zicem (B), astfel încât fiecare relație cu domeniu (B) extinde o funcție cu domeniu (B).

Compatibilitatea tuturor acestor forme de alegere cu teoria constructivă a seturilor a fost dovedită de Aczel prin extinderea interpretării lui CZF în teoria tipului Martin-Löf (Aczel 1982). Rathjen (2006) a avut în vedere și diverse principii de alegere constructivă și relațiile lor reciproce.

O remarcă finală: deși teoriile de seturi constructive și intuiționale sunt compatibile cu principiile de alegere menționate, teoriile stabilite sunt adesea definite fără principii de alegere. Aceasta are scopul de a permite o abordare fundamentală „pluralistă”. În special, s-ar dori să se obțină o teorie fundamentală compatibilă cu acele contexte (de exemplu, modelele categorice ale teoriei de seturi) în care chiar și aceste principii mai slabe de alegere nu pot fi validate. Pentru idei similare în contextul teoriei de tip constructiv, a se vedea (Maietti și Sambin 2005, Maietti 2009). De asemenea, amintim aici apelul lui Richman pentru o matematică constructivă care nu folosește principiile de alegere (Richman 2000; 2001).

5. Teoria probei și semantica ZF constructiv și intuițional

Atunci când luăm în considerare o anumită practică matematică (sau o teorie folosită pentru a o codifica) dintr-o perspectivă filozofică, trebuie să clarificăm cu cea mai mare precizie posibilă presupunerile care sunt făcute în cadrul acesteia, precum și consecințele care decurg din aceste presupuneri. Acest lucru este valabil în special atunci când lucrăm cu teorii care se bazează pe o logică mai slabă decât cea clasică, pentru care este necesară o perspectivă mai profundă și mai precisă. Sunt disponibile multe instrumente tehnice care ne pot ajuta să clarificăm aceste aspecte. Printre instrumentele disponibile, se numără tehnicile teoretice ale probelor, cum ar fi interpretările teoretice ale probelor, precum și tehnicile semantice, precum realizabilitatea, modelele Kripke, semantica valorizată de Heyting. De fapt, în literatura de specialitate asistăm adesea la interacțiunea tehnicilor teoretice și semantice. Vă prezentăm aici o privire curioasă în unele dintre aceste subiecte și sugerăm citirea în continuare.

5.1 Puterea teoretică a probei

O temă fundamentală în teoria probelor (în special în ramura acestei discipline cunoscută sub denumirea de analiză ordinală) este clasificarea teoriilor cu ajutorul ordinalelor transfinite care măsoară „puterea lor de consistență” și „puterea de calcul”. Aceste ordinale oferă o indicație despre cât de puternică este o teorie și, prin urmare, oferă un mod de a compara diferite teorii. De exemplu, ordinalul (varepsilon_0) este ordinalul teoretic al aritmeticii Peano și este mult mai mic decât cel ordinal (Gamma_0), denumit de obicei „limita predicativității” (vezi secțiunea 1.3 de mai sus). Acest lucru indică faptul că există teorii acceptabile predicativ, care sunt mult mai puternice decât aritmetica Peano.

Așa cum s-a discutat în secțiunea 1, pasul de la ZF clasic la variantele sale intuiționale ne impune să alegem o formulare adecvată pentru fiecare axiom teoretic setat: o axiomă clasică poate avea o serie de variante intuiționale care se dovedesc a nu fi echivalente între ele.. Acest lucru este reflectat uneori de puterea teoretică a probelor din teoriile rezultate, care poate varia în funcție de principiile pe care le alegem. De exemplu, am observat deja că în CZF nu avem un set complet de separare și putere, care sunt înlocuite cu principiile acceptabile predicativ de separare delimitată și respectiv colectarea subsetului. Cu toate acestea, dacă adăugăm la CZF oricare dintre aceste principii, obținem teorii impredicative. Impredicativitatea teoriilor rezultate este mărturisită de faptul că rezistența lor teoretică a probelor o depășește cu mult pe cea a CZF.

Nu este surprinzător faptul că investigațiile cu privire la puterea teoretică a probelor din teoriile grupurilor constructive și intuiționale au fost un instrument meta-teoretic crucial pentru înțelegerea acestor teorii și relațiile lor între ele. Investigațiile privind puterea teoretică a probei unei teorii sunt bogate și informative. În special, Feferman (1993) a susținut că o analiză teoretică doveditoare ne poate ajuta să stabilim dacă o anumită teorie respectă un cadru filosofic dat: de exemplu, analiza poate dezvălui că o teorie este predicativă sau finitistică etc. În plus, ca produs secundar al analizei teoretice a probelor obținem uneori dovezi simple de independență. De fapt, putem arăta că o teorie nu poate dovedi un principiu specific, deoarece adăugarea acesteia la teorie ar crește puterea teoretică a probei. De exemplu,CZF nu dovedește axioma powerset, deoarece adăugarea de powerset la CZF dă naștere unei teorii mult mai puternice. De asemenea, s-au folosit interpretări teoretice pentru a compara teoriile constructive și intuiționale ale seturilor ZF între ele, precum și cu omologii lor clasici, precum și cu alte sisteme fundamentale pentru matematica constructivă, cum ar fi teoria tipului constructiv și matematica explicită (vezi, de exemplu, Griffor și Rathjen 1994, Tupailo 2003). Pentru o definiție a noțiunii de rezistență teoretică a probei și pentru sondaje asupra teoriei dovezilor, a se vedea, de exemplu, (Rathjen 1999, 2006b).precum și cu omologii lor clasici și, de asemenea, cu alte sisteme fundamentale pentru matematica constructivă, precum teoria constructivă de tip și matematica explicită (vezi, de exemplu, Griffor și Rathjen 1994, Tupailo 2003). Pentru o definiție a noțiunii de rezistență teoretică a probei și pentru sondaje asupra teoriei dovezilor, a se vedea, de exemplu, (Rathjen 1999, 2006b).precum și cu omologii lor clasici și, de asemenea, cu alte sisteme fundamentale pentru matematica constructivă, precum teoria constructivă de tip și matematica explicită (vezi, de exemplu, Griffor și Rathjen 1994, Tupailo 2003). Pentru o definiție a noțiunii de rezistență teoretică a probei și pentru sondaje asupra teoriei dovezilor, a se vedea, de exemplu, (Rathjen 1999, 2006b).

Deși CZF și IZF sunt cele mai studiate sisteme, până în prezent, în literatura de specialitate au fost luate în considerare numeroase alte sisteme pentru teoria constructivă și intuițională a seturilor. Puterea teoretică a probelor a mai multor teorii de seturi constructive și intuiționale a fost stabilită printr-o varietate de instrumente, cum ar fi, de exemplu, o extensie a teoriei de interpretare a dublei negații (originată în (Friedman 1973a)) și o varietate a altor interpretări teoretice ale dovezilor, care rezultă deseori dintr-o combinație atentă de tehnici teoretice semantice și doveditoare. În multe cazuri, puterea teoretică a unui sistem a fost determinată de un lanț de interpretări între sistemele constructive și cele clasice și prin utilizarea unei varietăți de instrumente, de la relabilitate la tehnici teoretice mai „tradiționale”, ca analiză ordinală (vezi,de exemplu, Beeson 1985; Griffor și Rathjen 1994; Rathjen 2012b). În special, realizabilitatea s-a dovedit a fi foarte utilă, datorită flexibilității sale. În ceea ce privește rezultatele acestor investigații, unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0). Beeson 1985; Griffor și Rathjen 1994; Rathjen 2012b). În special, realizabilitatea s-a dovedit a fi foarte utilă, datorită flexibilității sale. În ceea ce privește rezultatele acestor investigații, unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0). Beeson 1985; Griffor și Rathjen 1994; Rathjen 2012b). În special, realizabilitatea s-a dovedit a fi foarte utilă, datorită flexibilității sale. În ceea ce privește rezultatele acestor investigații, unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0). Rathjen 2012b). În special, realizabilitatea s-a dovedit a fi foarte utilă, datorită flexibilității sale. În ceea ce privește rezultatele acestor investigații, unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0). Rathjen 2012b). În special, realizabilitatea s-a dovedit a fi foarte utilă, datorită flexibilității sale. În ceea ce privește rezultatele acestor investigații, unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0).realizabilitatea s-a dovedit a fi foarte utilă, datorită flexibilității sale. În ceea ce privește rezultatele acestor investigații, unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0).realizabilitatea s-a dovedit a fi foarte utilă, datorită flexibilității sale. În ceea ce privește rezultatele acestor investigații, unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0).unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0).unele dintre sistemele analizate s-au dovedit a fi la fel de slabe ca aritmetica, cum ar fi, de exemplu, sistemul B al lui Friedman (Friedman 1977); alte sisteme sunt la fel de puternice ca ZF-ul clasic complet, precum IZF (Friedman 1973a). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii cu o definiție inductivă cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0). Există, de asemenea, sisteme cu rezistență intermediară, ca CZF. Puterea acestei din urmă teorii, de fapt, este egală cu cea a unei teorii a unei definiții inductive cunoscută sub numele de ID (_ 1). Faptul că CZF are aceeași putere ca ID (_ 1) este luat pentru a confirma predicativitatea (generalizată) a teoriei de seturi și pentru a demonstra că aceasta depășește limita de predicativitate dată numerelor naturale, deoarece ID (_ 1)) dovada teoretică ordinal este cu mult peste (Gamma_0).

Ca o remarcă finală: în timp ce puterea CZF este cu mult sub cea a aritmeticii de ordinul doi, simpla adăugare a mijlocului exclus la CZF ne oferă ZF (complet). Acest lucru ar trebui să fie contrastat cu IZF, care are deja puterea ZF (Friedman 1973a). Puterea limitată teoretică a CZF în comparație cu IZF a fost adesea considerată unul dintre principalele avantaje ale constructivului față de teoria intuitivistă a seturilor. Într-un anumit sens, s-ar părea că CZF profită la maximum de logica intuiționalistă, întrucât caracterizează o noțiune de set predicativ (generalizat) suficient de puternic pentru dezvoltarea multor matematici constructive, dar și suficient de slab pentru a evita impredicativitatea. Interesant este că, atunci când s-au adăugat unele axiome de seturi mari la teoria constructivă a seturilor, a apărut un model similar,deoarece puterea teoriei rezultate este cu mult sub cea a teoriei clasice corespunzătoare.

5.2 Seturi mari în ZF constructiv și intuițional

Un domeniu proeminent de cercetare în teoria clasică a seturilor este cel al cardinalilor mari (vezi intrarea în teoria seturilor). În contexte constructive, ordinele nu sunt ordonate liniar. (Pentru noțiunea de ordinal constructiv și o scurtă discuție a proprietăților sale, a se vedea documentul suplimentar cu privire la: Principiile teoretice-set incompatibile cu logica intuițională.) În consecință, numerele cardinale nu joacă același rol ca în cadrul clasic.

Cu toate acestea, se poate studia impactul „principiilor de reflecție” sub forma unor axiome mari. De exemplu, se poate adăuga la teorii de seturi constructive și intuiționale un axiom care afirmă existența unor seturi inaccesibile. [2] Adăugarea axiomelor setului mare la ZF intuiționist a fost propusă pentru prima dată de Friedman și Scedrov (Friedman și Scedrov 1984). Unul dintre obiectivele lor a fost să arunce lumină asupra noțiunilor clasice corespunzătoare; alta a fost studierea impactului acestor principii asupra proprietăților metateoretice ale teoriilor originale ale setului. Friedman și Scedrov au arătat, de exemplu, că adăugarea de axiome de set mare nu compromite validitatea disjuncției și a proprietăților de existență numerică pentru IZF.

În contextul teoriei constructive a seturilor, Aczel a introdus seturi mari sub forma așa-numitelor seturi obișnuite pentru a permite definițiile inductive ale mulțimilor (Aczel 1986). Rathjen și Crosilla au considerat seturi inaccesibile (Rathjen al. 1998; Crosilla și Rathjen 2001) și seturi Mahlo (Rathjen 2003a). Cu toate acestea, o obiecție ar putea fi ridicată la extensii ale teoriei constructive a seturilor prin axiome mari de set. În teoria clasică a seturilor, cardinalii mari pot fi văzuți ca o încarnare a infinității superioare. Cum justificăm constructiv aceste principii? Justificarea constructivă a acestor noțiuni se bazează din nou pe interpretarea teoretică de tip. Adăugarea acestor principii corespunde, de fapt, cu universurile și tipurile (W) din teoria constructivă a tipurilor. Justificarea extinderilor prin seturi mari este astfel legată de problema limitelor teoriei de tip Martin-Löf (Rathjen 2005). De asemenea, remarcăm faptul că adăugarea axiomelor de inaccesibile la un subsistem slab de CZF (fără inducție setată) produce o teorie a puterii (Gamma_0), ordinalul separat de Feferman și Schütte ca limită de predicativitate dată naturalului numere (Crosilla și Rathjen 2001; vezi și secțiunea 1.3). Acest lucru este mărturie a faptului că lucrând într-un context constructiv, predicativ, putem îmblânzi noțiuni puternice tradițional-teoretice.ordinalul cântat de Feferman și Schütte ca limită a predicativității date de numerele naturale (Crosilla și Rathjen 2001; vezi și secțiunea 1.3). Acest lucru este mărturie a faptului că lucrând într-un context constructiv, predicativ, putem îmblânzi noțiuni puternice tradițional-teoretice.ordinalul cântat de Feferman și Schütte ca limită a predicativității date de numerele naturale (Crosilla și Rathjen 2001; vezi și secțiunea 1.3). Acest lucru este mărturie a faptului că lucrând într-un context constructiv, predicativ, putem îmblânzi noțiuni puternice tradițional-teoretice.

Teoria de seturi a lui Crosilla și Rathjen cu seturi inaccesibile (dar fără inducție de seturi) este dovada teoretic destul de slabă, dar matematic destul de expresivă. De exemplu, a fost utilizat pentru a verifica dacă adăugarea Axiomului de Univalență al lui Voevodsky la teoria tipului Martin-Löf nu generează impredicativitate (Rathjen 2017). Axioma Univalenței a fost introdusă de Voevodsky ca parte a programului său Fundații univalente (Voevodsky 2015). (Pentru Fundații Univalente, consultați intrările din teoria tipurilor și despre teoria tipului intuiționalist). Voevodsky a dat un model de teorie de tip constructiv cu Axiomul Univalenței, care se bazează pe seturi simple de Kan (vezi Kapulkin & Lumsdaine 2012, Alte resurse de internet). Modelul simplial al teoriei constructive de tip cu univalență dezvoltat în articolul de mai sus este realizat în cadrul unei extensii a ZFC cu cardinale inaccesibile. Acest lucru a determinat întrebarea dacă s-ar putea da un model mai constructiv al acestei teorii de tip și, în special, dacă teoria tipurilor este predicativă. Bezem, Coquand și Huber (2014) au propus recent un model de teorie de acest tip în seturi cubice, care este de calcul și „poate fi exprimat într-un metalogic constructiv”. Rathjen (2017) a verificat că acest nou model poate fi codificat într-o extensie adecvată a CZF prin seturi inaccesibile, care este mult mai slabă decât teoria clasică a seturilor cu cardinale inaccesibile. De fapt, se dovedește că dacă luăm ca punct de plecare o teorie de tip relativ slabă, adică una fără tipuri W, și o extindem prin Axiomul Univalenței,teoria rezultată are dovada puterii teoretice (Gamma_0), ordinala luată de obicei pentru a reprezenta limita predicativității date de numerele naturale (Rathjen 2017). Pentru a arăta acest lucru, se dovedește că modelul cubic de Bezem, Coquand și Huber poate fi realizat într-o extensie a sistemului introdus în Crosilla și Rathjen (2001) prin (legat) Relativized Dependent Choice. Din (Crosilla și Rathjen 2001) și (Rathjen 2003) rezultă că acesta din urmă are o dovadă teoretică ordinală (Gamma_0). Coquand și Huber pot fi realizate într-o extensie a sistemului introdus în Crosilla și Rathjen (2001) prin (delimitat) Relativized Dependent Choice. Din (Crosilla și Rathjen 2001) și (Rathjen 2003) rezultă că acesta din urmă are o dovadă teoretică ordinală (Gamma_0). Coquand și Huber pot fi realizate într-o extensie a sistemului introdus în Crosilla și Rathjen (2001) prin (delimitat) Relativized Dependent Choice. Din (Crosilla și Rathjen 2001) și (Rathjen 2003) rezultă că acesta din urmă are o dovadă teoretică ordinală (Gamma_0).

5.3 Proprietăți metamatematice ale ZF constructive și intuiționale și tehnici semantice

O varietate de interpretări pentru logica intuiționalistă au fost extinse la teoriile de seturi intuitiviste și constructive, precum realizabilitatea, modelele Kripke și semantica apreciată de Heyting. Toate aceste tehnici au fost aplicate pentru a obține rezultate metamatematice despre teoriile stabilite.

5.3.1 Proprietățile de disjuncție și existență ale ZF constructive și intuiționale

Unele teorii intuitive de set satisfac anumite proprietăți metamatematice „caracteristice”, cum ar fi disjuncția și proprietățile existenței. De asemenea, li se poate demonstra că sunt în concordanță cu adăugarea de principii care depășesc ceea ce considerăm cel mai tipic constructiv. Printre acestea se numără, de exemplu, teza Bisericii și principiul lui Markov. Pentru o descriere a acestor principii în contextul logicii intuiționale, cititorul poate dori să consulte secțiunile 4.2 și 5.2 din intrarea despre logica intuiționalistă sau cartea lui Troelstra și van Dalen Constructivism în matematică (Troelstra și van Dalen, 1988).

Aici amintim proprietățile disjuncției și existenței, formulate pentru o teorie de set (T). Motivația informală pentru disjuncție și proprietățile existenței se bazează pe înțelegerea noastră a dovezilor constructive ale enunțurilor disjunctive și, respectiv, ale existenței. De fapt, pare rezonabil să ne așteptăm ca, dacă dovedim constructiv o disjuncție (phi / vee / psi), atunci ar trebui să putem, de asemenea, să dovedim (phi) sau să dovedim (psi). În mod similar, dacă dovedim o afirmație existențială, atunci ar trebui să putem demonstra că un martor al acestei afirmații este definit în teoria noastră.

Deși astfel de proprietăți par destul de naturale și sunt destul de ușor de stabilit pentru teoriile aritmetice, acestea se dovedesc a constitui provocări tehnice considerabile în cazul teoriilor setului, datorită ierarhiilor lor transfinite ale seturilor și axiomului de extensionalitate. De fapt, teorii constructive și intuiționale proeminente de ansamblu se dovedesc a nu poseda proprietatea existenței, așa cum este discutat în secțiunea următoare.

Fie (T) o teorie a cărei limbă, (L (T)), cuprinde limbajul teoriei de seturi. Mai mult, pentru simplitate, vom presupune că (L (T)) are o constantă ((omega) care notează setul de numere naturale von Neumann și pentru fiecare (n) o constantă (c_n) denotând. elementul (n) - al (omega).

O teorie (T) are proprietatea disjuncției (DP) dacă de fiecare dată când (T) se dovedește ((phi / vee / psi)) pentru propoziții (phi) și (psi) din (L (T)), apoi (T) dovedește (phi) sau (T) dovedește (psi).

Proprietatea existență are două versiuni distincte în contextul teoriei de seturi: proprietatea existenței numerice (NEP) și proprietatea existenței (EP). Să fie (theta (x)) o formulă cu cel mult (x) liber. Spunem că:

(1) (T) are NEP dacă de fiecare dată când (T) se dovedește (există x / in / omega / theta (x)), atunci, pentru un număr natural (n, T) se dovedește (theta (c_n)).

(2) (T) are PE dacă ori de câte ori (T) se dovedește (există x / theta) (x), atunci există o formulă (phi (x)) cu exact (x) gratuit, astfel încât (T) se dovedește (există! x (phi (x) wedge / theta (x))).

Deoarece tehnicile de realizare s-au dovedit cruciale în investigațiile privind existența și proprietățile disjuncționale pentru teoriile de seturi constructive și intuiționale, vom discuta rezultatele acestor studii în secțiunea următoare.

5.3.2 Realizare

Realizabilitatea a fost unul dintre primele și principalele instrumente din cercetările care înconjoară teoriile seturilor bazate pe logica intuiționalistă, pornind de la contribuțiile timpurii ale lui Friedman și Myhill (Friedman 1973, Myhill 1973). Semantica de realizabilitate pentru aritmetica intuițională a fost prima dată propusă de Kleene (Kleene 1945) și extinsă la ordinul superior Heyting aritmetic de Kreisel și Troelstra (Kreisel și Troelstra 1970). Pentru definirea realizabilității aritmeticii, vezi secțiunea 5.2 a intrării pe logica intuiționalistă. O realizabilitate similară cu Kreisel și Troelstra a fost aplicată sistemelor de aritmetică de ordin superior de Friedman (Friedman 1973). Myhill a introdus o variantă a acestei realizabilități care seamănă cu slash-ul lui Kleene (Myhill 1973; Kleene 1962, 1963). El a dovedit astfel că o versiune a IZF cu înlocuire în locul colecției (numită IZF (_ {Rep})) are DP, NEP și PE. Aceste rezultate au fost extinse în continuare (Myhill 1975; Friedman și Scedrov 1983). În timp ce Friedman și Myhill au oferit modele de realizabilitate pentru teoriile seturilor extensionale, Beeson a dezvoltat o noțiune de realizabilitate pentru teoriile de seturi non-extensionale. Apoi a studiat proprietățile metateoretice ale teoriilor setului extensional printr-o interpretare în omologii lor non-extensivi. El a dovedit astfel că IZF (cu colecție) are DP și NEP (Beeson 1985). Ulterior, McCarty a introdus realizabilitatea IZF direct pentru teoria seturilor extensionale (McCarty 1984; 1986). Semantica de realizabilitate pentru variante de CZF a fost luată în considerare, de exemplu, în (Crosilla și Rathjen 2001; Rathjen 2006a). Realizabilitatea din ultimul articol este inspirată de McCarty și are caracteristica importantă că, în calitate de McCarty pentru IZF, este o semantică auto-validată pentru CZF (adică această noțiune de realizabilitate poate fi formalizată în CZF și fiecare teoremă de CZF este realizat probabil în CZF). Rathjen a folosit această noțiune de realizabilitate pentru a arăta că CZF (și o serie de extensii ale acesteia) au DP și NEP (Rathjen 2005b).

Un alt tip de realizabilitate care s-a dovedit foarte utilă este realizarea Lifschitz. Lifschitz (1979) a introdus o modificare a realizării lui Kleene pentru aritmetica Heyting, care are particularitatea validării unei forme slabe de teză a Bisericii (CT) cu o condiție de unicitate, dar nu CT în sine. Realizabilitatea Lifschitz a fost extinsă la aritmetica de ordinul doi de către van Oosten (1990). Ulterior, a fost extins la IZF complet de către Cheng și Rathjen, care l-au angajat pentru a obține o serie de rezultate de independență, precum și pentru a valida așa-numitul Principiul Limitat al Omniscienței (LLPO) (pentru LLPO vezi rubrica despre matematica constructivă).

Întrebarea cu care teoriile stabilite satisfac proprietatea existenței s-a dovedit a fi deosebit de dificil de rezolvat. (Friedman și Scedrov 1985) au folosit modele Kripke pentru a arăta că IZF (adică sistemul cu colecție) nu are EP-ul, în timp ce este menționat mai sus, sistemul IZF (_ {Rep}) (care are înlocuire în loc de colectare) are PE. Acest lucru l-a determinat pe Beeson să pună întrebarea [Beeson 1985, IX]:

Există vreo teorie rezonabilă a seturilor cu colecție proprietatea existenței?

Un prim răspuns la întrebarea lui Beeson a venit cu (Rathjen 2012), unde autorul a introdus noțiunea de proprietate a existenței slabe: accentul aici este găsirea unui set de martori probabil definitor pentru fiecare teoremă existențială. El a introdus apoi o formă de realizabilitate bazată pe funcții recursive set generale, în care un realizator pentru o declarație existențială oferă un set de martori pentru cuantificatorul existențial, mai degrabă decât pe un singur martor. Rathjen a combinat această noțiune de realizabilitate cu adevărul pentru a rezulta că o serie de teorii cu colecția se bucură de proprietatea existenței slabe (în timp ce IZF nu). Printre ele, în special, teoria CZF fără colecție de subseturi, plus axiomul de exponențiere al lui Myhill, CZF (_ {Exp}). De fapt, Rathjen a susținut că prin combinarea acestor rezultate cu lucrările ulterioare pe care le-a desfășurat,el ar putea arăta că CZF (_ {Exp}) (și o serie de alte teorii) au proprietatea existenței. O observație izbitoare este că aceste teorii sunt formulate cu colecție; în consecință, eșecul proprietății existenței în cazul IZF nu poate fi atribuit doar colecției, ci interacțiunii dintre această schemă și separarea fără restricții.

În ceea ce privește întrebarea proeminentă dacă CZF în sine are proprietatea existenței, aceasta a fost rezolvată în negativ de Swan (2014). Acolo autorul a folosit trei modele de realizabilitate și încorporate bine concepute între ele, pentru a arăta că chiar și proprietatea existenței slabe nu reușește CZF. În acest fel, el a arătat că schema de colectare a subseturilor CZF este vinovatul. Așa cum s-a subliniat clar în (Swan 2014), faptul că CZF nu are PE nu indică o anumită slăbiciune în CZF ca teorie constructivă. Chiar dacă Swan a dovedit în esență că CZF afirmă existența unor obiecte matematice pe care nu știe să le construiască, totuși CZF are interpretări naturale în care aceste obiecte pot fi construite, cum ar fi, de exemplu, interpretarea lui Aczel în teoria tipurilor (Aczel 1978).

Pentru o anchetă a rezultatelor în teoria intuițională a seturilor a se vedea (Beeson 1985, Capitolul IX). Pentru evoluțiile corespunzătoare în CZF, a se vedea (Rathjen 2005b, 2006, 2012) și (Swan 2014).

5.3.3 Modele Kripke și semantică apreciată de Heyting

Modelele Kripke pentru teoriile intuitiveiste ale seturilor au fost utilizate în (Friedman și Scedrov 1985) pentru a arăta că IZF nu are PE (și combinând acest lucru cu rezultatele din (Myhill 1973) avem că IZF (_ {Rep}) nu dovedesc IZF). Modelele Kripke au fost aplicate mai recent pentru a clarifica relația dintre înlocuitorii constructivi ai axiomului setului de putere: axiomul de exponenție al lui Myhill și schema de colectare a subseturilor Aczel. Este clar că axioma setului de putere implică ambele principii și că colectarea de subseturi implică exponențiere. Pe de altă parte, fiecare din ultimele două principii nu implică setul de putere, deoarece teoria CZF cu puterea setată în locul colectării subsetului este mult mai puternică decât CZF și CZF (_ {Exp}) (Rathjen 2012b). De fapt, CZF și CZF (_ {Exp}) au aceeași rezistență teoretică (Griffor și Rathjen 1994);prin urmare, pentru a investiga relația dintre colectarea subsetului și exponențiarea în teoria constructivă a seturilor este necesară pentru a dezvolta instrumente, alte metode teoretice. Lubarsky (2005) a folosit modelele Kripke pentru a arăta că axioma de exponenție a lui Myhill nu implică colecția de subseturi a lui Aczel (pe baza colecției de subseturi CZF minus plus a separării complete). În (Lubarsky și Rathjen 2007) autorii au aplicat tehnica modelelor Kripke pentru a arăta că și consecințele teoriilor CZF și CZF (_ {Exp}) sunt diferite. Aczel și Rathjen (2001) au arătat că clasa numerelor reale ale Dedekind formează un set în CZF, folosind colecția de subseturi. Lubarsky și Rathjen (2007) au arătat că CZF (_ {Exp}) nu este suficient pentru a demonstra aceeași afirmație. Pentru aplicații suplimentare ale modelelor Kripke pentru separarea noțiunilor constructive cruciale, vezi de ex(Diener și Lubarsky 2013).

Semantica valorizată de Heyting pentru teoriile intuitiveiste ale seturilor a fost obținută de Grayson (Grayson 1979) ca o omologă pentru modelele booleane pentru teoria clasică a seturilor. Au fost generalizate în special prin semantică categorică (pentru o introducere a se vedea MacLane și Moerdijk 1992). Semantica apreciată de Heyting a găsit o aplicație la rezultatele independenței în (Scedrov 1981; 1982). Un tratament constructiv a fost administrat în (Gambino 2006). Vezi și (Lubarsky 2009). Vezi și Ziegler (2012) pentru o generalizare a modelelor de realizare și Heyting pentru teoria constructivă a seturilor.

5.3.4 Modele categorice ale teoriei de seturi constructive și intuiționale

Modelele categorice ale teoriilor seturilor constructive și intuiționale au înflorit de-a lungul anilor. Noțiunile de topos și teacă joacă un rol esențial aici (a se vedea, de exemplu, Fourman 1980 și Fourman și Scott 1980). Pentru o imagine de ansamblu asupra principalelor concepte, consultați intrarea în teoria categoriilor și referințele oferite acolo (a se vedea, în special, suplimentul Ghid de citire programatică). Pentru evoluțiile recente care se referă mai precis la teoriile de seturi constructive, vezi de exemplu (Simpson 2005) și (Awodey 2008), precum și pagina web: teoria algebrică a seturilor.

5.4 Variante de teorii de seturi constructive și intuiționale: teorii de set cu corelații și teorii de seturi care nu sunt extensibile

Uneori, sistemele de teoria intuitivistă și constructivă a seturilor au fost prezentate cu numerele naturale ca un fel separat de urelements, adică obiecte primitive fără elemente (Friedman 1977; Myhill 1975; Beeson 1985). Constructiv, aceasta este o alegere naturală, care este de acord cu ideile exprimate, de exemplu, de către Bishop (1967) (printre altele). În monografia lui Bishop, numerele naturale sunt luate ca un concept fundamental pe care se bazează toate celelalte concepte matematice. Din punct de vedere tehnic, dacă numerele naturale sunt luate ca primitive și distincte de reprezentările lor teoretice, setul axiomului infinitului ia forma: „există un set de numere naturale (ca urelements)”. O formă mai generală a urelement-urilor în teoriile constructive a fost luată în considerare (Cantini și Crosilla 2008). Aici se propune o variantă a teoriei constructive a seturilor care combină o noțiune intensivă și parțială de operare cu noțiunea extensională a setului CZF (a se vedea, de asemenea, Cantini și Crosilla 2010).

Axioma extensionalității este o caracteristică comună a tuturor sistemelor discutate până acum. Cu toate acestea, într-un context în care conținutul de calcul al unei afirmații este considerat a fi crucial, o teorie intensivă ar putea fi mai adecvată. De exemplu, teoria de tip constructiv și matematica explicită ambele încapsulează o anumită formă de intensivitate. În literatura de specialitate au fost luate în considerare teoriile setului intuiționalist fără extensionalitate (Friedman 1973a, Beeson 1985). Motivația lor nu a fost însă de natură computatională, ci tehnică, datorită dificultăților pe care extensionalitatea le are atunci când studiem proprietățile metamatematice ale teoriilor intuitiviste ale seturilor.

Bibliografie

  • Aczel, P., 1978, „The Type Theoretic Interpretation of Constructive Set Theory”, în Logic Colloquium '77, A. MacIntyre, L. Pacholski, J. Paris (eds.), Amsterdam și New York: Nord-Olanda, pp 55–66.
  • –––, 1982, „Interpretarea teoretică de tip a teoriei de seturi constructive: principii de alegere”, în The LEJ Brouwer Centenary Symposium, AS Troelstra și D. van Dalen (eds.), Amsterdam și New York: North-Holland, pp. 1-40.
  • –––, 1986, „Interpretarea teoretică de tip a teoriei de seturi constructive: definiții inductive”, în Logică, Metodologie și Filosofia Științei VII, RB Marcus, GJ Dorn și GJW Dorn (eds.), Amsterdam și New York: Olanda de Nord, p. 17–49.
  • –––, 1988, Seturi neîntrebuințate (CSLI Lecture Notes 14), Stanford: CSLI.
  • Aczel, P. și Rathjen, M., 2001, „Note despre teoria constructivă a seturilor”, Raport nr. 40, 2000/2001, Djursholm: Institut Mittag-Leffler, [disponibil online]
  • Aczel, P., și Gambino, N., 2002, „Principiile colecției în teoria tipurilor dependente”, în Tipuri pentru dovezi și programe (Note de lectură în informatică 2277), P. Callaghan, Z. Luo, J. McKinna și R. Pollack (eds.), Berlin: Springer, p. 1–23.
  • Awodey, S., 2008, „O scurtă introducere în teoria algebrică a seturilor”, Buletinul simbolic, 14 (3): 281–298.
  • Barwise, J., și Moss, L., 1996, Vicious Circles (CSLI Lecture Notes 60), Stanford: CSLI.
  • Beeson, M., 1985, Fundațiile constructive de matematică, Berlin: Springer.
  • Bezem, M., Thierry, C. și Huber, S., 2014, „Un model de teorie de tip în seturi cubice”, în cea de-a 19-a Conferință internațională privind tipurile de dovezi și programe (TYPES 2013), Matthes, R. și Schubert, A. (eds.), Dagstuhl: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, p. 107–128.
  • Bishop, E., 1967, Foundations of Constructive Analysis, New York: McGraw-Hill.
  • –––, 1970, „Matematica ca limbaj numeric”, în Intuitionism și teoria probei, A. Kino, J. Myhill și RE Vesley (eds.), Amsterdam: Olanda de Nord, p. 53-71.
  • Bishop, E., and Bridges, D., 1985, Analiză constructivă, Berlin și Heidelberg: Springer.
  • Bridges, D., and Richman, F., 1987, Varieties of Constructive Mathematics, Cambridge: Cambridge University Press.
  • Buchholz, W., Feferman, S., Pohlers, W., și Sieg, W., 1981, Iterated Inductive Definitions and Subsystems of Analysis, Berlin: Springer.
  • Cantini, A. și Crosilla, L., 2008, „Teoria constructivă a seturilor cu operații”, în A. Andretta, K. Kearnes, D. Zambella (eds.), Logic Colloquium 2004 (Lecture Notes in Logic 29), Cambridge: Cambridge University Press, p. 47–83.
  • Cantini, A. și Crosilla, L., 2010, „Teoria operațională explicită a seturilor”, în R. Schindler (ed.), Ways of Proof Theory, Frankfurt: Ontos, p. 199-240.
  • Chen, R.-M. și Rathjen, M., 2012, „Lifschitz Realizability for Intuitionistic Zermelo-Fraenkel Set Setory”, Arhiva pentru logica matematică, 51: 789–818.
  • Crosilla, L., 2017, „Predicativitate și Feferman”, în G. Jäger și W. Sieg (eds.), Feferman on Foundations (Outstanding Contributions to Logic: Volume 13), Cham: Springer, pp. 423-447.
  • Crosilla, L., și Rathjen, M., 2001, „Axiomele setului inaccesibile pot avea o rezistență redusă la consistență”, Analele logicii pure și aplicate, 115: 33–70.
  • Diaconescu, R., 1975, „Axiomul alegerii și al completării”, Proceedings of the American Mathematical Society, 51: 176-178.
  • Diener, H., și Lubarsky, R., 2013, „Separarea teoremei fanilor și a rezultatelor sale”, în SN Artemov și A. Nerode (eds.), Proceedings of LFCS '13 (Lecture Notes in Computer Science 7734), Dordrecht: Springer, p. 280–295.
  • Dummett, M., 2000, Elements of Intuitionism, ediția a doua, (Oxford Logic Guides 39), New York: Oxford University Press.
  • Feferman, S., 1964, „Sisteme de analiză predicativă”, Journal of Symbolic Logic, 29: 1-30.
  • –––, 1975, „Un limbaj și axiome pentru matematica explicită”, în Algebra și logică (Lecture Notes in Mathematics 450), J. Crossley (ed.), Berlin: Springer, p. 87–139.
  • –––, 1988, „Weyl vindicated: Das Kontinuum șaptezeci de ani mai târziu”, în Temi e prospettive della logica e della scienza contemporanee, C. Cellucci și G. Sambin (eds), p. 59-93.
  • –––, 1993, „Ce se bazează pe ce? Analiza teoretică a probelor de matematică”, în Filozofia matematicii, partea I, Procesele celui de-al 15-lea simpozion internațional Wittgenstein. Viena: Verlag Hölder-Pichler-Tempsky.
  • –––, 2005, „Predicativitate”, în Manualul filosofiei matematicii și logicii, S. Shapiro (ed.), Oxford: Oxford University Press.
  • Fletcher, P., 2007, „Infinity”, în Handbook of the Philosophy of Logic, D. Jacquette, (ed.), Amsterdam: Elsevier, p. 523–585.
  • Fourman, MP, 1980, „Modele de foaie pentru teoria seturilor”, Journal of Pure Applied Algebra, 19: 91–101.
  • Fourman, MP, și Scott, DS, 1980, „Sheaves and logic”, în Applications of Sheaves (Lecture Notes in Mathematics 753), MP Fourman, CJ Mulvey și DS Scott (eds.), Berlin: Springer, pp. 302– 401.
  • Friedman, H., 1973, „Unele aplicații ale metodelor lui Kleene pentru sisteme intuiționale”, în Proceedings of the Cambridge Summer School in 1971 Mathematical Logic (Lecture Notes in Mathematics 337), ARD Mathias și H. Rogers (eds.), Berlin: Springer, p. 113–170.
  • –––, 1973a, „Coerența teoriei de seturi clasice în raport cu o teorie a seturilor cu logică intuiționalistă”, Journal of Symbolic Logic, 38: 315–319.
  • –––, 1977, „Bazele teoretice stabilite pentru analiza constructivă”, Annals of Mathematics, 105: 1–28.
  • Friedman, H., Scedrov, A., 1983, „Setați proprietatea existenței pentru teoriile intuiționale cu alegerea dependentă”, Analele logicii pure și aplicate, 25: 129-140.
  • –––, 1984, „Seturi mari în teoria intuițională a seturilor”, Analele logicii pure și aplicate, 27: 1–24.
  • –––, 1985, „Lipsa martorilor definibili și a funcțiilor probabil recursive în teoria intuițională a seturilor”, Progresele în matematică, 57: 1–13.
  • Gambino, N., 2006, „Interpretări apreciate pentru Heyting pentru teoria constructivă a seturilor”, Analele logicii pure și aplicate, 137: 164-188.
  • Goodman, ND și Myhill, J., 1972, „Formalizarea matematicii constructive a lui Bishop”, în Toposes, Geometry algebraic and Logic (Lecture Notes in Mathematics 274), FW Lawvere (ed.), Berlin: Springer, p. 83 -96.
  • Goodman, ND și Myhill, J., 1978, „Alegerea implică mijlocul exclus”, Zeitschrift für matische Logik und Grundlagen der Mathematik, 24 (5): 461.
  • Grayson, RJ, 1979, „Heyting-valorated models for intuitionistic set teoria”, in Applications of Sheaves (Lecture Notes in Mathematics 753), MP Fourman, CJ Mulvey, and DS Scott (eds.), Berlin: Springer, pp. 402 -414.
  • Griffor, E. și Rathjen, M., 1994, „Puterea unor teorii de tip Martin-Löf”, Arhiva Matematică Logică, 33: 347-385.
  • van Heijenoort, J., 1967, De la Frege la Gödel. O carte sursă în logica matematică 1879–1931, Cambridge: Harvard Univ. Presa.
  • Kleene, SC, 1945, „Cu privire la interpretarea teoriei intuiționiste a numerelor”, Journal of Symbolic Logic, 10: 109–124.
  • –––, 1962, „Disjuncția și existența implicată în formalismele intuiționale elementare”, Journal of Symbolic Logic, 27: 11–18.
  • –––, 1963, „Un addendum”, Journal of Symbolic Logic, 28: 154-156.
  • Kreisel, G., 1958, „Logica ordinală și caracterizarea conceptelor informale ale dovezii”, Proceedings of the International Congress of Mathematicians (14–21 August 1958), Paris: Gauthier-Villars, p. 289-299.
  • Kreisel, G. și Troelstra, A., S., 1970, „Sisteme formale pentru unele ramuri ale analizei intuiționale”, Analele logicii matematice, 1: 229–387.
  • Lifschitz, V., 1979, „CT (_ 0) este mai puternic decât CT (_ 0)!”, Proceedings of the American Mathematical Society, 73 (1): 101–106.
  • Lindström, I., 1989, „O construcție a unor seturi neîntemeiate în teoria tipului Martin-Löf”, Journal of Symbolic Logic, 54: 57-64.
  • Lipton, J., 1995, „Realizabilitate, teoria seturilor și extracția termenului”, în Izomorfismul Curry-Howard (Cahiers du Centre de Logique de l’Université Catholique de Louvain 8), Louvain-la-Neuve: Academia, p. 257 -364.
  • Lorenzen, P. și Myhill, J., 1959, „Definirea constructivă a anumitor seturi de numere analitice”, Journal of Symbolic Logic, 24: 37–49.
  • Lubarsky, R., 2005, „Rezultatele independenței în jurul ZF constructiv”, Analele logicii pure și aplicate, 132: 209-225.
  • –––, 2006, „CZF și aritmetica de ordinul doi”, Analele logicii pure și aplicate, 141: 29–34.
  • –––, 2009, „Topologic Forcing Semantics with Settling”, în SN Artemov și A. Nerode (eds.), Proceedings of LFCS ’09 (Lecture Notes in Computer Science 5407), Dordrecht: Springer, pp. 309–322.
  • Lubarsky, R., și Rathjen, M., 2007, „Cu privire la construcțiile Dedekind Reals”, în în SN Artemov și A. Nerode (eds.), Proceedings of LFCS 2007 (Lecture Notes in Computer Science 4514), Dordrecht: Springer, p. 349–362.
  • MacLane, S., și Moerdijk, I., 1992, „Sheaves in Geometry and Logic”, New York: Springer.
  • Maietti, ME, Sambin, G., 2005, „Spre o fundație minimalistă pentru matematica constructivă”, în De la seturi și tipuri până la topologie și analiză: Către bazele practicabile pentru matematica constructivă (Oxford Logic Guides 48), L. Crosilla și P. Schuster (eds.), Oxford: Oxford University Press.
  • Maietti, ME, 2009, „O bază minimalistă la două niveluri pentru matematica constructivă”, Analele logicii pure și aplicate, 160 (3): 319–354.
  • Martin-Löf, P., 1975, „O teorie intuiționalistă a tipurilor: parte predicativă”, în HE Rose și J. Sheperdson (eds.), Logic Colloquium ’73, Amsterdam: North-Holland, p. 73–118.
  • –––, 1984, „Teoria tipului intuițional”, Napoli: Bibliopolis.
  • McCarty, DC, 1984, „Realizabilitate și Matematică Recursivă”, D. Phil. Disertație, Filozofie, Universitatea Oxford.
  • –––, 1986, „Realizare și teoria recursivă a seturilor”, Analele logicii pure și aplicate, 32: 153-183.
  • Myhill, J., 1973, „Unele proprietăți ale teoriei de seturi intuitioniste Zermelo-Fraenkel”, în Proceedings of the 1971 Summer School School in Mathematical Logic (Lecture Notes in Mathematics 337), ARD Mathias, and H. Rogers (eds.), Berlin: Springer, p. 206–231.
  • –––, 1975, „Teoria constructivă a seturilor”, Journal of Symbolic Logic, 40: 347–382.
  • van Oosten, J., 1990, „Realizabilitatea lui Lifschitz”, The Journal of Symbolic Logic, 55: 805–821.
  • Powell, W., 1975, „Extinderea interpretării negative a lui Gödel la ZF”, Journal of Symbolic Logic, 40: 221–229.
  • Rathjen, M., Griffor, E. și Palmgren, E., 1998, „Inaccesibilitatea în teoria constructivă a seturilor și teoria tipurilor”, Analele logicii pure și aplicate, 94: 181–200.
  • Rathjen, M., 1999, „The Realm of Analinal Ordinal”, în Sets and Proofs (London Mathematical Society Lecture Notes 258), Cambridge: Cambridge University Press, p. 219–279.
  • –––, 2003, „Axioma anti-fundație în teoriile seturilor constructive”, în Jocuri, logică și seturi constructive (CSLI Lecture Notes 161), Stanford: CSLI Publication, pp. 87–108.
  • –––, 2003a, „Realizarea teoriei setului de Mahlo în teoria tipurilor”, Arhiva pentru logica matematică, 42: 89–101.
  • –––, 2004, „Predicativitate, circularitate și anti-fundație”, în O sută de ani din paradoxul lui Russell (Logica și aplicațiile sale 6), G. Link (ed.), Berlin: de Gruyter, p. 191-219.
  • –––, 2005, „Înlocuire versus colecție și subiecte conexe în teoria constructivă a seturilor Zermelo-Fraenkel”, Analele logicii pure și aplicate, 136: 156–174.
  • –––, 2005a, „Programul constructiv Hilbert și limitele teoriei de tip Martin-Löf”, Synthese, 147: 81–120.
  • –––, 2005b, „Disjuncția și proprietățile aferente pentru teoria constructivă a seturilor de seturi Zermelo-Fraenkel”, Journal of Symbolic Logic, 70 (4): 1232–1254.
  • –––, 2006, „Principiile de alegere în teoriile seturilor constructive și clasice”, Logic Colloquium '02 (Lecture Notes in Logic 27), Z. Chatzidakis, P. Koepke și W. Pohlers (eds.), Wellesley, Massachusetts: AK Peters, 299–326.
  • –––, 2006a, „Realizare pentru teoria constructivă a seturilor Zermelo-Fraenkel”, în Logic Colloquium ’03 (Lecture Notes in Logic 24), V. Stoltenberg-Hansen și J. Väänänen (eds.), Wellesley, Massachusets: AK Peters, p. 282–314.
  • –––, 2006b, „Teorii și ordonanțe în teoria probelor”, Synthese, 148 (3): 719–743.
  • –––, 2008, „Numerele naturale în teoria constructivă a seturilor”, Matematica Logică Trimestrială, 54: 287–312.
  • –––, 2012, „De la proprietatea existenței slabe la cele puternice”, Analele logicii pure și aplicate, 163: 1400–1418.
  • –––, 2012b, „Teoria seturilor constructive Zermelo-Fraenkel, setul de putere și calculul construcțiilor”, în Epistemologie versus Ontologie: Eseuri despre filosofie și fundamentări ale matematicii în onoarea lui Per Martin-Löf, (Logică, Epistemologie și seria Unity of Science), P. Dybjer, S. Lindström, E. Palmgren și G. Sundhölm (eds.), New York și Dordrecht: Springer Verlag.
  • –––, 2017, „Teoria probelor sistemelor constructive: tipuri inductive și univalență”, în G. Jäger, și W. Sieg (eds.), Feferman pe fundații (contribuții excepționale la logică: volumul 13), Cham: Springer, p. 385–419.
  • Richman, F., 2000, „Teorema fundamentală a algebrei: o dezvoltare constructivă fără alegere”, Pacific Journal of Mathematics, 196: 213-230.
  • –––, 2001, „Matematică constructivă fără alegere”, în Reunirea antipodelor: Vizualizări constructive și nonstandard ale continuumului (Biblioteca Sinteză 306), P. Schuster și colab. (eds.), Dordrecth: Kluwer, p. 199–205.
  • Russell, B., 1908, „Logica matematică, bazată pe teoria tipurilor”, American Journal of Mathematics, 30: 222–262. Reeditată în van Heijenoort (1967), 150–182.
  • Scedrov, A., 1981, „Consistența și independența rezultă în teoria intuițională a seturilor” în Matematica constructivă (Lecture Notes in Mathematics 873), F. Richman (ed.), Berlin: Springer, p. 54-86.
  • –––, 1982, „Independența teoremei fanilor în prezența principiilor continuității” în The LEJ Brouwer Centenary Symposium, AS Troelstra și D. van Dalen (eds.), Amsterdam: Olanda de Nord, pp. 435-442.
  • –––, 1985, „Teoria intuițională a seturilor” în cercetările lui Harvey Friedman asupra fundamentelor matematicii, LA Garrubgtib și colab. (eds.), Amsterdam: Elsevier.
  • Schütte, K., 1965, „Predicative well-commandings”, în Sisteme formale și funcții recursive, J. Crossley și M. Dummett (eds.), Amsterdam: Olanda de Nord, pp. 279-302.
  • –––, 1965a, „Eine Grenze für die Beweisbarkeit der Transfiniten Induktion in der verzweigten Typenlogik”, Archiv for Mathische Logik and Grundlagenforschung, 7: 45–60.
  • Simpson. eds.), Oxford: Oxford University Press.
  • Swan, AW, 2014, „CZF nu are proprietatea existenței”, Analele logicii pure și aplicate, 165: 1115–1147.
  • Troelstra, AS, și van Dalen, D., 1988, Constructivism în matematică (două volume), Amsterdam: Olanda de Nord.
  • Tupailo, S., 2003, „Realizarea teoriei de seturi constructive în matematica explicită: o limită inferioară pentru universul impredicativ Mahlo”, Analele logicii pure și aplicate, 120: 165–196.
  • Voevodsky, V., 2015, „O bibliotecă experimentală de matematică oficializată bazată pe fundamente univalente”, Structuri matematice în informatică, 25: 1278–1294.
  • Weyl, H., 1918, „Das Kontinuum. Kritische Untersuchungen über die Grundlagen der Analysis”, Veit, Leipzig.
  • Ziegler, Albert, 2012, „Generalizarea realizării și modelelor Heyting pentru teoria constructivă a seturilor”, Analele logicii pure și aplicate, 163 (2): 175–184.
  • –––, 2014, „O ierarhie cumulativă a seturilor pentru teoria constructivă a seturilor”, Matematica Logică Trimestrială, 60 (1-2): 21-30.

Instrumente academice

pictograma omului sep
pictograma omului sep
Cum se citează această intrare.
pictograma omului sep
pictograma omului sep
Previzualizați versiunea PDF a acestei intrări la Societatea Prietenii SEP.
pictograma inpho
pictograma inpho
Căutați acest subiect de intrare la Proiectul Ontologia Filozofiei pe Internet (InPhO).
pictograma documente phil
pictograma documente phil
Bibliografie îmbunătățită pentru această intrare la PhilPapers, cu link-uri către baza de date a acesteia.

Alte resurse de internet

  • Aczel, P. și M. Rathjen, 2010, Note privind teoria seturilor constructive, schiță de carte, disponibilă online.
  • Kapulkin, C. și PL Lumsdaine, 2012, „Modelul simplial al fundațiilor univalente (după Voevodsky)”, preimprimat la arXiv.org.
  • Teoria setului algebric, de S. Awodey (Carnegie Mellon).

[Vă rugăm să contactați autorul pentru alte sugestii.]

Recomandat: