Ein kleiner Beweis aus der Analysis. - Brauche Hilfe.

Question

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 ?

Answer 1

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) .

Comments

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 !

Answer 2

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