Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Frei

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 S eine endliche Menge und P die partielle Ordnung der Teilmengen von S (bez. Inklusion). Dann ist E(P) der freie beschränkte distributive Verband auf S.
Beweis. Für s \in S sei X_s = \{T \subseteq S : s \in T\}. Dann gilt X_s \in |E(P)|. Wir möchten zeigen, dass für jeden beschränkten distributiven Verband V die Abbildung \alpha : \hom(E(P),V) \to |V|^S,\, f \mapsto (f(X_s))_{s \in S} bijektiv ist; denn dies ist gerade die Aussage, dass E(P) frei auf den Erzeugern (X_s)_{s \in S} ist. Wir zeigen zunächst die Injektivität von \alpha. Dafür reicht es zu zeigen, dass (X_s)_{s \in S} ein Erzeugendensystem von E(P) ist. Sei dazu A ein Endstück von P. Dann ist A = \bigcup_{T \in A} {\uparrow}T. Für jedes T \subseteq S ist ferner {\uparrow}T = \bigcap_{t \in T} X_t. Das zeigt, dass (X_s)_{s \in S} ein Erzeugendensystem ist. Es sagt uns zugleich, wie wir die Surjektivität von \alpha zeigen können: Ist (a_s)_{s \in S} \in |V|^S, so definiere f : E(P) \to V durch \displaystyle f(A) := \bigvee_{T \in A} \bigwedge_{t \in T} a_t. Dann gilt f(X_s)=\bigvee_{T \subseteq S,\, s \in T} \bigwedge_{t \in T} a_t = a_s. Man kann nun nachrechnen, dass f ein Homomorphismus ist. \checkmark
Korollar. Jeder endlich-erzeugte beschränkte distributive Verband ist endlich.
Bemerkung. Wenn S unendlich ist, so erhält man den freien beschränkten distributiven Verband auf S durch eine Kolimesbildung aus dem endlichen Fall. Bemerkung. Die Elemente von |E(P)| lassen sich auch anders beschreiben. Wenn wir nämlich ein Endstück von Teilmengen von S 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 S 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 S=\{1,2,3\} das Endstück \{\{1\},\{1,2\},\{1,3\},\{1,2,3\},\{2,3\}\} assoziiert mit der Antikette \{\{1\},\{2,3\}\}. Wir können das Endstück auch als X_1 \vee (X_2 \wedge X_3) schreiben. Allgemeiner korrespondert eine Antikette \{A_1,\dotsc,A_n\} von Teilmengen von S zu X_{A_1} \vee \dotsc \vee X_{A_n}, wobei wir X_A := \bigwedge_{s \in A} X_s setzen. Beispiel. Der freie beschränkte distributive Verband auf S=\{1,2,3\} besteht aus 20 Elementen. Zur Veranschaulichung das Hasse-Diagramm: \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} 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) Bemerkung. Die Anzahl der Elemente des freien beschränkten distributiven Verbands auf \{1,\dotsc,n\} heißt die Dedekind-Zahl M(n). Dies ist zugleich die Anzahl der Antiketten von Teilmengen von \{1,\dotsc,n\}. Die einzigen bisher bekannten Werte sind: \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} Diese Zahlen wachsen also erstaunlich schnell. Die Zahl M(9) hat man noch nicht exakt bestimmen können.
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]