DM - Preislösung

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Lösung des Preisrätsels

Die Aufgabe wurde von einem der Korrekturassistenten, Herrn Karel Vyborny, richtig gelöst. Da kein Student eine Lösung einreichte, geht der Preis an ihn.

Die Menge aller Partitionen einer festen Menge M läßt sich ordnen: Wir nennen eine Partition {A₁, A₂, ... , A_k} gröber als die Partition {B₁, B₂, ... , B_m}, falls es eine Abbildung f: {1,2,...,m} ® {1,2,...k} gibt, so daß B_i Í A_f(i) für jedes i Î {1,2,...,m} gilt. Insbesondere ist dann f surjektiv und deshalb k £ m.

Es ist etwas einfacher mit Äquivalenzrelationen statt mit Partitionen zu arbeiten: Relativ klar sollte sein:

(1) Eine Partition ist genau dann gröber als eine andere wenn die zugehörende Äquivalenzrelation die andere enthält.

(2) Die Teilmengenrelation ist natürlich eine Ordnungsrelation auf der Menge Äqu(M) aller Äquivalenzrelationen auf einer festen Menge M (eine Teilordnung von (P(M × M),Í)).

(3) Äqu(M) ist ein abgeschlossenes System.

Seien R_i, i Î I Äquivalenzrelationen auf M.
Dann ist (x,x) Î R_i für jedes i Î I. Ist (x,y) Î R_i für jedes i Î I, so ist auch für jedes i Î I: (y,x) Î R_i. Gilt (x,y) Î Ç_iÎI R_i und (y,z) Î Ç_iÎI R_i so folgt genauso auch (x,z) Î Ç_iÎI R_i
Deshalb ist Ç_iÎI R_i auch eine Äquivalenzrelation.

(4) (Äqu(M),Í) ist verbandsgeordnet. Dabei ist R Ù S = R Ç S und R Ú S = (R È S)^* die transitive Hülle der Vereinigung.

Dies folgt mit (3) und dem Satz über Hüllenoperatoren.

(5) Es ist i.A. keine Boolesche Algebra,

was man schon daran sieht, daß die Menge {1,2,3,4} 15 Partitionen hat---endliche Boolesche Algebren haben aber immer zweierpotenz viele Elemente. Genauer ist (8) der Grund.

(6) Es gibt 0 und 1,

nämlich die Menge id_M = {(x,x)/x Î M} sowie M × M.

(7) Jede Partition hat (mindestens) ein Komplement:

Sei R eine Äquivalenzrelation. Aus jeder Äquivalenzklasse A_i, 1£i£t, wählen wir ein Element a_i aus. Wir definieren S = id_M È {(a_i,a_j) / 1£ i,j £t}.
R Ú S = (R È S)^* = M × M, denn seien x,y Î M. Dann gibt es 1£ i,j £t mit (x,a_i) Î R und (a_j,y) Î R. Da (a_i,a_j) Î S, folgt (x,y) Î (R È S)^*.
R Ù S = R Ç S = id_M.

(8) Die Distributivgesetze gelten leider nicht.

Beispiel: M={1,2,3,4}, R={(1,1),(2,2),(3,3),(4,4),(2,3),(3,2)}, S={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)}, T={(1,1),(2,2),(3,3),(4,4),(1,3),(3,1),(2,4),(4,2)}. Wir haben
R Ú (S Ù T) = R Ú id_M = R ¹ M × M = (M × M) Ù (M × M) = (R È S)^* Ù (R È T)^* = (R Ú S) Ù (R Ú S), sowie
R Ù (S Ú T) = R Ù (S È T)^* = R Ù (M × M) = R ¹ id_M = id_M Ú id_M = (R Ù S) Ú (R Ù T).

Erich Prisner
erstellt am 25. Mai 2000.

DISKRETE MATHEMATIK Erich Prisner Sommersemester 2000

Lösung des Preisrätsels

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000