M. Künzer, J. Marhenke Abgabe bis Donnerstag, 23.10.03, 15h30, Briefkasten vor H3

Lineare Algebra für Informatiker, WS 03/04

Blatt 1

Aufgabe 1 (6 Punkte). Sei f : \{1, 2, 3, 4\} \overline{}\{1, 2, 3, 4\} definiert durch 1 \overline{}2, 2 \overline{}2, 3 \overline{}3, 4 \overline{}1. Bestimme folgende Teilmengen.

(1) f^{−1}({2, 3, 4}).

(2) f(f^{−1}(f({2, 3, 4}))).

(3) (f({1, 3}) ∩ f({2, 3})) ∖ f({1, 3} ∩ {2, 3}).

(4) ⋂_{m≥0} f^{m}({1, 2, 3, 4}).

Aufgabe 2 (5 Punkte). Sei X eine endliche Menge mit #X = n.

(1) Für welche n ∈ N ist #\{X ^{\overline{}^{f}} X | f bijektiv\} > #𝔓(X)?

(2) Sei X ^{\overline{}^{f}} X eine Abbildung. Zeige, daß f injektiv ist genau dann, wenn f surjektiv ist.

(3) Bestimme 𝔓(∅), 𝔓(𝔓(∅)) und 𝔓(𝔓(𝔓(∅))).

(4) Gib eine Bijektion an von 𝔓(X) nach \{X ^{\overline{}^{h}} \{0, 1\} | h beliebige Abbildung\}. Gib ihre Umkehrabbildung an.

(5) Bestimme #\{X ^{\overline{}^{f}} X | #f^{2}(X) = 1\} für n ∈ [1, 5].

Aufgabe 3 (4 Punkte). Sei M eine Menge, und sei M × M ^{\overline{}^{∗}} M, (x, y) \overline{}x ∗ y eine Operation auf M. Gib an, ob (M, ∗) ein Monoid, ein abelsches Monoid, eine Gruppe oder eine abelsche Gruppe ist. Begründe nur, wenn ein Begriff nicht zutrifft.

(1) (M, ∗) = (Z ∖ {0}, ·).

(2) M = R × R ∖ {(0, 0)}, und (x, y) ∗ (x′, y′) := (xx′, yy′) für x, y, x′, y′ ∈ R.

(3) Sei X eine Menge mit #X > 1, sei M die Menge der Abbildungen von X nach X, und sei f ∗ g := f ∘ g für f, g ∈ M.

(4) Sei X eine Menge mit #X > 1, sei M ⊆ 𝔓(X × X) die Menge der Äquivalenzrelationen auf X, und sei R ∗ S := R ∩ S für R, S ∈ M.

Aufgabe 4 (4 Punkte). Zeige, oder widerlege durch Angabe eines Gegenbeispiels.

(1) Ist eine Relation auf einer Menge X symmetrisch und transitiv, so ist sie auch reflexiv.

(2) Sei X ^{\overline{}^{f}} Y eine Abbildung, und sei auf X die Relation (∼) durch x ∼ y :⟺ f(x) = f(y) definiert. Es liegt eine Äquivalenzrelation vor.

(3) Sei X \overline{}Y eine Abbildung. Es ist f surjektiv genau dann, wenn die Abbildung 𝔓(Y) \overline{}𝔓(X) : V \overline{}f^{−1}(V) injektiv ist.

(4) Es gibt eine endliche Menge, auf der man genau 3 Äquivalenzrelationen definieren kann. (Diese Aussage ist durch Beispiel zu zeigen oder durch Begründung zu widerlegen.)

www.mathematik.uni-ulm.de/ReineM/kuenzer/WS03