Darstellungssatz von Birkhoff - Birkhoff's representation theorem

Hier geht es um Gittertheorie . Für andere ähnlich benannte Ergebnisse siehe den Satz von Birkhoff (Begriffsklärung) .

In der Mathematik , Birkhoffs Darstellungssatz für distributive Latices besagt , dass die Elemente jeder finite distributive Gitter kann dargestellt werden als endliche Mengen , so daß die Gitter Operationen entsprechen Vereinigungen und Kreuzungen von Sätzen. Das Theorem kann so interpretiert werden, dass es eine Eins-zu-Eins-Entsprechung zwischen distributiven Gittern und Teilordnungen , zwischen quasi-ordinalen Wissensräumen und Vorordnungen oder zwischen endlichen topologischen Räumen und Vorordnungen bereitstellt. Es ist nach Garrett Birkhoff benannt , der 1937 einen Beweis dafür veröffentlichte.

Der Name „Birkhoffs Darstellungssatz“ hat auch zwei weitere Ergebnisse von Birkhoff, ein aus dem Jahr 1935 auf der angewandte Darstellung der Booleschen Algebren als Familien von Sätzen unter Vereinigung, Schnitt geschlossen und Komplement (sogenannte Felder von Sätzen , eng verwandt mit die Ringe von Mengen, die von Birkhoff verwendet werden, um Verteilungsgitter darzustellen), und das HSP-Theorem von Birkhoff, das Algebren als Produkte irreduzibler Algebren darstellt. Der Darstellungssatz von Birkhoff wird auch als Fundamentalsatz für endliche Verteilungsgitter bezeichnet .

Das Theorem verstehen

Viele Gitter können so definiert werden, dass die Elemente des Gitters durch Mengen repräsentiert werden, die Join-Operation des Gitters durch Mengenvereinigung repräsentiert wird und die Meet-Operation des Gitters durch Mengenschnitt repräsentiert wird. Zum Beispiel hat das Boolesche Gitter, das aus der Familie aller Teilmengen einer endlichen Menge definiert ist, diese Eigenschaft. Allgemeiner gesagt hat jeder endliche topologische Raum ein Gitter von Mengen als seine Familie offener Mengen. Da Mengenvereinigungen und Schnittmengen dem Verteilungsgesetz gehorchen , ist jedes so definierte Gitter ein Verteilungsgitter. Der Satz von Birkhoff besagt, dass tatsächlich alle endlichen Verteilungsgitter auf diese Weise erhalten werden können, und spätere Verallgemeinerungen des Satzes von Birkhoff sagen ähnliches für unendliche Verteilungsgitter.

Beispiele

Das Verteilungsgitter der Teiler von 120 und seine Darstellung als Mengen von Primzahlen.

Betrachten Sie die Teiler einer zusammengesetzten Zahl, wie (in der Abbildung) 120, teilweise geordnet nach Teilbarkeit. Zwei beliebige Teiler von 120, wie 12 und 20, haben einen eindeutigen größten gemeinsamen Faktor 12 20 = 4, die größte Zahl, die beide teilt, und ein eindeutiges kleinstes gemeinsames Vielfaches 12 ∨ 20 = 60; beide dieser Nummern sind auch Divisoren von 120. Diese beiden Vorgänge ∨ und ∧ den befriedigen Distributivgesetzes , in einer von zwei äquivalenten Formen an : ( x  ∧  y ) ∨  z  = ( x  ∨  z ) ∧ ( y  ∨  z ) und ( x  ∨  y ) ∧  z  = ( x  ∧  z ) ∨ ( y  ∧  z ) für alle x , y , und z . Daher bilden die Teiler ein endliches Verteilungsgitter .

Man kann jeden Teiler der Menge der Primzahlen , die ihn teilen, zuordnen: 12 ist also der Menge {2,3,4} zugeordnet, während 20 der Menge {2,4,5} zugeordnet ist. Dann ist 12 ∧ 20 = 4 der Menge {2,3,4} ∩ {2,4,5} = {2,4} zugeordnet, während 12 ∨ 20 = 60 der Menge {2,3,4 . zugeordnet ist } ∪ {2,4,5} = {2,3,4,5}, also entsprechen die Join- und Meet-Operationen des Gitters der Vereinigung und dem Schnitt von Mengen.

Die in diesen Mengen als Elemente auftretenden Primzahlen 2, 3, 4, 5 und 8 können selbst teilweise nach Teilbarkeit geordnet sein; in dieser kleineren Teilordnung 2 ≤ 4 ≤ 8 und es gibt keine Ordnungsbeziehungen zwischen anderen Paaren. Die 16 Mengen, die Teilern von 120 zugeordnet sind, sind die unteren Mengen dieser kleineren Teilordnung, Teilmengen von Elementen, so dass, wenn x ≤ y und y zur Teilmenge gehört, auch x zur Teilmenge gehören muss. Aus jeder niedrigeren Menge L kann man den zugehörigen Teiler durch Berechnen des kleinsten gemeinsamen Vielfachen der Primzahlen in L wiederherstellen . Somit trägt die Teilordnung der fünf Primzahlen 2, 3, 4, 5 und 8 genügend Informationen, um das gesamte ursprüngliche 16-Elemente-Teilbarkeitsgitter wiederherzustellen.

Der Satz von Birkhoff besagt, dass diese Beziehung zwischen den Operationen ∧ und ∨ des Teilergitters und den Operationen ∩ und ∪ der zugehörigen Mengen von Primzahlen nicht zufällig ist und nicht von den spezifischen Eigenschaften der Primzahlen und der Teilbarkeit abhängt: die Elemente von Jedes endliche Verteilungsgitter kann auf die gleiche Weise mit niedrigeren Mengen einer Teilordnung assoziiert werden.

Als weiteres Beispiel erzeugt die Anwendung des Satzes von Birkhoff auf die Familie von Teilmengen einer n- elementigen Menge, die teilweise durch Inklusion geordnet ist, das freie Verteilungsgitter mit n Generatoren. Die Anzahl der Elemente in diesem Gitter ist durch die Dedekind-Zahlen gegeben .

Die partielle Ordnung der Join-Irreduziblen

In einem Gitter, ein Element x ist fugen irreduziblen wenn x nicht die Verbindung einer endlichen Menge von anderen Elementen ist. Entsprechend ist x nicht reduzierbar, wenn es weder das unterste Element des Gitters (die Verbindung von Nullelementen) noch die Verbindung zweier kleinerer Elemente ist. Zum Beispiel gibt es im Gitter der Teiler von 120 kein Elementpaar, dessen Join 4 ist, also ist 4 Join-irreduzibel. Ein Element x ist Join-prime , wenn sie von dem Bodenelement unterscheiden, und , wenn x  ≤  y  ∨  z entweder x  ≤  y oder x  ≤  z . Im selben Gitter ist 4 eine Primzahlverbindung: Immer wenn lcm( y , z ) durch 4 teilbar ist, muss mindestens eines von y und z selbst durch 4 teilbar sein.

In jedem Gitter muss ein Join-Prime-Element Join-irreduzibel sein. Entsprechend ist ein Element, das nicht Join-irreduzibel ist, nicht Join-Prime. Denn, wenn ein Element x ist nicht fugen irreduziblen existieren kleinere y und z , so daß x  =  y  ∨  z . Aber dann ist x  ≤  y  ∨  z , und x ist nicht kleiner oder gleich y oder z , was zeigt, dass es keine Primzahlverbindung ist.

Es gibt Gitter, in denen die Join-Prime-Elemente eine echte Teilmenge der Join-irreduziblen Elemente bilden, aber in einem distributiven Gitter fallen die beiden Arten von Elementen zusammen. Denn, annimmt , dass die x ist fugen irreduziblen und dass x  ≤  y  ∨  z . Diese Ungleichung ist äquivalent zu der Aussage x  =  x  ( y  ∨  z ) und nach dem Distributivgesetz x  = ( x  ∧  y ) ( x  ∧  z ). Da aber x ist fugen irreduziblen, mindestens eine der beiden Begriffe in diesem beitreten muss x selbst, was zeigt , daß entweder x  =  x  ∧  y (äquivalent x  ≤  y ) oder x  =  x  ∧  z (äquivalenter x  ≤  z ).

Die Gitterordnung auf der Teilmenge der verbindenden irreduziblen Elemente bildet eine Teilordnung ; Der Satz von Birkhoff besagt, dass das Gitter selbst aus den unteren Mengen dieser Teilordnung gewonnen werden kann.

Der Satz von Birkhoffhoff

Distributives Beispielgitter, mit Join-irreduziblen Elementen a,...,g (schattierte Knoten). Die untere Menge, der ein Knoten nach dem Birkhoff-Isomorphismus entspricht, ist blau dargestellt.

In jeder partiellen Ordnung bilden die unteren Mengen ein Gitter, in dem die partielle Ordnung des Gitters durch die Mengeninklusion gegeben ist, die Join-Operation der Mengenvereinigung entspricht und die Meet-Operation der Mengenschnittmenge entspricht, da Vereinigungen und Schnittmengen die Eigenschaft beibehalten, a . zu sein unteren Satz. Da Mengenvereinigungen und Schnittmengen dem Verteilungsgesetz gehorchen, handelt es sich um ein Verteilungsgitter. Der Satz von Birkhoff besagt, dass auf diese Weise jedes endliche Verteilungsgitter konstruiert werden kann.

Satz . Jedes endliche Verteilungsgitter L ist isomorph zum Gitter der unteren Mengen der Teilordnung der verbindenden irreduziblen Elemente von L .

Das heißt, es gibt eine eins-zu-eins ordnungserhaltende Entsprechung zwischen Elementen von L und niedrigeren Mengen der Teilordnung. Die untere Menge, die einem Element x von L entspricht, ist einfach die Menge der bei der Verbindung nicht reduzierbaren Elemente von L , die kleiner oder gleich x sind , und das Element von L , das einer unteren Menge S der nicht reduzierbaren Elemente der Verbindung entspricht, ist die Verbindung von S. .

Für jede niedrigere Menge S von Join-irreduziblen Elementen sei x der Join von S , und sei T der untere Satz der Join-irreduziblen Elemente kleiner oder gleich x . Dann ist S  =  T . Denn jedes Element von S gehört eindeutig zu T , und jedes Join-irreduzible Element kleiner oder gleich x muss (nach Join-Primalität) kleiner oder gleich einem der Mitglieder von S sein und muss daher (nach der Annahme dass S eine niedrigere Menge ist) gehören zu S selbst. Umgekehrt wird für jedes Element x von L , lassen S sein die Join-irreduziblen Elemente weniger als oder gleich x und ließ y die Join sein S . Dann ist x  =  y . Denn als Join von Elementen kleiner oder gleich x kann y nicht größer als x selbst sein, aber wenn x Join-irreduzibel ist, dann gehört x zu S, während x der Join von zwei oder mehr Join-irreduziblen Elementen ist, dann sie müssen wieder zu S gehören , also y  ≥  x . Daher ist die Korrespondenz eins zu eins und der Satz ist bewiesen.

Ringe von Sets und Vorbestellungen

Birkhoff (1937) definierte einen Ring von Mengen als eine Familie von Mengen , die unter den Operationen von Mengenvereinigungen und Mengenschnitten abgeschlossen ist; später, motiviert durch Anwendungen in der mathematischen Psychologie , bezeichneten Doignon & Falmagne (1999) dieselbe Struktur als quasi-ordinalen Wissensraum . Wenn die Mengen in einem Ring von Mengen durch Inklusion geordnet sind, bilden sie ein Verteilungsgitter. Den Elementen der Mengen kann eine Vorordnung gegeben werden, in der x  ≤  y ist, wenn eine Menge im Ring x aber nicht y enthält . Der Mengenring selbst ist dann die Familie der niedrigeren Mengen dieser Vorordnung, und jede Vorordnung führt auf diese Weise zu einem Mengenring.

Funktionalität

Der Satz von Birkhoff ist, wie oben erwähnt, eine Entsprechung zwischen einzelnen Teilordnungen und Verteilungsgittern. Sie kann aber auch auf eine Entsprechung zwischen ordnungserhaltenden Funktionen von Teilordnungen und beschränkten Homomorphismen der entsprechenden Verteilungsgitter erweitert werden. Die Richtung dieser Karten ist in dieser Korrespondenz umgekehrt.

Sei 2 die partielle Ordnung auf der zweielementigen Menge {0, 1} mit der Ordnungsrelation 0 < 1 und (nach Stanley) sei J(P) das Verteilungsgitter der unteren Mengen einer endlichen partiellen Ordnung P . Dann entsprechen die Elemente von J(P) eins zu eins den ordnungserhaltenden Funktionen von P bis 2 . Denn wenn ƒ eine solche Funktion ist, bildet ƒ −1 (0) eine niedrigere Menge, und umgekehrt, wenn L eine niedrigere Menge ist, kann man eine ordnungserhaltende Funktion ƒ L definieren , die L auf 0 abbildet und die die restlichen Elemente von abbildet P nach 1. Wenn g eine ordnungserhaltende Funktion von Q bis P ist , kann man eine Funktion g * von J(P) bis J(Q) definieren , die die Zusammensetzung von Funktionen verwendet , um ein beliebiges Element L von J(P) abzubilden. zu ƒ L  ∘  g . Diese zusammengesetzte Funktion bildet Q auf 2 ab und entspricht daher einem Element g *( L ) = (ƒ L  ∘  g ) −1 (0) von J(Q) . Ferner wird für jeden x und y in J (P) , g * ( x  ∧  y ) =  g * ( x ) ∧  g * ( y ) (ein Element von Q durch abgebildet g auf den unteren Satz x  ∩  y , wenn und nur wenn beide zu dem Satz von Elementen gehört abgebildet x und die Menge von Elementen abgebildet y ) und symmetrisch g * ( x  ∨  y ) =  g * ( x ) ∨  g * ( y ). Außerdem wird das untere Element von J(P) (die Funktion, die alle Elemente von P auf 0) abbildet, von g * auf das unterste Element von J(Q) abgebildet , und das oberste Element von J(P) wird von g . abgebildet * zum obersten Element von J(Q) . Das heißt, g * ist ein Homomorphismus beschränkter Gitter.

Jedoch entsprechen die Elemente von P selbst eins zu eins mit beschränkten Gitterhomomorphismen von J(P) bis 2 . Denn wenn x irgendein Element von P ist , kann man einen beschränkten Gitterhomomorphismus j x definieren , der alle unteren Mengen, die x enthalten, auf 1 und alle anderen unteren Mengen auf 0 abbildet . Und für jeden Gitterhomomorphismus von J(P) auf 2 , die Elemente von J(P) , die auf 1 abgebildet werden, müssen ein eindeutiges minimales Element x (das Zusammentreffen aller auf 1 abgebildeten Elemente) haben, das Join-irreduzibel sein muss (es kann nicht der Join irgendeiner Menge von Elementen sein, die auf 0 abgebildet sind ), so hat jeder Gitterhomomorphismus die Form j x für ein x . Wiederum kann man von jedem beschränkten Gitterhomomorphismus h von J(P) bis J(Q) die Zusammensetzung von Funktionen verwenden, um eine ordnungserhaltende Abbildung h * von Q bis P zu definieren . Es kann verifiziert werden, dass g ** =  g für jede ordnungserhaltende Abbildung g von Q nach P und dass und h ** =  h für jeden beschränkten Gitterhomomorphismus h von J(P) nach J(Q) .

In der kategorietheoretischen Terminologie ist J ein kontravarianter Hom-Funktor J  = Hom(—, 2 ), der eine Dualität von Kategorien zwischen der Kategorie endlicher Teilordnungen und ordnungserhaltenden Abbildungen einerseits und andererseits die Kategorie der endlichen Verteilungsgitter und der beschränkten Gitterhomomorphismen.

Verallgemeinerungen

Unendliche Verteilungsgitter

In einem unendlichen Verteilungsgitter kann es nicht der Fall sein, dass die unteren Sätze der nicht reduzierbaren Elemente in einer Eins-zu-Eins-Entsprechung mit Gitterelementen sind. Tatsächlich kann es überhaupt keine Join-irreduziblen geben. Dies geschieht zum Beispiel im Gitter aller natürlichen Zahlen, die mit der Umkehrung der üblichen Teilbarkeitsreihenfolge geordnet sind (also x  ≤  y, wenn y x teilt ): jede Zahl x kann als Verbindung der Zahlen xp und xq ausgedrückt werden, wobei p und q sind verschiedene Primzahlen . Elemente in unendlichen Verteilungsgittern können jedoch immer noch als Mengen über das Darstellungstheorem von Stone für Verteilungsgitter dargestellt werden, eine Form der Stone-Dualität, bei der jedes Gitterelement einer kompakten offenen Menge in einem bestimmten topologischen Raum entspricht . Dieser verallgemeinerte Darstellungssatz kann als kategorietheoretische Dualität zwischen Verteilungsgittern und Spektralräumen (manchmal als kohärente Räume bezeichnet, aber nicht identisch mit den kohärenten Räumen in der linearen Logik bezeichnet ), topologischen Räumen ausgedrückt werden , in denen die kompakten offenen Mengen unter Schnitt abgeschlossen sind und bilden eine Basis für die Topologie. Hilary Priestley zeigte, dass Stones Darstellungssatz als eine Erweiterung der Idee der Darstellung von Gitterelementen durch niedrigere Mengen einer Teilordnung interpretiert werden kann, indem sie Nachbins Idee geordneter topologischer Räume verwendet. Steinräume mit einer zusätzlichen Teilordnung, die über das Priestley-Trennaxiom mit der Topologie verknüpft ist, können auch verwendet werden, um beschränkte Verteilungsgitter darzustellen. Solche Räume werden als Priestley-Räume bezeichnet . Darüber hinaus verallgemeinern bestimmte bitopologische Räume , nämlich paarweise Stone-Räume , den ursprünglichen Ansatz von Stone, indem sie zwei Topologien auf einer Menge verwenden, um ein abstraktes Verteilungsgitter darzustellen. Somit erstreckt sich der Darstellungssatz von Birkhoff auf den Fall unendlicher (beschränkter) Verteilungsgitter auf mindestens drei verschiedene Arten, zusammengefasst in der Dualitätstheorie für Verteilungsgitter .

Medianalgebren und zugehörige Graphen

Der Darstellungssatz von Birkhoff kann auch auf andere endliche Strukturen als Verteilungsgitter verallgemeinert werden. In einem Verteilungsgitter ist die selbstduale Medianoperation

ergibt eine Medianalgebra , und die Überdeckungsrelation des Gitters bildet einen Mediangraphen . Endliche Medianalgebren und Mediangraphen haben eine duale Struktur als Menge von Lösungen einer 2-Erfüllbarkeitsinstanz ; Barthélemy & Constantin (1993) formulieren diese Struktur äquivalent als Familie der anfänglichen stabilen Mengen in einem gemischten Graphen . Bei einem distributiven Gitter hat der entsprechende gemischte Graph keine ungerichteten Kanten, und die anfänglichen stabilen Mengen sind nur die unteren Mengen des transitiven Abschlusses des Graphen. Äquivalent kann für ein distributives Gitter der Implikationsgraph der 2-Erfüllbarkeitsinstanz in zwei verbundene Komponenten unterteilt werden , eine auf die positiven Variablen der Instanz und die andere auf die negativen Variablen; der transitive Abschluss der positiven Komponente ist die zugrundeliegende Teilordnung des Verteilungsgitters.

Endliche Join-Verteilungsgitter und Matroide

Ein weiteres Ergebnis, das dem Darstellungssatz von Birkhoff analog ist, aber auf eine breitere Klasse von Gittern anwendbar ist, ist der Satz von Edelman (1980), dass jedes endliche Join-Distributiv-Gitter als ein Antimatroid dargestellt werden kann , eine Familie von Mengen, die unter Vereinigungen abgeschlossen sind, in denen aber Abschluss unter Schnittmengen wurde durch die Eigenschaft ersetzt, dass jede nichtleere Menge ein entfernbares Element hat.

Siehe auch

Anmerkungen

Verweise

  • Barthélemy, J.-P.; Constantin, J. (1993), "Median graphs, parallelism and posets", Discrete Mathematics , 111 (1–3): 49–63, doi : 10.1016/0012-365X(93)90140-O.
  • Birkhoff, Garrett (1937), "Rings of Sets", Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215/S0012-7094-37-00334-X.
  • Birkhoff, Garrett ; Kiss, SA (1947), "A ternary operation in distributive lattices" , Bulletin der American Mathematical Society , 53 (1): 749–752, doi : 10.1090/S0002-9904-1947-08864-9 , MR  0021540.
  • Doignon, J.-P.; Falmagne, J.-Cl. (1999), Wissensräume , Springer-Verlag, ISBN 3-540-64501-2.
  • Edelman, Paul H. (1980), "Meet-distributive lattices and the anti-exchange Closure", Algebra Universalis , 10 (1): 290–299, doi : 10.1007/BF02482912.
  • Johnstone, Peter (1982), „II.3 Coherent locales“, Stone Spaces , Cambridge University Press, S. 62–69, ISBN 978-0-521-33779-3.
  • Priestley, HA (1970), "Darstellung von distributiven Gittern mittels geordneter Steinräume", Bulletin der London Mathematical Society , 2 (2): 186–190, doi : 10.1112/blms/2.2.186.
  • Priestley, HA (1972), "Ordered topological space and the presentation of distributive lattices", Proceedings of the London Mathematical Society , 24 (3): 507–530, doi : 10.1112/plms/s3-24.3.507 , hdl : 10338 .dmlcz/134149.
  • Stanley, RP (1997), Enumerative Combinatorics, Band I , Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, S. 104–112.