Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

Aufzählung oder Menge von Elementen mit einer bestimmten Eigenschaft.

[a] ={ a' A a R a' }


Für zwei Elemente a, b A gilt entweder
[a] =[b] oder [a] [b] ={}.

Eine Relation R A x A heißt (partielle ) Ordnung, falls folgendes gilt:

- Reflexivität: für alle a A gilt (a, a) R
- Transitivität: falls für beliebige a, b, c A (a, b) R und (b, c) R gilt, so muss auch (a,c) R gelten.
- Antisymmetrie: falls für beliebige a, b A (a, b) R und (b, a) R gelten, so muss a = b gelten, d.h., a und b sind dann gleich.

Bei der Definition einer Ordnung hat sich gegenüber der Def. einer Äquivalenzrelation nur die letzte Eigenschaft geändert (Antisymmetrie vs. Symmetrie).

Achtung: Antisymmentrie ist nicht das Gegenteil von Symmetrie!
Jede Gleichheitsrelation erfüllt beide Eigenschaften.

steht für die Menge der  Natürlichen Zahlen mit 0
= {0, 1, 2, 3, 4, 5, ...}

steht für die Menge Ganzer Zahlen
= {..., -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, ...}

Rationale Zahlen
: die Menge aller Brüche (= Menge aller Kommazahlen mit endlicher oder periodischer Dezimaldarstellung)
2   -4           0,75    32.3347   = 0,3333....

Reelle Zahlen
: Die Menge aller reelen Zahlen( = Menge aller Kommazahlen mit beliebiger - auch unendlicher, nicht-periodischer Dezimaldarstellung)
2    -4       = 3,14159...      e = 2,718281...

M = { 0, 2, 4, 6, 8, . . . }

Beispiel:
∈   und n gerade

Allgemeines Format:

(M ist Menge aller Elemente x, die die Eigenschaft P erfüllen.)

Die Elemente einer Menge sind ungeordnet, d.h., ihre
Ordnung spielt keine Rolle. Beispielsweise gilt:
{ 1, 2, 3 } = { 1, 3, 2 } = { 2, 1, 3 } = { 2, 3, 1 } = { 3, 1, 2 } = { 3, 2, 1 }

Ein Element kann nicht “mehrfach” in einer Menge auftreten.
Es ist entweder in der Menge, oder es ist nicht in der Menge.
Beispielsweise gilt:

Wir schreiben a ∈ M, falls ein Element a in der Menge M
enthalten ist.

Für eine Menge M gibt | M | die Anzahl ihrer Elemente an.

Wir schreiben A ⊆ B, falls jedes Element von A auch in B
enthalten ist. Die Beziehung ⊆ heißt auch Inklusion.

Mit ∅ oder {} bezeichnet man die leere Menge. Sie enthält keine
Elemente und ist Teilmenge jeder anderen Menge.

Die Vereinigung zweier Mengen A, B ist die Menge M, die alle
Elemente enthält, die in A oder B vorkommen. Man schreibt dafür
A ∪ B.

A ∪ B = x | x ∈ A oder x ∈ B

Der Schnitt zweier Mengen A, B ist die Menge M, die die Element
enthält, die sowohl in A als auch in B vorkommen. Man schreibt
dafür A ∩ B.

A ∩ B = x | x ∈ A und x ∈ B

Seien A, B zwei Mengen. Dann bezeichnet A \ B die Menge aller
Elemente, die in A vorkommen und in B nicht vorkommen.
A \ B = x | x ∈ A und x ∈ B }

Beispiele:
{ 0, 1, 2, 3, 4, 5 }\{ 0 } = { 1, 2, 3, 4, 5 }
{ a, b, c }\{ c, d } = { a, b }

Die Menge P (M) ist die Menge aller Teilmengen von M.

Sei M eine Menge. Die Menge P (M) ist die Menge aller
Teilmengen von M.
P (M) = A | A ⊆ M

Beispiel:
P ( { 1, 2, 3 } ) = {∅ , { 1 } , { 2 } , { 3 } , { 1, 2 } , { 1, 3 } , { 2, 3 } , { 1, 2, 3 }} .
Es gilt:   (für eine endliche Menge M).

Seien A, B zwei Mengen. Die Menge A × B ist die Menge aller
Paare (a, b), wobei die erste Komponente des Paars aus A, die
zweite aus B kommt.

A × B = (a, b) | a ∈ A, b ∈ B

Beispiel:
{ 1, 2 } × { 3, 4, 5 } = { (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5) }
Es gilt: | A × B | = | A | · | B | (für endliche Menge A, B).

Eine Teilmenge des Kreuzprodukts von der Menge A und der Menge B nennt man Relation zwischen A und B.

Standardschreibweise: (2,b)∈R
Infix-Schreibweise: 2 R b

Es muss für eine Relation gelten:

Für jedes Element a∈ A gibt es genau ein Element b∈ B mit
(a,b) ∈ R

f:  A B
f(a)

Die Funktion f bildet ein Element a ∈ A auf ein Element f (a) ∈ B ab. Dabeist A der Definitionsbereich und B der Wertebreich.

Eine Funktion f:  A B heißt injenktiv, falls es keine Elemente a1, a2 ∈ A gibt mit a1 a2 und f(a1) = f(a2).

Mit anderen Worten: Auf kein Element im Wertebereich zeigt mehr als ein Pfeil.

Eine Funktion f: A B heißt surjektiv, falls es für jedes b ∈ B (mindestens) ein a ∈ A gibt mit f(a) = B.

Mit anderen Worten: auf jedes Element im Wertebreich zeigt (mindestens) ein Pfeil.

Eine Funktion f: heißt bijektiv, falls sie injektiv und surjektiv ist.

Mit anderen Worten: auf jedes Element im Wertebereich zeigt genau ein Pfeil, d.h., es gibt eine eins-zu-eins-Zuordnung  zwischen den Elementen des Definitionsbereichs und des Wertebereichs.

Die bijektiven Funktionen sind genau die invertierbaren
Funktionen. Zu einer bijektiven Funktion f : gibt es eine Umkehrfunktion mit folgenden Eigenschaften:
( (a)) = a für alle a A
(b)) = b für alle b B

Wenn die Funktionen f: und g: gegeben sind, dann wird die Verknüpfung bzw. die Hintereinanderausführung mit bezeichnet.

1. Reflexivität: für alle a ∈ A gilt (a,a) ∈ R.
2. Transitivität: Falls für beliebige a,b,c ∈ A (a,b) ∈ R und (b,c) ∈R gilt, so muss auch (a,c) ∈ R gelten.
3. Symmetrie: Falls für beliebige a,b ∈ A (a,b) ∈ R gilt, so muss auch (b,a) ∈ R gelten.

Das Bild von A' unter der Funktion f, wenn :

{ }


Das Urbild von B' unter der Funktion f, wenn :

{ }

Die Relation Teilbarkeit (senkrechter Strich | ) ist eine partielle Ordnung, wenn man sie auf die natürlichen Zahlen einschränkt.

Definition:
Seien a, b zwei ganze Zahlen.
Man sagt, a teilt b wenn es ein z gibt mit a * z = b.
Wir schreiben auch a | b und nennen a Teiler von b

2 | 18 gilt, z = 9
-7 | 14 gilt, z = -2
3 | 10 gilt nicht
0 | 0 gilt, z ist beliebig
0 | 7 gilt nicht
7 | 0 gilt, z = 0

Merk dir das: rechts darf immer die Null stehen, links nie (es sei denn, sie steht rechts auch)

Eine Zahl p 0 heißt Prinzahl, wenn folgendes gilt:
p 0 und p 1
Die einzigen Teiler von p in den natürlichen Zahlen sind 1 und p selbst.

(Es gibt unendlich viele Primzahlen. Die ersten sind
2, 3, 5, 7, 11, 13, 17, 19, 23)

Sei n eine natürliche Zahl mit n0.
Ein Produkt von Primzahlen = n heißt Primfaktorzerlegung von n.

Jede Zahl n0 besitzt eine solche Primfaktorzerlegung.

Wenn man zudem verlangt, dass die Primzahlen in aufsteigender Reihenfolge angeordnet sind, dann ist die Primfaktorzerlegung einer Zahl eindeutig.

Bsp: 55=5*11

Achtung: Die Primfaktorzerlegung von 1 ist das leere Produkt.

Komplizierte Frage - simple Antwort:

Dann ist d natürlich der größte gemeinsame Teiler von a und b.
Also:

d = ggT(a,b)

-> ggT(0,a) = a
-> ggT(a,b) = ggT(b,a)
-> falls a größer oder gleich b ist: ggT(a,b) = ggT(a-b,b)

auf Deutsch:
>>> Die beiden Zahlen kann man immer tauschen.
>>> Wenn links die größere (oder gleiche) steht, zieht man die kleinere von ihr ab.

Das alles macht man so lange, bis man links eine 0 stehen hat, die rechte Zahl ist dann das Ergebnis (vgl. Regel 1)

ggT(132,88) = ggT(44,88) = ggT(88,44) = ggT(44,44) = ggT(0,44) = 44

Dann ist m das kleinste gemeinse Vielfache von a und b, also:

m = kgV(a,b)

ggT(a,b) = ggT(a mod b, b)

bei a >= b

Die Gleichung hat genau eine Lösung, wenn gilt
ggT(a,b) | c
Also muss der ggT von a und b Teiler von c sein.
(Auch wenn das noch nicht die Lösung der Gleichung ist)

Zwei natürliche Zahlen (inkl. Null) heißten teilerfremd, falls
ihr ggT 1 ist:

ggT(a,b) = 1 ==> a und b sind teilerfremd

(n) mit n 0 ist die Anzahl der Zahlen zwischen 1 und n, die zu n teilerfremd sind.

(n) = | { m 0 1 m n und ggT(m,n) = 1 } |

Gegeben sei eine Menge M und eine zweistellige Abbildung

: M x M M. Wir benutzen meist die Infix-Schreibweise:
(m, m) = m m und bezeichnen als zweistelligen Operator.

(M, ) heißt Monoid, falls folgendes gilt:

- ist assoziativ, d.h., es gilt m (m m) = (m m) m
für alle m, m, m M.
- Es gibt ein neutrales Element e M, für das gilt:
e m = m e = m für alle m M.

Wir denieren = 0, 1, ..., n - 1 mit folgender Addition +
und Multiplikation . Seien k, Z, dann gilt:

k + = (k + ) mod n
k = (k ) mod n

(,+) und (, ) sind Monoide
(mit neutralen Elementen 0 bzw. 1)

Modulo-Gesetze
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a b) mod n = ((a mod n) (b mod n)) mod n
mod n = mod n

Ein Monoid mit neutralem Element e heißt Gruppe, wenn zusätzlich zu den Monoid-Eigenschaften noch folgendes gilt:

Für jedes gibt es ein mit .
Dabei heißt das Inverse von .
heißt kommutative Gruppe (oder abelsche Gruppe), falls außerdem für alle gilt.

Bemerkung: In jeder Gruppe gilt nicht nur , sondern auch für alle .

Nein.

Erläuterung s. Vorlesung.