Universität Karlsruhe (TH) Karlsruhe, 17.10.1990 Mathematisches Institut II Dr. W. Trinks

Algebra I — Übungsblatt 1

Für eine Menge M bezeichne I_{M} := {(m, m) | m ∈ M} ⊆ M × M die Gleichheitsrelation auf M (= Diagonale von M).

Aufgabe 1 (3 Punkte) Seien M, N Mengen und K eine Korrespondenz von M nach N. Zeigen Sie: K ist Graph einer Funktion f: M → N genau dann, wenn K^{t} ∘ K ⊇ I_{M} und K ∘ K^{t} ⊆ I_{N}.

Aufgabe 2 (4 Punkte) ⊢ sei eine Relation auf einer Menge M, ⊣ die Umkehrrelation (⊣= ⊢^{t}) und ⊢⊣ :=⊢ ∪ ⊣. Für n ∈ IN, n ≥ 1 sei ⊢⊣^{n} := \underbrace{⊢⊣ ∘ ⋯ ∘ ⊢⊣}_{n mal}.

Zeigen Sie, daß ⊧| := I_{M} ∪ ⋃_{n=1}^{∞} (⊢⊣^{n})

(a) eine Äquivalenzrelation ist,

(b) die (im Sinne der Teilmengenrelation) kleinste Äquivalenzrelation ist, die ⊢ umfaßt.

Aufgabe 3 (4 Punkte) Für ein Monoid (M, ·) heißt x ∈ M

linksregulär, wenn ∀y, z ∈ M : (x · y = x · z ⇒ y = z);

rechtsregulär, wenn ∀y, z ∈ M : (y · x = z · x ⇒ y = z).

Finden Sie

(a) ein Monoid M und ein x ∈ M, das weder links- noch rechtsregulär ist,

(b) ein Monoid M und ein x ∈ M, das links-, aber nicht rechtsregulär ist.

Aufgabe 4 (4 Punkte)

Sei M die Halbgruppe ZZ/12ZZ , versehen mit der gewöhnlichen Restklassenmultiplikation. Wieviele Unter-Halbgruppen (gegenüber der Multiplikation abgeschlossene nichtleere Teilmengen) N von M gibt es? (Sollten Sie die Aufgabe mit dem Computer lösen, so legen Sie bitte Programmlisting und Ausführungsprotokoll bei.)

* Aufgabe 5 (5 Punkte) Für n ∈ IN sei M = IN^{n}. Auf M sei durch (x_{1}, …, x_{n}) ≤ (y_{1}, …, y_{n}) :⇔ x_{1} ≤ y_{1} ∧ … ∧ x_{n} ≤ y_{n} eine (Teil-)Ordnung definiert. Zeigen Sie: Es gibt keine unendlich langen Folgen (x_{r})_{r∈IN} in M, die ∀r, s : (r < s ⇒ x_{r} ≰ x_{s}) erfüllen. D.h. jede solche Folge bricht ab. (Hinweis: Induktion über n.)

Abgabe: Bis spätestens Dienstag, 23.10.1990, 11.15 Uhr in den Kasten bei Zi. 308 des Mathematikgebäudes oder in der Übung im Neuen Hörsaal.