M. Künzer, J. Marhenke

Lineare Algebra für Informatiker, WS 03/04

Lösung 1

Aufgabe 1.

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

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

(3) Es ist f({1, 3}) ∩ f({2, 3}) = {2, 3}, wohingegen f({1, 3} ∩ {2, 3}) = f({3}) = {3}. Insgesamt also (f({1, 3}) ∩ f({2, 3})) ∖ f({1, 3} ∩ {2, 3}) = {2}.

(4) Es ist f({1, 2, 3, 4}) = {1, 2, 3}, ferner f({1, 2, 3}) = {2, 3} und schließlich f({2, 3}) = {2, 3}. Also ist ⋂_{m≥0} f^{m}({1, 2, 3, 4}) = f^{2}({1, 2, 3, 4}) = {2, 3}.

Aufgabe 2.

(1) Es ist #\{X ^{\overline{}^{f}} X | f bijektiv\} = n · (n − 1) ⋯ 2 · 1 =: n!, es ist #𝔓(X) = 2^{n}. Es ist n! > 2^{n} für n ≥ 4, da dies für n < 4 nicht zutrifft, da es für n = 4 zutrifft, und da für n ≥ 4 beim Übergang von n nach n + 1 die linke Seite stärker wächst als die rechte (formal: Induktion über n).

(2) Es ist f injektiv genau dann, wenn #f^{−1}({x}) ≤ 1 für alle x ∈ X. Da ∑_{x∈X} #f^{−1}({x}) = #X = n, und da nur n Summanden auftreten, muß diesenfalls stets #f^{−1}({x}) = 1 gelten, i.e. f muß bijektiv und insbesondere auch surjektiv sein.

Umgekehrt, es ist f surjektiv genau dann, wenn #f^{−1}({x}) ≥ 1 für alle x ∈ X. Da ∑_{x∈X} #f^{−1}({x}) = #X = n, und da n Summanden auftreten, muß diesenfalls stets #f^{−1}({x}) = 1 gelten, i.e. f muß bijektiv und insbesondere auch injektiv sein.

(3) Es ist 𝔓(∅) = {∅}, 𝔓(𝔓(∅)) = {∅, {∅}}, und 𝔓(𝔓(𝔓(∅))) = {∅, {∅}, {{∅}}, {∅, {∅}}}.

(4) Wir haben

𝔓(X) ^{\overline{}^{∼}} \{X ^{\overline{}^{h}} \{0, 1\} | h beliebige Abbildung\}
U  \overline{}h_{U} : x \overline{}\{ \begin{matrix}1 & falls x ∈ U \\ 0 & falls x ∉ U \end{matrix}
h^{−1}(\{1\}) \overline{}h .

Die Abbildung h_{U} heißt auch charakteristische Funktion von U.

(5) Sei x ∈ X. Die gesuchte Anzahl ist a(n) := #\{X ^{\overline{}^{f}} X | #f^{2}(X) = 1\} =

n · #\{X ^{\overline{}^{f}} X | f^{2}(X) = \{x\}\}.

Wir behaupten, daß f^{2}(X) = {x} impliziert, daß f(x) = x. In der Tat, sei f(x) = y ≠ x. Dann ist f(y) = f^{2}(x) = x und also f^{2}(y) = y ≠ x, Widerspruch.

Das Urbild Y ⊆ X von {x} unter f muß also x enthalten, ist ansonsten aber beliebig.

Fixieren wir ein solches Y mit #Y = m ∈ [1, n]. Nun muß f die Teilmenge X ∖ Y nach Y ∖ {x} abbilden. Dafür gibt es (m − 1)^{n−m} Möglichkeiten. Hierbei ist 0^{0} := 1 gesetzt.

Für eine Teilmenge Y ⊆ X mit #Y = m, die x enthält, gibt es \frac{(n−1)!}{(m−1)!(n−m)!} =: (\begin{matrix}n−1 \\ m−1 \end{matrix}) Möglichkeiten. Insgesamt wird

a(n) = n ∑_{m∈[1,n]} (\begin{matrix}n−1 \\ m−1 \end{matrix}) (m − 1)^{n−m} .

Insbesondere werden a(1) = 1, a(2) = 2, a(3) = 9, a(4) = 40 und a(5) = 205.

Aufgabe 3.

(1) Es liegt ein abelsches Monoid vor. Es liegt keine Gruppe vor, da etwa 2 kein multiplikativ Inverses in Z ∖ {0} besitzt.

(2) Es liegt ein abelsches Monoid vor. Es liegt keine Gruppe vor, da etwa (1, 0) kein multiplikativ Inverses in R × R ∖ {(0, 0)} besitzt.

(3) Es liegt ein Monoid vor, mit 1_{X} als neutralem Element. Seien x, y ∈ X, x ≠ y.

Es liegt keine Gruppe vor, da etwa die Abbildung f : X \overline{}X, die y \overline{}x schickt und alle anderen Elemente auf sich selbst abbildet (man schreibt f|_{X∖{y}} = 1_{X∖{y}}), kein Inverses besitzt.

Das Monoid ist nicht abelsch. Sei g : X \overline{}X durch x \overline{}y und g|_{X∖\{x\}} = 1_{X∖\{x\}} erklärt. Dann ist (f ∘ g)(x) = x und (g ∘ f)(x) = y, also f ∘ g ≠ g ∘ f.

(4) Es liegt ein abelsches Monoid vor. Beachte dafür, daß der Schnitt zweier Äquivalenzrelationen wieder eine Äquivalenzrelation ist. Das neutrale Element ist durch E := X × X gegeben, d.h. durch die Äquivalenzrelation, die nur eine Äquivalenzklasse besitzt.

Sei D := {(x, x) | x ∈ X} die Äquivalenzrelation, für die alle Äquivalenzrelationen genau ein Element enthalten. Es ist wegen Reflexivität D in jeder Äquivalenzrelation enthalten, d.h. D ∩ R = D für alle R ∈ M. Wegen #X > 1 ist D ≠ E, und folglich ist die Gleichung D ∩ R = E nicht lösbar mit R ∈ M. Damit liegt keine Gruppe vor.

Aufgabe 4.

(1) Aussage ist falsch. Sei X = {1, 2}. Die Relation R = {(1, 1)} ist symmetrisch und transitiv, aber nicht reflexiv, da (2, 2) ∉ R.

Noch kleineres Beispiel: X = {1}, R = ∅.

(2) Aussage ist richtig.

Reflexiv. Es gilt stets x ∼ x, da stets f(x) = f(x).

Symmetrisch. Aus x ∼ y, d.h. aus f(x) = f(y), folgt stets f(y) = f(x), also y ∼ x.

Transitiv. Aus x ∼ y und y ∼ z, d.h. aus f(x) = f(y) und f(y) = f(z), folgt stets f(x) = f(z), d.h. x ∼ z.

Wir bemerken noch, daß umgekehrt für eine gegebene Äquivalenzrelation die Abbildung X \overline{}X/ ∼, x \overline{}x̄ existiert, die auf die beschriebene Weise die Äquivalenzrelation auch wieder hervorbringt.

(3) Aussage ist richtig.

Sei f surjektiv. Seien V, V′ ⊆ Y gegeben mit f^{−1}(V) = f^{−1}(V′). Ist v ∈ V, so gibt es ein x ∈ X mit f(x) = v, und insbesondere ist x ∈ f^{−1}(V). Also ist x auch in f^{−1}(V′), und es folgt v = f(x) ∈ V′. Damit ist V ⊆ V′ gezeigt. Genauso zeigt man V′ ⊆ V.

Sei nun 𝔓(Y) \overline{}𝔓(X) : V \overline{}f^{−1}(V) injektiv. Sei y ∈ Y gegeben. Wir haben zu zeigen, daß f^{−1}(\{y\}) ≠ ∅. Aber es ist bereits f^{−1}(∅) = ∅, und aus {y} ≠ ∅ folgt mit der gegebenen Injektivität, daß f^{−1}(∅) ≠ f^{−1}({y}). Mithin gibt es ein x ∈ X mit f(x) = y.

(4) Aussage ist falsch. Hier ist nun kein Gegenbeispiel zu geben, sondern eine Begründung anzuführen.

Auf der Menge X = ∅ kann man genau eine Äquivalenzrelation definieren, nämlich R = ∅.

Auf einer Menge X = {x} aus einem Element kann man ebenfalls genau eine Äquivalenzrelation definieren, entsprechend der Partition X = {x} in eine einzige Äquivalenzklasse.

Auf einer Menge X = {x, y} aus zwei Elementen kann man genau zwei Äquivalenzrelation definieren, entsprechend der Partition X = {x} ⊔ {y} und entsprechend der Partition X = {x, y}.

Auf einer Menge X = {x, y, z} aus drei Elementen kann man genau fünf Äquivalenzrelation definieren, entsprechend den Partitionen

X = {x} ⊔ {y} ⊔ {z}
= {x, y} ⊔ {z}
= {x, z} ⊔ {y}
= {y, z} ⊔ {x}
= {x, y, z} .

Bleibt zu zeigen, daß für eine Menge X mit #X > 3 auch ≥ 5 Äquivalenzrelationen definiert werden können. Dazu nehme man 3 Elemente x, y, z aus X heraus und partitioniere sie wie eben angegeben. Die Komplementmenge X ∖ {x, y, z} lasse man eine weitere Äquivalenzklasse bilden. Damit sind schon einmal 5 verschiedene Äquivalenzrelationen auf X definiert. (In der Tat gibt es natürlich noch weit mehr.)

Damit kann der Fall, daß genau 3 Äquivalenzrelationen erklärbar sind, bei keiner Anzahl von Elementen von X eintreten.