Blatt 4 - Institut für Mathematik

Humboldt-Universität zu Berlin
Mathematisch-Naturwissenschaftliche Fakultät
Institut für Mathematik
Unter den Linden 6, D-10099 Berlin
Doz.Dr.sc. Werner Kleinert
Übungsaufgaben Algebra und Zahlentheorie (SoSe 2016)
Serie 4
Abgabe: 25.05.2016 in der Vorlesung
Aufgabe 1 (Peano-Systeme und vollständige Induktion (10 Punkte)).
Sei (S, s∗ , φ) ein Peano-System mit wohlbestimmter und eindeutiger Addition
sowie Multiplikation gemäß dem Dedekindschen Rekursionssatz. Zeige mittels
vollständiger Induktion:
(a) Für alle s ∈ S gilt s 6= φ(s), d.h.: kein Element von S ist sein eigener
Nachfolger.
(b) Es gilt t 6= s + t für alle (s, t) ∈ S × S.
(c) Es ist stets s∗ · t = t · s∗ und auch s · t = t · s für alle (s, t) ∈ S × S.
Aufgabe 2 (*(Bonusaufgabe) Mengenabbildungen und vollständige Induktion
(20 Puntke)).
Seien M eine Menge mit m ∈ N Elementen, N eine Menge mit n ∈ N
Elementen, wobei m ≤ n gelte. Zeige mittels vollständiger Induktion:
(a) Die Teilmenge Inj(M, N ) ⊂ Abb(M, N ) aller injektiven Abbildungen von
M nach N besitzt genau n!/(n − m)! Elemente.
(b) Ist m = n, so ist jede injektive Abbildung f ∈ Inj(M, N ) auch surjektiv, also sogar bijektiv, und insbesondere besitzt die Menge Bij(M ) :=
Bij(M, M ) aller bijektiven Selbstabbildungen (Permutationen) von M genau
n! Elemente.
(c) Sei wieder N eine Menge mit n ∈ N Elementen und k ∈ N mit k ≤ n.
Dann ist die Anzahl der Teilmengen B ∈ Pot(N ) mit jeweils k Elementen
genau
n!
n
:=
.
k
k!(n − k)!
Hier dürfen die Fakultätsfunktion und die Binomialkoeffizienten in bekannter
und üblicher Weise benutzt werden.
Aufgabe 3 (Peano-Systeme und Prinzip der kleinsten Zahl (10 Punkte)).
Sei (S, s∗ , φ) ein Peano-System mit der wohldefinierten Teilordnung ”≤” aus
der Vorlesung und dem daraus folgenden Prinzip der kleinsten Zahl. Zeige: Ist
T 6= ∅ eine nach oben beschränkte Teilmenge von S, so besitzt T ein (≤)-größtes
Element. (Hinweis: Wende das Prinzip der kleinsten Zahl für S auf eine von T
induzierte Teilmenge T̃ von S an!)
1
Aufgabe 4 (Beweise mittels vollständiger Induktion (10 Punkte)).
Beweise folgende Formeln mittels vollständiger Induktion für alle n ∈ N:
(a)
n
X
k2 =
k=1
n(n + 1)(2n + 1)
.
6
(b)
n
X
3
k =
k=1
n
X
!2
k
.
k=1
Vergessen Sie nicht,
1. die Lösungen jeder Aufgabe auf separaten Blättern abzugeben,
2. alle Blätter mit Name, Matrikelnummer und Übungsgruppe zu versehen,
3. Ihre Lösung stets auf Basis der Vorlesung bzw. Übung zu begründen.
2

Download Report