Mengenlehre: Konstruktives Und Intuitionistisches ZF

Inhaltsverzeichnis:

Mengenlehre: Konstruktives Und Intuitionistisches ZF
Mengenlehre: Konstruktives Und Intuitionistisches ZF

Video: Mengenlehre: Konstruktives Und Intuitionistisches ZF

Video: Mengenlehre: Konstruktives Und Intuitionistisches ZF
Video: Das Zermelo-Fraenkel-Axiomensystem der Mengenlehre (ZF) 2023, Dezember
Anonim

Eintragsnavigation

  • Eintragsinhalt
  • Literaturverzeichnis
  • Akademische Werkzeuge
  • Freunde PDF Vorschau
  • Autor und Zitierinfo
  • Zurück nach oben

Mengenlehre: Konstruktives und intuitionistisches ZF

Erstveröffentlichung am 20. Februar 2009; inhaltliche Überarbeitung Mi 13. Februar 2019

Konstruktive und intuitionistische Zermelo-Fraenkel-Mengen-Theorien sind axiomatische Theorien von Mengen im Stil der Zermelo-Fraenkel-Mengen-Theorie (ZF), die auf intuitionistischer Logik basieren. Sie wurden in den 1970er Jahren eingeführt und stellen einen formalen Kontext dar, in dem die Mathematik auf der Grundlage intuitionistischer Logik kodifiziert werden kann (siehe den Eintrag zur konstruktiven Mathematik). Sie sind in der Standardsprache erster Ordnung der Zermelo-Fraenkel-Mengenlehre formuliert und verwenden inhärent konstruktive Ideen nicht direkt. Bei der Arbeit in konstruktivem und intuitionistischem ZF können wir uns daher in gewissem Maße auf unsere Vertrautheit mit ZF und seinen Heuristiken verlassen.

Ungeachtet der Ähnlichkeiten mit der klassischen Mengenlehre unterscheiden sich die durch konstruktive und intuitionistische Mengenlehre definierten Mengenkonzepte erheblich von denen der klassischen Tradition; Sie unterscheiden sich auch voneinander. Die Techniken, die verwendet werden, um in ihnen zu arbeiten und um metamathematische Ergebnisse über sie zu erhalten, weichen in gewisser Hinsicht auch von der klassischen Tradition ab, da sie sich der intuitionistischen Logik verpflichtet fühlen. Tatsächlich steht, wie es in intuitionistischen Umgebungen üblich ist, eine Vielzahl semantischer und beweistheoretischer Methoden zur Untersuchung konstruktiver und intuitionistischer Mengen-Theorien zur Verfügung.

Dieser Eintrag stellt die Hauptmerkmale konstruktiver und intuitionistischer Mengenlehre vor. Da das Feld schnell wächst, können wir uns nur kurz an einige wichtige Aspekte der Ergebnisse und verfügbaren Techniken erinnern. Wir konzentrieren uns mehr auf die konstruktive Mengenlehre, um wichtige grundlegende Probleme hervorzuheben, die sich darin ergeben. Beachten Sie, dass wir einen auffälligen Teil der Literatur zu konstruktivem und intuitionistischem ZF weglassen, der sich auf ihre kategorialen Interpretationen bezieht. In diesem Bereich haben sich im Laufe der Jahre große Entwicklungen ergeben, so dass eine angemessene Behandlung dieser Fortschritte eine erhebliche Erweiterung dieses Eintrags erforderlich machen würde. Der interessierte Leser möchte möglicherweise den Eintrag zur Kategorietheorie und ihre Referenzen konsultieren (siehe auch den Anhang Programmatic Reading Guide).

  • 1. Die Essenz der konstruktiven und intuitionistischen Mengenlehre

    • 1.1 Axiomatische Freiheit
    • 1.2 Konstruktive versus intuitionistische Mengenlehre

    • 1.3 Prädikativität in der konstruktiven Mengenlehre

      • 1.3.1 Unvorhersehbarkeit der Trennung
      • 1.3.2 Unvorhersehbarkeit von Powerset
      • 1.3.3 Das konstruktive Universum der Mengen
  • 2. Ursprünge konstruktiver und intuitionistischer Mengenlehre
  • 3. Die Axiomsysteme CZF und IZF
  • 4. Konstruktive Auswahlprinzipien

  • 5. Beweistheorie und Semantik des konstruktiven und intuitionistischen ZF

    • 5.1 Beweistheoretische Stärke
    • 5.2 Große Mengen in konstruktivem und intuitionistischem ZF

    • 5.3 Metamathematische Eigenschaften konstruktiver und intuitionistischer ZF- und semantischer Techniken

      • 5.3.1 Disjunktions- und Existenzmerkmale konstruktiver und intuitionistischer ZF
      • 5.3.2 Realisierbarkeit
      • 5.3.3 Kripke-Modelle und Heyting-bewertete Semantik
      • 5.3.4 Kategoriale Modelle der konstruktiven und intuitionistischen Mengenlehre
      • 5.4 Varianten konstruktiver und intuitionistischer Mengen-Theorien: Mengen-Theorien mit Urelementen und nicht-extensiven Mengen-Theorien
  • Literaturverzeichnis
  • Akademische Werkzeuge
  • Andere Internetquellen
  • Verwandte Einträge

1. Die Essenz der konstruktiven und intuitionistischen Mengenlehre

Konstruktive und intuitionistische Zermelo-Fraenkel-Mengen-Theorien basieren eher auf intuitionistischer als auf klassischer Logik und stellen eine natürliche Umgebung dar, in der Mathematik basierend auf intuitionistischer Logik kodifiziert und studiert werden kann. Für das konstruktive ZF lag der Schwerpunkt auf der Darstellung der mathematischen Praxis des Bischofs (Bischof 1967, Bischof und Brücken 1985).

Für die Grundkonzepte und die treibenden Ideen der intuitionistischen Logik, der konstruktiven Mathematik und des Intuitionismus möchte der Leser möglicherweise die folgenden Einträge konsultieren:

  • intuitionistische Logik,
  • die Entwicklung der intuitionistischen Logik,
  • konstruktive Mathematik,
  • Intuitionismus in der Philosophie der Mathematik,
  • Luitzen Egbertus Jan Brouwer.

Zur klassischen Mengenlehre siehe den Eintrag zur Mengenlehre.

Konstruktives und intuitionistisches ZF basieren auf derselben Sprache erster Ordnung wie die klassische ZF-Mengenlehre, die nur das binäre Prädikatsymbol (in) (Zugehörigkeit) als nicht logisches Symbol hat. Das heißt, sie werden auf der Grundlage einer intuitionistischen Logik erster Ordnung mit Gleichheit plus dem binären Prädikatsymbol (in) formuliert. Wir können also die Einfachheit der satztheoretischen Sprache und unsere Vertrautheit damit nutzen (Myhill 1975). Wie bei der konstruktiven Mathematik im Bischofsstil sind konstruktive und intuitionistische ZF mit der klassischen Tradition vereinbar, in dem Sinne, dass alle ihre Sätze klassisch wahr sind. Tatsächlich sind die beiden formalen Systeme, die wir betrachten werden, konstruktives Zermelo-Fraenkel (CZF) und intuitionistisches Zermelo-Fraenkel (IZF),durch die einfache Hinzufügung des Prinzips der ausgeschlossenen Mitte entsteht ein vollklassischer ZF.

1.1 Axiomatische Freiheit

Die klassische Zermelo-Fraenkel-Mengenlehre basiert auf der klassischen Prädikatenlogik erster Ordnung mit Gleichheit. Zu den logischen Prinzipien gehören Axiome und Schemata, die den Begriff der Menge beschreiben, den die Theorie kodifiziert. Diese Prinzipien können in drei Arten eingeteilt werden. Erstens gibt es Prinzipien, die es uns ermöglichen, aus gegebenen Mengen neue Mengen zu bilden. Zum Beispiel erlaubt uns das Axiom des Paares, eine Menge zu bilden, die das Paar von zwei gegebenen Mengen ist. Zweitens gibt es Prinzipien, die Eigenschaften der satztheoretischen Struktur festlegen. Zum Beispiel identifiziert das Axiom der Extensionalität alle Mengen mit den gleichen Elementen. Drittens und schließlich gibt es Axiome, die die Existenz bestimmter Mengen behaupten. Das Axiom der Unendlichkeit besagt also, dass es eine unendliche Menge gibt. Diese Prinzipien zusammen werden gewöhnlich als satztheoretische Prinzipien bezeichnet.

Bei der Einführung von Versionen von ZF, die auf intuitionistischer Logik basieren, besteht der erste Schritt darin, das Prinzip der ausgeschlossenen Mitte (EM) aus der Logik zu entfernen. Der nächste Schritt besteht darin, einen guten Bestand an satztheoretischen Prinzipien zu wählen, die den gewünschten Begriff der konstruktiven Menge getreu wiedergeben. Diese Aufgaben stellen sich als schwieriger heraus, als man zunächst erwartet hätte. Bekanntlich können Systeme, die auf einer „schwächeren“Logik basieren, zwischen Aussagen unterscheiden, die unter dem Gesichtspunkt einer „stärkeren“Logik äquivalent sind. Im Fall der Mengenlehre werden einige der ZF-Axiome oder -Schemata häufig durch eine von vielen klassisch äquivalenten Formulierungen dargestellt. Klassischerweise ist es nur eine Frage der Bequemlichkeit, welche zu einem bestimmten Zeitpunkt verwendet werden soll. Bei der Arbeit auf der Basis intuitionistischer Logik jedochVerschiedene Formulierungen eines klassischen Axioms können sich als unterschiedlich herausstellen (nicht äquivalent). Tatsächlich kann man sich neue Aussagen vorstellen, die klassisch einem ZF-Axiom entsprechen, aber intuitiv von diesem getrennt sind (zum Beispiel das Axiom der CZF-Teilmengen-Sammlung (Aczel 1978)).

Was den ersten Schritt betrifft, der darin besteht, das Prinzip der ausgeschlossenen Mitte aus der Logik zu streichen, stellt sich heraus, dass es nicht ausreicht, dieses Prinzip einfach aus der zugrunde liegenden Logik zu entfernen. Das heißt, es reicht nicht aus, den intuitionistischen und nicht den klassischen Prädikatenkalkül als Grundlage zu nehmen. Wir müssen auch sicherstellen, dass die satztheoretischen Axiome keine unerwünschten Formen ausgeschlossener Mitte in unsere Theorie zurückbringen. Zum Beispiel brauchen wir, wie von Myhill (1973) festgestellt, besondere Sorgfalt bei der Auswahl einer geeigneten Aussage für das Axiom der Gründung. Foundation wird in die Mengenlehre eingeführt, um Mengen auszuschließen, die Mitglieder ihrer selbst und damit (in) - Ketten von Mengen sind. Die übliche Formulierung der Stiftung besagt, dass jede bewohnte Menge (eine Menge mit mindestens einem Element) ein kleinstes Element in Bezug auf die Zugehörigkeitsbeziehung hat. Diese Aussage ist jedochEs kann gezeigt werden, dass auf der Grundlage bescheidener satztheoretischer Annahmen konstruktiv inakzeptable Fälle ausgeschlossener Mitte entstehen. Daher muss die übliche Formulierung der Grundlage in einer auf intuitionistischer Logik basierenden Mengenlehre weggelassen werden. Einen Beweis finden Sie im ergänzenden Dokument:

Mengen-theoretische Prinzipien, die mit der intuitionistischen Logik unvereinbar sind.

Der typische Schritt bei der Formulierung von Mengen-Theorien auf der Grundlage intuitionistischer Logik besteht darin, die Grundlage durch das klassisch äquivalente Schema der Mengen-Induktion zu ersetzen, das nicht die gleichen „Nebenwirkungen“hat, aber ähnliche Konsequenzen hat. [1]

Was den zweiten Schritt betrifft, der sich auf die Auswahl eines guten Bestands an satztheoretischen Prinzipien bezieht, so haben die Schemata des Ersetzens und Trennens und das Axiom des Potenzsatzes die meiste Aufmerksamkeit auf sich gezogen. Die genaue Formulierung dieser Grundsätze finden Sie im ergänzenden Dokument:

Axiome von CZF und IZF.

Hier ist das folgende ein typisches Szenario. Angesichts der klassischen zwei Varianten eines einzigen satztheoretischen Prinzips erfordert ihr klassischer Äquivalenznachweis irgendwann eine Instanz der ausgeschlossenen Mitte. Im Allgemeinen führt dieser Äquivalenznachweis jedoch nicht zu einem intuitionistischen Kontext, und daher können die klassisch zwei Formen eines Prinzips bei intuitionistischer Arbeit zu zwei unterschiedlichen Prinzipien führen. Die Wahl des einen anstelle des anderen kann daher den Begriff der Menge beeinflussen, den wir so definieren. Im Kontext konstruktiver Mengen-Theorien wie CZF werden Machtmenge und Trennung durch intuitionistisch schwächere Prinzipien ersetzt. Ein Grund dafür ist, dass die volle Stärke des Kraftsatzes und die vollständige Trennung als unnötig angesehen werden.da ihre schwächeren Substitute für die Durchführung konstruktiver Mathematik zu genügen scheinen. Ein weiterer Grund ist, dass sie als philosophisch problematisch angesehen werden, da sie Formen der Impredikativität in die Mengenlehre einführen können (siehe Abschnitt über Prädikativität in der konstruktiven Mengenlehre). Der Fall von Ersatz gegen Sammlung ist irgendwie komplexer (siehe zum Beispiel die Artikel (Friedman und Scedrov 1985), (Rathjen 2005) und (Rathjen 2012)). Es ist hervorzuheben, dass die Annahme der üblichen Formulierung der Grundlage zwar gegen die Annahme der intuitionistischen Logik als Hintergrundlogik verstößt, die Prinzipien der Trennung und des Machtsatzes jedoch überhaupt nicht mit der intuitionistischen Logik unvereinbar sind, so dass sie integraler Bestandteil der intuitionistische Mengenlehre IZF (Friedman 1973a). Ein weiterer Grund ist, dass sie als philosophisch problematisch angesehen werden, da sie Formen der Impredikativität in die Mengenlehre einführen können (siehe Abschnitt über Prädikativität in der konstruktiven Mengenlehre). Der Fall von Ersatz gegen Sammlung ist irgendwie komplexer (siehe zum Beispiel die Artikel (Friedman und Scedrov 1985), (Rathjen 2005) und (Rathjen 2012)). Es ist hervorzuheben, dass die Annahme der üblichen Formulierung der Grundlage zwar gegen die Annahme der intuitionistischen Logik als Hintergrundlogik verstößt, die Prinzipien der Trennung und des Machtsatzes jedoch überhaupt nicht mit der intuitionistischen Logik unvereinbar sind, so dass sie integraler Bestandteil der intuitionistische Mengenlehre IZF (Friedman 1973a). Ein weiterer Grund ist, dass sie als philosophisch problematisch angesehen werden, da sie Formen der Impredikativität in die Mengenlehre einführen können (siehe Abschnitt über Prädikativität in der konstruktiven Mengenlehre). Der Fall von Ersatz gegen Sammlung ist irgendwie komplexer (siehe zum Beispiel die Artikel (Friedman und Scedrov 1985), (Rathjen 2005) und (Rathjen 2012)). Es ist hervorzuheben, dass die Annahme der üblichen Formulierung der Grundlage zwar gegen die Annahme der intuitionistischen Logik als Hintergrundlogik verstößt, die Prinzipien der Trennung und des Machtsatzes jedoch überhaupt nicht mit der intuitionistischen Logik unvereinbar sind, so dass sie integraler Bestandteil der intuitionistische Mengenlehre IZF (Friedman 1973a).da sie Formen der Impredikativität in die Mengenlehre einführen können (siehe Abschnitt über Prädikativität in der konstruktiven Mengenlehre). Der Fall von Ersatz gegen Sammlung ist irgendwie komplexer (siehe zum Beispiel die Artikel (Friedman und Scedrov 1985), (Rathjen 2005) und (Rathjen 2012)). Es ist hervorzuheben, dass die Annahme der üblichen Formulierung der Grundlage zwar gegen die Annahme der intuitionistischen Logik als Hintergrundlogik verstößt, die Prinzipien der Trennung und des Machtsatzes jedoch überhaupt nicht mit der intuitionistischen Logik unvereinbar sind, so dass sie integraler Bestandteil der intuitionistische Mengenlehre IZF (Friedman 1973a).da sie Formen der Impredikativität in die Mengenlehre einführen können (siehe Abschnitt über Prädikativität in der konstruktiven Mengenlehre). Der Fall von Ersatz gegen Sammlung ist irgendwie komplexer (siehe zum Beispiel die Artikel (Friedman und Scedrov 1985), (Rathjen 2005) und (Rathjen 2012)). Es ist hervorzuheben, dass die Annahme der üblichen Formulierung der Grundlage zwar gegen die Annahme der intuitionistischen Logik als Hintergrundlogik verstößt, die Prinzipien der Trennung und des Machtsatzes jedoch überhaupt nicht mit der intuitionistischen Logik unvereinbar sind, so dass sie integraler Bestandteil der intuitionistische Mengenlehre IZF (Friedman 1973a). Es ist hervorzuheben, dass die Annahme der üblichen Formulierung der Grundlage zwar gegen die Annahme der intuitionistischen Logik als Hintergrundlogik verstößt, die Prinzipien der Trennung und des Machtsatzes jedoch überhaupt nicht mit der intuitionistischen Logik unvereinbar sind, so dass sie integraler Bestandteil der intuitionistische Mengenlehre IZF (Friedman 1973a). Es ist hervorzuheben, dass die Annahme der üblichen Formulierung der Grundlage zwar gegen die Annahme der intuitionistischen Logik als Hintergrundlogik verstößt, die Prinzipien der Trennung und des Machtsatzes jedoch überhaupt nicht mit der intuitionistischen Logik unvereinbar sind, so dass sie integraler Bestandteil der intuitionistische Mengenlehre IZF (Friedman 1973a).

Zusammenfassend besteht die erste Aufgabe bei der Formulierung einer auf intuitionistischer Logik basierenden Mengenlehre darin, das Prinzip der ausgeschlossenen Mitte auszuschließen, einschließlich jener Fälle, die in bekannten Formulierungen satztheoretischer Axiome verborgen sein könnten. Die nächste Aufgabe besteht darin, eine Version jedes klassischen Prinzips auszuwählen, die den gewünschten Begriff der Menge am besten charakterisiert. Dies eröffnet eine Reihe von Entscheidungen, die getroffen werden können, da mehrere intuitionistische Prinzipien einem klassischen Prinzip entsprechen können. Es sollte betont werden, dass aus konstruktiver Sicht diese Vielzahl von Optionen (und damit Systemen) eine äußerst wünschenswerte Situation darstellt, anstatt Unbehagen zu verursachen, da sie eine Form der „axiomatischen Freiheit“darstellt. Zum Beispiel können wir zwischen einer Reihe von mathematischen Begriffen unterscheiden und so unsere Intuitionen besser als unterschiedlich erfassen. Es gibt uns auch die Freiheit, die Begriffe und Theorien zu wählen, die am besten zu einem bestimmten Kontext passen. Darüber hinaus können wir durch die Übernahme intuitionistischer Logik Prinzipien in unsere Theorien aufnehmen, die klassisch sehr stark sind, ohne uns auf ihre klassische Stärke festlegen zu müssen. Zum Beispiel kann man einer schwachen konstruktiven Mengenlehre einen Begriff der unzugänglichen Menge hinzufügen und eine prädikative Theorie erhalten, während derselbe Begriff, der in einen klassischen Kontext eingebettet ist, extrem stark wird (siehe die Abschnitte über Prädikativität in der konstruktiven Mengenlehre und große Mengen in konstruktiven und intuitionistisches ZF). Schließlich ergibt sich natürlich ein reiches Gebiet der (metatheoretischen) Untersuchung der Beziehungen zwischen den resultierenden unterschiedlichen satztheoretischen Systemen. Wie zu erwarten ist, hat diese Freiheit auch einen Preis,Eine hochtechnische Untersuchung der axiomatischen Theorien könnte notwendig sein, um ihre Prinzipien zu unterscheiden und einige ihrer Feinheiten aufzudecken. Dies kann wiederum als Vorteil angesehen werden, da es uns zu einer tieferen und klareren Analyse der beteiligten mathematischen Begriffe zwingt und uns dazu veranlasst, neue hochentwickelte Werkzeuge zu entwickeln.

1.2 Konstruktive versus intuitionistische Mengenlehre

Obwohl es viele Mengen von Mengen gibt, die auf intuitionistischer Logik basieren, können wir zwei Haupttrends in der Literatur unterscheiden. Nach dem ersten nehmen wir alles, was in der klassischen ZF-Mengenlehre verfügbar ist, und modifizieren nur jene Prinzipien wie die Grundlage, die eindeutig mit der intuitionistischen Logik unvereinbar sind. Daraus ergeben sich Theorien wie Intuitionistic Zermelo-Fraenkel, IZF, von denen eine Variante bereits in (Friedman 1973a) eingeführt wurde. (Siehe Beeson 1985, Kapitel 8 und 9 und Scedrov 1985 für zwei Umfragen zum IZF.) Das Grundprinzip dieser Theorien scheint darin zu bestehen, dem Mathematiker die leistungsfähigsten Werkzeuge zu gewähren, solange die Kompatibilität mit der intuitionistischen Logik erhalten bleibt. Nach dem zweiten AnsatzNeben der Einhaltung der intuitionistischen Logik führen wir auch Einschränkungen für die zugelassenen satztheoretischen Prinzipien ein, sofern das resultierende System der konstruktiven mathematischen Praxis entspricht. Theorien dieser zweiten Art können daher als Ergebnis eines doppelten Restriktionsprozesses gegenüber dem klassischen ZF angesehen werden. Zuerst wird die intuitionistische Logik eingeschränkt, dann werden die zulässigen satztheoretischen Konstruktionen eingeschränkt. Letzteres ist motiviert durch (1) die Beobachtung, dass schwächere Prinzipien für die konstruktive mathematische Praxis zu genügen scheinen, und (2) den Wunsch, an einer Form der Prädikativität festzuhalten (siehe den nächsten Abschnitt zur Klärung dieses Begriffs der Prädikativität). Paradigmatische Beispiele für die letztere Art von Systemen sind Myhills Konstruktive Mengenlehre (Myhill 1975),Friedmans System B (Friedman 1977) und Aczels konstruktive Zermelo-Fraenkel-Mengenlehre CZF (Aczel 1978; 1982; 1986, Aczel & Rathjen 2001; Aczel & Rathjen 2010, Other Internet Resources). Wir können auch sagen, dass bei diesem zweiten Ansatz die grundlegende Motivation die Praxis in höherem Maße beeinflusst.

Im Folgenden verwenden wir eine heute häufig vorkommende Konvention, nach der sich das Adjektiv „intuitionistisch“auf solche Mengen-Theorien wie IZF bezieht, die nicht aussagekräftig sind, während sich „konstruktiv“auf Mengen-Theorien wie CZF bezieht, die einer Form der Prädikativität entsprechen. Beachten Sie jedoch, dass diese Konvention in der Literatur nicht immer befolgt wird. Tatsächlich wurde das Adjektiv "konstruktiv" auch verwendet, um impredikative Theorien zu bezeichnen, und "intuitionistisch", um prädikative grundlegende Theorien wie die Martin-Löf-Typentheorie zu bezeichnen (Martin-Löf 1975; 1984). Es ist auch erwähnenswert, dass sich die vorliegende Konvention zur Verwendung der Wörter "konstruktiv" und "intuitionistisch" von der im Kontext der konstruktiven Mathematik gemachten unterscheidet (siehe zum Beispiel den Eintrag zur konstruktiven Mathematik sowie Bridges und Richman 1987)..

1.3 Prädikativität in der konstruktiven Mengenlehre

Der Prädikativismus hat seinen Ursprung in den Schriften von Poincaré und Russell, die auf die Paradoxien reagierten, die im frühen 20. Jahrhundert in den Theorien von Cantor und Frege entdeckt wurden. Anschließend leistete Weyl grundlegende Beiträge zum Studium der prädikativen Mathematik (Weyl 1918, siehe auch Feferman 1988). Nach einem Begriff ist eine Definition nicht aussagekräftig, wenn sie ein Objekt unter Bezugnahme auf eine Gesamtheit definiert, die das zu definierende Objekt enthält. Mit seinem Vicious Circle Principle (VCP) wollte Russell die Zirkularität in der Mathematik beseitigen, die sich aus solchen improvisierten Definitionen ergibt. Russell gab verschiedene Formulierungen des VCP an, von denen eine ist:

Was auch immer eine scheinbare Variable enthält, darf kein möglicher Wert dieser Variablen sein (Russell 1908, in van Heijenoort 1967, 163).

Die grundlegende Analyse der Prädikativität von Poincaré, Russell und Weyl hat den Weg für eine Vielzahl logischer Analysen des Begriffs geebnet. Die am häufigsten akzeptierte Analyse geht auf Feferman und Schütte (unabhängig) zurück, die den von Kreisel angegebenen Linien folgen (Kreisel 1958, Feferman 1964 und Schütte 1965; 1965a). Hier hat die Beweistheorie eine zentrale Rolle gespielt. In sehr groben Worten bestand die Idee darin, eine Sammlung von Theorien (eine transfinite Folge von Systemen verzweigter Arithmetik zweiter Ordnung, die durch Ordnungszahlen indiziert sind) herauszugreifen, mit deren Hilfe ein bestimmter Begriff der prädikativen Ordnungszahl charakterisiert werden kann. Die beweistheoretische Analyse dieser Theorien durch Feferman und Schütte hat eine Ordnungszahl identifiziert, die üblicherweise als (Gamma_0) bezeichnet wird und nach dieser Vorstellung die am wenigsten nicht prädikative Ordnungszahl ist. Ein formales System wird als prädikativ gerechtfertigt angesehen, wenn es nachweislich auf ein System verzweigter Arthmetik zweiter Ordnung reduziert werden kann, das durch eine Ordnungszahl kleiner als (Gamma_0) indiziert ist. Daher wird in der Beweistheorie (Gamma_0) normalerweise als die Grenze der Prädikativität angesehen. (Siehe Feferman 2005 für eine genauere informelle Darstellung dieses Begriffs der Prädikativität und für weitere Referenzen. Siehe auch Crosilla 2017. Der Leser kann auch den Abschnitt über Prädikativismus im Eintrag über Philosophie der Mathematik und den Eintrag über Paradoxien und zeitgenössische Logik konsultieren.).(Siehe Feferman 2005 für eine genauere informelle Darstellung dieses Begriffs der Prädikativität und für weitere Referenzen. Siehe auch Crosilla 2017. Der Leser kann auch den Abschnitt über Prädikativismus im Eintrag über Philosophie der Mathematik und den Eintrag über Paradoxien und zeitgenössische Logik konsultieren.).(Siehe Feferman 2005 für eine genauere informelle Darstellung dieses Begriffs der Prädikativität und für weitere Referenzen. Siehe auch Crosilla 2017. Der Leser kann auch den Abschnitt über Prädikativismus im Eintrag über Philosophie der Mathematik und den Eintrag über Paradoxien und zeitgenössische Logik konsultieren.).

Für konstruktive Grundlagentheorien wurde ein „liberalerer“Ansatz für den Prädikativismus vorgeschlagen, beginnend mit der Arbeit von Lorenzen, Myhill und Wang in den späten 1950er Jahren (siehe z. B. Lorenzen und Myhill 1959). Die treibende Idee ist, dass sogenannte induktive Definitionen im Bereich der konstruktiven Mathematik erlaubt sein sollten. Die intuitive Rechtfertigung induktiver Definitionen hängt damit zusammen, dass sie durch endliche Regeln „von unten nach oben“ausgedrückt werden können. Die beweistheoretische Stärke von Theorien induktiver Definitionen geht weit über die Grenzen von Feferman und Schütte hinaus (Buchholz, Feferman, Pohlers und Sieg 1981). Daher werden relativ starke Theorien in den heutigen Grundlagen der konstruktiven Mathematik als prädikativ angesehen. Dieser liberalere Begriff der Prädikativität wurde oft als generalisierte Prädikativität bezeichnet. In diesem Eintrag schreiben wir einfach Prädikativität für generalisierte Prädikativität und nennen Prädikativität angesichts der natürlichen Zahlen die bekanntere Form der Prädikativität, die im klassischen Kontext auftritt und von Kreisel, Feferman und Schütte analysiert wurde.

Ein Beispiel für eine prädikative Theorie in diesem Sinne ist die konstruktive Mengenlehre CZF, da ihre beweistheoretische Stärke dieselbe ist wie die einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Das System IZF ist stattdessen beeindruckend, da seine beweistheoretische Stärke der des gesamten klassischen ZF entspricht (Friedman 1973a).

In Mengen-Theorien, die auf intuitionistischer Logik basieren, wird Prädikativität normalerweise durch Einschränkung der Prinzipien der Trennung und der Machtmenge erreicht, da diese die Hauptquellen für Impredikativität zu sein scheinen (wenn das Unendlichkeits-Axiom angenommen wird).

1.3.1 Unvorhersehbarkeit der Trennung

Das Trennungsschema ermöglicht es uns, eine Teilmenge einer gegebenen Menge zu bilden, deren Elemente eine gegebene Eigenschaft erfüllen (ausgedrückt durch eine Formel in der Sprache der Mengenlehre). Wenn eine Menge (B) und eine Formel (phi (X)) gegeben sind, können wir durch Trennung eine neue Menge konstruieren, die Menge der Elemente (X) von (B), für die (phi) gilt. Dies wird normalerweise informell dargestellt als: ({X / in B: / phi (X) }). Eine Trennung kann zu Impredikativität führen, wenn die Formel (phi) unbegrenzte Quantifizierer enthält, die sich über das gesamte Universum von Mengen erstrecken. Tatsächlich können wir uns bei der Definition der neuen Menge durch Trennung auf genau diese Menge beziehen, was Russells VCP widerspricht. Wenn wir beispielsweise eine Menge (C) durch Trennung als ({X / in B: / für alle Y / psi (X, Y) }) definieren, gehört (C) zu den (Y), die auf die Eigenschaft (psi) überprüft werden müssen. Diese Form der Impredikativität wird in der konstruktiven Mengenlehre vermieden, indem das Trennungsschema eingeschränkt wird: indem verlangt wird, dass alle in der Formel (phi) vorkommenden Quantifizierer nur über "zuvor konstruierten" Mengen liegen. Syntaktisch bedeutet dies, dass wir bei gegebener Menge (B) eine neue Menge ({X / in B: / phi (X) }) durch Trennung nur dann bilden können, wenn alle Quantifizierer in (phi)) sind begrenzt; Das heißt, nur wenn alle Quantifizierer in (phi) die Form (für alle X (X / in Y / rightarrow / ldots)) oder (existiert X (X / in Y / wedge / ldots) haben)), für einige Mengen (Y).\ phi (X) }) durch Trennung nur, wenn alle Quantifizierer in (phi) begrenzt sind; Das heißt, nur wenn alle Quantifizierer in (phi) die Form (für alle X (X / in Y / rightarrow / ldots)) oder (existiert X (X / in Y / wedge / ldots) haben)), für einige Mengen (Y).\ phi (X) }) durch Trennung nur, wenn alle Quantifizierer in (phi) begrenzt sind; Das heißt, nur wenn alle Quantifizierer in (phi) die Form (für alle X (X / in Y / rightarrow / ldots)) oder (existiert X (X / in Y / wedge / ldots) haben)), für einige Mengen (Y).

Wir können sehen, dass die Einschränkung der Trennung auf diese Weise die Impredikativität vermeidet, indem beobachtet wird, dass die beweistheoretische Stärke von CZF, die nur die Trennung eingeschränkt hat, im Bereich der Prädikativität liegt. Durch Hinzufügen einer vollständigen Trennung zu CZF erhält man jedoch eine impredikative Theorie, die tatsächlich die gleiche beweistheoretische Stärke wie die vollständige Arithmetik zweiter Ordnung aufweist (Lubarsky 2006). Siehe auch Abschnitt 5 für eine Diskussion der Rolle der Beweistheorie bei der Analyse konstruktiver und intuitionistischer Mengen-Theorien.

1.3.2 Unvorhersehbarkeit von Powerset

Das Axiom der Potenzmenge ermöglicht es uns, eine Menge aller Teilmengen einer gegebenen Menge zu bilden. Ein Beispiel für die uneingeschränkte Verwendung der Potenzmenge ist die Definition einer Teilmenge der natürlichen Zahlen (N) wie folgt: (B: = {n / in N: / forall C / subseteq N / phi (n, C) }), wobei (phi) als begrenzte Formel angesehen werden kann. Eine Form der Zirkularität entsteht hier, da (B) selbst zu den Teilmengen von (N) gehört, die auf (phi) überprüft werden müssen. Wie von Myhill (1975, 354) betont, ist die Potenzmenge aus konstruktiver Sicht schwer zu rechtfertigen: Sie fasst alle Teilmengen einer gegebenen Menge zusammen, schreibt jedoch keine Regel vor, die die Menge aus der zuvor gegebenen Menge "konstruiert" setzt, wie es die Prädikativität zu erfordern scheint.

Myhill schreibt:

Power Set scheint im Vergleich zu den anderen Axiomen besonders unkonstruktiv und unkompliziert zu sein: Es geht nicht darum, wie die anderen, bereits zusammengestellte Sets zusammenzusetzen oder auseinanderzunehmen, sondern aus der Gesamtheit aller Sets diejenigen auszuwählen, die in der Beziehung stehen der Aufnahme in einen bestimmten Satz. (Myhill 1975, 351).

Die Potenzmenge scheint im Fall von unendlichen Mengen besonders problematisch zu sein, da "wir keine Ahnung haben, was eine beliebige Teilmenge einer unendlichen Menge ist; es gibt keine Möglichkeit, sie alle zu erzeugen, und daher haben wir keine Möglichkeit, die Menge aller zu bilden." sie "(Myhill 1975, 354). Infolgedessen scheint es keine Möglichkeit zu geben, der Menge aller Teilmengen einer unendlichen Menge einen konstruktiven Sinn zu geben.

Myhill stellt entscheidend fest, dass für die konstruktive Mathematik kein Bischofssatz benötigt wird, da er durch eine seiner Konsequenzen ersetzt werden kann. Dies wird oft als Myhills Potenzierungsaxiom bezeichnet und besagt, dass wir eine Menge aller Funktionen von einer gegebenen Menge zur anderen bilden können. Dieses Axiom entspricht eindeutig der Potenzmenge in einem klassischen Kontext, in dem Teilmengen einer gegebenen Menge durch charakteristische Funktionen dargestellt werden können. In Ermangelung des Prinzips der ausgeschlossenen Mitte sind Leistungssatz und Potenzierung jedoch nicht gleichwertig. Myhills grundlegende Beobachtung ist, dass die Potenzierung ausreicht, um die Mathematik von (Bischof 1967) durchzuführen; Zum Beispiel ermöglicht es die Konstruktion der (Cauchy) reellen Zahlen innerhalb der konstruktiven Mengenlehre. Myhill behauptet, dass Potenzierung konstruktiv bedeutsam ist, weil eine Funktion eine Regel ist,ein endliches Objekt, das tatsächlich gegeben werden kann.

Er schreibt auch, dass sich der Fall der Potenzmenge von dem der Potenzierung unterscheidet, als:

Selbst im Fall von unendlichen Mengen (A) und (B) haben wir eine Idee einer willkürlichen Abbildung von (A) in (B). Eine beliebige Zuordnung von (mathbf {Z}) zu (mathbf {Z}) ist eine teilweise rekursive Funktion zusammen mit dem Beweis, dass die Berechnung immer endet. Ein ähnlicher Bericht kann über eine beliebige reelle Funktion gegeben werden. Es gibt keine entsprechende Erklärung für "beliebige Teilmenge". (Myhill 1975, 354).

Myhills Potenzierungsaxiom ist jetzt Teil aller wichtigen Systeme der konstruktiven Mengenlehre. Im Fall von CZF hat man tatsächlich eine Verstärkung der Potenzierung, die als Teilmengenerfassung bekannt ist, was auch eine Schwächung der Potenzmenge darstellt. Eine Verallgemeinerung der Potenzierung findet sich auch in der konstruktiven Typentheorie.

Im Fall von CZF kann die Behauptung, dass das Hinzufügen des Axioms des Potenzsatzes eine Form der Impredikativität induziert, durch ein technisches Ergebnis belegt werden. Rathjen (2012b) zeigt, dass die durch das Potenzsatz-Axiom erweiterte CZF die Stärke der klassischen Zermelo-Mengen-Theorie übersteigt, und daher bringt uns die Hinzufügung des Potenzsatz-Axioms zu CZF zu einer vollständig impedikativen Theorie. Dies zeigt auch, dass die Implikation von der Potenzmenge zur Teilmengenerfassung nicht umgekehrt werden kann, da die beweistheoretische Stärke von CZF weit unter der der Zermleo-Mengenlehre liegt. Mit anderen Worten, das Potenzmengenaxiom ist viel stärker als sowohl die Potenzierung als auch die Teilmengenerfassung.

1.3.3 Das konstruktive Universum der Mengen

Nachdem wir angemessene Einschränkungen für die Festlegung und Trennung von Macht eingeführt haben, könnten wir nun einem erheblichen Einwand gegenüberstehen. Konstruktive und intuitionistische Mengenlehre können als Modifikationen der klassischen ZF-Mengenlehre angesehen werden, die erhalten werden durch: (1) Ersetzen der klassischen durch intuitionistische Logik und (2) genaue Auswahl derjenigen, die für bestimmte Zwecke geeigneter erscheinen, unter verschiedenen klassisch äquivalenten Prinzipien. Zum Beispiel könnten wir Prinzipien wählen, die ausreichen, um eine bestimmte mathematische Praxis darzustellen, wie zum Beispiel die Mathematik im Bischofsstil. Der resultierende Mengenbegriff könnte jedoch dunkel werden und die Wahl der satztheoretischen Prinzipien könnte bis zu einem gewissen Grad als willkürlich erscheinen. Im Falle des intuitionistischen ZF kann man die Wahl der satztheoretischen Prinzipien rechtfertigen, indem man ihre semantischen Interpretationen untersucht.als Heyting-Semantik oder durch Betrachten seiner kategorialen Modelle. Um diese Art von Einwänden zu verhindern, hat Aczel im Fall der konstruktiven Mengenlehre eine Interpretation von CZF in einer Version der Martin-Löf-Typentheorie gegeben (Aczel 1978). Die Behauptung ist, dass dem CZF-Mengenbegriff eine klare konstruktive Bedeutung zugewiesen wird, indem seine Bedeutung in der Martin-Löf-Typentheorie betrachtet wird, da letztere normalerweise als eine genaue und vollständig motivierte Formulierung eines konstruktiven Mengenbegriffs angesehen wird. Aczels Interpretation von CZF in der konstruktiven Typentheorie wird durch Interpeting von Mengen als Bäume in der Typentheorie gegeben. Das heißt, in der konstruktiven Typentheorie wird das Universum der Mengen von CZF durch einen Typ V iterativer Mengen dargestellt, die über dem Universum U kleiner Typen aufgebaut sind (Aczel 1978; Martin-Löf 1984). Diese Interpretation unterstreicht deutlich die (verallgemeinerte) Prädikativität von CZF, dessen Mengen als induktiv aufgebaute Bäume angesehen werden können und deren satztheoretisches Universum ebenfalls eine klare induktive Struktur aufweist.

Die Prädikativität von CZF und verwandten Systemen steht im Einklang mit philosophischen Positionen, die häufig mit der Verwendung intuitionistischer Logik verbunden sind. Insbesondere scheint es, dass, wenn wir die mathematischen Objekte konstruieren, zum Beispiel wenn die mathematischen Objekte irgendeine Art von mentalen Konstruktionen sind, der Rückgriff auf improvisatorische Definitionen eine unerwünschte Form der Zirkularität erzeugen würde. Dies steht eindeutig im Gegensatz zu einer Ansicht, die häufig mit der klassischen Mengenlehre in Verbindung gebracht wird, für die unsere mathematische Aktivität als schrittweise Offenlegung von Eigenschaften des Universums von Mengen angesehen werden kann, dessen Existenz von uns unabhängig ist. Eine solche Sichtweise ist normalerweise mit der Verwendung klassischer Logik und Impredikativität bei der Untersuchung des satztheoretischen Universums verbunden. Prädikativität wird auch oft als mit der althergebrachten Unterscheidung zwischen tatsächlicher und potentieller Unendlichkeit verbunden angesehen. Prädikative (und damit insbesondere konstruktive) Theorien werden oft als Vermeidung von Verweisen auf die tatsächliche Unendlichkeit und nur als Verpflichtung zur potenziellen Unendlichkeit angesehen (Dummett 2000, Fletcher 2007). Dies scheint wiederum besonders im Einklang mit jenen philosophischen Positionen zu stehen, die die menschliche Dimension unserer mathematischen Tätigkeit hervorheben, indem sie zum Beispiel die mathematischen Objekte und die Wahrheit von Aussagen über sie als von uns abhängig betrachten. Ein anderer verwandter Aspekt wird oft in Bezug auf die Prädikativität gesehen: Wenn das Universum der Mengen durch unsere eigene mathematische Aktivität schrittweise aufgebaut wird, wäre es natürlich, es auch als offen zu betrachten. Aus diesem Grund in einem konstruktiven Kontext,Wo die Ablehnung der klassischen Logik das Erfordernis der Prädikativität erfüllt, wird das Universum der Mengen oft als offenes Konzept beschrieben, als Universum „in Fieri“. Diese Idee wird besonders gut in der konstruktiven Typentheorie veranschaulicht, in der Per Martin-Löf den Begriff des typentheoretischen Universums bewusst offen gelassen hat (indem er keine spezifischen Eliminierungsregeln dafür postuliert). Die offene Natur des Universums der Mengen hat den Weg für Erweiterungen durch Reflexionsprinzipien geebnet. Diese wurden sowohl in der Typentheorie als auch in der konstruktiven Mengenlehre untersucht. Siehe (Rathjen 2005a) für eine Übersicht der Ergebnisse und eine grundlegende Diskussion sowie Abschnitt 5.2. Für eine formale Analyse des konstruktiven Universums von Mengen und einen Vergleich mit der Von Neumann-Hierarchie siehe (Ziegler 2014). Das Universum der Mengen wird oft als offenes Konzept beschrieben, als Universum „in Fieri“. Diese Idee wird besonders gut in der konstruktiven Typentheorie veranschaulicht, in der Per Martin-Löf den Begriff des typentheoretischen Universums bewusst offen gelassen hat (indem er keine spezifischen Eliminierungsregeln dafür postuliert). Die offene Natur des Universums der Mengen hat den Weg für Erweiterungen durch Reflexionsprinzipien geebnet. Diese wurden sowohl in der Typentheorie als auch in der konstruktiven Mengenlehre untersucht. Siehe (Rathjen 2005a) für eine Übersicht der Ergebnisse und eine grundlegende Diskussion sowie Abschnitt 5.2. Für eine formale Analyse des konstruktiven Universums von Mengen und einen Vergleich mit der Von Neumann-Hierarchie siehe (Ziegler 2014). Das Universum der Mengen wird oft als offenes Konzept beschrieben, als Universum „in Fieri“. Diese Idee wird besonders gut in der konstruktiven Typentheorie veranschaulicht, in der Per Martin-Löf den Begriff des typentheoretischen Universums bewusst offen gelassen hat (indem er keine spezifischen Eliminierungsregeln dafür postuliert). Die offene Natur des Universums der Mengen hat den Weg für Erweiterungen durch Reflexionsprinzipien geebnet. Diese wurden sowohl in der Typentheorie als auch in der konstruktiven Mengenlehre untersucht. Siehe (Rathjen 2005a) für eine Übersicht der Ergebnisse und eine grundlegende Diskussion sowie Abschnitt 5.2. Für eine formale Analyse des konstruktiven Universums von Mengen und einen Vergleich mit der Von Neumann-Hierarchie siehe (Ziegler 2014).wo der Begriff des typentheoretischen Universums von Per Martin-Löf bewusst offen gelassen wurde (indem keine spezifischen Eliminierungsregeln dafür postuliert wurden). Die offene Natur des Universums der Mengen hat den Weg für Erweiterungen durch Reflexionsprinzipien geebnet. Diese wurden sowohl in der Typentheorie als auch in der konstruktiven Mengenlehre untersucht. Siehe (Rathjen 2005a) für eine Übersicht der Ergebnisse und eine grundlegende Diskussion sowie Abschnitt 5.2. Für eine formale Analyse des konstruktiven Universums von Mengen und einen Vergleich mit der Von Neumann-Hierarchie siehe (Ziegler 2014).wo der Begriff des typentheoretischen Universums von Per Martin-Löf bewusst offen gelassen wurde (indem keine spezifischen Eliminierungsregeln dafür postuliert wurden). Die offene Natur des Universums der Mengen hat den Weg für Erweiterungen durch Reflexionsprinzipien geebnet. Diese wurden sowohl in der Typentheorie als auch in der konstruktiven Mengenlehre untersucht. Siehe (Rathjen 2005a) für eine Übersicht der Ergebnisse und eine grundlegende Diskussion sowie Abschnitt 5.2. Für eine formale Analyse des konstruktiven Universums von Mengen und einen Vergleich mit der Von Neumann-Hierarchie siehe (Ziegler 2014). Diese wurden sowohl in der Typentheorie als auch in der konstruktiven Mengenlehre untersucht. Siehe (Rathjen 2005a) für eine Übersicht der Ergebnisse und eine grundlegende Diskussion sowie Abschnitt 5.2. Für eine formale Analyse des konstruktiven Universums von Mengen und einen Vergleich mit der Von Neumann-Hierarchie siehe (Ziegler 2014). Diese wurden sowohl in der Typentheorie als auch in der konstruktiven Mengenlehre untersucht. Siehe (Rathjen 2005a) für eine Übersicht der Ergebnisse und eine grundlegende Diskussion sowie Abschnitt 5.2. Für eine formale Analyse des konstruktiven Universums von Mengen und einen Vergleich mit der Von Neumann-Hierarchie siehe (Ziegler 2014).

2. Ursprünge konstruktiver und intuitionistischer Mengenlehre

Intuitionistische Versionen von Zermelo-Fraenkel-Mengen-Theorien wurden in den frühen 1970er Jahren von Friedman und Myhill eingeführt. In (Friedman 1973) präsentiert der Autor eine Studie über formale Eigenschaften verschiedener intuitionistischer Systeme und führt für sie eine Erweiterung der Realisierbarkeitsmethode von Kleene ein. Die Realisierbarkeitstechnik wird in (Myhill 1973) angewendet, um die Existenz-Eigenschaft für eine Version der intuitionistischen Zermelo-Fraenkel-Mengen-Theorie (mit Ersatz anstelle der Sammlung) zu zeigen. In einem weiteren grundlegenden Beitrag erweitert Friedman die Doppel-Negations-Übersetzung der intuitonistischen Logik, um klassische und intuitionistische Mengen-Theorien in Beziehung zu setzen (Friedman 1973a). Diese ersten Arbeiten befassen sich bereits mit der Beziehung zwischen einigen wichtigen intuitionistischen Mengenlehre und dem klassischen ZF. Sie klären auch ein Schlüsselmerkmal der Mengenlehre, das auf intuitionistischer Logik basiert.hauptsächlich, dass es leistungsfähigen konstruktiven semantischen Interpretationen wie der Realisierbarkeit zugänglich ist. Diese Techniken werden zur Untersuchung entscheidender metatheoretischer Eigenschaften angewendet, die für den konstruktiven Ansatz typisch sind und von einigen konstruktiven Mengen-Theorien genutzt werden (siehe Abschnitt über semantische Techniken). Diese bahnbrechende Arbeit wurde von Beeson und McCarty vollständig genutzt und erheblich erweitert (siehe Beeson 1985; McCarty 1984). Diese bahnbrechende Arbeit wurde von Beeson und McCarty vollständig genutzt und erheblich erweitert (siehe Beeson 1985; McCarty 1984). Diese bahnbrechende Arbeit wurde von Beeson und McCarty vollständig genutzt und erheblich erweitert (siehe Beeson 1985; McCarty 1984).

Die konstruktive Mengenlehre hat von Anfang an eine ausgeprägtere grundlegende Berufung und ist mit der Mathematik des Bischofs verbunden. Tatsächlich veröffentlichte Bishop 1967 das Buch „Grundlagen der konstruktiven Analyse“(Bishop 1967), das eine neue Ära der Mathematik auf der Grundlage intuitionistischer Logik einleitete (siehe den Eintrag zur konstruktiven Mathematik). Die Monographie regte neue Versuche in der logischen Gemeinschaft an, die vom Bischof angewandten Prinzipien zu klären und formell darzustellen, wenn auch nur auf informeller Ebene. Erste Versuche von Goodman und Myhill (Goodman und Myhill 1972) verwendeten Versionen von Gödels System T (siehe auch (Bishop 1970) für einen ähnlichen Versuch). Myhill kam jedoch zu dem Schluss, dass die daraus resultierende Formalisierung zu komplex und künstlich war (Myhill 1975, 347). Myhill schlug stattdessen ein System vor, das näher am informellen Begriff der Menge liegt, der ursprünglich von Bishop verwendet wurde, und auch näher an der satztheoretischen Tradition. Myhill schreibt (1975, 347):

Wir weigern uns zu glauben, dass die Dinge so kompliziert sein müssen - die Argumentation von (Bischof 1967) sieht sehr glatt aus und scheint direkt von einem bestimmten Konzept der Mengen, Funktionen usw. zu stammen, und wir möchten einen Formalismus entdecken, der isoliert Die Prinzipien, die dieser Konzeption zugrunde liegen, wie die Zermelo-Fraenkel-Mengenlehre, isolieren die Prinzipien, die der klassischen (nichtkonstruktiven) Mathematik zugrunde liegen. Wir wollen, dass diese Prinzipien den Formalisierungsprozess völlig trivial machen, wie es im klassischen Fall der Fall ist.

Wir beobachten hier, dass Myhills konstruktive Mengenlehre Begriffe von Funktion, natürlicher Zahl und Menge unterschieden hatte; es stellte somit eine konstruktive Tradition dar, in der Funktionen und natürliche Zahlen konzeptionell unabhängig von Mengen sind. Ein weiterer grundlegender Schritt in der Entwicklung der konstruktiven Mengenlehre waren Friedmans „Mengen-theoretische Grundlagen für die konstruktive Analyse“(Friedman 1977). Hier wird unter anderem ein System namens B definiert, das die satztheoretischen Prinzipien im Vergleich zu Myhills weiter einschränkt (insbesondere hat es keine Mengeninduktion). Es hat auch eine eingeschränkte Form des Axioms der abhängigen Wahl. Es wird gezeigt, dass System B ausdrucksstark genug ist, um die konstruktive Analyse von Bishop (1967) darzustellen, während es gleichzeitig beweistheoretisch sehr schwach ist (aufgrund des Fehlens einer festgelegten Induktion). System B ist in der Tat eine konservative Erweiterung der Arithmetik (daher liegt es angesichts der in Abschnitt 1.3 kurz erwähnten natürlichen Zahlen weit unter der Prädikativitätsgrenze). Die Systeme von Myhill und Friedman wurden anschließend von Aczel modifiziert, um ein System CZF (Constructive Zermelo-Fraenkel) zu erhalten, das vollständig mit der ZF-Sprache kompatibel ist (Aczel 1978, 1982, 1986; Aczel und Rathjen 2001; 2010). CZF enthielt auch keine Auswahlprinzipien. Aczel gab eine Interpretation von CZF in der Martin-Löf-Typentheorie mit dem Ziel, den konstruktiven Charakter der Mengenlehre zu bekräftigen. Er stärkte auch einige der Prinzipien von Myhills System (nämlich Sammlung und Potenzierung) mit der Begründung, dass die stärkeren Versionen immer noch durch die Interpretation in der Typentheorie bestätigt werden.

Andere grundlegende Systeme für die konstruktive Mathematik im Bischofsstil wurden in den frühen 1970er Jahren eingeführt. Zum Beispiel: explizite Mathematik von S. Feferman (Feferman 1975) und die bereits erwähnte Intuitionistische Typentheorie (Martin-Löf 1975; 1984). Die konstruktive Typentheorie wird normalerweise als die zufriedenstellendste Grundlage für die konstruktive Mathematik im Bischofsstil angesehen. Sowohl die Typentheorie als auch die explizite Mathematik können so gesehen werden, dass sie den rechnerischen Inhalt der konstruktiven Mathematik direkter ausdrücken. Insbesondere die Typentheorie kann als sehr allgemeine und ausdrucksstarke Programmiersprache gelesen werden. Konstruktive und intuitionistische Mengen-Theorien zeigen ihren Recheninhalt nur indirekt durch ihre semantischen Interpretationen (siehe z. B. (Aczel 1977), (Lipton 1995) und den Abschnitt über semantische Techniken).

3. Die Axiomsysteme CZF und IZF

Für einen Leser, der bereits mit der ZF-Mengenlehre vertraut ist, erinnern wir uns nun kurz an die Axiome der Systeme CZF und IZF. Für eine vollständige Liste und eine Erklärung ihrer Axiome verweisen wir stattdessen auf das ergänzende Dokument:

Axiome von CZF und IZF.

CZF und IZF werden auf der Grundlage einer intuitionistischen Logik erster Ordnung mit Gleichheit formuliert, wobei nur (in) (Mitgliedschaft) als zusätzliches nicht logisches binäres Prädikatsymbol verwendet wird. Ihre satztheoretischen Axiome sind wie folgt.

(mathbf {IZF}) (mathbf {CZF})
Extensionalität (gleich)
Paar (gleich)
Union (gleich)
Unendlichkeit (gleich)
Trennung Eingeschränkte Trennung
Sammlung Starke Sammlung
Powerset Teilmengen-Sammlung
Induktion einstellen (gleich)

Beachten Sie, dass in IZF das Trennungsschema nicht eingeschränkt ist. In CZF wird die Sammlung verstärkt, um die eingeschränkte Trennung auszugleichen. Die Subset-Sammlung ist eine Stärkung des Potenzierungsaxioms von Myhill und ersetzt somit das Powerset von ZF.

4. Konstruktive Auswahlprinzipien

Wenn man die Rolle der klassischen Mengenlehre als Grundlage für die Mathematik diskutiert, betrachtet man normalerweise die Theorie ZFC, dh das Axiomensystem ZF plus das Axiom der Wahl (AC). Man könnte sich daher fragen, welchen Status das Axiom der Wahl in intuitionistischen Umgebungen hat. Die Frage ist besonders wichtig, da das Axiom der Wahl auf den ersten Blick oft als kontrovers und höchst unkonstruktiv angesehen wurde. In konstruktiven Kontexten sieht man jedoch ein besonderes Phänomen. Die übliche Form des Axioms der Wahl wird durch Theorien von Typen wie der Martin-Löf-Typentheorie bestätigt, in denen die Curry-Howard-Korrespondenz gilt (siehe Abschnitt 3.4 des Eintrags über konstruktive Mathematik). Andererseits führt die Annahme des Axioms der Wahl zu Instanzen der ausgeschlossenen Mitte in Extensionskontexten.wo auch eine Form der Trennung verfügbar ist. Dies ist beispielsweise bei konstruktivem und intuitionistischem ZF der Fall. (Für den Beweis siehe das ergänzende Dokument über satztheoretische Prinzipien, die mit intuitionistischer Logik nicht kompatibel sind.) Ein Beweis für die Inkompatibilität von AC mit auf intuitionistischer Logik basierenden erweiterten Mengen-Theorien scheint erstmals in (Diaconescu 1975) in einem kategorialen Kontext erschienen zu sein. Goodman und Myhill liefern ein Argument für Mengen-Theorien, die auf intuitionistischer Logik basieren (Goodman und Myhill 1978).) Ein Beweis für die Unvereinbarkeit von AC mit auf intuitionistischer Logik basierenden Extensionssatztheorien scheint erstmals in (Diaconescu 1975) in einem kategorialen Kontext erschienen zu sein. Goodman und Myhill liefern ein Argument für Mengen-Theorien, die auf intuitionistischer Logik basieren (Goodman und Myhill 1978).) Ein Beweis für die Unvereinbarkeit von AC mit auf intuitionistischer Logik basierenden Extensionssatztheorien scheint erstmals in (Diaconescu 1975) in einem kategorialen Kontext erschienen zu sein. Goodman und Myhill liefern ein Argument für Mengen-Theorien, die auf intuitionistischer Logik basieren (Goodman und Myhill 1978).

Obwohl das Axiom der Wahl sowohl mit konstruktivem als auch mit intuitionistischem ZF nicht kompatibel ist, können den Basissystemen andere Wahlprinzipien hinzugefügt werden, ohne die gleichen unerwünschten Ergebnisse zu erzielen. Zum Beispiel könnte man das Prinzip der zählbaren Wahl (AC (_ 0)) oder das der abhängigen Wahl (DC) hinzufügen. Tatsächlich wurden beide häufig in der konstruktiven mathematischen Praxis eingesetzt. (Die genaue Formulierung finden Sie im ergänzenden Dokument zu Axiomen von CZF und IZF.)

In (Aczel 1978) betrachtete der Autor auch ein Auswahlprinzip namens Presentation Axiom, das behauptet, dass jede Menge das surjektive Bild einer sogenannten Basis ist. Eine Basis ist eine Menge, beispielsweise (B), so dass jede Beziehung zur Domäne (B) eine Funktion zur Domäne (B) erweitert.

Die Kompatibilität all dieser Wahlformen mit der konstruktiven Mengenlehre wurde von Aczel durch die Erweiterung seiner Interpretation von CZF in der Martin-Löf-Typentheorie (Aczel 1982) bewiesen. Rathjen (2006) hat auch verschiedene konstruktive Wahlprinzipien und ihre gegenseitigen Beziehungen berücksichtigt.

Eine letzte Bemerkung: Obwohl konstruktive und intuitionistische Mengen-Theorien mit den gerade erwähnten Wahlprinzipien kompatibel sind, werden die Mengen-Theorien oft ohne Wahlprinzipien definiert. Dies hat das Ziel, einen „pluralistischen“grundlegenden Ansatz zu ermöglichen. Insbesondere möchte man eine Grundtheorie erhalten, die mit jenen Kontexten kompatibel ist (z. B. kategoriale Modelle der Mengenlehre), in denen selbst diese schwächeren Wahlprinzipien möglicherweise nicht validiert werden. Für ähnliche Ideen im Kontext der konstruktiven Typentheorie siehe (Maietti und Sambin 2005, Maietti 2009). Wir möchten hier auch Richmans Appell für eine konstruktive Mathematik erwähnen, die keine Wahlprinzipien verwendet (Richman 2000; 2001).

5. Beweistheorie und Semantik des konstruktiven und intuitionistischen ZF

Wenn wir eine bestimmte mathematische Praxis (oder eine Theorie, die zur Kodifizierung verwendet wird) aus einer philosophischen Perspektive betrachten, müssen wir die darin getroffenen Annahmen sowie die Konsequenzen, die sich aus diesen Annahmen ergeben, mit größtmöglicher Genauigkeit klären. Dies gilt insbesondere für die Arbeit mit Theorien, die auf einer schwächeren Logik als der klassischen basieren und für die eine tiefere und genauere Einsicht erforderlich ist. Es stehen viele technische Tools zur Verfügung, mit denen wir diese Aspekte klären können. Unter den verfügbaren Instrumenten gibt es beweistheoretische Techniken wie beweistheoretische Interpretationen sowie semantische Techniken wie Realisierbarkeit, Kripke-Modelle und Heyting-bewertete Semantik. Tatsächlich sieht man in der Literatur oft das Zusammenspiel von beweistheoretischen und semantischen Techniken. Wir geben hier einen flüchtigen Blick auf einige dieser Themen und schlagen eine weitere Lektüre vor.

5.1 Beweistheoretische Stärke

Ein grundlegendes Thema in der Beweistheorie (insbesondere in dem als Ordinalanalyse bekannten Zweig dieser Disziplin) ist die Klassifizierung von Theorien mittels transfiniter Ordnungszahlen, die ihre "Konsistenzstärke" und "Rechenleistung" messen. Diese Ordnungszahlen geben einen Hinweis darauf, wie stark eine Theorie ist, und bieten daher eine Möglichkeit, verschiedene Theorien zu vergleichen. Zum Beispiel ist die Ordnungszahl (varepsilon_0) die beweistheoretische Ordnungszahl der Peano-Arithmetik und viel kleiner als die Ordnungszahl (Gamma_0), die üblicherweise als "Grenze der Prädikativität" bezeichnet wird (siehe Abschnitt 1.3 oben)). Dies weist darauf hin, dass es prädikativ akzeptable Theorien gibt, die viel stärker sind als die Peano-Arithmetik.

Wie in Abschnitt 1 erläutert, müssen wir für den Schritt vom klassischen ZF zu seinen intuitionistischen Varianten für jedes satztheoretische Axiom eine geeignete Formulierung auswählen: Ein klassisches Axiom kann eine Reihe von intuitionistischen Varianten aufweisen, die sich als nicht äquivalent zueinander herausstellen. Dies spiegelt sich manchmal in der beweistheoretischen Stärke der resultierenden Theorien wider, die je nach den von uns gewählten Prinzipien variieren können. Zum Beispiel haben wir bereits festgestellt, dass wir in CZF keine vollständige Trennung und Potenzmenge haben, die durch die prädikativ akzeptablen Prinzipien der begrenzten Trennung bzw. der Teilmengenerfassung ersetzt werden. Wenn wir jedoch eines dieser Prinzipien zu CZF hinzufügen, erhalten wir improvisatorische Theorien. Die Impredikativität der resultierenden Theorien zeigt sich darin, dass ihre beweistheoretische Stärke die von CZF bei weitem übertrifft.

Es ist nicht überraschend, dass Untersuchungen zur beweistheoretischen Stärke konstruktiver und intutionistischer Mengen-Theorien ein entscheidendes metatheoretisches Instrument zum Verständnis dieser Theorien und ihrer Beziehungen untereinander waren. Untersuchungen zur beweistheoretischen Stärke einer Theorie sind reichhaltig und informativ. Insbesondere hat Feferman (1993) argumentiert, dass eine beweistheoretische Analyse uns dabei helfen kann festzustellen, ob eine bestimmte Theorie einem bestimmten philosophischen Rahmen entspricht: Beispielsweise kann die Analyse ergeben, dass eine Theorie prädikativ oder finitistisch ist usw. Nebenprodukt der beweistheoretischen Analyse erhalten wir manchmal einfache Unabhängigkeitsbeweise. Tatsächlich können wir zeigen, dass eine Theorie ein bestimmtes Prinzip nicht beweisen kann, weil das Hinzufügen zur Theorie die beweistheoretische Stärke der Theorie erhöhen würde. Beispielsweise,CZF beweist das Powerset-Axiom nicht, da die Hinzufügung von Powerset zu CZF zu einer viel stärkeren Theorie führt. Proof-theoretische Interpretationen wurden auch verwendet, um konstruktive und intuitionistische ZF-Mengen-Theorien untereinander sowie mit ihren klassischen Gegenstücken und auch mit anderen grundlegenden Systemen für die konstruktive Mathematik wie der konstruktiven Typentheorie und der expliziten Mathematik zu vergleichen (siehe z. Griffor und Rathjen 1994, Tupailo 2003). Zur Definition des Begriffs der beweistheoretischen Stärke und zu Erhebungen zur Beweistheorie siehe beispielsweise (Rathjen 1999, 2006b).sowie mit ihren klassischen Gegenstücken und auch mit anderen grundlegenden Systemen für die konstruktive Mathematik, wie der konstruktiven Typentheorie und der expliziten Mathematik (siehe z. B. Griffor und Rathjen 1994, Tupailo 2003). Zur Definition des Begriffs der beweistheoretischen Stärke und zu Erhebungen zur Beweistheorie siehe beispielsweise (Rathjen 1999, 2006b).sowie mit ihren klassischen Gegenstücken und auch mit anderen grundlegenden Systemen für die konstruktive Mathematik, wie der konstruktiven Typentheorie und der expliziten Mathematik (siehe z. B. Griffor und Rathjen 1994, Tupailo 2003). Zur Definition des Begriffs der beweistheoretischen Stärke und zu Erhebungen zur Beweistheorie siehe beispielsweise (Rathjen 1999, 2006b).

Obwohl CZF und IZF die am häufigsten untersuchten Systeme sind, wurden in der Literatur bisher zahlreiche andere Systeme für die konstruktive und intuitionistische Mengenlehre berücksichtigt. Die beweistheoretische Stärke einer Reihe konstruktiver und intuitionistischer Mengen-Theorien wurde durch eine Vielzahl von Werkzeugen festgestellt, wie zum Beispiel eine Erweiterung der Mengen-Theorie der Doppel-Negations-Interpretation (entstanden in (Friedman 1973a)) und eine Vielzahl anderer beweistheoretischer Interpretationen, die häufig aus einer sorgfältigen Kombination von semantischen und beweistheoretischen Techniken resultieren. In vielen Fällen wurde die beweistheoretische Stärke eines Systems durch eine Interpretationskette zwischen konstruktiven und klassischen Systemen und durch die Verwendung einer Vielzahl von Werkzeugen bestimmt, von der Zuverlässigkeit bis zu "traditionelleren" beweistheoretischen Techniken als Ordnungsanalyse (siehe,zum Beispiel Beeson 1985; Griffor und Rathjen 1994; Rathjen 2012b). Insbesondere die Realisierbarkeit hat sich aufgrund ihrer Flexibilität als sehr nützlich erwiesen. In Bezug auf die Ergebnisse dieser Untersuchungen erweisen sich einige der analysierten Systeme als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Grenze der Prädikativität angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Beeson 1985; Griffor und Rathjen 1994; Rathjen 2012b). Insbesondere die Realisierbarkeit hat sich aufgrund ihrer Flexibilität als sehr nützlich erwiesen. In Bezug auf die Ergebnisse dieser Untersuchungen erweisen sich einige der analysierten Systeme als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Grenze der Prädikativität angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Beeson 1985; Griffor und Rathjen 1994; Rathjen 2012b). Insbesondere die Realisierbarkeit hat sich aufgrund ihrer Flexibilität als sehr nützlich erwiesen. In Bezug auf die Ergebnisse dieser Untersuchungen erweisen sich einige der analysierten Systeme als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Grenze der Prädikativität angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Rathjen 2012b). Insbesondere die Realisierbarkeit hat sich aufgrund ihrer Flexibilität als sehr nützlich erwiesen. In Bezug auf die Ergebnisse dieser Untersuchungen erweisen sich einige der analysierten Systeme als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Grenze der Prädikativität angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Rathjen 2012b). Insbesondere die Realisierbarkeit hat sich aufgrund ihrer Flexibilität als sehr nützlich erwiesen. In Bezug auf die Ergebnisse dieser Untersuchungen erweisen sich einige der analysierten Systeme als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Grenze der Prädikativität angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Die Realisierbarkeit hat sich aufgrund ihrer Flexibilität als sehr nützlich erwiesen. In Bezug auf die Ergebnisse dieser Untersuchungen erweisen sich einige der analysierten Systeme als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Grenze der Prädikativität angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Die Realisierbarkeit hat sich aufgrund ihrer Flexibilität als sehr nützlich erwiesen. In Bezug auf die Ergebnisse dieser Untersuchungen erweisen sich einige der analysierten Systeme als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Grenze der Prädikativität angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Einige der analysierten Systeme erweisen sich als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Prädikativitätsgrenze angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Einige der analysierten Systeme erweisen sich als ebenso schwach wie die Arithmetik, wie beispielsweise Friedmans System B (Friedman 1977); andere Systeme sind so stark wie das klassische ZF wie das IZF (Friedman 1973a). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Prädikativitätsgrenze angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Prädikativitätsgrenze angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0). Es gibt auch Systeme mittlerer Stärke wie CZF. Die Stärke der letzteren Theorie entspricht tatsächlich der einer Theorie einer induktiven Definition, die als ID (_ 1) bekannt ist. Die Tatsache, dass CZF die gleiche Stärke wie ID (_ 1) hat, wird verwendet, um die (verallgemeinerte) Prädikativität der Mengenlehre zu bestätigen und um zu beweisen, dass sie die Grenze der Prädikativität angesichts der natürlichen Zahlen überschreitet, da ID (_ 1)) 's beweistheoretische Ordnungszahl liegt weit über (Gamma_0).

Als letzte Bemerkung: Während die Stärke von CZF deutlich unter der der Arithmetik zweiter Ordnung liegt, ergibt die einfache Addition der ausgeschlossenen Mitte zu CZF (volles) ZF. Dies sollte im Gegensatz zu IZF stehen, das bereits die Stärke von ZF hat (Friedman 1973a). Die begrenzte beweistheoretische Stärke von CZF im Vergleich zu IZF wurde oft als einer der Hauptvorteile der konstruktiven gegenüber der intuitionistischen Mengenlehre angesehen. In gewissem Sinne scheint das CZF die intuitionistische Logik optimal zu nutzen, da es einen Begriff der (verallgemeinerten) prädikativen Menge charakterisiert, der für die Entwicklung eines Großteils der konstruktiven Mathematik ausreichend stark, aber auch schwach genug ist, um Impredikativität zu vermeiden. Interessanterweise hat sich ein ähnliches Muster herausgebildet, als der konstruktiven Mengenlehre einige Axiome großer Mengen hinzugefügt wurden.da die Stärke der resultierenden Theorie weit unter der der entsprechenden klassischen Theorie liegt.

5.2 Große Mengen in konstruktivem und intuitionistischem ZF

Ein prominentes Forschungsgebiet in der klassischen Mengenlehre ist das der großen Kardinäle (siehe Eintrag zur Mengenlehre). In konstruktiven Kontexten sind die Ordnungszahlen nicht linear geordnet. (Für den Begriff der konstruktiven Ordnungszahl und eine kurze Erörterung ihrer Eigenschaften siehe das ergänzende Dokument über: Mengen-theoretische Prinzipien, die mit der intuitionistischen Logik nicht kompatibel sind.) Infolgedessen spielen Kardinalzahlen nicht die gleiche Rolle wie in der klassischen Umgebung.

Man kann dennoch die Auswirkungen von „Reflexionsprinzipien“in Form von Axiomen mit großen Mengen untersuchen. Zum Beispiel kann man konstruktiven und intuitionistischen Mengen-Theorien ein Axiom hinzufügen, das die Existenz unzugänglicher Mengen behauptet. [2] Die Hinzufügung von Axiomen großer Mengen zu intuitionistischem ZF wurde zuerst von Friedman und Scedrov vorgeschlagen (Friedman und Scedrov 1984). Eines ihrer Ziele war es, die entsprechenden klassischen Begriffe zu beleuchten; Eine andere bestand darin, die Auswirkungen dieser Prinzipien auf die metatheoretischen Eigenschaften der ursprünglichen Mengenlehre zu untersuchen. Friedman und Scedrov haben zum Beispiel gezeigt, dass das Hinzufügen von Axiomen mit großen Mengen die Gültigkeit der Disjunktions- und numerischen Existenz-Eigenschaften für IZF nicht beeinträchtigt.

Im Kontext der konstruktiven Mengenlehre wurden von Aczel große Mengen in Form von sogenannten regulären Mengen eingeführt, um induktive Definitionen von Mengen zu ermöglichen (Aczel 1986). Rathjen und Crosilla haben unzugängliche Sets (Rathjen al. 1998; Crosilla und Rathjen 2001) und Mahlo-Sets (Rathjen 2003a) in Betracht gezogen. Dennoch könnte ein Einwand gegen Erweiterungen der konstruktiven Mengenlehre durch Axiome großer Mengen erhoben werden. In der klassischen Mengenlehre können große Kardinäle als Inkarnation höherer Unendlichkeit angesehen werden. Wie rechtfertigen wir diese Prinzipien konstruktiv? Die konstruktive Rechtfertigung dieser Begriffe beruht wiederum auf der typentheoretischen Interpretation. Die Hinzufügung dieser Prinzipien entspricht tatsächlich der von Universen und (W) - Typen innerhalb der konstruktiven Typentheorie. Die Rechtfertigung von Erweiterungen durch große Mengen ist daher mit der Frage nach den Grenzen der Martin-Löf-Typentheorie verbunden (Rathjen 2005). Wir stellen auch fest, dass die Hinzufügung unzugänglicher Mengenaxiome zu einem schwachen Teilsystem von CZF (ohne Mengeninduktion) eine Theorie der Stärke (Gamma_0) ergibt, die Ordnungszahl, die von Feferman und Schütte als Grenze der Prädikativität angesichts des Natürlichen herausgegriffen wurde Zahlen (Crosilla und Rathjen 2001; siehe auch Abschnitt 1.3). Dies ist ein Beweis dafür, dass wir durch die Arbeit in einem konstruktiven, prädikativen Kontext traditionell starke satztheoretische Begriffe zähmen können.die Ordnungszahl, die Feferman und Schütte als Grenze der Prädikativität angesichts der natürlichen Zahlen herausgestellt haben (Crosilla und Rathjen 2001; siehe auch Abschnitt 1.3). Dies ist ein Beweis dafür, dass wir durch die Arbeit in einem konstruktiven, prädikativen Kontext traditionell starke satztheoretische Begriffe zähmen können.die Ordnungszahl, die Feferman und Schütte als Grenze der Prädikativität angesichts der natürlichen Zahlen herausgestellt haben (Crosilla und Rathjen 2001; siehe auch Abschnitt 1.3). Dies ist ein Beweis dafür, dass wir durch die Arbeit in einem konstruktiven, prädikativen Kontext traditionell starke satztheoretische Begriffe zähmen können.

Die Mengenlehre von Crosilla und Rathjen mit unzugänglichen Mengen (aber ohne Mengeninduktion) ist theoretisch eher schwach, aber mathematisch recht aussagekräftig. Beispielsweise wurde damit überprüft, dass die Hinzufügung von Voevodskys Univalenzaxiom zur Martin-Löf-Typentheorie keine Impredikativität hervorruft (Rathjen 2017). Das Axiom der Univalenz wurde von Voevodsky im Rahmen seines Programms Univalent Foundations eingeführt (Voevodsky 2015). (Für einwertige Grundlagen siehe die Einträge zur Typentheorie und zur intuitionistischen Typentheorie). Voevodsky gab mit dem Univalence Axiom ein Modell der konstruktiven Typentheorie an, das auf Kan-Simplizialsätzen basiert (siehe Kapulkin & Lumsdaine 2012, Other Internet Resources). Das im obigen Artikel entwickelte einfache Modell der konstruktiven Typentheorie mit Univalenz wird im Rahmen einer Erweiterung von ZFC mit unzugänglichen Kardinälen durchgeführt. Dies warf die Frage auf, ob man ein konstruktiveres Modell dieser Typentheorie geben könnte und insbesondere, ob die Typentheorie prädikativ ist. Bezem, Coquand und Huber (2014) haben kürzlich ein Modell dieser Typentheorie in kubischen Mengen vorgeschlagen, das rechnerisch ist und „in einer konstruktiven Metallogik ausgedrückt werden kann“. Rathjen (2017) hat bestätigt, dass dieses neue Modell in einer geeigneten Erweiterung von CZF durch unzugängliche Mengen kodifiziert werden kann, was viel schwächer ist als die klassische Mengenlehre mit unzugänglichen Kardinälen. Tatsächlich stellt sich heraus, dass, wenn wir eine relativ schwache Typentheorie, dh eine ohne W-Typen, als Ausgangspunkt nehmen und sie um das Univalenzaxiom erweitern,Die resultierende Theorie hat eine beweistheoretische Stärke (Gamma_0), die Ordnungszahl, die normalerweise verwendet wird, um die Grenze der Prädikativität angesichts der natürlichen Zahlen darzustellen (Rathjen 2017). Um dies zu zeigen, beweist man, dass das kubische Modell von Bezem, Coquand und Huber in einer Erweiterung des in Crosilla und Rathjen (2001) eingeführten Systems durch (begrenzte) relativierte abhängige Wahl ausgeführt werden kann. Aus (Crosilla und Rathjen 2001) und (Rathjen 2003) folgt, dass letztere eine beweistheoretische Ordnungszahl (Gamma_0) haben. Coquand und Huber können in einer Erweiterung des in Crosilla und Rathjen (2001) eingeführten Systems durch (begrenzte) relativierte abhängige Wahl ausgeführt werden. Aus (Crosilla und Rathjen 2001) und (Rathjen 2003) folgt, dass letztere eine beweistheoretische Ordnungszahl (Gamma_0) haben. Coquand und Huber können in einer Erweiterung des in Crosilla und Rathjen (2001) eingeführten Systems durch (begrenzte) relativierte abhängige Wahl ausgeführt werden. Aus (Crosilla und Rathjen 2001) und (Rathjen 2003) folgt, dass letztere eine beweistheoretische Ordnungszahl (Gamma_0) haben.

5.3 Metamathematische Eigenschaften konstruktiver und intuitionistischer ZF- und semantischer Techniken

Eine Vielzahl von Interpretationen für die intuitionistische Logik wurde auf intuitionistische und konstruktive Mengen-Theorien wie Realisierbarkeit, Kripke-Modelle und Heyting-bewertete Semantik erweitert. Alle diese Techniken wurden angewendet, um metamathematische Ergebnisse über die Mengen-Theorien zu erhalten.

5.3.1 Disjunktions- und Existenzmerkmale konstruktiver und intuitionistischer ZF

Einige intuitionistische Mengen-Theorien erfüllen bestimmte metamathematische Eigenschaften, wie die Disjunktion und die Existenz-Eigenschaften. Es kann auch gezeigt werden, dass sie mit der Hinzufügung von Prinzipien übereinstimmen, die über das hinausgehen, was wir normalerweise als konstruktiv betrachten. Dazu gehören zum Beispiel Church Thesis und Markovs Prinzip. Für eine Beschreibung dieser Prinzipien im Kontext der intuitionistischen Logik kann der Leser die Abschnitte 4.2 und 5.2 des Eintrags über intuitionistische Logik oder Troelstra und van Dalens Buch Konstruktivismus in der Mathematik (Troelstra und van Dalen 1988) konsultieren.

Hier erinnern wir uns an die Disjunktions- und Existenzmerkmale, die für eine Mengenlehre (T) formuliert wurden. Die informelle Motivation für die Disjunktion und die Existenzmerkmale basiert auf unserem Verständnis der konstruktiven Beweise für disjunktive bzw. existenzielle Aussagen. In der Tat scheint es vernünftig zu erwarten, dass wir, wenn wir konstruktiv eine Disjunktion (phi / vee / psi) beweisen, auch in der Lage sein sollten, (phi) oder (psi) zu beweisen. Wenn wir eine existenzielle Aussage beweisen, sollten wir in der Lage sein zu beweisen, dass ein Zeuge dieser Aussage innerhalb unserer Theorie definierbar ist.

Obwohl solche Eigenschaften ziemlich natürlich erscheinen und für arithmetische Theorien ziemlich einfach zu etablieren sind, stellen sie sich im Fall von Mengen-Theorien aufgrund ihrer transfiniten Hierarchien von Mengen und des Extensionalitätsaxioms als erhebliche technische Herausforderungen heraus. Tatsächlich stellen sich heraus, dass prominente konstruktive und intuitionistische Mengen-Theorien nicht die Existenz-Eigenschaft besitzen, wie im nächsten Abschnitt erörtert.

Sei (T) eine Theorie, deren Sprache (L (T)) die Sprache der Mengenlehre umfasst. Darüber hinaus nehmen wir der Einfachheit halber an, dass (L (T)) eine Konstante (omega) hat, die die Menge der natürlichen Zahlen von Neumann bezeichnet, und für jede (n) eine Konstante (c_n), die bezeichnet das (n) - te Element von (omega).

Eine Theorie (T) hat die Disjunktionseigenschaft (DP), wenn (T) für Sätze (phi) und (psi) von ((phi / vee / psi)) beweist (L (T)), dann beweist (T) (phi) oder (T) beweist (psi).

Die Existenz-Eigenschaft hat im Kontext der Mengenlehre zwei unterschiedliche Versionen: die numerische Existenz-Eigenschaft (NEP) und die Existenz-Eigenschaft (EP). Sei (theta (x)) eine Formel mit höchstens (x) frei. Wir sagen das:

(1) (T) hat die NEP, wenn immer dann, wenn (T) beweist, dass (x / in / omega / theta (x) existiert), für eine natürliche Zahl (n, T) beweist (theta (c_n)).

(2) (T) hat die EP, wenn (T) beweist, dass (existiert x / theta) (x), dann gibt es eine Formel (phi (x)) mit genau (x) frei, so dass (T) beweist (existiert! x (phi (x) wedge / theta (x))).

Da sich Realisierbarkeitstechniken bei Untersuchungen der Existenz- und Disjunktionseigenschaften für konstruktive und intuitionistische Mengen-Theorien als entscheidend erwiesen haben, diskutieren wir die Ergebnisse dieser Studien im nächsten Abschnitt.

5.3.2 Realisierbarkeit

Die Realisierbarkeit war eines der ersten und wichtigsten Werkzeuge in der Forschung zu Set-Theorien, die auf intuitionistischer Logik basieren, ausgehend von den frühen Beiträgen von Friedman und Myhill (Friedman 1973, Myhill 1973). Die Realisierbarkeitssemantik für die intuitionistische Arithmetik wurde zuerst von Kleene (Kleene 1945) vorgeschlagen und von Kreisel und Troelstra (Kreisel und Troelstra 1970) auf die Heyting-Arithmetik höherer Ordnung erweitert. Zur Definition der Realisierbarkeit für die Arithmetik siehe Abschnitt 5.2 des Eintrags zur intuitionistischen Logik. Eine Realisierbarkeit ähnlich Kreisel und Troelstra wurde von Friedman (Friedman 1973) auf Systeme höherer Ordnung angewendet. Myhill führte eine Variante dieser Realisierbarkeit ein, die Kleenes Schrägstrich ähnelt (Myhill 1973; Kleene 1962, 1963). Er bewies somit, dass eine Version von IZF mit Ersatz anstelle der Sammlung (genannt IZF (_ {Rep})) die DP, die NEP und die EP hat. Diese Ergebnisse wurden in (Myhill 1975; Friedman und Scedrov 1983) weiter ausgebaut. Während Friedman und Myhill Realisierbarkeitsmodelle für Extensionsmengen-Theorien gaben, entwickelte Beeson einen Realisierbarkeitsbegriff für nicht-Extensionsmengen-Theorien. Anschließend untersuchte er die metatheoretischen Eigenschaften der Extensionsmengen-Theorien über eine Interpretation in ihren nicht-Extensions-Gegenstücken. Er bewies damit, dass das IZF (mit Sammlung) die DP und NEP hat (Beeson 1985). Anschließend führte McCarty die Realisierbarkeit für IZF direkt für die Extensional-Set-Theorie ein (McCarty 1984; 1986). Die Realisierbarkeitssemantik für Varianten von CZF wurde beispielsweise in (Crosilla und Rathjen 2001; Rathjen 2006a) berücksichtigt. Die Realisierbarkeit in letzterem Artikel ist von McCarty's inspiriert und hat das wichtige Merkmal, dass es sich bei McCarty's für IZF um eine selbstvalidierende Semantik für CZF handelt (dh dieser Begriff der Realisierbarkeit kann in CZF formalisiert werden und jeder Satz von CZF ist nachweislich in CZF realisiert). Rathjen hat diesen Begriff der Realisierbarkeit genutzt, um zu zeigen, dass CZF (und eine Reihe von Erweiterungen davon) die DP und die NEP haben (Rathjen 2005b).

Eine andere Art der Realisierbarkeit, die sich als sehr nützlich erwiesen hat, ist die Lifschitz-Realisierbarkeit. Lifschitz (1979) führte eine Modifikation von Kleenes Realisierbarkeit für die Heyting-Arithmetik ein, die die Besonderheit aufweist, eine schwache Form von Church's Thesis (CT) mit einer Eindeutigkeitsbedingung zu validieren, nicht jedoch CT selbst. Die Realisierbarkeit von Lifschitz wurde von van Oosten (1990) auf die Arithmetik zweiter Ordnung erweitert. Anschließend wurde es von Cheng und Rathjen auf das vollständige IZF ausgeweitet, die es einsetzten, um eine Reihe von Unabhängigkeitsergebnissen zu erzielen und das sogenannte Lesser Limited Principle of Omniscience (LLPO) zu validieren (für LLPO siehe den Eintrag zur konstruktiven Mathematik).

Die Frage, welche Mengen-Theorien die Existenz-Eigenschaft erfüllen, erwies sich als besonders schwer zu lösen. (Friedman und Scedrov 1985) verwendeten Kripke-Modelle, um zu zeigen, dass IZF (dh das System mit Sammlung) nicht über das EP verfügt, während, wie oben erwähnt, das System IZF (_ {Rep}) (das ersetzt wurde) vorhanden ist der Sammlung) hat die EP. Dies veranlasste Beeson, die Frage zu stellen [Beeson 1985, IX]:

Hat eine vernünftige Mengenlehre mit Sammlung die Existenz-Eigenschaft?

Eine erste Antwort auf Beesons Frage kam mit (Rathjen 2012), wo der Autor den Begriff des schwachen Existenzvermögens einführte: Der Fokus liegt hier darauf, für jeden existenziellen Satz eine nachweisbar definierbare Gruppe von Zeugen zu finden. Anschließend führte er eine Form der Realisierbarkeit ein, die auf allgemeinen rekursiven Mengenfunktionen basiert, wobei ein Realisierer für eine existenzielle Aussage eine Reihe von Zeugen für den existenziellen Quantifizierer anstelle eines einzelnen Zeugen bereitstellt. Rathjen kombinierte diesen Begriff der Realisierbarkeit mit der Wahrheit, um zu ergeben, dass eine Reihe von Theorien mit Sammlung die schwache Existenz-Eigenschaft genießen (während IZF dies nicht tut). Darunter insbesondere die Theorie CZF ohne Teilmengenerfassung plus Myhills Exponentiationsaxiom CZF (_ {Exp}). In der Tat behauptete Rathjen, dass er durch die Kombination dieser Ergebnisse mit weiteren Arbeiten, die er durchgeführt hatte,er konnte zeigen, dass CZF (_ {Exp}) (und eine Reihe anderer Theorien) die Existenz-Eigenschaft haben. Eine bemerkenswerte Beobachtung ist, dass diese Theorien mit Sammlung formuliert sind; Folglich kann das Versagen des Existenzvermögens im Fall von IZF nicht nur auf die Sammlung zurückgeführt werden, sondern auch auf das Zusammenspiel zwischen diesem Schema und der uneingeschränkten Trennung.

Die wichtige Frage, ob CZF selbst die Existenzgrundlage besitzt, wurde von Swan (2014) verneint. Dort verwendete der Autor drei gut ausgearbeitete Realisierbarkeitsmodelle und Einbettungen zwischen ihnen, um zu zeigen, dass selbst die Eigenschaft der schwachen Existenz für CZF versagt. Dabei zeigte er auch, dass das CZF-Teilmengen-Sammlungsschema der Schuldige ist. Wie in (Swan 2014) deutlich hervorgehoben, weist die Tatsache, dass CZF kein EP hat, nicht auf eine gewisse Schwäche von CZF als konstruktive Theorie hin. Auch wenn Swan im Wesentlichen bewiesen hat, dass CZF die Existenz mathematischer Objekte behauptet, die nicht konstruiert werden können, hat CZF dennoch natürliche Interpretationen, in denen diese Objekte konstruiert werden können, wie zum Beispiel Aczels Interpretation in die Typentheorie (Aczel 1978)..

Für eine Übersicht über die Ergebnisse der intuitionistischen Mengenlehre siehe (Beeson 1985, Kapitel IX). Zu den entsprechenden Entwicklungen in CZF siehe (Rathjen 2005b, 2006, 2012) und (Swan 2014).

5.3.3 Kripke-Modelle und Heyting-bewertete Semantik

Kripke-Modelle für intuitionistische Mengen-Theorien wurden in (Friedman und Scedrov 1985) verwendet, um zu zeigen, dass IZF nicht über die EP verfügt (und wenn wir dies mit den Ergebnissen in (Myhill 1973) kombinieren, haben wir, dass IZF (_ {Rep}) dies tut nicht beweisen IZF). In jüngerer Zeit wurden Kripke-Modelle angewendet, um die Beziehung zwischen den konstruktiven Substituten des Potenzmengenaxioms zu verdeutlichen: Myhills Exponentiationsaxiom und Aczels Teilmengen-Erfassungsschema. Es ist klar, dass das Axiom der Potenzmenge beide Prinzipien impliziert und dass die Sammlung von Teilmengen eine Potenzierung impliziert. Andererseits impliziert jedes der beiden letztgenannten Prinzipien keine Potenzmenge, da die Theorie CZF mit Potenzmenge anstelle der Teilmengenerfassung viel stärker ist als CZF und CZF (_ {Exp}) (Rathjen 2012b). Tatsächlich haben CZF und CZF (_ {Exp}) die gleiche beweistheoretische Stärke (Griffor und Rathjen 1994);Um die Beziehung zwischen Teilmengenerfassung und Exponentiation in der konstruktiven Mengenlehre zu untersuchen, musste man daher andere Werkzeuge entwickeln, als theoretische Methoden zu beweisen. Lubarsky (2005) verwendete Kripke-Modelle, um zu zeigen, dass Myhills Exponentiationsaxiom nicht Aczels Teilmengen-Sammlung impliziert (auf der Grundlage von CZF minus Teilmengen-Sammlung plus vollständiger Teilung). In (Lubarsky und Rathjen 2007) verwendeten die Autoren die Technik der Kripke-Modelle, um zu zeigen, dass auch die Konsequenzen der Theorien CZF und CZF (_ {Exp}) unterschiedlich sind. Aczel und Rathjen (2001) hatten gezeigt, dass die Klasse der Dedekind-reellen Zahlen unter Verwendung der Teilmengen-Sammlung eine Menge in CZF bildet. Lubarsky und Rathjen (2007) haben gezeigt, dass CZF (_ {Exp}) nicht ausreicht, um dieselbe Aussage zu beweisen. Für weitere Anwendungen von Kripke-Modellen zur Trennung entscheidender konstruktiver Begriffe siehe z(Diener und Lubarsky 2013).

Die Heyting-wertige Semantik für intuitionistische Mengen-Theorien wurde von Grayson (Grayson 1979) als Gegenstück zu Booleschen Modellen für die klassische Mengen-Theorie erhalten. Sie wurden insbesondere über kategoriale Semantik verallgemeinert (für eine Einführung siehe MacLane und Moerdijk 1992). Heyting-wertige Semantik hat Anwendung auf Unabhängigkeitsergebnisse gefunden (Scedrov 1981; 1982). Eine konstruktive Behandlung wurde in (Gambino 2006) gegeben. Siehe auch (Lubarsky 2009). Siehe auch Ziegler (2012) für eine Verallgemeinerung der Realisierbarkeit und Heyting-Modelle für die konstruktive Mengenlehre.

5.3.4 Kategoriale Modelle der konstruktiven und intuitionistischen Mengenlehre

Kategoriale Modelle konstruktiver und intuitionistischer Mengenlehre haben im Laufe der Jahre floriert. Die Begriffe Topos und Garbe spielen hier eine wesentliche Rolle (siehe z. B. Fourman 1980 und Fourman und Scott 1980). Eine Übersicht über die wichtigsten Konzepte finden Sie im Eintrag zur Kategorietheorie und in den dort bereitgestellten Referenzen (siehe insbesondere den Anhang Programmatic Reading Guide). Für neuere Entwicklungen, die sich spezifischer auf konstruktive Mengen-Theorien beziehen, siehe z. B. (Simpson 2005) und (Awodey 2008) sowie die Webseite: Algebraische Mengen-Theorie.

5.4 Varianten konstruktiver und intuitionistischer Mengen-Theorien: Mengen-Theorien mit Urelementen und nicht-extensiven Mengen-Theorien

Manchmal wurden Systeme der intuitionistischen und konstruktiven Mengenlehre mit den natürlichen Zahlen als separate Art von Urelementen dargestellt, dh primitiven Objekten ohne Elemente (Friedman 1977; Myhill 1975; Beeson 1985). Konstruktiv ist dies eine natürliche Entscheidung, die mit Ideen übereinstimmt, die beispielsweise von Bishop (1967) (unter anderem) geäußert wurden. In Bishops Monographie werden die natürlichen Zahlen als grundlegendes Konzept angesehen, auf dem alle anderen mathematischen Konzepte basieren. Aus technischer Sicht nimmt das Axiom der Unendlichkeit die Form an, wenn die natürlichen Zahlen als primitiv genommen werden und sich von ihren satztheoretischen Darstellungen unterscheiden: „Es gibt eine Menge natürlicher Zahlen (als Urelemente)“. Eine allgemeinere Form von Urelementen in konstruktiven Mengen-Theorien wurde in (Cantini und Crosilla 2008) betrachtet. Hier wird eine Variante der konstruktiven Mengenlehre vorgeschlagen, die einen intensiven und partiellen Funktionsbegriff mit dem CZF-Erweiterungsbegriff der Menge kombiniert (siehe auch Cantini und Crosilla 2010).

Das Axiom der Extensionalität ist ein gemeinsames Merkmal aller bisher diskutierten Systeme. In einem Kontext, in dem der rechnerische Inhalt einer Aussage als entscheidend angesehen wird, könnte eine Intensionstheorie jedoch geeigneter sein. Zum Beispiel verkapseln sowohl die konstruktive Typentheorie als auch die explizite Mathematik irgendeine Form von Intensionalität. Intuitionistische Mengenlehre ohne Extensionalität wurde in der Literatur berücksichtigt (Friedman 1973a, Beeson 1985). Ihre Motivation war jedoch nicht rechnerischer, sondern technischer Natur, da die Extensionalität beim Studium der metamathematischen Eigenschaften intuitionistischer Mengen-Theorien Schwierigkeiten bereitet.

Literaturverzeichnis

  • Aczel, P., 1978, "The Type Theoretic Interpretation of Constructive Set Theory", im Logic Colloquium '77, A. MacIntyre, L. Pacholski, J. Paris (Hrsg.), Amsterdam und New York: North-Holland, pp 55–66.
  • –––, 1982, „Die typentheoretische Interpretation der konstruktiven Mengenlehre: Wahlprinzipien“, im LEJ Brouwer Centenary Symposium, AS Troelstra und D. van Dalen (Hrsg.), Amsterdam und New York: Nordholland, pp. 1–40.
  • –––, 1986, „Die typentheoretische Interpretation der konstruktiven Mengenlehre: induktive Definitionen“, in Logik, Methodik und Wissenschaftstheorie VII, RB Marcus, GJ Dorn und GJW Dorn (Hrsg.), Amsterdam und New York: Nordholland, S. 17–49.
  • –––, 1988, Nicht fundierte Sets (CSLI Lecture Notes 14), Stanford: CSLI.
  • Aczel, P. und Rathjen, M., 2001, "Notes on Constructive Set Theory", Bericht Nr. 40, 2000/2001, Djursholm: Institut Mittag-Leffler, [online verfügbar]
  • Aczel, P. und Gambino, N., 2002, "Sammlungsprinzipien in der Theorie abhängiger Typen", in Typen für Beweise und Programme (Lecture Notes in Computer Science 2277), P. Callaghan, Z. Luo, J. McKinna und R. Pollack (Hrsg.), Berlin: Springer, S. 1–23.
  • Awodey, S., 2008, „Eine kurze Einführung in die algebraische Mengenlehre“, The Bulletin of Symbolic, 14 (3): 281–298.
  • Barwise, J. und Moss, L., 1996, Vicious Circles (CSLI Lecture Notes 60), Stanford: CSLI.
  • Beeson, M., 1985, Grundlagen der Konstruktiven Mathematik, Berlin: Springer.
  • Bezem, M., Thierry, C. und Huber, S., 2014, „Ein Modell der Typentheorie in kubischen Mengen“, in der 19. Internationalen Konferenz über Typen für Beweise und Programme (TYPEN 2013), Matthes, R. und Schubert, A. (Hrsg.), Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, S. 107–128.
  • Bishop, E., 1967, Grundlagen der konstruktiven Analyse, New York: McGraw-Hill.
  • –––, 1970, „Mathematik als numerische Sprache“, in Intuitionismus und Beweistheorie, A. Kino, J. Myhill und RE Vesley (Hrsg.), Amsterdam: Nordholland, S. 53–71.
  • Bishop, E. und Bridges, D., 1985, Konstruktive Analyse, Berlin und Heidelberg: Springer.
  • Bridges, D. und Richman, F., 1987, Varieties of Constructive Mathematics, Cambridge: Cambridge University Press.
  • Buchholz, W., Feferman, S., Pohlers, W. und Sieg, W., 1981, Iterierte induktive Definitionen und Subsysteme der Analyse, Berlin: Springer.
  • Cantini, A. und Crosilla, L., 2008, "Konstruktive Mengenlehre mit Operationen", in A. Andretta, K. Kearnes, D. Zambella (Hrsg.), Logic Colloquium 2004 (Lecture Notes in Logic 29), Cambridge: Cambridge University Press, S. 47–83.
  • Cantini, A. und Crosilla, L., 2010, „Explicit Operational Set Theory“, in R. Schindler (Hrsg.), Ways of Proof Theory, Frankfurt: Ontos, S. 199–240.
  • Chen, R.-M. und Rathjen, M., 2012, „Lifschitz-Realisierbarkeit für die intuitionistische Zermelo-Fraenkel-Mengenlehre“, Archive for Mathematical Logic, 51: 789–818.
  • Crosilla, L., 2017, „Predicativity and Feferman“, in G. Jäger und W. Sieg (Hrsg.), Feferman on Foundations (Hervorragende Beiträge zur Logik: Band 13), Cham: Springer, S. 423–447.
  • Crosilla, L. und Rathjen, M., 2001, „Unzugängliche Mengenaxiome haben möglicherweise eine geringe Konsistenzstärke“, Annals of Pure and Applied Logic, 115: 33–70.
  • Diaconescu, R., 1975, „Axiom of Choice and Complementation“, Proceedings of the American Mathematical Society, 51: 176–178.
  • Diener, H. und Lubarsky, R., 2013, „Trennung des Fan-Theorems und seiner Schwächungen“, in SN Artemov und A. Nerode (Hrsg.), Proceedings of LFCS '13 (Lecture Notes in Computer Science 7734), Dordrecht: Springer, S. 280–295.
  • Dummett, M., 2000, Elements of Intuitionism, zweite Ausgabe, (Oxford Logic Guides 39), New York: Oxford University Press.
  • Feferman, S., 1964, „Systems of Predicative Analysis“, Journal of Symbolic Logic, 29: 1–30.
  • –––, 1975, „Eine Sprache und Axiome für die explizite Mathematik“, in Algebra und Logik (Lecture Notes in Mathematics 450), J. Crossley (Hrsg.), Berlin: Springer, S. 87–139.
  • –––, 1988, „Weyl bestätigt: Das Kontinuum siebzig Jahre später“, in Temi e prospettive della logica und della scienza contemporanee, C. Cellucci und G. Sambin (Hrsg.), S. 59–93.
  • –––, 1993, „Worauf beruht was? Die beweistheoretische Analyse der Mathematik “in Philosophy of Mathematics, Teil I, Proceedings of the 15th International Wittgenstein Symposium. Wien: Verlag Hölder-Pichler-Tempsky.
  • –––, 2005, „Predicativity“, im Handbuch der Philosophie der Mathematik und Logik, S. Shapiro (Hrsg.), Oxford: Oxford University Press.
  • Fletcher, P., 2007, „Infinity“, im Handbuch der Philosophie der Logik, D. Jacquette, (Hrsg.), Amsterdam: Elsevier, S. 523–585.
  • Fourman, MP, 1980, „Garbenmodelle für die Mengenlehre“, Journal of Pure Applied Algebra, 19: 91–101.
  • Fourman, MP, und Scott, DS, 1980, „Garben und Logik“, in Anwendungen von Garben (Lecture Notes in Mathematics 753), MP Fourman, CJ Mulvey und DS Scott (Hrsg.), Berlin: Springer, S. 302– 401.
  • Friedman, H., 1973, "Einige Anwendungen von Kleenes Methoden für intuitionistische Systeme", in Proceedings der Cambridge Summer School in Mathematical Logic von 1971 (Lecture Notes in Mathematics 337), ARD Mathias und H. Rogers (Hrsg.), Berlin: Springer, S. 113–170.
  • –––, 1973a, „Die Konsistenz der klassischen Mengenlehre in Bezug auf eine Mengenlehre mit intuitionistischer Logik“, Journal of Symbolic Logic, 38: 315–319.
  • –––, 1977, „Mengen-theoretische Grundlagen für die konstruktive Analyse“, Annals of Mathematics, 105: 1–28.
  • Friedman, H., Scedrov, A., 1983, „Setze Existenz-Eigenschaft für intuitionistische Theorien mit abhängiger Wahl“, Annals of Pure and Applied Logic, 25: 129–140.
  • –––, 1984, „Große Mengen in der intuitionistischen Mengenlehre“, Annals of Pure and Applied Logic, 27: 1–24.
  • –––, 1985, „Das Fehlen definierbarer Zeugen und nachweislich rekursiver Funktionen in der intuitionistischen Mengenlehre“, Advances in Mathematics, 57: 1–13.
  • Gambino, N., 2006, „Heyting-wertvolle Interpretationen für die konstruktive Mengenlehre“, Annals of Pure and Applied Logic, 137: 164–188.
  • Goodman, ND, und Myhill, J., 1972, "Die Formalisierung der konstruktiven Mathematik des Bischofs", in Toposes, Algebraische Geometrie und Logik (Lecture Notes in Mathematics 274), FW Lawvere (Hrsg.), Berlin: Springer, S. 83 –96.
  • Goodman, ND, und Myhill, J., 1978, "Wahl impliziert ausgeschlossene Mitte", Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 24 (5): 461.
  • Grayson, RJ, 1979, "Heyting-wertige Modelle für die intuitionistische Mengenlehre", in Applications of Sheaves (Lecture Notes in Mathematics 753), MP Fourman, CJ Mulvey und DS Scott (Hrsg.), Berlin: Springer, S. 402 –414.
  • Griffor, E. und Rathjen, M., 1994, „Die Stärke einiger Theorien vom Typ Martin-Löf“, Archive Mathematical Logic, 33: 347–385.
  • van Heijenoort, J., 1967, Von Frege nach Gödel. Ein Quellenbuch in Mathematical Logic 1879–1931, Cambridge: Harvard Univ. Drücken Sie.
  • Kleene, SC, 1945, „Zur Interpretation der intuitionistischen Zahlentheorie“, Journal of Symbolic Logic, 10: 109–124.
  • –––, 1962, „Disjunktion und Existenz unter Implikation in elementaren intuitionistischen Formalismen“, Journal of Symbolic Logic, 27: 11–18.
  • –––, 1963, „Ein Nachtrag“, Journal of Symbolic Logic, 28: 154–156.
  • Kreisel, G., 1958, „Ordnungslogik und die Charakterisierung informeller Beweiskonzepte“, Tagungsband des Internationalen Mathematikerkongresses (14.-21. August 1958), Paris: Gauthier-Villars, S. 289–299.
  • Kreisel, G. und Troelstra, A., S., 1970, „Formale Systeme für einige Zweige der intuitionistischen Analyse“, Annals of Mathematical Logic, 1: 229–387.
  • Lifschitz, V., 1979, „CT (_ 0) ist stärker als CT (_ 0)!“, Proceedings of the American Mathematical Society, 73 (1): 101–106.
  • Lindström, I., 1989, „Eine Konstruktion nicht fundierter Mengen innerhalb der Martin-Löf-Typentheorie“, Journal of Symbolic Logic, 54: 57–64.
  • Lipton, J., 1995, "Realisierbarkeit, Mengenlehre und Termextraktion", in Der Curry-Howard-Isomorphismus (Cahiers du Centre de Logique de l'Universite Catholique de Louvain 8), Louvain-la-Neuve: Academia, S. 257 –364.
  • Lorenzen, P. und Myhill, J., 1959, „Konstruktive Definition bestimmter analytischer Zahlenmengen“, Journal of Symbolic Logic, 24: 37–49.
  • Lubarsky, R., 2005, „Unabhängigkeitsergebnisse rund um konstruktives ZF“, Annals of Pure and Applied Logic, 132: 209–225.
  • –––, 2006, „CZF und Arithmetik zweiter Ordnung“, Annals of Pure and Applied Logic, 141: 29–34.
  • –––, 2009, „Topological Forcing Semantics with Settling“, in SN Artemov und A. Nerode (Hrsg.), Proceedings of LFCS '09 (Lecture Notes in Computer Science 5407), Dordrecht: Springer, S. 309–322.
  • Lubarsky, R. und Rathjen, M., 2007, "On the Constructive Dedekind Reals", in SN Artemov und A. Nerode (Hrsg.), Proceedings of LFCS 2007 (Lecture Notes in Computer Science 4514), Dordrecht: Springer S. 349–362.
  • MacLane, S. und Moerdijk, I., 1992, "Sheaves in Geometry and Logic", New York: Springer.
  • Maietti, ME, Sambin, G., 2005, „Auf dem Weg zu einer minimalistischen Grundlage für konstruktive Mathematik“, in Von Mengen und Typen zu Topologie und Analyse: Auf dem Weg zu praktikablen Grundlagen für konstruktive Mathematik (Oxford Logic Guides 48), L. Crosilla und P. Schuster (Hrsg.), Oxford: Oxford University Press.
  • Maietti, ME, 2009, „Eine minimalistische zweistufige Grundlage für konstruktive Mathematik“, Annals of Pure and Applied Logic, 160 (3): 319–354.
  • Martin-Löf, P., 1975, „Eine intuitionistische Typentheorie: prädikativer Teil“, in HE Rose und J. Sheperdson (Hrsg.), Logic Colloquium '73, Amsterdam: Nordholland, S. 73–118.
  • –––, 1984, „Intuitionistic Type Theory“, Neapel: Bibliopolis.
  • McCarty, DC, 1984, "Realisability and Recursive Mathematics", D. Phil. Dissertation, Philosophie, Universität Oxford.
  • –––, 1986, „Realisierbarkeit und rekursive Mengenlehre“, Annals of Pure and Applied Logic, 32: 153–183.
  • Myhill, J., 1973, "Einige Eigenschaften der intuitionistischen Zermelo-Fraenkel-Mengenlehre", in Proceedings der Cambridge Summer School 1971 in Mathematical Logic (Lecture Notes in Mathematics 337), ARD Mathias und H. Rogers (Hrsg.), Berlin: Springer, S. 206–231.
  • –––, 1975, „Constructive Set Theory“, Journal of Symbolic Logic, 40: 347–382.
  • van Oosten, J., 1990, „Lifschitz 'Realisierbarkeit“, The Journal of Symbolic Logic, 55: 805–821.
  • Powell, W., 1975, „Ausweitung von Gödels negativer Interpretation auf ZF“, Journal of Symbolic Logic, 40: 221–229.
  • Rathjen, M., Griffor, E. und Palmgren, E., 1998, „Unzugänglichkeit in der konstruktiven Mengen- und Typentheorie“, Annals of Pure and Applied Logic, 94: 181–200.
  • Rathjen, M., 1999, „Das Reich der Ordnungsanalyse“, in Sets and Proofs (Lecture Notes 258 der London Mathematical Society), Cambridge: Cambridge University Press, S. 219–279.
  • –––, 2003, „Das Anti-Foundation-Axiom in konstruktiven Mengen-Theorien“, in Spiele, Logik und konstruktive Mengen (CSLI Lecture Notes 161), Stanford: CSLI Publication, S. 87–108.
  • –––, 2003a, „Realisierung der Mahlo-Mengenlehre in der Typentheorie“, Archive for Mathematical Logic, 42: 89–101.
  • –––, 2004, „Prädikativität, Zirkularität und Anti-Foundation“, in 100 Jahren Russells Paradoxon (Logik und ihre Anwendungen 6), G. Link (Hrsg.), Berlin: de Gruyter, S. 191–219.
  • –––, 2005, „Ersatz versus Sammlung und verwandte Themen in der konstruktiven Zermelo-Fraenkel-Mengenlehre“, Annals of Pure and Applied Logic, 136: 156–174.
  • –––, 2005a, „Das konstruktive Hilbert-Programm und die Grenzen der Martin-Löf-Typentheorie“, Synthese, 147: 81–120.
  • –––, 2005b, „Die Disjunktion und verwandte Eigenschaften für die konstruktive Zermelo-Fraenkel-Mengenlehre“, Journal of Symbolic Logic, 70 (4): 1232–1254.
  • –––, 2006, „Auswahlprinzipien in konstruktiven und klassischen Mengenlehre“, Logic Colloquium '02 (Lecture Notes in Logic 27), Z. Chatzidakis, P. Koepke und W. Pohlers (Hrsg.), Wellesley, Massachusetts: AK Peters, 299–326.
  • –––, 2006a, „Realisierbarkeit für konstruktive Zermelo-Fraenkel-Mengenlehre“, im Logic Colloquium '03 (Lecture Notes in Logic 24), V. Stoltenberg-Hansen und J. Väänänen (Hrsg.), Wellesley, Massachusets: AK Peters S. 282–314.
  • –––, 2006b, „Theorien und Ordnungszahlen in der Beweistheorie“, Synthese, 148 (3): 719–743.
  • –––, 2008, „Die natürlichen Zahlen in der konstruktiven Mengenlehre“, Mathematical Logic Quarterly, 54: 287–312.
  • –––, 2012, „Von der schwachen zur starken Existenz“, Annals of Pure and Applied Logic, 163: 1400–1418.
  • –––, 2012b, „Konstruktive Zermelo-Fraenkel-Mengenlehre, Potenzmenge und Konstruktionsrechnung“, in Erkenntnistheorie versus Ontologie: Aufsätze zur Philosophie und den Grundlagen der Mathematik zu Ehren von Per Martin-Löf, (Logik, Erkenntnistheorie und die Einheit der Wissenschaft), P. Dybjer, S. Lindström, E. Palmgren und G. Sundhölm (Hrsg.), New York und Dordrecht: Springer Verlag.
  • –––, 2017, „Beweistheorie konstruktiver Systeme: Induktive Typen und Univalenz“, in G. Jäger und W. Sieg (Hrsg.), Feferman on Foundations (Herausragende Beiträge zur Logik: Band 13), Cham: Springer, S. 385–419.
  • Richman, F., 2000, „Der Grundsatz der Algebra: eine konstruktive Entwicklung ohne Wahl“, Pacific Journal of Mathematics, 196: 213–230.
  • –––, 2001, „Konstruktive Mathematik ohne Wahl“, in Reuniting the Antipodes: Konstruktive und nicht standardisierte Ansichten des Kontinuums (Synthese Library 306), P. Schuster, et al. (Hrsg.), Dordrecth: Kluwer, S. 199–205.
  • Russell, B., 1908, „Mathematische Logik basierend auf der Theorie der Typen“, American Journal of Mathematics, 30: 222–262. Nachdruck in van Heijenoort (1967), 150–182.
  • Scedrov, A., 1981, „Konsistenz und Unabhängigkeit führen zu einer intuitionistischen Mengenlehre“in der Konstruktiven Mathematik (Lecture Notes in Mathematics 873), F. Richman (Hrsg.), Berlin: Springer, S. 54–86.
  • –––, 1982, „Unabhängigkeit des Fan-Theorems bei Vorhandensein von Kontinuitätsprinzipien“im LEJ Brouwer Centenary Symposium, AS Troelstra, und D. van Dalen (Hrsg.), Amsterdam: Nordholland, S. 435–442.
  • –––, 1985, „Intuitionistische Mengenlehre“in Harvey Friedmans Forschungen zu den Grundlagen der Mathematik, LA Garrubgtib et al. (Hrsg.), Amsterdam: Elsevier.
  • Schütte, K., 1965, „Predicative Well Orderings“, in Formal Systems and Recursive Functions, J. Crossley und M. Dummett (Hrsg.), Amsterdam: North-Holland, S. 279–302.
  • –––, 1965a, „Eine Grenze für die Beweisfähigkeit der Transfiniten-Induktion in der verzweigten Typenlogik“, Archiv für mathematische Logik und Grundlagenforschung, 7: 45–60.
  • Simpson, A., 2005, „Konstruktive Mengen-Theorien und ihre kategorietheoretischen Modelle“, in Von Mengen und Typen zu Topologie und Analyse: Auf dem Weg zu praktikablen Grundlagen für konstruktive Mathematik (Oxford Logic Guides 48), L. Crosilla und P. Schuster (Hrsg.), Oxford: Oxford University Press.
  • Swan, AW, 2014, „CZF hat nicht die Existenz-Eigenschaft“, Annals of Pure and Applied Logic, 165: 1115–1147.
  • Troelstra, AS, und van Dalen, D., 1988, Konstruktivismus in der Mathematik (zwei Bände), Amsterdam: Nordholland.
  • Tupailo, S., 2003, „Verwirklichung der konstruktiven Mengenlehre in der expliziten Mathematik: eine Untergrenze für das improvisierte Mahlo-Universum“, Annals of Pure and Applied Logic, 120: 165–196.
  • Voevodsky, V., 2015, „Eine experimentelle Bibliothek formalisierter Mathematik auf der Grundlage einwertiger Grundlagen“, Mathematical Structures in Computer Science, 25: 1278–1294.
  • Weyl, H., 1918, „Das Kontinuum. Kritische Untersuchungen über die Grundlagen der Analyse “, Veit, Leipzig.
  • Ziegler, Albert, 2012, „Verallgemeinerung von Realisierbarkeits- und Heyting-Modellen für die konstruktive Mengenlehre“, Annals of Pure and Applied Logic, 163 (2): 175–184.
  • –––, 2014, „Eine kumulative Hierarchie von Mengen für die konstruktive Mengenlehre“, Mathematical Logic Quarterly, 60 (1-2): 21–30.

Akademische Werkzeuge

Sep Mann Symbol
Sep Mann Symbol
 Wie man diesen Eintrag zitiert.
Sep Mann Symbol
Sep Mann Symbol
 Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
Inpho-Symbol
Inpho-Symbol
 Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
Phil Papers Ikone
Phil Papers Ikone
 Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

  • Aczel, P. und M. Rathjen, 2010, Anmerkungen zur konstruktiven Mengenlehre, Buchentwurf, online verfügbar.
  • Kapulkin, C. und PL Lumsdaine, 2012, „Das einfache Modell einwertiger Fundamente (nach Voevodsky)“, Preprint bei arXiv.org.
  • Algebraische Mengenlehre von S. Awodey (Carnegie Mellon).

[Bitte kontaktieren Sie den Autor mit weiteren Vorschlägen.]

Empfohlen:

Die Frühe Entwicklung Der Mengenlehre

Die Frühe Entwicklung Der Mengenlehre

Eintragsnavigation Eintragsinhalt Literaturverzeichnis Akademische Werkzeuge Freunde PDF Vorschau Autor und Zitierinfo Zurück nach oben Die frühe Entwicklung der Mengenlehre Erstveröffentlichung Di 10. April 2007; inhaltliche Überarbeitung Do 18.

Mengenlehre

Mengenlehre

Eintragsnavigation Eintragsinhalt Literaturverzeichnis Akademische Werkzeuge Freunde PDF Vorschau Autor und Zitierinfo Zurück nach oben Mengenlehre Erstveröffentlichung Mi 8. Oktober 2014; inhaltliche Überarbeitung Di 12.

Beliebte für den Tag

Watsuji Tetsurô

Watsuji Tetsurô

Willensschwäche

Willensschwäche

Hermann Weyl

Hermann Weyl

Alfred North Whitehead

Alfred North Whitehead

Wittgensteins Ästhetik

Wittgensteins Ästhetik

Bernard Williams

Bernard Williams