Zeigen Sie folgende Aussagen zur Bijektion und dem Schubfachprinzip.

Question

Aufgabe:

Es sei \( M \) eine Menge mit endlich vielen Elementen und \( f: M \rightarrow M \) eine Abbildung. Zeigen Sie folgende Aussagen:

b) Es existieren natürliche Zahlen \( k, l \in \mathbb{N}, \) sodass \( f^{k}(x)=f^{k+l}(x) \) für alle \( x \in M \) gilt.

c) Ist \( f \) bijektiv, so existiert ein \( k \in \mathbb{N} \) mit \( f^{k}=\mathrm{id}_{M} . \) Dabei bezeichnet id \( _{M}: M \rightarrow M \) die identische Abbildung.

Problem/Ansatz:

Ich habe gerade Probleme, diese Aufgaben zu lösen. Vielleicht sind da Verständnismängel im Bereich von Endlichen Mengen und Homomorphismen. Ich habe gezeigt dass f bijektiv ist in einer anderen Aufgabe. Anscheinend sollte man bei der b das Schubfachprinzip anwenden. Wie sollte man das dort machen ?

für die Hilfe.

Comments

Was soll \(f^k(x)\) sein? Die k'te Ableitung sicher nicht. Oder ist damit \(f(f(f( \dots f(x) \dots )))\) und das k-mal gemeint?

---

Es ist das zweite

---

Ist noch jemand da ? Entschuldige das weitere Kommentar.

---

Ist noch jemand da ? Entschuldige das weitere Kommentar.

gibt's nichts zu entschuldigen - passt schon ;-)

Wir sind noch da und ich für meinen Teil denke auch noch drüber nach. Habe aber keinen Gedanken, der für eine Antwort taugt. Beim Schubfachprinzip gilt es, die Schubfächer zu finden ... der Rest ist dann meist ganz einfach.

Btw.: Ist bei b) die Bijektivität von \(f(x)\) bereits voraus gesetzt?

---

Leider nicht, aber in der a) welche nicht hier vorhanden ist hab ich gezeigt, dass wenn f injektiv (bzw. Surjektiv ist), dass f surjektiv (injektiv ist)

Answer 1

zu b)

Sei \(n\) die Anzahl der Elemente von \(M\). Dann gibt es \(n^n\) verschiedene

Abbildungen \(M\rightarrow M\). Nach dem Schubfachprinzip muss also

eine dieser Abbildungen unter den \(f^1,f^2,\cdots,f^{n^n+1}\) zweimal vorkommen.

Sei dies bei \(f^k\) und \(f^j\) der Fall und oBdA \(l:=j-k\gt 0\), dann gilt

\(f^k=f^{k+l}\), q.e.d.

zu c)

Sei \(f\) eine Bijektion. Nach b) gibt es nat. Zahlen \(k,l>0\) mit

\(f^k=f^{k+l}\). Da die Bijektionen von \(M\) auf sich eine Gruppe bilden,

können wir diese Gleichung mit \(f^{-k}\) (von links oder rechts)

multiplizieren und erhalten \(f^l=id_M\) mit \(l>0\), q.e.d.