Die Teilbarkeitsrelation als Ordnungsrelation

Die Eigenschaften der Teilbarkeitsrelation werden untersucht. Besonders ausführlich wird gezeigt, dass sie eine Ordnungsrelation ist, welche Eigenschaften Ordnungsrelationen haben und wie sich diese in einem Hasse-Diagramm darstellen lassen. In den R-Skripten wird gezeigt, wie man das Hasse-Diagramm für eine beliebige Ordnungsrelation erzeugt. Die Anwendungsbeispiele zeigen dann Zusammenhänge zwischen der Teilbarkeitsrelation, der Teilmengenrelation und der Primfaktorzerlegung.

walter

28 Apr. 2019

transitive Reduktion Hasse-Diagramm Ordnungsrelation Transitivität vollständige Ordnung Teilbarkeitsrelation partielle Ordnung Antisymmetrie

Inhaltsverzeichnis

Einordnung des Artikels

Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
- Zahlentheorie
  - Rechnen mit Restklassen: Teilbarkeitsregeln
  - Die Teilbarkeitsrelation als Ordnungsrelation

In Rechnen mit Restklassen: Teilbarkeitsregeln wurden aus der Kongruenz, einer Äquivalenzrelation induziert durch die Ganzzahl-Division, die Teilbarkeitsregeln hergeleitet. Hier wird die Teilbarkeit unter einem anderen Aspekt untersucht, nämlich dass sie eine Ordnungsrelation auf den natürlichen Zahlen erzeugt. Die Kenntnis der Kongruenz ist für das Verständnis dieses Kapitels eigentlich nicht nötig, aber sehr hilfreich.

Definition: Teiler einer ganzen Zahl

Die folgenden Begriffe werden mit der Menge der ganzen Zahlen Z definiert:

Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}.

Mit den natürlichen Zahlen N wird die Menge der echt positiven ganzen Zahlen bezeichnet, also

N = {1, 2, 3, ...}.

Die 0 wird also nicht zu den natürlichen Zahlen gerechnet.

Der zentrale Begriff, auf den die weiteren Untersuchungen aufbauen ist der Begriff des Teilers – und damit verbunden der Teilbarkeit.

Definition: Eine ganze Zahl a heißt Teiler der ganzen Zahl b, wenn es eine weitere ganze Zahl q gibt mit: a · q = b. Man schreibt dann a|b. (Oft sagt man dann auch a teilt b.)

♦ ♦ ♦ ♦ ♦ ♦

Die Definition wirkt sehr einfach, wirft aber sofort Fragen auf, da sie mit ganzen Zahlen und nicht mit natürlichen Zahlen formuliert ist:

Wie lauten alle Teiler einer Zahl, zum Beispiel b = 12?
Welche Teiler hat die Zahl b = 0?
Von welchen ganzen Zahlen b ist a = 0 Teiler?

1. Frage: Naiv würde man antworten, dass die Teiler von b = 12 lauten: a = 2, 3, 4, 6; wähle dazu q = 6, 4, 3, 2. Laut der Definition sind aber auch a = 1 und a = 12 Teiler von 12, da obige Definition mit q = 12 beziehungsweise q = 1 erfüllt wird.

Aber das sind immer noch nicht alle Teiler: Hat man einen Teiler a > 0 von 12 gefunden, so ist auch -a ein Teiler von 12; man muss die entsprechenden negativen q einsetzen.

Die Menge aller Teiler von 12 lautet somit:

{-12, -6, -4, -3, -2, -1, 1, 2, 3, 4, 6, 12}.

2. Frage: Um die Teiler von b = 0 zu finden, muss man alle ganzen Zahlen a finden, zu denen es ein q ∈ Z gibt mit a · q = 0. Da man aber immer q = 0 wählen kann, ist jede ganze Zahl a ∈ Z ein Teiler von 0.

3. Frage: Jetzt muss man zu a = 0 ganze Zahlen b und q finden mit: a · q = b. Wenn aber a = 0, muss auch b = 0 sein. Das heißt aber a = 0 ist nur Teiler von b = 0 und keiner anderen Zahl.

Im Kapitel Rechnen mit Restklassen: Teilbarkeitsregeln wurden Teilbarkeitsregeln formuliert, die bei großen Zahlen a und b sehr hilfreich sind, um zu entscheiden ob a ein Teiler von b ist oder nicht. Dort wurde aber nicht ausdrücklich auf die Möglichkeit negativer Teiler eingegangen; wenn sie keine besondere inhaltliche Bedeutung haben, werden auch hier meist nur die positiven Teiler angegeben.

Eigenschaften der Teilbarkeitsrelation

In Rechnen mit Restklassen: Teilbarkeitsregeln im Abschnitt Was ist eine Relation? wurde ausführlich beschrieben, dass man unter einer Relation zwischen A und B eine Menge geordnete Paare (a, b) ∈ A × B (kartesisches Produkt von A und B) versteht. Und dass Symbole wie = oder ≤, bei denen man eher an einen Vergleich denkt, eine Relation erzeugen.

In diesem Sinne erzeugt auch das Symbol | mit der Definition eines Teilers eine Relation auf Z: alle Zahlenpaare (a, b) ∈ Z × Z, bei denen a Teiler von b ist, also a|b, gehören der Relation an.

Abbildung 1: Darstellung der geordneten Paare (a, b) der Teilbarkeitsrelation a|b für 1 ≤ a, b ≤ 50. Zahlenpaare, bei denen b eine Primzahl ist, sind blau dargestellt, andere Zahlenpaare sind rot.

Abbildung 2: Nochmals die Darstellung der geordneten Paare (a, b) der Teilbarkeitsrelation a|b, jetzt aber für 1 ≤ a, b ≤ 1600. Damit der relevante Teil der Graphik besser sichtbar ist, wurde im Vergleich zu Abbildung 1 die a-Achse um den Faktor 2 gestreckt. Für Primzahlen b ist jetzt eine blaue Linie eingezeichnet.

Aufgabe:

Identifizieren Sie in Abbildung 2 die Zahl b = 60, sowie die Vielfachen von b.

Wie kann man die Anordnung der Punkte in der Umgebung von (1, 60) erklären?

Es ist nun naheliegend, nach den Eigenschaften der Teilbarkeitsrelation zu fragen; sie werden in den folgenden Unterabschnitten untersucht.

Teiler von Summen

Betrachtet man nochmals das Beispiel von oben mit der Menge der Teiler von 12, nämlich

{-12, -6, -4, -3, -2, -1, 1, 2, 3, 4, 6, 12},

so fällt sofort auf:

Wählt man einen Teiler von b = 12 aus, etwa a = 3, dann ist b + a = 15 und b - a = 9 ebenfalls durch a = 3 teilbar. Und dies gilt für alle Teiler a von b = 12.

Verbirgt sich dahinter eine allgemeinere Aussage?

1. Behauptung: Sind a, b ∈ Z mit a|b, so ist auch a|(b + a) und a|(b - a).

Beweis: Wenn a Teiler von b ist, dann gibt es eine ganze Zahl q mit a · q = b. Aber dann ist

b + a = a · q + a = (q + 1) · a.

Entsprechend erhält man

b - a = a · q - a = (q - 1) · a.

Aber dies bedeutet, dass a Teiler von b + a und von b - a ist.

An den Stellen, an denen oben 1 steht, kann auch eine beliebige natürliche Zahl m stehen, wodurch man die gesuchte allgemeine Aussage erhält.

Satz 1: Sind a, b ∈ Z mit a|b und m ∈ N, so ist auch a|(b + m · a) und a|(b - m · a).

Beweis: Wie im Beweis der Behauptung oben gibt es ein q ∈ Z mit · q = b. Dann ist

b + m · a = (q + m) · a und

b - m · a = (q - m) · a.

Da q + m und q -m ganze Zahlen sind, folgt die Behauptung des Satzes 1.

♦ ♦ ♦ ♦ ♦ ♦

Man beachte, dass man aus a|b nicht folgern kann, dass für beliebiges c gilt: a|(b + c). Ein Gegenbeispiel ist a = 3, b = 12 und c = 5.

Linearkombinationen in den ganzen Zahlen

Zu zwei gegebenen ganzen Zahlen a und b wird jeder Ausdruck der Form

n · a + m · b, n, m ∈ Z,

als Linearkombination in Z von a und b bezeichnet.

Man kann leicht den folgenden Zusammenhang zwischen Teilbarkeit und Linearkombination zeigen.

Satz 2: Sind d, a, b ganze Zahlen mit d|a und d|b. Dann gilt: d ist Teiler von jeder Linearkombination von a und b, also d|(n · a + m · b), n, m ∈ Z.

Beweis von Satz 2: Nach Voraussetzung kann a als Vielfaches von d und b als Vielfaches von d geschrieben werden. Da Summe beziehungsweise Produkt zweier ganzer Zahlen eine ganze Zahl ergeben, ist auch die Linearkombination n · a + m · b ein Vielfaches der Zahl d.

Reflexivität und Transitivität

In Ganzzahl-Division: Kongruenzen und Restklassen als Beispiele für Äquivalenzrelationen und Äquivalenzklassen wurden Äquivalenzrelationen ausführlich diskutiert. Man sieht sofort, dass die Teilbarkeitsrelation a|b keine Äquivalenzrelation ist, da die Symmetrie nur in einigen Spezialfällen gilt, aber nicht allgemein:

Aus "a ist Teiler von b" müsste folgen, dass b ein Teiler von a ist. Dies ist nur im Spezialfall a = b richtig, andernfalls falsch.

Die Äquivalenzrelation war durch die drei Eigenschaften

Reflexivität
Symmetrie
Transitivität

gekennzeichnet. Wie steht es bei der Teilbarkeitsrelation um die Reflexivität und die Transitivität?

Die Reflexivität ist offensichtlich erfüllt, da für alle ganzen Zahlen a gilt: a|a.

Auch die Transitivität ist erfüllt; sie wird unten bewiesen, wenn gezeigt wird, dass die Teilbarkeitsrelation eine Ordnungsrelation ist.

Die Teilbarkeitsrelation als Ordnungsrelation

Die Antisymmetrie

Oben wurde schon gesagt, dass die Teilbarkeitsrelation die Symmetrie nicht erfüllt. Aber sie hat eine leicht abgewandelte Eigenschaft der Symmetrie: die Antisymmetrie – aber nur, wenn man die Teilbarkeitsrelation auf die ganzen Zahlen N einschränkt.

Zur Definition der Antisymmetrie wird daran erinnert, dass eine Relation R auf M eine Menge geordneter Zahlenpaare aus dem kartesischen Produkt M × M ist.

Definition: Eine Relation R auf einer Menge M heißt antisymmetrisch, wenn für alle Elemente x, y ∈ M mit (x, y) ∈ R und (y, x) ∈ R gilt; x = y.

Beispiel: Die Relation "kleiner gleich" auf den ganzen Zahlen ist antisymmetrisch. Denn ist x ≤ y und zugleich y ≤ x, dann muss x = y gelten.

Die Symmetrie wird von der Relation ≤ verletzt: Aus x ≤ y kann man nicht folgern, dass y ≤ x.

Definition: Eine Relation R auf einer Menge M heißt Ordnungsrelation, wenn sie reflexiv, antisymmetrisch und transitiv ist.

Beispiel: Die bekannteste Ordnungsrelation ist die Relation "kleiner gleich", die hier auf den ganzen Zahlen betrachtet wird.

Satz 3: Die Teilbarkeitsrelation a|b auf den natürlichen Zahlen N ist eine Ordnungsrelation.

Bemerkung: Man beachte, dass in Satz 3 ausdrücklich gesagt wird, die Teilbarkeitsrelation wird auf N eingeschränkt. Auf Z ist sie keine Ordnungsrelation.

Beweis von Satz 3

Für die Reflexivität gibt es nicht viel zu zeigen: für alle natürlichen Zahlen a muss gelten a|a. Wegen a · 1 = a ist dies offensichtlich der Fall.

Der Beweis der Antisymmetrie wird sofort zeigen, warum Satz 3 nicht für die ganzen Zahlen Z formuliert wurde.

Zu zeigen ist jetzt: Sind a, b ∈ N mit a|b und zugleich b|a, dann muss a = b gelten.

Wegen a|b gibt es ein q (das jetzt in N ist und nicht in Z liegen kann) mit

a · q = b.

Wegen b|a gibt es ein p ∈ N mit

b · p = a.

Setzt man die Gleichungen ineinander ein, erhält man:

a · q · p = a.

Da aber a ungleich 0 ist, muss q · p = 1 gelten. Innerhalb der natürlichen Zahlen, ist dies aber nur für q = 1 = p zu erfüllen. Aber dann ist a = b.

(Man beachte: innerhalb von Z gibt es die weitere Möglichkeit mit q = 1, p = -1 oder q = -1, p = 1. Und dann ist a = - b.)

Zur Transitivität ist zu zeigen: Sind a, b, c natürliche Zahlen mit a|b und b|c, dann ist auch a|c.

Nach den Voraussetzungen gibt es natürliche Zahlen q und p mit

a · q = b und b · p = c.

Ineinander eingesetzt, erhält man

c = a · q · p.

Da q · p eine natürliche Zahl ist, folgt a|c.

♦ ♦ ♦ ♦ ♦

Äquivalenzrelation und Ordnungsrelation

Die folgende Tabelle soll zum besseren Verständnis des Unterschiedes zwischen einer Äquivalenzrelation und einer Ordnungsrelation die Eigenschaften der Kongruenz und der Teilbarkeit gegenüberstellen (die Aussagen sind so zu verstehen, dass sie " für alle ..." gelten).

	Kongruenz modulo k auf Z	Teilbarkeit auf N
Reflexivität	für alle x: x ≡ x (mod k)	für alle a: a\|a
Transitivität	x ≡ y (mod k), y ≡ z (mod k) ⇒ x ≡ z (mod k)	a\|b und b\|c ⇒ a\|c
Symmetrie	x ≡ y (mod k) ⇒ y ≡ x (mod k)	keine Symmetrie
Antisymmetrie	keine Antisymmetrie	a\|b und b\|a ⇒ a = b

Tabelle zur Gegenüberstellung von Äquivalenzrelation und Ordnungsrelation.

Bezeichnungen und Konventionen

Oben wurde die Ordnungsrelation in der Definition mit der Relation R formuliert. Um eine suggestivere Schreibweise für eine Ordnungsrelation zu verwenden, einigt man sich meist auf ein Symbol, das für eine beliebige Ordnungsrelation verwendet wird. Hier wird das Symbol ⊆ verwendet, wenn ausgedrückt werden soll, dass eine Relation R eine Ordnungsrelation ist. Das Symbol ≤ ("kleiner oder gleich") wird nur für die Ordnung auf Zahlen verwendet.

Das Symbol ⊆ steht eigentlich für die Teilmengenrelation, die weiter besprochen wird; es sollte aber aus dem Zusammenhang klar sein, wie ⊆ jeweils eingesetzt wird.

Die Verwendung der Ordnung ≤ etwa auf Z wirft sofort Fragen auf:

Welche Bedeutung hat das Symbol <?
Welche Bedeutung hat das Symbol ≥?

Zur ersten Frage: Das Symbol <, etwa in x < y bedeutet:

Zwischen x und y besteht die Relation x ≤ y und gleichzeitig gilt x ≠ y.

In diesem Sinne werden hier auch die Symbole ⊆ und ⊂ für eine beliebige Ordnungsrelation eingesetzt; wobei man sehen wird, dass ⊂ fast nie benötigt wird.

Zur zweiten Frage: Bei der Relation ≤ auf Z ist x ≥ y einfach nur eine andere Schreibweise für y ≤ x; es ist keine weitere Information enthalten.

Entsprechend kann man statt a ⊆ b auch gleichwertig b ⊃ a schreiben.

Für die hier am häufigsten vorkommende Teilbarkeitsrelation a|b wird kein "umgekehrtes" Symbol verwendet; man bräuchte dazu die Relation "ist Vielfaches von"

Vollständige und teilweise Ordnung

Die Ordnungsrelation hat ihren Namen natürlich von der Anordnung der Zahlen gemäß ≤. Es besteht aber ein wichtiger Unterschied zwischen der Relation x ≤ y und der Teilbarkeitsrelation a|b, die noch geklärt werden muss. Die Definition der Ordnungsrelation von oben muss dann überdacht werden.

Die Anordnung der Zahlen gemäß ≤ hat die Eigenschaft, dass man zwei beliebige Zahlen x, y ∈ Z miteinander vergleichen kann und es sinnvoll ist zu sagen: Wenn x ≤ y nicht erfüllt ist, gilt x ≥ y.

Dagegen kann man bei der Teilbarkeitsrelation nicht alle Zahlen a, b ∈ N miteinander vergleichen: Wenn a|b nicht erfüllt ist, kann man daraus nicht folgern, dass b|a gilt.

Beispiel:

3 ist kein Teiler von 5 und 5 ist kein Teiler von 3. Man kann daher die Zahlen 3 und 5 nicht mit der Teilbarkeitsrelation vergleichen.

Dieser Unterschied zwischen den Ordnungsrelationen x ≤ y und a|b führt zu den Begriffen der vollständigen (oder totalen) Ordnungsrelation und der teilweisen (oder partiellen) Ordnungsrelation.

Weiter oben wurde eine Relation R als Ordnungsrelation auf einer Menge M bezeichnet, wenn sie reflexiv, transitiv und antisymmetrisch ist. Mit dieser Definition ist nicht gesagt, ob sich wirklich alle Elemente x, y ∈ M mit der Relation vergleichen lassen. Man hätte obige Definition daher besser als die Definition einer teilweisen Ordnungsrelation auffassen sollen.

Fordert man zusätzlich, dass sich alle Elemente x, y ∈ M vergleichen lassen, bezeichnet man die Ordnungsrelation als vollständige Ordnungsrelation.

Definition: Eine Ordnungsrelation ⊆ auf einer Menge M heißt vollständige (oder totale) Ordnungsrelation, wenn für alle x, y ∈ M gilt: Es gilt x ⊆ y oder y ⊆ x.

Bemerkung: Eine vollständige Ordnungsrelation wird häufig als lineare Ordnungsrelation bezeichnet. (Man denke dabei etwa an den Zahlenstrahl: die Zahlen lassen sich in einer Linie anordnen. Unten werden dann Diagramme gezeigt für teilweise Ordnungsrelationen, wo sich die Elemente von M nicht mehr linear anordnen lassen.)

Definition: Ist ⊆ eine Ordnungsrelation auf einer Menge M, dann wird (M, ⊆) als Ordnung bezeichnet. Ist ⊆ eine vollständige Ordnungsrelation, dann wird (M, ⊆) als vollständige Ordnung bezeichnet.

Bemerkungen:

Möchte man ausdrücklich sagen, dass eine Ordnung keine vollständige Ordnung ist, wird sie meist als Halbordnung bezeichnet.
Wenn von einer "Ordnung" die Rede ist, ist somit nicht gesagt, ob diese Ordnung vollständig ist oder es sich um eine Halbordnung handelt.

Beispiele:

(Z, ≤) ist eine vollständige Ordnung.
(N, | ) ist eine Halbordnung.
Ist M eine endliche Menge und P(M) die Potenzmenge von M (also die Menge aller Teilmengen von M), dann ist (P(M), ⊆) eine Halbordnung. Es sollte klar sein, dass jetzt ⊆ für die Teilmengenrelation steht.

Minimum und minimales Element

Die folgende Beobachtung über die Rolle der Zahl 1 in den natürlichen Zahlen ist zunächst nur verwirrend, sie wird aber eine wichtige Begriffsbildung liefern, um die Eigenschaften von Halbordnungen besser charakterisieren zu können.

Beispiel: Betrachtet man die natürlichen Zahlen

N = {1, 2, 3, ...},

so kann man die Zahl 1 auf zwei Arten charakterisieren, die völlig gleichwertig erscheinen:

Die Zahl 1 ∈ N ist dadurch ausgezeichnet, dass für alle Zahlen n ∈ N, die ungleich 1 sind, gilt: 1 < n.
Die Zahl 1 ∈ N ist dadurch ausgezeichnet, dass es keine natürliche Zahl k ∈ N gibt mit: k < 1.

♦ ♦ ♦ ♦ ♦

Wo soll der Unterschied der beiden Aussagen über die 1 in N liegen? Das folgende Beispiele zeigt, dass die Aussagen bei Halbordnungen nicht identisch sein müssen.

Beispiel:

Betrachtet man die Teilbarkeitsrelation | auf der Menge N, so gilt:

1|n für alle n ∈ N.
Es gibt kein k ∈ N (außer k = 1) mit: k|1.

Wieder scheinen die Aussagen gleichwertig zu sein.

Betrachtet man aber die Ordnung (N₂, | ) mit N₂ = {2, 3, 4, ...}, so sieht man, dass diese beiden Aussagen nicht ein und dasselbe Element charakterisieren:

Es gibt kein Element n₀ ∈ N₂ mit n₀|n für alle n ∈ N₂. Denn zu jedem n₀ lassen sich Zahlen finden, mit denen n₀ nicht verglichen werden kann.
Jede Primzahl p erfüllt die Bedingung, dass es kein Element k ∈ N₂ gibt (außer k = p) mit: k|p. Denn der einzige Kandidat für k ist 1, die aber nicht in N₂ enthalten ist.

♦ ♦ ♦ ♦ ♦

Um Halbordnungen besser beschreiben zu können, ist es daher nötig Begriffe einzuführen, die Elemente aus obigen Aussagen charakterisieren.

Definition: Ist (M, ⊆) eine Ordnung und N eine Teilmenge von M. Dann heißt n₀ ∈ N Minimum von N, wenn für alle n ∈ N gilt n₀ ⊆ n. Ein Element n₀ heißt minimales Element von N, wenn es kein n ∈ N gibt mit: n ⊆ n₀.

Die Definitionen für Maximum und maximales Element sind analog.

Bemerkungen:

Man beachte, dass ein Minimum von N mit allen Elementen von N vergleichbar sein muss. Dagegen muss ein minimales Element nicht mit allen Elementen von N vergleichbar sein.
Die erste Bemerkung zeigt, dass man nur bei Halbordnungen eine Unterscheidung zwischen Minimum und minimalem Element erwarten kann.
In der Definition ist gesagt, dass N eine Teilmenge von M ist; damit kann auch N = M gelten. Mit der Definition kann also auch ein Minimum von M oder ein minimales Element von M charakterisiert werden.
Die Definition sagt nichts darüber aus, ob und wann ein Minimum beziehungsweise ein minimales Element existieren und ob es eindeutig ist. Die folgenden Beispiele zeigen, dass es hier zahlreiche Möglichkeiten gibt.
Dass ein Minimum (oder Maximum) eindeutig ist, falls es existiert, ist aber leicht zu sehen: Angenommen es gibt in (M, ⊆) zwei Minima m₁ und m₂, dann gilt m₁ ⊆ m₂ und m₂ ⊆ m₁. Beide Ungleichungen können aber nur erfüllt werden, wenn m₁ = m₂. (Die Argumentation kann leicht auf eine Teilmenge N von M übertragen werden. Aber auf minimale (oder maximale) Elemente lässt sich diese Argumentation nicht übertragen (denn zwei minimale Elemente müssen nicht vergleichbar sein).

Beispiele:

Die vollständige Ordnung (Z, ≤) besitzt kein Minimum und kein minimales Element. Betrachtet man dagegen nur eine endliche Teilmenge von Z, so besitzt sie beides. Zum Beispiel hat die Menge {-2, -1, 0, 1, 2} das Minimum -2, das zugleich minimales Element ist. Maximum und maximales Element ist 2.
In der vollständigen Ordnung (N, ≤) ist 1 das Minimum und zugleich minimales Element.
Versieht man die Menge der positiven Teiler von 12, also M₁₂ = {1, 2, 3, 4, 6, 12}, mit der Teilbarkeitsrelation, dann ist (M₁₂, | ) keine vollständige Ordnung, da 4 und 6 nicht vergleichbar sind. Die 1 ist Minimum und minimales Element, 12 ist Maximum und maximales Element.
Versieht man die Menge N = {1, 2, 3, ..., 12} mit der Teilbarkeitsrelation, so ist auch (N, | ) keine vollständige Ordnung. Die Zahl 1 ist immer noch Minimum und minimales Element. Aber 12 ist kein Maximum, da 12 zum Beispiel nicht mit 11 vergleichbar ist. In N existiert kein Maximum. Aber es gibt mehrere maximale Elemente: 12, 11, 10, 9, 8, 7.
Versieht man die Menge N = {2, 3, ..., 12} mit der Teilbarkeitsrelation, so ist auch (N, | ) keine vollständige Ordnung. Jetzt gibt es kein Minimum, aber mehrere minimale Elemente: 2, 3, 5, 7, 11. Ein Maximum gibt es wiederum nicht. Die maximalen Elemente sind jetzt: 12, 11, 10, 9, 8, 7. Man beachte, dass 7 und 11 sowohl minimales als auch maximales Element sind.

Aufgabe:

Im folgenden Abschnitt werden Hasse-Diagramme eingeführt, mit denen sich Ordnungen sehr gut veranschaulichen lassen. Gehen Sie, nachdem Sie die Hasse-Diagramme kennengelernt haben, nochmals zu den obigen Beispielen zurück und skizzieren Sie die zugehörigen Hasse-Diagramme.

Das Hasse-Diagramm

Darstellung einer Ordnungsrelation im Hasse-Diagramm

Als Paradebeispiele für vollständige Ordnungen können (N, ≤) oder (Z, ≤) herangezogen werden: Hier ist es kaum nötig, nach einer graphischen Darstellung zu fragen; denn der Zahlenstrahl ist bekannt und er drückt die Ordnungsrelation treffend aus.

Die Halbordnungen sind hier schon deutlich komplizierter: Die Frage, wann eine Zahl a Teiler einer anderen Zahl b ist, ist noch leicht zu beantworten. Aber wie soll man etwa (N, | ) treffend darstellen? In Abbildung 2 wurden alle geordneten Zahlenpaare der Relation | dargestellt. Und folglich müssen darin alle Informationen über die Teilbarkeitsrelation enthalten sein.

Die folgende Abbildung 3 zeigt dazu nochmals die geordneten Zahlenpaare (a, b) der Teilbarkeitsrelation a|b für b ≤ 16, wobei die Teiler von 12 rot gekennzeichnet sind.

Abbildung 3: Die Teilbarkeitsrelation a|b für b ≤ 16.

Man erkennt in Abbildung 3 zwar sofort die Teiler von 12, aber die Anordnung dieser Teiler von 12 erfolgt gemäß der Ordnungsrelation ≤ und man erkennt am Diagramm zum Beispiel nicht sofort, dass die beiden Teiler 4 und 6 von 12 gemäß der Ordnungsrelation | nicht vergleichbar sind. Wie sie gemäß der Ordnungsrelation | anzuordnen sind, muss man sich selbst erschließen. Daher soll eine treffendere Darstellung gefunden werden, die tatsächlich die Eigenschaften der Ordnungsrelation | zum Ausdruck bringt.

In einem Hasse-Diagramm werden für eine Ordnung (M, ⊆) nicht die geordneten Paare der Relation ⊆, also Zahlenpaare aus M × M dargestellt, sondern nur die Elemente aus M; und zwar so, dass zu jedem Element m ∈ M die unmittelbaren Nachfolger zu sehen sind. Wie aus den besprochenen Beispielen klar geworden ist, können dies beliebig viele Elemente aus M sein.

Aber was genau ist mit unmittelbarer Nachfolger gemeint? Die folgende Abbildung 4 zeigt zunächst drei vollständige Ordnungen als Hasse-Diagramm:

die Menge M = {1, 2, ..., 6}
die natürlichen Zahlen N,
die ganzen Zahlen Z,

jeweils versehen mit der Ordnungsrelation ≤.

Abbildung 4: Hasse-Diagramm für die Ordnungsrelation ≤ auf den Mengen {1, 2, ..., 6}, den natürlichen Zahlen und den ganzen Zahlen.

Wenn wirklich die Ordnungsrelation ≤ dargestellt werden soll, müssten zum Beispiel für die Menge M = {1, 2, ..., 6} alle Ungleichungen x ≤ y gezeichnet werden: Dies sind 5 + 4 + 3 + 2 + 1 = 15 Verbindungen zwischen den Elementen der Menge. Von diesen 15 Verbindungen werden aber nur diejenigen gezeichnet, die ein Element mit dem unmittelbaren Nachfolger verbinden, also 1 mit 2, 2 mit 3 und so weiter.

Man spricht bei dieser Vorgehensweise von transitiver Reduktion; damit ist gemeint, dass zu x ≤ z solange ein Element y gesucht wird, bis es zwischen x und y kein weiteres Element aus M gibt, aber x nicht mit y übereinstimmt.

Man beachte, dass das Verfahren der transitiven Reduktion ins Leere laufen kann: Auf der Menge der rationalen oder der reellen Zahlen gibt es zu keiner Zahl einen unmittelbaren Nachfolger.

Weiter ist zu beachten, dass man die Ordnungsrelation eigentlich durch einen Pfeil kennzeichnen sollte: In Abbildung 4 gilt etwa 1 ≤ 2 und daher sollte die Verbindung zwischen 1 und 2 nicht als Linie, sondern als Pfeil von 1 nach 2 gezeichnet werden. Wenn aus dem Zusammenhang aber klar ist, wie die Anordnung zu lesen ist, kann man die Pfeile weglassen (Hasse-Diagramme werden meist von unten nach oben gezeichnet).

Nachdem die transitive Reduktion erklärt ist, sollen endlich Hasse-Diagramme für eine Halbordnung gezeigt werden. Die folgende Abbildung 5 zeigt die Teilbarkeitsrelation (M, | ) einmal für die Menge M₈ = {1, 2, ..., 8} und einmal für die Menge M₁₆ = {1, 2, ..., 16}.

Abbildung 5: Hasse-Diagramm für natürliche Zahlen z bis 8 beziehungsweise 16 angeordnet gemäß der Teilbarkeitsrelation.

Man erkennt in Abbildung 5:

Geht man von 1 aus, ist jedes Element nur mit seinen unmittelbaren Nachfolgern verbunden; dies sind jeweils die in der Menge enthaltenen Primzahlen.
Dass zwei Elemente a, b vergleichbar sind, also a|b gilt, wird durch eine Verbindung von a nach b ausgedrückt, die von unten nach oben verläuft, etwa 1 und 6 in M₈.
Bei nicht vergleichbaren Elementen kann man keine derartige Verbindung finden, etwa 6 und 8 in M₈ (die Verbindung 8 → 4 → 2 → 6 ist nicht erlaubt, da sie teilweise entgegen der Anordnung verläuft).

Für die Menge M₈ gilt:

Minimum ist 1.
Ein Maximum existiert nicht.
Einziges minimales Element ist 1.
Maximale Elemente sind 8, 7, 6, 5.
Die Teilmenge {1, 2, 4, 8} von M₈ besitzt das Minimum 1 und das Maximum 8, sie sind zugleich minimales beziehungsweise maximales Element.

Für die Menge M₁₆ gilt:

Minimum ist 1.
Ein Maximum existiert nicht.
Einziges minimales Element ist 1.
Maximale Elemente sind 16, 15, 14, 13, 12, 11, 10, 9.
Die Teilmenge {1, 2, 4, 8, 16} von M₁₆ besitzt das Minimum 1 und das Maximum 16, sie sind zugleich minimales beziehungsweise maximales Element.

Darstellung der Teiler einer oder mehrerer Zahlen im Hasse-Diagramm

In Abbildung 5 war die Teilbarkeitsrelation (M, | ) für zwei Mengen M dargestellt. Man kann natürlich auch die Menge M so wählen, dass sie nur aus den Teilern einer Zahl z besteht. In den folgenden Abbildungen 6 und 7 sind die Hasse-Diagramme für die positiven Teiler von z = 99 und z = 60 dargestellt.

Abbildung 6: Hasse-Diagramm für z = 99.

Abbildung 7: Hasse-Diagramm für z = 60.

Aufgaben:

Zeichnen Sie das Hasse-Diagramm für die positiven Teiler von 12!
Wie ist in Abbildung 7 das Hasse-Diagramm zu z = 30 zu erkennen?
Im Hasse-Diagramm zu z = 30 sind in der Anzahl der Elemente auf den verschiedenen Ebenen die Binomialkoeffizienten "k aus 3", mit k = 0, 1, 2, 3 erkennbar, in den anderen Hasse-Diagrammen nicht. Woran liegt das?

Lösungen:

Die erste Aufgabe wird analog zur zweiten Aufgabe gelöst.
Die Teiler von 30 sind eine Teilmenge der Teiler von 60. Daher muss das Hasse-Diagramm zu z = 12 beziehungsweise z = 30 im Diagramm für z = 60 enthalten sein. In Abbildung 8 sind die Verbindungen zwischen den Teilern von 30 rot gekennzeichnet und in Abbildung 9 separat dargestellt.
Die Frage nach den Binomialkoeffizienten wird unten bei den R-Skripten aufgegriffen und wird leichter verständlich, wenn die Teilmengenrelation untersucht wird.

Abbildung 8: Nochmals das Hasse-Diagramm für z = 60; rot gekennzeichnet sind die Verbindungen zwischen den Teilern von 30.

Abbildung 9: Hasse-Diagramm für z = 30.

Man kann jetzt auch die Teiler mehrerer Zahlen in einem Hasse-Diagramm darstellen. Abbildung 10 zeigt die positiven Teiler von 18 und 24.

Abbildung 10: Hasse-Diagramm für die Teiler von 18 und 24.

Aufgabe:

Welche besondere Bedeutung hat der Teiler 6 in Abbildung 10?

R-Skripte

Erzeugen eines Hasse-Diagramms

Hasse-Diagramm für die Teiler einer Zahl

In den Abbildungen 6 und 7 waren die Hasse-Diagramme für die Teiler der Zahlen z = 99 und z = 60 dargestellt. Der Algorithmus zur Erzeugung der Diagramme soll hier nur grob im Pseudocode entwickelt, aber nicht implementiert werden – warum, wird die nächste Aufgabe zeigen.

Der Algorithmus ist nicht schwer zu entwickeln; dazu muss man sich nur selbst die Aufgabe stellen, zu einer Zahl wie etwa z = 60 das Hasse-Diagramm zu zeichnen und sich überlegen, wie man systematisch für beliebiges z vorgehen würde.

Eine grobe Beschreibung der Vorgehensweise könnte wie folgt aussehen:

Man startet mit einer ganzen Zahl z und berechnet aller Teiler von z: k₁, ..., k_n.
Jetzt wird über die Teiler k₁, ..., k_n iteriert: Für manche Teiler k_i wird es andere Teiler geben, die zwischen k_i und z liegen; dabei ist mit "dazwischen liegen" die Anordnung gemäß der Teilbarkeitsrelation gemeint. Teiler, für die es in diesem Sinne kein dazwischen liegendes Element gibt, sind unmittelbare Vorgänger von z. (Beispiel: 30 ist ein unmittelbarer Vorgänger von 60, aber nicht 15, da 30 zwischen 15 und 60 liegt.)
Die Iteration aus dem letzten Schritt liefert zwei Mengen von Teilern von z: die unmittelbaren Vorgänger von z und andere Teiler.
Die unmittelbaren Vorgänger werden in die oberste Ebene des Hasse-Diagramms gezeichnet und mit z verbunden.
Die anderen Teiler werden weiter untersucht; ab hier ist die Vorgehensweise rekursiv. Denn in der verbleibenden Menge an Teilern von z, müssen auch alle Teiler der zu untersuchenden Zahl sein. Und somit kann man wie oben die unmittelbaren Vorgänger suchen und die entsprechende Verbindung ins Diagramm einzeichnen.
Das Diagramm ist vollständig, wenn nur noch der Teiler 1 zu bearbeiten ist, der keinen Vorgänger besitzt.

Man erkennt schnell, dass in dieser Beschreibung des Algorithmus der zweite Schritt der entscheidende Schritt ist:

Zum Einen wird hier von der Transitivität der Teilbarkeitsrelation Gebrauch gemacht: mit ihr erkennt man, ob ein Teiler unmittelbarer Vorgänger von z ist oder nicht. Diese Vorgehensweise wurde oben als transitive Reduktion bezeichnet.
Zum Anderen wird hier – allerdings nur zwischen den Zeilen – angenommen, dass es tatsächlich einen oder mehrere unmittelbare Vorgänger gibt und der Algorithmus sinnvoll fortgesetzt werden kann.

Das folgende Beispiele zeigen, dass die Existenz eines oder mehrerer unmittelbarer Vorgänger nicht in der Tatsache begründet ist, dass eine Ordnungsrelation vorliegt. Man wird eher vermuten, dass die Endlichkeit der zugrundeliegenden Menge verantwortlich ist – hier die Menge der Teiler von z.

Beispiele:

1. Rationale Zahlen: Versieht man die Menge der rationalen Zahlen mit der Ordnungsrelation ≤, so gibt es zu z = 1 keinen unmittelbaren Vorgänger. Denn zu jeder rationalen Zahl x < z gibt es ein natürliche Zahl n, so dass

x < 1 - 1/n < 1.

Somit ist ein "besserer" Vorgänger als z gefunden, aber dieser Prozess kann unendlich fortgesetzt werden.

2. Reelle Zahlen: Dasselbe Problem entsteht natürlich, wenn man die reellen Zahlen mit der Ordnungsrelation ≤ ausstattet. Wie lautet etwa der unmittelbare Vorgänger von π?

Gegen den Algorithmus oben könnte man noch einwenden, dass "er nicht entsprechend der natürlichen Ordnung" vorgeht. Damit ist gemeint, dass die Teilbarkeitsrelation eigentlich den Aufbau des Hasse-Diagramms von unten (beginnend bei 1) nach oben erfolgen müsste und jeweils "unmittelbare Nachfolger" gesucht werden. Man kann sich aber leicht überlegen, dass das Diagramm symmetrisch ist und man eine gleichwertige Vorgehensweise mit einer Suche nach Nachfolgern formulieren kann. Es wird nochmals obiger Algorithmus angegeben, jetzt aber mit dem Start bei Eins.

Um das Hasse-Diagramm zu einer ganzen Zahl z zu bestimmen, berechnet man alle Teiler von z: k₁, ..., k_n.
Jetzt wird über die Teiler k₁, ..., k_n iteriert: Für manche Teiler k_i wird es andere Teiler geben, die zwischen 1 und k_i liegen (gemäß der Teilbarkeitsrelation). Teiler, für die es in diesem Sinne kein dazwischen liegendes Element gibt, sind unmittelbare Nachfolger von 1.
Die Iteration aus dem letzten Schritt liefert zwei Mengen von Teilern von z: die unmittelbaren Nachfolger von 1 und andere Teiler.
Die unmittelbaren Nachfolger werden in die erste Ebene des Hasse-Diagramms gezeichnet und mit 1 verbunden.
Die anderen Teiler werden weiter untersucht; ab hier ist die Vorgehensweise rekursiv: die unmittelbaren Nachfolger werden bestimmt und die entsprechende Verbindung ins Diagramm eingezeichnet.
Das Diagramm ist vollständig, wenn nur noch der Teiler z zu bearbeiten ist, der keinen Nachfolger besitzt und die Spitze des Diagramms bildet.

Aufgaben:

1. Hasse-Diagramm und Primfaktorzerlegung:

Geben Sie für die Hasse-Diagramme zu z = 99 und z = 60 in den Abbildungen 6 und 7 die Primfaktorzerlegung für alle Teiler an.

Kann man an der Primfaktorzerlegung für z ablesen, wie viele Ebenen zwischen z und 1 vorkommen und wie viele Teiler in jeder Ebene stehen?

Welche Symmetrie besitzt das Hasse-Diagramm und wie kann man diese Symmetrie mit der Primfaktorzerlegung von z begründen?

Entwickeln Sie einen Algorithmus zum Erstellen eines Hasse-Diagramms zu einer gegebenen Zahl z, der auf der Primfaktorzerlegung von z beruht.

Diskutieren Sie: Macht es einen Unterschied, ob der Algorithmus bei 1 oder bei z startet?

Diskutieren Sie, ob der Algorithmus einfacher ist als der oben vorgestellte Algorithmus.

2. Hasse-Diagramm und Ordnungsrelation:

Identifizieren Sie in dem oben vorgestellten Algorithmus zum Erstellen des Hasse-Diagramms, an welchen Stellen die Teilbarkeitsrelation eingeht.

Kann der Algorithmus noch verwendet werden, wenn man statt der Teilbarkeitsrelation eine beliebige andere Ordnungsrelation einsetzt?

♦ ♦ ♦ ♦ ♦

Der Algorithmus, der in obiger Aufgabe (mit der Primfaktorzerlegung) angedeutet wird, ist vermutlich deutlich einfacher umzusetzen als der ausführlich vorgestellte Algorithmus zum Erstellen eines Hasse-Diagramms; Er hat aber einen Nachteil: er beruht komplett auf den Eigenschaften der Teilbarkeitsrelation und wie sie mit Primzahlen formuliert werden.

Möchte man ein Hasse-Diagramm zu einer anderen Ordnungsrelation entwickeln, hilft der Algorithmus nicht weiter. Im nächsten Abschnitt wird gezeigt, wie leicht man den oben vorgestellten Algorithmus verallgemeinern kann, so dass man eine beliebige Ordnungsrelation einsetzen kann.

Hasse-Diagramm für eine beliebige Ordnungsrelation

Der oben formulierte Algorithmus soll nun von den speziellen Eigenschaften der Teilbarkeitsrelation bereinigt werden und für eine beliebige Ordnungsrelation ⊆ formuliert werden.

Auf einer endlichen Menge M soll eine Ordnungsrelation ⊆ definiert sein; dabei wird nicht vorausgesetzt, dass es sich um eine vollständige Ordnung handelt.

Man startet mit einem Element z von M und bestimmt alle Elemente x₁, ..., x_n aus M mit: z ⊆ x₁, ..., z ⊆ x_n.
Mit Hilfe der Transitivität von ⊆ lässt sich feststellen, welche Elemente der x₁, ..., x_n unmittelbare Nachfolger von z sind (transitive Reduktion).
Die unmittelbaren Nachfolger von z werden in der ersten Ebene des Hasse-Diagramms eingetragen und mit z verbunden.
Jeder der unmittelbaren Nachfolger von z wird anschließend wie z selbst verarbeitet, wodurch neue Ebenen und neue Verbindungen im Hasse-Diagramm entstehen.

Eine Implementierung dieses Algorithmus mit R soll im folgenden Unterabschnitt vorgestellt werden. Anschließend wird er auf spezielle Ordnungsrelationen angewendet.

Implementierung des Algorithmus zum Erzeugen eines Hasse-Diagramms

Die Hauptfunktion hasse()

Die zentrale Funktion zum Erzeugen des Hasse-Diagramms wird mit hasse() bezeichnet; sie wird dann weitere Hilfsfunktionen aufrufen.

Bevor die Implementierung beginnen kann, muss man festlegen, in welcher Form das Diagramm erzeugt wird beziehungsweise in welcher Form die im Diagramm enthaltene Information ausgegeben oder gespeichert wird.

Hier werden folgende Konventionen verwendet:

Die Abarbeitung startet mit einem Wert z der Menge M; später wird dieses Start-Element dann mit root bezeichnet (Wurzel des Diagramms).
Die Menge M muss als Menge von Zahlen gegeben sein, wobei die Ordnungsrelation ⊆ aber nicht mit der üblichen Anordnung ≤ der Zahlen übereinstimmen muss. Und dies muss auch nicht heißen, dass man nur Ordnungen zwischen Zahlen bearbeiten kann; es heißt lediglich, dass die Elemente von M als Zahlen kodiert werden. (Unten wird dann ein Beispiel folgen, in dem zweidimensionale Vektoren als Zahlen kodiert werden.)
Ausgehend von z werden die Ebenen des Hasse-Diagramms berechnet; die Elemente jeder Ebene werden auf der Konsole ausgegeben.
Da man an den Elementen der Ebene noch nicht erkennt, welche Elemente der benachbarten Ebenen die Vorgänger und Nachfolger sind, wird eine Adjazenz-Matrix berechnet. Hat ein Element x den Nachfolger y, dann hat die Adjazenz-Matrix an der Stelle [x, y] (Zeile x, Spalte y) den Eintrag 1; ist y kein Nachfolger von x, ist der Eintrag gleich 0.
Wahlweise kann die Bearbeitung auch von oben nach unten erfolgen; in der Adjazenz-Matrix sind dann unmittelbare Vorgänger durch die 1 zu erkennen.
Die Bearbeitung bricht ab, entweder wenn alle Elemente von M in das Diagramm eingetragen sind oder wenn kein Element einer Ebene unmittelbare Nachfolger besitzt.

Da eine beliebige Ordnungsrelation ⊆ verarbeitet werden soll, muss man festlegen, in welcher Form diese implementiert werden muss; dies wird sofort am Beispiel der Teilbarkeitsrelation gezeigt.

Die Teilbarkeitsrelation kann folgendermaßen implementiert werden:

isDivisor <- function(x, y){
  return((y %% x) == 0)
}

Sie erhält zwei Zahlen als Eingabewerte und liefert:

den Rückgabewert TRUE , falls x ein Teiler von y ist,
andernfalls den Rückgabewert FALSE .

Mit dieser Implementierung liefert isDivisor() auch dann TRUE , wenn x = 1 oder x = y.

Man erkennt an diesem Beispiel die Anforderungen, die hier an die Implementierung der Ordnungsrelation gestellt werden:

Eingabewerte sind Zahlen, da auch die Menge M aus Zahlen besteht.
Falls die Zahlen gemäß der Ordnungsrelation x ⊆ y angeordnet sind, also x ⊆ y, wird TRUE zurückgegeben.
Für alle anderen Fällen reicht es, FALSE zurückzugeben.

Die letzte Anforderung ist keine Selbstverständlichkeit, denn es gibt Ordnungsrelationen, in denen nicht alle Elemente von M vergleichbar sind. Der Algorithmus in hasse() wird aber immer nur prüfen, ob zwei Elemente x, y gemäß x ⊆ y angeordnet sind oder nicht. Falls "nein" ist keine Unterscheidung nötig, ob x ⊇ y oder ob x und y nicht vergleichbar sind.

Das folgende Skript zeigt die Eingabewerte der Funktion hasse() und ihre Implementierung im Pseudocode angedeutet:

hasse <- function(root, m, relation, adj.incr = TRUE){

  # Adjazenz-Matrix adj vorbereiten
  
  # Zu untersuchende Menge vorbereiten:
    # set: Menge der Elemente, für die alle unmittelbaren Nachfolger 
    # gefunden werden müssen; zu Beginn: set <- root
    # successors: Menge der unmittelbaren Nachfolger; zu Beginn: successors <- NULL
    
   # Iteration: jeder Schleifen-Durchlauf erzeugt eine Ebene des Hasse-Diagramms
    
      # Iteration über die Elemente von set:
        # für jedes Element werden die unmittelbaren Nachfolger bestimmt
        # Zusammenfassen der unmittelbaren Nachfolger zu successors
        # die Einträge in der Adjazenz-Matrix werden erzeugt
        
      # Ausgabe der Elemente der aktuellen Ebene: successors
      # Menge set neu setzen: set <- successors 
      
    # Nach Beendigung der Iteration wird die Adjazenz-Matrix zurückgegeben
return(adj)
}

Die Eingabewerte von hasse() sind:

root : das Element von M, von dem aus das Diagramm aufgebaut werden soll.
m : die Menge M als Vektor.
relation : die Ordnungsrelation.
adj.incr = TRUE : Vorgabe der Richtung, ob ausgehend von root Nachfolger (default) oder Vorgänger gesucht werden sollen; insbesondere im Aufbau der Adjazenz-Matrix muss dies berücksichtigt werden.

Eine mögliche Implementierung für hasse() könnte wie folgt aussehen – die Funktionen, an die einige Aufgaben delegiert werden, werden später erklärt:

hasse <- function(root, m, relation, adj.incr = TRUE){
  
  lgth.m <- length(m)
  
  # Adjazenz-Matrix:
  # kleinstes Element zuerst
  if(adj.incr){
    adj <- matrix( data = 0, nrow = lgth.m, ncol = lgth.m, dimnames = list(m, m) )
  } else {
    # größtes Element zuerst: mit rev() in dimnames
    adj <- matrix(data = 0, nrow = lgth.m, ncol = lgth.m, dimnames = list(rev(m), rev(m)))
  }

  # Mengen setzen
  successors <- NULL   # aktuelle Nachfolger
  set <- root    # Menge, für die die Nachfolger gesucht werden; beginnend bei root

  level <- 1

  while(level < lgth.m){
    # Matrix mit Nachfolgern
    matrix.successors <- getSuccessors(set = set, m = m, relation = relation) 
    if(is.null(matrix.successors)) break()
    # Menge der Nachfolger
    successors <- union(x = NULL, y = matrix.successors[ , 2])
    
    for( r in (1:nrow(matrix.successors)) ){
      v <- matrix.successors[r, ]
      if(adj.incr){
        adj[[as.character(v[1]), as.character(v[2])]] <- 1
      } else {
        adj[[as.character(v[2]), as.character(v[1])]] <- 1
      }
    }
    
    # Ausgabe 
    cat("Level: ", level, " || Nachfolger: ", successors, "\n")

    set <- successors
    level <- level + 1
  }
  return(adj)
}

Nach obigen Vorbereitungen in Pseudocode sollte der Großteil des Quelltextes verständlich sein. Unverständlich sind noch:

Die Funktion getSuccessors(), mit deren Hilfe die Nachfolger bestimmt werden (Zeile 22).
Unklar ist dabei vor allem, in welcher Form die Nachfolger im Rückgabewert von getSuccessors() abgespeichert sind.
Diese Information benötigt man dann auch, um zu verstehen, wie die Komponenten der Adjazenz-Matrix gesetzt werden (Zeile 29 bis 32).

Bevor dies erklärt wird, sollen einfache Anwendungen der Funktion hasse() gezeigt werden:

Ordnungsrelation ≤ mit M = {1, 2, 3, 4, 5}.
Erzeugen des Hasse-Diagramms zu z = 99 und 60.

Ordnungsrelation <= :

le <- function(x, y){
  return(x <= y)
}

hasse(root = 1, m = (1:5), relation = le)
# Level:  1  || Nachfolger:  2 
# Level:  2  || Nachfolger:  3 
# Level:  3  || Nachfolger:  4 
# Level:  4  || Nachfolger:  5 
#   1 2 3 4 5
# 1 0 1 0 0 0
# 2 0 0 1 0 0
# 3 0 0 0 1 0
# 4 0 0 0 0 1
# 5 0 0 0 0 0

Zur Erklärung:

Zeile 1 bis 3: Die Funktion le() implementiert die Ordnungsrelation ≤.

Zeile 5: Für die Menge der Zahlen von 1 bis 5 soll ausgehend von root = 1 das Hasse-Diagramm erstellt werden.

Zeile 6 bis 9: Jede Ebene enthält nur ein Element; das Element root wird nicht ausgegeben. Die Ausgabe endet mit dem letzten Element 5.

Zeile 10 bis 15: Die Adjazenz-Matrix ist leicht zu lesen:

Die erste Zeile und die erste Spalte stehen für das Attribut dimnames, das die Werte 1 bis 5 annimmt.
Die Einträge der Matrix können nur die Werte 0 und 1 annehmen.
Die erste Zeile der Matrix ist zu lesen: das Element 1 hat als Nachfolger nur das Element 2.
Die zweite Zeile besagt, dass 2 den Nachfolger 3 hat und so weiter.

Anwendung: Hasse-Diagramm zu den Teilern von 99 beziehungsweise 60

divisors <- getRelatedElements(m = (1:99), x = 99, relation = isDivisor)
divisors
# [1]  1  3  9 11 33 99

h.1.99 <- hasse(root = 1, m = divisors, relation = isDivisor)
# Level:  1  || Nachfolger:  3 11 
# Level:  2  || Nachfolger:  9 33 
# Level:  3  || Nachfolger:  99

h.1.99
#   1 3 9 11 33 99
# 1  0 1 0  1  0  0
# 3  0 0 1  0  1  0
# 9  0 0 0  0  0  1
# 11 0 0 0  0  1  0
# 33 0 0 0  0  0  1
# 99 0 0 0  0  0  0

In Zeile 1 werden die Teiler von 99 mit Hilfe der Funktion getRelatedElements() berechnet (diese Funktion wurde in Ganzzahl-Division: Kongruenzen und Restklassen als Beispiele für Äquivalenzrelationen und Äquivalenzklassen besprochen: sie sucht aus der Menge m diejenigen Elemente, die zu x in der Beziehung relation stehen).

Die restlichen Ausgaben sollten sich (zusammen mit Abbildung 6) selbst erklären. Man erkennt, dass die in den Ausgaben (cat()-Befehle zur Ausgabe der Nachfolger in jeder Ebene) eigentlich überflüssig ist, da man diese Information auch der Adjazenz-Matrix entnehmen kann – allerdings etwas umständlich.

Ebenso sollte sich das folgende Skript (zusammen mit Abbildung 7) selbst erklären:

divisors <- getRelatedElements(m = (1:60), x = 60, relation = isDivisor)
divisors
# [1]  1  2  3  4  5  6 10 12 15 20 30 60

h.1.60 <- hasse(root = 1, m = divisors, relation = isDivisor)
# Level:  1  || Nachfolger:  2 3 5 
# Level:  2  || Nachfolger:  4 6 10 15 
# Level:  3  || Nachfolger:  12 20 30 
# Level:  4  || Nachfolger:  60

h.1.60
#    1 2 3 4 5 6 10 12 15 20 30 60
# 1  0 1 1 0 1 0  0  0  0  0  0  0
# 2  0 0 0 1 0 1  1  0  0  0  0  0
# 3  0 0 0 0 0 1  0  0  1  0  0  0
# 4  0 0 0 0 0 0  0  1  0  1  0  0
# 5  0 0 0 0 0 0  1  0  1  0  0  0
# 6  0 0 0 0 0 0  0  1  0  0  1  0
# 10 0 0 0 0 0 0  0  0  0  1  1  0
# 12 0 0 0 0 0 0  0  0  0  0  0  1
# 15 0 0 0 0 0 0  0  0  0  0  1  0
# 20 0 0 0 0 0 0  0  0  0  0  0  1
# 30 0 0 0 0 0 0  0  0  0  0  0  1
# 60 0 0 0 0 0 0  0  0  0  0  0  0

Zuletzt soll noch ein umfangreicheres Beispiel gezeigt werden:

divisors <- getRelatedElements(m = (1:60060), x = 60060, relation = isDivisor)
length(divisors)
# [1] 96

h.1.60060 <- hasse(root = 1, m = divisors, relation = isDivisor)
# Level:  1  || Nachfolger:  2 3 5 7 11 13 
# Level:  2  || Nachfolger:  4 6 10 14 22 26 15 21 33 39 35 55 65 77 91 143 
# Level:  3  || Nachfolger:  12 20 28 44 52 30 42 66 78 70 110 130 154 182 286 105 165 195 231 273 429 385 455 715 1001 
# Level:  4  || Nachfolger:  60 84 132 156 140 220 260 308 364 572 210 330 390 462 546 858 770 910 1430 2002 1155 1365 2145 3003 5005 
# Level:  5  || Nachfolger:  420 660 780 924 1092 1716 1540 1820 2860 4004 2310 2730 4290 6006 10010 15015 
# Level:  6  || Nachfolger:  4620 5460 8580 12012 20020 30030 
# Level:  7  || Nachfolger:  60060

Die Adjazenz-Matrix ist jetzt eine 96 × 96 Matrix – sie ist zu umfangreich, um sie hier wiederzugeben.

Hilfsfunktionen zur Berechnung der unmittelbaren Nachfolger

Damit zur Funktion getSuccessors(), die die Nachfolger zu einer gegebenen Ebene im Hasse-Diagramm berechnet:

getSuccessors <- function(set, m, relation){
  
  result <- NULL    # Matrix mit 2 Spalten und unbekannter Anzahl Zeilen. 
  # 1. Spalte: Element aus set, 2. Spalte dessen Nachfolger
  
  for(s in set){
    successors <- successor(x = s, m = m, relation)
    result <- rbind(result, successors)
  }
  
  return(result)
}

Man sieht beim Aufruf von getSuccessors() in Zeile 22 von hasse(), dass die Eingabewerte m und relation einfach von hasse() weitergereicht werden; sie stehen für die Menge M und die darauf definierte Ordnungsrelation ⊆.

Der Eingabewert set steht für diejenigen Elemente, für die die unmittelbaren Nachfolger berechnet werden sollen.

Da man später die Information benötigt, welches Element aus set welchen Nachfolger hat, reicht es nicht, alle Nachfolger zusammengefasst in einem Vektor zurückzugeben – dabei würde gerade diese Zuordnung verloren gehen. Deshalb wird eine Matrix mit 2 Spalten erzeugt:

in der ersten Spalte steht jeweils das Element aus set,
in der zweiten Spalte der unmittelbare Nachfolger.

Gibt es mehrere unmittelbare Nachfolger zu einem Element, werden mehrere Zeilen erzeugt (Iteration über die Menge set in Zeile 6 bis 9).

Man erkennt an diesem Quelltext nicht ausdrücklich, dass der Rückgabewert eine Matrix ist, lediglich die Verwendung der Funktion rbind() gibt den Hinweis darauf. Die Aufgabe, den Nachfolger zu einem Element von set zu finden, wird an die Funktionen successor() und isImmediateSucc() delegiert (siehe Aufruf von successor() in Zeile 7):

successor <- function(x, m, relation){
  result <- NULL   # Matrix mit 2 Spalten und unbekannter Anzahl Zeilen.
  
  # Menge M \ {x} iterieren mit index d
  # falls d == x: kein Nachfolger
  # falls relation(x, d): d ist Kandidat für Nachfolger
  # Aber: jetzt genauer prüfen (diese Prüfung übernimmt isImmediateSucc()):
    # falls es ein Element zwischen x und d gibt, also x|d1 und d1|d, dann ist d kein Nachfolger
    # gibt es kein solches d1: d ist Nachfolger
  
  m.x <- setdiff(x = m, y = x)    # Menge m ohne x
  for(d in m.x){
    if( relation(x = x, y = d)  ){  # d ist Kandidat 
      cond <- isImmediateSucc(x = x, cand = d, m = m.x, relation)
      if( cond ){
        result <- rbind(result, c(x, d))
      }
    }
  }
  return(result)
}

isImmediateSucc <- function(x, cand, m, relation){
  # Beachte: man weiss, dass x <= cand, sonst wäre die Funktion nicht aufgerufen worden
  # Und es wurde mit m.x, also "m ohne x" aufgerufen
  result <- TRUE
  
  for(d in m){
    # condition besagt, dass es ein Element d zwischen x und cand gibt
    condition <- ( relation(x = x, y = d) && relation(x = d, y = cand) && !identical(x,d) && !identical(d, cand) )

    if(condition) {
      result <- FALSE
      break()
    } 
  }    # Ende for
  return(result)
}

Die Arbeitsweise der beiden Funktionen ist in den Kommentaren erklärt, salopp gesagt sorgen sie für die transitive Reduktion:

successor() iteriert über alle Elemente von M und sucht zu x diejenigen Kandidaten cand, die die Ordnungsrelation x ⊆ cand erfüllen.
isImmediateSucc() prüft mit der Transitivität, ob cand tatsächlich ein unmittelbarer Nachfolger ist.
Für die unmittelbaren Nachfolger wird in successor() ein Eintrag in die Matrix erzeugt (siehe Zeile 16), die später zurückgegeben wird (Zeile 20).

Aufgabe:

Welche Bedeutung hat die Bedingung condition, die in Zeile 30 definiert wird?

Warum kann man in Zeile 34 den break-Befehl einsetzen?

Implementierung einer speziellen Ordnungsrelation

Die besprochene Funktion hasse() scheint den zu untersuchenden Ordnungsrelationen eine große Einschränkung aufzuerlegen: Die Menge M, auf der die Ordnungsrelation definiert ist, muss als Vektor m der Funktion hasse() übergeben werden. Damit sind aber als Elemente von M nur Zahlen zugelassen.

Das folgende Beispiel zeigt eine Ordnungsrelation, die auf einer Menge M von Vektoren definiert ist (also keine Zahlen wie oben gefordert). Durch eine geeignete Kodierung der Vektoren kann erreicht werden, dass die Funktion hasse() nicht neu implementiert werden muss – man benötigt lediglich die Hilfsfunktionen zum Kodieren und Dekodieren der Vektoren.

Die Menge M und die Ordnungsrelation ⊆

Die zu implementierende Ordnungsrelation kann man leicht an einem Glücksspiel zwischen zwei Spielern A und B mit einem Würfel veranschaulichen:

Jeder Spieler wirft den Würfel zweimal nacheinander und notiert die beiden Ergebnisse: (a₁, a₂) für A und (b₁, b₂) für B.
Damit Spieler A gewinnt, muss
- entweder a₁ > b₁ und a₂ ≥ b₂
- oder a₁ ≥ b₁ und a₂ > b₂ gelten.
Damit B gewinnt, müssen in den Bedingungen die Ungleichheitszeichen umgekehrt werden.
Dabei gibt es viele Ergebnisse, bei denen keine Entscheidung fällt, zum Beispiel (3, 4) für A und (5, 2) für B; in diesem Fall ist das Spiel unentschieden (und die Einsätze gehen in den Jackpot).

Beispiele:

(a₁, a₂) = (4, 3) und (b₁, b₂) = (3, 3): A gewinnt.

(a₁, a₂) = (4, 3) und (b₁, b₂) = (4, 3): unentschieden.

(a₁, a₂) = (4, 3) und (b₁, b₂) = (5, 2): unentschieden.

(a₁, a₂) = (4, 3) und (b₁, b₂) = (5, 4): B gewinnt.

Da für das Spiel hier nicht die Anzahl möglicher Gewinne oder unentschiedener Ausgänge oder gar die Gewinn-Wahrscheinlichkeiten untersucht werden soll, sind die Einsätze irrelevant.

Für die Untersuchungen hier ist nur die Ordnungsrelation ⊆ relevant, die durch die Spielregeln auf der Menge M der möglichen Spielausgänge entsteht; es gilt:

(a₁, a₂) ⊆ (b₁, b₂), falls a₁ ≤ b₁ und zugleich a₂ ≤ b₂, wobei alle Einzel-Würfe die Werte 1, 2, ..., 6 annehmen können.

Um jedes Element der Menge M als Zahl zu kodieren, geht man folgendermaßen vor:

Von jedem Ergebnis des Würfelns wird 1 abgezogen: (x₁, x₂) → (x₁ - 1, x₂ - 1) = (y₁, y₂).
Der Vektor (y₁, y₂) wird als Zahl im Zahlensystem zur Basis 6 interpretiert, zum Beispiel steht y₁ für die Sechser und y₂ für die Einer; dadurch erhält man eine Zahl z = y₁ · 6 + y₂.
Die Zahlen z können jetzt Werte von 0 bis 35 annehmen und die Zuordnung zwischen z und (x₁, x₂) ist in beide Richtungen eindeutig.

Die folgenden Skripte zeigen die Umrechnungen zwischen (x₁, x₂) und z und umgekehrt (unsinnige Eingaben werden nicht abgefangen):

# Kodieren eines Vektors (v1, v2), v1, v2 = 1, 2, ..., 6
code <- function(v){
  v <- v - 1
  return(v[1] * 6 + v[2])
}

# Dekodieren einer Zahl z = 0, 1, ..., 35 
decode <- function(z){
  v <- vector(mode = "integer", length = 2)
  v[1] <- z %/% 6
  v[2] <- z %% 6 
  return(v + 1)
}

# Test der Kodierung:

for(i in (0:35)){
  v <- decode(i)
  z <- code(v)
  cat("Würfeln: ", v, " || Kodierung: ", z, "\n")
}
# Würfeln:  1 1  || Kodierung:  0 
# Würfeln:  1 2  || Kodierung:  1 
# Würfeln:  1 3  || Kodierung:  2 
# Würfeln:  1 4  || Kodierung:  3 
# Würfeln:  1 5  || Kodierung:  4 
# Würfeln:  1 6  || Kodierung:  5 
# Würfeln:  2 1  || Kodierung:  6 
# Würfeln:  2 2  || Kodierung:  7 
# Würfeln:  2 3  || Kodierung:  8 
# Würfeln:  2 4  || Kodierung:  9 
# Würfeln:  2 5  || Kodierung:  10 
# Würfeln:  2 6  || Kodierung:  11 
# Würfeln:  3 1  || Kodierung:  12 
# Würfeln:  3 2  || Kodierung:  13 
# Würfeln:  3 3  || Kodierung:  14 
# Würfeln:  3 4  || Kodierung:  15 
# Würfeln:  3 5  || Kodierung:  16 
# Würfeln:  3 6  || Kodierung:  17 
# Würfeln:  4 1  || Kodierung:  18 
# Würfeln:  4 2  || Kodierung:  19 
# Würfeln:  4 3  || Kodierung:  20 
# Würfeln:  4 4  || Kodierung:  21 
# Würfeln:  4 5  || Kodierung:  22 
# Würfeln:  4 6  || Kodierung:  23 
# Würfeln:  5 1  || Kodierung:  24 
# Würfeln:  5 2  || Kodierung:  25 
# Würfeln:  5 3  || Kodierung:  26 
# Würfeln:  5 4  || Kodierung:  27 
# Würfeln:  5 5  || Kodierung:  28 
# Würfeln:  5 6  || Kodierung:  29 
# Würfeln:  6 1  || Kodierung:  30 
# Würfeln:  6 2  || Kodierung:  31 
# Würfeln:  6 3  || Kodierung:  32 
# Würfeln:  6 4  || Kodierung:  33 
# Würfeln:  6 5  || Kodierung:  34 
# Würfeln:  6 6  || Kodierung:  35

Die Kodierung der Vektoren hat eine einfache Konsequenz für z:

Wird die erste Komponente in (x₁, x₂) um 1 erhöht, wächst z um 6.
Wird die zweite Komponente in (x₁, x₂) um 1 erhöht, wächst z um 1.

Diese Aussagen charakterisieren aber zugleich die unmittelbaren Nachfolger:

Ein Vektor (x₁, x₂) hat die beiden unmittelbaren Nachfolger (x₁ + 1, x₂) und (x₁, x₂ + 1).
Eine Zahl z hat die beiden unmittelbaren Nachfolger z + 1 und z + 6.

Dabei sind die Summen nur dann zu bilden, wenn die Menge M nicht verlassen wird.

Mit diesen Vorüberlegungen ist es nicht mehr schwer, eine Implementierung le.2dice() der Ordnungsrelation anzugeben; man kann zum Vergleich zweier Zahlen sogar die umständliche Subtraktion von 1 weglassen. Die Umrechnung einer Zahl in einen Vektor mit Komponenten im Zahlensystem zur Basis 6 übernimmt die Funktion decToSix():

# Umrechnung x -> (v1, v2)
decToSix <- function(x){
  v <- vector(mode = "integer", length = 2)
  v[1] <- x %/% 6
  v[2] <- x%% 6
  return(v)
}

# Ordnungsrelation
le.2dice <- function(x, y){
  v.x <- decToSix(x = x)
  v.y <- decToSix(x = y)
  if(all(v.x <= v.y)) return(TRUE)
  else return(FALSE)
}

Man beachte in der Implementierung der Ordnungsrelation die Zeilen 13 und 14:

TRUE wird zurückgegeben, wenn beide Komponenten mit ≤ angeordnet werden können.
In allen anderen Fällen wird FALSE zurückgegeben.

Es ist nicht nötig, den Fall unvergleichbarer Elemente zu berücksichtigen (etwa mit Rückgabewert NA), da in der Implementierung von hasse() immer nur geprüft wird, ob ⊆ vorliegt oder nicht.

Das Hasse-Diagramm für die Ordnungsrelation

Nach den Vorbereitungen kann das Hasse-Diagramm für die Ordnungsrelation des Würfelspiels erzeugt werden. Die Funktion hasse() wird mit der Menge m = (0:35) und der Ordnungsrelation relation = le.2dice aufgerufen:

h.2dice <- hasse(root = 0, m = (0:35), relation = le.2dice)
# Level:  1  || Nachfolger:  1 6 
# Level:  2  || Nachfolger:  2 7 12 
# Level:  3  || Nachfolger:  3 8 13 18 
# Level:  4  || Nachfolger:  4 9 14 19 24 
# Level:  5  || Nachfolger:  5 10 15 20 25 30 
# Level:  6  || Nachfolger:  11 16 21 26 31 
# Level:  7  || Nachfolger:  17 22 27 32 
# Level:  8  || Nachfolger:  23 28 33 
# Level:  9  || Nachfolger:  29 34 
# Level:  10  || Nachfolger:  35 

print(x = h.2dice, max =  37*37)
#    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
# 0  0 1 0 0 0 0 1 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 1  0 0 1 0 0 0 0 1 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 2  0 0 0 1 0 0 0 0 1 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 3  0 0 0 0 1 0 0 0 0 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 4  0 0 0 0 0 1 0 0 0 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 5  0 0 0 0 0 0 0 0 0 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 6  0 0 0 0 0 0 0 1 0 0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 7  0 0 0 0 0 0 0 0 1 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 8  0 0 0 0 0 0 0 0 0 1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 9  0 0 0 0 0 0 0 0 0 0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 10 0 0 0 0 0 0 0 0 0 0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 11 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 12 0 0 0 0 0 0 0 0 0 0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 13 0 0 0 0 0 0 0 0 0 0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 14 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 15 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# 16 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0
# 17 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0
# 18 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0
# 19 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0
# 20 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0
# 21 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0
# 22 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0
# 23 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0
# 24 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0
# 25 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0
# 26 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0
# 27 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0
# 28 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0
# 29 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
# 30 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0
# 31 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0
# 32 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0
# 33 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0
# 34 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
# 35 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

An den Konsolen-Ausgaben kann man die oben formulierten Regeln über die unmittelbaren Nachfolger leicht nachvollziehen. Die Adjazenz-Matrix wird als h.2dice abgespeichert und zur Ausgabe wird die Option max = 37*37 gesetzt, um alle Komponenten der Matrix auszugeben.

Aufgaben:

Erzeugen Sie die Adjazenz-Matrix wie oben, aber mit der Option adj.incr = FALSE und diskutieren Sie die Unterschiede.
Implementieren Sie für das Würfelspiel die Ordnungsrelation "lexikographische Anordnung" und erzeugen Sie damit die Adjazenz-Matrix!

Lösung von Abzählproblemen mit Hilfe des Hasse-Diagramms

Abzählprobleme werden systematisch in Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme und Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik untersucht. Hier soll – ohne eine systematische Darstellung anzustreben – gezeigt werden, wie man derartige Abzählprobleme mit Hilfe des Hasse-Diagramms angehen kann.

Abbildung 11 zeigt das Hasse-Diagramm, für das oben bereits die Adjazenz-Matrix berechnet wurde; in der Mitte und rechts sind die Würfel-Ergebnisse sowie ihre Kodierung zu sehen.

Abbildung 11: Links: Hasse-Diagramm für die beschriebene Ordnungsrelation, die die Ergebnisse beim zweimaligen Würfeln anordnet. Mitte: Angedeutet sind einige Ergebnisse beim Würfeln. Man beachte, dass das Diagramm achsensymmetrisch ist und es daher unerheblich ist, wie die Zeilen sortiert werden. Rechts: Kodierung der Würfel-Ergebnisse mit den Zahlen von 0 bis 35. Da die Kodierung auf dem Zahlensystem zur Basis 6 beruht, kann man die Kodierung durch Division durch 6 und Restbildung leicht entschlüsseln.

Nachdem oben diese spezielle Ordnungsrelation ⊆ an einem Würfelspiel motiviert wurde, sind folgende Fragestellungen naheliegend:

Es spielen A und B gegeneinander: Wie viele mögliche Spielausgänge N gibt es insgesamt?
Bei wie vielen Spielen gewinnt A? Diese Anzahl wird mit N_A bezeichnet.
Bei wie vielen Spielen gewinnt B? Diese Anzahl wird mit N_B bezeichnet.
Bei wie vielen Spielen ist der Ausgang unentschieden? Diese Anzahl wird mit N_U bezeichnet.
Ist der Ausgang der Würfe von A bekannt, also a = (a₁, a₂), kann man weiter fragen:
1. Wie viele Möglichkeiten gibt es jetzt dafür, dass A gewinnt?
2. Wie viele Möglichkeiten gibt es jetzt dafür, dass B gewinnt?
3. Wie viele Möglichkeiten gibt es jetzt dafür, dass das Spiel unentschieden ausgeht?

Es ist klar, dass

N = N_A + N_B + N_U

und dass aus Symmetriegründen gilt:

N_A = N_B.

Entsprechend addieren sich die gesuchten Anzahlen bei der Frage zu einem speziellen Wurf von A.

Diese Fragestellungen sollen jetzt – soweit möglich – in Fragestellungen über die Ordnungsrelation ⊆ umformuliert werden.

Da es für Spieler A beim zweimaligen Würfeln 6 · 6 = 36 Spielausgänge gibt und ebenso viele für B, gibt es insgesamt

N = 36 · 36 = 1 296 mögliche Spielausgänge.

Brute-force Algorithmus

Als erster Ansatz wird ein brute-force Algorithmus vorgestellt. Kodiert man ihre Ergebnisse mit den Zahlen von 0 bis 35, so reicht es alle möglichen Kombinationen zu bilden und mit Hilfe der Relation ⊆ zu vergleichen, wer gewonnen hat (beziehungsweise ob das Spiel unentschieden ist).

Dazu bereitet man eine 36 × 36 Matrix vor, deren Werte zunächst 0 gesetzt werden (Zeile 2 bis 5).

In einer Doppelschleife (Zeile 8 und 9) werden ihre Werte gesetzt: Immer wenn B gewinnt, wird die entsprechende Komponente der Matrix auf 1 gesetzt. Zählt man anschließend die Komponenten, die gleich 1 sind, hat man N_B bestimmt. Und wie oben gesagt wurde, sind dann auch N_A und N_U bekannt.

# Matrix erzeugen:
v <- (0:35)
lgth.v <- length(v)

m.b <- matrix(data = 0, nrow = lgth.v, ncol = lgth.v)

# Matrix setzen für "B gewinnt"
for(a in v){
  for(b in v){
    if(a != b){   # gleiches Ergebnis: unentschieden
      m.b[a + 1, b + 1] <- as.integer(le.2dice(a, b))
    }
  }
}

# Auswertung:
b.wins <- sum(m.b)
b.wins
# 405
draw <- lgth.v * lgth.v - 2 * b.wins
draw
# 486

Die entscheidenden Zeilen sind 10 und 11: Falls a ungleich b ist (unentschieden!), wird mit Hilfe der bereits implementierten Ordnungsrelation le.2dice() festgestellt, ob B gewinnt.

Das Ergebnis ist:

Von den insgesamt N = 1 296 Spielen enden jeweils N_A = 405 = N_B mit einem Sieg von A beziehungsweise B und N_U = 486 Spiele enden unentschieden.

Der Algorithmus ist ein echter brute-force-Algorithmus, der keinerlei spezielle Eigenschaften der hier vorliegenden Ordnungsrelation verwendet, sondern nur auf dem Abzählen sämtlicher Spielausgänge und der Verwendung der Funktion le.2dice() beruht. Es ist auch klar, dass er mit einem sehr hohen Rechnenaufwand verbunden ist.

Es sollen jetzt ein Algorithmus vorgestellt werden, der auf die spezielle Struktur der Ordnungsrelation ⊆ zugeschnitten ist.

Spezieller Abzähl-Algorithmus

Abbildung 11 zeigt, dass das Hasse-Diagramm quadratisch ist und nur durch die übliche Darstellung (Minimum unten, Maximum oben) als Raute wirkt. Abbildung 12 zeigt, wie man das Hasse-Diagramm entlang der Achsen a₁ und a₂ aufbaut und das folgende Skript zeigt, wie man die Kodierung der Elemente berechnet. Man beachte, dass die Wahl der Achsen und ihre Orientierung unerheblich ist, denn keine der hier behandelten Fragen hängt von der Reihenfolge der Würfe ab. Die Achsen werden so gewählt, dass man die Ergebnisse der Matrizen-Rechnungen leichter mit den Diagrammen in Verbindung bringen kann.

Abbildung 12: Links: Das Hasse-Diagramm in der üblichen Darstellung; eingetragen sind die Eckpunkte mit ihrer Kodierung. Rechts: Das Hasse-Diagramm wird gedreht; die ursprüngliche Symmetrie-Achse wird jetzt zur Hauptdiagonalen. Diese Darstellung ist an die folgenden Berechnungen angepasst, die mit 6 × 6 Matrizen ausgeführt werden.

a <- (1:6)

m.hasse <- outer(X = a, Y = a, FUN = function(x, y){ return( (x - 1)  + (y - 1) * 6 ) })

m.hasse
#       [,1] [,2] [,3] [,4] [,5] [,6]
# [1,]    0    6   12   18   24   30
# [2,]    1    7   13   19   25   31
# [3,]    2    8   14   20   26   32
# [4,]    3    9   15   21   27   33
# [5,]    4   10   16   22   28   34
# [6,]    5   11   17   23   29   35

Abbildung 13 zeigt einen speziellen Punkt im Hasse-Diagramm, hier a = (4, 3) mit der Kodierung x = 20. Eingezeichnet sind 3 Punktmengen:

Alle Punkte b mit b ⊂ a. Wenn Spieler B eines dieser Ergebnisse erzielt, gewinnt A.
Alle Punkte b mit a ⊂ b. Wenn Spieler B eines dieser Ergebnisse erzielt, gewinnt B.
Alle Punkte b, die nicht mit a vergleichbar sind. Wenn Spieler B eines dieser Ergebnisse erzielt, ist das Spiel unentschieden.

Abbildung 13: Links: Jeder Punkt a im Hasse-Diagramm zerlegt das Diagramm in drei Mengen: Punkte echt unterhalb von a, Punkte echt oberhalb von a und Punkte, die nicht mit a vergleichbar sind. Mitte: zum Punkt a = 20 sind die Mächtigkeiten dieser drei Mengen angegeben. Rechts: Die angedeutete Darstellung der drei Mengen im gedrehten Hasse-Diagramm.

Die Mächtigkeiten der Punktmengen sind in Abbildung 13 angegeben. Wichtiger als diese Zahlen ist hier, wie man sie im allgemeinen Fall berechnet. Man erkennt, dass die Punktmengen Rechtecke sind oder aus solchen zusammengesetzt sind. Daher kann man die Anzahl der enthaltenen Punkte durch einfache Multiplikation der Seitenlängen berechnen; anschließend muss 1 abgezogen werden, da der Ausgangspunkt nicht zur Menge gerechnet wird.

Man kann jetzt für jeden Punkt a im Hasse-Diagramm berechnen:

Wie viele Punkte liegen echt unterhalb von a?

(Wenn B ein derartiges Ergebnis erzielt, gewinnt A.) Da ein Punkt a durch seine Koordinaten a₁ und a₂ beschrieben wird, erhält man für die gesuchte Anzahl:

a₁ · a₂ - 1.

(Die 1 wird abgezogen, da a nicht zur Menge gerechnet wird.)

Das folgende Skript berechnet diese Anzahlen für alle Punkte a:

a <- (1:6)

m.le <- outer(X = a, Y = a, FUN = function(x, y){ return(x * y - 1) })

m.le
#      [,1] [,2] [,3] [,4] [,5] [,6]
# [1,]    0    1    2    3    4    5
# [2,]    1    3    5    7    9   11
# [3,]    2    5    8   11   14   17
# [4,]    3    7   11   15   19   23
# [5,]    4    9   14   19   24   29
# [6,]    5   11   17   23   29   35

sum(m.le)
# 405

Die Matrix m.le muss symmetrisch zur Hauptdiagonalen sein. Die Nebendiagonalen entsprechen den Ebenen des Hasse-Diagramms, wenn es als Raute gezeichnet wird.

Summiert man die Komponenten der Matrix m.le auf, erhält man die Anzahl der Möglichkeiten N_A, bei denen A gewinnt. Daraus lassen sich wieder die anderen Anzahlen berechnen.

Aufgabe:

Die letzten Berechnungen haben ein sehr viel besseres Verständnis für die Struktur des Hasse-Diagramms erzeugt – und wie man damit Abzählprobleme löst – als der brute-force-Algorithmus. Mit diesem Verständnis kann man jetzt versuchen, die Anzahl N_A allgemein zu berechnen; "allgemein" soll ausdrücken, dass man anstelle der Anzahl b = 6 der möglichen Ergebnisse beim Würfeln die Anzahl N_A in Abhängigkeit von b = 2, 3, ... berechnet.

Führen Sie die Summation, die das letzte Skript erledigt hat, allgemein aus!

Hinweis: Dazu ist nicht mehr nötig als "der kleine Gauß", also die Formel für die Summe der ganzen Zahlen:

1 + 2 + ... + b = b · (b + 1) / 2.

Man erhält:

N_A(b) = b² · (b - 1)² / 4 - b² · (b - 1).

Die folgende Tabelle zeigt die Ergebnisse für b = 2, ..., 10:

b	N	N_A(b)	N_U(b)
2	16	5	6
3	81	27	27
4	256	84	88
5	625	200	225
6	1296	405	486
7	2401	735	931
8	4096	1232	1632
9	6561	1944	2673
10	10000	2925	4150

Weiteres Beispiel: Die Teilmengenrelation

Potenzmenge

Im Folgenden wird eine Menge M_n mit n Elementen betrachtet, n = 1, 2, .... Die Elemente von M werden durchnumeriert, da ihre Bedeutung für die Überlegungen unerheblich ist:

M_n = {1, 2, ..., n}.

Die Potenzmenge P(M_n) ist die Menge aller Teilmengen von M_n:

P(M_n) = {{}, {1}, {2}, ..., {1, 2}, ..., {1, n}, ..., {n-1, n}, ..., {1, ..., n}}.

Man kann leicht nachzählen, dass die Potenzmenge aus 2ⁿ Mengen besteht.

Stattet man die Potenzmenge P(M_n) mit der Teilmengenrelation ⊆ aus, erhält man eine partielle Ordnungsrelation.

Aufgabe: Zeigen Sie, dass die Teilmengenrelation ⊆ auf der Potenzmenge P(M_n) einer n-elementigen Menge M_n reflexiv, transitiv und antisymmetrisch ist. Zeigen Sie zudem, dass die Ordnungsrelation nicht vollständig ist.

Implementierungen der Teilmengenrelation und Darstellung im Hasse-Diagramm

Die Implementierung der Teilmengenrelation als Ordnungsrelation, die feststellt, ob eine Menge A in einer Menge B enthalten ist, ist sehr einfach. Das folgende Skript zeigt die Ordnungsrelation isSubset(a, b):

isSubset <- function(a, b){

  # Gleichheit der Mengen: TRUE
  if( setequal(x = a, y = b)){
    return(TRUE)
  } else {
    v = vector(length = length(a))
    
    # Für jedes Element von a prüfen, ob es ein b enthalten ist:
    for( i in (1:length(a)) ){
      v[i] <- is.element(el = a[i], set = b)
    }
    if( all(v) ){
      return(TRUE)
    } else {
      return(FALSE)
    }
  }
}

Die Eingabewerte sind zwei Vektoren a und b und es wird geprüft, ob die Teilmengenrelation ⊆ erfüllt ist, wenn man die Vektoren als Mengen interpretiert.

Deutlich schwieriger ist es, eine geeignete Kodierung der Teilmengen anzugeben, um die oben entwickelte Funktion hasse() einzusetzen. Die folgende Abbildung 14 zeigt das Hasse-Diagramm zur Menge M₃ = {1, 2, 3}.

Abbildung 14: Hasse-Diagramm zur Teilmengenrelation auf der Potenzmenge von M<sub>3</sub> = {1, 2, 3}.

Abbildung 14: Hasse-Diagramm zur Teilmengenrelation auf der Potenzmenge von M₃ = {1, 2, 3}.

Das Diagramm suggeriert zwei mögliche Kodierungen:

Jede Teilmenge aus P(M₃) wird durch eine dreistellige Dualzahl kodiert, die wiederum eindeutig in eine Dezimalzahl umgerechnet werden kann.
Die Strukturgleichheit der Hasse-Diagramme in Abbildung 14 und 7 legt folgenden Ansatz nahe: Einelementige Teilmengen von M₃ werden als Primzahlen kodiert, mehrelementige Teilmengen als Produkte der entsprechenden Primzahlen.

In den folgenden Unterabschnitten werden diese Kodierungen implementiert.

Kodierung mit Dualzahlen

Die Menge M war von 1 bis n durchnumeriert. Daher kann man für jedes Element ein Bit reservieren, also eine Stelle eines Vektors der Länge n. Soll nun eine Teilmenge A von M durch eine Dualzahl kodiert werden, so geben die Elemente von A an, welche Bits gleich 1 gesetzt werden, die anderen bleiben 0. Um auszudrücken, dass das Element k in A enthalten ist, wird das k-te Bit gesetzt. Die leere Menge wird dadurch kodiert, dass alle Bits gleich 0 sind.

Beispiel: Ist (M₃ = {1, 2, 3}, dann werden deren Teilmengen durch dreistellige Dualzahlen kodiert, zum Beispiel:

{1} → (1, 0, 0),

{3} → (0, 0, 1),

{1, 3} → (1, 0, 1).

Das folgende Skript zeigt die Funktion setToBin(), die eine als Vektor gegebene Menge set in eine n-stellige Dualzahl verwandelt. Die Dualzahl ist dann ein Vektor der Länge n.

# set: Menge, die kodiert werden soll
# n: Anzahl der Stellen, die die Dualzahl haben wird
# dies setzt voraus, dass set eine Teilmenge von (1:n) ist

setToBin <- function(set, n){
  result <- vector(mode = "integer", length = n)
  
  # Leere Menge
  if(identical(set, 0)){
    return(result)
  } else {
    for(i in (1:n)){
      if( is.element(el = i, set = set) ){
        result[i] <- 1
      }
    }
  }
  return(result)
}

Es folgen einige Tests für die Kodierung:

setToBin(set = 0, n = 8)
# [1] 0 0 0 0 0 0 0 0
setToBin(set = 1, n = 8)
# [1] 1 0 0 0 0 0 0 0
setToBin(set = (1:8), n = 8)
# [1] 1 1 1 1 1 1 1 1
setToBin(set = c(1,3,4), n = 8)
# [1] 1 0 1 1 0 0 0 0

Diese Dualzahlen kann man jetzt leicht in Dezimalzahlen umrechnen, man muss nur festlegen, welches Bit für welche Stelle steht. Hier wird folgende Konvention verwendet:

Die erste Stelle steht für die Einer,
die zweite Stelle für die Zweier,
die dritte Stelle für die Vierer und so weiter.

Üblicherweise werden die Einer an der letzten Stelle gesetzt; da aber hier die Länge der zugrundeliegenden Menge M variabel ist, beginnt man besser von vorne.

Die umgekehrte Umrechnung geschieht mit Hilfe der Funktion decToBin(): sie verwandelt eine Dezimalzahl in eine Dualzahl – aber wiederum mit der Konvention, dass die Einer vorne stehen.

decToBin <- function(x){
  if(x == 0){
    return(0)
  } else {
    # Länge des Vektors festlegen
    lg <- log2(x)
    n <- trunc(lg) + 1
    result <- vector(mode = "integer", length = n )
    
    # Bits setzen
    for(i in (1:n)){
      y <- x %/% 2
      r <- x %% 2
      result[i] <- r
      x <- y
    }
    return(result)
  }
}

Erklärungsbedürftig ist vielleicht, wie die Länge des Vektors result festgelegt wird:

Die Zahlen x = 0 und x = 1 werden in Vektoren der Länge 1 umgewandelt. Für x = 0 geschieht dies schon in Zeile 2 und 3.
Die Zahlen x = 2 und x = 3 werden in zweistellige Dualzahlen verwandelt.
Immer wenn x eine Potenz von 2 ist, wird eine Stelle mehr benötigt, also drei Stellen ab x = 4, vier Stellen ab x = 8 und so weiter.
Berechnet man von diesen Sprungstellen x den Logarithmus zur Basis 2, ist das Ergebnis genau um 1 kleiner als die benötigte Stellenanzahl.
Bei Werten von x zwischen den Sprungstellen muss man aufrunden (oder abrunden und 1 addieren).
Mit den Zeilen 6 und 7 werden somit für alle x-Werte die richtigen Vektor-Längen berechnet.

Zur Veranschaulichung:

# x:  0  || Dualzahl:  0 
# x:  1  || Dualzahl:  1 
# x:  2  || Dualzahl:  0 1 
# x:  3  || Dualzahl:  1 1 
# x:  4  || Dualzahl:  0 0 1 
# x:  5  || Dualzahl:  1 0 1 
# x:  6  || Dualzahl:  0 1 1 
# x:  7  || Dualzahl:  1 1 1

Nach diesen Vorbereitungen kann man die Ordnungsrelation implementieren, die dann zwei Dezimalzahlen vergleicht (die Dezimalzahl entspricht eindeutig einer Dualzahl, die Dualzahl eindeutig einer Teilmenge von M). Die Ordnungsrelation wird mit le.set() bezeichnet (le steht für less equal):

le.set <- function(x , y){
  if(x == 0) {
    return(TRUE)
  } else {
    set.x <- binToSet(decToBin(x))
    set.y <- binToSet(decToBin(y))
  if( isSubset(a = set.x, b = set.y) ){
    return(TRUE)
  } else {
    return(FALSE)
    }
  }
}

Der entscheidende Schritt geschieht in den Zeilen 5 und 6: Dort werden die Dezimalzahlen x und y in Mengen umgerechnet und mit diesen Zahlen wird in Zeile 7 die Ordnungsrelation isSubset() aufgerufen.

Damit hat man alles vorbereitet, um die allgemeine Funktion hasse(root, m, relation, adj.incr = TRUE) aufzurufen:

Die Teilmengenrelation relation ist auf Zahlen definiert.
Die Menge m wird durch die Potenzmenge festgelegt. Möchte man wie in Abbildung 14 das Hasse-Diagramm für die Teilmengenrelation zur Menge M₃ = {1, 2, 3} erzeugen, ist m die Potenzmenge von M₃ und hat somit 8 Elemente.
Als root kann die leere Menge gewählt werden, die durch 0 kodiert wird.

h.set.0.7 <- hasse_adj(root = 0, m = (0:7), relation = le.set)
h.set.0.7
# Level:  1  || Nachfolger:  1 2 4 
# Level:  2  || Nachfolger:  3 5 6 
# Level:  3  || Nachfolger:  7 
# 
#   0 1 2 3 4 5 6 7
# 0 0 1 1 0 1 0 0 0
# 1 0 0 0 1 0 1 0 0
# 2 0 0 0 1 0 0 1 0
# 3 0 0 0 0 0 0 0 1
# 4 0 0 0 0 0 1 1 0
# 5 0 0 0 0 0 0 0 1
# 6 0 0 0 0 0 0 0 1
# 7 0 0 0 0 0 0 0 0

Nach dem obigen Test von decToBin() entsprechen

die Zahlen 1, 2 und 4 gerade den einelementigen Teilmengen,
die Zahlen 3, 5, 6 den zweielementigen Teilmengen und
die 7 entspricht der Menge M₃.

Zum Schluss soll noch auf die Ähnlichkeit zwischen der hier verwendeten Ordnungsrelation le.set() und der Ordnungsrelation le.2dice() hingewiesen werden; Letztere wurde verwendet, um die Ergebnisse beim zweimaligen Würfeln zu vergleichen. Man kann eine n-stellige Dualzahl als das Ergebnis von n Münz-Würfen interpretieren (etwa mit Kopf als 1 und Zahl als 0). Das entsprechende Glücksspiel würde dann nach folgenden Regeln gespielt:

Jeder Spieler wirft seine Münze n mal und notiert die Ergebnisse; dies entspricht einer n-stelligen Dualzahl.
Gewonnen hat der Spieler, der an jeder Stelle der Dualzahl die größere Zahl stehen hat, etwa (1, 1, 1, 1) gegen (0, 0, 0, 0).
Es ist klar, dass jetzt der Großteil der Spiele unentschieden ausgehen und der Einsatz in den Jackpot wandert.

Die entsprechende Ordnungsrelation auf den Dualzahlen wird dann alle Stellen vergleichen und TRUE zurückgeben, wenn für alle Stellen a_i ≤ b_i gilt; andernfalls FALSE.

Aufgaben:

1. Noch fehlende Funktionen:

Implementieren Sie die noch fehlenden Funktionen:

Eine Funktion binToDec() die als Eingabewert einen Vektor erhält, der nach obiger Konvention eine Dualzahl beschreibt. Rückgabewert ist die zugehörige Dezimalzahl.
Eine Funktion asSet(), die als Eingabewert eine Dezimalzahl x erhält und den Vektor mit den entsprechenden Elementen der Menge M zurückgibt.

2. Zusammenhang mit Binomialkoeffizienten:

Diskutieren Sie, warum im Hasse-Diagramm für die Teilbarkeitsrelation bei einer Menge M mit n Elementen gilt:

In jeder Ebene ist die Anzahl der Teilmengen durch den entsprechenden Binomialkoeffizienten gegeben. Genauer: Beginnt man unten (leere Menge) die Ebene mit k = 0 zu bezeichnen und in der Ebene k stehen die k-elementigen Teilmengen von M, so gibt es in der k-ten Ebene "k aus n" Teilmengen.

Kodierung mit Primzahlen

Eine anderen Ansatz zur Kodierung aller Teilmengen einer gegebenen Menge M = {1, 2, ..., n} bieten die Primzahlen: Man bereitet sich die Folge der ersten n Primzahlen vor:

p₁, p₂, p₃,...p_n = 2, 3, 5, ...

Kodierung heißt dann, dass eine Teilmenge von M durch das Produkt der entsprechenden Primzahlen ersetzt wird, etwa:

A = {1, 3} → p₁ · p₃ = 2 · 5 = 10.

Möchte man jetzt das Hasse-Diagramm für M = {1, 2, ..., n} erzeugen, kann man das Hasse-Diagramm für die Teiler der Zahl

z = p₁ · p₂ · ... · p_n

erzeugen.

Beispiel:

Für M = {1, 2, 3} erhält man z = 30; das Hasse-Diagramm zeigt Abbildung 9. Übersetzt man die Teiler von 30 wieder in Teilmengen, erhält man das gewünschte Hasse-Diagramm für die Teilmengenrelation.

Aufgabe:

Implementieren Sie die Funktionen zum Kodieren einer Teilmenge als Produkt von Primzahlen und die Umkehrfunktion (Dekodieren einer Zahl und Erzeugen der Teilmenge, die dann als Vektor zurückgegeben wird).