Äquivalenzrelation und Bahn

Question

Aufgabe:

Es sei δ die symmetrische Gruppe, d. h. die Gruppe aller Bijektionen der Menge {1, 2,...,n}. Für

σ∈ δ und i ∈{1,...,n} definiere man die Bahn von i unter σ durch

$$B_σ(i)=\left\{{σ^{k}| k\in \mathbb{N} } \right\}=\left\{i,σ(i),σ^{2}(i),...\right\}$$

Es sei ~ die Relation auf {1,...,n} definiert durch
i~j ⇔ B_σ(i) = B_σ(j)

(a) Zeigen Sie, dass ~ eine Aquivalenzrelation ist und folgern Sie, dass {1,...,n}
in paarweise disjunkte Bahnen unter σ zerlegt wird.

(b) Für σ= (1 2)(3 4) ∈δ bestimmen Sie den Quotienten {1, 2, 3, 4, 5}/ ~.

Problem/Ansatz:

Das ist das erste mal, dass ich von einer Bahn höre und habe dem entsprechend Probleme.

Zu a) hätte ich folgenden Ansatz: Zuerst muss ich zeigen, dass es sich um eine Äquivalenzrelation handelt. Das ~ eine Relation ist ist in der Aufgabe gegeben und nun müssen nur noch Reflexivität, Transitivität und Symmetrie gezeigt werden. Die Reflexivität ist klar, denn das ergibt ja einfach eine wahre Aussage für i~i. Weiter komme ich aber auch schon nicht. Für den zweiten Aufgabenteil habe ich keine Idee...

Comments

Ist für b) folgendes richtig?

{1,2,3,4,5}/~ = {1~1 ,1~2 ,1~3 ,1~4 ,1~5 , 2~2 , 2~3 , 2~4 , 2~5 , 3~3 , 3~4 , 3~5 , 4~4 , 4~5 , 5~5}

Reicht das oder muss ich ernsthaft alle Bahnen explizit ausrechnen?

Answer 1

a) Transitivität : Seien also i,j,k ∈ {1, 2,...,n} und

i~j und j~k

also \( \left\{i,σ(i),σ^{2}(i),...\right\} = \left\{j,σ(j),σ^{2}(j),...\right\}\)

und \( \left\{j,σ(j),σ^{2}(j),...\right\} = \left\{k,σ(k),σ^{2}(k),...\right\}\)

also auch

  \( \left\{i,σ(i),σ^{2}(i),...\right\} = \left\{k,σ(k),σ^{2}(k),...\right\}\)

und somit i~k.

und Symmetrie:

Wenn \( \left\{i,σ(i),σ^{2}(i),...\right\} = \left\{j,σ(j),σ^{2}(j),...\right\}\)

dann auch \(  \left\{j,σ(j),σ^{2}(j),...\right\}=\left\{i,σ(i),σ^{2}(i),...\right\} \)

Comments

Danke für die schnelle Antwort. Verstehe ich etwas falsch, oder ist dein Beweis für die Transitivität nicht nur eine anders ausgedrückte Behauptung? Woher wissen wir denn, dass das gilt?

---

Nach der Def. der Relation gilt doch

i~j ⇔ B_σ(i) = B_σ(j) ⇔   \( \left\{i,σ(i),σ^{2}(i),...\right\} = \left\{j,σ(j),σ^{2}(j),...\right\}\)

und zu " muss ich ernsthaft alle Bahnen explizit ausrechnen?"

Ist es doch m.E. so: Es gibt nur 3 verschiedene Bahnen:

Bσ(1) = {1;2}=Bσ(2)

Bσ(3) = {3;4}=Bσ(4)

Bσ(5)={5}

Bedenke {1,2,3,4,5 }  wird in 3 paarweise disjunkte Bahnen zerlegt.

---

Klar stimmt das... Ich glaube ich habe einfach zu kompliziert gedacht.

Kann mir vielleicht jemand noch helfen wie man daraus folgern kann, dass {1,2,...,n} in paarweise disjunkte Bahnen unter σ zerlegt wird?

---

Das sind die Äquivalenzklassen von ~.