www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Mengenlehre" - Überabzählbar Menge aller N->N
Überabzählbar Menge aller N->N < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Mengenlehre"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Überabzählbar Menge aller N->N: Beweis durch Widerspruch
Status: (Frage) beantwortet Status 
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.

        
Bezug
Überabzählbar Menge aller N->N: Antwort
Status: (Antwort) fertig Status 
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.


Bezug
                
Bezug
Überabzählbar Menge aller N->N: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Überabzählbar Menge aller N->N: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                
Bezug
Überabzählbar Menge aller N->N: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Mengenlehre"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.mathebank.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]