Potenzmengen sind abzählbar? < naiv < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:54 Mo 11.11.2013 | | Autor: | HenningD |
Hallo!
Ich bin auf ein mathematisches Problem gestoßen, welches ich alleine nicht zu lösen vermag.
Wenn man folgende Menge betrachtet:
[mm]M := \{2^{k-1} | k \in \IN \}[/mm]
also
[mm]\IN = \{1, 2, 3, ...\}[/mm]
[mm]M = \{1, 2, 4, ...\}[/mm]
Und nun davon die Potenzmenge bildet:
[mm]P(M) = \{\{\}, \{1\}, \{2\}, \{1, 2\}, \{4\}, \{1, 4\}, \{2, 4\}, \{1, 2, 4\}, ...\}[/mm]
Dann kann man jetzt ein Element m [mm] \in [/mm] M und ein Element t [mm] \in [/mm] P(M) in Relation setzen und gibt durch eine 1 an, dass m [mm] \in [/mm] t, und durch eine 0, dass m [mm] \not\in [/mm] t ist.
Diese Relation kann man nun durch eine Tabelle darstellen:
1, 2, 4, ..., m
[mm] P(M)_1: [/mm] 0, 0, 0
[mm] P(M)_2: [/mm] 1, 0, 0
[mm] P(M)_3: [/mm] 0, 1, 0
[mm] P(M)_4: [/mm] 1, 1, 0
[mm] P(M)_5: [/mm] 0, 0, 1
[mm] P(M)_6: [/mm] 1, 0, 1
[mm] P(M)_7: [/mm] 0, 1, 1
[mm] P(M)_8: [/mm] 1, 1, 1
...
t
Und man sieht nun, dass sich die Potenzmenge sehr gut durch eine binäre Zählweise abzählen lässt. Es ist auch nicht wirklich schwer, eine bijektive Abbildung von P(M) auf [mm] \IN [/mm] anzugeben: Einfach die Summe der Elemente. Und injektiv ist diese Abbildung, da die Summanden ja nur aus M sein dürfen.
Allerdings, wenn man Cantors Diagonalbeweis darauf anwendet und nur bis zur 3. Zeile schaut, passiert folgendes:
Man nimmt die Diagonale
(1,1), (2,2), (3,3) = 0, 0, 0 und negiert sie: 1, 1, 1
und weiß nun, dass man diese Spalte noch nicht aufgezählt hat, da sie weder in der ersten, noch in der zweiten noch in der dritten auftaucht. Laut Cantor ist die Potenzmenge deswegen nicht abzählbar, aber sie taucht doch in der 8. Spalte auf? Sind damit jetzt die natürlichen Zahlen nicht mehr abzählbar unendlich?
Und wenn ich P(M) abzählen kann, kann ich doch auch [mm] P(\IN) [/mm] abzählen, da eine bijektive Abbildung von M auf N existiert, oder?
Und nun der nächste Gedanke:
Wenn ich hier eine reelle Zahl angeben will, sodass andere mich verstehen können, reicht es ja nicht, wenn ich sie approximiere.
Z.b. ist folgende Darstellung nicht eindeutig:
[mm]d := 1,414213...[/mm]
Aber folgende:
[mm]d := \wurzel[2]{2}[/mm]
Auch folgende Darstellung ist nicht eindeutig:
[mm]f := 2,718281...[/mm]
Aber folgende:
[mm]f := e = \limes_{n\rightarrow\infty}(1+1/n)^n[/mm]
D.h. reelle Zahlen kann ich nicht explizit sondern immer nur durch eine Beschreibung angeben, wie ich es oben getan habe. Und diese Beschreibung wird in diesem Forum auf einem Server mit Einsen und Nullen beschrieben, die als natürliche Zahl aufgefasst werden können.
Da die natürlichen Zahlen aber abzählbar unendlich sind, müssten doch auch die reellen Zahlen abzählbar unendlich sein?
Gibt es reelle Zahlen, die sich nicht auf dem Papier beschreiben lassen, also durch keine mathematische Aussage?
Wie kann man sie denn dann nachweisen?
Was habe ich falsch gemacht?
Vielen Dank für Antworten und ich freue mich schon jetzt darauf, wie dieses Mysterium gelüftet werden kann!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:30 Mo 11.11.2013 | | Autor: | Marcel |
Hallo,
> Hallo!
>
> Ich bin auf ein mathematisches Problem gestoßen, welches
> ich alleine nicht zu lösen vermag.
>
> Wenn man folgende Menge betrachtet:
> [mm]M := \{2^{k-1} | k \in \IN \}[/mm]
> also
> [mm]\IN = \{1, 2, 3, ...\}[/mm]
> [mm]M = \{1, 2, 4, ...\}[/mm]
>
> Und nun davon die Potenzmenge bildet:
> [mm]P(M) = \{\{\}, \{1\}, \{2\}, \{1, 2\}, \{4\}, \{1, 4\}, \{2, 4\}, \{1, 2, 4\}, ...\}[/mm]
>
> Dann kann man jetzt ein Element m [mm]\in[/mm] M und ein Element t
> [mm]\in[/mm] P(M) in Relation setzen und gibt durch eine 1 an, dass
> m [mm]\in[/mm] t, und durch eine 0, dass m [mm]\not\in[/mm] t ist.
> Diese Relation kann man nun durch eine Tabelle
> darstellen:
>
> 1, 2, 4, ..., m
> [mm]P(M)_1:[/mm] 0, 0, 0
> [mm]P(M)_2:[/mm] 1, 0, 0
> [mm]P(M)_3:[/mm] 0, 1, 0
>
> [mm]P(M)_4:[/mm] 1, 1, 0
> [mm]P(M)_5:[/mm] 0, 0, 1
> [mm]P(M)_6:[/mm] 1, 0, 1
> [mm]P(M)_7:[/mm] 0, 1, 1
> [mm]P(M)_8:[/mm] 1, 1, 1
> ...
> t
>
> Und man sieht nun, dass sich die Potenzmenge sehr gut durch
> eine binäre Zählweise abzählen lässt.
da ist doch schon der erste Fehler - Du sagst "man sieht". In der Mathematik
reicht sowas eben nicht, Du müßtest Deine Behauptung beweisen. Da ich
Dir aber beweisen kann, dass es keine Surjektion einer Menge $M [mm] \not=\varnothing$ [/mm] in
ihre Potenzmenge geben kann, kannst Du hier auch schon aufhören.
Von mir aus machen wir das auch hier mal speziell, indem ich Dir zeige,
dass es keine surjektive Abbildung [mm] $\IN \to P(\IN)$ [/mm] geben kann:
Angenommen, Du hättest eine surjektive Abbildung $f [mm] \colon \IN \to P(\IN)\,.$ [/mm] Dann
betrachte die Menge
[mm] $Y:=\{n \in \IN: \;\; n \notin \underbrace{f(n)}_{\subseteq \;\IN}\} \;\in\; P(\IN)\,.$
[/mm]
Ich behaupte: Du findest mit Sicherheit kein $x [mm] \in \IN$ [/mm] mit [mm] $f(x)=Y\,.$ [/mm] Denn:
Angenommen, es wäre $x [mm] \in \IN$ [/mm] mit [mm] $Y=f(x)\,. [/mm] $Für dieses $x [mm] \in \IN$ [/mm] gibt es nur
die folgenden zwei Möglichkeiten:
(Entweder) Es ist
$x [mm] \in [/mm] Y=f(x)$
oder es ist
$x [mm] \notin Y=f(x)\,.$
[/mm]
Keiner dieser Fälle funktioniert aber (versuche mal, Dir das selbst zu
erläutern).
> Es ist auch nicht
> wirklich schwer, eine bijektive Abbildung von P(M) auf [mm]\IN[/mm]
> anzugeben:
Nein? Doch, es ist verdammt schwer, etwas anzugeben, was gar nicht
existieren kann - denn Bijektionen sind insbesondere Surjektionen!
> Einfach die Summe der Elemente. Und injektiv ist
> diese Abbildung, da die Summanden ja nur aus M sein
> dürfen.
>
> Allerdings, wenn man Cantors Diagonalbeweis darauf anwendet
> und nur bis zur 3. Zeile schaut, passiert folgendes:
> Man nimmt die Diagonale
> (1,1), (2,2), (3,3) = 0, 0, 0 und negiert sie: 1, 1, 1
> und weiß nun, dass man diese Spalte noch nicht
> aufgezählt hat, da sie weder in der ersten, noch in der
> zweiten noch in der dritten auftaucht. Laut Cantor ist die
> Potenzmenge deswegen nicht abzählbar, aber sie taucht doch
> in der 8. Spalte auf? Sind damit jetzt die natürlichen
> Zahlen nicht mehr abzählbar unendlich?
??? Jetzt verstehe ich nicht, was Du hier machst. Mit dem
![[]](/images/popup.gif) zweiten Cantorschen Diagonalargument
beweist man doch Nichtabzählbarkeit - worum geht's Dir hier? Du
betrachtest doch gar nicht [mm] $\IN$...?! [/mm]
> Und wenn ich P(M) abzählen kann, kann ich doch auch [mm]P(\IN)[/mm]
> abzählen, da eine bijektive Abbildung von M auf N
> existiert, oder?
Ja, wenn man [mm] $P(M)\,$ [/mm] abzählen könnte, dann auch [mm] $P(\IN)\,.$ [/mm] Aber weil man,
s.o., [mm] $P(\IN)$ [/mm] nicht abzählen kann (dazu habe ich Dir alles Wesentliche für
einen Beweis hingeschrieben), wird das auch mit [mm] $P(M)\,$ [/mm] nicht machbar sein:
Du kannst also [mm] $P(M)\,$ [/mm] leider nicht abzählen, ebensowenig, wie Du [mm] $P(\IN)\,$
[/mm]
abzählen kannst. Generell folgt aus dem oben Gesagten (damit meine ich,
dass es keine Surjektion einer Menge in ihre Potenzmenge geben kann -
das Gesagte gilt ja im Falle der leeren Menge offensichtlich):
Ist [mm] $A\,$ [/mm] abzählbar unendlich, so kann [mm] $P(A)\,$ [/mm] nicht abzählbar (unendlich) sein!
(M.a.W.: Dann ist [mm] $P(A)\,$ [/mm] überabzählbar... was übrigens noch nicht heißt, dass
[mm] $P(A)\,$ [/mm] automatisch gleichmächtig zu [mm] $\IR$ [/mm] sein muss!)
> Und nun der nächste Gedanke:
> Wenn ich hier eine reelle Zahl angeben will, sodass andere
> mich verstehen können,
Was? Was ist denn "eine relle Zahl, so, dass andere sie verstehen?"
> reicht es ja nicht, wenn ich sie approximiere.
Für was sowas reicht hängt davon ab, für was Du sie verwenden willst!
> Z.b. ist folgende Darstellung nicht eindeutig:
> [mm]d := 1,414213...[/mm]
Nein, denn solche "..." sind eigentlich nie klar, und damit nie eindeutig in ihrer
Bedeutung!
> Aber folgende:
> [mm]d := \wurzel[2]{2}[/mm]
Und weiter?
> Auch folgende Darstellung ist nicht eindeutig:
> [mm]f := 2,718281...[/mm]
> Aber folgende:
> [mm]f := e = \limes_{n\rightarrow\infty}(1+1/n)^n[/mm]
>
> D.h. reelle Zahlen kann ich nicht explizit sondern immer
> nur durch eine Beschreibung angeben, wie ich es oben getan
> habe. Und diese Beschreibung wird in diesem Forum auf einem
> Server mit Einsen und Nullen beschrieben, die als
> natürliche Zahl aufgefasst werden können.
Naja, dass man in "Rechnerarithmetik" stark eingeschränkt ist, soweit ich
weiß hat man ja sogar nur endlich viele Zahlen dort zur Verfügung, ist doch
aber klar. Aber da soll mal ein wissender Informatiker mehr zu sagen. 
> Da die natürlichen Zahlen aber abzählbar unendlich sind,
> müssten doch auch die reellen Zahlen abzählbar unendlich
> sein?
??? Nein, warum sollten sie?
> Gibt es reelle Zahlen, die sich nicht auf dem Papier
> beschreiben lassen, also durch keine mathematische
> Aussage?
Wie willst Du sie sonst beschreiben? Was ist denn bei Dir eine "zulässige,
aber nichtmathematische Aussage"??
> Wie kann man sie denn dann nachweisen?
Das kann man nicht beantworten - das geht bei Dir momentan so in
Richtung Religion oder Philosophie; ich verstehe jedenfalls Deine Frage
so ziemlich gar nicht!
> Was habe ich falsch gemacht?
Du behauptest "man sieht, dass ...", ohne Dir einen sauberen Beweis dafür
aufzuschreiben. Wenn Du versuchen würdest, eine Surjektion wie
gewünscht anzugeben, so wird das halt nicht gehen, denn sowas kann
es nicht geben!
> Vielen Dank für Antworten und ich freue mich schon jetzt
> darauf, wie dieses Mysterium gelüftet werden kann!
Ich glaube allerdings nicht, dass Du jetzt direkt schon viel neues daraus
gewonnen hast; das ist halt auch etwas, was man "verdauen" muss...
und ich ahne schon jetzt, dass Du das nicht akzeptieren wollen wirst.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:23 Mi 17.06.2015 | | Autor: | HenningD |
> > Gibt es reelle Zahlen, die sich nicht auf dem Papier
> > beschreiben lassen, also durch keine mathematische
> > Aussage?
> Wie willst Du sie sonst beschreiben? Was ist denn bei Dir eine "zulässige,
> aber nichtmathematische Aussage"??
Jetzt, da mir nun einige Dinge viel klarer geworden sind, kann ich abschließend zu meiner ursprünglichen Verwirrung sagen: Ja, es gibt reelle Zahlen, die sich durch keine endliche Formel beschreiben lassen. Genauer: Für jede formale Sprache S und für jede Interpretation [mm] I:S\to\mathds{R} [/mm] gibt es eine reelle Zahl x, sodass es keine Formel [mm] f\in [/mm] S gibt mit I(f) = x.
Diese reellen Zahlen heißen "unknowable numbers" ([1] und [2]) und wurden wohl noch nicht so gut erforscht. Immerhin hatte meine Verwirrung Berechtigung und vielleicht hilft mein Nachtrag ja auch anderen Verwirrten, die auf diesen Thread stoßen.
[1] http://c2.com/cgi/wiki?UnknowableNumbers
[2] http://math.stackexchange.com/questions/1145238/are-there-numbers-in-r-which-cannot-be-expressed-as-a-finite-formula-including
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:27 Di 12.11.2013 | | Autor: | HenningD |
Vielen Dank für deine Antwort!
> Da ich Dir aber beweisen kann, dass es keine Surjektion einer Menge $ M [mm] \not=\varnothing [/mm] $ in ihre Potenzmenge geben kann
Es tut mir leid, dass ich nicht erwähnt habe, dass ich den Satz von Cantor bereits kenne. Ich kann ihn auch nachvollziehen, nur verstehe ich dadurch dennoch nicht, was mein Denkfehler ist.
Außerdem gefällt mir die Menge Y nicht:
Angenommen, ich habe eine Menge M:
[mm]M := \{n \in A: n \not\in n\}[/mm]
Und eine Menge A:
[mm]A := \{x: x = x\}[/mm]
Dann stellt sich die Frage, ob M in M enthalten ist. Das führt genau so wie im Satz von Cantor zu einem Widerspruch: Wenn M [mm] \in [/mm] M, ist M [mm] \not\in [/mm] M und umgekehrt.
Warum darf ich die Menge M denn jetzt nicht so wählen, aber Y darf so (ähnlich) gewählt werden? Mit der Menge M kann ich doch auch jede Aussage zum Widerspruch führen.
Abgesehen davon: Du behauptest, es gibt keine surjektive Abbildung von M nach P(M).
Dann nenne mir eine Teilmenge von P(M), die ich nach dem von mir beschriebenen Verfahren nicht einer Nummer zuordnen kann. Und zwar eine explizite Teilmenge, nicht irgendwelche Mengen, die Mengen enthalten, die sich nicht selbst enthalten.
> Du sagst "man sieht".
Ok, hier der Beweis:
Also:
[mm]M := \{2^{k-1} | k \in \IN \}, M \subset \IN[/mm]
Die Abbildung f: M [mm] \mapsto [/mm] P(M) ist definiert wie folgt:
[mm]f(0)=\emptyset[/mm]
[mm]f(n)=f(n-g(n)) \cup \{g(n)\}[/mm]
Wobei g den nächst kleineren oder gleich großen Wert zurückgibt, der in M enthalten ist:
[mm]g: \IN \mapsto M[/mm]
[mm]g(1)=1 [/mm]
[mm]g(n)=\begin{cases} n, & \mbox{für } n \in M \\ g(n - 1), & \mbox{sonst} \end{cases}[/mm]
Beispiele zu g:
[mm]g(5)=4[/mm]
[mm]g(8)=8[/mm]
[mm]g(1780)=1024[/mm]
[mm]g(2)=2[/mm]
Beispiele zu f:
[mm]f(1)=\{1\}[/mm]
[mm]g(2)=\{2\}[/mm]
[mm]g(3)=\{1,2\}[/mm]
[mm]g(4)=\{4\}[/mm]
f terminiert zumindest immer, da für g(n) gilt: [mm]\forall n \in \IN: 0 < g(n) \le n[/mm].
Darum ist n-g(n) für alle n [mm] \in \IN [/mm] stets zwischen 0 und n-1. Daraus folgt, dass der Parameter für n immer kleiner aber nicht kleiner als 0 wird.
Außerdem enthält die Potenz-Teilmenge stets nur Elemente auf M, da g auf M abbildet.
Es gilt zu zeigen: [mm]\forall m_1 \subset P(M): \forall m_2 \subset P(M): m1 \not= m2 \gdw \sum m1 \not= \sum m2 [/mm]
Beweis durch Widerspruch: Die Summen der Elemente von zwei unterschiedlichen Teilmengen m1, m2 von P(M) sei gleich.
Nun wird eine symmetrische Differenz gebildet: Da bei dieser Differenz aus beiden Mengen nur gleiche Elemente entfernt werden, sind die Summen von m1 und m2 danach immer noch gleich. Entweder m1 oder m2 enthält nun ein größeres Element.
Allerdings ist jedes Element aus M größer als die Summe aller Elemente aus M, die kleiner sind, weswegen die Summe von m1 und m2 nicht gleich sein kann - Widerspruch! [mm] \Box
[/mm]
Es gilt zu zeigen: Jedes Element m aus M ist größer als die Summe aller Elemente aus M, die kleiner als m sind.
Beweis durch Induktion:
I.A.: Für m=1 gilt: Kein Element ist kleiner, also ist die Summe der Elemente aus M, die kleiner sind = 0. Da 1 > 0 ist, stimmt diese Behauptung.
I.V.: Für ein m gilt: m ist größer als die Summe aller Elemente aus M, die kleiner sind als m.
I.S.: Wenn m ein Element aus M ist, ist das nächste Element n aus M, genau doppelt so groß wie m. Da m größer ist als die Summe der kleineren Elemente aus M, ist m plus diese Summe kleiner als 2 * m. Da n = 2 * m, ist n größer als die Summe von m und den Elementen, die kleiner als m sind. n ist also größer als die Summe von allen Elementen aus M, die kleiner als n sind. [mm] \Box
[/mm]
Die Summe der Elemente einer Teilmenge von P(M) ist in P(M) also eindeutig, damit ist f schonmal injektiv.
f(n) konstruiert genau eine Teilmenge von M, deren Summe gleich n ist. Von n wird nur der Wert abgezogen, der der Menge hinzugefügt wird. f terminiert nur, wenn n = 0. Außerdem werden der Menge nur Elemente von M hinzugefügt. Da ich bereits gezeigt habe, dass f terminiert, kommt f immer zu einem Ergebnis.
Zu zeigen gilt: f ist surjektiv.
Beweis durch Widerspruch: Es gibt ein Element m [mm] \in [/mm] P(M), welches nicht getroffen wird.
f konstruiert zu jedem n [mm] \in \IN [/mm] eine Teilmenge von P(M), sodass die Summe ihrer Elemente gerade n entspricht. Da m eine eindeutige Summe haben muss, und jede Summe eine natürliche Zahl ist, kann m nicht existieren. Widerspruch! [mm] \Box
[/mm]
Damit ist f bijektiv.
Ein paar Fehler stecken auch noch drin, 0 ist z.B. keine nat. Zahl. Aber das sind Index-Verschiebungen, die definitiv lösbar sind. Oder statt g(n) müsste es g(n+1) heißen. Das ändert aber nichts. Grobe Fehler kann ich aber nicht erkennen.
Und LaTeX mag ich noch nicht besonders, handschriftliche hätte gerade der Induktionsbeweis noch viel schöner ausgesehen.
> beweist man doch Nichtabzählbarkeit - worum geht's Dir hier?
Hmm, ich glaube das kann man erst dann verstehen, wenn man versteht, was ich mit "Man sieht" meine. Ich versuche diesen Gedanken nochmal zu überdenken, bzw. besser darzustellen.
> Was? Was ist denn "eine relle Zahl, so, dass andere sie verstehen?"
Wenn wir über ein Element reden wollen, ist die erste Voraussetzung, dass wir über das selbe Element reden. Damit wir über das selbe Element reden können, muss derjenige, der es erwähnt, dieses Element sehr präzise angeben.
> Und weiter?
Das waren Beispiele für das danachfolgende "D.h. reelle Zahlen kann ich nicht explizit..."
> Nein, denn solche "..." sind eigentlich nie klar, und damit nie eindeutig in ihrer Bedeutung!
Das habe ich doch gesagt?
> Wie willst Du sie sonst beschreiben?
Genau darum geht es mir. Darf ich also der Rückfrage entnehmen, dass es keine reelle Zahl gibt, die ich nicht eindeutig auf Papier beschreiben kann?
Nun kann ich jedes endliche Papier digitalisieren (im einfachsten Fall kann ich es abfotografieren, ich kann es aber auch in ein LaTeX-Dokument schreiben).
Das Foto f [mm] \in [/mm] F wird durch eine Speicherstruktur beschrieben.
Diese Speicherstruktur kann als k-Tupel ausgedrückt werden:
[mm]F := \{0,1\}^k[/mm]
k gibt also die Größe des Fotos an, also die Anzahl der verwendeten Bits. Da das Papier endlich ist, ist auch die Größe des Fotos endlich, deswegen ist k ebenfalls endlich.
Außerdem ist [mm]F \subseteq \IN^k[/mm].
Laut diesem hier lässt sich f eindeutig einem n [mm] \in \IN [/mm] zuordnen.
Da [mm] \IN [/mm] abzählbar ist, ist es auch die Menge aller Fotos F.
Da du meintest, dass es keine reelle Zahl gibt, die nicht auf Papier geschrieben werden kann (und zwar ohne die Pünktchen "..."), aber die Menge der Fotos vom Papier abzählbar ist, sind dann doch auch die Menge der Zahlen abzählbar, die du auf dieses Papier schreiben kannst. Also auch die reellen Zahlen.
Es sei denn, es gibt eine reelle Zahl, die nicht auf endlichem Papier niedergeschrieben werden kann.
Das führt aber zu einem Problem: Mathematiker können sich über diese Zahl nicht unterhalten, denn sie wüssten nie, ob sie die selbe Zahl meinen.
Wüssten sie nämlich nach endlich viel Papier (oder nach einem endlichen Gespräch), ob sie die selbe Zahl meinen, könnte diese Zahl (oder die Beschreibung dieser Zahl, mithilfe der sie sich letztendlich geeinigt haben) ebenfalls auf endlich viel Papier niedergeschrieben werden.
> und ich ahne schon jetzt, dass Du das nicht akzeptieren wollen wirst.
da liegst du leider vollkommen richtig ;)
Mir fehlt momentan leider noch das Handwerkzeugs, mein Problem vernünftig zu formalisieren, dass ich von anderen verstanden werde...
Grüße,
Henning
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:39 Di 12.11.2013 | | Autor: | hippias |
...
>
> Es gilt zu zeigen: [mm]\forall m_1 \subset P(M): \forall m_2 \subset P(M): m1 \not= m2 \gdw \sum m1 \not= \sum m2[/mm]
>
> Beweis durch Widerspruch: Die Summen der Elemente von zwei
Diese Funktion ist nicht wohldefiniert: Du betrachtest nur endliche Teilmengen von $M$, aber es gibt doch auch unendliche. Fuer diese divergiert die Summe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:05 Di 12.11.2013 | | Autor: | felixf |
Moin,
> ...
> >
> > Es gilt zu zeigen: [mm]\forall m_1 \subset P(M): \forall m_2 \subset P(M): m1 \not= m2 \gdw \sum m1 \not= \sum m2[/mm]
>
> >
> > Beweis durch Widerspruch: Die Summen der Elemente von zwei
> Diese Funktion ist nicht wohldefiniert: Du betrachtest nur
> endliche Teilmengen von [mm]M[/mm], aber es gibt doch auch
> unendliche. Fuer diese divergiert die Summe.
und um etwas das zu ergaenzen:
Die Menge der endlichen Teilmengen von [mm] $\IN$ [/mm] ist durchaus abzaehlbar. (Und das kann man mit der Binaerentwicklung beweisen.)
Nicht abzaehlbar ist die Menge aller Teilmengen von [mm] $\IN$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:22 Di 12.11.2013 | | Autor: | Gonozal_IX |
Hiho,
auch wenn die Antwort auf die Frage schon gegeben wurde, ist die Begründung doch meiner Meinung nach nicht korrekt.
Es gilt ja: [mm] $\summe_{m\in M} [/mm] m < [mm] \infty$ [/mm] wegen der Geometrischen Reihe und damit insbesondere für [mm] $M_1 \in \mathcal{P}(M)$ [/mm] ebenso [mm] $\summe_{m\in M_1} [/mm] m < [mm] \infty$
[/mm]
edit: ist natürlich Blödsinn und würde nur stimmen, falls da noch ein Minus im Exponenten auftauchen würde
Gruß,
Gono.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:34 Di 12.11.2013 | | Autor: | Marcel |
Hallo,
> Vielen Dank für deine Antwort!
>
> > Da ich Dir aber beweisen kann, dass es keine Surjektion
> einer Menge [mm]M \not=\varnothing[/mm] in ihre Potenzmenge geben
> kann
>
> Es tut mir leid, dass ich nicht erwähnt habe, dass ich den
> Satz von Cantor bereits kenne. Ich kann ihn auch
> nachvollziehen, nur verstehe ich dadurch dennoch nicht, was
> mein Denkfehler ist.
>
> Außerdem gefällt mir die Menge Y nicht:
> Angenommen, ich habe eine Menge M:
> [mm]M := \{n \in A: n \not\in n\}[/mm]
> Und eine Menge A:
> [mm]A := \{x: x = x\}[/mm]
> Dann stellt sich die Frage, ob M in M
> enthalten
Du meinst als Element, oder? Also die Frage lautet
$M [mm] \in [/mm] M$?
> ist. Das führt genau so wie im Satz von Cantor
> zu einem Widerspruch: Wenn M [mm]\in[/mm] M, ist M [mm]\not\in[/mm] M und
> umgekehrt.
Nein - hier kommst Du eher zu einem Problem, durch das man sagt, dass
es in der klassischen Mengenlehre "Probleme" gibt (es kann nicht die Menge
aller Mengen geben usw.). Dann kommt Zermel-Fränkel oder so... (Du
machst oben sowas wie den Barbier, der alle rasiert, die sich nicht selbst
rasieren.) Aber da frage besser jemanden, der sich besser auskennt, so
direkt fällt mir Tobi ein, und ich meine, auch Felix kennt sich da aus...
> Warum darf ich die Menge M denn jetzt nicht so wählen,
> aber Y darf so (ähnlich) gewählt werden?
Wie gesagt: Das sind Probleme der klassischen Mengenlehre.
> Mit der Menge M
> kann ich doch auch jede Aussage zum Widerspruch führen.
>
> Abgesehen davon: Du behauptest, es gibt keine surjektive
> Abbildung von M nach P(M).
> Dann nenne mir eine Teilmenge von P(M), die ich nach dem
> von mir beschriebenen Verfahren nicht einer Nummer zuordnen
> kann.
Habe ich: Betrachte [mm] $Y:=\{m \in M:\;\; m \notin f(M)\}\,,$ [/mm] unter der Annahme, dass
$f [mm] \colon [/mm] M [mm] \to [/mm] P(M)$ surjektiv sei. Das ist per Definitionem automatisch eine
Teilmenge von [mm] $M\,,$ [/mm] hier gibt's keine Probleme, es sei denn, Deine Problematik
beginnt schon damit, dass es für jede Menge ihre Potenzmenge gibt - hier
steht definitiv eine Menge [mm] $Y\,$ [/mm] mit $Y [mm] \in P(M)\,.$ [/mm] Da kannst Du drehen und
wenden, soviel Du willst. Sobald ich für eine Menge [mm] $X\,$ [/mm] schreibe:
Sei
[mm] $U:=\{x \in X: x\text{ hat irgendeine tolle Eigenschaft} \}\,,$
[/mm]
folgt für jedes $x [mm] \in [/mm] U$ auch $x [mm] \in [/mm] X$ und damit $U [mm] \subseteq X\,,$ [/mm] also $U [mm] \in P(X)\,.$ [/mm]
> Und zwar eine explizite Teilmenge, nicht irgendwelche
> Mengen, die Mengen enthalten, die sich nicht selbst
> enthalten.
Wenn Du $f [mm] \colon [/mm] M [mm] \to [/mm] P(M)$ hast, dann folgt
$f(x) [mm] \in [/mm] P(M)$ für alle $x [mm] \in M\,.$
[/mm]
Also ist $f(x) [mm] \subseteq M\,.$ [/mm] Und natürlich kann ich prüfen, ob nun irgendein
Element [mm] $y\,$ [/mm] erfüllt, ob $y [mm] \in [/mm] f(x)$ gilt oder ob $y [mm] \notin [/mm] f(x)$ gilt. Erst recht,
wenn $y [mm] \in [/mm] M$ ist, denn dann folgt aus $y [mm] \notin [/mm] f(x)$ sofort $y [mm] \in [/mm] M [mm] \setminus f(x)\,.$
[/mm]
Insbesondere kann ich $y=x [mm] \in [/mm] M$ betrachten! Ob Dir das gefällt, interessiert
dabei niemanden, das ist genauso uninteressant, wie wenn Du sagst,
dass Dir das Auswahlaxiom nicht gefällt, aber Dir jemand sagt, dass man
mit dem Auswahlaxiom etwas beweisen kann, was ohne so vielleicht nicht
geht. Was ändert ein "Missfallen" daran, dass der Beweis (sofern er denn
richtig ist) mit dem Auswahlaxiom dennoch richtig ist???
Ebensogut kannst Du sagen, dass Dir die Darstellung der rationalen
Zahlen als
[mm] $\{p/q:\;\; p \in \IZ \wedge q \in \IN\}$
[/mm]
nicht gefällt. Mit "Gefallen" ist hier nichts getan - wenn es Dir nicht gefällt,
musst Du etwas anderes (gleichwertiges) finden, was Dir vielleicht gefällt.
So gefällt mir das Auswahlaxiom sehr gut, aber das Zornsche Lemme finde
ich "hammerhart" vom Inhalt. Andere finden das Zornsche Lemma toll,
aber denen gefällt das Auswahlaxiom nicht. Und dennoch arbeiten wir
alle "gleichwertig".
> > Du sagst "man sieht".
>
> Ok, hier der Beweis:
>
> Also:
> [mm]M := \{2^{k-1} | k \in \IN \}, M \subset \IN[/mm]
>
> Die Abbildung f: M [mm]\mapsto[/mm] P(M) ist definiert wie folgt:
> [mm]f(0)=\emptyset[/mm]
> [mm]f(n)=f(n-g(n)) \cup \{g(n)\}[/mm]
>
> Wobei g den nächst kleineren oder gleich großen Wert
> zurückgibt, der in M enthalten ist:
> [mm]g: \IN \mapsto M[/mm]
> [mm]g(1)=1[/mm]
> [mm]g(n)=\begin{cases} n, & \mbox{für } n \in M \\ g(n - 1), & \mbox{sonst} \end{cases}[/mm]
>
> Beispiele zu g:
> [mm]g(5)=4[/mm]
> [mm]g(8)=8[/mm]
> [mm]g(1780)=1024[/mm]
> [mm]g(2)=2[/mm]
Auf den Rest wurde ja schon eingegangen, glaube ich, wenn ich die
Mitteilungen richtig überblicke...
P.S. Meintest Du oben
[mm] $A=\{x: \; x \red{\;\in\;}x\}$?
[/mm]
Übrigens wäre bei Dir stets $M [mm] \subseteq A\,,$ [/mm] also $M [mm] \in [/mm] P(A)$...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:57 Di 12.11.2013 | | Autor: | HenningD |
Hallo!
Vielen Dank für eure zahlreichen Antworten!
Jetzt macht es Sinn.
Zum Thema "gefallen": Ich habe nicht gesagt, dass ich die Richtigkeit von Cantors Satz bezweifele. Ich habe nur nicht verstanden, warum man es so machen kann, und ich habe mein Problem nicht verstanden. Jetzt ist es aber klar ;)
Als Programmierer habe ich mich bisher nur mit endlichen Datenstrukturen beschäftigt, bin also nicht auf die Idee gekommen, dass es auch unendliche Mengen in Potenzmengen von unendlich abzählbaren Mengen geben kann. Ich hatte nur den Blick auf die unendlich abzählbaren Teilmengen der Potenzmenge.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:09 Di 12.11.2013 | | Autor: | Marcel |
Hallo Henning,
> Hallo!
>
> Vielen Dank für eure zahlreichen Antworten!
> Jetzt macht es Sinn.
>
> Zum Thema "gefallen": Ich habe nicht gesagt, dass ich die
> Richtigkeit von Cantors Satz bezweifele. Ich habe nur nicht
> verstanden, warum man es so machen kann, und ich habe mein
> Problem nicht verstanden. Jetzt ist es aber klar ;)
das ist gut.  Mir ging's auch nicht drum, Dir da was Böses zu wollen, sondern
es ging mir drum, dass man mit "das gefällt mir" oder "das gefällt mir aber
nicht" in der Mathematik nicht wirklich einen Blumentopf gewinnen kann.
Ich habe ja nichts gegen Zweifel - und mir war das, als ich das erste mal
diesen Beweis, dass es keine Surjektion einer Menge in ihre Potenzmenge
geben kann, ähnlich unklar, warum man eigentlich da so eine komische
Menge einfach so definieren darf. Wenn man es sich aber "schrittweise"
anguckt, dann wird das klar (mir wurde es so jedenfalls klar, denn wenn
ich ein Universum [mm] $U\,$ [/mm] habe und eine Teilmenge $T [mm] \subseteq U\,,$ [/mm] dann habe ich
generell kein Problem damit, wenn jemand sagt: Für $u [mm] \in [/mm] U$ gilt entweder $u [mm] \in [/mm] T$
oder halt $u [mm] \notin [/mm] T$ (letzteres ist dann gleichwertig mit $u [mm] \in [/mm] U [mm] \setminus [/mm] T$)).
Während die Frage, ob eine Menge in sich selbst als Element enthalten ist,
für mich doch schon wieder "komisch" klingt...
> Als Programmierer habe ich mich bisher nur mit endlichen
> Datenstrukturen beschäftigt, bin also nicht auf die Idee
> gekommen, dass es auch unendliche Mengen in Potenzmengen
> von unendlich abzählbaren Mengen geben kann. Ich hatte nur
> den Blick auf die unendlich abzählbaren Teilmengen der
> Potenzmenge.
Ich finde es gut, dass Dir solche Fragen hier in den Sinn kommen. Viele
haben vielleicht ähnliche Fragen, aber nehmen es einfach hin, ohne sich
je weiter damit zu beschäftigen. Dabei hat jede solcher Fragen ihre
Berechtigung und kann durchaus auch mal "eine treibende Kraft" entwickeln;
nicht umsonst hat man sich ja über die naive Mengenlehre viele viele
Gedanken gemacht, ob man sie nicht stark überarbeiten muss...
Gruß,
Marcel
|
|
|
| |
|
Zunächst zu deiner Bijektion:
Du hast recht, wenn du sagts, dass man jede zahl aus [mm] \IN [/mm] auf P(M) eindeutig abbilden kann, z.B. 5 =1+4 auf { [mm] 2^1,2^4 [/mm] }.
Umgekehrt schlägst du vor, die Menge auf die Summe abzubilden (Umkehrabbildung), und das sieht gut aus, so lange du nur endliche Mengen aus P(M) betrachtest. Worauf bildest du aber {1,4,16,...} ab (nur ungerade Zweierpotenzen) im Gegensatz zu {2,8,32,...} (nur gerade Zweierpotenzen? Bitte zwei verschiedene sinnvolle Werte angeben!
Zur Diagonalisierung. Du machst folgenden Fehler:
Du sagst, dass für die Diagonale bis (3,3) der Wert 1,1,1 entsteht, der dann in der 8. Spalte auftaucht.
Das ist so, als wenn du bei den reellen Zahlen aufschreibst:
0,123
0,357
0,338
0,269
Nun nimmst du die Diagonale der ersten drei Zahlen: 0,158, zähltst zu jeder Ziffer 1 hinzu, gibt 0,269, und das findest du nun in der 4. Zeile, was ja gar nicht sein dürfte.
So funktioniert aber der Beweis nicht: Du must die 4. Zeile auch noch bis mindestens zur Diagonalen verlängern, also 0,2060 nehmen. Nun heißt die Diagonale 0,1580, du zählst 1 ziffernweise hinzu, macht 0,2691 [mm] \ne [/mm] 0,2690.
Für deine 0-1-Darstellung bedeutet das, daß deine 8. Zeile eben nicht 1,1,1 heißt, sondern 1,1,1,0,0,0,0,0,0,...
und auch die anderen Zeilen ab 4 sind mit 0-en aufzufüllen.
Dann aber heißt die negierte Diagonale nicht 1,1,1, sondern 1,1,1,1,1,1,1,1,1,1,1,1,1,1... und stimmt nicht mehr mit der 8. Zeile überein.
|
|
|
|
