Die Mathe-Redaktion - 30.04.2017 07:12 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 353 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Der Satz von Birkhoff über distributive Verbände
Freigegeben von matroid am Mi. 10. Februar 2016 19:00:05
Verfasst von Martin_Infinite -   700 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Der Satz von Birkhoff über distributive Verbände

<math>\begin{tikzcd}[nodes={inner sep=-0.7pt},column sep=22pt,row sep=15pt]
&& \bullet \ar[-]{dr} & \\
& \circledcirc  \ar[-]{ur}  & \bullet \ar[-]{dr} \ar[-]{u} & \circledcirc \\
&\bullet \ar[-]{u} \ar[-]{dr} \ar[-]{ur} & & \circledcirc  \ar[-]{u}\\
\bullet \ar[-]{ur}  & \bullet \ar[-]{dr} \ar[-]{u} & \bullet  \ar[-]{ur} &\\
\circledcirc \ar[-]{u} \ar[-]{dr} \ar[-]{ur} & \ar[-,crossing over]{ul} \circledcirc  \ar[-,crossing over]{ur} & \circledcirc  \ar[-]{u}&\\
& \bullet \ar[-]{u} \ar[-]{ur} & &
\end{tikzcd}</math>

Garrett Birkhoff

Verbände sind algebraische und zugleich ordnungstheoretische Strukturen, die überall in der Mathematik auftauchen. In diesem Artikel wird Birkhoffs Satz über distributive Verbände besprochen, welcher eine Dualität zwischen endlichen partiellen Ordnungen und endlichen beschränkten distributiven Verbänden herstellt. Wir benutzen die Sprache der Kategorientheorie.
 
Zunächst werden ein paar Grundbegriffe der Verbandstheorie vorgestellt. Als Veranschaulichung dienen uns dabei Hasse-Diagramme. Dann wird relativ formal eine kontravariante Adjunktion zwischen der Kategorie <math>\mathsf{BDV}</math> der beschränkten distributiven Verbände und der Kategorie <math>\mathsf{PO}</math> der partiellen Ordnungen hergestellt. Schließlich wird gezeigt, dass die endlichen Objekte jeweils Fixpunkte dieser Adjunktion sind, womit wir die gewünschte Dualität <math>(\mathsf{BDV}_{\mathsf{fin}})^{\mathsf{op}} \simeq \mathsf{PO}_{\mathsf{fin}}</math> erhalten. Wir schauen uns ein paar Beispiele dafür an.

Im Anhang werden freie beschränkte distributive Verbände sowie der Zusammenhang zur Topologie diskutiert.


1. Verbände und Hasse-Diagramme

Die Teilmengen <math>A \subseteq S</math> einer festen Menge <math>S</math> kann man miteinander schneiden und vereinigen; dabei ergeben sich neue Teilmengen, und es gelten gewisse Rechenregeln wie zum Beispiel <math>A \cap A = A</math>, <math>A \cup B = B \cup A</math>, und <math>A \cap (B \cup C) = (A \cap B) \cup (A \cap C)</math>. Bei Verbänden geht es darum, diese Rechenregeln in einem abstrakten Rahmen zu axiomatisieren.
 
Definition. Ein Verband <math>V=(X,\vee,\wedge)</math> besteht aus einer Grundmenge <math>X</math> und zwei binären kommutativen assoziativen Verknüpfungen <math>\vee,\,\wedge: X \times X \to X</math> derart, dass die beiden sog. Absorbtionsgesetze

<math>a \vee (a \wedge b) = a</math>
<math>a \wedge (a \vee b) = a</math>
 
für alle <math>a,b \in X</math> gelten. Der Vollständigkeit halber schreiben wir auch noch aus, was Kommutativität und Assoziativität besagen: Für alle <math>a,b,c \in X</math> gilt:

<math>a \vee b = b \vee a,</math>
<math>a \wedge b = b \wedge a</math>
<math>a \vee (b \vee c) = (a \vee b) \vee c</math>
<math>a \wedge (b \wedge c) = (a \wedge b) \wedge c</math>

Verbände sind demnach algebraische Strukturen. Man nennt <math>|V|:=X</math> auch die unterliegende Menge von <math>V</math>. Man nennt <math>a \vee b</math> die Vereinigung, und <math>a \wedge b</math> den Schnitt von <math>a</math> und <math>b</math>.

Bemerkung. (a) Aus den Absorbtionsgesetzen folgt <math>a \wedge a = a</math> und analog <math>a \vee a = a</math> (Idempotenz), denn es gilt
 
<math>a  \wedge a = a \wedge (a \vee (a \wedge a))=a.</math>

(b) Die Axiome eines Verbands sind völlig symmetrisch; daher ist mit <math>V=(X,\vee,\wedge)</math> auch <math>V^{\mathrm{op}}:=(X,\wedge,\vee)</math> ein Verband.

Definition. Ein beschränkter Verband <math>(X,\vee,\wedge,0,1)</math> besteht aus einem Verband <math>(X,\vee,\wedge)</math> und zwei Elementen <math>0,1 \in X</math> derart, dass

<math>a \vee 0 = a</math>
<math>a \wedge 1 = a</math>
 
für alle <math>a \in X</math> gilt. Ein distributiver Verband ist ein Verband, in dem die Distributivgesetze

<math>a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)</math>
<math>a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)</math>
 
gelten. Tatsächlich lässt sich das eine Distributivgesetz jeweils aus dem anderen herleiten, siehe hier.

Bemerkung. In einem beschränkten Verband gilt <math>a \wedge 0 = (a \vee 0) \wedge 0 = 0</math> und analog <math>a \vee 1 = 1</math> für alle <math>a</math>.
 
Definition. Ein beschränkter distributiver Verband ist ein beschränkter Verband, dessen unterliegender Verband distributiv ist.

Bemerkung. In einem beschränkten distributiven Verband gelten die Gleichungen
 
<math>a \vee \bigwedge_{i \in I} b_i = \bigwedge_{i \in  I} a \vee b_i\medskip\\a \wedge \bigvee_{i \in I} b_i = \bigvee_{i \in I} a \wedge b_i</math>

für endliche Indexmengen <math>I</math>, wobei <math>\bigwedge_{i \in I} b_i</math> (und analog <math>\bigvee_{i \in I} b_i</math>) rekursiv durch <math>\bigwedge_{i \in \emptyset} b_i = 1</math> und <math>\bigwedge_{i \in \{j\} \sqcup I} b = b_j \wedge \bigwedge_{i \in I} b_i</math> definiert ist.

Beispiel. (a) Für jede feste Menge <math>S</math> bilden die Teilmengen von <math>S</math> einen beschränkten distributiven Verband <math>(\mathcal{P}(S),\cup,\cap,\emptyset,S)</math>.

(b) Es gibt den beschränkten distributiven Verband <math>\mathds{B}:=(\{0,1\},\vee,\wedge,0,1)</math>, wobei (notwendigerweise) <math>a \vee 0 = a</math>, <math>a \wedge 0 = 0</math>, <math>a \vee 1 = 1</math>, <math>a \wedge 1 = a</math> für <math>a \in \{0,1\}</math>. Dies entspricht gerade dem Teilmengenverband einer Menge mit nur einem Element.
 
(c) Für eine natürliche Zahl <math>n</math> ist <math>(\text{Teilermenge von } n,\mathrm{kgV},\mathrm{ggT},1,n)</math> ein beschränkter distributiver Verband; wir lassen hierbei nur nichtnegative Teiler zu. Für <math>n=0</math> ergibt sich <math>(\mathds{N},\mathrm{kgV},\mathrm{ggT},1,0)</math>.

(d) Es ist <math>(\mathds{N} \cup \{\infty\},\max,\min,0,\infty)</math> ein beschränkter distributiver Verband.

(e) Für einen <math>K</math>-Vektorraum <math>V</math> hat man den beschränkten Verband der Unterräume von <math>V</math>, wobei hier <math>\wedge</math> der Durchschnitt und <math>\vee</math> die Summe von zwei Unterräumen ist. Dieser Verband ist allerdings etwa für <math>V=K^2</math> nicht distributiv, denn es gilt
 
<math>\langle (1,1) \rangle \cap \bigl(\langle (1,0) \rangle + \langle (0,1) \rangle\bigr) = \langle (1,1)\rangle,\medskip\\\bigl(\langle (1,1) \rangle \cap \langle (1,0) \rangle\bigr) + \bigl(\langle (1,1) \rangle \cap \langle (0,1) \rangle\bigr) = \langle (0,0)\rangle.</math>

Analog ist der Verband der Untergruppen einer festen Gruppe in der Regel nicht distributiv.
 
Definition. Ein Homomorphismus von Verbänden ist eine Abbildung der unterliegenden Mengen, welche <math>\vee</math> und <math>\wedge</math> erhält. Zwischen distributiven Verbänden wählen wir dieselben Homomorphismen. Ein Homomorphismus von beschränkten Verbänden ist eine Abbildung der unterliegenden Mengen, welche <math>0,1,\vee,\wedge</math> erhält. Zwischen beschränkten distributiven Verbänden wählen wir dieselben Homomorphismen. Wir erhalten also vier Kategorien zusammen mit Vergissfunktoren, deren Objekte die (beschränkten) (distributiven) Verbände sind:
 
<math>\begin{tikzcd}[nodes={inner sep=2pt,align=center,text width=9mm},row sep=15pt,column sep=2pt]\phantom{.}& \mathsf{DV} \ar{dr} & \\  \mathsf{BDV} \ar{ur} \ar{dr} &&  \mathsf{V} \\ & \mathsf{BV} \ar{ur} & \end{tikzcd}</math>
 
Wie bei allen algebraischen Kategorien gilt hier: Die Isomorphismen sind genau die bijektiven Homomorphismen.
 
Beispiel. Sei <math>f : S \to T</math> eine Abbildung. Diese induziert dann einen Homomorphismus zwischen den Teilmengenverbänden <math>f^* : (\mathcal{P}(T),\cup,\cap,\emptyset,T) \to (\mathcal{P}(S),\cup,\cap,\emptyset,S)</math>, <math>A \mapsto f^{-1}(A)</math>. Das liegt an den Gleichungen <math>f^{-1}(\emptyset)=\emptyset</math>, <math>f^{-1}(T)=S</math>, <math>f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)</math>, <math>f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)</math>. Die Abbildung <math>f_* : \mathcal{P}(S) \to \mathcal{P}(T)</math>, <math>A \mapsto f_*(A) := \{f(a) : a \in A\}</math> ist allerdings i.A. kein Homomorphismus, denn <math>f_*(S)=T</math> gilt nur für surjektive <math>f</math>, und <math>f_*(A \cap B)=f_*(A) \cap f_*(B)</math> für alle <math>A,B \subseteq S</math> gilt nur für injektive <math>f</math>.

Beispiel. Wenn <math>R</math> ein kommutativer Ring ist, so bilden seine Ideale bezüglich der gewöhnlichen Addition und dem Schnitt von Idealen einen beschränkten Verband <math>I(R)</math>. Wenn <math>R</math> ein Hauptidealring ist, so definiert <math>(R/R^{\times},\mathrm{ggT},\mathrm{kgV},[0],[1]) \to I(R)</math>, <math>[x] \mapsto xR</math> einen Isomorphismus von beschränkten Verbänden. Insbesondere ist dann <math>I(R)</math> distributiv. Es ist <math>I(R)</math> auch dann distributiv, wenn <math>R</math> ein Dedekindring ist: Denn es bettet sich <math>I(R)</math> in das Produkt der Verbände <math>I(R_{\mathfrak{p}})</math> ein, wobei <math>\mathfrak{p}</math> alle Primideale von <math>R</math> durchläuft, und <math>R_{\mathfrak{p}}</math> ist jeweils ein Hauptidealring.
 
Eine wichtige Beobachtung ist dass wir aus jedem Verband eine partielle Ordnung erhalten:
 
Definition. Es sei <math>V=(X,\vee,\wedge)</math> ein Verband. Wir definieren die Relation <math>\leq</math> auf <math>X</math> durch
 
<math>a \leq b \Longleftrightarrow a \vee b = b.</math>

Aus <math>a \vee b = b</math> folgt <math>a \wedge b = a \wedge (a \vee b) = a</math>, und umgekehrt: Aus <math>a \wedge b = a</math> folgt <math>a \vee b = (a \wedge b) \vee b = b</math>. Daher ist also
 
<math>a \leq b \Longleftrightarrow a \wedge b = a.</math>

Man prüft leicht, dass <math>\leq</math> eine reflexive, transitive und antisymmetrische Relation ist. Man erhält also eine partielle Ordnung <math>(X,\leq)</math>, die zu <math>V</math> assoziierte partielle Ordnung. Der Leser sollte sich an dieser Stelle überlegen, wie diese in den oben genannten Beispielen (a)-(e) konkret aussieht.

Die assoziierte partielle Ordnung liefert uns einen Funktor <math>\mathsf{V} \longrightarrow \mathsf{PO},</math> wobei <math>\mathsf{PO}</math> die Kategorie der partiellen Ordnungen zusammen mit monotonen Abbildungen bezeichnet. Dieser Funktor ist nicht voll, denn eine monotone Abbildung muss nicht <math>\vee</math> erhalten. Wenn wir die Kategorie allerdings abändern, so erhalten wir sogar:
 
Satz. (a) Es sei <math>\mathsf{PO}_{\mathsf{sup},\mathsf{inf}}</math> die Kategorie der partiellen Ordnungen, für die jedes Paar von Elementen ein Infimum und ein Supremum besitzt, zusammen mit monotonen Abbildungen, die diese Infima und Suprema erhalten. Dann gibt es einen Isomorphismus von Kategorien <math>\mathsf{PO}_{\mathsf{sup},\mathsf{inf}} \cong \mathsf{V}</math>.
 
(b) Wenn <math>\mathsf{BPO}_{\mathsf{sup},\mathsf{inf}}</math> die Kategorie der partiellen Ordnungen wie oben bezeichnet, für die ebenfalls ein kleinstes und ein größtes Element existiert, zusammen monotonen Abbildungen, die Infima, Suprema und kleinste wie größte Elemente erhalten, so gibt es einen Isomorphismus von Kategorien <math>\mathsf{BPO}_{\mathsf{sup},\mathsf{inf}} \cong \mathsf{BV}</math>.

Beweisskizze. In der zu einem Verband assoziierten partiellen Ordnung gilt <math>\sup(a,b) = a \vee b</math> und <math>\inf(a,b) = a \wedge b</math>. Wir erhalten daher einen Funktor <math>\mathsf{V} \longrightarrow \mathsf{PO}_{\mathsf{sup},\mathsf{inf}}</math>. Den inversen Funktor definiert man so: Ist <math>P \in \mathsf{PO}_{\mathsf{sup},\mathsf{inf}}</math>, so definiere auf der Grundmenge <math>|P|</math> die Struktur eines Verbands durch <math>a \vee b := \sup(a,b)</math> und <math>a \wedge b := \inf(a,b)</math>. Das Absorbtionsgesetz <math>\sup(a,\inf(a,b))=a</math> folgt sofort aus <math>\inf(a,b) \leq a</math>; analog folgt <math>\inf(a,\sup(a,b))=a</math> aus <math>a \leq \sup(a,b)</math>. <math>\checkmark</math>

Aufgrund dieses Satzes findet man in manchen Quellen auch die Definition, dass ein Verband eine partielle Ordnung mit binären Infima und Suprema ist.

Wir können partielle Ordnungen, insbesondere also Verbände, wie folgt graphisch veranschaulichen:

Definition. Das Hasse-Diagramm einer partiellen Ordnung <math>P</math> ist der gerichtete Graph, dessen Knotenmenge <math>|P|</math> ist, und in dem es eine Kante <math>a \to b</math> genau dann gibt, wenn <math>a \neq b</math> und <math>a \leq b</math> gilt, und für jedes <math>x</math> mit <math>a \leq x \leq b</math> schon <math>a=x</math> oder <math>x=b</math> gilt. Üblicherweise zeichnet man lediglich einen ungerichteten Graphen mit der Vereinbarung, dass die nächst größeren Elemente oben liegen. Im beschränkten Fall ist demnach <math>0</math> ganz unten und <math>1</math> ganz oben.
 
Beispiel. Das Hasse-Diagramm des Verbandes der <math>K</math>-Unterräume von <math>K^2</math> sieht für <math>K=\mathds{F}_2</math> so aus:

<math>\begin{tikzcd}[nodes={inner sep=1pt},column sep=20pt,row sep=20pt,font=\small] \phantom{.} & K^2 &\phantom{.} \\ \langle (1,0) \rangle \ar[-]{ur} & \langle (1,1) \rangle \ar[-]{u} & \langle (0,1) \rangle \ar[-]{ul} \\ & \langle (0,0) \rangle \ar[-]{ur} \ar[-]{ul} \ar[-]{u} & \end{tikzcd} </math>

Beispiel. Der Teilerverband von <math>60</math> besitzt das folgende Hasse-Diagramm:

<math>\begin{tikzcd}[column sep=8pt,row sep=18pt,nodes={inner sep=1pt,align=center,text width=10mm}]
&60 && \\
12 \ar[-]{ur} & 20 \ar[-]{u} \ar[-,crossing over]{dr} & 30\ar[-]{ul} \ar[-,crossing over]{dl} & \\
4 \ar[-]{u} \ar[-]{ur} & 6  \ar[-,crossing over]{ul}  & 10\ar[-]{u}  \ar[-]{dr} & 15 \ar[-]{ul}\ar[-,crossing over]{dl} \\
& 2 \ar[-]{u} \ar[-]{ul} \ar[-]{ur} & 3 \ar[-,crossing over]{ul} & 5 \ar[-]{u}  \\
& & 1 \ar[-]{ul} \ar[-]{u} \ar[-]{ur} &  \end{tikzcd}</math>

Allgemeiner ist der Teilerverband einer positiven natürlichen Zahl <math>n = p_1^{k_1} \cdot \dotsc \cdot p_s^{k_s}</math> in Primfaktorzerlegung ein <math>s</math>-dimensionaler "Quader" mit den Seitenlängen <math>k_1,\dotsc,k_s</math>.
 
Bemerkung. Das Hasse-Diagramm eines Verbandes zeichnet sich dadurch aus, dass je zwei Knoten oben und unten (i.W. eindeutig) miteinander verbunden sind. Daher auch der Name Verband. So korrespondieren etwa die folgenden zwei Hasse-Diagramme nicht zu Verbänden:

<math>\begin{tikzcd}[nodes={inner sep=-1pt},column sep=27pt,row sep=27pt] \bullet & \bullet & \bullet  \\ & \bullet \ar[-]{ur} \ar[-]{ul} \ar[-]{u} & \end{tikzcd} \hspace{1cm} \begin{tikzcd}[nodes={inner sep=-1pt},column sep=30pt,row sep=27pt] \bullet & \bullet  \\  \bullet \ar[-]{u} \ar[-]{ur} & \bullet \ar[-]{u} \end{tikzcd}</math>

2. Eine Adjunktion mit Endstücken und Primfiltern

Wir definieren hier Funktoren

<math>E : \mathsf{PO} \longrightarrow \mathsf{BDV}^{\mathsf{op}}\medskip \\ S : \mathsf{BDV}^{\mathsf{op}} \longrightarrow \mathsf{PO} </math>
 
und werden zeigen, dass sie zueinander adjungiert sind.

Definition. Es sei <math>P=(X,\leq)</math> eine partielle Ordnung. Ein Endstück von <math>P</math> sei eine Teilmenge <math>A \subseteq X</math> mit der Eigenschaft:

• Aus <math>a \leq b</math> und <math>a \in A</math> folgt <math>b \in A</math>.
 
Es sind <math>\emptyset</math> und <math>X</math> Endstücke von <math>P</math>. Ferner sind mit je zwei Endstücken <math>A,B</math> auch <math>A \cup B</math> und <math>A \cap B</math> Endstücke von <math>P</math>. Wir erhalten daher einen beschränkten distributiven Verband <math>E(P)</math> der Endstücke von <math>P</math>, als Unterverband des Teilmengenverbandes von <math>X</math>. Wenn <math>f : P \to Q</math> eine monotone Abbildung partieller Ordnungen ist, so ist das <math>f</math>-Urbild eines Endstücks von <math>Q</math> ein Endstück von <math>P</math>. Dies erklärt einen Funktor

<math>E : \mathsf{PO} \longrightarrow \mathsf{BDV}^{\mathsf{op}}.</math>
 
Beispiel. Wir betrachten die partielle Ordnung <math>P</math> mit der Grundmenge <math>\{a,b,c,u,v,w\}</math> und den Relationen <math>v \leq u</math>, <math>w \leq u</math>, <math>u \leq a</math>, <math>u \leq b</math>, <math>u \leq c</math>. Das Hasse-Diagramm dazu ist:

<math>\begin{tikzcd}[nodes={inner sep=-1pt}] \bullet & \bullet & \bullet \\ & \bullet \ar[-]{ul} \ar[-]{ur} \ar[-]{u} \ar[-]{dr} \ar[-]{dl} & \\  \bullet && \bullet \end{tikzcd}</math>
 
Die Endstücke von <math>P</math> sind:
 
<math>\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\},\{a,b,c,u\},</math>
<math>\{a,b,c,u,v\},\{a,b,c,u,w\},\{a,b,c,u,v,w\}.</math>

Das Hasse-Diagramm des Verbandes der Endstücke <math>E(P)</math> ist:

<math>\begin{tikzcd}[nodes={inner sep=-1pt,align=center,text width=25pt},column sep=6pt,row sep=17pt] & \bullet & \\ \bullet \ar[-]{ur} && \bullet \ar[-]{ul} \\ & \bullet \ar[-]{ur} \ar[-]{ul} & \\ & \bullet \ar[-]{u} \ar[-]{dr} &  \\ \bullet \ar[-]{ur} & \bullet \ar[-]{u} \ar[-]{dr} &  \bullet \\ \bullet \ar[-]{u} \ar[-]{ur} \ar[-]{dr} & \bullet \ar[-,crossing over]{ur} \ar[-,crossing over]{ul} & \bullet \ar[-]{u}   \\ & \bullet  \ar[-]{u} \ar[-]{ur}  \end{tikzcd}</math>
 
 
Definition. Es sei <math>V=(X,\vee,\wedge,0,1)</math> ein beschränkter distributiver Verband. Ein Filter von <math>V</math> sei eine Teilmenge <math>J \subseteq X</math> mit den Eigenschaften:

<math>1 \in J</math>
• Aus <math>a \in J</math> und <math>b \in X</math> folgt <math>a \vee b \in J</math>
• Aus <math>a \in J</math> und <math>b \in J</math> folgt <math>a \wedge b \in J</math>
 
Ein solcher Filter heißt Primfilter, wenn zusätzlich gilt:
 
<math>0 \notin J</math> (äquivalent, <math>J \neq X</math>)
• Aus <math>a \vee b \in J</math> folgt <math>a \in J</math> oder <math>b \in J</math>
 
Die durch Inklusion partiell geordnete Menge der Primfilter von <math>V</math> bezeichnen wir mit <math>S(V)</math>; es wird auch auch das Primspektrum von <math>V</math> genannt. Ist <math>f : V \to W</math> ein Homomorphismus von beschränkten distributiven Verbänden, so ist das <math>f</math>-Urbild eines Primfilters von <math>W</math> ein Primfilter von <math>V</math>. Also bekommen wir einen Funktor

<math>S : \mathsf{BDV}^{\mathsf{op}} \longrightarrow \mathsf{PO}.</math>

Satz. Der Funktor <math>E</math> ist linksadjungiert zu <math>S</math>.

Beweis. Wir müssen eine natürliche Bijektion

<math>\hom_{\mathsf{BDV}}(V,E(P)) \cong \hom_{\mathsf{PO}}(P,S(V))</math>

konstruieren, wobei <math>V \in \mathsf{BDV}</math> und <math>P \in \mathsf{PO}</math>. Sei <math>f : V \to E(P)</math> ein Homomorphismus von beschränkten distributiven Verbänden. Das bedeutet, dass <math>f</math> jedem Element <math>x \in |V|</math> der Grundmenge von <math>V</math> ein Endstück <math>f(x) \subseteq |P|</math> von <math>P</math> zuordnet derart, dass die Gleichungen

<math>f(0)=\emptyset</math>, <math>f(1)=|P|</math>, <math>f(x \vee y)=f(x) \cup f(y)</math>, <math>f(x \wedge y) = f(x) \cap f(y)</math>
 
gelten. Für <math>p \in |P|</math> ist dann

<math>\{x \in |V| : p \in f(x)\}</math>
 
ein Primfilter von <math>V</math>, wie man leicht nachrechnet. Nennen wir ihn <math>\widetilde{f}(p)</math>. Für <math>p \leq q</math> gilt dann <math>\widetilde{f}(p) \subseteq \widetilde{f}(q)</math>. Also bekommen wir eine monotone Abbildung <math>\widetilde{f} : P \to S(V)</math>. Ist umgekehrt <math>g : P \to S(V)</math> eine monotone Abbildung, so ist für jedes <math>x \in |V|</math> die Menge

<math>\check{g}(x):=\{p \in |P| : x \in g(p)\}</math>
 
ein Endstück von <math>P</math>. Man prüft außerdem nach, dass <math>\check{g} : V \to E(P)</math> ein Morphismus in <math>\mathsf{BDV}</math> ist; das liegt letztlich daran, dass <math>g</math> nur Primfilter als Werte besitzt. Schließlich überzeugt man sich leicht davon, dass die beiden Konstruktionen zueinander invers sind. <math>\checkmark</math>

Bemerkung. Die Einheit dieser Adjunktion ist durch

<math>\eta_P : P \to S(E(P))</math>, <math>p \mapsto \{A \text{ Endstück von } P : p \in A\}</math>

gegeben. Die Koeinheit dieser Adjunktion (eigentlich ein Morphismus in <math>\mathsf{BDV}^{\mathrm{op}}</math>, aber wir betrachten ihn als einen Morphismus in <math>\mathsf{BDV}</math>) ist ganz ähnlich durch

<math>\varepsilon_V : V \to E(S(V))</math>, <math>x \mapsto \{J \text{ Primfilter von } V : x \in J\}</math>

gebeben.
 
Bemerkung. Ein Endstück einer partiellen Ordnung <math>P</math> kann äquivalent als eine monotone Abbildung <math>P \to (\{0,1\},0 \leq 1)</math> beschrieben werden; man nehme hierzu das Urbild der <math>1</math>. Ein Primfilter eines beschränkten distributiven Verbandes <math>V</math> kann äquivalent als ein Homomorphismus <math>V \to \mathds{B}</math> in <math>\mathsf{BDV}</math> beschrieben werden.

3. Der Satz von Birkhoff

Definition. Ein Verband (bzw. eine partielle Ordnung) heiße endlich, wenn die unterliegende Menge endlich ist.

Lemma. Sei <math>V=(X,\vee,\wedge,0,1)</math> ein endlicher beschränkter distributiver Verband. Dann hat jeder Filter von <math>V</math> die Form <math>{\uparrow} x := \{y \in X : x \leq y\}</math> für ein eindeutiges <math>x \in X</math>.

Beweis. Es ist klar, dass <math>{\uparrow}x</math> stets ein Filter ist. Nun sei umgekehrt <math>J \subseteq X</math> ein Filter von <math>V</math>. Setze <math>x = \bigwedge_{y \in J} y = \inf(J)</math>; dieses Element können wir bilden, weil <math>J</math> endlich ist. Wir behaupten <math>J= {\uparrow} x</math>. Die Inklusion <math>J\subseteq {\uparrow}x</math> folgt aus der Definition von <math>x</math>. Sei umgekehrt <math>z \in {\uparrow}x</math>, also <math>x \leq z</math>. Es folgt <math>z = z \vee x = \bigwedge_{y \in J} (z \vee y)</math>. Weil <math>J</math> ein Filter ist, gilt <math>z \vee y \in J</math> für alle <math>y \in J</math>. Weil <math>J</math> ein Filter ist, folgt weiter <math>z=\bigwedge_{y \in J} (z \wedge y) \in J</math>, wie gewünscht. Die Eindeutigkeit folgt aus <math>x = \inf({\uparrow}x)</math>. <math>\checkmark</math>
 
Lemma. Sei <math>V=(X,\vee,\wedge,0,1)</math> ein beschränkter distributiver Verband. Sei <math>x \in X</math>. Die folgenden Bedingungen sind äquivalent:
<math>{\uparrow} x</math> ist ein Primfilter von <math>V</math>.
<math>x \neq 0</math> und aus <math>x \leq y \vee z</math> folgt <math>x \leq y</math> oder <math>x \leq z</math>.
<math>x \neq 0</math> und aus <math>x = y \vee z</math> folgt <math>x = y</math> oder <math>x = z</math>.

Definition. Ist eine der äquivalenten Bedingungen des Lemmas erfüllt, so nennen wir <math>x</math> irreduzibel (bezüglich <math>\vee</math>).

Beweis. Dass <math>{\uparrow}x</math> ein Primfilter ist, bedeutet <math>0 \notin {\uparrow}x</math>, d.h. <math>x \neq 0</math>, und dass aus <math>y \vee z \in {\uparrow}x</math> schon <math>y \in {\uparrow}x</math> oder <math>z \in {\uparrow}x</math> folgt; das ist gerade die zweite Bedingung. Aus ihr folgt offenbar die dritte Bedingung. Ist umgekehrt die dritte Bedingung erfüllt und <math>x \leq y \vee z</math>, so folgt <math>x = (y \vee z) \wedge x = (y \wedge x) \vee (z \wedge x)</math>, also nach Annahme <math>x = y \wedge x</math> oder <math>x = z \wedge x</math>, d.h. <math>x \leq y</math> oder <math>x \leq z</math>. <math>\checkmark</math>

Bemerkung. Es gilt <math>x \leq y</math> genau dann, wenn <math>{\uparrow}y \subseteq {\uparrow}x</math> gilt. Wenn also <math>V</math> endlich ist und <math>\mathrm{Irr}(V)</math> die partielle Ordnung der irreduziblen Elemente von <math>V</math> bezeichnet, so ist <math>x \mapsto {\uparrow}x</math> ein Isomorphismus

<math>\mathrm{Irr}(V)^{\mathrm{op}} \xrightarrow{~\cong~} S(V).</math>
 
Dabei bedeutet das <math>\mathrm{op}</math> im Exponenten, das wir die Ordnung umgedreht haben. Der inverse Isomorphismus bildet ein Primfilter <math>J</math> auf <math>\inf(J)</math> ab. Wenn <math>f : V \to W</math> ein Homomorphismus zwischen zwei endlichen beschränkten distributiven Verbänden ist, so lässt sich die zu <math>f^{-1}: S(W) \to S(V)</math> gehörige Abbildung <math>\mathrm{Irr}(W)^{\mathrm{op}} \to \mathrm{Irr}(V)^{\mathrm{op}}</math> durch <math>x \mapsto \inf\bigl(f^{-1}({\uparrow}x})\bigr)</math> beschreiben. Hieran wird ersichtlich, dass es besser ist, mit Primfiltern zu arbeiten, weil sich diese einfacher entlang von Homomorphismen zurückziehen lassen. Im unendlichen Fall wäre nicht einmal klar, ob <math>\mathrm{Irr}(-)</math> funktoriell ist.
 
Satz (Satz von Birkhoff).

(1) Wenn <math>P</math> eine endliche partielle Ordnung ist, dann ist <math>E(P)</math> ein endlicher beschränkter distributiver Verband, und die Einheit <math>\eta : P \to S(E(P))</math> ist ein Isomorphismus.

(2) Wenn <math>V</math> ein endlicher beschränkter distributiver Verband ist, dann ist <math>S(V)</math> eine endliche partielle Ordnung, und die Koeinheit <math>\varepsilon : V \to E(S(V))</math> ist ein Isomorphismus.

(3) Wenn <math>\mathsf{BDV}_{\mathsf{fin}}</math> die Kategorie der endlichen beschränkten distributiven Verbände und <math>\mathsf{PO}_{\mathsf{fin}}</math> die Kategorie der endlichen partiellen Ordnungen ist, so induzieren <math>S</math> und <math>E</math> eine Äquivalenz von Kategorien

<math>(\mathsf{BDV}_{\mathsf{fin}})^{\mathrm{op}} \simeq \mathsf{PO}_{\mathsf{fin}}.</math>

Beweis. (1) Unter Benutzung des Isomorphismus <math>S(V) \cong \mathrm{Irr}(V)^{\mathrm{op}}</math> für <math>V=E(P)</math> reicht es zu zeigen, dass die Abbildung <math>P \to \mathrm{Irr}(E(P))^{\mathrm{op}}</math>, <math>p \mapsto \inf( \{A \text{ Endstück von } P : p \in A\} )={\uparrow} p</math> ein Isomorphismus ist, wobei <math>{\uparrow} p := \{q \in |P| : p \leq q\}</math>. Offenbar gilt <math>p \leq p' \Leftrightarrow  {\uparrow} p' \subseteq {\uparrow} p</math>. Sei nun <math>A</math> ein irreduzibles Endstück von <math>P</math>. Wegen <math>A = \bigcup_{p \in A} {\uparrow} p</math> gibt es dann ein <math>p \in A</math> mit <math>A = {\uparrow} p</math>. Das war zu zeigen.
 
(2) Unter Benutzung des Isomorphismus <math>S(V) \cong \mathrm{Irr}(V)^{\mathrm{op}}</math> reicht es zu zeigen, dass <math>V \to E(\mathrm{Irr}(V)^{\mathrm{op}})</math>, <math>x \mapsto \{p \in \mathrm{Irr}(V): p \leq x\}</math> ein Isomorphismus ist. Für den Beweis bemerken wir zunächst, dass sich jedes <math>x \in |V|</math> als

<math>\displaystyle x = p_1 \vee \dotsc \vee p_n</math>
 
mit <math>p_i \in \mathrm{Irr}(V)</math> schreiben lässt (wobei der Fall <math>x=0</math> durch <math>n=0</math> abgedeckt ist). Denn wenn <math>x</math> irreduzibel oder <math>x=0</math> ist, ist dies sicherlich der Fall, und andernfalls ist <math>x = y \vee z</math> mit <math>y,z \neq x</math>. Fahren wir nun mit <math>y,z</math> genauso fort und beachten, dass wir in einer <math>\vee</math>-Zerlegung kein Element doppelt aufführen müssen, so folgt mit der Endlichkeit von <math>V</math> die Zwischenbehauptung. Daraus folgt

<math>\displaystyle  x = \bigvee_{p \,\in\, \mathrm{Irr}(V),\, p \leq x} \, p.</math>

Dies zeigt schon einmal, dass unsere Abbildung injektiv, ja sogar eine Ordnungseinbettung ist. Sei umgekehrt <math>A</math> ein Endstück von <math>\mathrm{Irr}(V)^{\mathrm{op}}</math>, und setze

<math>\displaystyle x := \bigvee_{p \,\in A} \, p.</math>
 
Jedes <math>p \in A</math> ist dann ein irreduzibles Element mit <math>p \leq x</math>. Ist umgekehrt <math>q \leq x</math> irreduzibel, so folgt <math>q \in A</math>: Aus der Irreduzibilität von <math>q</math> (und der Definition von <math>x</math>) folgt, dass es ein <math>p \in A</math> gibt mit <math>q \leq p</math>. Weil aber <math>A</math> ein Endstück bezüglich der umgekehrten partiellen Ordnung ist, folgt hieraus <math>q \in A</math>. Damit ist die Bijektivität der Abbildung <math>x \mapsto \{p \in \mathrm{Irr}(V): p \leq x\}</math> gezeigt.
 
(3) Dies folgt aus (1) und (2). <math>\checkmark</math>

Korollar. Jeder endliche beschränkte distributive Verband ist zum Verband der Endstücke einer endlichen partiellen Ordnung isomorph, nämlich der umgedrehten partiellen Ordnung ihrer irreduziblen Elemente.

Definieren wir ein Anfangsstück einer partiellen Ordnung <math>P</math> als ein Endstück in <math>P^{\mathrm{op}}</math>, so kann man das Korollar auch so formulieren:

Korollar. Jeder endliche beschränkte distributive Verband ist zum Verband der Anfangsstücke einer endlichen partiellen Ordnung isomorph, nämlich der partiellen Ordnung ihrer irreduziblen Elemente.

Beispiel. Betrachte den Teilmengenverband einer festen endlichen Menge <math>S</math>. Die irreduziblen Elemente sind gerade die einelementigen Mengen <math>\{s\}</math>, <math>s \in S</math>. Die partielle Ordnung ist hier trivial; nur gleiche Elemente stehen in Relation. Das hat zur Folge, dass jede Menge von irreduziblen Elementen ein Anfangsstück ist; wir erhalten also wieder die Teilmengen von <math>S</math>.

Beispiel. Im Teilerverband einer natürlichen Zahl <math>n \geq 1</math> sind die irreduziblen Elemente gerade die Primzahlpotenzen, die <math>n</math> teilen. Diese sind durch Teilbarkeit partiell geordnet. Jeder Teiler <math>d|n</math> liefert ein Anfangsstück in dieser partiellen Ordnung, bestehend aus denjenigen Primzahlpotenzen, die <math>d</math> teilen. Umgekehrt besteht jedes Anfangsstück aus Primzahlpotenzen <math>p^0,p^1,\dotsc,p^{k_p}</math> (die <math>n</math> teilen) bis zu einem gewissen Exponenten <math>k_p</math>, für jede Primzahl <math>p</math>, womit wir 1:1 den Teiler <math>d=\prod_{p \text{ prim}} \, p^{k_p}</math> von <math>n</math> assoziieren können.

Beispiel. Betrachten wir den Verband, der zum Hasse-Diagramm
 
<math>\begin{tikzcd}[nodes={inner sep=-0.5pt,align=center,text width=7pt},column sep=35pt,row sep=20pt]
&& \bullet \ar[-]{dr} & \\
&\bullet \ar[-]{ur}  & \bullet \ar[-]{dr} \ar[-]{u} & \bullet \\
&\bullet \ar[-]{u} \ar[-]{dr} \ar[-]{ur} & & \bullet \ar[-]{u}\\
\bullet \ar[-]{ur}  & \bullet \ar[-]{dr} \ar[-]{u} & \bullet  \ar[-]{ur} &\\
\bullet \ar[-]{u} \ar[-]{dr} \ar[-]{ur} & \ar[-,crossing over]{ul} \bullet \ar[-,crossing over]{ur} & \bullet \ar[-]{u}&\\
& \bullet \ar[-]{u} \ar[-]{ur} & &
\end{tikzcd}</math>
 
korrespondiert. Er ist distributiv und beschränkt. Die irreduziblen Elemente sind:
 
<math>\begin{tikzcd}[nodes={inner sep=-0.5pt,align=center,text width=7pt},column sep=35pt,row sep=20pt]
&& \bullet \ar[-]{dr} & \\
& \circledcirc  \ar[-]{ur}  & \bullet \ar[-]{dr} \ar[-]{u} & \circledcirc \\
&\bullet \ar[-]{u} \ar[-]{dr} \ar[-]{ur} & & \circledcirc  \ar[-]{u}\\
\bullet \ar[-]{ur}  & \bullet \ar[-]{dr} \ar[-]{u} & \bullet  \ar[-]{ur} &\\
\circledcirc \ar[-]{u} \ar[-]{dr} \ar[-]{ur} & \ar[-,crossing over]{ul} \circledcirc  \ar[-,crossing over]{ur} & \circledcirc  \ar[-]{u}&\\
& \bullet \ar[-]{u} \ar[-]{ur} & &
\end{tikzcd}</math>
 
Die partielle Ordnung der irreduziblen Elemente besitzt demnach das folgende Hasse-Diagramm:

<math>\begin{tikzcd}[nodes={inner sep=-1pt},column sep=40pt,row sep=35pt] && \bullet \\ & \bullet \ar[-]{dr} & \bullet \ar[-]{u} \\ \bullet \ar[-]{ur} & \bullet \ar[-,crossing over]{ur} \ar[-]{u} & \bullet  \ar[-]{u} \end{tikzcd}</math>
 
Man kann sich nun graphisch überlegen, dass die Anfangsstücke gerade den ursprünglichen Verband liefern.
 
Eine nützliche Anwendung des Satzes von Birkhoff ist:

Korollar. Sobald eine Identität in der Sprache der distributiven Verbände für Teilmengenverbände gilt, so gilt sie für jeden beschränkten distributiven Verband. Es reicht sogar aus, sie in <math>\mathds{B}</math> zu prüfen.

Beispiel. Wir betrachten die Gleichung

<math>(a \wedge b) \vee (a \wedge c) \vee (b \wedge c) = (a \vee b) \wedge (a \vee c) \wedge (b \vee c)</math>

und behaupten, dass diese in jedem beschränkten distributiven Verband gilt. Das lässt sich aus den Axiomen folgern und ist auch nicht besonders schwer. Aber wir können es auch so machen: Wir betrachten den von <math>a,b,c</math> erzeugten Unterverband. Dieser ist endlich (vgl. Anhang B). Er bettet sich also nach dem Satz von Birkhoff in den Teilmengenverband einer endlichen Menge <math>S</math> ein. Dieser ist aber isomorph zum Produktverband (mit komponentenweisen Verknüpfungen) <math>\prod_{s \in S} \mathds{B}</math>. Daher reicht es, die Aussage im Verband <math>\mathds{B}</math> zu prüfen, was wiederum einfach durch Ausprobieren oder durch "logisches Argumentieren" geschehen kann, wobei hier <math>0</math> als "falsch" und <math>1</math> als "wahr" interpretiert werden muss. Im vorliegenden Fall reicht auch ein Venn-Diagramm:

<math>\begin{tikzpicture}[scale=1.3]
\definecolor{hellgruen}{rgb}{0.6,0.95,0.3}
\def\firstcircle{(0,0) circle [radius=8mm]}
\def\secondcircle{(0.5,0.866) circle [radius=8mm]}
\def\thirdcircle{(1,0) circle [radius=8mm]}
\begin{scope}
\clip \firstcircle;
\fill[hellgruen] \secondcircle;
\fill[hellgruen] \thirdcircle;
\end{scope}
\begin{scope}
\clip \secondcircle;
\fill[hellgruen] \thirdcircle;
\end{scope}
\draw [thin] \firstcircle;
\draw [thin]  \secondcircle;
\draw [thin] \thirdcircle;
\draw node at (-0.2,-0.2) {$a$};
\draw node at (1.2,-0.2) {$b$};
\draw node at (0.5,1.066) {$c$};    
\end{tikzpicture}</math>

Sobald wir eine Identität für allgemeine Verbände bewiesen haben, können wir sie natürlich auf konkrete Verbände anwenden. Zum Beispiel erhalten wir

<math>\mathrm{kgV}(\mathrm{ggT}(a,b),\mathrm{ggT}(a,c),\mathrm{ggT}(b,c))=\mathrm{ggT}(\mathrm{kgV}(a,b),\mathrm{kgV}(a,c),\mathrm{kgV}(b,c))</math>
 
für natürliche Zahlen <math>a,b,c</math>.

Bemerkung. Nach dem Satz von Birkhoff ist das Koprodukt von zwei endlichen beschränkten distributiven Verbänden <math>V,W</math> gegeben durch <math>E(S(V) \times S(W))</math>.
 
Bemerkung. Neben der Birkhoff-Dualität gibt es noch eine Reihe weiterer Dualitäten für Verbände, zum Beispiel die Stone-Dualität, die Priestley-Dualität und die Heyting-Dualität. Siehe etwa Dualities in Lattice Theory von Patrick J. Morandi sowie Wikipedia.

Anhang A. Topologische Räume

Definition. Eine Präordnung <math>(X,\leq)</math> ist eine Menge <math>X</math> zusammen mit einer reflexiven, transitiven Relation <math>\leq</math>.
 
Im Gegensatz zu einer partiellen Ordnung ist also keine Antisymmetrie gefordert. Ein typisches Beispiel ist <math>(\mathds{Z},|)</math>. Sei nun <math>\mathsf{PrO}</math> die Kategorie der Präordnungen zusammen mit monotonen Abbildungen.
 
Satz. Es gibt einen Isomorphismus von Kategorien <math>\mathsf{PrO}_{\mathsf{fin}} \cong \mathsf{Top}_{\mathsf{fin}}</math>.

Beweisskizze. Sei <math>P</math> eine endliche Präordnung. Dann ist <math>T(P):=(|P|,|E(P)|)</math> ein endlicher topologischer Raum (d.h. wir nehmen als Grundmenge diejenige von <math>P</math> und als offene Mengen die Endstücke von <math>P</math>). Jede monotone Abbildung ist dann stetig. Ist umgekehrt <math>T</math> ein endlicher topologischer Raum, so ist <math>P(T):=(|T|,\leq)</math> eine endliche Präordnung, wobei per Definition <math>x \leq y \Leftrightarrow x \in \overline{\{y\}}</math>. Jede stetige Abbildung ist dann monoton. Dies erklärt zwei zueinander inverse Funktoren. <math>\checkmark</math>

Definition. Ein topologischer Raum <math>T</math> heißt <math>\definecolor{roti}{rgb}{0.63,0,0}\textcolor{roti}{T_0}</math>-Raum, wenn aus <math>\overline{\{x\}}=\overline{\{y\}}</math> stets <math>x=y</math> folgt.
 
Das heißt also gerade, dass die zugehörige Präordnung eine partielle Ordnung ist. Aus dem Satz erhalten wir daher <math>\mathsf{PO}_{\mathsf{fin}} \cong \mathsf{Top}_{\mathsf{fin},T_0}</math>. Setzen wir das mit der Äquivalenz aus dem Satz von Birkhoff zusammen:
 
Korollar. Es gibt eine Äquivalenz von Kategorien <math>(\mathsf{BDV}_{\mathsf{fin}})^{\mathsf{op}} \simeq \mathsf{Top}_{\mathsf{fin},T_0}</math>.

Dabei wird ein endlicher <math>T_0</math>-Raum auf den Verband der offenen Teilmengen (versehen mit <math>\cup</math> und <math>\cap</math>) geschickt. Jeder endliche beschränkte distributive Verband ist also zu einem solchen Verband isomorph.

Bemerkung. Allgemeiner kann man zeigen, dass jeder beschränkte distributive Verband zum Verband der kompakt-offenen Teilmengen eines spektralen Raumes isomorph ist, und dass dabei sogar eine Äquivalenz von Kategorien <math>\mathsf{BDV}^{\mathrm{op}} \simeq \mathsf{Spek}</math> entsteht (Stone Dualität für distributive Verbände). Dabei heißt ein topologischer Raum spektral, wenn er zum Spektrum eines kommutativen Ringes homöomorph ist. Dies ist u.a. äquivalent dazu, dass sich der Raum als gerichteter Limes von endlichen <math>T_0</math>-Räumen schreiben lässt. Wenn man das weiß, folgt <math>\mathsf{BDV}^{\mathrm{op}} \simeq \mathsf{Spek}</math> leicht aus dem endlichen Fall. Hieraus ergibt sich als Spezialfall die klassische Stone-Dualität für sog. boolesche Verbände.

Anhang B. Freie beschränkte distributive Verbände

Weil beschränkte distributive Verbände algebraische Strukturen sind, können wir insbesondere von freien Strukturen dieses Typs sprechen. Bloß wie sehen diese konkret aus? Birkhoffs Satz sagt uns, dass wir (im endlichen Fall) nur eine geeignete partielle Ordnung finden und dann den Verband der Endstücke betrachten müssen.
 
Satz. Sei <math>S</math> eine endliche Menge und <math>P</math> die partielle Ordnung der Teilmengen von <math>S</math> (bez. Inklusion). Dann ist <math>E(P)</math> der freie beschränkte distributive Verband auf <math>S.</math>

Beweis. Für <math>s \in S</math> sei <math>X_s = \{T \subseteq S : s \in T\}</math>. Dann gilt <math>X_s \in |E(P)|</math>. Wir möchten zeigen, dass für jeden beschränkten distributiven Verband <math>V</math> die Abbildung

<math>\alpha : \hom(E(P),V) \to |V|^S,\, f \mapsto (f(X_s))_{s \in S}</math>

bijektiv ist; denn dies ist gerade die Aussage, dass <math>E(P)</math> frei auf den Erzeugern <math>(X_s)_{s \in S}</math> ist. Wir zeigen zunächst die Injektivität von <math>\alpha</math>. Dafür reicht es zu zeigen, dass <math>(X_s)_{s \in S}</math> ein Erzeugendensystem von <math>E(P)</math> ist. Sei dazu <math>A</math> ein Endstück von <math>P</math>. Dann ist <math>A = \bigcup_{T \in A} {\uparrow}T</math>. Für jedes <math>T \subseteq S</math> ist ferner <math>{\uparrow}T = \bigcap_{t \in T} X_t</math>. Das zeigt, dass <math>(X_s)_{s \in S}</math> ein Erzeugendensystem ist. Es sagt uns zugleich, wie wir die Surjektivität von <math>\alpha</math> zeigen können:

Ist <math>(a_s)_{s \in S} \in |V|^S</math>, so definiere <math>f : E(P) \to V</math> durch

<math>\displaystyle f(A) := \bigvee_{T \in A} \bigwedge_{t \in T} a_t.</math>

Dann gilt <math>f(X_s)=\bigvee_{T \subseteq S,\, s \in T} \bigwedge_{t \in T} a_t = a_s</math>. Man kann nun nachrechnen, dass <math>f</math> ein Homomorphismus ist. <math>\checkmark</math>

Korollar. Jeder endlich-erzeugte beschränkte distributive Verband ist endlich.

Bemerkung. Wenn <math>S</math> unendlich ist, so erhält man den freien beschränkten distributiven Verband auf <math>S</math> durch eine Kolimesbildung aus dem endlichen Fall.

Bemerkung. Die Elemente von <math>|E(P)|</math> lassen sich auch anders beschreiben. Wenn wir nämlich ein Endstück von Teilmengen von <math>S</math> haben, so schauen wir uns die minimalen darin enthaltenden Teilmengen an. Diese bilden dann eine Antikette, d.h. sind bezüglich der Inklusion paarweise nicht miteinander vergleichbar. Ist umgekehrt eine Antikette von Teilmengen von <math>S</math> gegeben, so nehmen wir ihre Obermengen hinzu, und enthalten somit ein Endstück. (Diese Korrespondenz zwischen Endstücken und Antiketten funktioniert für jede endliche partielle Ordnung.) So ist zum Beispiel für <math>S=\{1,2,3\}</math> das Endstück <math>\{\{1\},\{1,2\},\{1,3\},\{1,2,3\},\{2,3\}\}</math> assoziiert mit der Antikette <math>\{\{1\},\{2,3\}\}</math>. Wir können das Endstück auch als <math>X_1 \vee (X_2 \wedge X_3)</math> schreiben. Allgemeiner korrespondert eine Antikette <math>\{A_1,\dotsc,A_n\}</math> von Teilmengen von <math>S</math> zu <math>X_{A_1} \vee \dotsc \vee X_{A_n}</math>, wobei wir <math>X_A := \bigwedge_{s \in A} X_s</math> setzen.
 
Beispiel. Der freie beschränkte distributive Verband auf <math>S=\{1,2,3\}</math> besteht aus <math>20</math> Elementen. Zur Veranschaulichung das Hasse-Diagramm:
 
<math>\begin{tikzcd}[nodes={inner sep=1.5pt},column sep=0pt,row sep=35pt,font=\small,nodes={align=center,text width=23mm}]
 & & 1 && \\
& & X_1 {\vee} X_2 {\vee} X_3 \ar[-]{u} & &  \\
& X_1 {\vee} X_2 \ar[-]{ur} & X_1 {\vee} X_3 \ar[-]{u} \ar[-]{dr} & X_2 {\vee} X_3 \ar[-]{ul} \ar[crossing over,-]{dl} & \\
& X_1 {\vee}  (X_2 {\wedge} X_3) \ar[-]{u} \ar[-]{ur} & X_2 {\vee}  (X_1 {\wedge} X_3)  \ar[-,crossing over]{ul} & X_3 {\vee} (X_1 {\wedge} X_3) \ar[-]{u} & \\
X_1 \ar[-]{ur} && A \ar[-]{u} \ar[-]{ur} \ar[-]{ul} \ar[-]{dr} & X_2 \ar[-,crossing over]{ul} \ar[-,crossing over]{dl}& X_3 \ar[-]{ul}\\
& X_1 {\wedge} (X_2 {\vee} X_3) \ar[-]{ul} \ar[-]{ur} & X_2 {\wedge} (X_1 {\vee} X_3) \ar[-]{u} \ar[-]{dr} & X_3 {\wedge} (X_1 {\vee} X_2)  \ar[-]{ur} & \\
& X_1 {\wedge} X_2 \ar[-]{u} \ar[-]{ur} & X_1 {\wedge} X_3 \ar[-,crossing over]{ul} \ar[-,crossing over]{ur} & X_2 {\wedge} X_3 \ar[-]{u}  & \\
&& X_1 {\wedge} X_2 {\wedge} X_3 \ar[-]{u} \ar[-]{ul} \ar[-]{ur} && \\
&& 0 \ar[-]{u} &&
\end{tikzcd}</math>
 
<math>A := (X_1 {\wedge} X_2) \vee (X_1 {\wedge} X_3) \vee (X_2 {\wedge} X_3) = (X_1 {\vee}  X_2) \wedge  (X_1 {\vee}  X_3) \wedge (X_2 {\vee} X_3)</math>

Bemerkung. Die Anzahl der Elemente des freien beschränkten distributiven Verbands auf <math>\{1,\dotsc,n\}</math> heißt die Dedekind-Zahl <math>M(n)</math>. Dies ist zugleich die Anzahl der Antiketten von Teilmengen von <math>\{1,\dotsc,n\}</math>. Die einzigen bisher bekannten Werte sind:

<math>\begin{tabular}{l|l}
$n$ & $M(n)$ \\ \hline
0 & 2 \\
1 & 3 \\
2 & 6\\
3 & 20\\
4 & 168 \\
5 & 7581 \\
6 & 7828354 \\
7 & 2414682040998 \\
8 & 56130437228687557907788
\end{tabular}</math>

Diese Zahlen wachsen also erstaunlich schnell. Die Zahl <math>M(9)</math> hat man noch nicht exakt bestimmen können.

Quellen

Federico Ardila: Enumerative Combinatorics (Lecture 23)
George Grätzer: General Lattice Theory
Kamala Krithivasan: Lattices
Patrick Morandi: Dualities in Lattice Theory
Wikipedia: Birkhoff's representation theorem
Wikipedia: Dedekind number
Wikipedia: Distributive Lattice
Wikipedia: Duality theory for distributive lattices
Wikipedia: Filter (mathematics)
Wikipedia: Hasse-Diagramm
Wikipedia: Lattice (order theory)


Ich bedanke mich bei meinem Korrekturleser KidinK.


Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
Der Satz von Birkhoff über distributive Verbände [von Martin_Infinite]  
begin{tikzcd}[nodes={inner sep=-0.7pt},column sep=22pt,row sep=15pt] && bullet ar[-]{dr} & & circledcirc ar[-]{ur} & bullet ar[-]{dr} ar[-]{u} & circledcirc &bullet ar[-]{u} ar[-]{dr} ar[-]{ur} & & circledcirc ar[-]{u} bullet ar[-]{ur} & b
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 700
 
Aufrufstatistik des Artikels
Insgesamt 7 externe Besuche zwischen 2017.04 und 2017.04 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com457.1%57.1 %
http://images.google.de114.3%14.3 %
http://google.at114.3%14.3 %
http://google.ch114.3%14.3 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 3 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.04.05-2017.04.27 (3x)https://www.google.de/

[Seitenanfang]

" Mathematik: Der Satz von Birkhoff über distributive Verbände" | 4 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

Re: Der Satz von Birkhoff über distributive Verbände
von Slash am Mi. 10. Februar 2016 19:48:49


Das Foto von Garrett Birkhoff sieht deinem Avatar in Sachen Kopfhaltung, Mimik und Kleidung zum Verwechseln ähnlich. wink

Die Dedekind-Zahlen finden sich auch in der OEIS unter A000372.

Der gesamte Artikel ist für mich inhaltlich zu hoch, aber diese Dedekind-Zahlen haben mich sofort fasziniert. Allem voran der Umstand, dass bisher erst neun davon bekannt sind. Auf der Wikipedia-Seite findet sich eine Summenformel zu deren Berechnung, die zwar richtig ist, aber leider keinen praktischen Nutzen hat. Der polnische Mathematiker Andrzej Kisielewicz hatte sie 1988 auf der "Arbeitstagung Allgemeine Algebra" in Bern vorgestellt. Der Grund für die Nutzlosigkeit: Die Anzahl der Antiketten steigt derart schnell, dass selbst die modernsten Supercomputer mit der Berechnung überfordert sind. Schon für <math>M(5)=7581</math> muss die äußere Klammer der Formel mehr als <math>10^{12}</math>-mal ausgewertet werden.

Quelle: "Diskrete Mathematik: Geordnete Mengen" von Bernhard Ganter, Kapitel 4.4 Ketten und Antiketten von Mengen.

Gruß, Slash

 [Bearbeiten]

Re: Der Satz von Birkhoff über distributive Verbände
von KidinK am Mi. 10. Februar 2016 20:04:57


Da auch für mich die aktuelle Version mit den vielen Diagrammen neu ist, möchte ich diese hier in aller Öffentlichkeit loben, was ich hiermit tue.

Liebe Grüße,
KidinK

 [Bearbeiten]

Re: Der Satz von Birkhoff über distributive Verbände
von JoeM am Do. 11. Februar 2016 00:30:08


Hallo Slash,

SUPER BILD !

das erinnert mich an die >Ähnlichkeitstheorie< von Reynolds !   smile

viele Grüße

JoeM

 [Bearbeiten]

Re: Der Satz von Birkhoff über distributive Verbände
von Marbin am Do. 11. Februar 2016 18:56:30


Ich habe wenig Ahnung von distributiven Verbänden, finde aber die Latex-Abbildungen sehr ästhetisch und inspirierend. Zumindest die Defizite, die ich hier habe, werde ich nachholen.

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]