In der Mathematik, vor allem, um der Theorie, ist ein Galois-Verbindung eine bestimmte Übereinstimmung zwischen zwei Halbordnungen. Der gleiche Begriff kann auch auf vorbestellt Sätze oder Klassen definiert werden; Dieser Artikel stellt die häufigste Fall von Posets. Galois-Verbindungen zu verallgemeinern die Korrespondenz zwischen Untergruppen und Unterfelder in Galoistheorie sucht. Sie finden Anwendung in verschiedenen mathematischen Theorien.

Ein Galois-Verbindung ist eher schwach im Vergleich zu einer Bestellung Isomorphismus zwischen den beteiligten Posets, aber jedes Galois-Verbindung führt zu einem Isomorphismus bestimmter Unter Posets, wie weiter unten erläutert wird.

In der Literatur sind zwei eng verwandte Begriffe "Galois-Verbindung". In diesem Artikel werden wir zwischen den beiden unter Bezugnahme auf die erste als Galois-Anschluss und mit dem zweiten als antitone Galoisverbindung unterscheiden.

Der Begriff Galois Korrespondenz wird manchmal zur bijektive Galoisverbindung meine, ist einfach ein, um Isomorphismus.

Begriffsbestimmungen

 Galoisverbindung

Lassen Sie Und Werden zwei Halbordnungen. Eine monoton Galois Verbindung zwischen diesen posets aus zwei monotone Funktionen: F: A → B und G: B → A, so daß für alle a in A und B in B haben wir

In dieser Situation F heißt die untere Adjungierte G und G wird als der obere Adjungierte F. mnemonisch bezieht sich der obere / untere Terminologie, wo der Funktionsanwendung relativ zum ≤ erscheint; der Begriff "adjungierten" bezieht sich auf die Tatsache, dass monotone Galois-Verbindungen sind Spezialfälle Paare adjungierten functors in Kategorie Theorie wie weiter unten diskutiert. Weitere Terminologie hier begegnet, ist coadjoint für den unteren adjoint.

Eine wesentliche Eigenschaft eines Galois-Verbindung ist, dass eine obere / untere adjoint eines Galois-Verbindung eindeutig die anderen bestimmt:

A → A, wie die zugehörige Verschlussbetreiber bekannt, und FG:: B → B, wie der zugehörige Kernel Betreiber bekannt gegeben ein Galois Verbindung mit niedrigeren adjoint F und Ober adjoint G, können wir die Kompositionen GF berücksichtigen. Beide sind monoton und idempotent, und wir haben eine ≤ GF für alle a in A und FG ≤ b für alle b in B.

Ein Galois Insertion von A in B ist ein Galois-Verbindung, in der die Schließung des Bedieners GF ist die Identität von A.

Antitone Galoisverbindung

Die obige Definition ist in vielen Anwendungen muß und deutlich in Gitter und Domain Theorie. Die ursprüngliche Vorstellung in Galoistheorie ist jedoch etwas anders. Bei dieser alternativen Definition ist ein Galois-Verbindung ein Paar von antitone, dh um Richtung, Funktionen F: A → B und G: B → A zwischen zwei Posets A und B, so dass

Die Symmetrie von F und G in dieser Version löscht die Unterscheidung zwischen den oberen und unteren, die beiden Funktionen werden dann Polaritäten statt adjoints bezeichnet. Jede Polarität eindeutig bestimmt die anderen, da

Die Kompositionen GF: A → A und FG: B → B sind die damit verbundenen Schließung Betreiber; sie sind monotone idempotent Karten mit der Eigenschaft a ≤ GF für alle a in A und b ≤ FG für alle b in B.

Die Auswirkungen der beiden Definitionen der Galois-Verbindungen sind sehr ähnlich, da eine antitone Galois Verbindung zwischen A und B ist nur eine monotone Galois Verbindung zwischen A und die Reihenfolge Dual B von B. Die nachstehenden Aussagen über Galois-Verbindungen können so einfach sein in Aussagen über antitone Galois-Verbindungen umgewandelt.

Beispiele

Monotone Galois-Verbindungen

Antriebssatz; Implikation und Verbindung

Für eine Bestellung theoretischen Beispiel wollen einige U-Set, und sei A und B sowohl die Potenzmenge von U, durch die Aufnahme bestellt werden. Wählen Sie einen festen Untermenge L von U. Dann die Karten F und G, wobei F = L ∩ M und G = N ∪, bilden eine monotone Galois-Verbindung, wobei F die untere adjoint. Eine ähnliche Galoisverbindung dessen untere adjoint wird von der Operation gegeben treffen kann in jeder Heyting Algebra gefunden werden. Insbesondere ist es in jeder Boolesche Algebra, wo die beiden Zuordnungen können durch F = und G = = beschrieben vor. In logischen Begriffen: "stillschweigend aus a" ist der obere adjoint der "Verbindung mit einem".

Die Gitter

Weitere interessante Beispiele für die Galois-Verbindungen werden in dem Artikel auf Vollständigkeit Eigenschaften beschrieben. Grob gesagt, es stellt sich heraus, dass die üblichen Funktionen ∨ und ∧ sind untere und obere adjoints zur Diagonale Karte X → X × X. Die kleinsten und größten Elemente einer Teilordnung werden von unteren und oberen adjoints der einzigartigen Funktion gegeben X → {1}. Weiter zu gehen, können sogar vollständige Verbände durch das Vorhandensein von geeigneten adjoints charakterisiert werden. Diese Überlegungen geben einen Eindruck von der Allgegenwart von Galois-Verbindungen, um Theorie.

Transitive Gruppenaktionen

Sei G Akt transitiv auf X und holen einige Punkt x in X. Betrachten

der Satz von Blöcken mit x. Ferner sei aus der Untergruppen von G den Stabilisator enthaltenden von x.

Dann wird die Korrespondenz:

eine monotone, eins-zu-eins Galoisverbindung. Als logische Folge, kann man feststellen, dass zweifach transitive Handlungen keine anderen als die trivialen Blöcke: Dies folgt aus der Stabilisatoren als maximaler in G in diesem Fall. Siehe doppelt transitive Gruppe für die weitere Diskussion.

Bild und Urbild

Ist f: X → Y ist eine Funktion, dann für jede Teilmenge M von X können wir das Bild F = f = {f bilden | m ∈ M} und für jede Untergruppe N von Y können wir das Urbild G = f bilden = {x ∈ X | f ∈ N}. Dann F und G bilden eine monotone Galois Verbindung zwischen dem Leistungssatz X und die Potenzmenge von Y, die beide durch die Aufnahme bestellt ⊆. Es gibt ein weiteres adjoint Paar in dieser Situation: für eine Teilmenge M von X, definieren H = {y ∈ Y | f ⊆ M}. Dann G und H bilden eine monotone Galois Verbindung zwischen dem Leistungssatz Y und der Potenzmenge von X. Im ersten Galois-Verbindung ist, G die obere adjoint, während in der zweiten Galois-Verbindung ist es als untere adjoint dient.

Im Fall eines Quotienten Karte zwischen algebraischen Objekten ist dieser Zusammenhang so genannte Gittersatz: Gruppen von G verbinden Gruppen von G / N, und das Verschluss Operator auf Untergruppen von G wird durch H = HN angegeben.

Span und Verschluss

Pick einige mathematisches Objekt X, die eine zugrunde liegende Satz hat, zum Beispiel eine Gruppe, Ring, Vektorraum, usw. Für jede Teilmenge S von X sei F die kleinste Unterobjekt von X, die S enthält, dh der Untergruppe, Unterring oder Teilraum erzeugt von S. Für jede Teilobjekt U von X, sei G die zugrunde liegende Satz von U. sein (Wir können sogar X ein topologischer Raum, sei F die Schließung von S, und nehmen Sie als "Unterobjekte von X" die geschlossenen Teilmengen X.) Jetzt F und G bilden eine monotone Galois Verbindung zwischen Teilmengen von X und Unterobjekte von X, wenn beide durch die Aufnahme bestellt. F ist die untere adjoint.

Syntax und Semantik

Eine sehr allgemeine Bemerkung von William Lawvere ist, dass Syntax und Semantik sind adjoint: Nehmen Sie ein, um die Menge aller logischen Theorien zu sein, und B die Potenzmenge der Menge aller mathematischen Strukturen. Für eine Theorie T ∈ A sei F die Menge aller Strukturen, die die Axiome T befriedigen; für eine Reihe von mathematischen Strukturen S, sei G das Minimum der Axiomatisierungen sein, was ungefähre S. Wir können dann sagen, dass F eine Teilmenge von S, wenn und nur wenn T bedeutet logischerweise G: der "Semantik Funktor" F und die "Syntax Funktor "G bilden eine monotone Galois-Verbindung, mit der Semantik als die untere adjoint.

Antitone Galois-Verbindungen

Galoistheorie

Die motivierende Beispiel stammt aus Galoistheorie: Angenommen, L / K eine Körpererweiterung. Sei A die Menge aller Teilfelder L, die K enthalten, durch die Aufnahme ⊆ bestellt werden. Wenn E ist so ein Unterfeld, schreiben Gal für die Gruppe von Feld Automorphismen von L, die E halten fixiert. Sei B die Menge der Untergruppen von Gal, durch die Aufnahme bestellt ⊆ sein. Für eine solche Untergruppe G definieren beheben, um das Feld, bestehend aus allen Elementen der L, die von allen Elementen der G. Dann wird die Karten E ↦ Gal und G festgehalten werden ↦ Fix bilden einen antitone Galois-Verbindung sein.

Algebraischen Topologie: Überlagerungen

Analog kann bei einer wegzusammenhängender topologischen Raum X, gibt es eine antitone Galois Verbindung zwischen Untergruppen der Fundamentalgruppe π1 und wegzusammenhängender Lagerungen von X. Insbesondere wenn X halb lokal einfach zusammenhängenden, dann für jeden Untergruppe G von π1, gibt es eine Überlagerung mit G als Fundamentalgruppe.

Lineare Algebra: Vernichter und orthogonalen Komplemente

Bei einer Innenproduktraum V, können wir das orthogonale Komplement F jeder Teilraum X von V. Dies ergibt eine antitone Galois Verbindung zwischen dem Satz von Teilräume von V und selbst durch die Aufnahme bestellt bilden; beide Polaritäten gleich F. sind

Bei einem Vektorraum V und eine Teilmenge von X V wir ihre annihilator F zu definieren, bestehend aus allen Elementen des Dualraum V von V, zu verschwinden X. Ebenso gegebene Teilmenge Y V, dessen annihilator G = {definieren wir x ∈ V | φ = 0 ∀φ ∈ Y}. Dies ergibt eine antitone Galois Verbindung zwischen den Untergruppen von V und der Untergruppen von V.

Algebraische Geometrie

In der algebraischen Geometrie, ist die Beziehung zwischen den Sätzen von Polynomen und ihre Nullsätze ein antitone Galois-Verbindung.

Fix eine natürliche Zahl n und eine Feld K und A die Menge aller Teilmengen der Polynomring K durch die Aufnahme ⊆ bestellt, und sei B die Menge aller Teilmengen von K durch die Aufnahme ⊆ bestellt werden. Wenn S eine Menge von Polynomen, definieren die Vielzahl von Nullen

die Menge der gemeinsamen Nullstellen der Polynome in S. Wenn U eine Teilmenge von K definiere ich als idealer von Polynomen Flucht auf U, ist, dass

Dann V und I bilden einen antitone Galois-Verbindung.

Die Schließung von K ist die Schließung in der Zariski-Topologie, und wenn das Feld K algebraisch abgeschlossen ist, dann ist der Verschluss auf dem Polynomring den Rest ideal durch S. generiert

Allgemeiner gegeben ein kommutativer Ring R, gibt es eine antitone Galois Verbindung zwischen radikalen Ideale in den Ring und Unterarten der affinen Vielzahl Spec.

Ganz allgemein gibt es eine antitone Galois Verbindung zwischen Idealen in den Ring und Teilregelungen der entsprechenden affine Varietät.

Anschlüsse an Stromaggregate, die aus binären Beziehungen

Angenommen, X und Y beliebige Mengen und eine binäre Relation R auf X und Y gegeben ist. Für jede Teilmenge M von X definieren wir F = {y ∈ Y | MRY ∀m ∈ M}. In ähnlicher Weise für jede Untergruppe N von Y, definieren G = {x ∈ X | XRN ∀n ∈ N}. Dann F und G ergeben einen antitone Galois Verbindung zwischen den Stromaggregate von X und Y, die beide durch die Aufnahme bestellt ⊆.

Viele antitone Galois-Verbindungen ergeben sich auf diese Weise; Beispiele sind die ursprüngliche Verbindung von Galois Theorie, die Verbindungen in der linearen Algebra und die Verbindung von algebraischen Geometrie oben erläutert.

Immobilien

Im Folgenden betrachten wir einen Galoisverbindung f =, wobei f: A → B ist die untere adjungierten wie oben eingeführt. Einige nützliche und lehrGrundEigenschaften kann sofort bezogen werden. Durch die definierende Eigenschaft der Galois-Verbindungen ist f ≤ f äquivalent zu x ≤ f * (f) für alle x in A durch eine ähnliche Argumentation, dass f (f *) ≤ y, für alle y in B. findet man Diese Eigenschaften können mit den Worten beschrieben werden die Verbund f ∘ f * ist Deflation, während f * ∘ f ist inflationär.

Nun betrachten x, y ∈ A x ≤ y, dann unter Verwendung des obigen erhält man x ≤ f * (f). Die Anwendung der grundlegenden Eigenschaft des Galois-Verbindungen kann man nun schließen, dass f ≤ f. Aber das zeigt nur, dass f bewahrt die Reihenfolge der zwei Elemente, dh sie ist monoton. Auch hier ergibt sich eine ähnliche Argumentation Monotonie von f *. So Monotonie muss nicht in der Definition ausdrücklich einbezogen werden. , Erwähnens Monotonie hilft jedoch zu Verwirrung über die zwei alternative Vorstellungen von Galois-Verbindungen zu vermeiden.

Eine weitere grundlegende Eigenschaft des Galois-Verbindungen ist die Tatsache, dass f * (f (f *)) = f * für alle x in B. Offensichtlich finden wir, dass

da f * ∘ f Inflations wie oben gezeigt. Auf der anderen Seite, da f ∘ f * ist Deflation, während f * monoton ist, findet man, dass

Dies zeigt die gewünschte Gleichheit. Darüber hinaus können wir diese Eigenschaft verwenden, zu schließen, dass

und

dh f ∘ f * und f * ∘ f sind idempotent.

Es kann gezeigt werden, daß eine Funktion f ist eine niedrigere adjungierten genau dann, wenn f eine residuated Kartierung. Daher der Begriff residuated Kartierung und monotone Galoisverbindung im wesentlichen gleich sind.

Closure Betreiber und Galois-Verbindungen

Die obigen Ergebnisse können wie folgt zusammengefasst werden: für ein Galois-Verbindung ist das Verbund f * ∘ f monoton, Inflations und idempotent. Diese besagt, dass f * ∘ f ist in der Tat ein Verschluss Operator auf A. Dual dazu f ∘ f * ist monoton, deflationären und idempotent. Solche Zuordnungen werden manchmal auch als Kernel-Operatoren. Im Rahmen der Rahmen und Sprachumgebungen wird die Verbund f * f ∘ genannte Kern durch f induziert. Kernen induzieren Homomorphismen Rahmen; eine Teilmenge einer Länderkennung genannt sublocale wenn es von einem Kern gegeben ist.

Umgekehrt ist jede Verschlussbetreiber c auf einige Poset A ergibt sich die Galois Verbindung mit niedrigeren adjoint f wobei nur die corestriction von c, um das Bild von c (dh als surjektive Abbildung das Verschlusssystem c). Der obere adjungierten f * wird dann durch den Einschluß von C in A, die jedes geschlossene Element, um sich als ein Element A. Auf diese Weise berücksichtigt Karten angegeben, werden Verschlussbetreiber und Galois Verbindungen gesehen, eng verwandt werden, die jeweils eine Angabe Instanz des anderen. Ähnliche Schlussfolgerungen gelten für Kernel-Operatoren.

Die vorstehenden Überlegungen zeigen auch, dass geschlossene Elemente eines (Elemente x mit f * (f) = x), um Elemente im Bereich des Kernels Operator f ∘ f * zugeordnet, und umgekehrt.

Existenz und Eindeutigkeit von Galois-Verbindungen

Eine weitere wichtige Eigenschaft des Galois-Verbindungen ist, dass niedrigere adjoints erhalten alle suprema, die innerhalb ihrer Domäne vorhanden. Dual dazu oberen adjoints erhalten alle bestehenden infima. Von diesen Eigenschaften kann man auch Monotonie der adjoints schließen, sofort. Die adjungierten Funktor Satz für Ordnung Theorie besagt, dass die umgekehrte Implikation ist auch in bestimmten Fällen gelten: insbesondere ist jede Zuordnung zwischen vollständige Verbände, die alle suprema bewahrt die untere adjoint eines Galois-Verbindung.

In dieser Situation ist ein wichtiges Merkmal der Galois-Verbindungen, die eine adjungierten eindeutig bedingt das andere. Daher kann man die obige Aussage zu verstärken, um zu gewährleisten, dass jede supremum erhalt Karte zwischen vollständige Verbände ist die untere adjoint der einzigartigen Galois-Verbindung. Die wichtigste Eigenschaft, um diese Einzigartigkeit abzuleiten ist folgende: Für alle x in A, f die kleinste Element y von B, so dass x ≤ f *. Dual dazu für jedes y in B, f * der größte x in A, so dass f ≤ y. Die Existenz einer bestimmten Galoisverbindung impliziert nun die Existenz der jeweiligen mindestens oder größten Elemente, unabhängig davon, ob die entsprechenden posets keine Vollständigkeit Eigenschaften erfüllen. Somit wird, wenn eine obere adjoint eines Galois-Verbindung gegeben ist, die andere obere adjoint können über diese gleiche Eigenschaft definiert werden.

Auf der anderen Seite, ist etwas monotone Funktion f eine niedrigere adjoint wenn und nur wenn jeder Satz von der Form {x ∈ A | f ≤ b}, für b in B, enthält ein größtes Element. Auch dies kann für den oberen adjungierten dualisierten werden.

Galois-Verbindungen als Morphismen

Galois-Verbindungen stellen auch eine interessante Klasse von Abbildungen zwischen posets die verwendet werden können, um Kategorien von Posets erhalten. Insbesondere ist es möglich, Galois-Verbindungen zusammen: gegebenen Galois Verbindungen zwischen posets A und B und zwischen B und C ist das Verbund auch ein Galois-Verbindung. Bei der Betrachtung Kategorien der vollständige Verbände, kann diese vereinfachten auf die Prüfung nur Zuordnungen Erhaltung alle suprema sein. Abbilden vollständige Verbände ihre duals, Anzeige dieser Kategorien Auto Dualität, die ganz wesentlich für den Erhalt anderen Dualität Theoreme sind. Weitere spezielle Arten von Morphismen, die zwischen zusammengefügten Zuordnungen in die andere Richtung zu induzieren sind die Morphismen in der Regel für Rahmen betrachtet.

Verbindung zum Kategorientheorie

Jedes Halbordnung kann als eine Kategorie auf eine natürliche Weise betrachtet werden: Es ist eine einzigartige Morphismus von x nach y genau dann, wenn x ≤ y. Eine monotone Galois-Verbindung ist dann nichts anderes als ein Paar von adjungierten Funktoren zwischen zwei Kategorien, die von Halbordnungen ergeben. In diesem Zusammenhang ist der obere adjungierten die rechte adjungierten während die untere adjungierten ist die linke adjungierten. Allerdings ist diese Terminologie für Galois-Verbindungen vermieden, denn es gab eine Zeit, Posets wurden in Kategorien in einer Dual Mode verwandelt, dh mit Pfeilen, die in die entgegengesetzte Richtung. Dies führte zu einer komplementären Notation hinsichtlich links und rechts adjoints, die heute nicht eindeutig ist.

Anwendungen in der Theorie der Programmierung

Galois-Verbindungen verwendet werden, um viele Formen der Abstraktion in der Theorie der abstrakten Interpretation von Programmiersprachen zu beschreiben.