Abzählbarkeit < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:22 Do 17.05.2012 | | Autor: | durden88 |
| Aufgabe | Ist die folgende Funktion abzählbar, überabzählbar oder höchstabzählbar?
Die Menge [mm] A=\{f :\IN -> \IN : f(n) = f(n + 1) \forall n \in \IN\} [/mm] |
Ich habe mich nochmals mit dieser Aufgabe beschäftigt und hoffe das ich es nochmal hinkriege, also:
Da f(n)=(n+1) gilt müssen alle nachfolge Funktionen von f(n) gleich sein, Beispiel:
f(1)=f(2)
f(2)=f(3)
f(3)=f(4)
usw.
daraus folgt eigendlich, dass es eine konstante Funktion ist: f(1)=f(2)=f(3)=f(4)=f(5)...
Egal welchen Wert die Funktion nun annehmen soll, er ist für alle Gleich. Ich kann aber auch unendlich viele Werte für die Funktionen nehmen.
So ist Beispielsweise all diese Funktionen [mm] \in [/mm] A:
[mm] f_1: \IN->\IN
[/mm]
n->1
[mm] f_2: \IN->IN
[/mm]
n->2
[mm] f_3: \IN->\IN
[/mm]
n->3
etc. pp
Das wiederum bedeutet: Ich habe unendlich viele Möglichkeiten, ohne Einschränkung bei den natürlichen Zahlen, sodass [mm] \IN->A [/mm] eine bijektion darstellt und es abzählbar ist?
Ist das ist richtig?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:55 Do 17.05.2012 | | Autor: | Marcel |
Hallo,
> Ist die folgende Funktion abzählbar, überabzählbar oder
> höchstabzählbar?
>
> Die Menge [mm]A=\{f :\IN -> \IN : f(n) = f(n + 1) \forall n \in \IN\}[/mm]
>
> Ich habe mich nochmals mit dieser Aufgabe beschäftigt und
> hoffe das ich es nochmal hinkriege, also:
>
> Da f(n)=(n+1) gilt müssen alle nachfolge Funktionen von
> f(n) gleich sein,
da verstehe ich - ehrlich gesagt - den Inhalt Deines Satzes nicht: Meinst Du, dass, wenn eine Funktion $f: [mm] \IN \to \IN$ [/mm] erfüllt [mm] $f(n+1)=f(n)\,$ [/mm] für alle $n [mm] \ge n_0\,,$ [/mm] dass dann schon [mm] $f(m)=f(n_0)$ [/mm] für alle natürlichen $m [mm] \ge n_0$ [/mm] gilt? Das stimmt!
> Beispiel:
>
> f(1)=f(2)
> f(2)=f(3)
> f(3)=f(4)
> usw.
>
> daraus folgt eigendlich, dass es eine konstante Funktion
> ist: f(1)=f(2)=f(3)=f(4)=f(5)...
Genau: Mit [mm] $A:=\{f: \IN \to \IN \text{ mit }f(n)=f(n+1) \text{ für alle }n \in \IN\}$ [/mm] gilt
[mm] $$A=\{g: \IN \to \IN:\;g \text{ ist eine konstante Funktion}\}$$
[/mm]
> Egal welchen Wert die Funktion nun annehmen soll, er ist
> für alle Gleich. Ich kann aber auch unendlich viele Werte
> für die Funktionen nehmen.
Du meinst: Es gibt unendlich viele Funktionen [mm] $\IN \to \IN\,,$ [/mm] die konstant sind!
> So ist Beispielsweise all diese Funktionen [mm]\in[/mm] A:
> [mm]f_1: \IN->\IN[/mm]
> n->1
> [mm]f_2: \IN->IN[/mm]
> n->2
> [mm]f_3: \IN->\IN[/mm]
> n->3
> etc. pp
Genau: [mm] $A=\{g: \IN \to \IN: g \text{ ist konstant}\}=\bigcup^d_{m \in \IN}\{h: \IN \to \IN: h(n)=m \text{ für alle }n \in \IN\}$
[/mm]
> Das wiederum bedeutet: Ich habe unendlich viele
> Möglichkeiten, ohne Einschränkung bei den natürlichen
> Zahlen, sodass [mm]\IN->A[/mm] eine bijektion darstellt und es
> abzählbar ist?
>
> Ist das ist richtig?
Das ist komisch ausgedrückt:
Wenn Du oben nochmal genau hinguckst, zeigt die Darstellung
[mm] $$A=\bigcup^d_{m \in \IN}\{h=h_m: \IN \to \IN: h(n)=h_m(n):=m \text{ für alle }n \in \IN\}\,,$$
[/mm]
doch gerade, dass [mm] $A\,$ [/mm] abzählbar ist: [mm] $\{h=h_m: \IN \to \IN: h(n)=h_m(n):=m \text{ für alle }n \in \IN\}$ [/mm] ist ja eine einelementige Menge, und abzählbare Vereinigungen abzählbarer Mengen sind abzählbar.
Wobei das ganze hier wirklich auch auf anderem, übersichtlichem Wege sehr schnell und einfach geht:
1.) Du hast ja bereits erkannt, dass [mm] $A=\{g: \IN \to \IN: \;g \text{ ist eine konstante Funktion}\}$ [/mm] gilt.
2.) Betrachte die Abbildung
$$v: [mm] \begin{cases} \IN \to A\\ \IN \ni m \mapsto v(m):=h_m \in A \end{cases}\,,$$
[/mm]
wobei für $m [mm] \in \IN$ [/mm] definiert sei
[mm] $$h_m:\begin{cases} \IN \to \IN \\ \IN \ni n \mapsto h_m(n):=m \end{cases}\,.$$
[/mm]
(Damit sieht man dann auch, dass in der Tat [mm] $h_m \in [/mm] A$ gilt!)
(Kurz: [mm] $v\,$ [/mm] ordnet jeder natürlichen Zahl $m [mm] \in \IN$ [/mm] die Abbildung [mm] $h_m\,$ [/mm] zu, wobei letztere einfach nur die konstante Abbildung [mm] $\IN \to \IN$ [/mm] ist, die nur den Wert [mm] $m\,$ [/mm] annimmt.)
Dann ist [mm] $v\,$ [/mm] eine Bijektion. (Du kannst die letzte Behauptung ja auch mal formal beweisen: Wohldefiniertheit ist klar (oder?); Injektivität ist leicht einzusehen und Surjektivität fast ebenso leicht.)
P.S.
Beachte bitte, dass Du oben siehst: [mm] $A^\IN$ [/mm] ist abzählbar. Dabei ist selber $A [mm] \subseteq \IN^{\IN}\,,$ [/mm] und die obige Aussage zeigt, dass sicherlich $A [mm] \subsetneqq \IN^{\IN}$ [/mm] gelten muss.
(Letzteres ist auch trivial, wenn man etwa mit der obigen Bijektion erkannt hat, dass [mm] "$A\,$ [/mm] im Wesentlichen nichts anderes wie [mm] $\IN$ [/mm] ist").
P.P.S.
Ich denke, dass Deine Gedanken schon in die richtige Richtung gegangen sind. Du musst aber daran arbeiten, klar und eindeutig auszudrücken, was Du eigentlich sagen willst. Es ist manchmal schwer, aus Deinen Fragen herauszulesen, was Du eigentlich meinst oder meinen könntest, weil Deine Formulierungen einfach entweder was anderes ausdrücken oder nicht klar genug sind. Beispielsweise:
> Das wiederum bedeutet: Ich habe unendlich viele
> Möglichkeiten, ohne Einschränkung bei den natürlichen
> Zahlen, sodass [mm]\IN->A[/mm] eine bijektion darstellt und es
> abzählbar ist?
Was ist "es" - dieses mysteriöse es, welches abzählbar sein soll? Welche Abbildung [mm] $\IN \to [/mm] A$ ist eine Bijektion? (Ich habe oben eine angegeben: [mm] $v\,$ [/mm] heißt sie bei mir.) Ich meine: Ohne Angabe kann man schlecht nachprüfen, dass die Abbildung eine Bijektion ist. Man erahnt aus Deinem Post, dass Du genau das machen willst, was ich mache (das erahnen meines Wissens nach aber nur die Wissenden: das heißt, Leute, die die Aufgabe selbst (so) lösen (könn(t)en)), aber Du schreibst es nirgends hin.
Das ist ein wenig fatal, dass Du das nicht aufschreibst:
Beispielsweise gibt es ja auch unendlich viele konstante Abbildungen [mm] $\IN \to \IR\,.$ [/mm] Trotzdem gibt es keine Bijektion [mm] $\IN \to \{r: \IN \to \IR:\; r\text{ ist eine konstante Abbildung}\}\,.$ [/mm] Warum? Eine injektive kann man leicht angeben - aber eine surjektive?
Gruß,
Marcel
|
|
|
|
