Bereichstheorie ist ein Zweig der Mathematik, die spezielle Arten teilweise bestellter Sätze (posets) allgemein genannte Gebiete studiert. Folglich kann Bereichstheorie als ein Zweig der Ordnungstheorie betrachtet werden. Das Feld hat Hauptanwendungen in der Informatik, wo es verwendet wird, um denotational Semantik besonders für funktionelle Programmiersprachen anzugeben. Bereichstheorie formalisiert die intuitiven Ideen von der Annäherung und Konvergenz auf eine sehr allgemeine Weise und hat nahe Beziehungen zur Topologie. Eine alternative wichtige Annäherung an die denotational Semantik in der Informatik ist die von metrischen Räumen.

Motivation und Intuition

Die primäre Motivation für die Studie von Gebieten, die von Dana Scott gegen Ende der 1960er Jahre begonnen wurde, war die Suche nach einer denotational Semantik der Lambda-Rechnung. In diesem Formalismus betrachtet man "Funktionen" als angegeben durch bestimmte Begriffe auf der Sprache. Auf eine rein syntaktische Weise kann man von einfachen Funktionen bis Funktionen gehen, die andere Funktionen als ihre Eingangsargumente nehmen. Mit wieder gerade die syntaktischen in diesem Formalismus verfügbaren Transformationen kann man so genannten festen Punkt combinators erhalten (von denen der am besten bekannte der Y combinator ist); diese haben definitionsgemäß das Eigentum dass f (Y (f)) = Y (f) für alle Funktionen f.

Um solch eine denotational Semantik zu formulieren, könnte man zuerst versuchen, ein Modell für die Lambda-Rechnung zu bauen, in der eine echte (ganze) Funktion mit jedem Lambda-Begriff vereinigt wird. Solch ein Modell würde eine Verbindung zwischen der Lambda-Rechnung als ein rein syntaktisches System und der Lambda-Rechnung als ein notational System formalisieren, um konkrete mathematische Funktionen zu manipulieren. Die Combinator Rechnung ist solch ein Modell. Jedoch sind die Elemente der Rechnung von Combinator Funktionen von Funktionen bis Funktionen; in der Größenordnung von den Elementen eines Modells der Lambda-Rechnung, um des willkürlichen Gebiets und der Reihe zu sein, konnten sie nicht wahre Funktionen, nur teilweise Funktionen sein.

Scott hat um diese Schwierigkeit herumgekommen, indem er einen Begriff "der teilweisen" oder "unvollständigen" Information formalisiert hat, um Berechnung zu vertreten, die ein Ergebnis noch nicht zurückgegeben hat. Das wurde durch das Betrachten, für jedes Gebiet der Berechnung (z.B die natürlichen Zahlen), ein zusätzliches Element modelliert, das eine unbestimmte Produktion, d. h. das "Ergebnis" einer Berechnung vertritt, die nie endet. Außerdem wird das Gebiet der Berechnung mit einer Einrichtungsbeziehung ausgestattet, in der das "unbestimmte Ergebnis" kleinstes Element ist.

Der wichtige Schritt, ein Modell für die Lambda-Rechnung zu finden, soll nur jene Funktionen denken (auf solch einem teilweise bestellten Satz), die, wie man versichert, Punkte am wenigsten befestigt haben. Der Satz dieser Funktionen, zusammen mit einer passenden Einrichtung, ist wieder ein "Gebiet" im Sinne der Theorie. Aber die Beschränkung zu einer Teilmenge aller verfügbaren Funktionen hat einen anderen großen Vorteil: Es ist möglich, Gebiete zu erhalten, die ihre eigenen Funktionsräume enthalten, d. h. man Funktionen bekommt, die auf sich angewandt werden können.

Neben diesen wünschenswerten Eigenschaften berücksichtigt Bereichstheorie auch eine ansprechende intuitive Interpretation. Wie oben erwähnt werden die Gebiete der Berechnung immer teilweise bestellt. Diese Einrichtung vertritt eine Hierarchie der Information oder Kenntnisse. Je höher ein Element innerhalb der Ordnung ist, desto spezifischer es ist und mehr Information, enthält es. Niedrigere Elemente vertreten unvollständige Kenntnisse oder Zwischenergebnisse.

Berechnung wird dann durch die Verwendung von Eintönigkeitsfunktionen wiederholt auf Elementen des Gebiets modelliert, um ein Ergebnis zu raffinieren. Das Erreichen eines festen Punkts ist zum Vollenden einer Berechnung gleichwertig. Gebiete stellen eine höhere Einstellung für diese Ideen zur Verfügung, da, wie man versichern kann, befestigte Punkte von Eintönigkeitsfunktionen bestehen und unter zusätzlichen Beschränkungen, von unten näher gekommen werden können.

Ein Handbuch zu den formellen Definitionen

In dieser Abteilung werden die Hauptkonzepte und Definitionen der Bereichstheorie eingeführt. Die obengenannte Intuition von Gebieten, die Informationseinrichtung sind, wird betont, um die mathematische Formalisierung der Theorie zu motivieren. Die genauen formellen Definitionen sollen in den hingebungsvollen Artikeln für jedes Konzept gefunden werden. Eine Liste von allgemeinen mit der Ordnung theoretischen Definitionen, die Gebiet theoretische Begriffe ebenso einschließen, kann im Ordnungstheorie-Wörterverzeichnis gefunden werden. Die wichtigsten Konzepte der Bereichstheorie werden dennoch unten eingeführt.

Geleitete Sätze als konvergierende Spezifizierungen

Wie erwähnt, vorher befasst sich Bereichstheorie mit teilweise bestellten Sätzen, um ein Gebiet der Berechnung zu modellieren. Die Absicht ist, die Elemente solch einer Ordnung wie Information oder (teilweise) Ergebnisse einer Berechnung zu interpretieren, wo Elemente, die in der Ordnung höher sind, die Information der Elemente unter ihnen auf eine konsequente Weise erweitern. Von dieser einfachen Intuition ist es bereits klar, dass Gebiete häufig kein größtes Element haben, da das bedeuten würde, dass es ein Element gibt, das die Information aller anderen Elemente - eine ziemlich langweilige Situation enthält.

Ein Konzept, das eine wichtige Rolle in der Theorie spielt, ist dasjenige einer geleiteten Teilmenge eines Gebiets, d. h. von einer nichtleeren Teilmenge der Ordnung, in der jeder zwei Elemente haben, haben einige ober gebunden, der ein Element dieser Teilmenge ist. Im Hinblick auf unsere Intuition über Gebiete bedeutet das, dass jede zwei Information innerhalb der geleiteten Teilmenge durch ein anderes Element in der Teilmenge durchweg erweitert wird. Folglich können wir geleitete Sätze als konsequente Spezifizierungen, d. h. als Sätze von teilweisen Ergebnissen ansehen, in denen keine zwei Elemente widersprechend sind. Diese Interpretation kann im Vergleich zum Begriff einer konvergenten Folge in der Analyse sein, wo jedes Element spezifischer ist als das vorhergehende. Tatsächlich, in der Theorie von metrischen Räumen, spielen Folgen eine Rolle, die in vielen Aspekten ist, die der Rolle von geleiteten Sätzen in der Bereichstheorie analog sind.

Jetzt, als im Fall von Folgen, interessieren wir uns für die Grenze eines geleiteten Satzes. Gemäß was oben gesagt wurde, würde das ein Element sein, das die allgemeinste Information ist, die die Information aller Elemente des geleiteten Satzes, d. h. des einzigartigen Elements erweitert, das genau die Information enthält, die im geleiteten Satz - und nichts mehr da gewesen ist. In der Formalisierung der Ordnungstheorie ist das gerade das des geleiteten Satzes gebundene am wenigsten obere. Als im Fall von Grenzen von Folgen bestehen kleinste obere Grenzen von geleiteten Sätzen nicht immer.

Natürlich hat man ein spezielles Interesse an jenen Gebieten der Berechnung, in der alle konsequenten Spezifizierungen, d. h. in Ordnungen zusammenlaufen, in denen alle geleiteten Sätze einen gebundenen am wenigsten oberen haben. Dieses Eigentum definiert die Klasse von geleiteten ganzen teilweisen Ordnungen oder dcpo für den kurzen. Tatsächlich denken die meisten Rücksichten der Bereichstheorie wirklich nur Ordnungen, die mindestens abgeschlossen geleitet werden.

Von der zu Grunde liegenden Idee von teilweise angegebenen Ergebnissen als das Darstellen unvollständiger Kenntnisse leitet man ein anderes wünschenswertes Eigentum ab: die Existenz von kleinstem Element. Solch ein Element-Modelle dass der Staat keiner Information - der Platz, wo der grösste Teil der Berechnung anfängt. Es kann auch als die Produktion einer Berechnung betrachtet werden, die kein Ergebnis überhaupt zurückgibt.

Berechnung und Gebiete

Jetzt wo wir einige grundlegende formelle Beschreibungen dessen haben, wie ein Gebiet der Berechnung sein sollte, können wir uns der Berechnung selbst zuwenden. Klar müssen diese Funktionen sein, Eingänge von einem rechenbetonten Gebiet nehmend und Produktionen in einigen (vielleicht verschieden) Gebiet zurückgebend. Jedoch würde man auch erwarten, dass die Produktion einer Funktion mehr Information enthalten wird, wenn der Informationsinhalt des Eingangs vergrößert wird. Formell bedeutet das, dass wir eine Funktion wollen, monotonisch zu sein.

Als, sich dcpos befassend, man auch wollen könnte, dass Berechnung mit der Bildung von Grenzen eines geleiteten Satzes vereinbar war. Formell bedeutet das, dass, für etwas Funktion f, das Image f (D) eines geleiteten Satzes D (d. h. des Satzes der Images jedes Elements von D) wieder geleitet wird und hat, weil ein am wenigsten oberer das Image des D gebundenen am wenigsten oberen gebunden hat. Man konnte auch sagen, dass F-Konserven suprema geleitet haben. Bemerken Sie auch, dass, durch das Betrachten von geleiteten Sätzen von zwei Elementen, solch eine Funktion auch monotonisch sein muss. Diese Eigenschaften verursachen den Begriff einer Scott-dauernden Funktion. Da das häufig nicht ist, kann zweideutiger auch von dauernden Funktionen sprechen.

Annäherung und Endlichkeit

Bereichstheorie ist eine rein qualitative Annäherung an das Modellieren der Struktur von Informationsstaaten. Man kann sagen, dass etwas mehr Information enthält, aber der Betrag der Zusatzinformation wird nicht angegeben. Und doch gibt es einige Situationen, in denen über Elemente sprechen will, die gewissermaßen viel einfacher (oder viel unvollständiger sind) als ein gegebener Staat der Information. Zum Beispiel, in der natürlichen Teilmenge-Einschließung, die auf einem powerset bestellt, ist jedes unendliche Element (d. h. Satz) "viel informativer" als einige seiner begrenzten Teilmengen.

Wenn man solch eine Beziehung modellieren will, kann man zuerst die veranlasste strenge Ordnung, denken

wollen

es gibt ein Element d in solchem D dass

:.

Dann sagt man auch, dass x y näher kommt und schreibt

:.

Das bezieht wirklich das ein

:

seitdem der Singleton untergegangen ist {y} wird geleitet. Für ein Beispiel, in einer Einrichtung von Sätzen, ist ein unendlicher Satz Weg über einigen seiner begrenzten Teilmengen. Denken Sie andererseits den geleiteten Satz (tatsächlich: die Kette) begrenzter Sätze

:

Da das Supremum dieser Kette der Satz aller natürlichen Zahlen N ist, zeigt das, dass kein unendlicher Satz weit unter N ist.

Jedoch weit unter einem Element zu sein, ist ein Verhältnisbegriff und offenbart viel über ein Element allein nicht. Zum Beispiel würde man gern begrenzte Sätze auf eine mit der Ordnung theoretische Weise charakterisieren, aber sogar unendliche Sätze können weit unter einem anderen Satz sein. Das spezielle Eigentum dieser begrenzten Elemente x besteht darin, dass sie weit unter sich, d. h. sind

:.

Ein Element mit diesem Eigentum wird auch kompakt genannt. Und doch müssen solche Elemente nicht "begrenzt" noch in jedem anderen mathematischen Gebrauch der Begriffe "kompakt" sein. Die Notation wird dennoch durch bestimmte Parallelen zu den jeweiligen Begriffen in der Mengenlehre und Topologie motiviert. Die Kompaktelemente eines Gebiets haben das wichtige spezielle Eigentum, dass sie als eine Grenze eines geleiteten Satzes nicht erhalten werden können, in dem sie nicht bereits vorgekommen sind.

Viele andere wichtige Ergebnisse über weit unter der Beziehung unterstützen den Anspruch, dass diese Definition passend ist, um viele wichtige Aspekte eines Gebiets zu gewinnen.

Basen von Gebieten

Die vorherigen Gedanken bringen eine andere Frage auf: Ist es möglich zu versichern, dass alle Elemente eines Gebiets als eine Grenze von viel einfacheren Elementen erhalten werden können? Das ist in der Praxis ziemlich wichtig, da wir unendliche Gegenstände nicht schätzen können, aber wir können noch hoffen, ihnen willkürlich nah näher zu kommen.

Mehr allgemein würden wir gern auf eine bestimmte Teilmenge von Elementen als genügend seiend einschränken, um alle anderen Elemente als kleinste obere Grenzen zu bekommen. Folglich definiert man eine Basis eines poset P als seiend eine Teilmenge B P, solch, dass, für jeden x in P, der Satz von Elementen in B, die weit unter x sind, einen geleiteten Satz mit dem Supremum x enthält. Der poset P ist ein dauernder poset, wenn er eine Basis hat. Besonders, P selbst ist eine Basis in dieser Situation. In vielen Anwendungen schränkt man auf den dauernden (d) cpos als ein Hauptgegenstand der Studie ein.

Schließlich wird eine noch stärkere Beschränkung eines teilweise bestellten Satzes durch das Verlangen der Existenz einer Basis von Kompaktelementen gegeben. Solch ein poset wird algebraisch genannt. Aus dem Gesichtspunkt der denotational Semantik sind algebraische posets besonders wohl erzogen, da sie die Annäherung aller Elemente selbst wenn berücksichtigen, auf begrenzte einschränkend. Wie bemerkt, vorher ist nicht jedes begrenzte Element in einem klassischen Sinn "begrenzt", und es kann gut sein, dass die begrenzten Elemente einen unzählbaren Satz einsetzen.

In einigen Fällen, jedoch, ist die Basis für einen poset zählbar. In diesem Fall spricht man von einem ω-continuous poset. Entsprechend, wenn die zählbare Basis völlig aus begrenzten Elementen besteht, erhalten wir eine Ordnung, die ω-algebraic ist.

Spezielle Typen von Gebieten

Ein einfacher spezieller Fall eines Gebiets ist als ein elementares oder flaches Gebiet bekannt. Das besteht aus einer Reihe unvergleichbarer Elemente, wie die ganzen Zahlen, zusammen mit einem einzelnen "untersten" Element betrachtet kleiner als alle anderen Elemente.

Man kann mehrere andere interessante spezielle Klassen von bestellten Strukturen erhalten, die als "Gebiete" passend sein konnten. Wir haben bereits dauernden posets und algebraischen posets erwähnt. Speziellere Versionen sowohl dessen sind dauernder als auch algebraischer cpos. Das Hinzufügen noch weiterer Vollständigkeitseigenschaften man erhält dauernde Gitter und algebraische Gitter, die gerade ganze Gitter mit den jeweiligen Eigenschaften sind. Für den algebraischen Fall findet man breitere Klassen von posets, die sich es noch lohnt zu studieren: Historisch waren die Gebiete von Scott die ersten in der Bereichstheorie zu studierenden Strukturen. Noch werden breitere Klassen von Gebieten durch SFP-Gebiete, L-Gebiete und bifinite Gebiete eingesetzt.

Alle diese Klassen von Ordnungen können in verschiedene Kategorien von dcpos mit Funktionen geworfen werden, die Eintönigkeit, Scott-dauernd, oder noch mehr spezialisiert als morphisms sind. Bemerken Sie schließlich, dass der Begriff Gebiet selbst nicht genau ist und nur so als eine Abkürzung gebraucht wird, als eine formelle Definition vorher gegeben worden ist, oder wenn die Details irrelevant sind.

Wichtige Ergebnisse

Ein poset D ist ein dcpo, wenn, und nur wenn jede Kette in D ein Supremum hat.

Wenn f eine dauernde Funktion auf einem poset D dann ist, hat er einen am wenigsten festen Punkt, gegeben als das am wenigsten obere, das aller begrenzten Wiederholungen von f auf kleinstem Element 0 gebunden ist: V f (0). Das ist der Fixpunktsatz von Kleene.

Generalisationen

• Synthetische Bereichstheorie
• Topologische Bereichstheorie
• Ein Kontinuitätsraum ist eine Generalisation von metrischen Räumen und posets, der verwendet werden kann, um die Begriffe von metrischen Räumen und Gebieten zu vereinigen.

Siehe auch

• Gebiet von Scott
• Informationssystem von Scott
• Typ-Theorie
• Kategorie-Theorie

Weiterführende Literatur

Außenverbindungen

• Einführung in die Bereichstheorie von Graham Hutton, Universität Nottinghams