Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Beweise


Siebformel: Sind A1, A2, ¼An endliche Mengen, so ist
|A1 ÈA2 ȼAn| = a1 - a2 +a3 - ¼+(-1)n-1an,
wobei jedes ai = åS Í {1,2,¼,n}, |S| = i |Çi Î I Ai| ist.

Beweis: Es werden Kenntnisse über Binomialkoeffizienten benötigt. Wir betrachten ein Element in A1 È A2 ȼ ÈAn. Es liege in genau k dieser n Mengen. Dann trägt es genau k = k choose 1 zu a1 bei. Es trägt auch genau k choose 2 zu a2 bei, u.s.w, es trägt genau 1 zu ak bei aber 0 zu jedem ap mit p > k. Somit ist der Beitrag dieses Elements zur alternierenden Summe a1 - a2 + a3 - ¼+ (-1)n -1an gleich

æ
ç
è
k
1
ö
÷
ø
- æ
ç
è
k
2
ö
÷
ø
+ ¼+ (-1)k -1 æ
ç
è
k
k
ö
÷
ø
.
Nach dem Satz über alternierende Zeilensummen im Pascalschen Dreieck ist dies gleich 1. ..........
Satz: Die Menge R der reellen Zahlen ist nicht abzählbar.

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


Satz: Es seien zwei Folgen (an) und (bn) und zwei Zahlen C1, C2 gegeben. Dann gibt es genau eine Abbildung f(n,k), die für alle natürlichen Zahlen 0 £ k £ n definiert ist, die Rekursionsgleichung f(n,k) = C1 f(n-1,k-1) + C2 f(n-1,k) (für k < n) erfüllt, und außerdem noch die Anfangswerte f(n,0) = an sowie f(n,n) = bn für alle n erfüllt.

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


Satz: Die Fibonaccizahlen erfüllen
Fn = 1
Ö5
(Fn - (-1)n
Fn
),
wobei F = (1 + Ö5)/2 » 1.61803 der sogenannte "goldene Schnitt" ist.

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

Weiterhin ist

Ö5(Fn+2 - Fn+1 - Fn)
=
F n (F2 - F- 1) - (-1/F)n ((-1/F) 2 - (-1/F) - 1) = 0.
also Fn + Fn+1 = Fn+2. Die Anfangsbedingungen stimmen auch: [1/(Ö5)] (F0 - [((-1)0)/ (F0)]) = 0 sowie
1
Ö5
(F- (-1)
F
) = 1
Ö5
((Ö5+1)/2 + (Ö5 -1)/2) ) = 1.

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


{Ú,Ù} ist keine Junktorbasis.

Beweis:


Für jede endliche Boolesche Algebra (B,Ù,Ú) gibt es eine Menge M und eine Bijektion f: B ® P(M), so daß für alle x,y Î B gilt:

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) = {a1,a2, ¼, ak}, dann ist b = a1 Ú a2 Ú ¼Úak.
Beweis von (*): Wir setzen c = a1 Ú a2 Ú ¼Úak. Da b obere Schranke von a1, ¼, ak 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 = ai für ein 1 £ i £ k. Das hieß e ai £ c ÙØc = 0, ein Widerspruch.

(**) Ist b = a1 Ú ¼Úak, mit allen ai Atomen, dann ist f(b) = {a1,¼,ak}
Beweis von (**): Nach Konstruktion von f ist {a1,¼,ak} Í f(b). Wären die Mengen verschieden, gäbe es ein Atom a Î f(b) \ {a1,¼,ak}. Da für jedes 1 £ i £ k folgt a Ùai = 0, folgt a = a Ùb = a Ù(a1 Ú ¼Úak) = (a Ù a1) Ú ¼Ú (a Ùak) = 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).


Ist C ein Hüllenoperator auf einer Menge M, so ist die Menge {C(X) | X Í M} aller Hüllen bzgl. Í verbandsgeordnet. Dabei ist C(X) Ú C(Y) = C(X È Y) und C(X) Ù C(Y) = C(X) Ç C(Y).

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.


[Abian/Brown 1961, Birkhoff, Bourbaki 1950] Die geordnete Menge (X, £ ) habe die Eigenschaft, daß jede nichtleere wohlgeordnete Kette ein Supremum hat. f: X ® X sei eine Selbstabbildung, mit "x Î X: x £ f(x).
Dann hat f einen Fixpunkt.

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

  1. x0 Î 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.
Checken Sie, daß  beliebige Durchschnitte von Kegeln wieder Kegel sind. Also hat K = ÇT Kegel T auch diese Eigenschaften (1), (2), und (3).
Zeigen Sie, daß  K eine wohlgeordnete Kette ist. Nach der obigen Voraussetzung existiert dann sup(K). Zeigen Sie, daß  sup(K) = f(sup(K)) ist.
[Tarski 1955] Jeder Homomorphismus f: V ® V eines vollständigen Verbandes (V, £ ) in sich hat einen Fixpunkt.

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

"x Î S: x £ f(x) £ f(a),
also ist f(a) eine weitere obere Schranke von S und somit a £ f(a). Da f Homomorphismus ist, folgt f(a) £ f2(a), somit ist f(a) Î S. Daher ist auch f(a) £ a, und somit a = f(a).
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:


Beweis der "Dedekind-Formel" (Q ° R) Ç S Í (Q Ç (S ° RT)) ° (R Ç (QT ° S)):

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) Î RT ist (x,z) Î Q Ç (S ° RT).
Da (z,x) Î QT folgt (z,y) Î R Ç (QT ° S).
Aus beiden obigen Zeilen folgt (x,y) Î (Q Ç (S ° RT)) ° (R Ç (QT ° S)).


Beweis der "Schröder-Umformung" Q ° R Í S genau dann wenn QT ° ØS Í Ø R genau dann wenn ØS ° RT Í Ø Q:

(1) Sei Q ° R Í S.
Zu zeigen: QT ° ØS Í Ø R.
Wähle (x,y) Î QT ° ØS, d.h. es gibt ein z Î A mit (x,z) Î QT 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 (QT ° ØS Í Ø R) ® (ØS ° RT Í Ø Q) und (ØS ° RT Í Ø Q) ® (Q ° R Í S) gehen ziemlich analog.


Definiert man für einen Verband (V,Ù,Ú) x £ y falls x Ú y = y, so ist (B,£) verbandsgeordnet.

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}).

Damit erhalten wir     å M'ÎM |M' |! (n- |M' |)! £ n!,   und nach Division durch n!:

å
M'ÎM  
( n
|M' |
) -1

 
=
å
M' ÎM 
|M' |! (n- |M' |)!
n!
£ 1
Nun benutzen wir die Tatsache, daß  unter allen Binomialkoeffizienten n choose k der Wert für k = n/2 (falls n gerade ist) bzw. k=(n-1)/2 und k=(n+1)/2 (falls n ungerade ist) maximiert wird. Damit ist (im Fall, daß n gerade ist)
|M| ( n
n/2
) -1

 
£
å
M¢ ÎM 
( n
|M¢ |
) -1

 
£ 1,
und im ungeraden Fall genauso.

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 {a1, a2, ... ,an} in X \ C. Diese Menge erzeugt ein "upper order ideal" Up = {z Î X/ $ i: ai £ z}, sowie ein ein "lower order ideal" Down = {z Î X/ $ i: z £ ai }. 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 = {a1, a2, ... ,an } (warum?). Nach Induktionsvoraussetzung können wir Down in Ketten C1', C2', ... ,Cn' partitionieren, und Up in Ketten C1'', C2'', ... ,Cn'' (wobei wir so nummerieren können, daß jedes ai in Ci' sowie in Ci'' liegt). Dann sind die Ketten Ci' È Ci'' mit 1 £ i £ n eine Partitionierung von X in n Ketten, wie gewünscht.



Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.