Mengen


Das Verständnis von Mengen ist grundlegend in der theoretischen Informatik. Viele Teilbereich der theoretischen Informatik greifen auf die Mengenlehre zurück. Grundlegend versteht man unter einer Menge eine Zusammenfassung von einer beliebigen Anzahl von Dingen. Eine Schulklasse wäre z.B. eine Menge aller Schüler dieser Klasse. Die Schüler wären dabei die Elemente der Menge Schulklasse.

Die wohl berühmteste Definition einer Menge ist die vom deutschen Mathematiker Georg Cantor:

“Unter einer Menge verstehen wir jede Zusammenfassung M von bestimmten wohl unterschiedenen Objekten unserer Anschauung oder unseres Denkens (welche die Elemente von M genannt werden) zu einem Ganzen.“

Unsere Menge Schulklasse besteht also aus einer endlichen Anzahl an Schüler. So könnte die Menge Schulklasse folgendermaßen aussehen:

Schulklasse := {Paul, Lisa, Manuel, Fritz}

Möchte man nun ausdrücken das ein bestimmtes Element in einer Menge enthalten ist, so schreibt man allgemein a ∈ M. Bezogen auf unser konkretes Beispiel würde also Paul ∈ Schulklasse sein. Gehören mehrere Elemente zu einer Menge, dann kann man die Schreibweise auch abkürzen. Statt also zu schreiben: Paul ∈ Schulklasse, Lisa ∈ Schulklasse würde die abkürzende Schreibweise Paul, Lisa ∈ Schulklasse ebenfalls bedeuten, dass Paul und Lisa Element der Menge Schulklasse sind.

Gehört allgemein a nicht zu M, dann schreibt man a ∉ M. Auf das Beispiel wieder bezogen würde gelten: Tobi ∉ Schulklasse.

Besitzen zwei Mengen exakt dieselben Elemente, dann spricht man davon, dass die Mengen gleich sind. Es gelte dann also M1 = M2. Nun kann das bei zwei Schulklassen natürlich nicht der Fall sein, da man als Schüler immer nur einer Klasse zugehörig ist. Man würde also in diesem Fall schreiben: Schulklasse1 ≠ Schulklasse2. Damit zwei Mengen nicht gleich sind, reicht es schon aus, wenn lediglich ein Element in M1 oder M2 ist, und nicht in der anderen Menge enthalten ist.

Im Gegensatz zu der umgangssprachlichen Menge kann eine Menge im mathematischen Sinn auch keine Elemente besitzen. Man spricht dann von der leeren Menge, für die es das spezielle Symbol: ∅ gib.

Schreibweisen von Mengen

In der Praxis haben sich zwei Schreibweisen von Mengen durchgesetzt: die aufzählende Beschreibung und die deskriptive Beschreibung.

Aufzählende Beschreibung

Die aufzählende Beschreibung haben wir schon in unserem Schulklassen-Beispiel kennengelernt. Hierbei werden alle Elemente einer Menge explizit nacheinander aufgelistet. Bei einer Anzahl von 30 Schülern je Schulklasse wäre das Aufzählen der einzelnen Schüler zwar lästig, dennoch aber gut machbar. Anders sieht es da bei unendlichen Mengen aus, wie z.B. den natürlichen Zahlen. Das Aufzählen aller natürlichen Zahlen ist schlichtweg nicht möglich, dennoch kann man mit der aufzählenden Beschreibung genau diese Menge beschreiben. Statt alle Elemente aufzulisten muss man lediglich so viele Elemente aufzählen, bis eine unmittelbare einsichtige Regelmäßigkeit vorliegt. Bei den natürlichen Zahlen wäre dies einfach:
Natuerliche Zahl := {0,1,2,3,4,5,6,7,8 ...}

Ein weiteres Beispiel wäre die Menge aller geraden natürlichen Zahlen
M1 := {0,2,4,6,8,10,12,14 …}

Deskriptive Beschreibung

Etwas einfacher und klarer, aber auf dem ersten Blick komplizierter ist die deskriptive Beschreibung. Hier wird die Mengenzugehörigkeit eines Elements über eine charakteristische Eigenschaft beschrieben. Jedes Element auf die diese Eigenschaft zutrifft, gehört zur Menge. Nehmen wir das Beispiel die Menge aller geraden natürlichen Zahlen. Diese könnten deskriptiv folgendermaßen beschrieben werden:
M2 := {n ∈ Natuerliche Zahl | n mod 2 = 0}
In der Menge M2 sind also alle natürliche Zahlen die modulo 2 gleich 0 ergeben, also durch 2 ohne Rest teilbar sind. Das sind gerade alle gerade natürliche Zahlen und damit ist M2 = M1.

Da man es meist mit der deskriptiven Beschreibung zu tun hat, lohnt es sich mit dieser Form auseinanderzusetzen. Dafür kann man sich einfach unterschiedliche Mengen in aufzählender Beschreibung aufschreiben und sich dann dazu jeweils die deskriptive Beschreibung überlegen. Dies geht zwar nicht mit allen Mengen ohne weiteres, oft findet man aber eine viele elegantere deskriptive Beschreibung, als die aufzählende Beschreibung.

Teilmengen

Wie haben gelernt das Mengen gleich sein können, wenn sie exakt die selben Elemente besitzen. Darüber hinaus kann eine Menge eine Obermenge oder eine Untermenge einer anderen Menge sein. So bedeutet:
M1 ⊆ M2, das M1 Untermenge von oder gleich mit M2 ist. Ein beliebiges Element aus M1 muss also auch immer in M2 enthalten sein. Der Umkehrschluss gilt aber nicht, ein beliebiges Element aus M2 muss nicht in M1 sein.
M1 ⊇M2 bedeutet dann entsprechend, dass M1 eine Obermenge oder gleich mit M2 ist. Es gilt M1 ⊇M2 ⇔ M2 ⊆M1
Wer anfänglich noch Probleme hat die Symbole der Ober- bzw. Untermenge zuzuordnen, der muss sich gedanklich einfach nur ein „Größer-Gleich“ oder „Kleiner-Gleich“-Zeichen denken. Statt M1 ⊇ M2 denkt man sich also M1 ≥ M2 und weiß damit, dass die linke Menge größer oder gleich als die rechte Menge sein muss und damit M1 die Obermenge von M2 oder eben gleich M2 ist.

Die leere Menge ist eine Teilmenge jeder anderen Menge. Darüber hinaus gilt auch, dass jede Menge auch eine Teilmenge von sich selbst ist. Es gelten also die Beziehungen: ∅ ⊆ M, M ⊇ ∅, M ⊆ M, M ⊇ M.

Neben ⊆ gibt es auch ⊂ (echte Untermenge) und neben ⊇ auch ⊃ (echte Obermenge).
So bedeutet M1 ⊂ M2 ⇔ M1 ⊆ M2 und M1 ≠ M2

Mengenoperationen

Mengen können nicht nur zueinander in Beziehung stehen, sondern man kann sie auch miteinander verknüpfen und so zu neuen Mengen machen. Man unterscheidet dabei zwischen der Vereinigungsmenge, der Schnittmenge, der Differenzmenge und der Komplementärmenge.

Schnittmenge: M1 ∩ M2 := {a | a ∈ M1 und a ∈ M2}

Vereinigungsmenge: M1 ∪ M2 := {a | a ∈ M1 oder a ∈ M2}

Differenzmenge: M1 \ M2 := {a | a ∈ M1 und a ∉ M2}

Komplementärmenge: Komplementärmenge := T \ M

Wobei T eine nichtleere Trägermenge von M1 und M2 ist.

Zwei Mengen M1 und M2 heißen disjukt, wenn M1 ∩ M2 = ∅ ist.


Für die Vereinigung und den Schnitt gelten das Kommutativgesetz, Distributivgesetz, Assoziativgesetz, Idempotenzgesetzt, Absoptionsgesetz, die Gesetze von De Morgan, das Auslöschungsgetz und das Gesetz der Doppelnegation.


Quellen:

Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972