Äquivalenzrelation beweisen

03.11.2012, 15:20

WunderWutz

Auf diesen Beitrag antworten »

Äquivalenzrelation beweisen

Hey also ich habe hier eine Aufgabe die ich nicht im geringsten verstehe.
Vielleicht kann mir ja jmd von euch weiterhelfen...

Angabe:
Für zwei Mengen B,Z schreiben wir B~Z, falls sie gleichmächtig sind. Beweise, dass
dies eine Äquivalenzrelation auf der Menge aller Mengen definiert.

So, was ich weis:
gleichmächtig heißt, dass die Mengen die selbe Anzahl von Elementen bestitzen.
Äuqivalenzrelation ist es wenn Vx,y,z € Z? gilt: Reflexivität, Symetrie und Transitivität.
x~x
x~y -> y~x
x~y und y~z -> x~z

Wie soll ich das jetzt beweisen? Ohne Angaben finde ich dazu einfach keinen Ansatz. Oder soll ich einfach wieder ein x,y,z annehmen?
Und der Teil: auf der Menge aller Mengen definiert. häää Was soll damit gemeint sein?

03.11.2012, 15:46

Mulder

Auf diesen Beitrag antworten »

RE: Äquivalenzrelation beweisen

Zitat:

Original von WunderWutz
Und der Teil: auf der Menge aller Mengen definiert.

Naja, das heißt genau das. Betrachtet werden alle Mengen, die es gibt. Diese bilden ja auch wieder eine Menge. Und die gegebene Relation, die wir hier betrachten, ist eben die Gleichmächtigkeit.

Argumentieren kannst du damit, dass zwischen zwei Mengen gleicher Mächtigkeit immer eine Bijektion existiert. Das ist die eigentliche Definition.

Zitat:

x~x
x~y -> y~x
x~y und y~z -> x~z

Ja, dann mal ran an den Speck. x,y,z sind in diesem Fall halt Mengen.

Zitat:

gleichmächtig heißt, dass die Mengen die selbe Anzahl von Elementen bestitzen.

Bei endlichen Mengen kann man das so sagen. Bei Mengen mit unendlich vielen Elementen ist diese Formulierung natürlich schwierig.

03.11.2012, 17:59

WunderWutz

Auf diesen Beitrag antworten »

Zitat:

Original von Mulder

Argumentieren kannst du damit, dass zwischen zwei Mengen gleicher Mächtigkeit immer eine Bijektion existiert. Das ist die eigentliche Definition.

Aber es muss doch nicht immer eine Bijektion gegeben sein? Ich kann doch frei bestimmen von welchem Element ich auf ein anderes Abbilde, ich könnte doch jetzt auch von 5 Elementen der Bildmenge auf eines der Zielmenge abbilden, so wie ich das verstanden habe...

Zitat:

Original von Mulder
Ja, dann mal ran an den Speck. x,y,z sind in diesem Fall halt Mengen.

Heißt das, dass ich jeztzt nicht mit transivität usw arbeiten soll sonern mit surjek, injek usw?
Aber die sind doch nur für Abbildungen vorhanden oder nicht?
Wie soll ich damit anfangen?

03.11.2012, 18:07

Mulder

Auf diesen Beitrag antworten »

Zitat:

Original von WunderWutz
Aber es muss doch nicht immer eine Bijektion gegeben sein? Ich kann doch frei bestimmen von welchem Element ich auf ein anderes Abbilde, ich könnte doch jetzt auch von 5 Elementen der Bildmenge auf eines der Zielmenge abbilden, so wie ich das verstanden habe...

Entscheidend ist nur: Es GIBT eine. Natürlich ist nicht jede Abbildung eine Bijektion. Aber wenn zwei Mengen die gleiche Mächtigkeit besitzen, dann existiert eine Bijektion zwischen diesen beiden Mengen, wie auch immer die nun aussehen mag (das interessiert uns gar nicht). Hauptsache es gibt mindestens eine. Unter all den unendlich vielen Abbildungen, die man "zwischen" zwei Mengen definieren kann, muss halt eine dabei sein, die bijektiv ist.

Beispiel: $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ sind nicht gleichmächtig, das heißt, es gibt keine Bijektion zwischen diesen beiden Mengen. Da kannst du dich auf den Kopf stellen, du wirst keine Bijektion finden.

Zitat:

Original von WunderWutz
Heißt das, dass ich jeztzt nicht mit transivität usw arbeiten soll sonern mit surjek, injek usw?
Aber die sind doch nur für Abbildungen vorhanden oder nicht?

Wie gesagt: "Zwei Mengen haben die gleiche Mächtigkeit" und "es gibt eine Bijektion zwischen diesen beiden Mengen" sind äquivalente Aussagen. Irgendwie müsst ihr den Begriff "Mächtigkeit" doch auch eingeführt haben.

Und natürlich musst du transtiv, symmetrisch und reflexiv nachweisen. Du benutzt eben die Existenz einer Bijektion um das zu zeigen. Wie willst du das sonst machen?

Um zum Beispiel zu zeigen, dass die Relation reflexiv ist, zeigst du halt für irgendeine Menge X:

$\begin{eqnarray*} |X|=|X| \end{eqnarray*}$

Dass das richtig ist, liegt ja nahe, aber du zeigst es, indem du eine konkrete Bijektion von X nach X angibst. Da gibt es ja eine ganz einfache Abbildung, die man da nehmen kann.

03.11.2012, 19:01

WunderWutz

Auf diesen Beitrag antworten »

Zitat:

Original von Mulder
Wie gesagt: "Zwei Mengen haben die gleiche Mächtigkeit" und "es gibt eine Bijektion zwischen diesen beiden Mengen" sind äquivalente Aussagen. Irgendwie müsst ihr den Begriff "Mächtigkeit" doch auch eingeführt haben.

Und natürlich musst du transtiv, symmetrisch und reflexiv nachweisen. Du benutzt eben die Existenz einer Bijektion um das zu zeigen. Wie willst du das sonst machen?

Um zum Beispiel zu zeigen, dass die Relation reflexiv ist, zeigst du halt für irgendeine Menge X:

$\begin{eqnarray*} |X|=|X| \end{eqnarray*}$

Dass das richtig ist, liegt ja nahe, aber du zeigst es, indem du eine konkrete Bijektion von X nach X angibst. Da gibt es ja eine ganz einfache Abbildung, die man da nehmen kann.

aha, also ich kann das mischen, bijektion und reflexiv und co. ? okay...

Aber ich verstehe nicht weshalb ich da mit Bijektionen arbeiten muss?/soll, denn die sind doch nur bei Abbildungen vorhanden und hier habe ich doch gar keine?!

Mächtigkeit:
zwei Mengen M und N sind gleichmächtig, falls eine bijektive Abb f M->N gilt.
Ahh okay und in der angabe steht ja, gleichmächtig also müssen die bijektiv sein, laut obiger Def.

Zitat:

Original von Mulder
Wie willst du das sonst machen?

Wenn ich nach Eigenschaften oder Mächtigkeit einer Menge googel komm ich immer nur zu surj usw, ...

Hmm wenn die Mengen X und Y gleich viele Elemente haben sind sie gleichmächtig.

reflex: $\begin{eqnarray*} |B|=|B| \end{eqnarray*}$
$\begin{eqnarray*} |Y|=|Y| \end{eqnarray*}$

sym.: $\begin{eqnarray*} |B|=|Y| -> |Y|=|B| \end{eqnarray*}$

trans.: $\begin{eqnarray*} |B|=|Y| und|Y|=|Z| -> |B|=|Z| \end{eqnarray*}$

Wie soll ich mit diesen Bedingungen jetzt etwas Beweisen?...

Zitat:

Original von Mulder
Da gibt es ja eine ganz einfache Abbildung, die man da nehmen kann.

f: B->Z ?

03.11.2012, 19:17

Mulder

Auf diesen Beitrag antworten »

Zitat:

Original von WunderWutz
f: B->Z ?

Was soll das jetzt sein? Das ist eine Abbildung, ja. Und was fängt man damit nun an? Bitte auch ein wenig im Auge behalten, wo man überhaupt hin will.

Also, sei B eine Menge. Wir wollen zeigen:

$\begin{eqnarray*} |B|=|B| \end{eqnarray*}$

Wir nehmen uns nun einfach mal die identische Abbildung auf B:

$\begin{eqnarray*} f= \mathrm{id}_B \end{eqnarray*}$

Egal, was B nun für eine Menge ist, eine solche Abbildung kann man immer konstruieren. Die bildet nun also jedes b aus B wieder auf b ab, also:

$\begin{eqnarray*} f: B \mapsto B \, , \, b \mapsto b \end{eqnarray*}$

Diese Abbildung ist sicher bijektiv. Also ist B gleichmächtig zu B. Weil es eben diese eine Bijektion gibt. Es mag auch noch andere Bijektionen geben, aber das juckt uns nicht. Uns reicht eine.

Fertig.

Jetzt überleg dir mal was, um Symmetrie und Transitivität zu beweisen.

Anzeige

03.11.2012, 20:11

WunderWutz

Auf diesen Beitrag antworten »

Zitat:

Original von Mulder
Was soll das jetzt sein? Das ist eine Abbildung, ja. Und was fängt man damit nun an? Bitte auch ein wenig im Auge behalten, wo man überhaupt hin will.

Ich soll etwas beweisen aber wohin ich damit soll....

Zitat:

Original von Mulder
Also, sei B eine Menge. Wir wollen zeigen:

$\begin{eqnarray*} |B|=|B| \end{eqnarray*}$

Wir nehmen uns nun einfach mal die identische Abbildung auf B:

$\begin{eqnarray*} f= \mathrm{id}_B \end{eqnarray*}$

Ist dieses iD wichtig? oO
In der Vorlesung wurde das nämlich nur genau dreimal erwähnt aber was das ist kann ich daraus nicht schließen.. nur dass hat er dazu erwähnt:
F={(x,x) x€D} <DxD ; und das was im {} steht ist iD
id^-1 = {(y,y), y€D} : id ist also id^-1 Abb; aha..... :-\
Und irgendwas mit Komposition steht auch noch da.

Lt. google ist eine identische Abbildung eine Funktion, die genau ihr Argument zurückgibt.
Ich hab zwar keine Ahnung was jetzt mit Argument gemeint ist, aber wenn ich es in bezug zu Informatik bringe, dann gibt sie mir das was ich übergebe (id(x) ->x) wieder zurück?
Dann wäre sie doch etwas nutzlos oder etwa nicht?

lt. Youtube:
Eine Menge die auf sich selbst abgebildet wird mit der Eigenschaft, dass sie jedes einzelne Element auch auf sich selbst abbildet.
noch immer Nutzlos?

Zitat:

Original von Mulder
Egal, was B nun für eine Menge ist, eine solche Abbildung kann man immer konstruieren. Die bildet nun also jedes b aus B wieder auf b ab, also:

$\begin{eqnarray*} f: B \mapsto B \, , \, b \mapsto b \end{eqnarray*}$

Diese Abbildung ist sicher bijektiv. Also ist B gleichmächtig zu B. Weil es eben diese eine Bijektion gibt. Es mag auch noch andere Bijektionen geben, aber das juckt uns nicht. Uns reicht eine.

Fertig.

Jetzt überleg dir mal was, um Symmetrie und Transitivität zu beweisen.

03.11.2012, 20:29

WunderWutz

Auf diesen Beitrag antworten »

Hmm wenn ichs einfach so mache wie du, dann:

$\begin{eqnarray*} f: B \mapsto Y \, , \, b \mapsto y -> f: Y \mapsto B \, , \, y \mapsto b \end{eqnarray*}$

$\begin{eqnarray*} f: B \mapsto Y \, , \, b \mapsto y AND Y \mapsto Z \, , \, y \mapsto z -> f: B \mapsto Z \, , \, b \mapsto z \end{eqnarray*}$

Das wäre doch dann 1zu1 das gleiche, wie du es gemacht hast.

03.11.2012, 21:18

Mulder

Auf diesen Beitrag antworten »

Zitat:

Original von WunderWutz
Ich hab zwar keine Ahnung was jetzt mit Argument gemeint ist, aber wenn ich es in bezug zu Informatik bringe, dann gibt sie mir das was ich übergebe (id(x) ->x) wieder zurück?
Dann wäre sie doch etwas nutzlos oder etwa nicht?

Die identische Abbildung mag nicht sonderlich spektakulär erscheinen, aber sie ist doch nicht nutzlos. Wir haben sie doch jetzt gerade eben gebraucht, um zu beweisen, dass die Relation reflexiv ist. Damit hat sie ihren Nutzen doch gerade eben schon unter Beweis gestellt.

Hast du dich in der Schule auch immer beschwert, wenn du in irgendeiner Form mal mit der Funktion f(x)=x arbeiten musstest?

Mit dem "Argument" einer Abbildung ist einfach das Urbild gemeint. Also das Element aus dem Definitionsbereich. Also das, was in die Funktion "eingesetzt" wird. Und genau das tut die identische Abbildung: Sie bildet das Argument auf sich selbst ab, schickt also jedes Element x aus dem Definitionsbereich wieder auf x.

Zitat:

Original von WunderWutz
Hmm wenn ichs einfach so mache wie du, dann:

$\begin{eqnarray*} f: B \mapsto Y \, , \, b \mapsto y -> f: Y \mapsto B \, , \, y \mapsto b \end{eqnarray*}$

$\begin{eqnarray*} f: B \mapsto Y \, , \, b \mapsto y AND Y \mapsto Z \, , \, y \mapsto z -> f: B \mapsto Z \, , \, b \mapsto z \end{eqnarray*}$

Das wäre doch dann 1zu1 das gleiche, wie du es gemacht hast.

Das ist doch sinnlos, was da steht. Da hast du doch jetzt überhaupt nichts gemacht. Das sind einfach irgendwelche sehr seltsamen Abbildungsvorschriften. Und was sollen wir damit jetzt anfangen?

Du musst dir schon ein bisschen Gedanken machen: Was will ich zeigen? Was habe ich an Voraussetzungen? Was ist gegeben? Wo will ich hin? Was müsste ich dafür zeigen?

Zur Symmetrie: Seien X,Y zwei Mengen. Wir wollen zeigen: Ist X gleichmächtig zu Y, so ist auch Y gleichmächtig zu X.

Sei also X gleichmächtig zu Y.

Dann gibt es.... was?

-> führe diese Gedanken nun weiter.

03.11.2012, 21:42

WunderWutz

Auf diesen Beitrag antworten »

Zitat:

Original von Mulder
Hast du dich in der Schule auch immer beschwert, wenn du in irgendeiner Form mal mit der Funktion f(x)=x arbeiten musstest?

Nein, warum auch? Ich setze einfach nen Wert für eine Variable ein die in einer Gleichung steht.

Zitat:

Original von Mulder
Mit dem "Argument" einer Abbildung ist einfach das Urbild gemeint. Also das Element aus dem Definitionsbereich. Also das, was in die Funktion "eingesetzt" wird. Und genau das tut die identische Abbildung: Sie bildet das Argument auf sich selbst ab, schickt also jedes Element x aus dem Definitionsbereich wieder auf x.

also wenn ich 2 Mengen habe und von der menge a auf b abbilde.
Und darin von der Menge a das Element x auf das El y auf b abilde.
id(y) -> dann bekomme ich x raus? Warum nicht gleich das Urbild bzw Umkehrfunktion?

Zitat:

Original von Mulder
Das ist doch sinnlos, was da steht. Da hast du doch jetzt überhaupt nichts gemacht. Das sind einfach irgendwelche sehr seltsamen Abbildungsvorschriften. Und was sollen wir damit jetzt anfangen?

Hatte ich schon fast gedacht.... Aber dachte halt da du auch "einfach so" reflexivität gezeigt hast, dachte ich das es das ist was ich machen soll.

Zitat:

Original von Mulder
Du musst dir schon ein bisschen Gedanken machen: Was will ich zeigen? Was habe ich an Voraussetzungen? Was ist gegeben? Wo will ich hin? Was müsste ich dafür zeigen?

Gut, wo will ich denn bitte hin?
Ich wills beweisen aber weiter....

Zitat:

Original von Mulder
Zur Symmetrie: Seien X,Y zwei Mengen. Wir wollen zeigen: Ist X gleichmächtig zu Y, so ist auch Y gleichmächtig zu X.

Sei also X gleichmächtig zu Y.

Dann gibt es.... was?

-> führe diese Gedanken nun weiter.

Wenn X, Y gleichmächtig sind dann sind sie bijektiv.

03.11.2012, 21:56

Mulder

Auf diesen Beitrag antworten »

So langsam weiß ich ehrlich nicht mehr weiter... unglücklich

unglücklich

Irgendwie kommt nichts von dem, was ich sage, bei dir an. Entweder ich bin wirklich grottenschlecht im Erklären, oder... tja.

Zitat:

Original von WunderWutz
also wenn ich 2 Mengen habe und von der menge a auf b abbilde.
Und darin von der Menge a das Element x auf das El y auf b abilde.
id(y) -> dann bekomme ich x raus? Warum nicht gleich das Urbild bzw Umkehrfunktion?

Ich weiß nicht, was da jetzt id(y) heißen soll. Einerseits redest du - allem Anschein nach - von einer Abbildung, die von A nach B abbilden soll (jedenfalls hast du die Mengen so genannt), schreibst dann aber irgendwas von id(y). Die letzte Frage verstehe ich nichtmal ansatzweise.

Vielleicht schaust du nochmal bei Wikipedia nach: Identische Abbildung.

Dieses id ist doch auch nur eine Kurzschreibweise für eine besondere Abbildung. Wenn dich das stört, dann lass es halt weg und nenn die Abbildung irgendwie anders.

Zitat:

Original von WunderWutz
Wenn X, Y gleichmächtig sind dann sind sie bijektiv.

Wieder falsch. Mengen sind nicht bijektiv. Abbildungen können bijektiv sein.

Ich hatte die Antwort auf meine Frage ja eigentlich weiter oben auch schon ungefähr 10 Mal selbst beantwortet. Nun denn:

Ist X gleichmächtig zu Y, so gibt es eine bijektive Abbildung f: X -> Y.

Gibt es dann denn auch eine bijektive Abbildung von Y nach X?

03.11.2012, 22:35

WunderWutz

Auf diesen Beitrag antworten »

Zitat:

Original von Mulder
So langsam weiß ich ehrlich nicht mehr weiter... unglücklich

unglücklich

Irgendwie kommt nichts von dem, was ich sage, bei dir an. Entweder ich bin wirklich grottenschlecht im Erklären, oder... tja.

Keine Ahnung... das sind einfach nur die Antworten die ich mit Hilfe von Google und meinen Mitschriften finden konnte....... >.<

Zitat:

Original von Mulder
Ich weiß nicht, was da jetzt id(y) heißen soll. Einerseits redest du - allem Anschein nach - von einer Abbildung, die von A nach B abbilden soll (jedenfalls hast du die Mengen so genannt), schreibst dann aber irgendwas von id(y). Die letzte Frage verstehe ich nichtmal ansatzweise.

Vielleicht schaust du nochmal bei Wikipedia nach: Identische Abbildung.

Ja, habe ebenfalls Wikipedia verwendet.
Und wenn ich mir das so durchlese, dann komme ich auf die oben geschriebene Definition.
Das ist doch komplett das gleiche wie ich oben schreibe nur mit anderen Variablen.

Zitat:

Original von Mulder
Wieder falsch. Mengen sind nicht bijektiv. Abbildungen können bijektiv sein.

Okay

Zitat:

Original von Mulder

Ich hatte die Antwort auf meine Frage ja eigentlich weiter oben auch schon ungefähr 10 Mal selbst beantwortet. Nun denn:

Ist X gleichmächtig zu Y, so gibt es eine bijektive Abbildung f: X -> Y.

Gibt es dann denn auch eine bijektive Abbildung von Y nach X?

Mächtigkeit:
zwei Mengen M und N sind gleichmächtig, falls eine bijektive Abb f M->N gilt.

Hmm, wenn ich mir das so anschaue, dann ... nur wenn ich die Umkehrfunktion anwende oder?
Denn ich bilde ja was von M auf N ab und das ist bijektiv und wenn ich dann von der anderen Seite zu M gehe dann muss ich die Umekehrfuktion bilden und die wäre dann auch bijektiv.
?

03.11.2012, 22:51

Mulder

Auf diesen Beitrag antworten »

Zitat:

Original von WunderWutz
Hmm, wenn ich mir das so anschaue, dann ... nur wenn ich die Umkehrfunktion anwende oder?
Denn ich bilde ja was von M auf N ab und das ist bijektiv und wenn ich dann von der anderen Seite zu M gehe dann muss ich die Umekehrfuktion bilden und die wäre dann auch bijektiv.

Die Umkehrfunktion ist genau das richtige Stichwort, ja.

Ist X gleichmächtig zu Y und ist f:X->Y eine passende Bijektion, so ist die Umkehrfunktion f^(-1):Y->X ebenfalls bijektiv und damit auch Y gleichmächtig zu X.

Das war's schon.

03.11.2012, 23:11

WunderWutz

Auf diesen Beitrag antworten »

Hmm okay..

Dann muss ich noch Transivität beweisen......

Wenn ich das aufzeichne:
f: B->Z und f: Z->C dann muss auch f: B->C gleichmächtig sein.

Lass mich raten, falsch?

03.11.2012, 23:16

Mulder

Auf diesen Beitrag antworten »

Zitat:

Original von WunderWutz
Wenn ich das aufzeichne:
f: B->Z und f: Z->C dann muss auch f: B->C gleichmächtig sein.

Zunächst mal ist es höchst unglücklich, die Abbildungen alle gleich zu benennen. Du kennst doch sicher noch ein paar mehr Buchstaben außer f. Dann kann der Leser das auch besser unterscheiden.

Aber auch sonst kann man damit aber nichts anfangen. Formuliere mal vernünftig aus, was du eigentlich vor hast, bzw. machst.

04.11.2012, 16:14

WunderWutz

Auf diesen Beitrag antworten »

okay..
Ich würde sagen:
f: M->N
g: N-> Z
dann muss auch gelten das m gleichmächtig ist wie Z, also für die Aquivalenzrelation symetrisch ist.

Das einzige, was ich in meiner Mitschrift dazu finde wäre die Komposition:

f o g : M->Z
Das ist dann doch sozusagen die Weiterleitung von dem Element in M auf das abgebildete in Z.
Also ist das symetrisch?!
Kann ich damit etwas anfangen?

10.11.2012, 16:32

Mulder

Auf diesen Beitrag antworten »

Mist, diesen Thread habe ich jetzt völlig aus den Augen verloren, tut mir leid. Wahrscheinlich eh schon zu spät, aber der Vollständigkeit halber:

Zitat:

Original von WunderWutz
f o g : M->Z
Das ist dann doch sozusagen die Weiterleitung von dem Element in M auf das abgebildete in Z.
Also ist das symetrisch?!
Kann ich damit etwas anfangen?

Ja, die Komposition ist hier der Punkt. Denn die Komposition bijektiver Abbildungen ist ebenfalls wieder bijektiv, also ist das eine Bijektion von M nach Z. Damit sind M und Z gleichmächtig.

Allerdings musst du hier natürlich g°f schreiben. Nicht f°g.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »