abzählbare Menge, sur. Fkt. < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeigen Sie, dass eine Menge X genau dann abzählbar ist, wenn es eine surjektive Funktion [mm] $f:\mathbb{N}\to [/mm] X$ gibt. |
Hallo,
wäre jemand so lieb mir ein Feedback zu meinem Beweis zu geben?
Beweis:
[mm] $\Rightarrow$
[/mm]
Sei $X$ eine abzählbare Menge. Wenn [mm] $|X|=n<\infty$ [/mm] mit [mm] $X=\{x_0,\dotso, x_{n-1}\}$, [/mm] wähle [mm] $f:\mathbb{N}\to [/mm] X$ mit [mm] $f(n)=x_n$. [/mm] Dies ist offensichtlich surjektiv.
Wenn X unendlich ist, dann gibt es nach Definition eine bijektive Funktion
[mm] $g:X\to\mathbb{N}$. [/mm] Da $g$ bijektiv ist, hat g eine bijektive Umkehrfunktion [mm] $g^{-1}:\mathbb{N}\to [/mm] X$. Insbesondere ist [mm] $g^{-1}$ [/mm] surjektiv.
[mm] $\Leftarrow$
[/mm]
Sei [mm] $f:\mathbb{N}\to [/mm] X$ surjektiv. Dann existiert eine rechtsinverse Funktion $g: [mm] X\to\mathbb{N}$ [/mm] mit [mm] $f\circ g=\operatorname{id}$ [/mm] und $g$ ist injektiv.
Also ist $X$ abzählbar.
Vielen Dank fürs drüber schauen.
mfg
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:57 So 26.04.2015 | | Autor: | tobit09 |
Hallo impliziteFunktion!
Wie habt ihr "abzählbar" definiert?
Die Behauptung aus der Aufgabenstellung ist übrigens nicht ganz korrekt:
Die leere Menge ist abzählbar, ohne dass es eine surjektive Abbildung [mm] $f\colon \IN\to\emptyset$ [/mm] gibt.
Aber indem man X als nichtleer voraussetzt, lässt sich die Behauptung "retten".
Viele Grüße
Tobias
|
|
|
| |
|
Abzählbar hatten wir so definiert:
Eine Menge X ist abzählbar, wenn X endlich ist, es gibt eine bijektive Funktion [mm] $f:X\to\mathbb{N}$
[/mm]
Die Voraussetzung, dass X nicht leer ist, scheinen wir nicht getroffen zu haben.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:39 So 26.04.2015 | | Autor: | Marcel |
Hallo,
> Abzählbar hatten wir so definiert:
>
> Eine Menge X ist abzählbar, wenn X endlich ist, es gibt
> eine bijektive Funktion [mm]f:X\to\mathbb{N}[/mm]
wie habt ihr *endlich* definiert? Möglich ist:
Eine Menge [mm] $X\,$ [/mm] heißt endlich, falls [mm] $X=\varnothing$, [/mm] oder falls es ein $N [mm] \in \IN$ [/mm] so gibt, dass
eine surjektive Abbildung
$f [mm] \colon \{1,\ldots,N\} \to [/mm] X$
existiert.
Danach kommt dann meist ein Satz: Ist die nichtleere Menge [mm] $X\,$ [/mm] endlich, so
existiert
[mm] $n:=\min\{N \in \IN\mid \exists f \colon \{1,\ldots,N\}\to X\text{ surjektiv}\}\,.$
[/mm]
Genau die surjektiven Abbildungen $f [mm] \colon \{1,\ldots,\red{\,n\,}\} \to [/mm] X$ sind dann
bijektiv, und man setzt für nichtleeres [mm] $X\,$ [/mm] wie oben
$|X|:=n$ und [mm] $|\varnothing|:=0\,.$
[/mm]
Natürlich gibt es auch andere Strategieren: Für nichtleeres [mm] $X\,$ [/mm] definiert man
[mm] $|X|\,$ [/mm] als diejenige natürliche Zahl [mm] $n\,$, [/mm] für die eine bijektive Abbildung
$f [mm] \colon \{1,...,n\} \to [/mm] X$ (oder $f [mm] \colon [/mm] X [mm] \to \{1,...,n\}$)
[/mm]
existiert. Damit man das aber überhaupt machen darf, muss man dann
zeigen, dass dieses [mm] $n\,$ [/mm] auch eindeutig ist, d.h.:
Sind $f [mm] \colon \{1,...,n\} \to [/mm] X$ und $g [mm] \colon \{1,...,m\} \to [/mm] X$ (mit $m,n [mm] \in \IN$) [/mm] beide bijektiv,
so folgt [mm] $n=m\,.$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
Endlich hatten wir wie folgt definiert:
Eine Menge X ist endlich, wenn es eine bijektive Funktion
[mm] $f:X\to\{0,\dotso, n-1\}$ [/mm] für ein [mm] $n\in\mathbb{N}$ [/mm] gibt.
Wir scheinen also die von dir letztgenannte Strategie gewählt zu haben, auch wenn wir nicht die Eindeutigkeit gezeigt haben.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:22 So 26.04.2015 | | Autor: | Marcel |
Hallo,
> Endlich hatten wir wie folgt definiert:
>
> Eine Menge X ist endlich, wenn es eine bijektive Funktion
>
> [mm]f:X\to\{0,\dotso, n-1\}[/mm] für ein [mm]n\in\mathbb{N}[/mm] gibt.
>
> Wir scheinen also die von dir letztgenannte Strategie
> gewählt zu haben, auch wenn wir nicht die Eindeutigkeit
> gezeigt haben.
ja, denn [mm] $\{1,..,n\}$ [/mm] und [mm] $\{0,...,n-1\}$ [/mm] sind *gleich groß*.
Bei dieser Definition der Endlichkeit braucht man ja auch die Eindeutigkeit
nicht, sondern nur die Existenz. Aber um [mm] $|X|:=n\,$ [/mm] setzen zu können, braucht
ihr die Eindeutigkeit!
Gruß,
Marcel
|
|
|
| |
|
Das heißt also, dass wenn ich in meinem Beweis die Kardinalität der Menge angeben möchte, ich vorher die Eindeutigkeit dieser bijektiven Abbildung zeigen muss, damit es Sinn ergibt bzw. ich das machen darf?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:33 Mo 27.04.2015 | | Autor: | tobit09 |
> Das heißt also, dass wenn ich in meinem Beweis die
> Kardinalität der Menge angeben möchte, ich vorher die
> Eindeutigkeit dieser bijektiven Abbildung zeigen muss,
> damit es Sinn ergibt bzw. ich das machen darf?
Es geht nicht um eine Eindeutigkeit der bijektiven Abbildung [mm] $f:X\to\{0,\dotso, n-1\} [/mm] $, sondern "nur" um die Eindeutigkeit der natürlichen Zahl $n$, für die es es so eine bijektive Abbildung gibt.
Genau genommen ist die Eindeutigkeit dieser Zahl $n$ zu zeigen, bevor man von der Kardinalität/Mächtigkeit $|X|$ einer endlichen Menge $X$ sprechen kann.
Aber in Anfängervorlesungen wird dieser technische Beweis meist ausgelassen und trotzdem mit $|X|$ gearbeitet.
Häufig wird $|X|$ auch gar nicht formal definiert, sondern anschaulich als "Anzahl der Elemente von X" eingeführt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:34 Mo 27.04.2015 | | Autor: | Marcel |
Hallo,
> > Das heißt also, dass wenn ich in meinem Beweis die
> > Kardinalität der Menge angeben möchte, ich vorher die
> > Eindeutigkeit dieser bijektiven Abbildung zeigen muss,
> > damit es Sinn ergibt bzw. ich das machen darf?
> Es geht nicht um eine Eindeutigkeit der bijektiven
> Abbildung [mm]f:X\to\{0,\dotso, n-1\} [/mm], sondern "nur" um die
> Eindeutigkeit der natürlichen Zahl [mm]n[/mm], für die es es so
> eine bijektive Abbildung gibt.
so ist es. Bijektive Abbildungen $X [mm] \to \{0,...,n-1\}$ [/mm] gibt es ja *viele* - man kann
sogar genau sagen, wieviele es gibt: [mm] $n!\,$ [/mm] an der Zahl. 
> Genau genommen ist die Eindeutigkeit dieser Zahl [mm]n[/mm] zu
> zeigen, bevor man von der Kardinalität/Mächtigkeit [mm]|X|[/mm]
> einer endlichen Menge [mm]X[/mm] sprechen kann.
Genau. Geht man aber den Weg über die Surjektivität, so braucht man das
nicht - dann kann man [mm] $n:=\min\{N \in \IN \mid f \colon \{0,...,N-1\} \to X, f \text{ surjektiv}\}$ [/mm] setzen,
wobei nur kurz zu begründen ist, warum die Menge rechterhand auch ein
Minimum hat.
Die *Schönheit*, dass für [mm] $|X|=n\,$ [/mm] dann eine surjektive Abbildung $f [mm] \colon \{0,...,n-1\} \to [/mm] X$ schon
bijektiv ist, ist hier dann aber nicht trivial.
> Aber in Anfängervorlesungen wird dieser technische Beweis
> meist ausgelassen und trotzdem mit [mm]|X|[/mm] gearbeitet.
>
> Häufig wird [mm]|X|[/mm] auch gar nicht formal definiert, sondern
> anschaulich als "Anzahl der Elemente von X" eingeführt.
Naja, man sagt halt gerne: "Wir können schon zählen." Oder auch: "Eine
Menge ist endlich, wenn wir beim Durchzählen der Menge irgendwann zum
Abbruch kommen, weil wir alle Elemente erfasst haben."
(So mancher Informatiker würde das sicher nicht anders ausdrücken.
Vielleicht noch mit dem Wort "... terminiert."  )
Mathematisch jetzt nicht wirklich sauber, aber wie das anzuwenden ist,
würden sicher die meisten dennoch verstehen...
Ist halt auch immer die Frage, inwieweit das im Folgenden gebraucht wird
bzw. das Vorangegangene auch detailliert verstanden worden sein
musste.
Gruß,
Marcel
|
|
|
| |
|
> Zeigen Sie, dass eine Menge X genau dann abzählbar ist,
> wenn es eine surjektive Funktion [mm]f:\mathbb{N}\to X[/mm] gibt.
>
> Hallo,
>
> wäre jemand so lieb mir ein Feedback zu meinem Beweis zu
> geben?
>
> Beweis:
>
> [mm]\Rightarrow[/mm]
>
> Sei [mm]X[/mm] eine abzählbare Menge. Wenn [mm]|X|=n<\infty[/mm] mit
> [mm]X=\{x_0,\dotso, x_{n-1}\}[/mm], wähle [mm]f:\mathbb{N}\to X[/mm] mit
> [mm]f(n)=x_n[/mm].
Dies ist keine Abbildung. Erstens mal kannst du nicht [mm] $f(n)=\dots$ [/mm] schreiben, weil du $n$ zu Beginn als Mächtigkeit von $X$ definiert hast, sondern du brauchst hier einen anderen Variablennamen. Aber auch [mm] $f(k)=x_k$ [/mm] liefert keine Abbildung. Was soll denn z.B. $f(n)$ sein? Ein so genanntes [mm] $x_n$ [/mm] haben wir hier keines. Die Idee lässt sich aber durch Fallunterscheidung retten. [mm] $f(k)=x_k$ [/mm] für [mm] $k\le [/mm] n-1$ ist schon einmal eine gute Wahl. Für [mm] $k\ge [/mm] n$ brauchst du auch noch eine Festlegung. Bedenke hierbei die Anmerkung von tobit09!
> Dies ist offensichtlich surjektiv.
> Wenn X unendlich ist, dann gibt es nach Definition eine
> bijektive Funktion
> [mm]g:X\to\mathbb{N}[/mm]. Da [mm]g[/mm] bijektiv ist, hat g eine bijektive
> Umkehrfunktion [mm]g^{-1}:\mathbb{N}\to X[/mm]. Insbesondere ist
> [mm]g^{-1}[/mm] surjektiv.
>
> [mm]\Leftarrow[/mm]
>
> Sei [mm]f:\mathbb{N}\to X[/mm] surjektiv. Dann existiert eine
> rechtsinverse Funktion [mm]g: X\to\mathbb{N}[/mm] mit [mm]f\circ g=\operatorname{id}[/mm]
> und [mm]g[/mm] ist injektiv.
> Also ist [mm]X[/mm] abzählbar.
Wenn ihr das benutzen dürft, dass surjektive Funktionen rechtsinvertierbar sind (das ist das so genannte Auswahlaxiom), dann ist das bis hierhin ein guter Ansatz. Ich würde aber gerne noch fertig bewiesen sehen, weshalb $X$ nun endlich oder gleichmächtig zu [mm] $\IN$ [/mm] ist.
> Vielen Dank fürs drüber schauen.
>
> mfg
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
Du hast recht. Das war natürlich ungeschickt hier die Variable n zu nehmen.
Denn benötige ich also die Fälle
1. [mm] $X=\emptyset$
[/mm]
2. $|X|=n$ wobei [mm] $0
und 3. X ist eine unendliche Menge.
Der erste Fall ist trivial, weil die leere Menge eine endliche Menge ist und die sind abzählbar.
Der zweite Fall ist aber auch trivial, weil X nun mal endlich ist, ich weiß gar nicht weshalb ich hier unbedingt eine Abbildung angeben wollte, das sollte doch unnötig sein.
Der einzige interessante Fall, ist der dritte, wenn X eine unendliche Menge ist.
Und auch dies folgt unmittelbar aus der Definition.
> Wenn X unendlich ist, dann gibt es nach Definition eine
> bijektive Funktion
> $ [mm] g:X\to\mathbb{N} [/mm] $. Da $ g $ bijektiv ist, hat g eine bijektive
> Umkehrfunktion $ [mm] g^{-1}:\mathbb{N}\to [/mm] X $. Insbesondere ist
> $ [mm] g^{-1} [/mm] $ surjektiv.
Oder ist dies inkorrekt?
Zur Rückrichtung:
> Ich würde aber gerne noch fertig bewiesen sehen, weshalb $ X $ nun endlich > oder gleichmächtig zu $ [mm] \IN [/mm] $ ist.
Reicht es nicht zu sagen, dass eine injektive Abbildung $g: [mm] X\to\mathbb{N}$ [/mm] existiert?
Nun ja, da die Abbildung injektiv ist, gilt natürlich [mm] |X|\leq |\mathbb{N}|
[/mm]
X ist also endlich, oder gleichmächtig zu [mm] $\mathbb{N}$.
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:01 Mo 27.04.2015 | | Autor: | tobit09 |
Beweisen wollen wir also nun die korrigierte Behauptung:
Eine Menge $X$ ist genau dann abzählbar, wenn [mm] $X=\emptyset$ [/mm] gilt oder eine surjektive Abbildung [mm] $f\colon\IN\to [/mm] X$ existiert.
Dabei heißt $X$ abzählbar, wenn $X$ endlich ist oder eine bijektive Abbildung [mm] $f\colon X\to\IN$ [/mm] existiert.
> Denn benötige ich also die Fälle
>
> 1. [mm]X=\emptyset[/mm]
>
> 2. [mm]|X|=n[/mm] wobei [mm]0
>
> und 3. X ist eine unendliche Menge.
Bei welcher der beiden Richtungen bist du gerade?
Oder möchtest du in jedem der drei Fälle die Äquivalenz (beide Richtungen) überlegen?
> Der erste Fall ist trivial, weil die leere Menge eine
> endliche Menge ist und die sind abzählbar.
Wenn [mm] $X=\emptyset$ [/mm] gilt, sind daher beide Seiten der Äquivalenz-Behauptung erfüllt.
> Der zweite Fall ist aber auch trivial, weil X nun mal
> endlich ist, ich weiß gar nicht weshalb ich hier unbedingt
> eine Abbildung angeben wollte, das sollte doch unnötig
> sein.
Trivialerweise ist $X$ abzählbar, wenn $X$ (nichtleer und) endlich ist.
Aber warum ist auch die "rechte Seite" der Äquivalenz-Behauptung erfüllt?
Das halte ich schon für Beweis-bedürftig.
> Der einzige interessante Fall, ist der dritte, wenn X eine
> unendliche Menge ist.
> Und auch dies folgt unmittelbar aus der Definition.
???
> > Wenn X unendlich ist,
und abzählbar ist,
> > dann gibt es nach Definition eine
> > bijektive Funktion
> > [mm]g:X\to\mathbb{N} [/mm]. Da [mm]g[/mm] bijektiv ist, hat g eine bijektive
> > Umkehrfunktion [mm]g^{-1}:\mathbb{N}\to X [/mm]. Insbesondere ist
> > [mm]g^{-1}[/mm] surjektiv.
![[ok]](/images/smileys/ok.gif "[ok]") Damit ist im Falle $X$ unendlich die Hin-Richtung gezeigt.
> Zur Rückrichtung:
>
> > Ich würde aber gerne noch fertig bewiesen sehen, weshalb [mm]X[/mm]
> nun endlich > oder gleichmächtig zu [mm]\IN[/mm] ist.
>
> Reicht es nicht zu sagen, dass eine injektive Abbildung [mm]g: X\to\mathbb{N}[/mm]
> existiert?
> Nun ja, da die Abbildung injektiv ist, gilt natürlich
> [mm]|X|\leq |\mathbb{N}|[/mm]
Was meinst du mit [mm] $|\mathbb{N}|$?
[/mm]
Solange ihr keine allgemeinen Kardinalzahlen behandelt habt, macht die Schreibweise $|Y|$ allenfalls für endliche Mengen $Y$ Sinn.
Eure Definition von "X abzählbar" verlangt für unendliches $X$ die Existenz einer bijektiven Abbildung [mm] $g\colon X\to\IN$, [/mm] nicht nur die Existenz einer injektiven Abbildung [mm] $g\colon X\to\IN$.
[/mm]
Der exakte Nachweis, dass im Falle der Existenz einer surjektiven Abbildung [mm] $f\colon\IN\to [/mm] X$ für unendliches $X$ eine bijektive Abbildung [mm] $g\colon X\to\IN$ [/mm] existiert, erscheint mir übrigens alles andere als einfach.
Es genügt, eine bijektive Abbildung [mm] $h\colon\IN\to [/mm] X$ zu finden, denn dann leistet die Umkehrabbildung [mm] $g:=h^{-1}$ [/mm] das Gewünschte.
Die Idee hinter der Konstruktion von h:
Definiere rekursiv $h(i)$ für [mm] $i\in\IN$ [/mm] als $f(j)$ für möglichst kleines [mm] $j\in\IN$, [/mm] so dass $f(j)$ mit keinem der ("schon vergebenen") Werte [mm] $h(0),\ldots,h(i-1)$ [/mm] übereinstimmt.
|
|
|
| |
|
Hier nun mein Beweis für diese Aufgabe:
1. Fall
[mm] $X=\emptyset$
[/mm]
trivial.
2. Fall:
$|X|=m$ mit [mm] $0
[mm] "$\Rightarrow$"
[/mm]
Sei X eine (endliche) abzählbare Menge, dann existiert eine bijektive Funktion
[mm] $f:X\to\{0,\dotso, m-1\}$. [/mm] Somit eine surjektive Funktion
[mm] $g:\{0,\dotso,m-1\}\to [/mm] X$ (Gerade die Umkehrfunktion).
[mm] "$\Leftarrow$"
[/mm]
Sei [mm] $f:\mathbb{N}\to [/mm] X$ surjektiv.
Daher, für alle [mm] $n\in\mathbb{N}$ [/mm] existiert ein [mm] $x\in [/mm] X$ mit $f(n)=x$.
Da $X$ endlich mit $|X|=m$ definiere die Abbildung
[mm] $f(n)=\begin{cases} x_n, \text{falls} n
Betrachte [mm] $f_{|\{0,\dotso,m-1\}}:\mathbb{N}\to [/mm] X$.
Diese Abbildung ist bijektiv. Also existiert eine Umkehrfunktion [mm] $f^{-1}_{\{0,\dotso, m-1\}} X\to\mathbb{N}, [/mm] welche insbesondere injektiv ist. Somit ist $X$ abzählbar.
3. Fall:
X ist unendlich.
Die Hinrichtung war ja bereits korrekt. Ich probiere nun die Rückrichtung zu zeigen. Ich habe nun aber einen anderen Ansatz als den ursprünglichen gewählt, der vielleicht einfacher ist.
[mm] "$\Leftarrow$"
[/mm]
Sei [mm] $f:\mathbb{N}\to [/mm] X$ surjektiv und $X$ eine unendliche Menge.
Da $f$ surjektiv ist, gibt es eine Zuordnung so, dass für alle [mm] $x\in [/mm] X$ ein [mm] $n\in\mathbb{N}$ [/mm] existiert mit f(n)=x.
Wähle [mm] $f(n)=x_n$. [/mm] Eine leichte Rechnung zeigt, dass die so gewählte Abbildung injektiv ist.
Ich hoffe das geht so in Ordnung.
Die Abbildung in der Rückrichtung von Fall 3 drängt sich ja im Grunde auf und ist ziemlich kanonisch. Ich hoffe nur mir entgeht nun nichts...
Vielen Dank fürs drüber schauen.
mfg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:43 Di 28.04.2015 | | Autor: | tobit09 |
> Hier nun mein Beweis für diese Aufgabe:
>
> 1. Fall
>
> [mm]X=\emptyset[/mm]
>
> trivial.
(Zumindest, wenn man schon weiß, dass die leere Menge endlich und damit abzählbar ist.)
> 2. Fall:
>
> [mm]|X|=m[/mm] mit [mm]0
>
> "[mm]\Rightarrow[/mm]"
>
> Sei X eine (endliche) abzählbare Menge, dann existiert
> eine bijektive Funktion
> [mm]f:X\to\{0,\dotso, m-1\}[/mm]. Somit eine surjektive Funktion
> [mm]g:\{0,\dotso,m-1\}\to X[/mm] (Gerade die Umkehrfunktion).
Ja, aber gesucht ist bei dieser Richtung eine surjektive Funktion [mm] $h\colon\IN\to [/mm] X$, also mit Definitionsbereich [mm] $\IN$.
[/mm]
> "[mm]\Leftarrow[/mm]"
Zu zeigen ist hier die Abzählbarkeit von $X$.
Da im 2. Fall $X$ endlich ist, ist die Abzählbarkeit von $X$ hier trivial (d.h. direkt aus der Definition der Abzählbarkeit folgend).
> Sei [mm]f:\mathbb{N}\to X[/mm] surjektiv.
> Daher, für alle [mm]n\in\mathbb{N}[/mm] existiert ein [mm]x\in X[/mm] mit
> [mm]f(n)=x[/mm].
(Das hat nichts mit der Surjektivität von f zu tun, sondern gilt für jede Funktion [mm] $f\colon\IN\to [/mm] X$.)
> Da [mm]X[/mm] endlich mit [mm]|X|=m[/mm] definiere die Abbildung
>
> [mm]f(n)=\begin{cases} x_n, \text{falls} n
Du möchtest also nun eine neue Abbildung [mm] $f\colon\IN\to [/mm] X$ definieren und die alte (surjektive) Abbildung [mm] $f\colon\IN\to [/mm] X$ wieder vergessen?
Mit [mm] $x_0,\ldots,x_{m-1}$ [/mm] meinst du Elemente von X mit [mm] $X=\{x_0,\ldots,x_{m-1}\}$?
[/mm]
> Betrachte [mm]f_{|\{0,\dotso,m-1\}}:\mathbb{N}\to X[/mm].
> Diese Abbildung ist bijektiv.
[mm] $f\colon\IN\to [/mm] X$ ist sicherlich nicht bijektiv.
Aber [mm] $f|_{\{0,\ldots,m-1\}}\colon\{0,\ldots,m-1\}\to [/mm] X$ ist bijektiv.
> Also existiert eine
> Umkehrfunktion [mm]$f^{-1}_{\{0,\dotso, m-1\}} X\to\mathbb{N},[/mm]
> welche insbesondere injektiv ist.
Die Umkehrfunktion g von [mm] $f|_{\{0,\ldots,m-1\}}$ [/mm] ist eine bijektive Abbildung [mm] $g\colon X\to\{0,\ldots,m-1\}$, [/mm] nicht etwa [mm] $g\colon X\to\IN$.
[/mm]
(Eine solche bijektive Abbildung von $X$ nach [mm] $\{0,\ldots,m-1\}$ [/mm] hättest du auch gleich der Eigenschaft $|X|=m$ entnehmen können.)
Du kannst allerdings die Abbildung [mm] $g\colon X\to\{0,\ldots,m-1\}$ [/mm] auch als Abbildung [mm] $g\colon X\to\IN$ [/mm] auffassen; diese Abbildung [mm] $g\colon X\to\IN$ [/mm] ist injektiv, aber nicht surjektiv.
> Somit ist $X$
> abzählbar.
Dieser Schlussfolgerung kann ich nicht folgen.
Was hat die Existenz einer injektiven Abbildung [mm] $g\colon X\to\IN$ [/mm] mit eurer Definition der Abzählbarkeit zu tun?
Oder habt ihr schon gezeigt, dass aus der Existenz einer injektiven Abbildung [mm] $g\colon X\to\IN$ [/mm] die Abzählbarkeit von $X$ folgt?
> 3. Fall:
>
> X ist unendlich.
>
> Die Hinrichtung war ja bereits korrekt. Ich probiere nun
> die Rückrichtung zu zeigen. Ich habe nun aber einen
> anderen Ansatz als den ursprünglichen gewählt, der
> vielleicht einfacher ist.
>
> "[mm]\Leftarrow[/mm]"
>
> Sei [mm]f:\mathbb{N}\to X[/mm] surjektiv und [mm]X[/mm] eine unendliche
> Menge.
(Da wir im Fall "$X$ unendlich" sind, können wir [mm] $X=\emptyset$ [/mm] ausschließen und somit tatsächlich die Existenz einer surjektiven Abbildung [mm] $f\colon\IN\to [/mm] X$ annehmen.)
> Da [mm]f[/mm] surjektiv ist, gibt es eine Zuordnung so, dass für
> alle [mm]x\in X[/mm] ein [mm]n\in\mathbb{N}[/mm] existiert mit f(n)=x.
(Es GIBT nicht nur irgendeine solche Zuordnung, sondern "unser" gerade von dir eingeführtes $f$ hat diese Eigenschaft.)
> Wähle [mm]f(n)=x_n[/mm].
Du möchtest schon wieder unsere gerade eingeführte Abbildung $f$ vergessen und eine neue Abbildung [mm] $f\colon\IN\to [/mm] X$ definieren?
Was meinst du jetzt mit [mm] $x_n$?
[/mm]
> Eine leichte Rechnung zeigt, dass die so
> gewählte Abbildung injektiv ist.
Du behauptest, dass die neue Abbildung [mm] $f\colon\IN\to [/mm] X$ (die ich ja mangels Wissen, was du mit [mm] $x_n$ [/mm] meinst, noch nicht kenne) injektiv und surjektiv ist?
Wenn du das nachweisen könntest, wärst du fast fertig: Dann würde die Umkehrfunktion von f bezeugen, dass $X$ abzählbar ist.
Wie gesagt: Die exakte (rekursive) Definition einer bijektiven Abbildung [mm] $h\colon\IN\to [/mm] X$ (und insbesondere der Nachweis ihrer Surjektivität) erscheint mir technisch und alles andere als einfach.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:21 Di 28.04.2015 | | Autor: | Marcel |
Hallo,
> > Hier nun mein Beweis für diese Aufgabe:
> >
> > 1. Fall
> >
> > [mm]X=\emptyset[/mm]
> >
> > trivial.
> (Zumindest, wenn man schon weiß, dass die leere Menge
> endlich und damit abzählbar ist.)
>
>
> > 2. Fall:
> >
> > [mm]|X|=m[/mm] mit [mm]0
> >
> > "[mm]\Rightarrow[/mm]"
> >
> > Sei X eine (endliche) abzählbare Menge, dann existiert
> > eine bijektive Funktion
> > [mm]f:X\to\{0,\dotso, m-1\}[/mm]. Somit eine surjektive
> Funktion
> > [mm]g:\{0,\dotso,m-1\}\to X[/mm] (Gerade die Umkehrfunktion).
> Ja, aber gesucht ist bei dieser Richtung eine surjektive
> Funktion [mm]h\colon\IN\to X[/mm], also mit Definitionsbereich [mm]\IN[/mm]Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
.
strenggenommen hast Du recht, aber das Wesentliche steht dennoch schon
da: ich gebe mal den Hinweis: Man definiere $h \colon \IN \to \red{X}$ nun so, dass
$\left. h \right|_{\{0,\ldots,m-1\}}=g=f^{-1}\,.$
P.S. "Außerhalb" von $\{0,\ldots,m-1\}$ kann man $h\,$ ja *konstant machen* (allerdings
sollte man drauf achten, dass der Funktionswert zu $X\,$ gehören muss, deswegen
habe ich das oben auch rotmarkiert).
Falls jemand keine Idee hat: $g(\{0,\ldots,m-1\})=h(\{0,\ldots,m-1\}) \subseteq X$ wissen wir ja schon...
Gruß,
Marcel
|
|
|
| |
|
> Ja, aber gesucht ist bei dieser Richtung eine surjektive Funktion $ [mm] h\colon\IN\to [/mm] > X $, also mit Definitionsbereich $ [mm] \IN [/mm] $.
Dies könnte ich dann doch so lösen, wie ich es in der Rückrichtung des Falls 2 gemacht habe, nämlich das ich ab einem bestimmten Wert alle natürliche Zahlen auf ein Element der Menge abbilde.
> Du möchtest also nun eine neue Abbildung $ [mm] f\colon\IN\to [/mm] X $ definieren und > die alte (surjektive) Abbildung $ [mm] f\colon\IN\to [/mm] X $ wieder vergessen?
Nein, das hatte ich eigentlich nicht vor.
Ich wollte eine Möglichkeit angeben wie man diese surjektive Funktion konstruieren kann, von der ich weiß, dass sie existiert.
> Mit $ [mm] x_0,\ldots,x_{m-1} [/mm] $ meinst du Elemente von
> X mit $ X=\ [mm] {x_0,\ldots,x_{m-1}\} [/mm] $?
Genau. Das hätte ich nochmal explizit aufschreiben sollen...
> $ [mm] f\colon\IN\to [/mm] X $ ist sicherlich nicht bijektiv.
>
> Aber $ [mm] f|_{\{0,\ldots,m-1\}}\colon\{0,\ldots,m-1\}\to [/mm] X $ ist bijektiv.
Ich dachte ich könnte die Schreibweisen äquivalent verwenden, also das
[mm] $f_{|\{0,...,m-1\}}:\mathbb{N}\to [/mm] X$ das selbe ist wie wenn ich
[mm] $f|_{\{0,\ldots,m-1\}}\colon\{0,\ldots,m-1\}\to [/mm] X $ schreibe.
Da ich ja den Definitionsbereich [mm] $\mathbb{N}$ [/mm] auf [mm] $\{0,...,m-1\}$ [/mm] einschränke.
> Oder habt ihr schon gezeigt, dass aus der Existenz einer injektiven Abbildung > $ [mm] g\colon X\to\IN [/mm] $ die Abzählbarkeit von $ X $ folgt?
Ja, das ist bekannt. Hätte ich dazu sagen sollen.
> Du möchtest schon wieder unsere gerade eingeführte Abbildung $ f $
> vergessen und eine neue Abbildung $ [mm] f\colon\IN\to [/mm] X $ definieren?
> Was meinst du jetzt mit $ [mm] x_n [/mm] $?
Nein, auch hier wollte ich nur eine mögliche Konstruktion angeben.
Mit [mm] $x_n$ [/mm] meine ich ein Element aus [mm] $X=\{x_0,...,x_{m-1}\}$
[/mm]
> Wie gesagt: Die exakte (rekursive) Definition einer bijektiven Abbildung $
> [mm] h\colon\IN\to [/mm] X $ (und insbesondere der Nachweis ihrer Surjektivität)
> erscheint mir technisch und alles andere als einfach.
Mein Ansatz ist also zum scheitern verurteilt?
Oder wie ist dies zu verstehen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:37 Di 28.04.2015 | | Autor: | tobit09 |
> > Ja, aber gesucht ist bei dieser Richtung eine surjektive
> Funktion [mm]h\colon\IN\to > X [/mm], also mit Definitionsbereich
> [mm]\IN [/mm].
>
> Dies könnte ich dann doch so lösen, wie ich es in der
> Rückrichtung des Falls 2 gemacht habe, nämlich das ich ab
> einem bestimmten Wert alle natürliche Zahlen auf ein
> Element der Menge abbilde.
(Weil $X$ im zweiten Fall nichtleer ist, existiert auch ein Element der Menge.)
> > Du möchtest also nun eine neue Abbildung [mm]f\colon\IN\to X[/mm]
> definieren und > die alte (surjektive) Abbildung
> [mm]f\colon\IN\to X[/mm] wieder vergessen?
>
> Nein, das hatte ich eigentlich nicht vor.
> Ich wollte eine Möglichkeit angeben wie man diese
> surjektive Funktion konstruieren kann, von der ich weiß,
> dass sie existiert.
Das musst du bei dieser Richtung gar nicht tun, da wir hier ja schon diese Existenz voraussetzen.
> > [mm]f\colon\IN\to X[/mm] ist sicherlich nicht bijektiv.
> >
> > Aber [mm]f|_{\{0,\ldots,m-1\}}\colon\{0,\ldots,m-1\}\to X[/mm] ist
> bijektiv.
>
> Ich dachte ich könnte die Schreibweisen äquivalent
> verwenden, also das
>
> [mm]f_{|\{0,...,m-1\}}:\mathbb{N}\to X[/mm] das selbe ist wie wenn
> ich
>
> [mm]f|_{\{0,\ldots,m-1\}}\colon\{0,\ldots,m-1\}\to X[/mm] schreibe.
(Zumindest habe ich die Schreibweise [mm] $f_{|\{0,...,m-1\}}:\mathbb{N}\to [/mm] X$ noch nie gesehen. Sie würde meiner Meinung nach suggerieren, dass der Definitionsbereich dieser Abbildung [mm] $\IN$ [/mm] wäre.)
> > Oder habt ihr schon gezeigt, dass aus der Existenz einer
> injektiven Abbildung > [mm]g\colon X\to\IN[/mm] die Abzählbarkeit
> von [mm]X[/mm] folgt?
>
> Ja, das ist bekannt. Hätte ich dazu sagen sollen.
Alles klar. Dann darfst du das natürlich benutzen.
(Der Beweis dieses Zusammenhangs war vermutlich technisch und alles andere als einfach, oder?)
Mithilfe dieses Abzählbarkeits-Kriteriums lässt sich der gesamte Nachweis, dass im Falle der Existenz einer surjektiven Abbildung [mm] $f\colon\IN\to [/mm] X$ die Menge $X$ abzählbar ist, genau so führen, wie du es in deiner Ausgangsfrage getan hast.
![[sorry]](/images/smileys/sorry.gif "[sorry]") , dass ich nicht eher danach gefragt habe, ob ihr weitere Kriterien für Abzählbarkeit kennt.
> > Du möchtest schon wieder unsere gerade eingeführte
> Abbildung [mm]f[/mm]
> > vergessen und eine neue Abbildung [mm]f\colon\IN\to X[/mm]
> definieren?
>
> > Was meinst du jetzt mit [mm]x_n [/mm]?
>
> Nein, auch hier wollte ich nur eine mögliche Konstruktion
> angeben.
Es ist ja hier gerade unsere Voraussetzung, dass (mindestens) eine solche surjektive Abbildung existiert.
Dann können wir eine solche Abbildung f wählen.
Wie diese genau aussieht, wissen wir nicht.
f zu konstruieren, erscheint mir wenig Erfolgs-versprechend, aber das ist ja auch gar nicht nötig: Wir dürfen bei dieser Richtung ja schon voraussetzen, dass wir eine solche Abbildung gegeben haben.
> Mit [mm]x_n[/mm] meine ich ein Element aus [mm]X=\{x_0,...,x_{m-1}\}[/mm]
Wir sind gerade im Fall, dass $X$ unendlich ist.
Daher besitzt $X$ gar keine solche Darstellung.
(Wenn $X$ eine solche Darstellung besäße, wäre weiter zu erklären, was mit [mm] $x_n$ [/mm] für [mm] $n\ge [/mm] m$ gemeint wäre.)
> > Wie gesagt: Die exakte (rekursive) Definition einer
> bijektiven Abbildung $
> > [mm]h\colon\IN\to[/mm] X $ (und insbesondere der Nachweis ihrer
> Surjektivität)
> > erscheint mir technisch und alles andere als einfach.
>
> Mein Ansatz ist also zum scheitern verurteilt?
> Oder wie ist dies zu verstehen?
Dein letzter Versuch des Beweises der Rückrichtung im Falle $X$ unendlich scheint mir in der Tat nicht zum Ziel zu führen.
(Ich wollte vor allem betonen, dass es keine Schande ist, die explizite Konstruktion einer Bijektion zwischen $X$ und [mm] $\IN$ [/mm] nicht zu schaffen.)
Aber wie gesagt: Wenn ihr schon wisst, dass für die Abzählbarkeit von $X$ die Existenz einer injektiven Abbildung [mm] $g\colon X\to\IN$ [/mm] bereits hinreichend ist, kannst du für den besagten Teil so argumentieren wie in deiner Ausgangsfrage!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:26 Di 28.04.2015 | | Autor: | Marcel |
Hallo,
> > > Ja, aber gesucht ist bei dieser Richtung eine surjektive
> > Funktion [mm]h\colon\IN\to > X [/mm], also mit Definitionsbereich
> > [mm]\IN [/mm].
> >
> > Dies könnte ich dann doch so lösen, wie ich es in der
> > Rückrichtung des Falls 2 gemacht habe, nämlich das ich ab
> > einem bestimmten Wert alle natürliche Zahlen auf ein
> > Element der Menge abbilde.
>
> (Weil [mm]X[/mm] im zweiten Fall nichtleer ist, existiert auch ein
> Element der Menge.)
>
>
> > > Du möchtest also nun eine neue Abbildung [mm]f\colon\IN\to X[/mm]
> > definieren und > die alte (surjektive) Abbildung
> > [mm]f\colon\IN\to X[/mm] wieder vergessen?
> >
> > Nein, das hatte ich eigentlich nicht vor.
> > Ich wollte eine Möglichkeit angeben wie man diese
> > surjektive Funktion konstruieren kann, von der ich weiß,
> > dass sie existiert.
> Das musst du bei dieser Richtung gar nicht tun, da wir
> hier ja schon diese Existenz voraussetzen.
>
>
> > > [mm]f\colon\IN\to X[/mm] ist sicherlich nicht bijektiv.
> > >
> > > Aber [mm]f|_{\{0,\ldots,m-1\}}\colon\{0,\ldots,m-1\}\to X[/mm] ist
> > bijektiv.
> >
> > Ich dachte ich könnte die Schreibweisen äquivalent
> > verwenden, also das
> >
> > [mm]f_{|\{0,...,m-1\}}:\mathbb{N}\to X[/mm] das selbe ist wie wenn
> > ich
> >
> > [mm]f|_{\{0,\ldots,m-1\}}\colon\{0,\ldots,m-1\}\to X[/mm] schreibe.
> (Zumindest habe ich die Schreibweise
> [mm]f_{|\{0,...,m-1\}}:\mathbb{N}\to X[/mm] noch nie gesehen. Sie
> würde meiner Meinung nach suggerieren, dass der
> Definitionsbereich dieser Abbildung [mm]\IN[/mm]Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
wäre.)
da in der Notation $a \colon D \to Z$ $D\,$ der Definitionsbereich und $Z$ der Zielbereich
ist, würde ich sogar sagen, dass oben dann $f_{|\{0,...,m-1\}}$ gemäß der Notation
den Definitionsbereich $\IN$ haben muss (es ist also implizieren, nicht nur
suggerieren).
Es würde sogar etwas ganz Schlimmes zur Folge haben: Es wäre $\IN=\{0,...,m-1\}$,
d.h. die Menge der positiven ganzen Zahlen wäre endlich.
Und in der Notation $g=\left. a \right_{|M}$ für $M \subseteq D$ *unterstellt man
ja, alleine, wenn man $a\,$ sieht, zu wissen, welcher Definitionsbereich $D\,$ zu
$a\,$ gehört*.
Wir reden meist ja auch immer nur von *der Abbildung $a\,$*, und nicht von einem
Tupel $(a\,,D,\,Z)$ (wobei viele auch eher das Tupel als Abbildung definieren,
also $a=(G_a,D,Z,\ldots)$ - da muss man aber aufpassen, weil so manch' einer
wieder $a\,$ und $G_a$ *identifiziert*. Am Besten einfach an den Notationen
und Definitionen der Vorlesung orientieren.)
Jedenfalls: $\left. f \right_{|\{0,...,m-1\}} \colon \IN \to ...$ widerspricht der Tatsache, dass der Definitionsbereich
der eingeschränkten Funktion $\{0,\ldots,m-1\}$ ist, nach Definition des Symbols $a_{|M}$.
Daher würde ich sogar so weit gehen, zu sagen, dass man das gar nicht
schreiben darf!
Gruß,
Marcel
|
|
|
| |
|
> Es würde sogar etwas ganz Schlimmes zur Folge haben: Es wäre $ [mm] \IN=\{0,...,m-> 1\} [/mm] $,
> d.h. die Menge der positiven ganzen Zahlen wäre endlich.
Dann lassen wir das mal lieber bleiben. :D
|
|
|
| |
|
> , dass ich nicht eher danach gefragt habe, ob ihr weitere Kriterien für
> Abzählbarkeit kennt.
Kein Problem. Das ist eher mein Versäumnis.
Ja, der Beweis war tatsächlich sehr technisch. :)
Wir hatten mal eine Übungsaufgabe wo wir einen ähnlichen Beweis führen mussten, der mir sogar noch technischer vorkam, daher fand ich den Beweis irgendwie schön.
Ok. Um mal zusammenzufassen was wir bisher haben.
Fall 1, ist klar.
Fall 2, mit der Kenntnis, dass wir mehrere Kriterien zur Überprüfung der Abzählbarkeit haben sollte die Hinrichtung abgeharkt sein?
Die Rückrichtung folgt unmittelbar aus der Definition.
Fall 3,
für die Rückrichtung gehe ich dann so vor, dass ich weiß, dass surjektive Funktionen eine Rechtsinverse besitzen, wie ich es ursprünglich vorhatte.
Die Hinrichtung folgt hier auch aus der Definition von "abzählbar".
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:29 Di 28.04.2015 | | Autor: | Marcel |
Hallo,
> ...
> Überprüfung der Abzählbarkeit haben sollte die
> Hinrichtung abgeharkt sein?
also unsere Dozenten hatten IMMER erwähnt, dass man das Wort Hinrichtung
mit Vorsicht genießen sollte: Es könnte missverstanden werden.
(Ich habe mir angewöhnt, wenigstens Hin-Richtung zu schreiben, wenn ich
es denn schriftlich verwenden will.)
Aber dass die *Hinrichtung abgeharkt* wurde: Das finde ich nun einfach
toll von der Wortwahl her. ![[grins]](/images/smileys/grins.gif "[grins]")
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:44 Mi 29.04.2015 | | Autor: | tobit09 |
Danke für dein Verständnis!
> Ok. Um mal zusammenzufassen was wir bisher haben.
>
> Fall 1, ist klar.
>
> Fall 2, mit der Kenntnis, dass wir mehrere Kriterien zur
> Überprüfung der Abzählbarkeit haben sollte die
> Hinrichtung abgeharkt sein?
Es geht also um die Richtung, in der die Existenz einer surjektiven Abbildung [mm] $f\colon\IN\to [/mm] X$ (nicht etwa die Abzählbarkeit von $X$) zu zeigen ist.
Wie möchtest du dabei welches Abzählbarkeits-Kriterium ins Spiel bringen?
Ich würde eine (da $X$ endlich ist, existierende) Bijektion [mm] $g\colon X\to\{0,\ldots,m-1\}$ [/mm] und ein (wegen [mm] $X\not=\emptyset$ [/mm] existierendes) Element [mm] $x\in [/mm] X$ wählen und dann
[mm] $f\colon\IN\to X,\quad f(n)=\begin{cases}g^{-1}(n),&\text{ für }n\in\{0,\ldots,m-1\}\\ x,&\text{ sonst}\end{cases}$
[/mm]
betrachten.
> Die Rückrichtung folgt unmittelbar aus der Definition.
Ja, im 2. Fall ist $X$ als endliche Mengen per Definitionem abzählbar.
> Fall 3,
>
> für die Rückrichtung gehe ich dann so vor, dass ich
> weiß, dass surjektive Funktionen eine Rechtsinverse
> besitzen, wie ich es ursprünglich vorhatte.
Ja. (Hier geht dann das nunmehr zur Verfügung stehende hinreichende Abzählbarkeits-Kriterium ein.)
> Die Hinrichtung folgt hier auch aus der Definition von
> "abzählbar".
Da $X$ hier als abzählbar, aber nicht endlich, angenommen wird, existiert nach Definition der Abzählbarkeit eine Bijektion [mm] $f\colon X\to\IN$.
[/mm]
Die Umkehrfunktion [mm] $f^{-1}\colon\IN\to [/mm] X$ ist ebenfalls bijektiv und somit insbesondere surjektiv.
|
|
|
| |
|
Vielen Dank an alle beteiligten für die Hilfe.
mfg
|
|
|
|
