Überabzählbar Menge aller N->N < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:43 Mo 24.11.2014 | | Autor: | asg |
| Aufgabe | | Zeigen Sie: Die Menge [mm] Abb(\mathbb{N}, \mathbb{N}) [/mm] ist nicht abzählbar. |
Hallo,
[mm] {Abb(\mathbb{N}, \mathbb{N})} [/mm] stellt die Menge aller Funktionen [mm] {f:\mathbb{N} \rightarrow \mathbb{N}}
[/mm]
Meine Lösung sieht wie folgt aus:
Zeige: es gibt keine surjektive Funktion [mm] {f:\mathbb{N} \rightarrow Abb(\mathbb{N}, \mathbb{N})}
[/mm]
Beweis durch Widerspruch:
Angenommen, [mm] {f:\mathbb{N} \rightarrow Abb(\mathbb{N}, \mathbb{N})} [/mm] ist surjektiv.
Sei
[mm] {M:=\{n \in \mathbb{N}:n\neq f(n)\}} [/mm] (*)
[mm] {\Rightarrow M \in Abb(\mathbb{N}, \mathbb{N})}
[/mm]
Da [mm] \\f [/mm] surjektiv ist, muss es ein [mm] \\{m \in \mathbb{N}\\} [/mm] geben, mit [mm] \\{f(m) \in M\\}
[/mm]
Es gibt zwei Fälle:
Fall 1: [mm] \\{m \neq f(m)\\}
[/mm]
Wegen [mm] \\{f(m) \in M\\} [/mm] gilt also [mm] \\{m = f(m)\\}
[/mm]
Gemäß (*) für [mm] \\{n:=m\\} [/mm] gilt [mm] \\{m \neq f(m)\\}
[/mm]
[mm] \Rightarrow [/mm] Widerspruch zum Fall 1, [mm] \\{m \neq f(m)\\}
[/mm]
Fall 2: [mm] \\{m = f(m)\\}
[/mm]
Wegen [mm] \\{f(m) \in M\\} [/mm] gilt also [mm] \\{m = f(m)\\}
[/mm]
Gemäß (*) für [mm] \\{n:=m\\} [/mm] gilt [mm] \\{f(m) \not\in M\\} \Rightarrow \\{m \neq f(m)\\}
[/mm]
[mm] \Rightarrow [/mm] Widerspruch zum Fall 2, [mm] \\{m = f(m)\\}
[/mm]
Da beide Fälle zum Widerspruch führen, ist die Funktion [mm] {f:\mathbb{N} \rightarrow Abb(\mathbb{N}, \mathbb{N})} [/mm] nicht surjektiv und somit ist die Menge [mm] {Abb(\mathbb{N}, \mathbb{N})} [/mm] nicht abzählbar. [mm] \\{q.e.d.\\}
[/mm]
Kann mir bitte jemand sagen, ob mein Beweis so korrekt ist, oder gibt es irgendwo Fehler?
Dankeschön vorab für jede Hilfe
Viele Grüße
Asg
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:07 Di 25.11.2014 | | Autor: | fred97 |
> Zeigen Sie: Die Menge [mm]Abb(\mathbb{N}, \mathbb{N})[/mm] ist nicht
> abzählbar.
> Hallo,
>
> [mm]{Abb(\mathbb{N}, \mathbb{N})}[/mm] stellt die Menge aller
> Funktionen [mm]{f:\mathbb{N} \rightarrow \mathbb{N}}[/mm]
>
> Meine Lösung sieht wie folgt aus:
> Zeige: es gibt keine surjektive Funktion [mm]{f:\mathbb{N} \rightarrow Abb(\mathbb{N}, \mathbb{N})}[/mm]
>
> Beweis durch Widerspruch:
>
> Angenommen, [mm]{f:\mathbb{N} \rightarrow Abb(\mathbb{N}, \mathbb{N})}[/mm]
> ist surjektiv.
>
> Sei
>
> [mm]{M:=\{n \in \mathbb{N}:n\neq f(n)\}}[/mm] (*)
Das ist sicher unfreiwillige Komik ! Mit Deiner Notation ist f(n) eine Abbildung f(n): [mm] \IN \to \IN. [/mm] Dann ist sicherlich n [mm] \ne [/mm] f(n). Für Deine Menge M gilt also
M= [mm] \IN.
[/mm]
>
> [mm]{\Rightarrow M \in Abb(\mathbb{N}, \mathbb{N})}[/mm]
Naja, dass M = [mm] \IN [/mm] ist, haben wir oben schon festgestellt
Somit gilt M [mm] \notin Abb(\mathbb{N}, \mathbb{N})
[/mm]
Dein "Beweis" kommt mir bekannt vor..... Wo hab ich das schon mal soähnlich gesehen ?
Bingo: Beweis für die Überabzählbarkeit der Potenzmenge einer abzählbar unendlichen Menge.
Gib zu: Du hast abgeschrieben.
FRED
>
> Da [mm]\\f[/mm] surjektiv ist, muss es ein [mm]\\{m \in \mathbb{N}\\}[/mm]
> geben, mit [mm]\\{f(m) \in M\\}[/mm]
>
> Es gibt zwei Fälle:
>
> Fall 1: [mm]\\{m \neq f(m)\\}[/mm]
> Wegen [mm]\\{f(m) \in M\\}[/mm] gilt also
> [mm]\\{m = f(m)\\}[/mm]
> Gemäß (*) für [mm]\\{n:=m\\}[/mm] gilt [mm]\\{m \neq f(m)\\}[/mm]
>
> [mm]\Rightarrow[/mm] Widerspruch zum Fall 1, [mm]\\{m \neq f(m)\\}[/mm]
>
> Fall 2: [mm]\\{m = f(m)\\}[/mm]
> Wegen [mm]\\{f(m) \in M\\}[/mm] gilt also
> [mm]\\{m = f(m)\\}[/mm]
> Gemäß (*) für [mm]\\{n:=m\\}[/mm] gilt [mm]\\{f(m) \not\in M\\} \Rightarrow \\{m \neq f(m)\\}[/mm]
>
> [mm]\Rightarrow[/mm] Widerspruch zum Fall 2, [mm]\\{m = f(m)\\}[/mm]
>
> Da beide Fälle zum Widerspruch führen, ist die Funktion
> [mm]{f:\mathbb{N} \rightarrow Abb(\mathbb{N}, \mathbb{N})}[/mm]
> nicht surjektiv und somit ist die Menge [mm]{Abb(\mathbb{N}, \mathbb{N})}[/mm]
> nicht abzählbar. [mm]\\{q.e.d.\\}[/mm]
>
>
> Kann mir bitte jemand sagen, ob mein Beweis so korrekt ist,
> oder gibt es irgendwo Fehler?
>
> Dankeschön vorab für jede Hilfe
>
> Viele Grüße
>
> Asg
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 06:33 Di 25.11.2014 | | Autor: | asg |
Guten Morgen,
danke für die Antwort.
Vorneweg: ja, ich habe den Beweis für die Potenzmenge verwendet und versucht ihn anzupassen. Wie es aber scheint, habe ich mich dabei sehr dumm angestellt :(
Die Idee ist doch eigentlich die selbe bei [mm] \\{f : \IN \to \mathcal{P}(\IN)\\} [/mm] und [mm] \\{f : \IN \to Abb(\IN, \IN)\\}, [/mm] nur dass die erste Funktion eine Menge von natürlichen Zahlen liefert und die zweite Funktion ein Element bzw. eine Zahl aus der Menge der natürlichen Zahlen zurückliefert.
Oder nicht??
Kannst du mir bitte sagen, in welche Richtung ich weitermachen kann?
Vielen Dank nochmals
Viele Grüße
Asg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:32 Di 25.11.2014 | | Autor: | fred97 |
> Guten Morgen,
>
> danke für die Antwort.
>
> Vorneweg: ja, ich habe den Beweis für die Potenzmenge
> verwendet und versucht ihn anzupassen. Wie es aber scheint,
> habe ich mich dabei sehr dumm angestellt :(
>
> Die Idee ist doch eigentlich die selbe bei [mm]\\{f : \IN \to \mathcal{P}(\IN)\\}[/mm]
> und [mm]\\{f : \IN \to Abb(\IN, \IN)\\},[/mm] nur dass die erste
> Funktion eine Menge von natürlichen Zahlen liefert und die
> zweite Funktion ein Element bzw. eine Zahl aus der Menge
> der natürlichen Zahlen zurückliefert.
> Oder nicht??
>
> Kannst du mir bitte sagen, in welche Richtung ich
> weitermachen kann?
Sei M eine nichtleere Teilmenge von [mm] \IN. [/mm] Konstruiere eine Abb. [mm] f_M \in Abb(\IN, \IN) [/mm] mit
[mm] f_M(\IN)=M.
[/mm]
Dann definiere die Abb. [mm] \phi:Abb(\IN,\IN) \to \mathcal{P}(\IN) [/mm] durch
[mm] \phi(f_M):=M [/mm]
und
[mm] \phi(f):= \emptyset, [/mm] falls f [mm] \ne f_M [/mm] für jede nichtleere Teilmenge M von [mm] \IN.
[/mm]
[mm] \phi [/mm] ist surjektiv !
Nun nimm an, es würde eine surjektive Abb. [mm] \psi: \IN \to Abb(\IN,\IN) [/mm] geben..
Dann wäre
[mm] \phi \circ \psi: \IN \to \mathcal{P}(\IN) [/mm] surjektiv.
FRED
>
> Vielen Dank nochmals
>
> Viele Grüße
>
> Asg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 05:59 Mi 26.11.2014 | | Autor: | asg |
Guten Morgen,
super, dankeschön für die Erklärung und den Beweis.
Viele Grüße
Asg
|
|
|
|
