matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenMengenlehreÜberabzählbar Menge aller N->N
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
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.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]