· Grundlagen 1 Mengen Element einer Menge Wir schreiben a 2M, falls ein Element a in der Menge M enthalten ist. Anzahl der Elemente einer Menge F ur eine endliche Menge M …

Vorlesung”Mathematische Strukturen“

Sommersemester 2017

Prof. Janis VoigtlanderUbungsleitung: Dennis Nolte

Mathematische Strukturen Sommersemester 2017

Grundlagen 1

Mengen

Menge

Menge M von Elementen, oft beschrieben als Aufzahlung

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

oder als Menge von Elementen mit einer bestimmten Eigenschaft

M = {n | n ∈ N0 und n gerade} = {n ∈ N0 | n gerade}.

Allgemeines Format:M = {x | E (x)}

M ist Menge aller Elemente, die die Eigenschaft E erfullen.

M = {x ∈ X | E (x)}

M ist Menge aller Elemente aus der Grundmenge X , die E erfullen.


Grundlagen 1

Mengen

Bemerkungen:

Die Elemente einer Menge sind ungeordnet, d.h., ihreOrdnung 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. Esist entweder in der Menge, oder es ist nicht in der Menge.Beispielsweise gilt:

{1, 2, 3, 4, 4} = {1, 2, 3, 4} 6= {1, 2, 3}


Grundlagen 1

Mengen

Element einer Menge

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

Anzahl der Elemente einer Menge

Fur eine endliche Menge M gibt |M| die Anzahl ihrer Elemente an.

Teilmengenbeziehung

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

Leere Menge

Mit ∅ oder {} bezeichnen wir die leere Menge. Sie enthalt keineElemente und ist (echte) Teilmenge jeder anderen Menge.


Grundlagen 1

Mengen

Beispiele:

4 ∈ {1, 2, 3, 4}4 6∈ {1, 2, 3}4 6∈ ∅4 ∈ N0

|{1, 2, 3, 4, 4}| = 4

|∅| = 0

∅ ⊆ {1, 2, 3} ⊆ {1, 2, 3, 4} ⊆ N0 ⊆ Z

{1, 2, 3, 4} 6⊆ {1, 2, 3}{1, 2, 3, 4} 6⊆ {1, 2, 3, 5} und {1, 2, 3, 5} 6⊆ {1, 2, 3, 4}


Grundlagen 1

Mengen

Anmerkungen:

Wenn A ⊆ B und beide Mengen sind endlich, dann |A| ≤ |B|.|N0| 6∈ N0

Wenn M = {x ∈ X | E (x)}, dann M ⊆ X , unabhangig von E .

Insbesondere, {x ∈ ∅ | E (x)} = ∅.


Grundlagen 1

Mengen

Mengenvereinigung

Die Vereinigung zweier Mengen A und B ist diejenige Menge,welche die Elemente enthalt, die in A oder B (oder in beiden)vorkommen. Man schreibt dafur A ∪ B.

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

Mengenschnitt

Der Schnitt zweier Mengen A und B ist diejenige Menge, welchedie Element enthalt, die sowohl in A als auch in B vorkommen.Man schreibt dafur A ∩ B.

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


Grundlagen 1

Mengen

Veranschaulichung von Vereinigung und Schnitt durchVenn-Diagramme:

Blau eingefarbte Flacheentspricht der Vereinigung A∪B

Blau eingefarbte Flacheentspricht dem Schnitt A ∩ B


Grundlagen 1

Mengen

Beispiele:

{1, 2, 3} ∪ {3, 4} = {1, 2, 3, 3, 4} = {1, 2, 3, 4}{1, 2, 3} ∪ N0 = N0

{1, 2, 3} ∩ {3, 4} = {3}{1, 2, 3} ∩ {4} = ∅{1, 2, 3} ∩ N0 = {1, 2, 3}

Allgemeine Anmerkungen:

|A ∪ B| = |A|+ |B| − |A ∩ B|(A ∩ B) ⊆ A ⊆ (A ∪ B) und (A ∩ B) ⊆ B ⊆ (A ∪ B)

Wenn A ⊆ B, dann A ∪ B = B und A ∩ B = A.


Grundlagen 1

Mengen

Mengendifferenz

Die Differenz zweier Mengen A und B ist diejenige Menge, welchedie Elemente enthalt, die in A vorkommen und in B nichtvorkommen. Man schreibt dafur A \ B.

A \ B = {x | x ∈ A und x 6∈ B} = {x ∈ A | x 6∈ B}

Beispiele:

{0, 1, 2, 3, 4, 5} \ {0} = {1, 2, 3, 4, 5}{a, b, c} \ {c , d} = {a, b}{1, 2, 3} \ ∅ = {1, 2, 3}{1, 2, 3} \ N0 = ∅({1, 2, 3} \ {1, 2}) \ {1} 6= {1, 2, 3} \ ({1, 2} \ {1})


Grundlagen 1

Mengen

Veranschaulichung der Differenz durch ein Venn-Diagramm:

Blau eingefarbte Flache entspricht der Differenz A \ B

Anmerkungen:

(A \ B) ⊆ A

|A \ B| = |A| − |A ∩ B|Wenn A ⊆ B, dann A \ B = ∅ (und umgekehrt).


Grundlagen 1

Mengen

Potenzmenge

Die Potenzmenge einer Menge M ist diejenige Menge, welche alleTeilmengen von M enthalt. Man schreibt dafur P(M).

P(M) = {A | A ⊆ M}

Beispiele:

P({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}P(∅) = {∅}P(P(∅)) = {∅, {∅}}

Anmerkungen:

Fur endliche Mengen M gilt |P(M)| = 2|M|.

Es gilt P(A) ⊆ P(B) genau dann wenn A ⊆ B.


Grundlagen 1

Mengen

Kreuzprodukt (Kartesisches Produkt)

Das Kreuzprodukt zweier Mengen A und B ist diejenige Menge,welche alle Paare (a, b) enthalt, wobei die erste Komponente desPaars aus A, die zweite aus B kommt. Man schreibt dafur A× B.

A× B = {(a, b) | a ∈ A und b ∈ B}

Beispiele:

{1, 2} × {3, 4, 5} = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}{1, 2} × ∅ = ∅

Anmerkungen:

Fur endliche Mengen A und B gilt |A× B| = |A| · |B|.Wenn A ⊆ B, dann A× C ⊆ B × C und C × A ⊆ C × B.


Grundlagen 1

Mengen

Weitere Bemerkungen:

Wir betrachten nicht nur Paare, sondern auch sogenannteTupel aus mehr als zwei Komponenten.Ein Tupel (a1, . . . , an) bestehend aus n Komponenten heißtauch n-Tupel.

In einem Tupel sind die Komponenten geordnet! Es gilt z.B.:

(1, 2, 3) 6= (1, 3, 2) ∈ N0 × N0 × N0

Ein Element kann mehrfach in einem Tupel auftreten. Tupelunterschiedlicher Lange sind immer verschieden.Beispielsweise:

(1, 2, 3, 4) 6= (1, 2, 3, 4, 4)

Runde Klammern (, ) und geschweifte Klammern {, } stehen furganz verschiedene mathematische Objekte!


Grundlagen 1

Mengen

Beispiel: Zustandsmodellierung

Angenommen, wir betrachten einen einfachen Snackautomaten furRiegel und Chips. Von jedem dieser beiden Snacks hat er maximal30 Stuck auf Vorrat. Der Automat hat eine gelbe und eine roteWarnleuchte (

”kein Wechselgeld mehr“ bzw.

”keine Scheine mehr

akzeptiert“), die unabhangig voneinander leuchten konnen. DieMenge der moglichen Zustande dieses Automaten konnen wir als

P({gelb, rot})× {0, 1, . . . , 30} × {0, 1, . . . , 30}

beschreiben. Das Element (∅, 20, 10) dieser Menge zum Beispielentspricht dem Zustand, in dem beide Warnleuchten ausgeschaltetsind und noch 20 Riegel und 10 Packungen Chips vorratig. Warenbei diesem Vorrat die Warnleuchten beide eingeschaltet, so befandesich der Automat stattdessen im Zustand ({gelb, rot}, 20, 10).


Grundlagen 1

Relationen

Relation zwischen Mengen

Seien A und B Mengen. Eine (binare) Relation zwischen A und B(oder

”von A nach B“) ist eine Teilmenge ihres Kreuzprodukts.

R ⊆ A× B

Beispiel:A = {1, 2, 3} B = {a, b, c , d} R = {(1, a), (1, b), (2, b), (3, d)}Endliche Relationen konnen wie folgt dargestellt werden:

1

2

3

a

b

c

d


Grundlagen 1

Relationen

Auch”arithmetische“ Relationen passen zu dieser Definition, zum

Beispiel ≤ ⊆ N0 × N0, mit (0, 3) ∈ ≤ und (3, 2) 6∈ ≤.

Schreibweise:Wir notieren folgendermaßen, dass ein Paar in einer Relation liegt.

Standard-Schreibweise:(2, b) ∈ R

Infix-Schreibweise:2 R b

Fur Relationen wie =, <, ≤, >, ≥ wird fast immer dieInfix-Schreibweise verwendet (beispielsweise 2 < 5 und 7 ≥ 3).


Grundlagen 1

Relationen

Darstellung in Tabellenform:Das vorige Beispiel mit A = {1, 2, 3}, B = {a, b, c , d},R = {(1, a), (1, b), (2, b), (3, d)} lasst sich auch darstellen als:

a b c d

1 X X − −2 − X − −3 − − − X

Geht das auch bei Relationen zwischen unendlichen Mengen?


Grundlagen 1

Relationen

Weitere Beispiele:

{(x , sin x) | x ∈ R} ⊆ R× R

parall. Seiten rechte Winkel orthog. Diagonalen

Quadrat X X XDrachenviereck − − XParallelogramm X − −

Ingo

Selim

Petra

StrukturenMath.

Model-lierung


Grundlagen 1

Relationen

Umkehrung einer Relation

Sei R eine Relation zwischen A und B, also R ⊆ A× B.Die Umkehrung von R, bezeichnet mit R−1, entsteht durchVertauschen der Elemente in jedem enthaltenen Paar.

R−1 = {(b, a) | (a, b) ∈ R} ⊆ B × A

Beispiel:R:

1

2

3

a

b

c

d

R−1:

1

2

3

a

b

c

d


Grundlagen 1

Relationen

Beispiel fur Modellierung mit Relationen:

Betrachten wir erneut das einfache Snackautomaten-Szenario.Die Menge der moglichen Zustande des Automaten war:

P({gelb, rot})× {0, 1, . . . , 30} × {0, 1, . . . , 30}

Wenn wir dies als A× (B × C ) lesen, konnen wir eine binareRelation dafur aufstellen, welche Warnleuchtenkonstellationen beiwelchen Vorratsstanden kritisch sind. Zum Beispiel:

‘kritisch bei’ = {(W , (r , c)) | r + c > 60− 20 · |W |}

Dann:{gelb} ‘kritisch bei’ (25, 25)

{gelb, rot} ‘kritisch bei’ (20, 10)

aber nicht:{rot} ‘kritisch bei’ (20, 10)

{gelb, rot} ‘kritisch bei’ (5, 5)


Grundlagen 1

Relationen

Wir sehen uns einige besondere Arten von Relationen an:

Funktionen

Aquivalenzrelationen

Ordnungen


Grundlagen 1

Funktionen

Funktion (Abbildung) von der Menge A in die Menge B

Eine Relation R ⊆ A× B heißt Funktion, wenn folgendes gilt:

fur jedes Element a ∈ A gibt es genau ein Element b ∈ B mit(a, b) ∈ R.

Ublicherweise bezeichnet man solch spezielle Relationen, die alsoFunktionen sind, mit Kleinbuchstaben, etwa f statt R.

Anschaulich:

Jedes Element in A hat genau einen ausgehenden Pfeil.

In Tabellendarstellung enthalt jede Zeile genau ein Hakchen.

(Die meisten vorherigen Beispiels-Relationen waren also keineFunktionen.)


Grundlagen 1

Funktionen

Notation und Begriffe fur Funktionen

Um auszudrucken, dass eine Relation f ⊆ A× B sogar eineFunktion ist, schreibt man spezieller

”f : A→ B“.

Man bezeichnet A als Definitionsbereich und B als Wertebereich.Paare aus einem Element a ∈ A und dem (eindeutig gegebenen)Element b = f (a) ∈ B, auf welches die Funktion es abbildet,schreibt man, statt als

”(a, b)“, auch in der Form

”a 7→ b“.

Die gleiche Notation verwendet man, um eine allgemeineZuordnungsvorschrift anzugeben:

”a 7→ f (a)“.

Beispiel: Quadratfunktion auf der Menge der ganzen Zahlen

f : Z→ N0, f (z) = z2, bzw. Angabe als: z 7→ z2

Angabe konkreter Paare:

. . . , −3 7→ 9, −2 7→ 4, −1 7→ 1, 0 7→ 0, 1 7→ 1, 2 7→ 4, 3 7→ 9, . . .


Grundlagen 1

Funktionen

Weiteres Beispiel: Zuordnung Studierender zu Ubungsgruppen

Gruppe 1 Gruppe 2 Gruppe 3 Gruppe 4

Ingo − X − −Selim − − − X

Marina − − − XKiril X − − −Ewa − − X −...

......

......

Angabe konkreter Paare:

Ingo 7→ Gruppe 2, Selim 7→ Gruppe 4, Marina 7→ Gruppe 4, . . .

Angabe einer Zuordnungsvorschrift als mathematische Formel hiereher nicht moglich.


Grundlagen 1

Funktionen

Bild einer Menge, Urbild einer Menge

Sei f : A→ B eine Funktion und A′ ⊆ A. Dann nennt man dieMenge

f (A′) = {f (a) | a ∈ A′}

das Bild von A′ unter der Funktion f .

Sei andererseits B ′ ⊆ B. Dann nennt man die Menge

f −1(B ′) = {a ∈ A | f (a) ∈ B ′}

das Urbild von B ′ unter der Funktion f .


Grundlagen 1

Funktionen

Beispiel:

Gruppe 1 Gruppe 2 Gruppe 3 Gruppe 4

Ingo − X − −Selim − − − X

Marina − − − XKiril X − − −Ewa − − X −...

......

......

Bild der Menge {Kiril,Ewa} unter dieser Funktion:

f ({Kiril,Ewa}) = {Gruppe 1,Gruppe 3}Urbild der Menge {Gruppe 1,Gruppe 3} unter dieser Funktion:

f −1({Gruppe 1,Gruppe 3}) = {Kiril,Ewa, . . . }Auch interessant, Urbild einelementiger Mengen, etwa:

f −1({Gruppe 4}) = . . .Mathematische Strukturen Sommersemester 2017

Grundlagen 1

Funktionen

Weitere Beispiele:

1

2

3

a

b

c

d

f ({1, 2, 3}) = {a, b, d}f ({1, 2}) = {a, b}f −1({b, d}) = {2, 3}

sin : R→ R (= {(x , sin x) | x ∈ R})sin({k · π | k ∈ Z}) = {0} (und

”umgekehrt“)

Anmerkungen: (fur beliebige Funktionen f )

f (∅) = ∅, f −1(∅) = ∅Wenn A1 ⊆ A2, dann f (A1) ⊆ f (A2). (analog fur f −1)

Fur endliche A′ gilt |f (A′)| ≤ |A′|. (und fur f −1 ?)


Grundlagen 1

Funktionen

Kann man Funktionen eigentlich auch direkt umkehren?

Gedankengang:

Jede Funktion ist eine Relation.

Jede Relation kann man umkehren (R R−1).

Also warum denn nicht?


Grundlagen 1

Funktionen

Injektive Funktion

Eine Funktion f : A→ B heißt injektiv, falls es keine Elementea1, a2 ∈ A gibt mit a1 6= a2 und f (a1) = f (a2).

Alternativ: Eine Funktion f heißt injektiv, falls fur alle Elementea1, a2 ∈ A aus f (a1) = f (a2) immer a1 = a2 folgt.

Anschaulich:

Auf kein Element in B zeigt mehr als ein Pfeil.

In Tabelle enthalt jede Spalte hochstens ein Hakchen.

Welche der Beispielfunktionen sind injektiv?

Quadratfunktion?

Zuordnung Studierender zu Ubungsgruppen?

f : {1, 2, 3} → {a, b, c, d} mit 1 7→ a, 2 7→ b, 3 7→ d ?

sin ?Mathematische Strukturen Sommersemester 2017

Grundlagen 1

Funktionen

Surjektive Funktion

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

Alternativ: Eine Funktion f heißt surjektiv falls f (A) = B.

Anschaulich:

Auf jedes Element in B zeigt mindestens ein Pfeil.

In Tabelle enthalt jede Spalte mindestens ein Hakchen.

Welche der Beispielfunktionen sind surjektiv?

Quadratfunktion f : Z→ N0 mit z 7→ z2 ?

Zuordnung Studierender zu Ubungsgruppen?

f : {1, 2, 3} → {a, b, c, d} mit 1 7→ a, 2 7→ b, 3 7→ d ?

sin : R→ R ?


Grundlagen 1

Funktionen

Sind eigentlich alle Kombinationen der beiden gerade eingefuhrtenEigenschaften realisierbar?

Also, gibt es:

Funktionen, die weder injektiv noch surjektiv sind?

Funktionen, die injektiv, aber nicht surjektiv sind?

Funktionen, die nicht injektiv, aber surjektiv sind?

Funktionen, die sowohl injektiv als auch surjektiv sind?


Grundlagen 1

Funktionen

Bijektive Funktion

Eine Funktion f : A→ B heißt bijektiv, falls sie injektiv undsurjektiv ist.

Anschaulich:

Auf jedes Element in B zeigt genau ein Pfeil. Das heißt, esgibt eine Eins-zu-Eins-Zuordnung zwischen den Elementen desDefinitionsbereichs und denen des Wertebereichs.

In Tabelle enthalt jede Spalte genau ein Hakchen.


Grundlagen 1

Funktionen

Anmerkung:Ist f : A→ B bijektiv und ist eine der beiden Mengen A und Bendlich, so ist es auch die andere, und sie sind sogar gleich groß.

Begrundung:

Stellen wir uns f wieder als Relation in Tabellendarstellungvor, dann enthalt jede Zeile genau ein Hakchen (da f eineFunktion ist).

Da f injektiv sein soll, enthalt außerdem jede Spaltehochstens ein Hakchen.

Und da f auch surjektiv sein soll, enthalt jede Spaltemindestens ein Hakchen, folglich genau ein Hakchen.

Es gibt also genauso viele Hakchen wie Zeilen und genausoviele Hakchen wie Spalten. Also gleich viele Zeilen wie Spalten.

Daraus folgt die obige Anmerkung unmittelbar.


Grundlagen 1

Funktionen

Schließlich:

Die bijektiven Funktionen sind genau die invertierbaren Funktionen(umkehrbaren Funktionen).Zu jeder bijektiven Funktion f : A→ B gibt es eineUmkehrfunktion f −1 : B → A mit folgenden Eigenschaften:

f −1(f (a)) = a fur alle a ∈ A

f (f −1(b)) = b fur alle b ∈ B

Beispiel:

Die Funktionf : Z→ Z, z 7→ z − 1

hat als Umkehrfunktion

f −1 : Z→ Z, z 7→ z + 1


Grundlagen 1

Funktionen

Verknupfung (Komposition) von Funktionen

Gegeben seien zwei Funktionen f : B → C und g : A→ B.Mit f ◦ g bezeichnen wir die Verknupfung oderHintereinanderausfuhrung von g und f (in dieser Reihenfolge).Diese Funktion ist wie folgt definiert:

f ◦ g : A→ Ca 7→ f (g(a))

Das ist wirklich nur erlaubt, wenn der Definitionsbereich von fgleich dem Wertebereich von g ist.

Verdeutlichung:

Ag//

f ◦ g

AABf // C


Grundlagen 1

Funktionen

Beispiel: Funktionsverknupfung

1

2

a

b

c

d3

X

Y

Z

g f


Grundlagen 1

Funktionen

Beispiel: Funktionsverknupfung

1

2

3

X

Y

Z

f ◦ g


Grundlagen 1

Funktionen

Anmerkungen:

Die Bedingungen an die Umkehrfunktion f −1 : B → A einerbijektiven Funktion f : A→ B, zur Erinnerung:

f −1(f (a)) = a fur alle a ∈ A

f (f −1(b)) = b fur alle b ∈ B

entsprechen genau den folgenden beiden Forderungen:

f −1 ◦ f : A→ A, a 7→ a

f ◦ f −1 : B → B, b 7→ b

Außerdem gelten Zusammenhange wie:

(f ◦ g)−1 = g−1 ◦ f −1

(f −1)−1 = f


Grundlagen 1

Relationen

Wir betrachten nun spezielle Relationen (nicht mehr Funktionen),die auf nur einer Menge A definiert sind.

Aquivalenzrelation

Eine Relation R ⊆ A× A heißt Aquivalenzrelation, falls alle dreifolgenden Eigenschaften zutreffen:

Reflexivitat: fur alle a ∈ A gilt (a, a) ∈ R.

Transitivitat: fur jede Wahl von a1, a2, a3 ∈ A, falls sowohl(a1, a2) ∈ R als auch (a2, a3) ∈ R gilt, so muss auch(a1, a3) ∈ R gelten.

Symmetrie: fur jede Wahl von a1, a2 ∈ A, falls (a1, a2) ∈ Rgilt, so muss auch (a2, a1) ∈ R gelten.


Grundlagen 1

Relationen

Beispiel fur eine Aquivalenzrelation:

R = {(m, n) ∈ N0 × N0 | m und n lassen denselben Rest

bei ganzzahliger Division durch 3}= {(m, n) ∈ N0 × N0 | m mod 3 = n mod 3}

Bemerkungen:

Uberprufung von Reflexivitat und Symmetrie ist meist einfach(wie auch in obigem Beispiel), Uberprufung von Transitivitatnicht immer so sehr (selbst wenn sie gilt).

Reflexivitat und Symmetrie lassen sich auch leicht anschaulichetwa an Hand der Tabellendarstellung interpretieren. (Wie?)


Grundlagen 1

Relationen

Weitere Bemerkung:

Durch jede Aquivalenzrelation R ⊆ A× A zerfallt die MengeA in sogenannte Aquivalenzklassen.

Grafische Darstellung der Aquivalenzklassen fur das ebenbetrachtete Beispiel:

...

1

4

7...

0

3

6...

2

5

8


Grundlagen 1

Relationen

Formal:

Aquivalenzklassen

Sei R ⊆ A× A eine Aquivalenzrelation und a ∈ A. Dannbezeichnen wir als Aquivalenzklasse von a die Menge allerElemente, die mit a in dieser Relation stehen. Notation:

[a]R = {a′ ∈ A | (a, a′) ∈ R}

Bemerkungen:

Wegen der Symmetrie-Eigenschaft von Aquivalenzrelationenist es egal, ob in der obigen Definition (a, a′) ∈ R oder(a′, a) ∈ R steht.

Fur Elemente a1, a2 aus A gilt immer entweder [a1]R = [a2]Roder [a1]R ∩ [a2]R = ∅.


Grundlagen 1

Relationen

Weiteres Beispiel: Aquivalenzrelation”Besuch gleicher Ubungsgruppe“

Ingo Selim Kiril Marina Ewa · · ·Ingo X − − − − · · ·Selim − X − X − · · ·Kiril − − X − − · · ·

Marina − X − X − · · ·Ewa − − − − X · · ·...

......

......

.... . .

Die Aquivalenzklassen waren gerade die Ubungsgruppen-Mengen:

{Ingo, . . . }{Selim,Marina, . . . }{Kiril, . . . }{Ewa, . . . }


Grundlagen 1

Relationen

Weiteres Beispiel: Aquivalenzrelation”Besuch gleicher Ubungsgruppe“

Ingo Selim Kiril Marina Ewa · · ·Ingo X − − − − · · ·Selim − X − X X · · ·Kiril − − X − − · · ·

Marina − X − X − · · ·Ewa − − − − X · · ·...

......

......

.... . .

Diskussion:

Was wurde aus Symmetrie und Transitivitat folgen, wenn wirauch noch ein Hakchen bei Selim / Ewa setzen wollten?

Und was wurde das fur die Aquivalenzklassen bedeuten?


Grundlagen 1

Relationen

Beispiel: Nachweis der Eigenschaften einer Aquivalenzrelation

Gegeben sei:R = {(m, n) |

⌊m10

⌋=

⌊n10

⌋} ⊆ N0 × N0

wobei bqc fur eine rationale Zahl q ≥ 0 das Ergebnis beimAbrunden zur nachsten naturlichen Zahl ist.

Also zum Beispiel:⌊201710

⌋= b201,7c = 201.

Reflexivitat: Fur alle a ∈ N0 gilt (a, a) ∈ R genau dann wenn⌊a10

⌋=

⌊a10

⌋. Das trifft aber offensichtlich stets zu.

Transitivitat: Fur jede Wahl von a1, a2, a3 ∈ N0 soll, falls sowohl(a1, a2) ∈ R als auch (a2, a3) ∈ R gilt, auch(a1, a3) ∈ R gelten. Die beiden Voraussetzungenbedeuten

⌊a110

⌋=

⌊a210

⌋und

⌊a210

⌋=

⌊a310

⌋. Dann gilt

ja wohl auch:⌊a110

⌋=

⌊a310

⌋, also (a1, a3) ∈ R.

Symmetrie: ahnlich zu Nachweis der Transitivitat.


Grundlagen 1

Relationen

Eine weitere spezielle Form von Relationen auf einer Menge A:

(Partielle) Ordnung

Eine Relation R ⊆ A× A heißt (partielle) Ordnung, falls alle dreifolgenden Eigenschaften zutreffen:

Reflexivitat: wie bei Aquivalenzrelationen.

Transitivitat: wie bei Aquivalenzrelationen.

Antisymmetrie: fur jede Wahl von a1, a2 ∈ A, falls sowohl(a1, a2) ∈ R als auch (a2, a1) ∈ R gilt, so muss a1 = a2 gelten,d.h., a1 und a2 mussen dann das gleiche Element aus A sein.

Anmerkung:Aus der Schule kennen Sie vor allem totale Ordnungen, etwagemaß der Anordnung von Zahlen auf dem Zahlenstrahl:{(m, n) | m ≤ n} ⊆ N0 × N0. Diese erfullen auch die Eigenschaftenvon partiellen Ordnungen, aber noch Zusatzliches daruber hinaus!


Grundlagen 1

Relationen

Bei der Definition einer Ordnung hat sich gegenuber der Definitioneiner Aquivalenzrelation nur die letzte Eigenschaft geandert(Antisymmetrie versus Symmetrie).

Achtung:

Antisymmetrie ist nicht das Gegenteil von Symmetrie!

Insbesondere erfullt jede Relation der Form {(x , x) | x ∈ M} beideEigenschaften.


Grundlagen 1

Relationen

Beispiel:

Fur jede Menge M ist die Mengeninklusion ⊆ eine Ordnung aufder Potenzmenge P(M).

Diskussion: Warum ist das, außer wenn M = ∅,keine Aquivalenzrelation?


Grundlagen 1

Relationen

Ordnungen werden grafisch als sogenannte Hasse-Diagrammedargestellt:

Falls a1 R a2 (und a1 6= a2)gilt, dann:

liegt a1 unterhalb von a2und

liegen keine Elemente

”zwischen“ a1 und a2

(bezuglich R),

dann werden beide miteiner Linie verbunden.

Beispiel: P({x , y , z}) undInklusion ⊆

{x , y , z}

{x , y} {x , z} {y , z}

{x} {y} {z}

∅


Grundlagen 1

Relationen

Weiteres Beispiel: Teilbarkeit

Fur jedes n ∈ N0 ist die Relation

{(a1, a2) | a1 ist ein Teiler von a2} ⊆ {1, . . . , n} × {1, . . . , n}

eine Ordnung.

Zum Beispiel fur n = 6, als Hasse-Diagramm dargestellt:

4 6

2 3 5

1


Grundlagen 1

Relationen

Ein Nicht-Beispiel: Besuch gleicher Ubungsgruppe

Ingo Selim Kiril Marina Ewa · · ·Ingo X − − − − · · ·Selim − X − X − · · ·Kiril − − X − − · · ·

Marina − X − X − · · ·Ewa − − − − X · · ·...

......

......

.... . .

Warum ist Obiges keine Ordnungsrelation?


Grundlagen 1

Relationen

Sowie: (aus Mathematikunterricht 7. Klasse)

Viereck

Drachen Trapez

Parallelogramm symm. Trapez

Raute Rechteck

Quadrat

Warum ist Obiges kein Hasse-Diagramm (obwohl es tatsachlicheine Ordnungsrelation auf den Vierecks-Arten gibt)?


Grundlagen 1

Zahlenbereiche

Wir betrachten folgende spezielle Mengen von Zahlen:

Naturliche Zahlen mit 0

N0 = {0, 1, 2, 3, 4, 5, . . . }

Ganze Zahlen

Z = {. . . ,−5,−4,−3,−2,−1, 0, 1, 2, 3, 4, 5, . . . }


Grundlagen 1

Zahlenbereiche

Rationale Zahlen

Q: die Menge aller Bruche aus ganzen Zahlen (= Menge allerKommazahlen mit endlicher oder periodischer Dezimaldarstellung)

2 −4 12

277 0,75 32,333417 1

3 = 0,3333 . . . = 0,3

Reelle Zahlen

R: die Menge aller reellen Zahlen (= Menge aller Kommazahlenmit beliebiger – auch unendlicher, nicht-periodischer –Dezimaldarstellung)

2 −4 12

√2 = 1,41421 . . . π = 3,14159 . . .

e = 2,718281 . . .


Grundlagen 1

Rechnen mit Betragen

Fur jede Zahl z ∈ R (oder auch z ∈ Q oder z ∈ Z) bezeichnet |z |ihren Absolutwert oder Betrag:

|z | =

{z falls z ≥ 0−z sonst

Beispielsweise: |7| = 7, |0| = 0, |−3,5| = 3,5

Anmerkungen:

Das ist die gleiche Notation wie |M| bei Mengen, aber nichtdamit zu verwechseln.

Es gelten spezielle (jedoch leicht ersichtliche) Regeln wie

|a · b| = |a| · |b| und∣∣ ab

∣∣ = |a||b| , aber nicht |a + b| = |a|+ |b|

und |a− b| = |a| − |b|.Auch: |−z | = |z |, ||z || = |z |,

∣∣z2∣∣ = |z |2 = z2 und|k · z | = k · |z | fur k ≥ 0.


Documents

· Grundlagen 1 Mengen Element einer Menge Wir schreiben a 2M, falls ein Element a in der Menge M enthalten ist. Anzahl der Elemente einer Menge F ur eine endliche Menge M …