Permutationen und Transpositionen - Beweis

Neue Frage »

ChronoTrigger Auf diesen Beitrag antworten »
Permutationen und Transpositionen - Beweis
Hallo,

bei dieser Aufgabe bin ich mir nicht sicher, ob ich sie richtig verstanden habe:

Zitat:

Sei und , eine bijektive Abbildung und .

Weiterhin ist die Vertauschungsabbildung für .

Sei Dann gibt es mit .

Zeige, dass für gilt:


Ich wollte das nun so zeigen:

.

Um nun zu zeigen, dass gilt, müsste es doch eigentlich ausreichen, dass

gilt.

Dafür sei





Wenn ich jetzt darauf anwende, erhalte ich


, und damit wäre und damit wäre die Teilmengenbeziehung gezeigt.

Habe ich das so richtig verstanden, oder bin ich mit meinen Überlegungen auf dem Holzweg?

danke schonmal im voraus.
zweiundvierzig Auf diesen Beitrag antworten »
RE: Permutationen und Transpositionen - Beweis
Zitat:
Original von ChronoTrigger

Damit könnte aber dennoch Gleichheit gelten.

Vielleicht hilft es, sich die Aufgabe mal in Worten klarzumachen: Ist kein Fixpunkt von so hat die Abbildung mehr Fixpunkte als . Hier kann man auch schon erahnen, welcher Fixpunkt genau dazukommt.

Zum Beweis genügt es, die Fixpunkte von klassifizieren. Wie lässt sich für die Bedingung noch schreiben? Für genau welche Punkte ist diese Gleichung dann erfüllt?

Edit: Übrigens geht es in der Betrachtung nicht um die Menge, die Du links notiert hast. Die ganze Abbildung wird in Abhängigkeit eines zu Beginn gewählten Nicht-Fixpunkts von definiert. Die Nicht-Fixpunktmenge von , die Du wohl eigentlich betrachten wolltest ist dann und nicht die von Dir oben genannte.
ChronoTrigger Auf diesen Beitrag antworten »

danke für die antwort.

Zitat:

Vielleicht hilft es, sich die Aufgabe mal in Worten klarzumachen: Ist kein Fixpunkt von so hat die Abbildung mehr Fixpunkte als . Hier kann man auch schon erahnen, welcher Fixpunkt genau dazukommt.


Der i-te Fixpunkt kommt immer durch die Transposition hinzu, wenn ich das richtig verstanden habe.

Zitat:
Wie lässt sich für die Bedingung noch schreiben? Für genau welche Punkte ist diese Gleichung dann erfüllt?


Für ist doch dann



und für und ist dann



jetzt ist mir allerdings nicht klar, in wie fern mich das weiterbringt.
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von ChronoTrigger
Der i-te Fixpunkt kommt immer durch die Transposition hinzu, wenn ich das richtig verstanden habe.

Besser gesagt, der Fixpunkt , ja.

Zitat:
Original von ChronoTrigger
Für ist doch dann



Freude

Hier sieht man den Beweis deiner obigen Behauptung, d.h. .

Was passiert denn noch in den verbleibenden Fällen, dass ein Fixpunkt von ist bzw. dass ein Nicht-Fixpunkt von ist?
ChronoTrigger Auf diesen Beitrag antworten »

Zitat:
Hier sieht man den Beweis deiner obigen Behauptung, d.h. .


um ehrlich zu sein, sehe ich hier momentan noch nichts. Könntest du mir das vielleicht noch einmal erklären?

Zitat:
Was passiert denn noch in den verbleibenden Fällen, dass ein Fixpunkt von ist bzw. dass ein Nicht-Fixpunkt von ist?


wenn k ein Fixpunkt von ist, gilt und dann

ist

und dann ist und

Wenn kein Fixpunkt von ist, gilt , dann ist ja auch

, dann muss aber oder gelten.

Irgendwie verstehe ich aber immer noch nicht, in wiefern mich das nun weiterbringt.
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von ChronoTrigger
Zitat:
Hier sieht man den Beweis deiner obigen Behauptung, d.h. .


um ehrlich zu sein, sehe ich hier momentan noch nichts. Könntest du mir das vielleicht noch einmal erklären?

Ich schreibe im folgenden . Es gilt . Was kommt dabei heraus?

Zitat:
Original von ChronoTrigger
wenn k ein Fixpunkt von ist, gilt und dann

ist

und dann ist und

Am Ende gehst Du einen Schritt zurück: wenn ein Fixpunkt von ist, folgt sofort, dass sein muss, da als Nicht-Fixpunkt vorausgesetzt ist. Berechne doch mal .

Zitat:
Original von ChronoTrigger
Wenn kein Fixpunkt von ist, [...] dann ist ja auch

[...]

Denk' darüber lieber nochmal nach. Sei ein Nicht-Fixpunkt von . Was gilt für im Falle von bzw. ?
 
 
ChronoTrigger Auf diesen Beitrag antworten »

Zitat:
Ich schreibe im folgenden . Es gilt . Was kommt dabei heraus?


ahh, da kommt natürlich i raus, das macht sinn smile

und daraus folgt ja dann bereits die behauptung, da wir dann einen Fixpunkt haben, und die Menge der Nicht-Fixpunkte somit definitiv schon weniger Elemente enthält.


Zitat:

Am Ende gehst Du einen Schritt zurück: wenn ein Fixpunkt von ist, folgt sofort, dass sein muss, da als Nicht-Fixpunkt vorausgesetzt ist. Berechne doch mal .


k ist ein Fixpunkt von , d.h. , und damit (wie in deiner Notation)
mit der Begründung aus deinem post.

also ist , also ist k ein Fixpunkt von und damit kann die Menge der Nicht-Fixpunkte von nur weniger Elemente als die Menge der Nicht-Fixpunkte von enthalten.


Zitat:
Denk' darüber lieber nochmal nach. Sei ein Nicht-Fixpunkt von . Was gilt für im Falle von bzw. ?


Wenn also gilt und k kein Fixpunkt von ist, also wenn gilt, dann gilt im Falle von , dass






falls gilt, ist , darüber kann ich doch sonst nichts weiter aussagen.






ist es eigentlich Absicht, dass wir die ganze Zeit von einem sprechen? Denn in der aufgabenstellung ist das k ja schon anderweitig definiert, was etwas verwirrend ist.
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von ChronoTrigger
Zitat:
Ich schreibe im folgenden . Es gilt . Was kommt dabei heraus?


ahh, da kommt natürlich i raus, das macht sinn smile

und daraus folgt ja dann bereits die behauptung, da wir dann einen Fixpunkt haben, und die Menge der Nicht-Fixpunkte somit definitiv schon weniger Elemente enthält.

Richtig, . Aber daraus folgt noch nicht, dass wirklich mehr Fixpunkte hat, schließlich müssen wir noch zeigen, dass es auch die Fixpunkte von festlässt.

Zitat:
Original von ChronoTrigger
k ist ein Fixpunkt von , d.h. , und damit (wie in deiner Notation)
mit der Begründung aus deinem post.

also ist , also ist k ein Fixpunkt von [...]

Hier hattest Du wohl oben versehentlich statt geschrieben? Die weitere Folgerung ist jedenfalls richtig.

Zitat:
Original von ChronoTrigger
falls gilt, ist , darüber kann ich doch sonst nichts weiter aussagen.

Das hatte ich vielleicht etwas verwirrend ausgedrückt. Sei also ein Nicht-Fixpunkt von mit . Was gilt dann für ?

Zitat:
Original von ChronoTrigger
ist es eigentlich Absicht, dass wir die ganze Zeit von einem sprechen? Denn in der aufgabenstellung ist das k ja schon anderweitig definiert, was etwas verwirrend ist.

Stimmt, sorry, ist angesichts der Definition in der Aufgabe eine unglückliche Bezeichnung. Allerdings hatten wir im weiteren diese Definition auch nicht mehr explizit benutzt, sodass es keine Verwirrungen gab. Augenzwinkern

Edit: Fehler in Formel verbessert.
ChronoTrigger Auf diesen Beitrag antworten »

Zitat:
Richtig, . Aber daraus folgt noch nicht, dass wirklich mehr Fixpunkte hat, schließlich müssen wir noch zeigen, dass es auch die Fixpunkte von festlässt.


ah, alles klar.


Zitat:
Hier hattest Du wohl oben versehentlich statt geschrieben? Die weitere Folgerung ist jedenfalls richtig.


ja, das war wohl ein tippfehler von mir geschockt


Zitat:
Das hatte ich vielleicht etwas verwirrend ausgedrückt. Sei also ein Nicht-Fixpunkt von mit . Was gilt dann für ?


dann müsste doch gelten, oder?
dann ist k also auch kein Fixpunkt von .
zweiundvierzig Auf diesen Beitrag antworten »

Richtig. smile
ChronoTrigger Auf diesen Beitrag antworten »

Ich glaube, ich habe es nun verstanden.

danke für deine Hilfe !
zweiundvierzig Auf diesen Beitrag antworten »

Gern geschehen. Freut mich, dass ich Dir helfen konnte. smile
Neue Frage »
Antworten »



Verwandte Themen

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