Abzählbarkeit von A,B,N

Question

ich besuche gerade die Analysis 1 Vorlesung und soll jetzt folgendes beweisen oder widerlegen

1. Die Menge Fun ({A,B},ℕ) aller Funktionen von {A,B} nach ℕ ist abzählbar.

2. Die Menge Fun (ℕ,{A,B}) aller Funktionen von ℕ nach {A,B} ist abzählbar.

Weiter weiß ich noch dass eine Menge abzählbar ist, falls es eine bijektive Funktion M--> N gibt mit N ⊆ℕ

Leider weiß ich nicht wie ich bei dem Beweis anfangen soll weil ich mich allgemein mit dem Beweisen noch schwer tue. Kann mir da jemand weiterhelfen oder sagen wie ich an eine solche Aufgabe herangehe?

Answer 1

1. Die Menge Fun ({A,B},ℕ) aller Funktionen von {A,B} nach ℕ ist abzählbar.

Eine Funktion f von  {A,B} nach ℕ ist durch das Paar ( f(A) , f(B) ) festgelegt, also ist

die Menge aller dieser Funktionen analog zu ℕ x ℕ abzählbar.

2. Die Menge Fun (ℕ,{A,B}) aller Funktionen von ℕ nach {A,B} ist abzählbar.

Denke dir A=0 und B=1 und betrachte eine solche Funktion f als

Folge    f(1) , f(2) , f(3) ,.....

Setze noch 0,  davor und du hast die Binärdarstellung einer Zahl aus dem Intervall [0;1]

wobei 0,Periode 0 als 0 und o,Periode 1 als 1 interpretiert wird und jede abbrechende

Dezimalzahl durch Periode 0 ergänzt wird.

Dann kannst du damit alle reellen Zahlen in  [0;1] darstellen, also ist die Menge nicht

abzählbar. Siehe Cantors 2. Diagonalargument.