DeutschINSA, STH1 Oktober 2011

MERKBLATT - ALGEBRA

I– Allgemeine Methode
1. Die Voraussetzungen auf das Blatt aufschreiben.
2. Was ich beweisen muss : Automatismen (s. unten).
3. Die Voraussetzungen benutzen, um daraus Folgerungen zu ziehen.

II– Über Quantoren...

Jeder Buchstabe muss definiert werden, bevor er benützt wird :
1. Muss ich beweisen, dass etw. für allen x ∈ E gilt, dann fange ich mit Sei x ∈ E“ an und zeige, dass x die Bedingung
”
erfüllt.
2. Muss ich beweisen, dass es x ∈ E existiert so, dass etw. gilt, dann muss ich ein festes x finden, das diese Bedingung
erfüllt.
3. Muss ich zeigen, dass etw. falsch ist, dann brauche ich nur ein Gegenbeispiel zu finden.

III– Mengenlehre
Zu beweisen ist z.B. Methode(n) Automatismen
Anfang Ende

Eine Inklusion Zeigen, dass jedes Element

A⊂B a∈A⇒ (...) ⇒a∈B
von Mengen aus A zu B gehört

Zeigen, dass jedes Element

gehört zu M genau dann, x∈M ⇔ (...) ⇔x∈N
Eine Gleichheit wenn es zu N gehört
M =N
von Mengen 
Zeigen, dass M ⊂ N und (x ∈ M ⇒ (...) ⇒ x ∈ N ) ⇒ M ⊂ N
Folgt M = N
dass N ⊂ M (y ∈ N ⇒ (...) ⇒ y ∈ M ) ⇒ N ⊂ M

Eine Alternative : (¬b) ⇒ (...) ⇒ (¬a)

Eine Implikation (a) ⇒ (b)
Die Kontraposition (nicht b) ⇒ (...) ⇒ (nicht a)

Zeigen, dass p wahr ist

(p) ⇔ (...) ⇔ (q)
genau dann, wenn q wahr ist

Zeigen, dass (p) ⇒ (q) und (p) ⇒ (...) ⇒ (q)
Eine Äquivalenz (p) ⇔ (q) Folgt (p) ⇔ (q)
dass (q) ⇒ (p) (q) ⇒ (...) ⇒ (p)

Zeigen, dass (p) ⇒ (q) und (p) ⇒ (...) ⇒ (q)
Folgt (p) ⇔ (q)
dass (¬p) ⇒ (¬q) (¬p) ⇒ (...) ⇒ (¬q)

Algebra 1 Methoden für Mengen- und Relationenalgebra

DeutschINSA, STH1 Oktober 2011

IV– Relationen und Abbildungen

1) Was bedeutet ...
R bezeichnet eine Relation ; clR (x) bezeichnet die Äquivalenzklasse von x (Kx )

y ∈ R(A) ⇔ ∃x ∈ A | xRy
x(R ◦ R)z ⇔ ∃y ∈ E | (xRy ∧ yRz)
x ∈ R−1 (B) ⇔ ∃y ∈ B | xRy
(x ∈ D(f )) f (x) = das einzige y ∈ W (f ) | xf y (ergibt einen Sinn nur wenn f eine Funktion ist)
clR (x) = alle y ∈ E | xRy (x ist ein bestimmtes Element aus E und x ∈ clR (x))
(öfter muss man eine Gleichung mit Unbekannten y lösen)

2) Beweisautomatismen

Zu beweisen ist z.B. Methode(n) Automatismen

Anfang Ende

Mit Äquivalenzen xRy ⇔ (...) ⇔ xR0 y

Sei (x, y) ∈ E × E 0 so dass xRy


Eine Gleichheit

R = R0 Folgt xR0 y

(...)


von Relationen

Mit 2 Implikationen Folgt R = R0
0 0
Sei (x, y) ∈ E × E so dass xR y




(...) Folgt xRy


Reflexivität Sei x ∈ E (...) Folgt xRx : R ist reflexiv

Sei (x, y) ∈ E 2 so, dass xRy

Symmetrie
(...) Folgt yRx : R ist symmetrisch
Eigenschaften
einer Relation Sei (x, y) ∈ E 2 so,
Antisymmetrie
dass xRy und yRx (...) Folgt x = y : R ist antisymmetrisch

Sei (x, y, z) ∈ E 3 so,

Transitivität
dass xRy und yRz (...) Folgt xRz : R ist transitiv

Sei (x1 , x2 ) ∈ E 2 so,

dass f (x1 ) = f (x2 ) (...) Folgt x1 = x2 : f ist injektiv
Injektivität
Sei (x1 , x2 ) ∈ E 2 so,
dass x1 6= x2 (...) Folgt f (x1 ) 6= f (x2 ) : f ist injektiv

Eigenschaften Sei y ∈ E 0 . Zeigen wir, dass ∃x ∈ E | f (x) = y

Surjektivität
einer Funktion (...) [eventuell : Sei x = (...) Folgt f (x) = y] : f ist surjektiv

Injektivität von f : (...) f injektiv
Folgt f bijektiv
Surjektivität von f : (...) f surjektiv
Bijektivität
Sei y ∈ E 0 Zeigen wir, dass ∃!x ∈ E | f (x) = y
(...) [eventuell f −1 bestimmen] : f ist bijektiv

Algebra 1 Methoden für Mengen- und Relationenalgebra