Mächtigkeit von Mengen

27.07.2008, 08:28

Majin_Clodan

Mächtigkeit von Mengen

Morgen Leute! Wink

Heute geht es um die Mächtigkeit und zwar habe ich das folgende Problem:

also ich weiß, wie ich die Mächtigkeit 2er endlicher Mengen ermitteln kann(Kinderkram Big Laugh

). Aber bei unendlichen Mengen tu ich mich noch schwer. Das Problem ist das folgende:

Ich bin den Artikel "Mächtigkeit" bei Wikipedia durchgegangen und mir auch schon einige Beispiele angesehen.
Aber ich verstehe nicht, warum:

1)
Die Menge der Natürlichen, Ganzen und Rationalen Zahlen zueinander gleichmächtig sind. Bei den natürlichen und ganzen Zahlen kann ich es noch nachvollziehen, da sie identisch ab dem Wert 0 bzw. 1 sind. Aber Rationale??

2)
Wir haben 2 unendliche Mengen, für die gilt:
N = {1,2,3,4,5,...}
M = {x | x ist eine ungerade positive Zahl und geht gegen unendlich}
Hierbei sind diese beiden Mengen auch gleichmächtig und das verstehe ich auch nur schwer. Beide streben gegen unendlich

Das Problem ist nun, ich verstehe irgendwie nicht so ganz die Gleichmächtigkeit. Ich weiß, dass zwischen gleichmächtigen Mengen eine bijektion existieren muss d.h. beide Mengen sind zueinander sujektiv und injektiv(auch neu und selber erlernt smile

).
Ich kann also nur schwer nachvollziehen, wann 2 Mengen gleichmächtig sind, weil ich las irgendwo, dass 2 unendliche Mengen nicht gleichmächtig sein müssen wie z.B. die Menge der natürlichen und reellen Zahlen. O.o Auch hierbei verstehe ich nicht, wieso diese nicht gleichmächtig sind.

Nehmen wir mal noch ein beispiel von mir. Aber wehe einer lacht darüber. >>.>>
Sagen wir mal, wir haben 2 Mengen gegeben. Die eine Menge besteht aus unendlich Äpfeln und die andere aus unendlich Bananen.
Sind diese beiden Mengen gleichmächtig? Ich würde nein sagen, weil die Beschaffenheit bzw. das, woraus ein Apfel besteht, eine Banane nicht besteht. Es existieren also Obstunterschiede. smile

MFG Majin_Clodan

27.07.2008, 08:42

Mazze

Auf diesen Beitrag antworten »

Zitat:

Aber Rationale??

Cantorsches Diagonalargument

Zitat:

Hierbei sind diese beiden Mengen auch gleichmächtig und das verstehe ich auch nur schwer. Beide streben gegen unendlich

Ach, bei den Mengen handelt es sich also um Grenzwerte? Die Mengen streben nicht gegen unendlich, sie besitzen unendlich viele Elemente. Zudem ist Deine Menge M auch fehlerhaft formuliert, Zahlen streben genausowenig gegen irgendwas. Versuch doch mal eine Bijektion zwischen den beiden Mengen zu konstruieren. Kleiner Tip

1 -> 1
2 -> 3
3 -> 5
4 -> 7
5 -> 9

na erkennst Du ein System ?

Zitat:

z.B. die Menge der natürlichen und reellen Zahlen. O.o Auch hierbei verstehe ich nicht, wieso diese nicht gleichmächtig sind.

Zwischen jeweils zwei reellen Zahlen findet sicher immer noch eine reelle Zahl. Versuche so eine Surjektion von den natürlichen Zahlen auf die reellen Zahlen zu erhalten, und Du bekommst einen Widerspruch. Wenn es dich aber interessiert, die Potenzmenge der natürlichen Zahlen ist gleichmächtig zu der Menge der reellen Zahlen Augenzwinkern

Zitat:

ie eine Menge besteht aus unendlich Äpfeln und die andere aus unendlich Bananen.

Unendlich ist hier ein schwammiger Begriff. Überabzählbar unendlich viele Äpfel, abzählbar unendlich viele Bananen? .... Du solltest wissen das man unendlich nicht vergleichen kann.

27.07.2008, 09:09

Jacques

Auf diesen Beitrag antworten »

Zu 1) noch:

Zitat:

Original von Majin_Clodan
Bei den natürlichen und ganzen Zahlen kann ich es noch nachvollziehen, da sie identisch ab dem Wert 0 bzw. 1 sind.

Die Gleichmächtigkeit hat damit nichts zu tun. Sondern es existiert einfach eine bijektive Funktion von der einen Menge zur anderen (was Du weiter unten ja auch als Kriterium genannt hast):

z. B.:

$\begin{eqnarray*} f\colon\ x\mapsto\begin{cases}2x, &\textrm{falls}\ x \geq 0\\ 2|x| - 1, & \textrm{falls}\ x < 0\end{cases}\qquad D_f := \mathbb{Z} \end{eqnarray*}$

Zitat:

Original von Majin_Clodan
Nehmen wir mal noch ein beispiel von mir. Aber wehe einer lacht darüber. >>.>>
Sagen wir mal, wir haben 2 Mengen gegeben. Die eine Menge besteht aus unendlich Äpfeln und die andere aus unendlich Bananen.
Sind diese beiden Mengen gleichmächtig? Ich würde nein sagen, weil die Beschaffenheit bzw. das, woraus ein Apfel besteht, eine Banane nicht besteht. Es existieren also Obstunterschiede.

Was hat die "Art" der Elemente mit der Gleichmächtigkeit zu tun? Man muss einfach nur jedem Apfel genau eine Banane zuordnen können, sodass jede Banane in genau einer Zuordnung vorkommt.

27.07.2008, 09:27

Majin_Clodan

Auf diesen Beitrag antworten »

Zitat:

Original von Mazze:
Ach, bei den Mengen handelt es sich also um Grenzwerte? Die Mengen streben nicht gegen unendlich, sie besitzen unendlich viele Elemente. Zudem ist Deine Menge M auch fehlerhaft formuliert, Zahlen streben genausowenig gegen irgendwas. Versuch doch mal eine Bijektion zwischen den beiden Mengen zu konstruieren. Kleiner Tip

1 -> 1
2 -> 3
3 -> 5
4 -> 7
5 -> 9

na erkennst Du ein System ?

Jetzt fange ich an es zu verstehen. Auch wenn es nur ein kleiner Teil sei. Wenn ich herausfinden will, ob 2 Mengen gleichmächtig sind, muss ich schauen, ob ein System existiert, wobei es, bei diesem Beispiel, für eine strukturierte und gleichmäßig erhöhte Veränderung, sorgt.
Das System laute, wenn die Werte links vom Pfeil der Parameter m seien:
2 * m - 1
Die Position, die m hat, sorgt für dessen rechten Wert. In der dritten Zeile hat also z.B. das m den Wert 3:
2 * 3 - 1 = 6 - 1 = 5

Wenn man solche Systeme zwischen Mengen entwickelt, muss aber auch jedes Element der einen Menge bijektiv zu einem Element der anderen Menge sein d.h. man dürfe kein Element auslassen. Jedem Element sei also einem Element der anderen Menge zugeordnet.

Zitat:

Original von Mazze:
Cantorsches Diagonalargument

Hierbei erkenne ich das System. smile

THX.

Doch Beim Schreiben viel mir etwas auf und zwar die folgende Zeile:

1, 1/2, 2, 3, 1/3, 1/4, 2/3, 3/2, 4, 5, 1/5, ...

Dies ist zu finden unter der zweiten Art von Bild. Ich weiß anhand des Bildes(?), wie ich auf die 1, 1/2, 2/3 und 3 komme. Aber dann hört es schon wieder auf.
Da ich das zweite zu kompliziert(für den ersten Blick!) finde, würde ich nur das erste nehmen, weil dies übersichtlicher ist. Reicht das, wen ich die Übersicht des ersten Bildes kann oder gibt es im zweiten Bild bestimmte Informationen, die im Ersten fehlen??

Zitat:

Original von Mazze:
Zwischen jeweils zwei reellen Zahlen findet sicher immer noch eine reelle Zahl. Versuche so eine Surjektion von den natürlichen Zahlen auf die reellen Zahlen zu erhalten, und Du bekommst einen Widerspruch.

Stimmt ja. Hammer

Jetzt ist es logisch. smile

Zitat:

Original von Mazze:
Unendlich ist hier ein schwammiger Begriff. Überabzählbar unendlich viele Äpfel, abzählbar unendlich viele Bananen? .... Du solltest wissen das man unendlich nicht vergleichen kann.

Und das nächste was ich gelernt habe. smile

Sagen wir mal, dass beide Mengen abzählbar unendlich sind. Es existiert eine Bijektion zur Menge der natürlichen Zahlen.
Sind dann trotzdem beide Mengen gleichmächtig? Ich würde sagen ja, da ein System existiert. Ein System, wobei sich z.B. die Menge der Bananen gleichmäßig zu der Menge der Äpfel erhöht.

MFG Majin_Clodan

Edit:

Zitat:

Original von Jacques:
Was hat die "Art" der Elemente mit der Gleichmächtigkeit zu tun? Man muss einfach nur jedem Apfel genau eine Banane zuordnen können, sodass jede Banane in genau einer Zuordnung vorkommt.

Stimmt. Dafür gibt es ja den Begriff Extensionalität. smile

27.07.2008, 09:48

Mazze

Auf diesen Beitrag antworten »

Zitat:

Das System laute, wenn die Werte links vom Pfeil der Parameter m seien:
2 * m - 1

Den Zusammenhang hast Du richtig erkannt. Allerdings reicht es nicht aus so ein "System" aufzustellen. Sei $\begin{eqnarray*} f: N \to M ~ f(n) = 2n - 1 \end{eqnarray*}$ Du musst jetzt zeigen dass f wirklich bijektiv auf N x M ist.

Zitat:

Dies ist zu finden unter der zweiten Art von Bild. Ich weiß anhand des Bildes(?), wie ich auf die 1, 1/2, 2/3 und 3 komme. Aber dann hört es schon wieder auf.

Das zweite Bild gibt Dir an wie man die Zahlen durchgeht um die Zahlen zu zählen. Der Schlüssel liegt hier drin

Zitat:

Durch das Überspringen kürzbarer Brüche liegt für jede positive rationale Zahl genau ein Repräsentant (der nicht mehr kürzbare Bruch) in dieser Abzählung, wodurch die gewünschte Bijektion hergestellt ist.

Zitat:

Jede abzählbare unendliche Menge ist gleichmächtig zu den natürlichen Zahlen. Das liegt in der Natur der Sache, wenn ich eine Menge abzählen kann, dann kann ich jedem Element der Menge eine eindeutige natürliche Zahl zuordnen (den Index). Damit existiert die Bijektion. Die Existenz des Systems , ist wie oben schon gesagt nicht ausreichend. Du musst es in eine Funktion verpacken, und zeigen das jene Funktion Bijektiv ist. Ein Beispiel wo es nicht so einfach klappt ist die Tatsache das

$\begin{eqnarray*} (0,1) \text{ und } \mathbb{R} \end{eqnarray*}$ gleichmächtig sind. Dieses erstaunliche Resultat kann man zum Beispiel damit zeigen dass die Funktion

$\begin{eqnarray*} f(x) = \tan\left(\pi * x - \frac{\pi}{2}\right) \end{eqnarray*}$ bijektiv auf $\begin{eqnarray*} (0,1) \times \mathbb{R} \end{eqnarray*}$ ist.

28.07.2008, 09:22

TheWitch

Auf diesen Beitrag antworten »

Zitat:

Original von Mazze
Zwischen jeweils zwei reellen Zahlen findet sicher immer noch eine reelle Zahl. (...)

Das ist kein Argument. Es trifft genauso auf rationale Zahlen zu - und dennoch sind $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} \mathbb Q \end{eqnarray*}$ gleichmächtig.

29.07.2008, 07:47

Majin_Clodan

Auf diesen Beitrag antworten »

Morgen!

Zitat:

Original von Mazze:
Den Zusammenhang hast Du richtig erkannt. Allerdings reicht es nicht aus so ein "System" aufzustellen. Du musst jetzt zeigen dass f wirklich bijektiv auf N x M ist.

Ach so ist das. Das System, was ich erstelle, ist zugleich eine Formel für eine Funktion.
Aber diese Funktion ist, wie ich dem Bild entnehme, nur von der Menge N zu der Menge M gültig. Das heißt, von der Menge M zu der Menge N müsste ein anderes System entstehen, oder?
Aber wie zeige ich nun anhand dieser Funktion die Bijektivität?? Sorry, aber das habe ich nicht in keiner Weise je in der Schule gehabt. unglücklich

Du hast auch unten ein Beispiel eines Funktions-Systemes(Sorry, aber weiß nicht genau, wie man es nennen soll), wobei du zeigst, dass 0 und 1 und die Menge der reellen Zahlen gleichmächtig sind. Auch hierbei verstehe ich es nicht.

Ich glaube, ich weiß jetzt, was ich nicht verstehe. In dem oberen Beispiel z.B. steht ja folgendes da:
N x M
ich sage mal schnell und frech, dass dies das kartesische Produkt sei. Heißt das denn dann, dass das Funktions-System bijektiv auf dem Kartesischen Produkt von N und M sein muss?? verwirrt

In welcher Weise soll ich das sehen bzw. mir dann vorstellen können?? O.o

MFG Majin_Clodan

29.07.2008, 11:52

Jacques

Auf diesen Beitrag antworten »

Wäre es nicht sinnvoller, mit den Grundlagen (Funktionen u. s. w.) anzufangen und erst danach mit Mengenlehre weiterzumachen? verwirrt

Zwei Mengen A und B sind genau dann gleichmächtig, wenn es eine bijektive Funktion von A nach B gibt (oder umgekehrt). Bijektivität bedeutet, dass jedes Element der Zielmenge genau einmal "getroffen" wird. D. h. es werden jeweils ein Element der Definitionsmenge und ein Element der Zielmenge so zu einem Paar zusammengefasst, dass es bei den Paaren keine Überschneidungen gibt.

Um die Gleichmächtigkeit zweier Mengen zu zeigen, muss man irgendeine bijektive Funktion nennen, welche die eine Menge auf die andere abbildet. Bei endlichen Mengen kann man die Funktion ausdrücklich angeben:

z. B.

$\begin{eqnarray*} A = \{2, 4, 6, 8, 10 \} \end{eqnarray*}$

$\begin{eqnarray*} B = \{10, 20, 30, 40, 50 \} \end{eqnarray*}$

Die beiden Mengen sind gleichmächtig, denn es gibt die geforderte Funktion:

$\begin{eqnarray*} f = \{ (2, 10), (4, 20), (6, 30), (8, 40), (10, 50) \} \end{eqnarray*}$

(natürlich wären auch andere Zuordnungen möglich)

Bei unendlichen Mengen hingegen kann man die Zuordnungen ja nicht mehr "per Hand" machen, sondern man muss eine passende Zuordnungsregel finden.

Um z. B. die Gleichmächtigkeit von

$\begin{eqnarray*} \mathbb{N}^{\ast} \end{eqnarray*}$

und

$\begin{eqnarray*} B = \{2, 4, 6, \ldots \} \end{eqnarray*}$

zu zeigen, würde man folgende Funktion angeben:

$\begin{eqnarray*} f\colon\ x \mapsto 2x \qquad D_f = \mathbb{N^{\ast}} \end{eqnarray*}$

Die Funktion ist bijektiv, d. h. sie ordnet jeder natürlichen Zahl so eine gerade Zahl zu, dass jede gerade Zahl genau einmal "getroffen" wird.

Den Beweis der Bijektivität kann man z. B. so machen:

Zuerst wird die Bijektivität in zwei "Teileigenschaften" unterteilt: Bijektivität gilt genau dann, wenn zugleich Surjektivität und Injektivität gelten.

Die Bedingung für Surjektivität lautet:

Zu jedem y in der Zielmenge gibt es ein x in der Definitionsmenge, sodass f(x) = y
(jedes Element der Zielmenge tritt (mindestens) einmal als Funktionswert auf)

Die Bedingung für Injektivität lautet:

Für alle x1 und x2 der Definitionsmenge gilt: f(x1) = f(x2) => x1 = x2
(zu genau einem Funktionswert gibt es auch genau eine zugehörige Stelle; d. h. jedes Element der Zielmenge tritt höchstens einmal als Funktionswert auf)

----

Nachweis der Surjektivität:

Man löst die Funktionsvorschrift

$\begin{eqnarray*} y = 2x \end{eqnarray*}$

nach der Stellenvariablen auf:

$\begin{eqnarray*} x = \frac{y}{2} \end{eqnarray*}$

...und überlegt, ob man jedes Element der Zielmenge für y einsetzen könnte und jedesmal einen passenden Wert für x erhielte. "Passend" heißt, dass die Zahl in der Definitionsmenge liegt. (also man prüft einfach, ob es zu jedem y der Zielmenge eine Stelle gibt, die auf y abgebildet wird)

----

Nachweis der Injektivität:

Man setzt:

$\begin{eqnarray*} f(x_1) = f(x_2) \end{eqnarray*}$

...und prüft, ob darauf x1 = x2 folgt:

$\begin{eqnarray*} f(x_1) = f(x_2) \ \Longleftrightarrow\ 2x_1 = 2x_2 \ \Longleftrightarrow\ x_1 = x_2 \end{eqnarray*}$

30.07.2008, 09:15

Majin_Clodan

Auf diesen Beitrag antworten »

Moin!

Herzlichen Dank für die Hilfe Jacques. Nun sind sehr viele Fragen verschwunden. smile

Nur noch ein paar kleine und zwar hast du das folgende Zeichen da zu stehen:

$\begin{eqnarray*} D_f = \mathbb N^* \end{eqnarray*}$

Was bedeutet dieses Df?? Hat es einen Namen bzw. was sagt es näher aus?
Ich würde jetzt einfach spekulieren, dass dies einem bei der Funktion:
$\begin{eqnarray*} x \to 2x \end{eqnarray*}$

kennzeichnet, von welcher Seite aus das System erstellt wurde d.h. das "x zu 2x" und das Df zeige, dass das System von der Menge der natürlichen Zahlen zu den geraden, positiven Zahlen gilt.
Oder lass es mich anders ausdrücken, dass das Df den Wert auf der linken Seite des Pfeiles angibt. Da man die gleichmächtigkeit von 2 Mengen zeigen will, ist es logisch, dass die andere Seite dann die andere Menge ist.
Hoffe, falls das richtig ist, was ich spekuliere, dass das auch jemand versteht.^^ Noch schwer es auszudrücken.

Dann zu guter Letzt der letzte Punkt, wo es um den Nachweis der Injektivität geht. Ich habe den Text 3x geschrieben und immer beim Lesen kam ein neues Verständigungslevel. O.o Nun hoffe ich, dass ich das richtige erwischt habe. smile

Also ich setze 2 beliebige Werte aus der Definitionsmenge in meine Funktion ein. Mache ich dies und kürze u.ä., muss ich dann wieder auf die Werte kommen, die ich eingesetzt habe. Ist das so richtig???
Wenn ich also z.B. folgendes einsetze:
$\begin{eqnarray*} x_1=3 \end{eqnarray*}$
$\begin{eqnarray*} x_2=5 \end{eqnarray*}$

dann sieht die Funktione folgendermaßen aus:
2 * 3 = 2 * 5
6 = 10

Nun teile ich durch 2 und bekomme folgendes heraus:
3 = 5
Also die Werte, die mir als Einsetzungswert dienten. Ist das so von mir richtig verstanden??? Hoffe es, denn dann wäre der Kampf erstmal mit der Mächtigkeit gewonnen. smile

Den Rest muss man halt üben, aber ohne einen ersten Leitfaden geht es leider nicht. traurig

MFG Majin_Clodan

30.07.2008, 10:14

Jacques

Auf diesen Beitrag antworten »

Bei dem Df ist Deine Vermutung eigentlich richtig.

Das Df steht für 'Definitionsmenge von f'. Funktionen sind ja Zuordnungen, die jedem Objekt x einer Menge (der Definitionsmenge) genau ein Objekt y einer weiteren Menge (der Zielmenge) zuordnen.

Bei "Mächtigkeits-Bijektion" ist eben einer der beiden Mengen (welche, spielt keine Rolle) die Definitionsmenge und die andere die Zielmenge.

Zum Nachweis der Injektivität:

x1 und x2 müssen symbolisch bleiben, also Du darfst dafür keine konkreten Zahlen einsetzen. Denn es geht darum, dass allgemein gilt, also für alle Stellen x1 und x2: f(x1) = f(x2) => x1 = x2.

Bei Deiner Vorgehensweise würdest Du nur (unnötig aufwendig*) zeigen , dass 3 und 5 nicht auf denselben Funktionswert abgebildet werden. Damit ist zwar die Injektivität nicht widerlegt, aber auch nicht bewiesen, denn Du könntest nur zufällig zwei Zahlen erwischt haben, die Deine Vermutung bestätigen. Es könnte durchaus sein, dass z. B. alle anderen Zahlen auf eine einzige abgebildet werden, also die Injektivität nicht gilt.

Ein weiteres Beispiel für einen Injektivitätsbeweis:

Behauptung:
$\begin{eqnarray*} f\colon\ x \mapsto 3x + 5 \end{eqnarray*}$ ist injektiv

Beweis:
$\begin{eqnarray*} f(x_1) = f(x_2) \ \longleftrightarrow\ 3x_1 + 5 = 3x_2 + 5 \ \longleftrightarrow\ 3x_1 = 3x_2\ \longleftrightarrow\ x_1 = x_2 \end{eqnarray*}$

//* unnötig aufwendig deshalb, weil der Beweis schon mit der Erkenntnis f(3) ungleich f(5) erledigt ist. Man will ja beweisen: Wenn zwei Funktionswerte gleich sind, dann sind es auch die zugehörigen Stellen. Also wenn die Funktionswerte gar nicht gleich sind, gibt es nichts zu zeigen.

30.07.2008, 11:07

system-agent

Auf diesen Beitrag antworten »

Zitat:

Original von Jacques
Ein weiteres Beispiel für einen Injektivitätsbeweis:

Behauptung:
$\begin{eqnarray*} f\colon\ x \mapsto 3x + 5 \end{eqnarray*}$ ist injektiv

Beweis:
$\begin{eqnarray*} f(x_1) = f(x_2) \ \longleftrightarrow\ 3x_1 + 5 = 3x_2 + 5 \ \longleftrightarrow\ 3x_1 = 3x_2\ \longleftrightarrow\ x_1 = x_2 \end{eqnarray*}$

Formal richtig musst du natürlich noch schreiben von wo nach wo die Funktion $\begin{eqnarray*} f \end{eqnarray*}$ abbilden will, also zum Beispiel $\begin{eqnarray*} f:\mathbb R\to\mathbb R \end{eqnarray*}$ .

Falls du noch ein schönes Bildli zur Injektivität willst, siehe hier.

31.07.2008, 08:29

Majin_Clodan

Auf diesen Beitrag antworten »

Nach einer langen Reise...
einem harten Kampf...
und einem starken Willen...

Ist die Mächtigkeit der Mengen nun geschafft. Prost

Das Bild...nunja...ich nehme lieber das Bild von wikipedia. Das sieht besser aus, aber trotzdem THX. smile

http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Injection.svg/200px-Injection.svg.png

Ein herzliches Danke an:
Mazze
Jacques
system-agent

Ihr habt mir sehr geholfen. Tanzen

Der Rest ist jetzt einfach nur Übungssache, aber, im Gegensatz zu vorher, kenne ich nun das Prinzip und die Vorgehensweise. smile

MFG Majin_Clodan

Neue Frage »

Antworten »

Mächtigkeit von Mengen

Verwandte Themen