0 Daumen
240 Aufrufe

Aufgabe:

Sei \(X\) eine endliche Menge und $$f:X→X$$ eine bijektive Abbildung. 

Zeigen Sie, dass es eine natürliche Zahl gibt mit \(f^n = idx.\)



Was weiss ich?
1. Da \(X\) endlich ist, kann ich sagen, dass die Mächtigkeit von \(X\), also \(|X|=n\) ist.

2. f ist injektiv. Das heisst, dass es zu jedem Element x aus X höchstens ein f(x)=y aus Y in meinem Fall X gibt.

3. f ist surjektiv. Das heisst, dass es zu jedem Element y aus Y ein x aus X gibt mit f(x) = y.

4. f ist bijektiv. Das heisst, dass (2) und (3) gelten, also dass jedes Element aus Y abgedeckt ist und zwei ungleiche Elemete aus X jeweils zwei verschiedene Bilder unter f haben.



Problem/Ansatz:
Intuitiv ist es ziemlich klar, dass es eine bijektive abbildung gibt mit f(x) = idx, nämlich dann, wenn jedes Element auf sich selbst abgebildet wird. 
Weiter kann es aber meiner Meinung mehr als eine solche bijektive Abbidlung geben. (und ich glaube die Aufgabe fragt danach) 
Also dann, wenn f hintereinander f(f(f(x))) oder hin und her (f(f-1(f(x))) geschaltet wird und dabei die Zuordnung so gewählt wird, dass immer idx dabei rauskommt.


Aber bereits hier hört mein wissen und meine Vorstellungskraft auf. 



Frage:Wie gehe ich nun vor um so etwas zu zeigen ?

Avatar von

2 Antworten

+1 Daumen

f ist also eine Permutation der Elemente von M.

Die Menge aller Permutationen bildet eine (endliche) Gruppe.

In jeder endlichen Gruppe, hat jedes Element a eine Ordnung,

das ist die kleinste nat. Zahl k, für die  a^k = e (neutr. El) gilt.

Die Ordnung von f ist das gesuchte n aus deiner Aufgabe.

Falls ihr das mit der Ordnung noch nicht bewiesen habt:

Betrachte in der Gruppe der Permutationen von M die

Potenzen von f. Da die Gruppe endlich ist ( Anzahl

ist die Fakultät von |M| ) gibt es irgendwann zwei Potenzen,

die gleich sind, etwa   f^k = f^h mit k<h.

         ==>    f^k = f^k * f^(h-k)

multipliziere von links mit dem Inversen von f^k und erhalte

                    id = f^(h-k) .

Avatar von 287 k 🚀

Okay, das mit dem Begriff Permutation sehe ich nicht, 

kann man sagen, dass eine Bijektive Abbildung eine Permutation, also eine Vertauschung der Zahlen ist ?

Vielen Dank !

+1 Daumen

Geben wir den n Elementen Hausnummern von #1 bis #n. und zwar so, dass #1  mittels f auf #2, dann #2 mittels f2 auf #3 und schließlich #n mittels fn auf #n+1 abgebildet wird. Ein Element #n+1 muss bereits unter #1 bis #n vorgekommen sein.

Avatar von 123 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community