DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Beweis: Es werden Kenntnisse über Binomialkoeffizienten benötigt. Wir betrachten ein Element in A₁ È A₂ ȼ ÈA_n. Es liege in genau k dieser n Mengen. Dann trägt es genau k = zu a₁ bei. Es trägt auch genau zu a₂ bei, u.s.w, es trägt genau 1 zu a_k bei aber 0 zu jedem a_p mit p > k. Somit ist der Beitrag dieses Elements zur alternierenden Summe a₁ - a₂ + a₃ - ¼+ (-1)^{n -1}a_n gleich

Beweis: ...........

Beweis: ...........

Beweis: Wie wir vielleicht später sehen werden ist ganz wesentlich, daß  F sowie -1/F Nullstellen des Polynoms x² -x -1 sind. (Beachten Sie auch die Analogien zwischen x²-x¹ -x⁰ = 0 und F_n+2- F_n+1-F_n+0 = 0.) Offenbar ist ja F² - F- 1 = (1 + 2Ö 5 + 5 - 2 - 2Ö5 - 4)/4 = 0 sowie -1/F = (1-Ö5)/2 und damit (-1/F) ² - (-1/F) - 1 = (1 - 2Ö 5 + 5 - 2 + 2 Ö5 - 4)/4 = 0.

Weiterhin ist

Natürlich folgt der Satz auch direkt aus dem allgemeinen Resultat über Rekursionsgleichungen.

Beweis:

• f(0) = Æ, f(1) = M,
• f(x Ú y) = f(x) Ç f(y), und f(x Ù y) = f(x) È f(y),
• f(Ø x) = M \ f(x).

Beweis: Betrachten wir die Elemente in unserer verbandsgeordneten Menge (B, £ ) die im Hasse-Diagramm mit der 0 verbunden sind. Offenbar sind das die x Î B mit y £ x Þ (y = 0 Úy = x). Diese Elemente werden (in beliebigen geordneten Mengen) Atome genannt.

In Teilmengenverbänden sind die Atome gerade die einelementigen Mengen. Wenn der zu beweisende Satz also wahr ist, so müssen die Atome von B mittels f auf die einelementigen Teilmengen der noch zu definierenden Menge M abgebildet werden. Wir wissen also zumindest schon, daß  M dann so viele Elemente wie B Atome enthalten muß . Da es nicht darauf ankommt wie die Elemente in M aussehen (nur auf ihre Zahl), können wir auch gleich M als die Menge der Atome von B definieren. Auf die Atome a von B definieren wir dann natürlich f(a) = {a}.

Haben wir in einem Teilmengenverband die Atome (d.h. die einelementigen Teilmengen) beschriftet, so ergibt sich daraus die Beschriftung aller anderen Mengen, denn {x} Í A Û x Î A. Damit können wir jetzt f für beliebige b Î B definieren. Wir setzen f(b) = {a Atom von B | a £ b}. Für b ¹ 0 ist f(b) nichtleer, da B endlich ist.

Nachdem wir f (hoffentlich richtig) definiert haben, müssen wir nur noch die Eigenschaften von f zeigen. Dazu müssen wir wohl auch die Voraussetzung, daß B nicht nur ein Verband, sogar Boolesche Algebra ist, anwenden. Zuerst zeigen wir folgendes:

(*) Ist b Î B, etwa f(b) = {a₁,a₂, ¼, a_k}, dann ist b = a₁ Ú a₂ Ú ¼Úa_k.
Beweis von (*): Wir setzen c = a₁ Ú a₂ Ú ¼Úa_k. Da b obere Schranke von a₁, ¼, a_k ist, ist c £ b, also c = b Ùc. Wir werden c = b zeigen. Wir wenden Distributivität sowie Komplementseigenschaft an und erhalten (b Ù Øc) Úc = (b ÙØc) Ú(b Ùc) = b Ù(c Ú Øc) = b Ù1 = b. Wäre b ¹ c, so wäre nach der Eindeutigkeit des Komplements b Ù Øc ¹ 0, also gäbe es ein Atom a £ Øb ÙØc. Wegen a £ b wäre a = a_i für ein 1 £ i £ k. Das hieß e a_i £ c ÙØc = 0, ein Widerspruch.

(**) Ist b = a₁ Ú ¼Úa_k, mit allen a_i Atomen, dann ist f(b) = {a₁,¼,a_k}
Beweis von (**): Nach Konstruktion von f ist {a₁,¼,a_k} Í f(b). Wären die Mengen verschieden, gäbe es ein Atom a Î f(b) \ {a₁,¼,a_k}. Da für jedes 1 £ i £ k folgt a Ùa_i = 0, folgt a = a Ùb = a Ù(a₁ Ú ¼Úa_k) = (a Ù a₁) Ú ¼Ú (a Ùa_k) = 0, ein Widerspruch.

Aus (*) folgt Injektivität von f, denn aus f(b) = f(b¢) folgt, mit c definiert wie eben, b = c = b¢.

Aus (**) folgt Surjektivität von f.

Die Eigenschaften in den letzten beiden Zeilen des Satzes sind jetzt einfach nachzuprüfen. Sei b, b¢ Î B. Nach (*) ist b = _{a Î f(b)} a, b¢ = _{a Î f(b¢)} a, Somit ist b Úb¢ = _{a Î f(b) Èf(b¢)} a und f(b Úb¢) = f(b) È f(b¢) nach (**). Auch ist b Ùb¢ = _{a Î f(b) a¢ Î f(b¢)} a Ù a¢ = _{a Î f(b) Çf(b¢)} a, da für verschiedene Atome a, a¢ gilt a Ùa¢ = 0. Wieder mit (**) folgt f(b Ùb¢) = f(b) Çf(b¢). Schließlich prüft man, wenn A die Menge aller Atome von B ist, für c = _{a Î A \f(b)} a leicht c Ùb = 0 und c Úb = 1 nach, also ist Øb = c und nach (**) f(Øb) = A \f(b).

Beweis: Die Hülle C(X ÈY) ist obere Schranke von {C(X), C(Y)}. Dies folgt aus X, Y Í X ÈY wegen der Monotonie der Hülle.

Sei C(Z) eine weitere obere Schranke von {C(X), C(Y)}, d.h. C(X), C(Y) Í C(Z). Machen Sie sich (z.B. an Hand des Konvexe-Hülle-Beispiels) klar, daß  wir über Z nicht viel aussagen können, aber wegen der Extensitivität (und Transitivität von " Í ") folgt X, Y Í C(Z), also X ÈY Í C(Z). Mit Monotonie und Idempotenz folgern wir C(X ÈY) Í C(C(Z)) = C(Z). Folglich ist C(X ÈY) kleinste obere Schranke von {C(X),C(Y)}.

Wieso ist C(X) ÇC(Y) eine Hülle? Wenn, dann ist sie sogar Hülle ihrer selbst. Tatsächlich ist wegen Monotonie und Idempotenz C(C(X) ÇC(Y)) Í C(C(X)) = C(X) und genauso C(C(X) ÇC(Y)) Í C(Y), also C(C(X) ÇC(Y)) Í C(X) ÇC(Y). Mit der Extensitivität gilt hier sogar Gleichheit.

Natürlich ist C(X) ÇC(Y) untere Schranke von {C(X), C(Y)}.

Jede weitere untere Schranke C(W) von {C(X), C(Y)} ist in C(X) ÇC(Y) enthalten, also ist C(X) ÇC(Y) größ te untere Schranke.

Beweis (vergleiche Aumann, Seite 38): Sei x₀ Î X und betrachte die Menge U[x₀] = {y Î X: x₀ £ y }. Eine Teilmenge T Í U[x₀] heisse Kegel, falls gilt

1. x₀ Î T,
2. Für jedes x Î T ist f(x) auch in T,
3. Ist M Í T und existiert sup(M) in (X, £ ), so ist sup(M) Î T.

Beweis: Wir definieren die Menge der "Gewinnler" S = {x Î V: x £ f(x) }. Da 0 £ f(0) ist diese Menge nichtleer. Das Supremum dieser Menge sei a = _{x Î S} x. Da f Homomorphismus ist, und a eine oberes Schranke von S, folgt

Bernstein'scher Äquivalenzsatz: Gibt es eine injektive Abbildung f: A ® B und eine injektive Abbildung g: B ® A, so sind A und B gleichmächtig.

Beweis mit dem Fixpunktsatz von Knaster/Tarski: Wir betrachten die Abbildung h: P(A) ® P(A); h(S) = A \ g(B\f(S)). Er ist ein Homomorphismus des Potenzmengenverbandes, weil aus S Í S' ersteinmal f(S) Í f(S') folgt, also auch B\f(S') Í B\f(S). Weiterhin folgt g(B\f(S')) Í g(B\f(S)), und h(S) = A \ g(B\f(S)) Í A \ g(B\f(S')) = h(S').
Nach dem Fixpunktsatz gibt es ein S Í A mit h(S)=S, d.h. {S, g(B\f(S))} ist eine Partition von A. Da A\S = g(B\f(S)), ist die Einschränkung g' von g auf B\f(S) eine Bijektion von B\f(S) nach A\S. D.h. g'^-1 ist eine Bijektion von A\S nach B\f(S). Auch die Einschränkung f' von f auf S ist eine Bijektion von S nach f(S).
Wir definieren q: A ® B durch q(x) = f'(x) falls x Î S, q(x) = g'^-1(x) falls x Î A\S. q ist bijektiv.

Beweis mit dem unendlichen Heiratssatz: ...

Beweis:

Sei (x,y) Î (Q ° R) Ç S, d.h. (x,y) Î S und es gibt ein z Î A mit (x,z) Î Q und (z,y) Î R.
Da (y,z) Î R^T ist (x,z) Î Q Ç (S ° R^T).
Da (z,x) Î Q^T folgt (z,y) Î R Ç (Q^T ° S).
Aus beiden obigen Zeilen folgt (x,y) Î (Q Ç (S ° R^T)) ° (R Ç (Q^T ° S)).

(1) Sei Q ° R Í S.
Zu zeigen: Q^T ° ØS Í Ø R.
Wähle (x,y) Î Q^T ° ØS, d.h. es gibt ein z Î A mit (x,z) Î Q^T und (z,y) Î ØS, d.h. (z,x) Î Q und (z,y) Ï S.
Angenommen (x,y) Ï Ø R, also (x,y) Î R, dann ist wegen der Voraussetzung Q ° R Í S (z,y) Î S im Widerspruch zu oben. Folglich muss (x,y) Î Ø R sein.

Die beiden anderen Implikationen (Q^T ° ØS Í Ø R) ® (ØS ° R^T Í Ø Q) und (ØS ° R^T Í Ø Q) ® (Q ° R Í S) gehen ziemlich analog.

Beweis:

Zuerst zeigen wir, daß  die so definierte Relation eine Ordnungsrelation ist.
Reflexivität gilt, denn x Úx = x (Idempotenz von 'Ú').
Sei nun x £ y und y £ x, d.h. x Úy = y und y Úx = x. Mit der Kommuntativität von 'Ú' folgt daraus x = y.
Sei schließlich x £ y, y £ z, d.h. x Úy = y und y Úz = z. Es folgt z = y Úz = (x Úy) Úz = x Ú(y Úz) = x Úz mit dem Assoziativgesetz für 'Ú', also x £ z.

Jetzt beweisen wir: Für beliebige x,y Î V gilt genau dann x Úy = y falls x Ùy = x ist. Denn sei x Úy = y. Nach dem Absorptionsgesetz ist x = x Ù(x Úy) = x Ùy. Ist umgekehrt x Ùy = x, dann ist x Úy = y Úx = y Ú(x Ùy) = y Ú(y Ùx) = y unter Benutzung beider Kommutativgesetze und eines Absorptionsgesetzes. D.h. wir hätten '£ ' (natürlich) auch mittels 'Ù' definieren können.

Seien x,y Î V.

Nun benötigen wir die Absorptionsgesetze x Ú(x Ùy) = x und y Ú(y Ùx) = y (und Kommutivität von 'Ú' und 'Ù') um einzusehen, daß  x Ùy eine untere Schranke von {x,y} ist. Sei nun z eine weitere untere Schranke von {x,y}, d.h. z Úx = x und z Úy = y, bzw. mit Obigem z Ùx = z und z Ùy = z. Mit dem Assoziativ- und Kommutativigesetz für 'Ù' folgt damit (x Ùy) Ùz = x Ù (z Ùy) = x Ùz = z, also z £ x Ùy , d.h. x Ùy ist tatsächlich größte untere Schranke von {x,y}.

Es ist auch x Ú (x Úy) = (x Úx) Úy = x Úy und genauso y Ú(x Úy) = x Úy (Assoziativgesetz und Idempotenz für 'Ú'). Also ist x Úy eine obere Schranke von {x,y}. Sei z eine weitere obere Schranke, d.h. x Úz = z und y Úz = z. Kraft Assoziativgesetz ist (x Úy) Úz = x Ú(y Úz) = x Úz = z, d.h. x Úy £ z, d.h. x Úy ist kleinste obere Schranke.

Satz von Sperner Im Potenzmengenverband (P({1,2,...,n}), Ç,È). ist die maximale Anzahl der Elemente in einer Antikette gleich

( n n/2 ) für gerades n, bzw. ( n (n+1)/2 ) für ungerades n

Beweis mit doppelter Abzählung. Eine maximale Kette ist eine Kette, die in keiner anderen Kette echt enthalten ist, die sich also nicht mehr vergrössern läßt. In unserem speziellen Verband haben maximale Ketten die Form Æ Í {a} Í {a,b} Í ... Í {1,2,...,n}. a,b,... ist dann also eine Permutation von {1,2,...,n}, und umgekehrt entspricht auch jeder Permutation eine maximale Antikette, weshalb die Anzahl dieser maximalen Antiketten gleich n! ist.
Man sieht auch leicht ein, daß eine Antikette und eine Kette höchstens ein gemeinsames Element haben.

Sei nun M eine Antikette.
Wir zählen alle Paare (S,M'), wobei S eine maximale Kette ist, und M' (das) gemeinsame Element von M und S ist (M' ist eine Teilmenge von {1,2,...,n}).

• Einerseits ist die Anzahl aller dieser Paare höchstens gleich |S| = n!, da (s.o.) jedes solche S höchstens ein M' Î M enthält,
• Andererseits liegt jedes solche M' Î M in genau |M'|! (n-|M'|)! solchen maximalen Ketten S, nämlich in denen, die Permutationen f entsprechen mit f(M') = {1,2,...,|M'|}, d.h. bei denen die Elemente von M' zuerst kommen. Deshalb ist die Anzahl aller dieser Paare (S,M') gleich å_{M'Î M} |M'|! (n-|M'|)!.

Satz von Dilworth In jeder endlichen geordneten Menge (M,£) ist die minimale Mächtigkeit einer Partition von M in Ketten gleich der maximalen Mächtigkeit einer Antikette.

direkter Beweis: durch Induktion nach |X|. Der Induktionsanfang mit |X|=1 ist klar; sei also |X|=k+1und der Satz für geordnete Mengen mit k oder weniger Elementen der Grundmenge gültig. Da der Satz für Ketten offenbar gilt, können wir auch annehmen, daß keine Kette vorliegt, d.h. die maximale Größe n einer Antikette mindestens 2 beträgt. Zu finden ist eine Partition von X in n Ketten.

Gibt es eine Kette C, so daß die Teilordnung X \ C keine Antikette mit n Elementen enthält, dann läßt sich nach Induktionsvoraussetzung X \ C mit höchstens n-1 Ketten partitionieren. Zusammen mit C ergibt das eine gewünschte Partitionierung von X.
(*) Wir können also im Folgenden annehmen, daß keine solche Kette existiert.

Nun konstruieren wir die Partitionierung in n Ketten. Wir wählen ein maximales Element x, und unter den Elementen kleiner als x wählen wir ein minimales als y. (Gäbe es kein solches y, so würde die Kette {x} (*) widersprechen.

Dann ist C={y,x} eine Kette, und nach Obigem gibt es eine Antikette {a₁, a₂, ... ,a_n} in X \ C. Diese Menge erzeugt ein "upper order ideal" Up = {z Î X/ $ i: a_i £ z}, sowie ein ein "lower order ideal" Down = {z Î X/ $ i: z £ a_i }. Offenbar liegt x nicht in Down (warum?) und y nicht in Up (warum?), weshalb beide Mengen weniger als k+1 Elemente haben. Außerdem ist Up Ç Down = {a₁, a₂, ... ,a_n } (warum?). Nach Induktionsvoraussetzung können wir Down in Ketten C₁', C₂', ... ,C_n' partitionieren, und Up in Ketten C₁'', C₂'', ... ,C_n'' (wobei wir so nummerieren können, daß jedes a_i in C_i' sowie in C_i'' liegt). Dann sind die Ketten C_i' È C_i'' mit 1 £ i £ n eine Partitionierung von X in n Ketten, wie gewünscht.