Aufgabe 21

Eine binäre Folge ist eine Folge, deren Elemente nur 0 und 1 sind. Besteht eine solche Folge aus n Komponenten, so spricht man von einer binären Folge der Länge n. Wie groß ist die Anzahl der binären Folgen der Länge n?

[Hinweis: Wenn Sie das nicht schnell sehen, schreiben Sie alle binären Folgen der Länge 2 und 3 auf; dann erhalten Sie eine Vermutung, die Sie dann „nur noch“ beweisen müssen.]

Aufgabe 19

Studieren Sie den Beweis des Satzes über Potenzmengen genau, und machen Sie sich klar, dass wir mehr bewiesen haben: Es gibt keine surjektive Abbildung von X nach P(X).

Aufgabe 18

Machen Sie sich klar, dass \mathbb{N} und die Menge der reellen Zahlen zwischen 0 und 1 nicht gleichmächtig sind.

Aufgabe 16

Zeigen Sie:

(a) Es gibt unendlich viele Primzahlen.

(b) \mathbb{Z} und die Menge P aller Primzahlen sind gleichmächtig.

Aufgabe 13

Sei f eine Abbildung einer Menge X in eine Menge Y. Zeigen Sie:

(a) Wenn X endlich ist, so gilt: f ist injektiv \Leftrightarrow f hat genau |X| Bilder

(b) Sind X und Y endlich und ist |X|=|Y|, so gilt:

f ist injektiv  \Leftrightarrow  f ist surjektiv.

(c) (Äquivalenz von Injektivität und Surjektivität) Wenn f eine Abbildung einer endlichen Menge in sich ist, so gilt:

f ist injektiv  \Leftrightarrow  f ist surjektiv  \Leftrightarrow. f ist bijektiv

(d) Zeigen Sie, dass die Aussage (c) falsch ist, wenn X eine unendliche Menge ist. [Wählen Sie zum Beispiel X = \mathbb{Z}.]

Aufgabe 12

Zeigen Sie den Satz über die Bijektivität invertierbarer Abbildungen:

Sei f:X \to Y eine Abbildung. Wenn es eine Abbildung f':Y \to X gibt, so dass gilt

f \circ f' = id_Y  und  f' \circ f = id_X ,

dann ist f bijektiv.