In der Mathematik sind verteilende Gitter Gitter, für die sich die Operationen der Verbindungslinie und treffen, verteilen über einander. Die archetypischen Beispiele solcher Strukturen sind Sammlungen von Sätzen, für die die Gitter-Operationen von der Satz-Vereinigung und Kreuzung gegeben werden können. Tatsächlich beschreiben diese Gitter von Sätzen die Landschaft völlig: Jedes verteilende Gitter ist - bis zum Isomorphismus - gegeben als solch ein Gitter von Sätzen.

Definition

Als im Fall von willkürlichen Gittern kann man beschließen, ein verteilendes Gitter L entweder als eine Struktur der Ordnungstheorie oder von der universalen Algebra zu denken. Beide Ansichten und ihre gegenseitige Ähnlichkeit werden im Artikel über Gitter besprochen. Vor der gegenwärtigen Situation scheint die algebraische Beschreibung, günstiger zu sein:

Ein Gitter (L,) ist verteilend, wenn die folgende zusätzliche Identität für den ganzen x, y, und z in L hält:

:

Gitter als teilweise bestellte Sätze ansehend, sagt das, dass die entsprechen Operation nichtleere begrenzte Verbindungslinien bewahrt. Es ist eine grundlegende Tatsache der Gitter-Theorie, dass die obengenannte Bedingung zu seinem Doppel-gleichwertig ist:

:

Mehr Information über die Beziehung dieser Bedingung zu anderen distributivity Bedingungen der Ordnungstheorie kann im Artikel über distributivity (Ordnungstheorie) gefunden werden.

Morphisms

Ein morphism von verteilenden Gittern ist gerade ein Gitter-Homomorphismus, wie gegeben, im Artikel über Gitter, d. h. einer Funktion, die mit den zwei Gitter-Operationen vereinbar ist. Weil solch ein morphism von Gittern die Gitter-Struktur bewahrt, wird er folglich auch den distributivity bewahren (und so ein morphism von verteilenden Gittern sein).

Beispiele

Verteilende Gitter sind allgegenwärtige sondern auch ziemlich spezifische Strukturen. Wie bereits erwähnt, ist das Hauptbeispiel für verteilende Gitter Gitter von Sätzen, wo sich anschließen und sich treffen, werden durch die üblichen mit dem Satz theoretischen Operationen gegeben. Weitere Beispiele schließen ein:

• Die Lindenbaum Algebra vom grössten Teil der Logik, die Verbindung und Trennung unterstützt, ist ein verteilendes Gitter, d. h. "und" verteilt "oder" und umgekehrt.
• Jede Boolean Algebra ist ein verteilendes Gitter.
• Jede Heyting Algebra ist ein verteilendes Gitter. Besonders schließt das alle Schauplätze und folglich alle offenen Satz-Gitter von topologischen Räumen ein. Bemerken Sie auch, dass Algebra von Heyting als Algebra von Lindenbaum der intuitionistic Logik angesehen werden können, die sie einen speziellen Fall des obengenannten Beispiels macht.
• Jeder völlig bestellte Satz ist ein verteilendes Gitter mit max, wie sich anschließen und Minute, wie sich treffen.
• Die natürlichen Zahlen bilden ein verteilendes Gitter (abgeschlossen als ein Entsprechen-Halbgitter) mit dem größten allgemeinen Teiler, wie sich treffen und kleinstes Gemeinsames Vielfaches, wie sich anschließen.
• In Anbetracht einer positiven ganzen Zahl n bildet der Satz aller positiven Teiler von n ein verteilendes Gitter wieder mit dem größten allgemeinen Teiler, wie sich treffen und kleinstes Gemeinsames Vielfaches, wie sich anschließen. Das ist eine Algebra von Boolean, wenn, und nur wenn n quadratfrei ist.
• Ein Gitter-bestellter Vektorraum ist ein verteilendes Gitter.
• Das Gitter von Young, das durch die Einschließung gegeben ist, die von Diagrammen von Young bestellt, die Teilungen der ganzen Zahl vertreten, ist ein verteilendes Gitter.

Charakteristische Eigenschaften

Verschiedene gleichwertige Formulierungen zur obengenannten Definition bestehen. Zum Beispiel ist L verteilend, wenn, und nur wenn der folgende für alle Elemente x, y, z in L hält:

: (xy) (yz) (zx) = (xy) (yz) (zx).

Ähnlich ist L wenn und nur wenn verteilend

: xz = yz und xz = yz beziehen immer x=y ein.

Image:Diamond Diamantgitter des Gitters svg|The M.

Image:Smallest_nonmodular_lattice_1.svg|The Pentagongitter N.

</Galerie>

Die einfachsten nichtverteilenden Gitter sind M, das "Diamantgitter" und N, das "Pentagongitter". Ein Gitter ist verteilend, wenn, und nur wenn keines seiner Subgitter zur M oder N isomorph ist; ein Subgitter ist eine Teilmenge, die unter dem Entsprechen geschlossen wird und schließen Sie sich Operationen des ursprünglichen Gitters an. Bemerken Sie, dass das nicht dasselbe als seiend eine Teilmenge ist, die ein Gitter laut der ursprünglichen Ordnung ist (aber vielleicht mit der verschiedenen Verbindungslinie und entsprechen Sie Operationen). Weitere Charakterisierungen sind auf die Darstellungstheorie in der folgenden Abteilung zurückzuführen.

Schließlich hat distributivity mehrere andere angenehme Eigenschaften zur Folge. Zum Beispiel ist ein Element eines verteilenden Gitters treffen sich - erst, wenn sich und nur wenn es ist - nicht zu vereinfachend treffen, obwohl der Letztere im Allgemeinen ein schwächeres Eigentum ist. Durch die Dualität ist dasselbe für die Verbindungslinie - erst wahr, und schließen Sie sich - nicht zu vereinfachende Elemente an. Wenn ein Gitter verteilend ist, bildet seine Bedeckung der Beziehung einen Mittelgraphen.

Außerdem ist jedes verteilende Gitter auch modular.

Darstellungstheorie

Die Einführung hat bereits von der wichtigsten Charakterisierung für verteilende Gitter angedeutet: Ein Gitter ist verteilend, wenn, und nur wenn es zu einem Gitter von Sätzen (geschlossen unter der Satz-Vereinigung und Kreuzung) isomorph ist. Diese Satz-Vereinigung und Kreuzung sind tatsächlich im obengenannten Sinn verteilend ist eine elementare Tatsache. Die andere Richtung ist weniger trivial, in dem sie verlangt, dass die Darstellungslehrsätze unten festgesetzt haben. Die wichtige Scharfsinnigkeit von dieser Charakterisierung ist, dass die Identität (Gleichungen), die in allen verteilenden Gittern halten, genau diejenigen ist, die in allen Gittern dessen halten, setzt der obengenannte Sinn ein.

Der Darstellungslehrsatz von Birkhoff für verteilende Gitter stellt fest, dass jedes begrenzte verteilende Gitter zum Gitter von niedrigeren Sätzen des poset seiner Verbindungslinie - erst isomorph ist (gleichwertig: Schließen Sie sich - nicht zu vereinfachend an) Elemente. Das gründet eine Bijektion (bis zum Isomorphismus) zwischen der Klasse des ganzen begrenzten posets und der Klasse aller begrenzten verteilenden Gitter. Diese Bijektion kann zu einer Dualität von Kategorien zwischen Homomorphismus von begrenzten verteilenden Gittern und Eintönigkeitsfunktionen von begrenztem posets erweitert werden. Die Generalisierung dieses Ergebnisses zu unendlichen Gittern verlangt jedoch das Hinzufügen weiterer Struktur.

Ein anderer früher Darstellungslehrsatz ist jetzt als der Darstellungslehrsatz von Stone für verteilende Gitter bekannt (der Name ehrt Marshall Harvey Stone, der es zuerst bewiesen hat). Es charakterisiert verteilende Gitter als die Gitter von offenen Kompaktsätzen von bestimmten topologischen Räumen. Dieses Ergebnis kann sowohl als eine Generalisation des berühmten Darstellungslehrsatzes von Stone für Algebra von Boolean als auch als eine Spezialisierung der allgemeinen Einstellung der Dualität von Stone angesehen werden.

Eine weitere wichtige Darstellung wurde von Hilary Priestley in ihrem Darstellungslehrsatz für verteilende Gitter gegründet. In dieser Formulierung wird ein verteilendes Gitter verwendet, um einen topologischen Raum mit einer zusätzlichen teilweisen Ordnung auf seinen Punkten zu bauen, (völlig geOrdnungstrennt) bestellter Steinraum (oder Raum von Priestley) tragend. Das ursprüngliche Gitter wird als die Sammlung von clopen niedrigere Sätze dieses Raums wieder erlangt.

Demzufolge der Lehrsätze des Steins und Priestleys sieht man leicht, dass jedes verteilende Gitter zu einem Gitter von Sätzen wirklich isomorph ist. Jedoch verlangen die Beweise von beiden Behauptungen Boolean idealer Hauptlehrsatz, eine schwache Form des Axioms der Wahl.

Freie verteilende Gitter

Das freie verteilende Gitter mehr als eine Reihe von Generatoren G kann viel leichter gebaut werden als ein allgemeines freies Gitter. Die erste Beobachtung besteht darin, dass, mit den Gesetzen von distributivity, jeder Begriff, der durch die binären Operationen und auf einer Reihe von Generatoren gebildet ist, in die folgende gleichwertige normale Form umgestaltet werden kann:

: M M... M

wo die M begrenzt ist, trifft sich von Elementen von G. Außerdem, seitdem sowohl sich zu treffen als auch Verbindungslinie sind auswechselbar und idempotent, man kann Duplikate ignorieren und bestellen, und eine Verbindungslinie dessen vertreten trifft sich wie derjenige oben als eine Reihe von Sätzen:

: {N, N..., N},

wo die N begrenzte Teilmengen von G sind. Jedoch ist es noch möglich, dass zwei solche Begriffe dasselbe Element des verteilenden Gitters anzeigen. Das kommt vor, wenn es solche Indizes j und k gibt, dass N eine Teilmenge von N ist. In diesem Fall wird das Entsprechen von N unter dem Entsprechen von N sein, und folglich kann man den überflüssigen Satz N sicher entfernen, ohne die Interpretation des ganzen Begriffes zu ändern. Folglich wird eine Reihe begrenzter Teilmengen von G irredundant genannt, wann auch immer alle seine Elemente N (in Bezug auf die Teilmenge gegenseitig unvergleichbar sind, die bestellt); d. h. wenn es eine Antikette von begrenzten Sätzen bildet.

Jetzt wird das freie verteilende Gitter mehr als eine Reihe von Generatoren G auf dem Satz aller begrenzten irredundant Sätze von begrenzten Teilmengen von G definiert. Die Verbindungslinie von zwei begrenzten Irredundant-Sätzen wird bei ihrer Vereinigung durch das Entfernen aller überflüssigen Sätze erhalten. Ebenfalls ist das Entsprechen von zwei Sätzen S und T die irredundant Version {NM | N in S, M in T}. Die Überprüfung, dass diese Struktur ein verteilendes Gitter mit dem erforderlichen universalen Eigentum ist, ist alltäglich.

Der Zahl der Elemente in freien verteilenden Gittern mit n Generatoren wird durch die Zahlen von Dedekind gegeben. Diese Zahlen wachsen schnell, und sind nur für n  8 bekannt; sie sind

:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788.

Sich die Zahlen zählen oben die Zahl von freien verteilenden Gittern auf, in denen die Gitter-Operationen Verbindungslinien sind und von begrenzten Sätzen von Elementen einschließlich des leeren Satzes trifft. Wenn leer, schließt sich an, und leer trifft sich werden zurückgewiesen, die resultierenden freien verteilenden Gitter haben zwei weniger Elemente; ihre Zahlen der Elemente bilden die Folge

:1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786.

Siehe auch

• Dualitätstheorie für verteilende Gitter
• Geisterhafter Raum

Weiterführende Literatur