Beweis der Gleichmächtigkeit < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:28 So 03.09.2006 | | Autor: | jbulling |
| Aufgabe | Es handelt sich dabei eigentlich nicht um eine konkret gestellte Aufgabe, sondern nur um eine Frage, die mir in einem anderen Zusammenhang kam.
Konkret geht es um ein Kriterium für den Beweis der gleichmächtigekeit endlicher Mengen. |
Normalerweise beweist man die Gleichmächtigkeit zweier Mengen dadurch, dass man eine bijektive Abbildung zwischen diesen Mengen (im Folgenden A und B genannt) findet.
Für endliche Mengen habe ich mir überlegt, dass es ausreichen müsste, wenn man eine injektive Funktion A->B findet und eine zweite injektive Funktion B->A.
Ich habe dafür folgendendermaßen geschlossen und bin mir jetzt nicht mehr so ganz sicher, ob ich das überhaupt so darf und warum diese Schlussweise bei unendlichen Mengen (zumindest bie überabzählbaren) nicht anwendbar ist. Also hier die Schlussweise:
Beennen wir die injektive Funktion A->B als f und die injektive Funktion B->A als g, dann gilt:
f(A) [mm] \subset [/mm] B also | f(A) | [mm] \le [/mm] | B |
und wegen der Injektivität gilt auch | f(A) | = | A | und insgesamt also | A | [mm] \le [/mm] | B |
genauso kann man von g(B) schließen:
g(B) [mm] \subset [/mm] A also | g(B) | und genauso wie oben letztendlich | B | [mm] \le [/mm] | A |.
Kombiniert also | A | = | B |
Dass aus A [mm] \subset [/mm] B folgt | A | [mm] \le [/mm] | B | folgt ja schon daraus, dass es eine injektive Abbildung auf eine Teilmenge von B gibt (die identitätsabbildung).
Im Prinzip müsste man auch B'=B [mm] \setminus [/mm] A setzen können, so dass gilt:
B=A [mm] \cup [/mm] B'
und es ist auch klar, dass immer gelten muss |B'| [mm] \ge [/mm] 0, denn es gibt keine Mengen mit einer negativen Anzahl von Elementen.
Weil A und B' disjunkt sind, muss gelten:
| B |=| A | + | B'|
Hier vermute ich aber schon das erste Problem, wenn A und B' nicht beide endlich sind. Stimmt das jetzt noch?
Ich habe mir überlegt, dass die Funktion | | eine Abbildung von einer Menge auf die Menge der Natürlichen Zahlen mit 0 ist und man also implizit annimmt, dass | | eine natürliche Zahl ist, was ja z.B. bei IR nicht der Fall ist.
Dafür dass die Schlussweise von oben, dass wenn man von einer Menge A in eine Menge B eine injektive Abbildung findet und eine injektive Abbildung von B nach A, im allgemeinen nicht richtig ist, wenn A und B unendlich sind, habe ich mal ein Beispiel konstruiert:
[mm] A=\IN
[/mm]
[mm] B=\mathcal{P}(\IN) [/mm] [Potenzmenge von [mm] \IN]
[/mm]
Dann sind ja A und B bekanntermaßen nicht gleichmächtig, aber man kann
trotzdem jeweils injektive Funktionen angeben.
Für A->B n->{1,2....n}
Für B->A [mm] M->\sum_{b \in M} 10^b
[/mm]
beide Abbildungen sind injektiv, aber die Mengen sind trotzdem nicht gleichmächtig.
Meine Hauptfrage ist jetzt, warum die Schlussweise oben für endliche Mengen stimmt, aber nicht für unendliche, oder stimmt sie womöglich für endliche Mengen auch nicht?
Ist meine Erklärung mit der Abbildung auf die natürlichen Zahlen richtig ( | | : M -> [mm] \IN^X)?
[/mm]
Wäre super, wenn mir da jemand helfen könnte
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:14 So 03.09.2006 | | Autor: | felixf |
Hallo!
> Es handelt sich dabei eigentlich nicht um eine konkret
> gestellte Aufgabe, sondern nur um eine Frage, die mir in
> einem anderen Zusammenhang kam.
> Konkret geht es um ein Kriterium für den Beweis der
> gleichmächtigekeit endlicher Mengen.
> Normalerweise beweist man die Gleichmächtigkeit zweier
> Mengen dadurch, dass man eine bijektive Abbildung zwischen
> diesen Mengen (im Folgenden A und B genannt) findet.
> Für endliche Mengen habe ich mir überlegt, dass es
> ausreichen müsste, wenn man eine injektive Funktion A->B
> findet und eine zweite injektive Funktion B->A.
Das gleiche gilt sogar fuer unendliche Mengen! Dies besagt der Schroeder-Bernstein-Satz. Etwas Infos dazu inkl. einem Beweis findets du z.B. in dem Buch `Das BUCH der Beweise' von Martin Aigner und Guenter M. Ziegler (sowieso ein sehr empfehlenswertes Buechlein  ); in der zweiten Auflage ist es Satz 3 auf Seite 118. (In dem Buch gibt es einen ganzen Abschnitt ueber Kardinalzahlen, wo das ganze recht anschaulich erklaert wird und auch einige Sachen -- wie eben dieser Satz -- bewiesen werden.)
> Ich habe dafür folgendendermaßen geschlossen und bin mir
> jetzt nicht mehr so ganz sicher, ob ich das überhaupt so
> darf und warum diese Schlussweise bei unendlichen Mengen
> (zumindest bie überabzählbaren) nicht anwendbar ist. Also
> hier die Schlussweise:
>
> Beennen wir die injektive Funktion A->B als f und die
> injektive Funktion B->A als g, dann gilt:
> f(A) [mm]\subset[/mm] B also | f(A) | [mm]\le[/mm] | B |
>
> und wegen der Injektivität gilt auch | f(A) | = | A | und
> insgesamt also | A | [mm]\le[/mm] | B |
>
> genauso kann man von g(B) schließen:
>
> g(B) [mm]\subset[/mm] A also | g(B) | und genauso wie oben
> letztendlich | B | [mm]\le[/mm] | A |.
Genau.
> Kombiniert also | A | = | B |
Bei endlichen Mengen stimmt das. Bei unendlichen Mengen ist das beweisenswuerdig (das ist dann halt der Satz von Schroeder-Bernstein).
> Dass aus A [mm]\subset[/mm] B folgt | A | [mm]\le[/mm] | B | folgt ja schon
> daraus, dass es eine injektive Abbildung auf eine Teilmenge
> von B gibt (die identitätsabbildung).
>
> Im Prinzip müsste man auch B'=B [mm]\setminus[/mm] A setzen können,
> so dass gilt:
>
> B=A [mm]\cup[/mm] B'
>
> und es ist auch klar, dass immer gelten muss |B'| [mm]\ge[/mm] 0,
> denn es gibt keine Mengen mit einer negativen Anzahl von
> Elementen.
Genau.
> Weil A und B' disjunkt sind, muss gelten:
>
> | B |=| A | + | B'|
>
> Hier vermute ich aber schon das erste Problem, wenn A und
> B' nicht beide endlich sind. Stimmt das jetzt noch?
Ja, das stimmt: Wenn man $+$ richtig definiert. Dazu musst du die natuerlichen Zahlen passend erweitern, naemlich grad zu den ![[]](/images/popup.gif) Kardinalzahlen.
> Ich habe mir überlegt, dass die Funktion | | eine Abbildung
> von einer Menge auf die Menge der Natürlichen Zahlen mit 0
> ist und man also implizit annimmt, dass | | eine natürliche
> Zahl ist, was ja z.B. bei IR nicht der Fall ist.
Nur fuer endliche Mengen liefert | | eine natuerliche Zahl (oder 0). Andernfalls bekommst du eine Kardinalzahl.
> Dafür dass die Schlussweise von oben, dass wenn man von
> einer Menge A in eine Menge B eine injektive Abbildung
> findet und eine injektive Abbildung von B nach A, im
> allgemeinen nicht richtig ist, wenn A und B unendlich sind,
Doch. Also muss irgendwas an deinem Beispiel falsch sein.
> habe ich mal ein Beispiel konstruiert:
>
> [mm]A=\IN[/mm]
> [mm]B=\mathcal{P}(\IN)[/mm] [Potenzmenge von [mm]\IN][/mm]
>
> Dann sind ja A und B bekanntermaßen nicht gleichmächtig,
> aber man kann
> trotzdem jeweils injektive Funktionen angeben.
>
> Für A->B n->{1,2....n}
> Für B->A [mm]M->\sum_{b \in M} 10^b[/mm]
Die Abbildung $B [mm] \to [/mm] A$ ist aber nur fuer alle endlichen Teilmengen von [mm] $\IN$ [/mm] definiert!
Die Teilmenge von $B$, die aus allen endlichen Teilmengen von [mm] $\IN$ [/mm] besteht, ist tatsaechlich abzaehlbar.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:22 So 03.09.2006 | | Autor: | jbulling |
Hallo Felix,
danke für Deine Antwort, hab schon angefangen an mir zu zweifeln *g*
Ich werde mir den Abschnitt im Buch der Beweise mal durchlesen, danke.
Lese von Aigner grad auch "Diskrete Mathematik". Ist wahrscheinlich der selbe Autor. Scheint sehr rührig zu sein.
Gruß & schönen Sonntag noch
Jürgen
|
|
|
|
