Sei A eine endliche Menge und f_i(a) = f(f_i-1(a)) mit f_0(a) = a, folgende Aussagen aquivalent

Question

ich bin gerade am Wiederholen und komme bei einer der Aufgaben nicht weiter..

 Sei A eine endliche Menge und $$f:  A \to A$$ eine Funktion. Fur alle ∀a ∈ A sei  f₀(a) := a und  f_i(a) := f(f_i−1(a))   fur  i ∈ N. Zeigen Sie, dass folgende Aussagen aquivalent sind:

(a) f ist injektiv.

(b) f ist surjektiv.

(c) Es gibt ein i ∈ N mit f_i = f₀.

Freue mich über jede Hilfe!

Answer 1

(a) f ist injektiv. 


==>  Da A endlich ist, etwa A = { a₁ , ... , a_n }

und f Injektiv, sind die Elemente f(a₁) , ... , f(a_n) alle verschieden

aber auch alle in A.  n verschiedene Elemente einer n-elementigen

Menge, sind die ganze Menge, also ist 

{ f(a₁) , ... , f(a_n) } = A , also f surjektiv.

(b)  =>  c)   f ist surjektiv.    Dann ist { f(a₁) , ... , f(a_n)} = A ,

also unterscheiden sich ( a₁ , ... , a_n ) und ( f(a₁) , ... , f(a_n)  )nur durch die Anordnung der Komponenten . Da es nur endlich viele


solcher Anordnungen gibt, gibt es k < m mit  f_k = f_m   also


f_o = f _m-k   


c)  => a)  ???

(c) Es gibt ein i ∈ N mit f_i = f₀.

Comments

Ich überleg mir zu der c) noch was.

---

Meine Idee dazu wäre:

Wenn irgend ein fi = f0 ist, dann ist ja die Bildmenge von fi wieder

ganz A und deshalb kann es nicht unterschiedliche a's aus A geben,

die das gleiche Bild haben.  Oder so ??

---

ja so hab ich mir das auch gedacht, also deutlicher wird es wenn man sich fi anschaut, dass ist ja f(f(..f(a))) und wenn f jetzt nicht injektiv wäre, dann hätte man ja am nach i Verknüpfungen mindestens ein Element weniger, dass kann aber nicht sein