Menge der Teilmengen abzählbar < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:11 Fr 10.06.2011 | | Autor: | Sup |
| Aufgabe | | Zeigen sie, dass die Menge der endlichen Teilmengen von [mm] \IN [/mm] abzählbar ist. |
Hi,
also ich komm mit den ganzen Begrifffen abzählbar unendlich, endlich, höchstens abzählbar, überabzählbar nicht ganz klar bzw. durcheinander.
Ich schreib mal hin wie ich sie verstanden habe.
abzählbar: die Menge ist Gleichmächtig zu [mm] \IN. [/mm] N ist zwar unendlich aber ich kann ja theoretisch bis unendlich (1, 2, 3, ....) zählen. Ist "abzählbar unendlich" das Gleiche?
endlich: Man kann der Menge eine konkrete Mächtigkeit zuweisen. Die Menge ist dann aber auch abzählbar nur nicht abzählbar unendlich?!
höchstens abzählbar: Da steht im Skirpt: "Eine Menge A heißt höchstens abzählbar (unendlich), falls A endlich oder abzählbar unendlich ist."
Versteh aber nicht wozu man diese Definition überhaupt braucht.
überabzählbar: wenn die Menge unednlich ist. Also z.B. [mm] \IR, [/mm] weil ja zwischen 0 und 1 schon unendliuch Elemente liegen (1,00...1, ..., 1,01, ..., 1,1 usw.)
So jetzt zur Aufgabe:
Ich kann [mm] \IN [/mm] schreiben als [mm] \IN:= A_1 \cup A_2 \cup [/mm] ... [mm] \cup A_n
[/mm]
wobei [mm] A_n:= [/mm] { [mm] A_n \subseteq \IN [/mm] : # [mm] A_n=n [/mm] , [mm] n\in \IN [/mm] } ist.
Oder muss die Menge { [mm] A_i \subseteq \IN [/mm] : # [mm] A_i=i [/mm] , i [mm] \in \IN [/mm] }, weil ich das "n" schon in der Vereinigung verwendet habe?
[mm] \IN:= A_1 \cup A_2 \cup [/mm] ... [mm] \cup A_n [/mm] sind abzählbar viele Teilmengen und jede dieser Teilmengen ist abzählbar, denn [mm] A_1:= [/mm] {1} [mm] \cup [/mm] {2} [mm] \cup [/mm] ... [mm] \cup [/mm] {n}.
Endlich sind aber die Teilmengen von [mm] A_n, [/mm] oder?
Insgesamt ist dann [mm] \IN=\bigcup_{i=1}^{n}A_i
[/mm]
Jetzt hatten wir in der Vorlesung volgenden Satz:
Ist A = [mm] \bigcup_{k \in \IN}^{} A_k [/mm] abzählbare Vereinigung von höchstens abzählbar unendlichen Mengen [mm] A_k [/mm] (k [mm] \in \IN), [/mm] so ist A höchstens abzählbar unendlich.
Da "höchstens abzählbar" ja auch die Eigenschaft "abzählbar" beinhaltet, wäre der Beweis mit diesem Satz erbracht.
Und nur damit ich das jetzt nochmal kapiert habe.
"die Menge der Endlichen Teilmengen von [mm] \IN"
[/mm]
1. Die einzelnen Teilmengen sind endlich
2. Die Menge der i-elementigen Teilmengen sind abzählbar unendlich
3. Die Menge aller Teilmenge sind ebendfalls abzählbar unendlich.
|
|
| |
|
> Zeigen sie, dass die Menge der endlichen Teilmengen von [mm]\IN[/mm]
> abzählbar ist.
> Hi,
>
> also ich komm mit den ganzen Begriffen abzählbar
> unendlich, endlich, höchstens abzählbar, überabzählbar
> nicht ganz klar bzw. durcheinander.
>
> Ich schreib mal hin wie ich sie verstanden habe.
>
> abzählbar: die Menge ist Gleichmächtig zu [mm]\IN.[/mm] N ist zwar
> unendlich aber ich kann ja theoretisch bis unendlich (1, 2,
> 3, ....) zählen. Ist "abzählbar unendlich" das Gleiche?
Ich denke, dass da die begrifflichen Probleme beginnen.
Wirklich zählen können wir ja nur die Elemente
(relativ kleiner) endlicher Mengen. Die Gleichmächtigkeit
einer Menge mit [mm] \IN [/mm] können wir nur durch eine bijektive
Zuordnung etablieren. Eine zu [mm] \IN [/mm] gleichmächtige Menge
nennt man "abzählbar unendlich". Nur aus Bequemlich-
keitsgründen sagt oder schreibt man dafür oft nur
"abzählbar" - das "unendlich" dabei sollte man sich dazu
denken.
> endlich: Man kann der Menge eine konkrete Mächtigkeit
> zuweisen. Die Menge ist dann aber auch abzählbar nur nicht
> abzählbar unendlich?!
Solche Mengen nennt man einfach endlich, insbesondere
weil "abzählbar" eben als Abkürzung für "abzählbar unendlich"
verwendet wird.
> höchstens abzählbar: Da steht im Skirpt: "Eine Menge A
> heißt höchstens abzählbar (unendlich), falls A endlich
> oder abzählbar unendlich ist."
> Versteh aber nicht wozu man diese Definition überhaupt
> braucht.
Hat man eine Kollektion von Mengen, von denen einige
endlich und einige andere abzählbar (unendlich) sind,
so sind alle "höchstens abzählbar", eben endlich oder
abzählbar unendlich.
> überabzählbar: wenn die Menge unendlich ist. ![[notok]](/images/smileys/notok.gif "[notok]")
Falsch.
[mm] \IN [/mm] ist ja auch schon eine unendliche Menge !
>Also z.B.
> [mm]\IR,[/mm] weil ja zwischen 0 und 1 schon unendliuch Elemente
> liegen (1,00...1, ..., 1,01, ..., 1,1 usw.)
[mm] \IR [/mm] ist überabzählbar, aber nicht aus diesem Grund.
Zum Vergleich: Zwischen 0 und 1 liegen auch schon
unendlich viele rationale Zahlen, aber trotzdem ist
die Menge [mm] \IQ [/mm] aller rationalen Zahlen abzählbar !
[mm] \IR [/mm] ist überabzählbar, weil es keine injektive Abbildung
[mm] \IR\to\IN [/mm] gibt.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:29 Fr 10.06.2011 | | Autor: | felixf |
Moin Al!
> > endlich: Man kann der Menge eine konkrete Mächtigkeit
> > zuweisen. Die Menge ist dann aber auch abzählbar nur nicht
> > abzählbar unendlich?!
>
> Solche Mengen nennt man einfach endlich, insbesondere
> weil "abzählbar" eben als Abkürzung für "abzählbar
> unendlich"
> verwendet wird.
Die Verwendung von "abzaehlbar" ist nicht ganz eindeutig: manche bezeichnen mit "abzaehlbar" auch das, was andere unter "hoechstens abzaehlbar" verstehen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:40 Fr 10.06.2011 | | Autor: | Sup |
> > Zeigen sie, dass die Menge der endlichen Teilmengen von [mm]\IN[/mm]
> > abzählbar ist.
> > Hi,
> >
> > also ich komm mit den ganzen Begriffen abzählbar
> > unendlich, endlich, höchstens abzählbar, überabzählbar
> > nicht ganz klar bzw. durcheinander.
> >
> > Ich schreib mal hin wie ich sie verstanden habe.
> >
> > abzählbar: die Menge ist Gleichmächtig zu [mm]\IN.[/mm] N ist zwar
> > unendlich aber ich kann ja theoretisch bis unendlich (1, 2,
> > 3, ....) zählen. Ist "abzählbar unendlich" das Gleiche?
>
> Ich denke, dass da die begrifflichen Probleme beginnen.
> Wirklich zählen können wir ja nur die Elemente
> (relativ kleiner) endlicher Mengen. Die Gleichmächtigkeit
> einer Menge mit [mm]\IN[/mm] können wir nur durch eine bijektive
> Zuordnung etablieren. Eine zu [mm]\IN[/mm] gleichmächtige Menge
> nennt man "abzählbar unendlich". Nur aus Bequemlich-
> keitsgründen sagt oder schreibt man dafür oft nur
> "abzählbar" - das "unendlich" dabei sollte man sich dazu
> denken.
>
> > endlich: Man kann der Menge eine konkrete Mächtigkeit
> > zuweisen. Die Menge ist dann aber auch abzählbar nur nicht
> > abzählbar unendlich?!
>
> Solche Mengen nennt man einfach endlich, insbesondere
> weil "abzählbar" eben als Abkürzung für "abzählbar
> unendlich"
> verwendet wird.
Bei Wikipedia steht aber z.B.eine Menge Geist abzählbar, wenn sie abzählbar unendlich oder endlich ist. Also sind endliche Mengen auch abzählbar.
>
> > höchstens abzählbar: Da steht im Skirpt: "Eine Menge A
> > heißt höchstens abzählbar (unendlich), falls A endlich
> > oder abzählbar unendlich ist."
> > Versteh aber nicht wozu man diese Definition überhaupt
> > braucht.
>
> Hat man eine Kollektion von Mengen, von denen einige
> endlich und einige andere abzählbar (unendlich) sind,
> so sind alle "höchstens abzählbar", eben endlich oder
> abzählbar unendlich.
>
> > überabzählbar: wenn die Menge unendlich ist.
>
> Falsch.
> [mm]\IN[/mm] ist ja auch schon eine unendliche Menge !
>
> >Also z.B.
> > [mm]\IR,[/mm] weil ja zwischen 0 und 1 schon unendliuch Elemente
> > liegen (1,00...1, ..., 1,01, ..., 1,1 usw.)
>
> [mm]\IR[/mm] ist überabzählbar, aber nicht aus diesem Grund.
> Zum Vergleich: Zwischen 0 und 1 liegen auch schon
> unendlich viele rationale Zahlen, aber trotzdem ist
> die Menge [mm]\IQ[/mm] aller rationalen Zahlen abzählbar !
> [mm]\IR[/mm] ist überabzählbar, weil es keine injektive
> Abbildung
> [mm]\IR\to\IN[/mm] gibt
So ganz habe ich die Überzählbarkeit nicht nicht verstanden.
Ich habe jetzt die Def. gefunden: Eine Menge heißt überabzählbar, wenn ihr Mächtigkeit Größe als die von [mm] \IN [/mm] ist.
Diese ist ja aber unendlich, d.h. die Mächtigkeit der überabzählbaren Menge müsste größer als unendlich sein!?
Aber warum muss die Abb. injektiv sein?
Gibt es überhaupt eine Abb. die von [mm] \IR [/mm] nach [mm] \IN [/mm] abbildet?
Injektiv würde heißen jedes n aus [mm] \IN [/mm] hat höchstens ein r aus [mm] \IR. [/mm] Das würde doch (sollte überhaupt so eine Abb. existieren) gelten den die natürlichen Zahlen sind in den reellen enthalten.
Aber wahrscheinlich bin ich wieder auf dem Holzweg.
Wäre nett wenn noch wer meinen Beweis durchsehen kann
|
|
|
| |
|
> Bei Wikipedia steht aber z.B. eine Menge G ist abzählbar,
> wenn sie abzählbar unendlich oder endlich ist. Also sind
> endliche Mengen auch abzählbar.
Bei Wikipedia wird auch auf die uneinheitliche Begrifflichkeit
hingewiesen:
"Die Verwendung des Begriffes abzählbar ist nicht einheitlich.
Er kann je nach Definition sowohl abzählbar unendlich als
auch höchstens abzählbar bedeuten."
> > > überabzählbar: wenn die Menge unendlich ist.
> >
> > Falsch.
> > [mm]\IN[/mm] ist ja auch schon eine unendliche Menge !
> >
> > >Also z.B.
> > > [mm]\IR,[/mm] weil ja zwischen 0 und 1 schon unendliuch Elemente
> > > liegen (1,00...1, ..., 1,01, ..., 1,1 usw.)
> >
> > [mm]\IR[/mm] ist überabzählbar, aber nicht aus diesem Grund.
> > Zum Vergleich: Zwischen 0 und 1 liegen auch schon
> > unendlich viele rationale Zahlen, aber trotzdem ist
> > die Menge [mm]\IQ[/mm] aller rationalen Zahlen abzählbar !
> > [mm]\IR[/mm] ist überabzählbar, weil es keine injektive
> > Abbildung
> > [mm]\IR\to\IN[/mm] gibt
> So ganz habe ich die Überzählbarkeit nicht nicht
> verstanden.
> Ich habe jetzt die Def. gefunden: Eine Menge heißt
> überabzählbar, wenn ihr Mächtigkeit Größe als die von
> [mm]\IN[/mm] ist.
> Diese ist ja aber unendlich, d.h. die Mächtigkeit der
> überabzählbaren Menge müsste größer als unendlich
> sein!?
Es war (vor über 100 Jahren) wirklich eine überraschende
Erkenntnis, dass es eben nicht nur ein "unendlich" gibt,
sondern eine (unendliche !) Hierarchie von verschiedenen
Stufen der Unendlichkeit.
Es kann einem dabei auch heute noch schwindlig werden ...
> Aber warum muss die Abb. injektiv sein?
Eine "Abzählung" einer (abzählbar) unendlichen Menge G besteht
genau darin, dass man die Elemente der Menge quasi "nummerieren"
kann: erstes Element, zweites Element, drittes Element etc.
Eine solche Zuordnung von natürlichen Zahlen als Nummern
der Elemente ist mathematisch gesehen nichts anderes als
eine Abbildung von G nach [mm] \IN. [/mm] Injektiv soll sie sein, weil unter-
schiedliche Elemente von G stets auch unterschiedliche Nummern
tragen müssen. Keine Nummer darf mehrfach benützt werden.
Das weiß auch jeder Schafhirte, der es nur mit endlichen Mengen
von Schafen zu tun hat ...
> Gibt es überhaupt eine Abb. die von [mm]\IR[/mm] nach [mm]\IN[/mm]
> abbildet?
Natürlich: nimm zum Beispiel den Betrag einer reellen Zahl,
runde den auf die nächstkleinere ganze Zahl ab:
[mm] x\mapsto\lfloor|x|\rfloor
[/mm]
Falls du die Null nicht zu [mm] \IN [/mm] zählst, dann nimm
[mm] x\mapsto\lfloor|x|\rfloor+1
[/mm]
> Injektiv würde heißen jedes n aus [mm]\IN[/mm] hat höchstens ein
> r aus [mm]\IR.[/mm]
Dabei sprichst du jetzt aber von einer Abbildung [mm] f:\IN\to\IR
[/mm]
Eine Abzählung von [mm] \IR [/mm] müsste aber (wenn es sie denn gäbe)
eine injektive Abbildung [mm] f:\IR\to\IN [/mm] sein.
> Das würde doch (sollte überhaupt so eine Abb.
> existieren) gelten den die natürlichen Zahlen sind in den
> reellen enthalten.
Klar, die "natürliche Abbildung" oder "Einbettung" [mm] f:\IN\to\IR
[/mm]
mit [mm] f(n)=n\in\IR [/mm] ist eine injektive Abbildung, die aber nur zeigt,
dass [mm] \IR [/mm] "mindestens abzählbar unendlich" ist. Man kann aber
beweisen, dass keine Abbildung [mm] f:\IN\to\IR [/mm] surjektiv sein kann
oder keine Abbildung [mm] f:\IN\to\IR [/mm] injektiv.
> Wäre nett wenn noch wer meinen Beweis durchsehen kann
(das hat reverend ja schon mal getan)
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:17 So 12.06.2011 | | Autor: | Marcel |
Hallo,
> Man kann
> aber
> beweisen, dass keine Abbildung [mm]f:\IN\to\IR[/mm] surjektiv sein
> kann
> oder keine Abbildung [mm]f:\IN\to\IR[/mm] injektiv.
nur mal nebenbei:
Es gibt dabei verschiedene Standardbeweise. Ein Standardbeweis geht über das Intervallschachtelungsprinzip und danach nimmt man an, dass [mm] $[0,1]\,$ [/mm] abgezählt werden könnte, beweist dann aber mithilfe des Intervallschachtelungsprinzip die Existenz einer (von der Abzählung abhängigen) Zahl in [mm] $[0,1]\,,$ [/mm] die nicht erfasst wurde - egal, wie $[0,1]$ abgezählt wird. Bei jeder Abzählung von $[0,1]$ verbleibt also eine Zahl darin, die nicht erfasst wird. Somit kann $[0,1]$ nicht abgezählt werden, und da das eine Teilmenge von [mm] $\IR$ [/mm] ist: [mm] $\IR$ [/mm] auch nicht! (Ich bin mir nicht mehr ganz sicher, aber ich glaube, im Prinzip taucht dabei auch sowas wie die Cantorsche Wischmenge auf, oder ein ähnliches Prinzip wie bei der Konstruktion der Cantorschen Wischmenge...)
Dann kann man mit den dyadischen Darstellungen reeller Zahlen wohl auch arbeiten.
Und ebenso kann man, das wird wohl analog zu der dyadischen Darstellung gehen, das Cantorsche Diagonalverfahren benutzen, um einen Widerspruch zu erzeugen. Wenn ich mich recht erinnere, läuft das etwa so ab, wie man mit diesem Diagonalverfahren zeigt, dass
[mm] $$\IN^{\IN}$$
[/mm]
nicht abzählbar sein kann. Was übrigens (formal erstmal) erstaunlich erscheint, da ja [mm] $\IN^n=\IN^{\{1,\ldots,n\}}$ [/mm] für jedes $n [mm] \in \IN$ [/mm] abzählbar ist. Aber oft schreibt so manch' einer auch
[mm] $$\IN^{\IN}=\bigcup_{n \in \IN}\IN^n \;\;\; \leftarrow \text{das ist natürlich UNFUG}$$
und behauptet damit, das Gegenteil bewiesen zu haben. Eigentlich wird damit aber nur gezeigt, dass noch nicht mal die Definition von $\IN^{\IN}$ verstanden worden ist. (Ich spreche mich übrigens nicht davon frei, im Eifer des Gefechtes auch mal derartigen Unfug behauptet zu haben. Aber peinlich wurde es mir erst, als ich meine Gedanken sortiert und alles verstanden hatte. Im Stress denkt man halt auch manchmal komische Sachen und reimt sich komisches zusammen, wo man sich später irgendwann mal fragt, wenn man es wieder sieht, welchen Teufel einen da geritten hat. ^^)
Gruß,
Marcel
[/mm]
|
|
|
| |
|
Hallo Sup,
nachdem die Begrifflichkeit in ihrer Mehrdeutigkeit ja nun hinreichend festgestellt ist...
> Zeigen sie, dass die Menge der endlichen Teilmengen von [mm]\IN[/mm]
> abzählbar ist.
>
> So jetzt zur Aufgabe:
> Ich kann [mm]\IN[/mm] schreiben als [mm]\IN:= A_1 \cup A_2 \cup[/mm] ...[mm]\cup A_n[/mm]
> wobei [mm]A_n:=[/mm] [mm]\{A_n \subseteq \IN[/mm] : # [mm]A_n=n[/mm] , [mm]n\in \IN\}[/mm] ist.
> Oder muss die Menge [mm]\{A_i \subseteq \IN[/mm] : # [mm]A_i=i[/mm] , i [mm]\in \IN\}[/mm], weil ich das "n" schon in der Vereinigung verwendet
> habe?
Ja, mit i, aber [mm] #A_i=n, [/mm] dann ist es m.E. am besten lesbar und sauber. Also [mm] A_n:=\{A_i\subseteq\IN : \text{\#}A_i=n, n\in\IN\} [/mm]
> [mm]\IN:= A_1 \cup A_2 \cup[/mm] ... [mm]\cup A_n[/mm] sind abzählbar viele
> Teilmengen und jede dieser Teilmengen ist abzählbar, denn
> [mm]A_1:=[/mm] {1} [mm]\cup[/mm] {2} [mm]\cup[/mm] ... [mm]\cup[/mm] {n}.
Hm, nein. Per Definition ist [mm] A_1=\{\{1\}\}\cup\{\{2\}\}\cup\ \cdots\ \cup\{\{n\}\}
[/mm]
Das ist etwas völlig anderes.
Und [mm] \IN [/mm] ist keineswegs die Vereinigung aller [mm] A_n.
[/mm]
Die Vereinigung aller [mm] A_n [/mm] enthält als Elemente z.B. die Mengen [mm] \{17\}, \{2,9001\}, \{64,65,8272485\}, \{1,2,3\} [/mm] und [mm] \{1,3,9,27,81\}
[/mm]
> Endlich sind aber die Teilmengen von [mm]A_n,[/mm] oder?
Ja, korrekt.
> Insgesamt ist dann [mm]\IN=\bigcup_{i=1}^{n}A_i[/mm]
Das stimmt eben nicht.
> Jetzt hatten wir in der Vorlesung volgenden Satz:
> Ist A = [mm]\bigcup_{k \in \IN}^{} A_k[/mm] abzählbare Vereinigung
> von höchstens abzählbar unendlichen Mengen [mm]A_k[/mm] (k [mm]\in \IN),[/mm]
> so ist A höchstens abzählbar unendlich.
Die Frage bleibt, ob A wirklich eine abzählbare Vereinigung ist, da A als Elemente Mengen enthält und nicht etwa Zahlen (was die Folge der Vereinigung solcher Mengen wäre).
> Da "höchstens abzählbar" ja auch die Eigenschaft
> "abzählbar" beinhaltet, wäre der Beweis mit diesem Satz
> erbracht.
Nein, ganz so einfach nicht, aber der Satz ist hier schon nützlich und führt auch unmittelbar zum Ergebnis.
Im Prinzip geht der Nachweis hier genauso wie der Nachweis der Abzählbarkeit der rationalen Zahlen. Aber wie gesagt, kannst Du Deinen Satz dafür gut einsetzen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:05 Fr 10.06.2011 | | Autor: | Sup |
> Hallo Sup,
>
> nachdem die Begrifflichkeit in ihrer Mehrdeutigkeit ja nun
> hinreichend festgestellt ist...
>
> > Zeigen sie, dass die Menge der endlichen Teilmengen von [mm]\IN[/mm]
> > abzählbar ist.
> >
> > So jetzt zur Aufgabe:
> > Ich kann [mm]\IN[/mm] schreiben als [mm]\IN:= A_1 \cup A_2 \cup[/mm]
> ...[mm]\cup A_n[/mm]
> > wobei [mm]A_n:=[/mm] [mm]\{A_n \subseteq \IN[/mm] : # [mm]A_n=n[/mm] ,
> [mm]n\in \IN\}[/mm] ist.
> > Oder muss die Menge [mm]\{A_i \subseteq \IN[/mm] : # [mm]A_i=i[/mm] , i
> [mm]\in \IN\}[/mm], weil ich das "n" schon in der Vereinigung
> verwendet
> > habe?
>
> Ja, mit i, aber [mm]#A_i=n,[/mm] dann ist es m.E. am besten lesbar
> und sauber. Also [mm]A_n:=\{A_i\subseteq\IN : \text{\#}A_i=n, n\in\IN\}[/mm]
>
> > [mm]\IN:= A_1 \cup A_2 \cup[/mm] ... [mm]\cup A_n[/mm] sind abzählbar viele
> > Teilmengen und jede dieser Teilmengen ist abzählbar, denn
> > [mm]A_1:=[/mm] {1} [mm]\cup[/mm] {2} [mm]\cup[/mm] ... [mm]\cup[/mm] {n}.
>
> Hm, nein. Per Definition ist
> [mm]A_1=\{\{1\}\}\cup\{\{2\}\}\cup\ \cdots\ \cup\{\{n\}\}[/mm]
> Das
> ist etwas völlig anderes.
>
> Und [mm]\IN[/mm] ist keineswegs die Vereinigung aller [mm]A_n.[/mm]
> Die Vereinigung aller [mm]A_n[/mm] enthält als Elemente z.B. die
> Mengen [mm]\{17\}, \{2,9001\}, \{64,65,8272485\}, \{1,2,3\}[/mm] und
> [mm]\{1,3,9,27,81\}[/mm]
Also es leuchtet mir nicht ganz ein. Ich schreib nochmal in "Worten", wie ich es mir gedacht habe, vllt habe ich mich auch falsch ausgedrückt.
[mm] \IN [/mm] zerlege ich in: {alle 1-elementigen teilmengen} [mm] \cup [/mm] {alle 2-elementigen Teilmengen} [mm] \cup ...\cup [/mm] {alle n- elementigen Teilmengen}.
Warum kann man das denn nicht so zerlegen?
Diese Mengen seien nun [mm] A_1, [/mm] ..., [mm] A_n. [/mm] Also [mm] A_i [/mm] := {alle i-elementigen Teilmengen}. Das sind ja abzählbarviele Mengen.
Diese Mengen sind doch auch abzählbar, denn [mm] A_1 [/mm] enthält z.B. die Mengen {1} [mm] \cup ...\cup [/mm] {n}.
Also habe ich die Vereinigung abzählbar vieler Mengen, die weiderum selsbt auch abzählbar sind.
Könntest du netterweise nochmal zeigen warum da ein Fehler ist?
Wenn das falsch ist fehlt mir im Moment der Ansatz.
> > Endlich sind aber die Teilmengen von [mm]A_n,[/mm] oder?
>
> Ja, korrekt.
>
> > Insgesamt ist dann [mm]\IN=\bigcup_{i=1}^{n}A_i[/mm]
>
> Das stimmt eben nicht.
>
> > Jetzt hatten wir in der Vorlesung volgenden Satz:
> > Ist A = [mm]\bigcup_{k \in \IN}^{} A_k[/mm] abzählbare
> Vereinigung
> > von höchstens abzählbar unendlichen Mengen [mm]A_k[/mm] (k [mm]\in \IN),[/mm]
> > so ist A höchstens abzählbar unendlich.
>
> Die Frage bleibt, ob A wirklich eine abzählbare
> Vereinigung ist, da A als Elemente Mengen enthält und
> nicht etwa Zahlen (was die Folge der Vereinigung solcher
> Mengen wäre).
>
> > Da "höchstens abzählbar" ja auch die Eigenschaft
> > "abzählbar" beinhaltet, wäre der Beweis mit diesem Satz
> > erbracht.
>
> Nein, ganz so einfach nicht, aber der Satz ist hier schon
> nützlich und führt auch unmittelbar zum Ergebnis.
>
> Im Prinzip geht der Nachweis hier genauso wie der Nachweis
> der Abzählbarkeit der rationalen Zahlen. Aber wie gesagt,
> kannst Du Deinen Satz dafür gut einsetzen.
>
> Grüße
> reverend
>
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:08 Fr 10.06.2011 | | Autor: | Blech |
Hi,
> Also es leuchtet mir nicht ganz ein. Ich schreib nochmal in "Worten", wie ich es mir gedacht habe, vllt habe ich mich auch falsch ausgedrückt.
Ja.
> $ [mm] \IN [/mm] $ zerlege ich in: {alle 1-elementigen teilmengen} $ [mm] \cup [/mm] $ {alle 2-elementigen Teilmengen} $ [mm] \cup ...\cup [/mm] $ {alle n- elementigen Teilmengen}.
> Warum kann man das denn nicht so zerlegen?
1. Weil es keine Zerlegung ist.
[mm] $A_1=\{\text{alle 1-elementigen teilmengen}\}=\{\{1\},\{2\},\{3\},\{4\},\ldots\}$
[/mm]
[mm] $A_2=\{\text{alle 2-elementigen Teilmengen}\}=\{\{2,1\},\{3,1\},\{3,2\},\{4,1\},\ldots\}$
[/mm]
[mm] $\vdots$
[/mm]
Wenn Du das vereinigst kommt nicht [mm] $\IN$ [/mm] raus, denn z.B. ist [mm] $1\in\IN$, [/mm] aber nicht in [mm] $\bigcup_n A_n$, [/mm] während [mm] $\{1\}\in A_1$, [/mm] aber nicht in [mm] $\IN$.
[/mm]
1 ist eine Zahl, sie ist ein Element von [mm] $\IN$. $\{1\}$ [/mm] ist eine Menge mit einem Element, nämlich der Zahl 1. Sie ist eine Teilmenge von [mm] $\IN$, $\{1\}\subseteq\IN$.
[/mm]
[mm] $\bigcup_{n\in\IN}A_n$ [/mm] ist gar kein so schlechter Anfang, aber danach geht's in die Binsen.
2. Gibt es kein größtes "n". Es gibt ja auch n+1-elementige Teilmengen, n+2 elementige Teilmengen, etc.
> $ [mm] A_1, [/mm] $ ..., $ [mm] A_n. [/mm] $
impliziert, daß es endlich viele [mm] $A_i$ [/mm] gibt (nämlich n Stück). Schreib entweder [mm] $A_1, A_2,\ldots$, [/mm] oder wenn Du ein "generisches" Element betrachten willst [mm] $A_1, A_2,\ldots, A_n,\ldots$.
[/mm]
> denn $ [mm] A_1 [/mm] $ enthält z.B. die Mengen {1} $ [mm] \cup ...\cup [/mm] $ {n}.
Nein. [mm] $\{1\}\cup\ldots\cup\{n\}=\{1,\ldots,n\}$, [/mm] das ist n-elmentig, also nicht in [mm] $A_1$.
[/mm]
ciao
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:27 Fr 10.06.2011 | | Autor: | Sup |
> Hi,
>
> > Also es leuchtet mir nicht ganz ein. Ich schreib nochmal in
> "Worten", wie ich es mir gedacht habe, vllt habe ich mich
> auch falsch ausgedrückt.
>
> Ja.
>
> > [mm]\IN[/mm] zerlege ich in: {alle 1-elementigen teilmengen} [mm]\cup[/mm]
> {alle 2-elementigen Teilmengen} [mm]\cup ...\cup[/mm] {alle n-
> elementigen Teilmengen}.
> > Warum kann man das denn nicht so zerlegen?
>
> 1. Weil es keine Zerlegung ist.
>
> [mm]A_1=\{\text{alle 1-elementigen teilmengen}\}=\{\{1\},\{2\},\{3\},\{4\},\ldots\}[/mm]
>
> [mm]A_2=\{\text{alle 2-elementigen Teilmengen}\}=\{\{2,1\},\{3,1\},\{3,2\},\{4,1\},\ldots\}[/mm]
>
> [mm]\vdots[/mm]
>
> Wenn Du das vereinigst kommt nicht [mm]\IN[/mm] raus, denn z.B. ist
> [mm]1\in\IN[/mm], aber nicht in [mm]\bigcup_n A_n[/mm], während [mm]\{1\}\in A_1[/mm],
> aber nicht in [mm]\IN[/mm].
>
> 1 ist eine Zahl, sie ist ein Element von [mm]\IN[/mm]. [mm]\{1\}[/mm] ist
> eine Menge mit einem Element, nämlich der Zahl 1. Sie ist
> eine Teilmenge von [mm]\IN[/mm], [mm]\{1\}\subseteq\IN[/mm].
>
> [mm]\bigcup_{n\in\IN}A_n[/mm] ist gar kein so schlechter Anfang,
> aber danach geht's in die Binsen.
>
>
> 2. Gibt es kein größtes "n". Es gibt ja auch
> n+1-elementige Teilmengen, n+2 elementige Teilmengen, etc.
>
> > [mm]A_1,[/mm] ..., [mm]A_n.[/mm]
>
> impliziert, daß es endlich viele [mm]A_i[/mm] gibt (nämlich n
> Stück). Schreib entweder [mm]A_1, A_2,\ldots[/mm], oder wenn Du ein
> "generisches" Element betrachten willst [mm]A_1, A_2,\ldots, A_n,\ldots[/mm].
>
>
> > denn [mm]A_1[/mm] enthält z.B. die Mengen {1} [mm]\cup ...\cup[/mm] {n}.
>
> Nein. [mm]\{1\}\cup\ldots\cup\{n\}=\{1,\ldots,n\}[/mm], das ist
> n-elmentig, also nicht in [mm]A_1[/mm].
>
Gut, dann habe ich jetzt schonmal verstanden, warum mein Ansatz Schrott ist 
War jetzt den ganzen Tag auf Achse, aber werd mir bis morgen Abend mal was überlegen.
Tipps sind natürlich trotzdem gerne wilkommen
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:52 Sa 11.06.2011 | | Autor: | Sup |
Ich glaub ich hab die Aufgabe bei meinem 1. Versuch auch etwas falsch Verstanden, fällt mir gerade am Rande auf.
> [mm]\bigcup_{n\in\IN}A_n[/mm] ist gar kein so schlechter Anfang,
> aber danach geht's in die Binsen.
Dann mal ne andere Idee:
Sei M:= {A [mm] \subseteq \IN: [/mm] A ist abzählbar} und
[mm] M_n:= [/mm] {A [mm] \subseteq \IN: [/mm] A mit sup (A) [mm] \le [/mm] n}
Also ist M die Menge aller endlichen Teilmengen von [mm] \IN [/mm] und [mm] M_n [/mm] ist die Menge aller nach oben beschränkten Teilmengen.
Dann ist doch [mm] M=bigcup_{n\in\IN}M_n
[/mm]
Jetzt müsste ich doch nur irgendwie zeigen, dass [mm] M_n [/mm] abzählbar ist, denn dann könnte ich den Satz anwenden.
Nur wie zeige ich das?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:36 Sa 11.06.2011 | | Autor: | Marcel |
Hallo,
> Ich glaub ich hab die Aufgabe bei meinem 1. Versuch auch
> etwas falsch Verstanden, fällt mir gerade am Rande auf.
> > [mm]\bigcup_{n\in\IN}A_n[/mm] ist gar kein so schlechter Anfang,
> > aber danach geht's in die Binsen.
>
> Dann mal ne andere Idee:
> Sei M:= [mm] $\{A \subseteq \IN$: A ist abzählbar$\}$ [/mm] und
> [mm] $M_n:= \{A \subseteq \IN$ A mit sup (A) $\le$ n$\}$
[/mm]
dann gilt auch [mm] $M_n=\{A \subseteq \IN: \text{max}(A) \le n\}\,.$ [/mm] Denn endliche nach oben beschränkte Mengen nehmen ihr Supremum an, insbesondere nimmt jede endliche Teilmenge der natürlichen Zahlen ihr Supremum an (und auch ihr Infimum). Aber das nur nebenbei nochmal.
> Also ist M die Menge aller endlichen Teilmengen von [mm]\IN[/mm] und
> [mm]M_n[/mm] ist die Menge aller nach oben beschränkten
> Teilmengen.
Nein. [mm] $M_n$ [/mm] ist nicht die Menge aller nach oben beschränkten Teilmengen von [mm] $\IN\,,$ [/mm] sondern die Menge aller nach oben beschränkten Teilmengen von [mm] $\IN\,,$ [/mm] so dass eine obere Schranke einer Menge aus [mm] $M_n$ [/mm] sicher [mm] $\le [/mm] n$ ist.
> Dann ist doch [mm]M=\bigcup_{n \in \IN}M_n[/mm]
Das sollte in der Tat so sein. Beweis es doch mal: Du hast zwei Sachen zu begründen:
1.) Jedes Element aus [mm] $M\,$ [/mm] muss auch in der Vereinigung rechterhand liegen.
UND
2.) Jedes Element aus der Vereinigung rechterhand muss auch in [mm] $M\,$ [/mm] liegen.
Etwa zu 2.): Ist $X [mm] \in \bigcup_{n \in \IN}M_n\,,$ [/mm] so existiert ein $N [mm] \in \IN$ [/mm] mit $X [mm] \in M_N\,.$ [/mm] Dann ist aber $X [mm] \subseteq \IN$ [/mm] mit [mm] $\text{sup}(X)=\text{max}(X) \le N\,,$ [/mm] also [mm] $X\,$ [/mm] beschränkte Teilmenge von [mm] $\IN\,,$ [/mm] also $X [mm] \in M\,.$ [/mm]
Jetzt beweise Du mal 1.)...
> Jetzt müsste ich doch nur irgendwie zeigen, dass [mm]M_n[/mm]
> abzählbar ist, denn dann könnte ich den Satz anwenden.
> Nur wie zeige ich das?
Das ist gar nicht so schwer. Beachte erstens:
Wenn ich die Potenzmenge einer endlichen Menge betrachte, so besteht diese aus endlich vielen Teilmengen. Genauer gilt:
Ist [mm] $T\,$ [/mm] eine [mm] $m\,$-elementige [/mm] Menge, so hat [mm] $\text{Pot}(T)$ [/mm] genau [mm] $2^m$ [/mm] Elemente (es gibt also [mm] $2^m$ [/mm] Teilmengen von [mm] $T\,$).
[/mm]
Nun gilt doch:
[mm] $$M_n=\{A \subseteq \IN: \text{sup}(A) \le n\}=\{A \subseteq \IN: A \subseteq \{1,\dlots,n\}\}=\text{Pot}(\{1,\ldots,n\})\,.$$
[/mm]
[mm] $\text{(}$Beweise [/mm] das zweite Gleichheitszeichen, oder kurz: Begründe, dass gilt:
[mm] $$\{A \subseteq \IN: \text{sup}(A) \le n\}=\text{Pot}(\{1,\ldots,n\}).$$
[/mm]
Also ist [mm] $|M_n|=2^n\,,$ [/mm] weil [mm] $|\{1,\ldots,n\}|=n\,.$ [/mm] Somit ist [mm] $M_n$ [/mm] sogar endlich (für jedes beliebige, feste $n [mm] \in \IN$), [/mm] insbesondere (höchstens) abzählbar. (Bemerkung: Im Gegensatz zu manch' anderem hier gesagten kenne ich es eigentlich so, dass man endliche oder abzählbar unendliche Mengen kurz einfach abzählbar nennt, um den Begriff "höchstens abzählbar" gar nicht zu benutzen. Ist aber auch ein wenig Geschmackssache oder Gebrauchs-/Gewöhnungssache...)
P.S.:
Gut ist jedenfalls, dass Du bei den [mm] $M_n$-Definitionen [/mm] ein [mm] $\le$ [/mm] und kein [mm] $=\,$ [/mm] stehen hast. Beim [mm] $=\,$ [/mm] könnte man sicher auch begründen, warum diese Mengen endlich sind (denn wenn [mm] $\tilde{M}_n:=\{A \subseteq \IN: \text{max}(A)=\text{sup}(A) \blue{=}n\}\,,$ [/mm] dann ist [mm] $\tilde{M}_n \subseteq M_n$) [/mm] - aber einen direkte Überlegung ohne diesen Umweg, warum [mm] $\tilde{M}_n$ [/mm] höchstens abz. bzw. sogar endlich ist, wäre evtl. umständlich(er).
P.P.S.:
Vielleicht wäre es sogar günstiger, den Beweis direkt so anzugehen, dass man
[mm] $$M_n:=\text{Pot}\{1,\ldots,n\}$$
[/mm]
definiert und dann
[mm] $$M=\bigcup_{n \in \IN}M_n$$
[/mm]
beweist. Das erspart uns den kleinen Umweg, den Deine Definition der [mm] $M_n$ [/mm] erfordert.
Beachte übrigens, dass ich davon ausgehe, dass bei Euch $0 [mm] \notin \IN$ [/mm] gilt. Ist bei Euch allerdings [mm] $\IN=\IN_0=\IN \cup \{0\}\,,$ [/mm] so wäre natürlich
[mm] $$M_n:=\{0,\ldots,n\}$$
[/mm]
zu setzen.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:07 So 12.06.2011 | | Autor: | reverend |
Hallo Marcel,
da muss ich ein "Moment mal!" dazwischen rufen. Dieser Weg führt nicht zur Lösung der Aufgabe.
> > Also ist M die Menge aller endlichen Teilmengen von [mm]\IN[/mm] und
> > [mm]M_n[/mm] ist die Menge aller nach oben beschränkten
> > Teilmengen.
>
> Nein. [mm]M_n[/mm] ist nicht die Menge aller nach oben beschränkten
> Teilmengen von [mm]\IN\,,[/mm] sondern die Menge aller nach oben
> beschränkten Teilmengen von [mm]\IN\,,[/mm] so dass eine obere
> Schranke einer Menge aus [mm]M_n[/mm] sicher [mm]\le n[/mm] ist.
Soweit gut. Wir behalten mal die Aussage "M ist die Menge aller endlichen Teilmengen von [mm] \IN" [/mm] im Kopf.
> > Jetzt müsste ich doch nur irgendwie zeigen, dass [mm]M_n[/mm]
> > abzählbar ist, denn dann könnte ich den Satz anwenden.
> > Nur wie zeige ich das?
Das ist richtig für endliches n. Sonst nicht.
> Das ist gar nicht so schwer. Beachte erstens:
> Wenn ich die Potenzmenge einer endlichen Menge betrachte,
> so besteht diese aus endlich vielen Teilmengen. Genauer
> gilt:
> Ist [mm]T\,[/mm] eine [mm]m\,[/mm]-elementige Menge, so hat [mm]\text{Pot}(T)[/mm]
> genau [mm]2^m[/mm] Elemente (es gibt also [mm]2^m[/mm] Teilmengen von [mm]T\,[/mm]).
Eben, eben.
> Nun gilt doch:
> [mm]M_n=\{A \subseteq \IN: \text{sup}(A) \le n\}=\{A \subseteq \IN: A \subseteq \{1,\dlots,n\}\}=\text{Pot}(\{1,\ldots,n\})\,.[/mm]
>
> [mm]\text{(}[/mm]Beweise das zweite Gleichheitszeichen, oder kurz:
> Begründe, dass gilt:
> [mm]\{A \subseteq \IN: \text{sup}(A) \le n\}=\text{Pot}(\{1,\ldots,n\}).[/mm]
>
> Also ist [mm]|M_n|=2^n\,,[/mm] weil [mm]|\{1,\ldots,n\}|=n\,.[/mm] Somit ist
> [mm]M_n[/mm] sogar endlich (für jedes beliebige, feste [mm]n \in \IN[/mm]),
> insbesondere (höchstens) abzählbar.
Das stimmt natürlich. Nur soll [mm] n\to\infty [/mm] laufen, und dann stimmt es nicht mehr so einfach.
Der Weg über die Potenzmenge führt nicht zum Ziel, da die Potenzmenge von [mm] \IN [/mm] überabzählbar ist. Von hier führt der Weg direkt zum berühmten Kontinuumsproblem, aber nicht zur Lösung der Aufgabe.
***
Ein Hinweis zur Lösung:
Ich hatte den Tipp hinterlassen, dass die Lösung so funktioniere wie der Nachweis, dass [mm] \IQ^+ [/mm] abzählbar sei (und von da aus auch [mm] \IQ; [/mm] ein bekannter Beweis, wie ich annehme).
Machen wir eine Tabelle auf. In der ersten Zeile stehen alle Teilmengen von [mm] \IN [/mm] mit einem Element. Das sind abzählbar (unendlich) viele.
In der zweiten Zeile stehen alle Teilmengen von [mm] \IN [/mm] mit zwei Elementen, zweifelsfrei angeordnet, z.B. [mm] \{1,1\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,4\}, \{2,4\}, \{3,4\} [/mm] etc.
(Hier ist wesentlich, dass die Zeile geordnet werden kann, auch wenn die Ordnung selbst nichts zur Sache tut).
In der nächsten Zeile also alle dreielementigen Teilmengen von [mm] \IN, [/mm] usw.
Nun haben wir eine Tabelle mit abzählbar unendlich vielen Zeilen, jede davon mit abzählbar unendlich vielen Einträgen.
Diese Tabelle laufen wir jetzt in einem einzigen Weg ab und zeigen damit, dass die Anzahl der Einträge darin abzählbar unendlich ist. Dieser Weg ist einfach konstruiert und leichter zu veranschaulichen, wenn man eine entsprechende Tabelle der positiven rationalen Zahlen betrachtet:
in der ersten Zeile stehen alle Brüche mit einer 1 im Nenner, in der zweiten alle mit einer 2 im Nenner etc.
Dann laufen wir wie folgt alle Einträge ab: [mm] \tfrac{1}{1}, \tfrac{2}{1}, \tfrac{1}{2}, \tfrac{1}{3}, \tfrac{2}{2}, \tfrac{3}{1}, \tfrac{4}{1}, \tfrac{3}{2}, \tfrac{2}{3}, \tfrac{1}{4}\ \cdots
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:59 So 12.06.2011 | | Autor: | Marcel |
Hallo Reverend,
> Hallo Marcel,
>
> da muss ich ein "Moment mal!" dazwischen rufen. Dieser Weg
> führt nicht zur Lösung der Aufgabe.
>
> > > Also ist M die Menge aller endlichen Teilmengen von [mm]\IN[/mm] und
> > > [mm]M_n[/mm] ist die Menge aller nach oben beschränkten
> > > Teilmengen.
> >
> > Nein. [mm]M_n[/mm] ist nicht die Menge aller nach oben beschränkten
> > Teilmengen von [mm]\IN\,,[/mm] sondern die Menge aller nach oben
> > beschränkten Teilmengen von [mm]\IN\,,[/mm] so dass eine obere
> > Schranke einer Menge aus [mm]M_n[/mm] sicher [mm]\le n[/mm] ist.
>
> Soweit gut. Wir behalten mal die Aussage "M ist die Menge
> aller endlichen Teilmengen von [mm]\IN"[/mm] im Kopf.
>
> > > Jetzt müsste ich doch nur irgendwie zeigen, dass [mm]M_n[/mm]
> > > abzählbar ist, denn dann könnte ich den Satz anwenden.
> > > Nur wie zeige ich das?
>
> Das ist richtig für endliches n. Sonst nicht.
>
> > Das ist gar nicht so schwer. Beachte erstens:
> > Wenn ich die Potenzmenge einer endlichen Menge
> betrachte,
> > so besteht diese aus endlich vielen Teilmengen. Genauer
> > gilt:
> > Ist [mm]T\,[/mm] eine [mm]m\,[/mm]-elementige Menge, so hat [mm]\text{Pot}(T)[/mm]
> > genau [mm]2^m[/mm] Elemente (es gibt also [mm]2^m[/mm] Teilmengen von [mm]T\,[/mm]).
>
> Eben, eben.
>
> > Nun gilt doch:
> > [mm]M_n=\{A \subseteq \IN: \text{sup}(A) \le n\}=\{A \subseteq \IN: A \subseteq \{1,\dlots,n\}\}=\text{Pot}(\{1,\ldots,n\})\,.[/mm]
>
> >
> > [mm]\text{(}[/mm]Beweise das zweite Gleichheitszeichen, oder kurz:
> > Begründe, dass gilt:
> > [mm]\{A \subseteq \IN: \text{sup}(A) \le n\}=\text{Pot}(\{1,\ldots,n\}).[/mm]
>
> >
> > Also ist [mm]|M_n|=2^n\,,[/mm] weil [mm]|\{1,\ldots,n\}|=n\,.[/mm] Somit ist
> > [mm]M_n[/mm] sogar endlich (für jedes beliebige, feste [mm]n \in \IN[/mm]),
> > insbesondere (höchstens) abzählbar.
>
> Das stimmt natürlich. Nur soll [mm]n\to\infty[/mm] laufen, und dann
> stimmt es nicht mehr so einfach.
nein. Wir wissen bisher:
Für jedes $n [mm] \in \IN$ [/mm] ist [mm] $M_n$ [/mm] als Potenzmenge einer endlichen Menge endlich, insbesondere (um in der vorgegebenen Sprechweise zu bleiben) höchstens abzählbar.
Weiter ist [mm] $\IN$ [/mm] abzählbar. Abzählbare Vereinigungen höchstens abzählbarer Mengen sind höchstens abzählbar. Und bei
[mm] $$M=\bigcup_{n \in \IN}M_n$$
[/mm]
steht rechterhand nicht wirklich, wie das [mm] $n\,$ [/mm] laufen gelassen wird. Der Index [mm] $n\,$ [/mm] durchläuft die abzählbare Menge [mm] $\IN\,$ [/mm] (egal wie), und daher ist [mm] $\bigcup_{n \in \IN}$ [/mm] "eine abzählbare Vereinigung".
(Das manchmal [mm] $\bigcup_{n \in \IN}$ [/mm] als [mm] $\bigcup_{n=1}^\infty$ [/mm] geschrieben wird, kann man machen, weil bei solch einer Vereinigung die Ordnung von [mm] $\IN$ [/mm] bzw. die Reihenfolge des Durchlaufs sich nicht auf das Endergebnis auswirkt. Anders, wie bei Reihen!)
Unklar war, ob für jedes $n [mm] \in \IN$ [/mm] auch [mm] $M_n$ [/mm] abzählbar ist, aber genau das wurde geklärt, weil das Mengensystem [mm] $M_n$ [/mm] nur endlich viele Mengen enthält. (S.o.)
Also ist die Behauptung bewiesen.
P.S.:
[mm] $\text{Pot}(\IN)$ [/mm] wird dort nirgends benutzt. Wir benutzen nur [mm] $\text{Pot}(\{1,\ldots,n\})$ [/mm] für jedes $n [mm] \in \IN\,,$ [/mm] was dann als beliebig, aber fest zu betrachten ist, und [mm] $\{1,\ldots,n\}$ [/mm] ist für jedes beliebige, feste $n [mm] \in \IN$ [/mm] eine endliche Menge.
Etwas komisches wie [mm] $\text{Pot(\IN)}$ [/mm] oder gar [mm] $\text{Pot}(\lim_{n \to \infty}\{1,\ldots,n\})$ [/mm] (was immer das auch bedeuten sollte) wird an keiner Stelle benutzt!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:42 So 12.06.2011 | | Autor: | reverend |
Hallo Marcel,
ich bezweifle überhaupt nicht, dass Du Recht hast, sondern nur, dass der Beweis eine Gratwanderung darstellt, die ständig nah am Abgrund verläuft. Es ist nötig, da so präzise wie möglich zu sein. Deine Erläuterungen zeigen, dass Du Dir diese Mühe gemacht hast, aber das war mir zuvor nicht so recht deutlich. Verzeih also den Zwischenruf; Deine Erklärung trägt sehr zur Präzisierung bei; ich habe nichts zu bemängeln. Hier also nur ein paar Reaktionen:
> > Das stimmt natürlich. Nur soll [mm]n\to\infty[/mm] laufen, und dann
> > stimmt es nicht mehr so einfach.
(Das war vielleicht nicht geschickt formuliert, aber das "nicht mehr so einfach" sollte eben eine genauere Erklärung einfordern.)
> nein. Wir wissen bisher:
> Für jedes [mm]n \in \IN[/mm] ist [mm]M_n[/mm] als Potenzmenge einer
> endlichen Menge endlich, insbesondere (um in der
> vorgegebenen Sprechweise zu bleiben) höchstens
> abzählbar.
>
> Weiter ist [mm]\IN[/mm] abzählbar. Abzählbare Vereinigungen
> höchstens abzählbarer Mengen sind höchstens abzählbar.
Ja, dieser Satz war ja bereits angeführt worden.
> Und bei
> [mm]M=\bigcup_{n \in \IN}M_n[/mm]
> steht rechterhand nicht wirklich,
> wie das [mm]n\,[/mm] laufen gelassen wird. Der Index [mm]n\,[/mm] durchläuft
> die abzählbare Menge [mm]\IN\,[/mm] (egal wie), und daher ist
> [mm]\bigcup_{n \in \IN}[/mm] "eine abzählbare Vereinigung".
>
> (Das manchmal [mm]\bigcup_{n \in \IN}[/mm] als [mm]\bigcup_{n=1}^\infty[/mm]
> geschrieben wird, kann man machen, weil bei solch einer
> Vereinigung die Ordnung von [mm]\IN[/mm] bzw. die Reihenfolge des
> Durchlaufs sich nicht auf das Endergebnis auswirkt. Anders,
> wie bei Reihen!)
Ja, klar.
> Unklar war, ob für jedes [mm]n \in \IN[/mm] auch [mm]M_n[/mm] abzählbar
> ist, aber genau das wurde geklärt, weil das Mengensystem
> [mm]M_n[/mm] nur endlich viele Mengen enthält. (S.o.)
>
> Also ist die Behauptung bewiesen.
Das ist richtig, aber nicht offensichtlich, eben weil ja nicht ein festes n untersucht wird, sondern jedes n, auch "das unendliche".
> P.S.:
> [mm]\text{Pot}(\IN)[/mm] wird dort nirgends benutzt. Wir benutzen
> nur [mm]\text{Pot}(\{1,\ldots,n\})[/mm] für jedes [mm]n \in \IN\,,[/mm] was
> dann als beliebig, aber fest zu betrachten ist, und
> [mm]\{1,\ldots,n\}[/mm] ist für jedes beliebige, feste [mm]n \in \IN[/mm]
> eine endliche Menge.
Richtig. Dennoch - und dagegen richtete sich mein Zwischenruf - ist es eben nicht zielführend, auf die Potenzmenge zu rekurrieren, eben weil sie in die Paradoxien der Unendlichkeit führen kann (ja, ich habe meinen Bolzano gelesen...).
> Etwas komisches wie [mm]\text{Pot(\IN)}[/mm] oder gar
> [mm]\text{Pot}(\lim_{n \to \infty}\{1,\ldots,n\})[/mm] (was immer
> das auch bedeuten sollte) wird an keiner Stelle benutzt!
Das wäre ja auch nicht klug. Genau darum würde ich eben Potenzmengen auch vermeiden, sie sind hier möglich, aber nicht nötig. Nur darum ging es mir.
Herzliche Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:50 So 12.06.2011 | | Autor: | Marcel |
Hallo Reverend,
> Hallo Marcel,
>
> ich bezweifle überhaupt nicht, dass Du Recht hast, sondern
> nur, dass der Beweis eine Gratwanderung darstellt, die
> ständig nah am Abgrund verläuft. Es ist nötig, da so
> präzise wie möglich zu sein. Deine Erläuterungen zeigen,
> dass Du Dir diese Mühe gemacht hast, aber das war mir
> zuvor nicht so recht deutlich. Verzeih also den
> Zwischenruf; Deine Erklärung trägt sehr zur Präzisierung
> bei; ich habe nichts zu bemängeln. Hier also nur ein paar
> Reaktionen:
>
> > > Das stimmt natürlich. Nur soll [mm]n\to\infty[/mm] laufen, und dann
> > > stimmt es nicht mehr so einfach.
>
> (Das war vielleicht nicht geschickt formuliert, aber das
> "nicht mehr so einfach" sollte eben eine genauere
> Erklärung einfordern.)
>
> > nein. Wir wissen bisher:
> > Für jedes [mm]n \in \IN[/mm] ist [mm]M_n[/mm] als Potenzmenge einer
> > endlichen Menge endlich, insbesondere (um in der
> > vorgegebenen Sprechweise zu bleiben) höchstens
> > abzählbar.
> >
> > Weiter ist [mm]\IN[/mm] abzählbar. Abzählbare Vereinigungen
> > höchstens abzählbarer Mengen sind höchstens abzählbar.
>
> Ja, dieser Satz war ja bereits angeführt worden.
>
> > Und bei
> > [mm]M=\bigcup_{n \in \IN}M_n[/mm]
> > steht rechterhand nicht
> wirklich,
> > wie das [mm]n\,[/mm] laufen gelassen wird. Der Index [mm]n\,[/mm] durchläuft
> > die abzählbare Menge [mm]\IN\,[/mm] (egal wie), und daher ist
> > [mm]\bigcup_{n \in \IN}[/mm] "eine abzählbare Vereinigung".
> >
> > (Das manchmal [mm]\bigcup_{n \in \IN}[/mm] als [mm]\bigcup_{n=1}^\infty[/mm]
> > geschrieben wird, kann man machen, weil bei solch einer
> > Vereinigung die Ordnung von [mm]\IN[/mm] bzw. die Reihenfolge des
> > Durchlaufs sich nicht auf das Endergebnis auswirkt. Anders,
> > wie bei Reihen!)
>
> Ja, klar.
>
> > Unklar war, ob für jedes [mm]n \in \IN[/mm] auch [mm]M_n[/mm] abzählbar
> > ist, aber genau das wurde geklärt, weil das Mengensystem
> > [mm]M_n[/mm] nur endlich viele Mengen enthält. (S.o.)
> >
> > Also ist die Behauptung bewiesen.
>
> Das ist richtig, aber nicht offensichtlich, eben weil ja
> nicht ein festes n untersucht wird, sondern jedes n, auch
> "das unendliche".
mag' sein, dass Du da mehr weißt, als ich. Aber ich verstehe generell die Problematik auch noch nicht. Wenn ich zeigen will, dass $n < [mm] n^2$ [/mm] für jedes $n [mm] \in \IN$ [/mm] gilt, laufe ich auch ins unendliche. Bei allen Grenzwertprozessen mache ich das. Um aber "analoger" zu bleiben:
Beim Majorantenkriterium geht man auch vor, dass man "für jedes $n [mm] \in \IN$" [/mm] etwas abschätzt, und schließt daraufhin etwas bei der Grenzprozessbildung.
> > P.S.:
> > [mm]\text{Pot}(\IN)[/mm] wird dort nirgends benutzt. Wir
> benutzen
> > nur [mm]\text{Pot}(\{1,\ldots,n\})[/mm] für jedes [mm]n \in \IN\,,[/mm] was
> > dann als beliebig, aber fest zu betrachten ist, und
> > [mm]\{1,\ldots,n\}[/mm] ist für jedes beliebige, feste [mm]n \in \IN[/mm]
> > eine endliche Menge.
>
> Richtig. Dennoch - und dagegen richtete sich mein
> Zwischenruf - ist es eben nicht zielführend, auf die
> Potenzmenge zu rekurrieren, eben weil sie in die Paradoxien
> der Unendlichkeit führen kann (ja, ich habe meinen Bolzano
> gelesen...).
Ich ehrlich gesagt nicht. Vielleicht ist das mein Manko und ich verstehe daher Deinen Einwand (noch) nicht. Denn derartige Argumentationen, auch mit Mengen etc. und auch Potenzmengen, sind eigentlich Usus in der Mathematik, ohne, dass da ständig irgendwelche Kritik angebracht wird. Was nicht heißt, dass da nicht vielleicht doch Kritik angebracht wäre. Mir ist nur die Kritik momentan einfach ganz und gar unklar, ganz ehrlich. Da bin ich vielleicht auch "mengentheoretisch zu naiv gebildet".
> > Etwas komisches wie [mm]\text{Pot(\IN)}[/mm] oder gar
> > [mm]\text{Pot}(\lim_{n \to \infty}\{1,\ldots,n\})[/mm] (was immer
> > das auch bedeuten sollte) wird an keiner Stelle benutzt!
>
> Das wäre ja auch nicht klug. Genau darum würde ich eben
> Potenzmengen auch vermeiden, sie sind hier möglich, aber
> nicht nötig. Nur darum ging es mir.
Wie gesagt:Nichts für ungut. Ich würde gerne draus lernen, bisher kapiere ich nur einfach gar nicht, was ich dafür verstehen muss.
Grüße,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:14 So 12.06.2011 | | Autor: | Marcel |
Hallo reverend,
> Ein Hinweis zur Lösung:
> Ich hatte den Tipp hinterlassen, dass die Lösung so
> funktioniere wie der Nachweis, dass [mm]\IQ^+[/mm] abzählbar sei
> (und von da aus auch [mm]\IQ;[/mm] ein bekannter Beweis, wie ich
> annehme).
das ist doch das gleiche wie der Beweis, dass [mm] $\IN \times \IN$ [/mm] abzählbar ist. Das kann man auch so machen:
Es gilt
[mm] $$\IN \times \IN=\bigcup_{p \in \IN} \IN_p$$
[/mm]
mit
[mm] $$\IN_p:=\{(p,q): q \in \IN\}\,.$$
[/mm]
Jedes [mm] $\IN_p$ [/mm] ist abzählbar, da zu [mm] $\IN$ [/mm] gleichmächtig (trivialerweise), und damit ist [mm] $\IN \times \IN$ [/mm] als abzählbare Vereinigung abzählbarer Mengen abzählbar.
Das ist das gleiche Prinzip wie eben:
Das [mm] $p\,,$ [/mm] was hier [mm] $\IN$ [/mm] durchläuft, entspricht dem [mm] $n\,$ [/mm] von eben. Und die [mm] $\IN_p$'s [/mm] übernehmen quasi die Rolle der [mm] $M_n$'s, [/mm] nur, dass die [mm] $M_n$'s [/mm] nur aus endlich vielen Elementen (jedes Element VON [mm] $M_n$ [/mm] (!!) war dabei eine Teilmenge von [mm] $\IN$) [/mm] bestanden haben, während die [mm] $\IN_p$'s [/mm] hier sogar abzählbar unendlich sind.
Du siehst übrigens:
Wäre bei mir vorhin so etwas wie [mm] $\text{Pot}(\IN)=M$ [/mm] entstanden, so würde diese Argumentation hier zeigen, dass [mm] $\text{Pot}(N)$ [/mm] eine Teilmenge von [mm] $\IN \times \IN$ [/mm] wäre. (Was wäre denn dann das Fazit, wenn man weiß, dass [mm] $\IN \times \IN$abzählbar [/mm] ist?)
Ich will jetzt nicht böse sein: Aber kann es sein, dass Du die Argumentationen bzgl. Abzählbarkeitsaufgaben mithilfe des Satzes
"abzählbare Vereinigungen abzählbarer Mengen sind abzählbar"
nicht gewohnt bist, oder die Verwendung dieses Satzes vermeiden willst? Denn mit dem Kontinummsproblem hat das ganze hier (weder bei dem Beweis der Abzählbarkeit von [mm] $\IN \times \IN$ [/mm] noch bei der hier gestellten Aufgabe) wenig bis nichts zu tun ^^
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:50 So 12.06.2011 | | Autor: | reverend |
Hallo nochmal,
wir sind uns, wie gesagt, nicht uneins.
> > Ein Hinweis zur Lösung:
> > Ich hatte den Tipp hinterlassen, dass die Lösung so
> > funktioniere wie der Nachweis, dass [mm]\IQ^+[/mm] abzählbar sei
> > (und von da aus auch [mm]\IQ;[/mm] ein bekannter Beweis, wie ich
> > annehme).
>
> das ist doch das gleiche wie der Beweis, dass [mm]\IN \times \IN[/mm]
> abzählbar ist.
Ja.
> Das kann man auch so machen:
> Es gilt
> [mm]\IN \times \IN=\bigcup_{p \in \IN} \IN_p[/mm]
> mit
> [mm]\IN_p:=\{(p,q): q \in \IN\}\,.[/mm]
>
> Jedes [mm]\IN_p[/mm] ist abzählbar, da zu [mm]\IN[/mm] gleichmächtig
> (trivialerweise), und damit ist [mm]\IN \times \IN[/mm] als
> abzählbare Vereinigung abzählbarer Mengen abzählbar.
Auch klar.
Genauso für [mm] \IN\times\IN\times\IN [/mm] oder für [mm] \IN^n [/mm] mit endlichem n.
Aber eben nur für endliche n. Diese Falle sollte man besser nicht öffnen.
> Das ist das gleiche Prinzip wie eben:
> Das [mm]p\,,[/mm] was hier [mm]\IN[/mm] durchläuft, entspricht dem [mm]n\,[/mm] von
> eben. Und die [mm]\IN_p[/mm]'s übernehmen quasi die Rolle der
> [mm]M_n[/mm]'s, nur, dass die [mm]M_n[/mm]'s nur aus endlich vielen Elementen
> (jedes Element VON [mm]M_n[/mm] (!!) war dabei eine Teilmenge von
> [mm]\IN[/mm]) bestanden haben, während die [mm]\IN_p[/mm]'s hier sogar
> abzählbar unendlich sind.
>
> Du siehst übrigens:
> Wäre bei mir vorhin so etwas wie [mm]\text{Pot}(\IN)=M[/mm]
> entstanden, so würde diese Argumentation hier zeigen, dass
> [mm]\text{Pot}(N)[/mm] eine Teilmenge von [mm]\IN \times \IN[/mm] wäre. (Was
> wäre denn dann das Fazit, wenn man weiß, dass [mm]\IN \times \IN[/mm]abzählbar
> ist?)
>
> Ich will jetzt nicht böse sein: Aber kann es sein, dass Du
> die Argumentationen bzgl. Abzählbarkeitsaufgaben mithilfe
> des Satzes
> "abzählbare Vereinigungen abzählbarer Mengen sind
> abzählbar"
> nicht gewohnt bist, oder die Verwendung dieses Satzes
> vermeiden willst?
Oh, keineswegs. Man muss keinen "Pfad" angeben, um die Abzählbarkeit von [mm] \IN\times\IN [/mm] zu zeigen. Mir ging es da nur um Anschaulichkeit, wie so oft. Der bereits zitierte Satz enthebt uns aber einer solchen Notwendigkeit.
> Denn mit dem Kontinummsproblem hat das
> ganze hier (weder bei dem Beweis der Abzählbarkeit von [mm]\IN \times \IN[/mm]
> noch bei der hier gestellten Aufgabe) wenig bis nichts zu
> tun ^^
Solange man sauber vorgeht, nicht. Aber die Gefahr, unversehens dahin abzurutschen, bleibt bestehen. Denn die Hierarchie der Unendlichkeiten lauert bei jedem falschen Schritt. Du kennst diese Bedrohung ja offenbar genau, aber das mag nicht jedem Neuling so gehen. Und bei [mm] \aleph_0^{\aleph_0} [/mm] wollen wir ja nicht landen.
Die Aufgabe ist übrigens gerade deswegen alles andere als leichtes Übungsmaterial.
Herzliche Grüße und gute Nacht,
reverend
PS: Ich bin wohl erst morgen abend wieder online. Nimm mir bitte nicht übel, wenn ich vorher nicht reagieren kann.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:12 So 12.06.2011 | | Autor: | Sup |
Also ihr beide habt mich jetzt etwas verwirrt.
Ist der Ansatz von Marcl jetzt richtig oder sind eure beiden Ansätze richtig?
> Hallo,
>
> > Ich glaub ich hab die Aufgabe bei meinem 1. Versuch auch
> > etwas falsch Verstanden, fällt mir gerade am Rande auf.
> > > [mm]\bigcup_{n\in\IN}A_n[/mm] ist gar kein so schlechter
> Anfang,
> > > aber danach geht's in die Binsen.
> >
> > Dann mal ne andere Idee:
> > Sei M:= [mm]\{A \subseteq \IN[/mm]: A ist abzählbar[mm]\}[/mm] und
> > [mm]M_n:= \{A \subseteq \IN[/mm] A mit sup (A) [mm]\le[/mm] n[mm]\}[/mm]
>
> dann gilt auch [mm]M_n=\{A \subseteq \IN: \text{max}(A) \le n\}\,.[/mm]
> Denn endliche nach oben beschränkte Mengen nehmen ihr
> Supremum an, insbesondere nimmt jede endliche Teilmenge der
> natürlichen Zahlen ihr Supremum an (und auch ihr Infimum).
> Aber das nur nebenbei nochmal.
>
> > Also ist M die Menge aller endlichen Teilmengen von [mm]\IN[/mm] und
> > [mm]M_n[/mm] ist die Menge aller nach oben beschränkten
> > Teilmengen.
>
> Nein. [mm]M_n[/mm] ist nicht die Menge aller nach oben beschränkten
> Teilmengen von [mm]\IN\,,[/mm] sondern die Menge aller nach oben
> beschränkten Teilmengen von [mm]\IN\,,[/mm] so dass eine obere
> Schranke einer Menge aus [mm]M_n[/mm] sicher [mm]\le n[/mm] ist.
>
> > Dann ist doch [mm]M=\bigcup_{n \in \IN}M_n[/mm]
>
> Das sollte in der Tat so sein. Beweis es doch mal: Du hast
> zwei Sachen zu begründen:
> 1.) Jedes Element aus [mm]M\,[/mm] muss auch in der Vereinigung
> rechterhand liegen.
>
> UND
>
> 2.) Jedes Element aus der Vereinigung rechterhand muss auch
> in [mm]M\,[/mm] liegen.
>
> Etwa zu 2.): Ist [mm]X \in \bigcup_{n \in \IN}M_n\,,[/mm] so
> existiert ein [mm]N \in \IN[/mm] mit [mm]X \in M_N\,.[/mm]
> Dann ist aber [mm]X \subseteq \IN[/mm]
> mit [mm]\text{sup}(X)=\text{max}(X) \le N\,,[/mm] also [mm]X\,[/mm]
> beschränkte Teilmenge von [mm]\IN\,,[/mm] also [mm]X \in M\,.[/mm]
> Jetzt beweise Du mal 1.)...
Also Y [mm] \in [/mm] M, dann ist Y abzählbar und Y [mm] \subseteq \IN. [/mm] Sei [mm] Y=\bigcup_{y \in \IN}^{}M_Y.
[/mm]
Dann ist [mm] M_Y \in M_n [/mm] und für alle [mm] M_Y \in [/mm] Y ist [mm] M_Y [/mm] endlich.
Also ist Y eine abzählbare Vereinigung aus endlichen Mengen.
Kommt das so hin?
>
> > Jetzt müsste ich doch nur irgendwie zeigen, dass [mm]M_n[/mm]
> > abzählbar ist, denn dann könnte ich den Satz anwenden.
> > Nur wie zeige ich das?
>
> Das ist gar nicht so schwer. Beachte erstens:
> Wenn ich die Potenzmenge einer endlichen Menge betrachte,
> so besteht diese aus endlich vielen Teilmengen. Genauer
> gilt:
> Ist [mm]T\,[/mm] eine [mm]m\,[/mm]-elementige Menge, so hat [mm]\text{Pot}(T)[/mm]
> genau [mm]2^m[/mm] Elemente (es gibt also [mm]2^m[/mm] Teilmengen von [mm]T\,[/mm]).
>
> Nun gilt doch:
> [mm]M_n=\{A \subseteq \IN: \text{sup}(A) \le n\}=\{A \subseteq \IN: A \subseteq \{1,\dlots,n\}\}=\text{Pot}(\{1,\ldots,n\})\,.[/mm]
>
> [mm]\text{(}[/mm]Beweise das zweite Gleichheitszeichen, oder kurz:
> Begründe, dass gilt:
> [mm]\{A \subseteq \IN: \text{sup}(A) \le n\}=\text{Pot}(\{1,\ldots,n\}).[/mm]
Ist das nicht mehr oder weniger trivial. Also sup(A) [mm] \le [/mm] n, d.h. A ist maximal n-elementig oder kleiner. Da bei endlichen Mengen sup(A)=max(A) ist, ist A genau n-Elementig. (Allerdings finde ich letzteren Satz nicht in unseren Aufzeichnungen.)
Also A={1, ..., n}
> Also ist [mm]|M_n|=2^n\,,[/mm] weil [mm]|\{1,\ldots,n\}|=n\,.[/mm]
Du meinst hier wohl [mm] |Pot(M_n)|=2^n
[/mm]
> Somit ist
> [mm]M_n[/mm] sogar endlich (für jedes beliebige, feste [mm]n \in \IN[/mm]),
> insbesondere (höchstens) abzählbar. (Bemerkung: Im
> Gegensatz zu manch' anderem hier gesagten kenne ich es
> eigentlich so, dass man endliche oder abzählbar unendliche
> Mengen kurz einfach abzählbar nennt, um den Begriff
> "höchstens abzählbar" gar nicht zu benutzen. Ist aber
> auch ein wenig Geschmackssache oder
> Gebrauchs-/Gewöhnungssache...)
Ich verstehe jetzt aber nicht, warum du überhaupt die Potenzmenge einführst.
> P.S.:
> Gut ist jedenfalls, dass Du bei den [mm]M_n[/mm]-Definitionen ein
> [mm]\le[/mm] und kein [mm]=\,[/mm] stehen hast. Beim [mm]=\,[/mm] könnte man sicher
> auch begründen, warum diese Mengen endlich sind (denn wenn
> [mm]\tilde{M}_n:=\{A \subseteq \IN: \text{max}(A)=\text{sup}(A) \blue{=}n\}\,,[/mm]
> dann ist [mm]\tilde{M}_n \subseteq M_n[/mm]) - aber einen direkte
> Überlegung ohne diesen Umweg, warum [mm]\tilde{M}_n[/mm] höchstens
> abz. bzw. sogar endlich ist, wäre evtl. umständlich(er).
>
> P.P.S.:
> Vielleicht wäre es sogar günstiger, den Beweis direkt so
> anzugehen, dass man
> [mm]M_n:=\text{Pot}\{1,\ldots,n\}[/mm]
> definiert und dann
> [mm]M=\bigcup_{n \in \IN}M_n[/mm]
> beweist. Das erspart uns den
> kleinen Umweg, den Deine Definition der [mm]M_n[/mm] erfordert.
>
> Beachte übrigens, dass ich davon ausgehe, dass bei Euch [mm]0 \notin \IN[/mm]
> gilt. Ist bei Euch allerdings [mm]\IN=\IN_0=\IN \cup \{0\}\,,[/mm]
> so wäre natürlich
> [mm]M_n:=\{0,\ldots,n\}[/mm]
> zu setzen.
Das ist bei uns nicht anders.
> Gruß,
> Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:29 Mo 13.06.2011 | | Autor: | Marcel |
Hallo,
> Also ihr beide habt mich jetzt etwas verwirrt.
> Ist der Ansatz von Marcl jetzt richtig oder sind eure
> beiden Ansätze richtig?
ich bin davon überzeugt, dass Dein Ansatz richtig ist und ich ihn richtig zu Ende gedacht habe. Aber das heißt nicht, dass ich mich nicht irren kann!
> > Hallo,
> >
> > > Ich glaub ich hab die Aufgabe bei meinem 1. Versuch auch
> > > etwas falsch Verstanden, fällt mir gerade am Rande auf.
> > > > [mm]\bigcup_{n\in\IN}A_n[/mm] ist gar kein so schlechter
> > Anfang,
> > > > aber danach geht's in die Binsen.
> > >
> > > Dann mal ne andere Idee:
> > > Sei M:= [mm]\{A \subseteq \IN[/mm]: A ist abzählbar[mm]\}[/mm] und
> > > [mm]M_n:= \{A \subseteq \IN[/mm] A mit sup (A) [mm]\le[/mm] n[mm]\}[/mm]
> >
> > dann gilt auch [mm]M_n=\{A \subseteq \IN: \text{max}(A) \le n\}\,.[/mm]
> > Denn endliche nach oben beschränkte Mengen nehmen ihr
> > Supremum an, insbesondere nimmt jede endliche Teilmenge der
> > natürlichen Zahlen ihr Supremum an (und auch ihr Infimum).
> > Aber das nur nebenbei nochmal.
> >
> > > Also ist M die Menge aller endlichen Teilmengen von [mm]\IN[/mm] und
> > > [mm]M_n[/mm] ist die Menge aller nach oben beschränkten
> > > Teilmengen.
> >
> > Nein. [mm]M_n[/mm] ist nicht die Menge aller nach oben beschränkten
> > Teilmengen von [mm]\IN\,,[/mm] sondern die Menge aller nach oben
> > beschränkten Teilmengen von [mm]\IN\,,[/mm] so dass eine obere
> > Schranke einer Menge aus [mm]M_n[/mm] sicher [mm]\le n[/mm] ist.
> >
> > > Dann ist doch [mm]M=\bigcup_{n \in \IN}M_n[/mm]
> >
> > Das sollte in der Tat so sein. Beweis es doch mal: Du hast
> > zwei Sachen zu begründen:
> > 1.) Jedes Element aus [mm]M\,[/mm] muss auch in der Vereinigung
> > rechterhand liegen.
> >
> > UND
> >
> > 2.) Jedes Element aus der Vereinigung rechterhand muss auch
> > in [mm]M\,[/mm] liegen.
> >
> > Etwa zu 2.): Ist [mm]X \in \bigcup_{n \in \IN}M_n\,,[/mm] so
> > existiert ein [mm]N \in \IN[/mm] mit [mm]X \in M_N\,.[/mm]
> > Dann ist aber
> [mm]X \subseteq \IN[/mm]
> > mit [mm]\text{sup}(X)=\text{max}(X) \le N\,,[/mm] also [mm]X\,[/mm]
> > beschränkte Teilmenge von [mm]\IN\,,[/mm] also [mm]X \in M\,.[/mm]
>
>
> > Jetzt beweise Du mal 1.)...
> Also Y [mm]\in[/mm] M, dann ist Y abzählbar und Y [mm]\subseteq \IN.[/mm]
Ich habe gesehen, dass Du etwas bei der Definition von [mm] $M\,$ [/mm] vergessen hast: Nämlich, dass [mm] $M\,$ [/mm] das System aller endlichen (oder "beschränkten", das ist hier das gleiche!) (insbesondere abzählbaren) Teilmengen von [mm] $\IN\,$ [/mm] sein soll. Ansonsten geht hier alles schon schief!
> Sei [mm]Y=\bigcup_{y \in \IN}^{}M_Y.[/mm]
> Dann ist [mm]M_Y \in M_n[/mm] und
> für alle [mm]M_Y \in[/mm] Y ist [mm]M_Y[/mm] endlich.
> Also ist Y eine abzählbare Vereinigung aus endlichen
> Mengen.
>
> Kommt das so hin?
Ne. Also nochmal:
[mm] $$M:=\{A \subseteq \IN: A \text{ ist endlich}\}\,.$$
[/mm]
Dann ist klar, dass $M [mm] \subseteq \bigcup_{\ldots} \ldots\,,$ [/mm] siehe etwa meine Antwort. Umgekehrt folgt:
Ist $T [mm] \in M\,,$ [/mm] so ist $T [mm] \subseteq \IN$ [/mm] und nach oben beschränkt. Ist etwa $B [mm] \in \IN$ [/mm] eine obere Schranke für [mm] $T\,$ [/mm] (d.h. $|t|=t [mm] \le [/mm] B$ für alle $t [mm] \in T\,,$ [/mm] - allerdings muss [mm] $B\,$ [/mm] nicht die kleinste obere Schranke sein), so folgt $T [mm] \in M_{B} \subseteq \bigcup_{n \in \IN}M_n\,.$
[/mm]
> > > Jetzt müsste ich doch nur irgendwie zeigen, dass [mm]M_n[/mm]
> > > abzählbar ist, denn dann könnte ich den Satz anwenden.
> > > Nur wie zeige ich das?
> >
> > Das ist gar nicht so schwer. Beachte erstens:
> > Wenn ich die Potenzmenge einer endlichen Menge
> betrachte,
> > so besteht diese aus endlich vielen Teilmengen. Genauer
> > gilt:
> > Ist [mm]T\,[/mm] eine [mm]m\,[/mm]-elementige Menge, so hat [mm]\text{Pot}(T)[/mm]
> > genau [mm]2^m[/mm] Elemente (es gibt also [mm]2^m[/mm] Teilmengen von [mm]T\,[/mm]).
> >
> > Nun gilt doch:
> > [mm]M_n=\{A \subseteq \IN: \text{sup}(A) \le n\}=\{A \subseteq \IN: A \subseteq \{1,\dlots,n\}\}=\text{Pot}(\{1,\ldots,n\})\,.[/mm]
>
> >
> > [mm]\text{(}[/mm]Beweise das zweite Gleichheitszeichen, oder kurz:
> > Begründe, dass gilt:
> > [mm]\{A \subseteq \IN: \text{sup}(A) \le n\}=\text{Pot}(\{1,\ldots,n\}).[/mm]
>
> Ist das nicht mehr oder weniger trivial.
Das heißt nur, dass der Beweis so kurz ist, dass man ihn fast ohne aufzuschreiben durchgehen kann. Was trivial ist oder nicht, hängt eigentlich auch von vielen Sachen ab. Ganz trivial ist es meiner Ansicht nach nicht (wenn zugleich trotzdem in einem gewissen Sinne einfach).
> Also sup(A) [mm]\le[/mm] n,
> d.h. A ist maximal n-elementig oder kleiner.
Was willst Du hier machen? Du strukturierst zu wenig. Also: Womit Du angefangen hast, ist: Du willst zeigen, dass [mm] $\{A \subseteq \IN:\;\text{sup}(A) \le n\} \subseteq \text{Pot}\{1,\ldots,n\}$ [/mm] gilt.
> Da bei
> endlichen Mengen sup(A)=max(A) ist, ist A genau
> n-Elementig. (Allerdings finde ich letzteren Satz nicht in
> unseren Aufzeichnungen.)
Weil es auch Unsinn ist. Es ist etwa [mm] $A:=\{2,3,5\} \subseteq \IN$ [/mm] mit [mm] $\text{sup}(A) \le 7\,,$ [/mm] aber [mm] $A=\{1,2,3,4,5,6,7\}$ [/mm] ist dann Quatsch, weil ja [mm] $\{2,3,5\} \not= \{1,2,3,4,5,6,7\}$ [/mm] ist.
Ebenso gilt auch [mm] $\text{sup}(A)=\text{max}(A)=5\,,$ [/mm] aber auch hier ist [mm] $\{2,3,5\} \not=\{1,2,3,4,5\}\,.$
[/mm]
> Also A={1, ..., n}
Nein. Also nochmal: Ist $A [mm] \subseteq \IN$ [/mm] mit [mm] $\text{sup}(A) \le n\,,$ [/mm] so weißt Du nur, dass $A [mm] \subseteq \IN$ [/mm] ist und für alle $a [mm] \in [/mm] A$ gilt, dass $a [mm] \le n\,.$ [/mm] Dann muss aber auch $A [mm] \subseteq \{1,\ldots,n\}$ [/mm] gelten (jedes $a [mm] \in [/mm] A$ erfüllt ja $a [mm] \in \IN$ [/mm] und wäre ein [mm] $a_0 \in [/mm] A$ vorhanden, dass [mm] $a_0 \notin \{1,\ldots,n\}$ [/mm] erfüllte, so wäre [mm] $a_0 [/mm] > n$ und damit [mm] $\text{sup}(A) \ge a_0 [/mm] > [mm] n\,.$ [/mm] Widerpruch!)
Was wir bisher gesehen haben, ist: [mm] $\{A \subseteq \IN: \text{sup}(A) \le n\} \subseteq \text{Pot}(\{1,\ldots,n\})\,.$
[/mm]
Zu beweisen hast Du nun noch die umgekehrte Teilmengenbeziehung (beachte: Für zwei Mengen [mm] $R,S\,$ [/mm] gilt [mm] $R=S\,$ [/mm] genau dann, wenn sowohl $R [mm] \subseteq [/mm] S$ als auch $S [mm] \subseteq [/mm] R$ gilt).
> > Also ist [mm]|M_n|=2^n\,,[/mm] weil [mm]|\{1,\ldots,n\}|=n\,.[/mm]
> Du meinst hier wohl [mm]|Pot(M_n)|=2^n[/mm]
Nein. Aber ich denke, das einzige, was hier passiert war, ist, dass Du mit den Bezeichnungen durcheinandergekommen bist. Wir wissen:
[mm] $$|\{1,\ldots,n\}|=n$$
[/mm]
und daher folgt
[mm] $$|\text{Pot}(\{1,\ldots,n\})|=2^n\,.$$
[/mm]
Oben war NICHT [mm] $\red{M_n=\{1,\ldots,n\}}$ [/mm] gesetzt, sondern
[mm] $$M_n:=\{A \subseteq \IN:\;\text{sup}(A) \le n\}$$
[/mm]
war definiert und wir hatten nachgewiesen, dass dann
[mm] $$\blue{M_n=\text{Pot}(\{1,\ldots,n\})}$$
[/mm]
gilt.
> > Somit ist
> > [mm]M_n[/mm] sogar endlich (für jedes beliebige, feste [mm]n \in \IN[/mm]),
> > insbesondere (höchstens) abzählbar. (Bemerkung: Im
> > Gegensatz zu manch' anderem hier gesagten kenne ich es
> > eigentlich so, dass man endliche oder abzählbar unendliche
> > Mengen kurz einfach abzählbar nennt, um den Begriff
> > "höchstens abzählbar" gar nicht zu benutzen. Ist aber
> > auch ein wenig Geschmackssache oder
> > Gebrauchs-/Gewöhnungssache...)
>
> Ich verstehe jetzt aber nicht, warum du überhaupt die
> Potenzmenge einführst.
Das hast Du hier noch nicht verstanden, weil Du mit den Bezeichnungen verwirrt warst, denke ich.
> > P.S.:
> > Gut ist jedenfalls, dass Du bei den [mm]M_n[/mm]-Definitionen
> ein
> > [mm]\le[/mm] und kein [mm]=\,[/mm] stehen hast. Beim [mm]=\,[/mm] könnte man sicher
> > auch begründen, warum diese Mengen endlich sind (denn wenn
> > [mm]\tilde{M}_n:=\{A \subseteq \IN: \text{max}(A)=\text{sup}(A) \blue{=}n\}\,,[/mm]
> > dann ist [mm]\tilde{M}_n \subseteq M_n[/mm]) - aber einen direkte
> > Überlegung ohne diesen Umweg, warum [mm]\tilde{M}_n[/mm] höchstens
> > abz. bzw. sogar endlich ist, wäre evtl. umständlich(er).
> >
> > P.P.S.:
> > Vielleicht wäre es sogar günstiger, den Beweis direkt
> so
> > anzugehen, dass man
> > [mm]M_n:=\text{Pot}\{1,\ldots,n\}[/mm]
> > definiert und dann
> > [mm]M=\bigcup_{n \in \IN}M_n[/mm]
> > beweist. Das erspart uns den
> > kleinen Umweg, den Deine Definition der [mm]M_n[/mm] erfordert.
> >
> > Beachte übrigens, dass ich davon ausgehe, dass bei Euch [mm]0 \notin \IN[/mm]
> > gilt. Ist bei Euch allerdings [mm]\IN=\IN_0=\IN \cup \{0\}\,,[/mm]
> > so wäre natürlich
> > [mm]M_n:=\{0,\ldots,n\}[/mm]
> > zu setzen.
> Das ist bei uns nicht anders.
> > Gruß,
> > Marcel
>
Gruß,
Marcel
|
|
|
| |
|
Zunächst kurz zu den Begriffen:
Eine Menge heißt endlich, wenn sie nur endlich viele Elemente enthält. Beispiel: Alle Zahlen von 1 bis 10 000, alle (gekürzten) Brüche mit positiven Zählern und Nennern, bei denen Summe aus Zähler und Nenner < 4000 ist.
Eine Menge heißt unendlich, wenn sie unendlich viele Zahlen enthält wie z.B. [mm] \IN, \IR, \IQ [/mm] oder das Intervall [0|1].
Eine Menge heißt abzählbar, wenn man alle ihre Elemente in irgendeiner Weise hintereinander anordnen kann, ohne dass dabei Elemente fehlen. Somit sind alle endlichen Mengen abzählbar (genauer dann: endlich abzählbar), viele unendliche auch (genauer dann: unendlich abzählbar) wie z.B. [mm] \IN [/mm] und [mm] \IQ, [/mm] nicht aber [mm] \IR. [/mm]
[mm] \IR [/mm] ist überabzählbar, das bedeutet auf jeden Fall unendlich, aber auch, dass es keine Anordnung gibt, bei der man alle Zahlen der Reihe nach hinschreiben kann. Das liegt aber nicht daran, dass das Intervall [0|1] schon unendlich viele Zahlen enthält und die nächsten Intervalle auch! Das Intervall [0|1] enthält nämlich unendlich viele Elemente aus [mm] \IQ, [/mm] das Intervall [1|2] auch usw., und trotzdem ist [mm] \IQ [/mm] abzählbar, [mm] \IR [/mm] aber nicht. Es liegt auch nicht daran, dass [mm] \IQ [/mm] geordnet ist und [mm] \IR [/mm] nicht: Von jeder reellen Zahl kann man sagen, ob sie größer oder kleiner als eine andere ist.
Deshalb war es ja auch eine Überraschung, als Georg Kantor zeigen konnte, dass - egal wie man die Zahlen aus [mm] \IR [/mm] aufschreibt - in jeder Liste immer Zahlen fehlen müssen (s.u.).
-----------------------------------------------------------
Nun zu deiner Aufgabe: Du musst einfach ein Verfahren finden, das dir garantiert, dass beim Erstellen einer Liste aller endlichen Mengen aus [mm] \IN [/mm] jede Menge irgendwann vorkommt. Es ist nicht erforderlich, zu sagen, auf welchem Platz diese Menge steht, sondern nur, dass jede Menge irgendwann auftaucht.
Hierzu folgender Lösungsvorschlag:
Jede endliche Teilmenge aus [mm] \IN [/mm] hat ein größtes Element.
Deshalb stellst du nun eine Liste zusammen, die folgende Grobordnung hat:
Zuerst kommen alle Teilmengen aus [mm] \IN, [/mm] deren größtes Element 1 ist. Danach kommen alle Teilmengen aus [mm] \IN, [/mm] deren größtes Element 2 ist. Danach kommen alle Teilmengen aus [mm] \IN, [/mm] deren größtes Element 3 ist. Danach kommen alle Teilmengen aus [mm] \IN, [/mm] deren größtes Element 4 ist. Danach ...
Deine Liste sieht dann so aus:
{1},
{2},{1,2},
{3},{1,3},{2,3},{1,2,3},
{4},{1,4},{2,4},{3,4},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4},
...
Jede Zeile ist doppelt so lang wie die vorherige, jede endliche Teilmenge von n kommt irgendwann einmal vor,
also ist die Menge der endlichen Teilmengen aus [mm] \IN [/mm] abzählbar.
Das ist schon die Lösung ohne komplizierte Schreibweisen.
Wichtig:
Jede der obigen Zeilen hat eine endliche Länge (weil wir nur endliche Teilmengen betrachten), so dass man irgendwann zur nächsten Zeile kommt. Wären auch unendlich viele unendliche Teilmengen dabei, gäbe es kein Verfahren, alles entsprechend anzuordnen, die Geschichte wäre schon überabzählbar.
----------------------------------------------------------
Hier der einfachste Beweis für die Überabzählbarkeit von [mm] \IR. [/mm] Ich beschränke mich auf das Intervall von [0|1].
Annahmen: [0|1] wäre abzählbar. Dann könnte man eine Tabelle aller Elemente aus [0|1] aufschreiben, und jede Zahl daraus müsste irgendwo auftauchen. Als Beispiel zur Erläuterung nehme ich die Tabelle
0, [mm] \red{1} [/mm] 3 3 4 5 6 0 0 0 0 0 0 0 0 0 0 ...
0, 7 [mm] \red{4} [/mm] 5 7 5 6 2 3 2 0 3 5 8 2 3 5 ...
0, 1 8 [mm] \red{9} [/mm] 2 3 5 8 3 5 2 9 0 7 5 3 5 ...
0, 7 3 8 [mm] \red{1} [/mm] 5 8 5 8 4 7 6 3 7 5 1 3 ...
0, 3 5 7 3 [mm] \red{4} [/mm] 4 5 2 3 5 5 3 2 3 4 7 ...
0, 5 7 2 5 6 [mm] \red{5} [/mm] 2 5 2 8 2 2 5 8 2 5 3 8 2 ...
usw.
In dieser Tabelle suche ich nun die Zahl aus [0|1], die folgende Eigenschaft hat: Die n-te Ziffer hinterm Komma heißt 1, außer dann, wenn die n-te Zahl in obiger Tabelle
auch eine 1 hat - dann soll die Ziffer 0 heißen. In meinem Beispiel wäre das die Zahl, die mit
0, 0 1 1 0 1 1 ...
beginnt ( die erste Zahl der Tabelle hat an der ersten, die vierte an der vierten Stelle eine 1, deshalb hat die von mir konstruierte Zahl dort eine 0).
Diese Zahl kann nun gar nicht in der Tabelle vorkommen: Es kann nicht die erste oder vierte sein, weil die an der ersten bzw. vierten Stelle eine 1, meine Zahl aber eine 0 hat. Es kann auch nicht die 2., 3., 5. oder 6. sein, weil meine Zahl dort jeweils eine 1 hat, die Zahlen in der Tabelle aber gerade nicht usw.
Zu jeder Tabelle kann ich also eine Zahl angeben, die auf jeden Fall dort fehlen muss. Einwand: Dann kann man die fehlende Zahl ja in die Tabelle irgendwo einfügen. Entgegnung. Dann hat man eine andere Tabelle, und zu der kann ich wieder eine Zahl basteln, die auf jeden Fall fehlt.
[0|1] ist somit überabzählbar.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:39 Mo 13.06.2011 | | Autor: | Sup |
>
> -----------------------------------------------------------
>
> Nun zu deiner Aufgabe: Du musst einfach ein Verfahren
> finden, das dir garantiert, dass beim Erstellen einer Liste
> aller endlichen Mengen aus [mm]\IN[/mm] jede Menge irgendwann
> vorkommt. Es ist nicht erforderlich, zu sagen, auf welchem
> Platz diese Menge steht, sondern nur, dass jede Menge
> irgendwann auftaucht.
>
> Hierzu folgender Lösungsvorschlag:
>
> Jede endliche Teilmenge aus [mm]\IN[/mm] hat ein größtes Element.
> Deshalb stellst du nun eine Liste zusammen, die folgende
> Grobordnung hat:
>
> Zuerst kommen alle Teilmengen aus [mm]\IN,[/mm] deren größtes
> Element 1 ist. Danach kommen alle Teilmengen aus [mm]\IN,[/mm] deren
> größtes Element 2 ist. Danach kommen alle Teilmengen aus
> [mm]\IN,[/mm] deren größtes Element 3 ist. Danach kommen alle
> Teilmengen aus [mm]\IN,[/mm] deren größtes Element 4 ist. Danach
> ...
>
> Deine Liste sieht dann so aus:
>
> {1},
> {2},{1,2},
> {3},{1,3},{2,3},{1,2,3},
> {4},{1,4},{2,4},{3,4},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4},
> ...
> Jede Zeile ist doppelt so lang wie die vorherige, jede
> endliche Teilmenge von n kommt irgendwann einmal vor,
> also ist die Menge der endlichen Teilmengen aus [mm]\IN[/mm]
> abzählbar.
>
Das ist mir alles klar und man sieht eig auch, dass jede Teilmenge irgendwann man drankommt, aber warum ist das konrket so. Wie kann man das begründen?
> Das ist schon die Lösung ohne komplizierte Schreibweisen.
>
> Wichtig:
> Jede der obigen Zeilen hat eine endliche Länge (weil wir
> nur endliche Teilmengen betrachten), so dass man irgendwann
> zur nächsten Zeile kommt. Wären auch unendlich viele
> unendliche Teilmengen dabei, gäbe es kein Verfahren, alles
> entsprechend anzuordnen, die Geschichte wäre schon
> überabzählbar.
>
>
> ----------------------------------------------------------
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:29 Mo 13.06.2011 | | Autor: | sangham |
> > Jede endliche Teilmenge aus [mm]\IN[/mm] hat ein größtes
> Element.
> > Deshalb stellst du nun eine Liste zusammen, die
> folgende
> > Grobordnung hat:
> >
> > Zuerst kommen alle Teilmengen aus [mm]\IN,[/mm] deren größtes
> > Element 1 ist. Danach kommen alle Teilmengen aus [mm]\IN,[/mm]
> deren
> > größtes Element 2 ist. Danach kommen alle Teilmengen
> aus
> > [mm]\IN,[/mm] deren größtes Element 3 ist. Danach kommen alle
> > Teilmengen aus [mm]\IN,[/mm] deren größtes Element 4 ist.
> Danach
> > ...
> >
> > Deine Liste sieht dann so aus:
> >
> > {1},
> > {2},{1,2},
> > {3},{1,3},{2,3},{1,2,3},
> >
> {4},{1,4},{2,4},{3,4},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4},
> > ...
> > Jede Zeile ist doppelt so lang wie die vorherige, jede
> > endliche Teilmenge von n kommt irgendwann einmal vor,
> > also ist die Menge der endlichen Teilmengen aus [mm]\IN[/mm]
> > abzählbar.
> >
> Das ist mir alles klar und man sieht eig auch, dass jede
> Teilmenge irgendwann man drankommt, aber warum ist das
> konrket so. Wie kann man das begründen?
Hi, dann ist es wohl doch nicht "alles klar"... 
Warum kommen alle Teilmengen vor? Antwort:
Die obige Lösung gibt eine Ordnungsvorschrift für alle endlichen Teilmengen an.
Das ausschlaggebende Argument 1 ist
Jede endliche Teilmenge aus [mm]\IN[/mm] hat ein größtes
> Element.
Das ist Fakt und das muss man einsehen.
Ausschlaggebendes Argument 2 ist, dass die Teilmengen einer endlichen Menge ebenfalls endlich sind. (Die Menge mit der größten Anzahl von Elementen ist in der n-ten Zeile {1,...,n} und steht oben jeweils am Ende der Zeile, davor sind alle Teilmengen davon aufgelistet).
Daraus folgt, dass die Elemente in jeder Zeile endlich sind.
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:40 Mo 13.06.2011 | | Autor: | Marcel |
Hallo,
> > > Jede endliche Teilmenge aus [mm]\IN[/mm] hat ein größtes
> > Element.
> > > Deshalb stellst du nun eine Liste zusammen, die
> > folgende
> > > Grobordnung hat:
> > >
> > > Zuerst kommen alle Teilmengen aus [mm]\IN,[/mm] deren
> größtes
> > > Element 1 ist. Danach kommen alle Teilmengen aus
> [mm]\IN,[/mm]
> > deren
> > > größtes Element 2 ist. Danach kommen alle
> Teilmengen
> > aus
> > > [mm]\IN,[/mm] deren größtes Element 3 ist. Danach kommen
> alle
> > > Teilmengen aus [mm]\IN,[/mm] deren größtes Element 4 ist.
> > Danach
> > > ...
> > >
> > > Deine Liste sieht dann so aus:
> > >
> > > {1},
> > > {2},{1,2},
> > > {3},{1,3},{2,3},{1,2,3},
> > >
> > {4},{1,4},{2,4},{3,4},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4},
> > > ...
> > > Jede Zeile ist doppelt so lang wie die vorherige,
> jede
> > > endliche Teilmenge von n kommt irgendwann einmal
> vor,
> > > also ist die Menge der endlichen Teilmengen aus [mm]\IN[/mm]
> > > abzählbar.
> > >
>
> > Das ist mir alles klar und man sieht eig auch, dass jede
> > Teilmenge irgendwann man drankommt, aber warum ist das
> > konrket so. Wie kann man das begründen?
>
> Hi, dann ist es wohl doch nicht "alles klar"...
>
> Warum kommen alle Teilmengen vor? Antwort:
> Die obige Lösung gibt eine Ordnungsvorschrift für alle
> endlichen Teilmengen an.
> Das ausschlaggebende Argument 1 ist
> Jede endliche Teilmenge aus [mm]\IN[/mm] hat ein größtes
> > Element.
> Das ist Fakt und das muss man einsehen.
man kann es beweisen. Der Beweis sollte in Analogie zum Beweis von
![[]](/images/popup.gif) Satz 3.20
(Wohlordnungsprinzip von [mm] $\IN$) [/mm] durchführbar sein.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:35 Mo 13.06.2011 | | Autor: | sangham |
> > Jede endliche Teilmenge aus [mm]\IN[/mm] hat ein größtes
> > > Element.
> > Das ist Fakt und das muss man einsehen.
>
> man kann es beweisen. Der Beweis sollte in Analogie zum
> Beweis von
>
> Satz 3.20
>
> (Wohlordnungsprinzip von [mm]\IN[/mm]) durchführbar sein.
Es folgt direkt daraus, dass [mm] \IN [/mm] wohl-geordnet ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:18 Mo 13.06.2011 | | Autor: | Marcel |
Hallo,
> > > Jede endliche Teilmenge aus [mm]\IN[/mm] hat ein größtes
> > > > Element.
> > > Das ist Fakt und das muss man einsehen.
> >
> > man kann es beweisen. Der Beweis sollte in Analogie zum
> > Beweis von
> >
> > Satz 3.20
>
> >
> > (Wohlordnungsprinzip von [mm]\IN[/mm]) durchführbar sein.
>
> Es folgt direkt daraus, dass [mm]\IN[/mm] wohl-geordnet ist.
ich bin davon ausgegangen, dass dieses Wissen noch nicht vorhanden ist.
Warum das direkt aus Satz 3.20 folgen soll, weiß ich gerade nicht. Was aber gehen sollte:
Nehmen wir an, dass wir eine nach oben beschränkte Teilmenge $A [mm] \subseteq \IN$ [/mm] haben (bzw. kurz: beschränkte, was hier das gleiche ist). Sei [mm] $a:=\sup(A) \in \IR\,.$ [/mm] Dann betrachten wir [mm] $B:=\IN \setminus \{1,\ldots,n\}\,,$ [/mm] wobei $n [mm] \in \IN$ [/mm] die größte ganze Zahl [mm] $\le\; [/mm] a$ sei. Dieses [mm] $B\,$ [/mm] hat ein Infimum, was wegen Satz 3.20 gleichzeitig Minimum ist. Das ist eine obere Schranke für [mm] $A\,.$ [/mm] Jetzt zeigt man sicher einfach, dass dieses Infimum bzw. Minimum von [mm] $B\,$ [/mm] gleich [mm] $\text{sup}(A)+1$ [/mm] ist. Dann ist [mm] $\text{inf}(B)-1$ [/mm] obere Schranke für [mm] $A\,$ [/mm] und wegen des Wohlordnungssatzes ist [mm] $\inf(B)$ [/mm] eine natürliche Zahl, also ist auch [mm] $\inf(B)-1$ [/mm] eine solche. Im Prinzip ist man dann auch schon fertig. Wenngleich hier sicher auch noch ein, zwei kleine Argumente meinerseits anzufügen wären.
P.S.:
Ich neige oft dazu, ein wenig zu kompliziert zu denken. Wenn es "noch schneller aus dem Wohlordungssatz 3.20 folgt", dann bitte gerne ergänzen!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:54 Mo 13.06.2011 | | Autor: | sangham |
Hi,
das kann man sicher so argumentieren, aber das Wort kompliziert ist schon in meinem Kopf aufgetaucht... aber gut
Die Menge der natürlichen Zahlen ist ja schließlich definiert
N = {1,2,3,...,n,n+1,...}
ich übersetze mal einfach ein bisschen ins Anschauliche, ok?
> > > > Jede endliche Teilmenge aus [mm]\IN[/mm] hat ein größtes
> > > > > Element.
> > > > Das ist Fakt und das muss man einsehen.
> > >
> > > man kann es beweisen. Der Beweis sollte in Analogie zum
> > > Beweis von
> > >
> > > Satz 3.20
>
> >
> > >
> > > (Wohlordnungsprinzip von [mm]\IN[/mm]) durchführbar sein.
> >
> > Es folgt direkt daraus, dass [mm]\IN[/mm] wohl-geordnet ist.
>
> ich bin davon ausgegangen, dass dieses Wissen noch nicht
> vorhanden ist.
ah, sorry, war mir nicht klar. (Das folgt im grunde aus der Definition der natürlichen Zahlen --> Piano Axiom hiess das glaub ich, aber evtl. wird das auch überall verschieden gehandhabt, wie man Zahlen einführt meine ich)
> Warum das direkt aus Satz 3.20 folgen soll, weiß ich
> gerade nicht. Was aber gehen sollte:
> Nehmen wir an, dass wir eine nach oben beschränkte
> Teilmenge [mm]A \subseteq \IN[/mm] haben (bzw. kurz: beschränkte,
> was hier das gleiche ist). Sei [mm]a:=\sup(A) \in \IR\,.[/mm] Dann
> betrachten wir [mm]B:=\IN \setminus \{1,\ldots,n\}\,,[/mm] wobei [mm]n \in \IN[/mm]
> die größte ganze Zahl [mm]\le\; a[/mm] sei.
Das bedeutet dann logischer weise n = a, und B = {a+1, a+2,....} unabhängig davon wie A genau aussieht. Aber man kann es sicher auch so schön abstrakt wie oben formulieren.
Ich vermute mal, dass meine Schwierigkeiten, das Problem zu verstehen mit dem unbekannten Hintergrundwissen zu tun haben. Wenn ich das jetzt irgend woraus hätte schließen können/müssen, möchte ich mich dafür entschuldigen. Gruss
> Dieses [mm]B\,[/mm] hat ein
> Infimum, was wegen Satz 3.20 gleichzeitig Minimum ist. Das
> ist eine obere Schranke für [mm]A\,.[/mm] Jetzt zeigt man sicher
> einfach, dass dieses Infimum bzw. Minimum von [mm]B\,[/mm] gleich
> [mm]\text{sup}(A)+1[/mm] ist. Dann ist [mm]\text{inf}(B)-1[/mm] obere
> Schranke für [mm]A\,[/mm] und wegen des Wohlordnungssatzes ist
> [mm]\inf(B)[/mm] eine natürliche Zahl, also ist auch [mm]\inf(B)-1[/mm] eine
> solche. Im Prinzip ist man dann auch schon fertig.
> Wenngleich hier sicher auch noch ein, zwei kleine Argumente
> meinerseits anzufügen wären.
>
> P.S.:
> Ich neige oft dazu, ein wenig zu kompliziert zu denken.
> Wenn es "noch schneller aus dem Wohlordungssatz 3.20
> folgt", dann bitte gerne ergänzen!
>
>
> Gruß,
> Marcel
|
|
|
| |
|
Bevor sich hier alle im Dickicht von unendlichen Anordnungen mit Suprema und Wohlordnungssatz verstricken, gebe ich jetzt mal an, wann wie wo welche Menge aufgeschrieben werden kann.
Du kennst sicher die Dualzahlen und weißt, dass man jede natürliche Zahl als Dualzahl schreiben kann. Das tue ich jetzt mal der Reihe nach: Ich zähle von 0 bis unendlich die natürlichen Zahlen ab und bringe dann jede (!) mit genau einer (!) endlichen Teilmege bijektiv (!) in Verbindung.
000000000000000000 [mm] \hat= [/mm] {}
000000000000000001 [mm] \hat= [/mm] {1}
000000000000000010 [mm] \hat= [/mm] {2}
000000000000000011 [mm] \hat= [/mm] {2,1}
000000000000000100 [mm] \hat= [/mm] {3}
000000000000000101 [mm] \hat= [/mm] {3,1}
000000000000000110 [mm] \hat= [/mm] {3,2}
000000000000000111 [mm] \hat= [/mm] {3,2,1}
usw.
001011101010001010 [mm] \hat= [/mm] {16,14,13,12,10,8,4,2}
mit anderen Worten: Die zugehörige Menge enthält genau dann die natürliche Zahl i, wenn die Dualzahl an der i-ten Stelle eine 1 hat, sonst nicht.
Damit werden alle endlichen Teilmengen erfasst und in eine Dualzahl übertragbar, die gleichzeitig ihre Position in der Abzählung angibt. Das ist die vermutlich einfachste Lösung der Aufgabenstellung.
--------------------------------------------------------
Deine Frage, woher man weiß, dass die jeweilige Zeile in meinem Vorschlag endlich ist, kann so beantwortet werden:
Du weißt sicher, dass die Potenzmenge der ersten n Natürlichen Zahlen aus [mm] 2^n [/mm] Teilmengen besteht. Wenn du aus allen Teilmengen, die die Zahl n selber enthalten, n entfernst, bekommst du genau die restlichen, die n nicht enthalten. Also gibt es [mm] 2^n/2 [/mm] Teilmengen, die n enthalten, die n-te Reihe hat somit [mm] 2^n/2 [/mm] Teilmengen.
Beispiel: Alle endlichen Teilmengen von [mm] \IN, [/mm] die als maximales Element 5 enthalten:
Potenzmenge von {1,2,3,4,5} besteht aus
{},{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4} (das sind alle ohne 5, jetzt packe ich in jede der Reihe nach noch die 5:
{5},{1,5},{2,5},{3,5},{4,5},{1,2,5},{1,3,5},{1,4,5},{2,3,5},{2,4,5},{3,4,5},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5},{1,2,3,4,5}.
Es gibt genau [mm] 2^5/2 [/mm] = 16 Teilmengen aus [mm] \IN, [/mm] die die 5 als maximales Element haben.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:56 Di 14.06.2011 | | Autor: | sangham |
> Bevor sich hier alle im Dickicht von unendlichen
> Anordnungen mit Suprema und Wohlordnungssatz verstricken,
> gebe ich jetzt mal an, wann wie wo welche Menge
> aufgeschrieben werden kann.
>
> Du kennst sicher die Dualzahlen und weißt, dass man jede
> natürliche Zahl als Dualzahl schreiben kann. Das tue ich
> jetzt mal der Reihe nach: Ich zähle von 0 bis unendlich
> die natürlichen Zahlen ab und bringe dann jede (!) mit
> genau einer (!) endlichen Teilmege bijektiv (!) in
> Verbindung.
>
> 000000000000000000 [mm]\hat=[/mm] {}
> 000000000000000001 [mm]\hat=[/mm] {1}
> 000000000000000010 [mm]\hat=[/mm] {2}
> 000000000000000011 [mm]\hat=[/mm] {2,1}
> 000000000000000100 [mm]\hat=[/mm] {3}
> 000000000000000101 [mm]\hat=[/mm] {3,1}
> 000000000000000110 [mm]\hat=[/mm] {3,2}
> 000000000000000111 [mm]\hat=[/mm] {3,2,1}
> usw.
> 001011101010001010 [mm]\hat=[/mm] {16,14,13,12,10,8,4,2}
>
> mit anderen Worten: Die zugehörige Menge enthält genau
> dann die natürliche Zahl i, wenn die Dualzahl an der i-ten
> Stelle eine 1 hat, sonst nicht.
>
> Damit werden alle endlichen Teilmengen erfasst und in eine
> Dualzahl übertragbar, die gleichzeitig ihre Position in
> der Abzählung angibt. Das ist die vermutlich einfachste
> Lösung der Aufgabenstellung.
Ja, das ist schick. Es ist bei Abzählbarkeitsbeweisen ohnehin immer empfehlenswert eine konkrete Abbildung hinzuschreiben. Damit hat man dann ganz klar bewiesen, dass es eine gibt
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:31 Di 14.06.2011 | | Autor: | SEcki |
> Zeigen sie, dass die Menge der endlichen Teilmengen von [mm]\IN[/mm]
> abzählbar ist.
Alternativbeweis (weil ich ihn schön finde): Sie [mm]p:\IN\to P[/mm] eine Abzählung der Primzahlen (die abzählbar unendlich sind!). Sei T die Menge der endlichen Teilmengen, dann ist die Abbildung [mm]r:T\to \IN,t \mapsto \prod_{i\in t}p(i)[/mm] wegen der Eindeutigkeit der Primzahlzerlegung injektiv. Fertig!
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:35 Di 14.06.2011 | | Autor: | reverend |
Hallo SEcki,
schicke Lösung!
![[hut]](/images/smileys/hut.gif "[hut]")
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:33 Mi 15.06.2011 | | Autor: | Marcel |
Hallo Secki,
> > Zeigen sie, dass die Menge der endlichen Teilmengen von [mm]\IN[/mm]
> > abzählbar ist.
>
> Alternativbeweis (weil ich ihn schön finde): Sie Sei [mm]p:\IN\to P[/mm]
> eine Abzählung der Primzahlen (die abzählbar unendlich
> sind!). Sei T die Menge der endlichen Teilmengen, dann ist
> die Abbildung [mm]r:T\to \IN,t \mapsto \prod_{i\in t}p(i)[/mm] wegen
> der Eindeutigkeit der Primzahlzerlegung injektiv. Fertig!
>
> SEcki
finde ich auch sehr schön. Insbesondere ordnet man jeder Teilmenge eine natürliche Zahl zu (das Produkt über den den Elementen der Teilmenge jeweils zugeordneten Primzahlen), hat also sogar eine konkrete injektive Abbildung - wie ich finde ziemlich geschickt - angegeben. Ich finde zwar, dass der Satz über die Eindeutigkeit der Primzahlzerlegung schon ein etwas stärkeres Geschütz ist (den Beweis, den ich mal in der Zahlentheorie kennengelernt hatte, war jedenfalls schon etwas, wenn auch nicht zu, "anstrengend"), aber jeder Schüler lernt diesen Satz relativ schnell zu akzeptieren. Von daher wäre der Beweis meines Erachtens nach sogar für Schüler "akzeptabel".
Gruß,
Marcel
|
|
|
|
