Blatt #1, 17. Okt. 2002 Aufgabe 1.

(1) Ja. x ∈ X : (h ∘ (g ∘ f))(x) = h((g ∘ f)(x)) = h(g(f(x))) = (h ∘ g)(f(x)) = ((h ∘ g) ∘ f)(x).

(2) Ja. x, y ∈ X: g(f(x)) = g(f(y)) ⇒^{g inj.} f(x) = f(y) ⇒^{f inj.} x = y.

(3) Nein. X = {1}, Y = {2, 3}, Z = {4} mit f(1) = 2, g(2) = 4, g(3) = 4.

(4) Nein. X = {1, 2}, Y = {3}, f(1) = 3, f(2) = 3, U = {1}.

(5) Nein. X = {1}, Y = {2, 3}, f(1) = 2, V = {2, 3}.

(6) Ja. Ann: f ist surj. Dann ∃y ∈ X mit f(y) = {x ∉ f(x) | x ∈ X}. Man folgert: y ∉ f(y) ⇒

y ∈ f(y) und y ∈ f(y) ⇒ y ∉ f(y). Widerspruch. Aufgabe 2.

(1) U ⊂ 𝔓(X). Für jedes x ∈ X dürfen wir entweder x ∈ U oder x ∉ U wählen. Damit #𝔓(X) = 2^{n}.

(2) Für jedes x ∈ X hat man m Wahlmöglichkeiten für y ∈ Y, d.h. #{f : X → Y } = m^{n}.

(3) Beginnt man mit einem Element x ∈ X, so kann dieses auf m verschiedene y ∈ Y geschickt werden. Fixiert man eine solche Zuordnung, so verbleiben für ein x′ ∈ X \ {x} noch die Elemente Y \ {y}, d.h. noch m − 1. So fortfahrend erhält man die Anzahl der injektiven Abbildungen zu m(m − 1) ⋯ (m − n + 1). Beachte, daß dies Auswahl für m < n (natürlich) gleich 0 ist.

(4) Für das erste Element x von X das wir abbilden möchten, haben wir n Möglichkeiten uns f(x) zu wählen, Für das zweite haben wir n − 1 Möglichkeiten, für das dritte dann n − 2 usw. Insgesamt gibt es n! Bijektionen von X nach X. (Alternativ: Die Zahl der Injektionen von X nach X ist n! und bei Mengen mit gleicher Anzahl an Elementen ist injektiv und surjektiv dasselbe.)

Aufgabe 3.

(1) Definiere auf Z z.B. a ∼ b ⇔ a ≤ b. Dann ist für a, b, c ∈ Z:

• a ∼ a, da a ≤ a.

• a ∼ b, b ∼ c ⇒ a ≤ b, b ≤ c ⇒ a ≤ c, d.h. a ∼ c.

• Aber da 1 ∼ 2 und nicht 2 ∼ 1 ist die Relation nicht symmetrisch.

(2) Definiere auf Z z.B. a ∼ b ⇔ |a − b| ≤ 1. Dann ist für a, b ∈ Z:

• a ∼ a, da |a − a| = 0 ≤ 1.

• a ∼ b ⇒ |a − b| ≤ 1 ⇒ |b − a| ≤ 1 ⇒ b ∼ a.

• Da 1 ∼ 2 und 2 ∼ 3 aber nicht 1 ∼ 3 (|1 − 3| ≰ 1) ist die Relation nicht transitiv.

(3) Betrachte z.B. die leere Relation, d.h. (∼) = ∅ ⊆ Z × Z. Symmetrie und Transitivität sind erfüllt. (∼) ist nicht reflexiv, da es keine Elemente (x, x) ∈ ∅ gibt.

(4) Wir wollen zeigen, daß es sich um eine Äquivalenzrelation handelt. Seien hierzu x, y, z ∈ Z und x′, y′, z′ ∈ Z ∖ {0}. (Zu A 1) Es ist (x, x′) ∼ (x, x′), da xx′ = xx′. (Zu A 2) Wir folgern (x, x′) ∼ (y, y′) ⇔ xy′ = yx′ ⇔ yx′ = xy′ ⇔ (y, y′) ∼ (x, x′). (Zu A 3) Ist (x, x′) ∼ (y, y′) und (y, y′) ∼ (z, z′), so wird mit xy′ = yx′ und yz′ = zy′

xy′z′ = x′yz′ = x′y′z ,

und da y′ ≠ 0, so folgt xz′ = x′z, d.h. (x, x′) ∼ (z, z′). Ein Repräsentantensystem ist gegeben durch S = {(x, x′) ∈ X | x und x′ teilerfremd und x′ > 0}.

In der Tat ist zum einen (xz′, x′z′) ∼ (x, x′), so daß wir gemeinsame Faktoren in erster und zweiter Stelle kürzen dürfen. Zum anderen, sind (x, x′) und (y, y′) in S, und gilt (x, x′) ∼ (y, y′), so ist wegen xy′ = yx′ jeder Teiler von x auch ein Teiler von yx′. Da x und x′ teilerfremd sind, ist jeder Teiler von x ein Teiler von y. Dies gilt nun auch umgekehrt, jeder Teiler von y ist Teiler von x. Damit ist y = ±x. Aus x′, y′ > 0 folgt nun x = y. Ist x ≠ 0, so folgt auch x′ = y′. Ist x = 0, so folgt bereits aus der Definition von S, daß (0, x′), (0, y′) ∈ S impliziert, daß x′ = y′ = 1. In jedem Falle erhalten wir (x, x′) = (y, y′).

Eine Bijektion nach Q ist nun durch X/ ∼→ Q : \overline{(x, x′)} ↦ x/x′ gegeben. Diese repräsentantenweise definierte Abbildung hängt nicht vom Repräsentanten ab, da aus (x, x′) ∼ (y, y′), d.h. aus xy′ = yx′ folgt, daß x/x′ = y/y′. Die Abbildung ist ersichtlich surjektiv, es liegt jeder Bruch im Bild. Injektiv ist sie, da zwei Brüche x/x′ und y/y′ genau dann gleich sind, wenn xy′ = yx′.

Bemerkung. Diese Konstruktion kann zur Definition von Q herangezogen werden.

Aufgabe 4.

(1) Zunächst zeigen wir, daß es sich um eine Äquivalenzrelation handelt. Seien hierzu g, h, k ∈ G. (Zu A 1) Es ist g ∼ g wegen 1 ∈ U, und also g · 1 = g. (Zu A 2) Ist g ∼ h, so gibt es ein u ∈ U mit gu = h. Dann ist h = gu^{−1}, und also h ∼ g (Zu A 3) Ist g ∼ h und h ∼ k, so gibt es u, v ∈ U mit gu = h und hv = k. Es folgt guv = k,

was wegen uv ∈ U auch g ∼ k zeigt. Also ist (∼) eine Äquivalenzrelation, mit Äquivalenzklassen ḡ = {gu | u ∈ U}. Für alle g ist #ḡ = #U, da die Abbildung ḡ → U, x ↦ g^{−1}x bijektiv ist, wie man am

besten durch Angabe der Umkehrabbildung U → ḡ, y ↦ gy. Da G als disjunkte Vereinigung gleich großer Äquivalenzklassen geschrieben werden kann, ist

#G = #U · #(G/∼) .

Insbesondere ist #U ein Teiler von #G.

(2) Seien g, h ∈ G. Wegen g^{2} = 1 ist g^{−1} = g, wegen h^{2} = 1 ist h^{−1} = h. Aus (gh)^{2} = 1 folgt also gh = h^{−1}g^{−1} = hg. Somit ist G abelsch.

(3) Für x ∈ G wird

x_{r}^{−1}x = x_{r}^{−1}x((x_{r}^{−1})(x_{r}^{−1})_{r}^{−1})
= x_{r}^{−1}(x(x_{r}^{−1}))(x_{r}^{−1})_{r}^{−1}
= x_{r}^{−1}(x_{r}^{−1})_{r}^{−1}
= e_{r} .

Also ist jedes rechtsinverse Element von x auch linksinvers (in Wirklichkeit gibt es genau eines).

Weiter wird für x ∈ G mit dem eben Gezeigten

e_{r}x = (xx_{r}^{−1})x
= x(x_{r}^{−1})x)
= x ,

d.h. e_{r} ist auch linksneutrales Element. Damit gelten (G 2, 3).