Unendliche Menge

Neue Frage »

Marina563 Auf diesen Beitrag antworten »
Unendliche Menge
Meine Frage:
Man soll beweisen, dass für jede unendliche Menge X gilt, dass |X| >= N.



Meine Ideen:
Mein Beweis sieht wie folgt aus: "Sei |X| < N . Dann gibt es ein n?N, sodass f:X --> {1, 2, ..., n} bijektiv ist. Somit ist X endlich, was im Widerspruch zur Ausgangsvoraussetzung steht."

Reicht das so - was meint ihr? Danke für jedwede Hilfe!
Elvis Auf diesen Beitrag antworten »

Es reicht nicht, nur zu behaupten, dass es ein n in N und eine bijektive Funktion f:X --> {1, 2, ..., n} gibt. Wo ist der Beweis für die Existenz dieser beiden Dinge ?
Man könnte einen Beweis durch vollständige Induktion über die Anzahl der Elemente führen, die man aus X heraus nimmt. In einer unendlichen Menge X sind sicher genügend Elemente enthalten.
 
 
Marina563 Auf diesen Beitrag antworten »

Danke für die Antwort! - aber ich habe ehrlich gesagt, keine Ahnung, wie das mit vollständiger Induktion funktionieren soll ... Könntest du mir bitte den Induktionsanfang verraten? Von dort käme ich vielleicht auf den Rest der Lösung
Elvis Auf diesen Beitrag antworten »

Induktionsanfang: ist eine unendliche Menge, enthält also unendlich viele Elemente. Nimm Element aus der Menge und bilde damit die Menge .
Marina563 Auf diesen Beitrag antworten »

Okay, danke! So dann in etwa?

Induktionsschritt: Es existiere eine injektive Abbildung f: {1, 2, ... , n} --> X, f(a) = x_n (Induktionsvoraussetzung). Wir zeigen, dass es eine injektive Abbildung g von {1, 2, ... , n, n+1} auf X gibt. Sei


g(b) = f(a), falls b = a für ein bestimmtes a element {1, ... , n}

g(b) = x_n+1, falls b = n+1



Funktion g ist injektiv und somit |N| <= |X|


Was meinst du?
Elvis Auf diesen Beitrag antworten »

Auch den Induktionsschritt mache ich zunächst einmal ganz anschaulich ohne Funktionen.

Induktionsschritt: Seien Elemente aus ausgewählt. Nehmen wir an, in gäbe es nicht mehr Elemente, dann wäre endlich mit im Widerspruch zur Voraussetzung. Also nehmen wir ein weiteres Element und bilden damit die Menge .

Folgerung: Für alle gibt es eine injektive Funktion .
Also gibt es eine injektive Funktion .

Falls das nicht klar genug ist, musst du eine Folge von Funktionen bilden, die jeweils die vorausgehende Funktion fortsetzen, und weil das so ist, kann man alle Glieder der Folge mit bezeichnen, und ist eine Fortsetzung von .
Marina563 Auf diesen Beitrag antworten »

Ahhh, ja, das leuchtet mir ein! Viele Dank! smile


Würdest du die folgende Aufgabe auch mit vollständiger Induktion lösen?

"Beweisen Sie: Ist X eine leere Menge, so existiert keine Telmenge Y von X derart, dass X\Y nichtleer ist, aber |X| = |Y|."

Könntest du mir bitte helfen? Ich hätte behauptet, dass vollständige Induktion hier nicht nötig/sinnvoll ist.
Elvis Auf diesen Beitrag antworten »

Ich verstehe den Sinn dieser Aussage nicht. Ist das die Originalaufgabe?
Marina563 Auf diesen Beitrag antworten »

Oh, sorry, meinte *endliche (!) Menge. Die Aufgabe ist ein Zweiteiler. Zuerst soll man zeigen, dass es für eine unendliche Menge X eine von ihr verschiedene Teilmenge Y gibt mit |X| = |Y|.
Im zweiten Teil der Aufgabe soll man dann zeigen, dass das für endliche Mengen nicht gilt, also dass es für eine endliche Menge keine von ihr verschiedene, aber gleichmächtige Teilmenge gibt.

Also für (a) reicht es, glaube ich, eine Funktion zu konstuieren, und deren Bijektivität nachzuweisen, oder?

Meine Frage ist, ob du bei (b) die vollständige Induktion verwendet würdest? Danke auf jeden Fall, dass du mir hilfst!
Elvis Auf diesen Beitrag antworten »

(a) ist nach Richard Dedekind die Definition einer unendlichen Menge, (b) die Definition einer endlichen Menge. (https://de.wikipedia.org/wiki/Unendliche...d-Unendlichkeit) Was gibt es da noch zu beweisen ? Wie definierst du unendliche Menge und endliche Menge ?
Marina563 Auf diesen Beitrag antworten »

Weiß nicht ... Also ich glaube, es geht darum, zu beweisen, dass die Dedekind-Definition tatsächlich ädaquat/gültig ist.
Elvis Auf diesen Beitrag antworten »

ist gleichbedeutend mit | und , und das heißt, es gibt injektive Abbildungen von nach und von nach . Jede unendliche Menge enthält eine abzählbar unendliche Teilmenge (das wissen wir schon), setze z.B. und konstruiere injektive Abbildungen. Orientiere dich an dem Beweis, für . Den Beweis, dass endliche Mengen keine gleichmächtigen echten Teilmengen haben, kennst du sicher schon (wenn nicht, erfindest du ihn neu).
Marina563 Auf diesen Beitrag antworten »

Okay, danke, habe die Abbildung


f: X --> X \ {x_2n},

f(x) = x_2n-1, falls x = x_n für ein n€N
f(x) = x, sonst


und jetzt zeigen, dass diese Funktion bijektiv ist?
Elvis Auf diesen Beitrag antworten »

Gut nachdenken ist besser als schlecht raten. Vielleicht fällt dir im Schlaf noch etwas ein, was zu meinem Vorschlag passt.
Marina563 Auf diesen Beitrag antworten »

Und Aufgabe (b) läuft auf den Beweis der folgenden Aussage hinaus, oder?


Sind n und m natürliche Zahlen mit m > n, dann gibt es keine injektive Abbildung E_m --> E_n


Muss ich dafür zuerst beweisen, dass eine Teilmenge von X, die ungleich X ist, "kleiner" ist als X?
Elvis Auf diesen Beitrag antworten »

Nein, aber du musst erst beweisen, dass zu jeder endlichen Menge mit n Elementen eine Bijektion von X auf {1,..., n} existiert. Und das musst du später benutzen.
Marina563 Auf diesen Beitrag antworten »

Hmm... ich versteh nicht, warum meine Abbildung nicht passt ...

Y ist ja X abzüglich der x_n mit einer geraden Zahl als Index. Das heißt, in Y gibt es nur die x mit ungeradem Index. Und deshalb bilden wir

x1 --> x1
x2 --> x3
x3 --> x5
x4 --> x7
x5 --> x9
usw.

ab. Also x_n --> x_(2n - 1). Ich stehe gerade auf dem Schlauch; kannst du mir bitte sagen, wo der Fehler liegt, ich finde ihn nicht unglücklich
Marina563 Auf diesen Beitrag antworten »

Danke! Aber ist das nicht einfach die Definition der endlichen Menge? In meinem Lehrbuch heißt es: "Eine Menge M heißt endlich, falls es eine Bijektion f: {1, ... , n} --> M für ein n€N gibt." Dementsprechend kann ich das doch einfach voraussetzen und muss es nicht beweisen, oder?

Auf jeden Fall ist es super lieb von dir, dass du mir so viel hilfst!!!!
Elvis Auf diesen Beitrag antworten »

Zu X->Y. Diese Funktion ist injektiv. Das ist gut. Jetzt brauchst du eine andere injektive Funktion Y->X. Tipp :Identität. Nach dem Satz von Cantor-Bernstein sind dann X, Y gleichmächtig.
Zu endlichen Mengen. Wenn das deine Definition ist, kannst du damit arbeiten. Tipp :Schubfachprinzip.
Elvis Auf diesen Beitrag antworten »

Nachtrag: Wenn man so konkret wie hier zwei Mengen und und eine (vermutlich bijektive) Abbildung gegeben hat, ist der einfachste Beweis für die Angabe der Umkehrabbildung und der Nachweis, dass und die identischen Abbildungen auf und sind. (Ich "sehe", dass das so ist, du musst es nur noch aufschreiben. Deine Formulierung der jeweiligen Abbildungsvorschriften zusammen mit kurzen Listen der ersten Funktionswerte sind ein unwiderlegbarer Beweis.)
Marina563 Auf diesen Beitrag antworten »

Okay, so dann also:

Aufgabe (a)

Wir konstruieren die Funktion

f: X --> X\{x_2n}

f(x) = x_(2n-1), falls x = x_n für ein n€N
f(x) = x, sonst

Und nun die Funktion

g: X\{x_2n} --> X,

g(x) = x_((n+1)/2), falls x = x_n für ein n€N
g(x) = x, sonst

Nun zeigen wir, dass f ° g = Idy und g ° f = Idx


Sei x = x_n. Dann haben wir

(f ° g)(x) = f(g(x_n)) = f(x_((n+1)/2))) = x_(2* ((n+1)/2) - 1) = x_n =

Sei x =/= x_n. Dann ist

f(g(x)) = f(x) = x


Und das dann noch für g ° f, und ich bin fertig?

Danke für deine Geduld!!!!
Marina563 Auf diesen Beitrag antworten »

Okay, so dann also:

Aufgabe (a)

Wir konstruieren die Funktion

f: X --> X\{x_2n}

f(x) = x_(2n-1), falls x = x_n für ein n€N
f(x) = x, sonst

Und nun die Funktion

g: X\{x_2n} --> X,

g(x) = x_((n+1)/2), falls x = x_n für ein n€N
g(x) = x, sonst

Nun zeigen wir, dass f ° g = Idy und g ° f = Idx


Sei x = x_n. Dann haben wir

(f ° g)(x) = f(g(x_n)) = f(x_((n+1)/2))) = x_(2* ((n+1)/2) - 1) = x_n

Sei x =/= x_n. Dann ist

f(g(x)) = f(x) = x

Folglich ist f ° g = Idx


Und das dann noch für g ° f, und ich bin fertig?

Danke für deine Geduld!!!!
Marina563 Auf diesen Beitrag antworten »

Okay, so dann also?

Aufgabe (a)

Wir konstruieren die Funktion

f: X --> X\{x_2n}

f(x) = x_(2n-1), falls x = x_n für ein n€N
f(x) = x, sonst

Und nun die Funktion

g: X\{x_2n} --> X,

g(x) = x_((n+1)/2), falls x = x_n für ein n€N
g(x) = x, sonst

Nun zeigen wir, dass f ° g = Idy und g ° f = Idx


Sei x = x_n. Dann haben wir

(f ° g)(x) = f(g(x_n)) = f(x_((n+1)/2))) = x_(2* ((n+1)/2) - 1) = x_n

Sei x =/= x_n. Dann ist

f(g(x)) = f(x) = x

Folglich ist f ° g = Idx


Und dann noch zeigen, dass g ° f = Idy, und ich bin fertig?

Danke für deine Geduld!!!!
Elvis Auf diesen Beitrag antworten »

Das passt ungefähr, Details musst du korrigieren.

Und du musst immer auch die Voraussetzungen dazu schreiben:
Jede unendliche Menge enthält eine abzählbar unendliche Teilmenge , also ist eine echte Teilmenge von .

Und zum Schluß musst du eine Zusammenfassung schreiben:
Damit ist bewiesen, dass eine Bijektion von auf eine echte Teilmenge von ist, und das heißt . qed.

Egal welches Mathematikbuch du zur Hand nimmst, darin ist jeder Beweis nicht nur ein Sammelsurium von Formeln, es steht auch immer eine Einleitung, verbindender Text und ein Schluß in jedem Beweis. Die Leser/in will nicht nur wissen, was du weißt, er/sie will auch verstehen, was du machst und wie du es machst, und sie/er möchte Spaß haben beim Lesen und Lernen.
Marina563 Auf diesen Beitrag antworten »

Okay, danke! Und danke für den Hinweis!!! Meinst du, ich sollte auch erläutern, wie ich auf f und g gekommen bin, bzw. warum f und g wohldefiniert sind?
Marina563 Auf diesen Beitrag antworten »

Und für Aufgabe (b) habe ich:

X ist endlich und somit gleichmächtig zu {1, ... , n} für ein bestimmtes n€N. Die Teilmenge Y von X ist gleichmächtig zu {1, ... , m} für ein m€N, wobei n > m.


Und jetzt beweise ich per Schubfachprinzip , dass es keine injektive (und somit bijektive) Funktion von {1, ... , n} zu {1, ... , m} gibt, oder?
Elvis Auf diesen Beitrag antworten »

Alles klar, richtig und gut gelöst. Wie du auf eine Funktion kommst, ist deine Privatsache, man muss sich nicht für eine gute Idee rechtfertigen. Die Funktionen f und g sind explizit definiert, noch mehr geht nicht. Wohldefiniert muss man nur zeigen, wenn eine Funktion z.B. für Restklassen definiert ist, dann ist zu zeigen, dass diese Funktion vertreterunabhaengig ist.
Marina563 Auf diesen Beitrag antworten »

Okay, danke! Noch mal eine Frage zu der ersten Aufgabe ("Ist X eine unendliche Menge, so gilt |X| >= N ").

Angenommen, man hat bereits bewiesen, dass jede Teilmenge einer abzählbaren Menge entweder endlich oder abzählbar (unendlich) ist; könnte man dann auch wie folgt vorgehen?

Es sei |X| < |N|. Dann ist X zu einer Teilmenge von N gleichmächtig, die kleiner als N ist. Jede Teilmenge von N ist entweder abzählbar oder endlich. X kann zu keiner abzählbaren Teilmenge von N gleichmächtig sein; denn dann wäre |X| = |N|. Wäre X hingegen gleichmächtig zu einer endlichen Teilmenge von N, dann wäre X selbst endlich, was im Widerdspruch zur Voraussetzung steht. Es folgt: |X| >= N.

Was meinst du?

Kann dir gar nicht genug danken!!!
Elvis Auf diesen Beitrag antworten »

Satz: Sei unendlich, dann ist
Beweis: ist endlich. qed.

Nachteil 1: Ich glaube, dass wir hier unterschwellig den Vergleichbarkeitssatz verwenden, und ich bin nicht sicher, ob wir den kennen. (http://www.aleph1.info/?call=Puc&permalink=mengenlehre1_1_5). Man darf die Ungleichheitszeichen zwischen Kardinalzahlen nicht verwechseln mit Ungleichheitszeichen zwischen reellen Zahlen !

Nachteil 2: Dieser Beweis ist nicht so schön konstruktiv wie der Beweis durch vollständige Induktion, den wir gemacht haben.
Marina563 Auf diesen Beitrag antworten »

Ja, hast recht, danke!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »