Mengenlehre Grundlagen

Eine Sammlung von bestimmten, wohlunterschiedenen Objekten (Elemente genannt), die zu einem Ganzen zusammengefasst werden.

Ein Element x gehört zur Menge M. Es wird geschrieben: x ∈ M

Ein Element x gehört nicht zur Menge M. Es wird geschrieben: x ∉ M

Zwei Mengen sind gleich, wenn sie die gleichen Elemente enthalten.

Mengen können durch Auflisten ihrer Elemente in geschweiften Klammern angegeben werden: M = {..., ...}

Mengen können durch Beschreibung der Eigenschaften ihrer Elemente angegeben werden: M = {x : E(x)}. Die Menge umfasst alle x, für die E(x) wahr ist.

Eine Menge ohne Elemente. Es wird geschrieben: ∅ = {}

Die Anzahl der Elemente einer Menge.

Die Vereinigung zweier Mengen A und B enthält alle Elemente, die in A, B oder beidem vorkommen.

Die Differenz zweier Mengen A und B enthält alle Elemente, die in A aber nicht in B vorkommen.

Das kartesische Produkt zweier Mengen A und B besteht aus allen möglichen Paaren (a, b), wobei a aus A und b aus B stammt.

Die Potenzmenge einer Menge A enthält alle möglichen Teilmengen von A, einschließlich der leeren Menge.

Das erste Distributivgesetz besagt: Die Differenz von A mit der Vereinigung von B und C ist gleich der Vereinigung der Differenz von A und B mit der Differenz von A und C.

Das zweite Distributivgesetz besagt: Die Vereinigung von A mit der Differenz von B und C ist gleich der Differenz der Vereinigung von A und B mit der Vereinigung von A und C.

Wenn die Vereinigung von A und B gleich B ist, dann ist A eine Teilmenge von B.

Ein n-Tupel ist eine geordnete Liste mit n Elementen, wobei die Reihenfolge relevant ist.

Eine Relation auf einer Menge M ist eine Teilmenge R des kartesischen Produkts M x M, die angibt, welche Elemente von M zueinander in Beziehung stehen.

Eine Relation ist reflexiv, wenn jedes Element zu sich selbst in Relation steht. Beispiel: a ist gleich a.

Eine Relation ist symmetrisch, wenn aus a steht zu b in Relation folgt, dass b auch zu a in Relation steht. Beispiel: a ist der Bruder von b, dann ist b der Bruder von a.

Eine Relation ist antisymmetrisch, wenn aus a steht zu b in Relation und b steht zu a in Relation folgt, dass a und b identisch sind. Beispiel: a ist älter als b, dann kann b nicht älter als a sein.

Eine Relation ist transitiv, wenn aus a steht zu b in Relation und b steht zu c in Relation folgt, dass a auch zu c in Relation steht. Beispiel: a ist kleiner als b, b ist kleiner als c, dann ist a kleiner als c.

Eine Relation ist total, wenn für alle Elemente a, b der Menge gilt, dass entweder a zu b in Relation steht oder b zu a in Relation steht. Beispiel: a ist kleiner als b, oder b ist kleiner als a.

Die Definition einer Relation auf einer Menge M beschreibt die Relation zwischen den Elementen der Menge.

Die Eigenschaften einer Relation, wie reflexiv, symmetrisch, antisymmetrisch, transitiv und total, beschreiben die Art der Beziehung zwischen den Elementen einer Menge.

Eine Abbildung ':G!H zwischen zwei Gruppen (G, ⇤) und (H, ·) heißt Homomorphismus, wenn sie die Gruppenoperationen erhält: '(a ⇤ b) = '(a) · '(b) für alle a, b 2 G.

Ein Homomorphismus heißt Isomorphismus, wenn er bijektiv ist.

Das neutrale Element von G wird durch den Homomorphismus ' auf das neutrale Element von H abgebildet: '(eG ) = eH.

Das inverse Element von a in G wird durch den Homomorphismus ' auf das inverse Element von '(a) in H abgebildet: '(a0 ) = '(a)0.

Wenn ein Homomorphismus ' bijektiv ist, dann ist auch seine Umkehrabbildung ' 1 : H !G ein Isomorphismus.

Isomorphe Gruppen sind "strukturell gleich" und unterscheiden sich nur in der Bezeichnung ihrer Elemente.

Die Abbildung ' : Z !Z, a 7! 2a ist ein Homomorphismus von (Z, +) nach (Z, +), da '(a + b) = 2(a + b) = 2a + 2b = '(a) + '(b) für alle a, b 2 Z gilt.

Die Abbildung exp : R !R>0 , x 7!exp(x) = ex ist ein Isomorphismus von (R, +) nach (R>0 , ·), da exp(a + b) = exp(a) · exp(b) für alle a, b 2 R und exp bijektiv ist.

Eine Permutation ⇡ ist eine bijektive Abbildung von der Menge {1, 2, ..., n} auf sich selbst. Sie wird als Folge der Bildwerte von 1 bis n dargestellt: ⇡ = (⇡(1), ⇡(2), ..., ⇡(n)).

Die Verknüpfung zweier Permutationen ⇡ und 2 erfolgt durch die Hintereinanderausführung der Abbildungen. Die Bildwerte werden durch Eingabe der Bildwerte von 2 in ⇡ berechnet.

Eine Gruppe ist eine Menge G mit einer Verknüpfung ⇤, die folgende Eigenschaften erfüllt: Assoziativität, Existenz eines neutralen Elements e, Existenz eines inversen Elements für jedes Element.

Eine Untergruppe ist eine nichtleere Teilmenge U einer Gruppe G, die mit der gleichen Verknüpfung ⇤ selbst wieder eine Gruppe bildet.

Eine Verknüpfung ⇤ auf einer Menge G heißt assoziativ, wenn für alle a, b und c ∈ G gilt: a ⇤ (b ⇤ c) = (a ⇤ b) ⇤ c.

In einer Gruppe existiert ein neutrales Element e, welches mit jedem anderen Element a der Gruppe verknüpft, das gleiche Element a ergibt.

Jeder Element a in einer Gruppe hat ein inverses Element a0, welches mit a verknüpft, das neutrale Element e ergibt.

Eine Gruppe heißt abelsch, wenn die Verknüpfung kommutativ ist, d. h. für alle Elemente a und b der Gruppe gilt a ⇤ b = b ⇤ a.

Die Division mit Rest besagt, dass für zwei ganze Zahlen a und b (mit b ungleich 0) es eindeutige ganze Zahlen q (Quotient) und r (Rest) gibt, sodass a = q · b + r gilt und 0 ≤ r < |b|.

Die Teilbarkeit einer ganzen Zahl a durch eine ganze Zahl b (mit b ungleich 0) bedeutet, dass es eine ganze Zahl q gibt, so dass a = q · b gilt.

Modulo 24 ist eine Art der Restklassenrechnung, bei der man die Uhrzeit berücksichtigt. Dabei wird der Rest der Division durch 24 verwendet, um die Uhrzeit zu bestimmen. Beispiel: 22 Uhr + 7 Stunden = 5 Uhr.

Restklassen sind Klassen von Zahlen, die den gleichen Rest bei der Division durch eine bestimmte Zahl (den Modul) haben. Beispiel: Die Restklasse 1 modulo 3 enthält die Zahlen {..., -8, -5, -2, 1, 4, 7, ...}.

Eine Restklasse modulo b enthält alle Zahlen, die den gleichen Rest wie a bei der Division durch b haben. Die Restklasse von a modulo b wird mit [a]b bezeichnet.

Zwei Restklassen [a]b und [c]b sind gleich, wenn die beiden Zahlen a und c den gleichen Rest bei der Division durch b haben (also a – c durch b teilbar ist).

Die Addition und Multiplikation von Restklassen erfolgt, indem man die Operationen auf den Repräsentanten der Restklassen ausführt und dann den Rest der Division durch den Modul betrachtet. Beispiel: [2]3 + [1]3 = [3]3 = [0]3.

Der Quotient der Division mit Rest ist die größte ganze Zahl, die kleiner oder gleich dem Ergebnis der Division ist. Der Rest ist die Differenz zwischen dem Dividenden und dem Produkt aus Quotient und Divisor.