Beweis: Mengengleichheit

10.02.2012, 11:36

OhneDurchblick

Beweis: Mengengleichheit

Hallo ihr lieben,

ich brüte noch immer über ungelösten bzw. unverstandenen Übungsaufgaben und habe nun folgendes Problem:

Ich soll beweisen, dass die Menge der ungeraden natürlichen Zahlen und die Menge der durch 5 teilbaren natürlichen Zahlen gleichmächtig sind, weiß aber nicht so recht wie.

Die Menge der ungeraden natürlichen Zahlen würde ich mir als

$\begin{eqnarray*} 2n-1 \end{eqnarray*}$

denken, die Menge der durch teilbaren Zahlen wären entsprechend

$\begin{eqnarray*} 5n \end{eqnarray*}$

In der VL hatten wir es via vollständiger Induktion an einem anderen Beispiel (Summe der ungeraden natürlichen Zahlen = n²) erklärt.

Hier steht:

$\begin{eqnarray*} \sum\limits_{k=1}^n (2k-1) = n² \end{eqnarray*}$

Induktionsanfang:

$\begin{eqnarray*} n=1 \Rightarrow \sum\limits_{k=1}^1 (2*1-1)=1² \end{eqnarray*}$

$\begin{eqnarray*} 1=1 = w.A. \end{eqnarray*}$

Induktionsschritt: (Gilt das auch für n+1? Beim Summenzeichen schreibt er das "n+1" nicht, also ersetze ich es durch n+1=m)

$\begin{eqnarray*} \sum\limits_{k=1}^m (2k-1) =(n+1)² \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=1}^m (2k-1)=\sum\limits_{k=1}^n(2k-1)+(2(n+1)-1) \end{eqnarray*}$

wobei 2(n+1)-1 das letzte Zahlenglied der Summe ist

und somit ist

$\begin{eqnarray*} n² (laut IA) + 2n+1 = (n+1)² \end{eqnarray*}$

q.e.d.

Das nachzuvollziehen fällt mir schon nicht leicht, aber wie soll ich das für den anderen geforderten Beweis machen, zumal es ja nicht um eine Summe geht, sondern um die Menge der Zahlen! Kann mir jemand einen Tipp geben?

Die Mächtigkeit einer Menge ist ja definiert durch $\begin{eqnarray*} 2^n \end{eqnarray*}$ , aber wie sieht dann die Mächtigkeit der Mengen $\begin{eqnarray*} 2n-1 \end{eqnarray*}$ und $\begin{eqnarray*} 5n \end{eqnarray*}$ aus?

verwirrt

10.02.2012, 11:42

galoisseinbruder

Auf diesen Beitrag antworten »

Hallo,

dein Problem scheint zu sein, dass du nicht weißt was "gleichmächtig" heißt. Das solltest du nachschauen. Mit Induktion hat das sehr wenig zu tun.
Ach ja und 2n-1 und 5n sind keine Mengen, eher Terme. Was du meinst ist
$\begin{eqnarray*} \{2n-1|n \in \mathbb N, n \neq 0\} \end{eqnarray*}$ und ähnlich für die durch 5 teilbaren Zahlen.

10.02.2012, 12:10

OhneDurchblick

Auf diesen Beitrag antworten »

Na gleichmächtig heißt bei mir, dass in der Menge A genau so viele Elemente wie in der Menge B enthalten sind, oder?
Meine Menge A stelle ich mir nun eben durch diese Bildungsvorschrift "2n-1" vor, weil die eben, wenn ich für n die Zahlen 1 bis unendlich einsetze, alle ungeraden Zahlen auflistet.

So ist z.B.

$\begin{eqnarray*} 2*1-1=0 \end{eqnarray*}$ und auch

$\begin{eqnarray*} 2*2-1=3 \end{eqnarray*}$ und ebenso

$\begin{eqnarray*} 2*3-1=5 \end{eqnarray*}$ ein Element der Menge A.

Das gleiche gilt für meine gedachte Menge B mit allen Elementen, die die Vorschrift "5n" erfüllen.

Ich meine vermutlich genau das, was du schreibt, konnte es nur nicht in die schöne Sprache der Mathematik bringen Hammer

Nunja, aber wie beweise ich dies nun? Laut meinem Heft kann ich versuchen, eine Abbildungsvorschrift zu finden, die die eine Menge auf die andere Menge abbildet.
Ich muss also eine Abbildungsvorschrift finden, welche 2n-1 auf 5n abbildet?
Komme ich der Sache näher oder eher nicht?
Wir hatten das mal mit der Mächtigkeit von $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ gemacht, da war das irgendwie einfacher...

10.02.2012, 12:21

galoisseinbruder

Auf diesen Beitrag antworten »

2*1-1=0 wär mir neu, auch das 0 ungerade ist.

Zitat:

Laut meinem Heft kann ich versuchen, eine Abbildungsvorschrift zu finden, die die eine Menge auf die andere Menge abbildet.

Das ist immer noch nicht die exakte Defintion von Gleichmächtig: Zwei mengen sind gleichmächtig wenn es eine Bijektion zwischen ihnen gibt. Und wenn du deine Mengen sauber in Mengenschreibweise schreibst kannst du evtl eine solche Bijektion sehen.

Ich find´s hier aber angenehmer zu zeigen, dass beide Mengen gleichmächtig zu $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ sind (die Bijektionen sind offensichtlich, ausgehend, von $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ ) und sich dann kurz zu überlegen/nachzuschauen warum damit die Behauptung bereits bewiesen ist.

10.02.2012, 15:27

OhneDurchblick

Auf diesen Beitrag antworten »

Huch, richtig. Habe auf meinem Zettelchen bereits die 0 ausgeschlossen smile

Gut, was du sagst, klingt einleuchtend.
Würde es dann nicht reichen, die natürlichen Zahlen auf die ungeraden Zahlen (U) mittels

$\begin{eqnarray*} f:\mathbb N -> U : n->2n-1 \end{eqnarray*}$

abzubilden? (Sorry, finde den Abbildungspfiel nicht...) Das müsste doch die Gleichmächtigkeit der ungeraden natürlichen Zahlen und der natürlichen Zahlen im Sinne einer bijektiven Abbildung zeigen, oder?

Gleiches macht man schließlich für die Vielfachen der 5 (V) , also

$\begin{eqnarray*} f:\mathbb N -> V : n->5n \end{eqnarray*}$

Bijektive Abbildung und somit Gleichmächtigkeit zu $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ .
Dann behilft man sich mit Äquivalenzen?
Nun sind bejektive Abbildungen immer reflexiv, symmetrisch und transitiv, womit
für das letzte gelten sollte:

Wenn $\begin{eqnarray*} U \end{eqnarray*}$ gleichmächtig ist zu $\begin{eqnarray*} \mathbb N \end{eqnarray*}$
und $\begin{eqnarray*} V \end{eqnarray*}$ gleichmächtig ist zu $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ ,
dann ist doch auch $\begin{eqnarray*} U \end{eqnarray*}$ gleichmächtig zu $\begin{eqnarray*} V \end{eqnarray*}$ . Oder?
Sicher habe ich etwas nicht beachtet...

Achso,

$\begin{eqnarray*} U=\left\{2n-1|n\in \mathbb N \wedge n\geq 2\right\}=\left\{ ...1;3;5;7...\right\} \end{eqnarray*}$

und

$\begin{eqnarray*} V=\left\{ 5n|n\in \mathbb N \wedge n\neq 0 \right\}=\left\{...5;10;15;20...\right\} \end{eqnarray*}$

Ich könnte aber auch versuchen (jetzt mal in meiner laienhaften Sprache formuliert), die Zahlen aus U mit denen aus V in Verbindung zu bringen, sprich eine Rechenvorschrift zu finden, in die ich 1 einsetze und aus der 5 rauskommt, in die ich 3 einsetze und aus der 10 rauskommt, in die ich 5 einsetze und aus der 15 rauskommt etc., oder?

10.02.2012, 16:57

galoisseinbruder

Auf diesen Beitrag antworten »

Zitat:

Wenn $\begin{eqnarray*} U \end{eqnarray*}$ gleichmächtig ist zu $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} V \end{eqnarray*}$ gleichmächtig ist zu $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ , dann ist doch auch $\begin{eqnarray*} U \end{eqnarray*}$ gleichmächtig zu $\begin{eqnarray*} V \end{eqnarray*}$ . Oder? Sicher habe ich etwas nicht beachtet...

Nein, das ist so vollkomen richtig. Auch die f,g sind passende Abbildungen, allerdings hast du bis jetzt nur behauptet allerdings nicht bewiesen, dass diese bijektiv sind.

Zitat:

$\begin{eqnarray*} U=\left\{2n-1|n\in \mathbb N \wedge n\geq 2\right\}=\left\{ ...1;3;5;7...\right\} \end{eqnarray*}$

Hier hat sich (genauso wie beim 2.Fall) ein Fehler eingeschlichen, die hintere Menge ist $\begin{eqnarray*} \left\{ 1;3;5;7...\right\} \end{eqnarray*}$ , denn die Menge enthält keine kleineren Elemente als 1.

Und wenn du eine Bijektionen zwischen U und V haben willst: Verwende f und g, bei einer von beiden wird die Umkehrfunktion nötig sein.

10.02.2012, 18:16

OhneDurchblick

Auf diesen Beitrag antworten »

Ich danke dir für die Korrektur smile

Gut, so wirklich bewiesen habe ich nicht, vermutlich bin ich von der Aussage des Dozenten ausgegangen, die in einer anderen Ü zu finden war:

"Die Menge der natürlichen Zahlen N und die Menge der ganzen Zahlen Z ist gleichmächtig. Dies bedeutet, Sie müssten eine bijektive Abbildung f finden, welche
$\begin{eqnarray*} f:\mathbb N \Rightarrow Z \end{eqnarray*}$ abbildet. Geben Sie eine solche Abbildungsvorschrift an etc."

Nun dachte ich, wenn man zeigt, dass es eben eine solche Abbildungsvorschrift gibt, ist auch bewiesen, dass beide Mengen gleichmächtig sind.
Wenn nicht, wie mache ich das dann?
Beweise ich die Bijektivität durch Reflexivität, Symmetrie und Transitivität?

Sprich (R soll hier mal das nicht vorhandene Relationszeichen sein...)

1. $\begin{eqnarray*} u R u \end{eqnarray*}$ (die ungeraden natürlichen Zahlen und die ungeraden natürlichen Zahlen sind gleichmächtig, sieht logisch aus)

2. $\begin{eqnarray*} uR\mathbb N \Rightarrow \mathbb NRu \end{eqnarray*}$
Das habe ich ja theoretisch durch die Abbildung gezeigt, oder liegt hier mein Denkfehler? Wie oben gesagt dachte ich bis eben, dass die Gleichmächtigkeit zweier Mengen durch eine Abbildung der einen auf die andere gezeigt wird...Aber jetzt will ich Bijektivität beweisen und nutze sie gleichzeitig als Voraussetzung. Irgendwas ist hier faul...

3. wäre ja dann, dass $\begin{eqnarray*} u R \mathbb N \wedge N R v \Rightarrow u R v \end{eqnarray*}$

Hmpf, wie zermürbend. Danke übrigens, dass du dir die Zeit so von mir rauben lässt Augenzwinkern

Die Beweiserei ist nicht so mein Ding, wie mir scheint... unglücklich

10.02.2012, 18:23

galoisseinbruder

Auf diesen Beitrag antworten »

Zitat:

"Die Menge der natürlichen Zahlen N und die Menge der ganzen Zahlen Z ist gleichmächtig. Dies bedeutet, Sie müssten eine bijektive Abbildung f finden, welche $\begin{eqnarray*} f:\mathbb N \Rightarrow Z \end{eqnarray*}$ abbildet. Geben Sie eine solche Abbildungsvorschrift an etc."

Ich behaupte eine solche Abb. ist $\begin{eqnarray*} f:\mathbb N \to \mathbb Z ; n \to n \end{eqnarray*}$ . Ist es damit beweisen? Nein, denn die Abb. ist nicht surjektiv.

Und zum Rest: Dein Problem ist nicht die Beweiserei, sondern Defintionrn. Was soll denn hier die Relation sein verwirrt

Es ist aus gutem Grund nicht vorhanden) Bijektivität einer Funktion ist ganz anders definiert.

10.02.2012, 18:49

OhneDurchblick

Auf diesen Beitrag antworten »

Eieieiii...

Die Umkehrfunktion von $\begin{eqnarray*} f(n)=2n-1 \end{eqnarray*}$ ist $\begin{eqnarray*} f^-1(n)=1/2n+1/2 \end{eqnarray*}$ ??

Und von $\begin{eqnarray*} g(n)=n² \end{eqnarray*}$ ist es $\begin{eqnarray*} g^-1(n)=\sqrt{n} \end{eqnarray*}$ ???

Nun habe ich grad 2 Hilfssätze gefunden:

H1: Wenn die genannten Abbildungen f ung g bijektiv sind, so ist auch g°f bijektiv.

H2: Ist f bijektiv, so besitzt sie automatisch auch eine Umkehrfunktion $\begin{eqnarray*} f^-1 \end{eqnarray*}$ .

Nun zum Beweis in meinem Heft:

1. Reflexiv, wie ich vorhin schon gesagt habe. u ist gleichmächtig zu u.

2. Symmetrie. Hier steht:

$\begin{eqnarray*} A\equiv B = B\equiv A? \end{eqnarray*}$

siehe H2: bijektive Abbildung? Ja! Es gibt eine Umkehrfunktion, daraus folgt Symmetrie.

3. Transitivität

siehe H1: $\begin{eqnarray*} u R \mathbb N \wedge \mathbb N R v \Rightarrow uRv \end{eqnarray*}$
Es muss bijektiv sein.

Genau so wurde es in der VL unter der Überschrift "Gleichmächtigkeit von Mengen" gezeigt. Ich weiß auch nicht mehr weiter... unglücklich

10.02.2012, 18:54

OhneDurchblick

Auf diesen Beitrag antworten »

Achso ja, bijektiv ist eine Funktion natürlich dann, wenn sie injektiv UND surjektiv ist, aber das wurde in der VL gar nicht erwähnt, wenn es um die Gleichmächtigkeit von Mengen ging. Wir mussten immer nur eine Abbildungsvorschrift finden, die dann m.E.n. ohne Beweis von Bijektivität als Lösung galt. Jetzt bin ich verunsichert...

10.02.2012, 18:59

galoisseinbruder

Auf diesen Beitrag antworten »

Was soll das ganze mit reflexiv, transitiv und symmetrisch? Was soll das überhaupt erfüllen?

Mit g meinte ich übrigens die Abb.
$\begin{eqnarray*} f:\mathbb N -> V : n->5n \end{eqnarray*}$ , dachte beim drüberlesen du hättest sie g genannt, was auch sinnvoll wäre.

Darf ich fragen was das für eine Vorlesung aus welchem Studiengang ist?

10.02.2012, 19:12

OhneDurchblick

Auf diesen Beitrag antworten »

Das ist eine gute Frage, ich weiß es auch nicht. Habe nur versucht, es nach diesem Beispiel zu machen. Das andere Beispiel war ja die eingangs erwähnte Beweisführung mittels vollständiger Induktion, die ich genauso bescheiden finde.
Das Problem ist, dass der Dozent (im Übrigen noch jünger als ich und ich bin kein oller Feger...) die Übungsserien nicht richtig bespricht und meiner Meinung nach auch in anderen Vorlesungen viel zu kompliziert erklärt, obwohl er es gern ganz sportlich und simpel machen möchte. Ziel verfehlt, ich verstehe nämlich trotz Nacharbeiten nicht viel...

Klar darfst du fragen: Es geht um Zahlbereiche und gehört zur Nebenstudienrichtung Mathe für Grund- und Regelschule...

Das mit dem g habe ich verstanden, ist natürlich cleverer so Augenzwinkern

Ein weiteres Beispiel, dessen Begründung ich in der Kürze der Zeit nur notiert hatte:

"Die Menge der geraden natürlichen Zahlen und die Anzahl der natürlichen Zahlen > 100 sind gleichmächtig"

Aussage war, dass eine Bildungsvorschrift gegeben werden kann (die ich leider nicht vorliegen habe), daraus folgt, dass eine Zuordnung besteht und DARAUS folgt, dass Bijektivität und Gleichmächtigkeit gegeben ist. Wie er zu seiner Schlussfolgerung kommt, hat er nicht gesagt...

10.02.2012, 19:27

galoisseinbruder

Auf diesen Beitrag antworten »

Wenn es eurem Dozenten reicht nur die Abb. hinzuschreiben dann musst du das weitere nicht mehr beweisen, allerdings finde ich es dann schwierig sich sicher zu sein. Vielleicht hilft dir ja, dass eine Abbildung bijektiv ist genau dann wenn es eine Umkehrabb. gibt (was du für f ja bereits gezeigt hast.)
Allerdings scheinst du ein Riesenverständnisproblem mit den Beweisen zu haben. Es gibt verschiedene Beweistechniken wie z.B. Induktion. Diese lassen sich aber nicht immer in jedem Fall anwenden. Wir müssen hier nicht zeigen, dass eine relation eine äquivalenzrelation ist oder das eine Summenformel für beliebige n gilt.

zur weiteren Frage. Was ist denn bei euch eine Zuordnung?
Und "Die Menge der geraden natürlichen Zahlen und die Anzahl der natürlichen Zahlen > 100 sind gleichmächtig" kannst die wieder über jeweilige Bijektionen in die natürlichen zahlen relativ gut zeigen.

10.02.2012, 19:50

OhneDurchblick

Auf diesen Beitrag antworten »

Ja, das stimmt, Beweistechniken bereiten mir noch Probleme, obgleich ich in vorangegangenen Klausuren immer Glück hatte...
Klar muss ich keine Äquivalenzrelation beweisen (wo wir beim nächsten wunden Punkt angekommen sind...die quälen mich auch schon seit dem letzten Semester, allerdings hat sich mein Verständnis dahingehend etwas verbessert... Augenzwinkern

), nur finde ich mich offenkundig in meinen Aufzeichnungen nicht zurecht.

Mir geht das speziell in seinen Vorlesungen eindeutig zu schnell und die Erarbeitung erfolgt zu unübersichtlich. In anderen VL habe ich diese Probleme nicht, bei ihm weiß ich aber auch wegen der fehlenden Besprechungen und Lösungen nicht, woran ich bin. Alle anderen Profs stellen die Lösungen meist auch online, sodass man bei Verständnisprobs wie den meinen auch mal nachlesen kann.
Und er bespricht die Übungen gleich nur halbherzig, was für mich natürlich das Todesurteil ist...

Bei meinen Beispielen hatte ich mich grad daran orientiert, wie er damals argumentiert hatte, möglicherweise ist mir der ein oder andere Zusammenhang auch verloren gegangen...

Zur Zuordnung: Nunja, ich begebe mich auf Glatteis, würde aus dem Bauch heraus behaupten, es ist die Abbildung der Elemente aus einer Menge A auf die Elemente der Menge B. Hier also z.B. die Abbildung der natürlichen Zahlen n durch eine "Funktion" bzw. Abbildungsvorschrift, also z.B. 2n-1, in die Menge der ungeraden natürlcihen Zahlen. Der 1 aus den natürlichen Zahlen wird die 1, der 2 die 3, der 3 die 5 usw. "zugeordnet".

Neue Frage »

Antworten »

Beweis: Mengengleichheit

Verwandte Themen