Woche 3 – Vollständige Induktion, Äquivalenzrelation und co.

Summen-/Produktzeichen

1. Schreibe \(\sum\limits_{i = 1}^5 2i\) aus. Welchen Wert erhältst Du?
2. Schreibe \(\prod\limits_{i = 1}^5 2i\) aus. Welchen Wert erhältst Du?
3. Simplifiziere \((\sum\limits_{i = 1}^n i) + (\sum\limits_{i = 1}^n 2i)\) so weit Du kannst. Welche Rechenregeln hast Du benutzt?
4. Stimmt es, dass \(k \cdot \sum\limits_{i = 1}^n i = \sum\limits_{i = 1}^n ki\)? Warum? Gibt es eine Rechenregel, mit der das zusammenhängt?

Injektiv, surjektiv, bijektiv

1. Erklärt euch gegenseitig, was injektiv, surjektiv und bijektiv bedeuten. Nutzt Umgangssprache, und probiert es so simpel wie möglich zu erklären.
2. Alice sagt, dass eine Funktion die zwischen zwei gleichen Mengen abbildet genau dann injektiv ist, wenn sie surjektiv ist. Besprecht untereinander, ob Ihr dem zustimmt. Falls ihr unterschiedlicher Meinung seid, so versucht die korrekte Antwort zu finden.
3. Bob sagt, dass eine Funktion, die in eine grössere Menge abbildet¹, niemals surjektiv sein kann. Stimmt ihr dem zu? Warum? Könnt Ihr ein Gegenbeispiel finden?

Vollständige Induktion

1. Wozu benutzt man das Prinzip der vollständigen Induktion? Welches Problem löst es?

2. Womit fängt man bei der vollständigen Induktion an? Was muss man dort beweisen? Warum ist dieser Schritt nötig?

3. Wir wollen zeigen, dass eine bestimmte Aussage für alle natürlichen Zahlen gilt. In der Induktionsannahme nehmen wir an, dass diese Aussage für ein beliebiges \(n\) gilt. Nehmen wir damit nicht bereits an, dass die Aussage, die wir zeigen wollen, gilt?

4. Was muss man im Induktionsschritt tun?

5. Beweise mit vollständiger Induktion, dass \(\sum\limits_{i = 1}^n i = \frac{n \cdot (n+1)}{2}\).

   Überlege im Induktionsschritt ganz genau, wann Du die Induktionsannahme benutzen darfst.

Äquivalenzrelationen

1. Welche Eigenschaften hat eine Äquivalenzrelation? Gib für jede Eigenschaft die Definition an, und erkläre umgangssprachlich was diese Eigenschaft überhaupt bedeutet.
2. Welche Unterschiede/Gemeinsamkeiten gibt es zwischen Relationen und Äquivalenzrelationen?
3. Wir definieren eine Relation \(\sim\) durch \(A \sim B :\iff | A | = | B |\), wobei \(A, B\) Mengen sind. Ist dies eine Äquivalenzrelation? Warum?
4. Welche Elemente sind per Definition in der selben Äquivalenzklasse?
5. Gibt für die Relation aus Aufgabenteil 3 alle Äquivalenzklassen an.