Probleme bei einer Aufgabe zu symmetrischen Gruppen

30.08.2012, 13:00

monk123

Probleme bei einer Aufgabe zu symmetrischen Gruppen

Meine Frage:
Ich habe ein Problem bei folgender Aufgabe:

Es seien $\begin{eqnarray*} n \in \mathbb N_{>0}, \sigma \in S_{n} \end{eqnarray*}$ und $\begin{eqnarray*} i \in \{1,...,n\} \end{eqnarray*}$ . Ferner sei $\begin{eqnarray*} k \in \mathbb N_{>0} \end{eqnarray*}$ die kleinste Zahl, so dass
$\begin{eqnarray*} \sigma^{k}(i) \in \{i,\sigma(i),\sigma^{2}(i),...,\sigma^{k-1}\}. \end{eqnarray*}$

Beweise, dass dann $\begin{eqnarray*} \sigma^{k}(i) = i \end{eqnarray*}$ gilt.

Meine Ideen:
Also, die kleinste Zahl ist k=1 und dass $\begin{eqnarray*} \sigma^{k}(i) = i \end{eqnarray*}$ gilt, muss k aber 0 sein, denn für k ungleich 0 ist $\begin{eqnarray*} \sigma^{k} \end{eqnarray*}$ eine Permutation die i auf ein anderes Element von {1,...,n} abbildet und dadurch ungleich i ist (es sei denn sigma bezeichnet eine identische Abbildung).

Jetzt habe ich aber das Problem dass k = 0 durch die Aufgabendefinition ausgeschlossen ist. Und jetzt grübele ich irgendwie rum wie ich die Aufgabe lösen könnte.

Die Menge $\begin{eqnarray*} \{i,\sigma(i),\sigma^{2}(i),...,\sigma^{k-1}\} \end{eqnarray*}$ hat die Mächtigkeit k und wenn ich es richtig sehe beginnt sie bei $\begin{eqnarray*} \sigma^{0} \end{eqnarray*}$ was per definition ausgeschlossen ist, es sei denn der Exponent zählt sich hoch durch k-1, was auch das letzte Element erklären würde. Dadurch bestünde die Menge dann bei k=1 aus einem Element und zwar $\begin{eqnarray*} \sigma^{0}(i) \end{eqnarray*}$ da stets gelten würde $\begin{eqnarray*} \sigma^{k-1} \end{eqnarray*}$ und dann wäre tatsächlich $\begin{eqnarray*} \sigma^{k}(i) = i \end{eqnarray*}$ da $\begin{eqnarray*} \sigma^{0} \end{eqnarray*}$ keine Permutation darstellt sondern nur i nochmal "zurückliefert".

Aber irgendwie bin ich nicht zufrieden damit und bevor ich jetzt weiter stundenlang drüber grübele und mich im kreis drehe ob es stimmt und wie ich es dann aufschreiben kann dass es als bewiesen gilt, dachte ich ich frage mal hier smile

Mit freundlichen Grüßen
monk

30.08.2012, 13:09

DP1996

Auf diesen Beitrag antworten »

Nimm doch mal an, es wäre $\begin{eqnarray*} \sigma^k(i)=\sigma^j(i) \end{eqnarray*}$ wobei $\begin{eqnarray*} 0\neq j<k \end{eqnarray*}$ eine natürliche Zahl ist (also dass $\begin{eqnarray*} \sigma^k(i) \end{eqnarray*}$ irgendein anderes Element dieser Menge ist) und versuche, auf einen Widerspruch zu kommen.

30.08.2012, 14:08

SinaniS

Auf diesen Beitrag antworten »

RE: Probleme bei einer Aufgabe zu symmetrischen Gruppen

Zitat:

Original von monk123
Meine Ideen:
Also, die kleinste Zahl ist k=1 und dass $\begin{eqnarray*} \sigma^{k}(i) = i \end{eqnarray*}$ gilt, muss k aber 0 sein, denn für k ungleich 0 ist $\begin{eqnarray*} \sigma^{k} \end{eqnarray*}$ eine Permutation die i auf ein anderes Element von {1,...,n} abbildet und dadurch ungleich i ist (es sei denn sigma bezeichnet eine identische Abbildung).

Nein, das ist falsch. Es gibt immer ein k>0, fuer das $\begin{eqnarray*} \sigma ^k (i) =i \end{eqnarray*}$ ist. Ein Beispiel: Sei $\begin{eqnarray*} \sigma = (1 2) \end{eqnarray*}$ und i=1. Dann ist
$\begin{eqnarray*} \sigma ^1(1) =2, \sigma ^2 (1) = \sigma (2) = 1 \end{eqnarray*}$ .

Hier waere also k=2.

Ihr habt doch bestimmt gelernt, dass $\begin{eqnarray*} S_n \end{eqnarray*}$ eine (endliche) Gruppe ist, und in jeder endlichen Gruppe hat jedes Element endliche Ordnung, das heisst, es gibt fuer jedes $\begin{eqnarray*} \sigma \in S_n \end{eqnarray*}$ ein n>0 mit $\begin{eqnarray*} \sigma ^n = id \end{eqnarray*}$ . Das alleine zeigt schon, dass es immer so ein k>0 geben muss, und es ist kleiner oder gleich der Ordnung n von $\begin{eqnarray*} \sigma \end{eqnarray*}$ .

30.08.2012, 15:23

monk123

Auf diesen Beitrag antworten »

Hallo ihr beiden smile

Erstmal Danke dass ihr mir geantwortet habt =)

Ich hatte durch mangelnde Kenntnis leider den total falschen Ansatz indem ich eine explizite natürliche Zahl gesucht habe die diese Bedingung erfüllt.

Ich habe jetzt nochmal ein bisschen "rumgelesen" und meine jetzt verstanden zu haben auf was es ankommt:

Da $\begin{eqnarray*} S_{n} \end{eqnarray*}$ eine endliche Gruppe ist muss es irgendwann mal ein k geben, so dass $\begin{eqnarray*} \sigma^{k} = \sigma^{j} \end{eqnarray*}$ weil ansonsten hätte sigma eine unendliche Mächtigkeit besitzt und das per definition ausgeschlossen ist.
Dann muss ich noch k und j miteinander "verkuddeln" um dadurch dann n zu erhalten. Und da n eine natürliche Zahl ist und es in jeder Gruppe von natürlichen Zahlen stets ein kleinstes Element gibt wäre die Aufgabe dann gelöst. Richtig? (Das "verkuddeln" mach ich später noch und schreibs dann auch noch hier hin, ich wollte nur jetzt nochmal nachfragen ob mein jetziger Gedankengang stimmt^^)

Mit freundlichen Grüßen
monk123

PS: @SinaniS nee, das hatte ich noch nicht gelernt. Ich fange erst in einem Monat mit dem studieren an und bringe es mir grade selber etwas bei indem ich ein Skript "Algebraische Strukturen" durcharbeite. Da ich keine ergänzende Vorlesung also bisher gehört habe, habe ich nur das Skript und daher fehlt mir manchmal was wie zB das mit der endlichen Ordnung, auch wenns eigentlich logisch ist.. ^^ (mir fehlt da einfach noch ein bisschen die Übung das direkt zu erkennen denke ich^^ deswegen stelle ich dann hier die Fragen und kriege dann Stichworte geliefert über die ich mich weiter informieren kann und dadurch dann das "Gesamtgebilde" besser verstehe, also danke! =)

Edit (jester): LaTeX repariert.

30.08.2012, 18:46

DP1996

Auf diesen Beitrag antworten »

Zitat:

Dann muss ich noch k und j miteinander "verkuddeln" um dadurch dann n zu erhalten. Und da n eine natürliche Zahl ist und es in jeder Gruppe von natürlichen Zahlen stets ein kleinstes Element gibt wäre die Aufgabe dann gelöst. Richtig? (Das "verkuddeln" mach ich später noch und schreibs dann auch noch hier hin, ich wollte nur jetzt nochmal nachfragen ob mein jetziger Gedankengang stimmt^^)

Mach einfach mal, denn das hört sich noch ein bisschen vage an.

30.08.2012, 22:50

monk123

Auf diesen Beitrag antworten »

Zur besseren Verständlichkeit nehme ich m als Bezeichnung für k in folgender Gleichung: Da $\begin{eqnarray*} \sigma^{m}(i)=\sigma^{j}(i) \end{eqnarray*}$ und $\begin{eqnarray*} m < j \end{eqnarray*}$ kann man durch $\begin{eqnarray*} \sigma^{j-m}(i) \end{eqnarray*}$ auf eben jenes gesuchte k in $\begin{eqnarray*} \sigma^{k}(i)=i \end{eqnarray*}$ kommen. Dabei nimmt man dann einfach das Element welches für $\begin{eqnarray*} \sigma^{m}(i) \end{eqnarray*}$ steht als neues i und dann zeigt eben jenes $\begin{eqnarray*} \sigma^{j-m} \end{eqnarray*}$ betreffendes k an. Man nimmt dann einfach an dass dieses k dann gleichzeitig das kleinste ist, oder?

MfG

PS: Danke noch an jester für das Latex richten ^^

31.08.2012, 09:58

DP1996

Auf diesen Beitrag antworten »

Zitat:

Man nimmt dann einfach an dass dieses k dann gleichzeitig das kleinste ist, oder?

Nein, das solltest du schon zeigen.

Zitat:

Da $\begin{eqnarray*} \sigma^m(i)=\sigma^j(i) \end{eqnarray*}$

Du kannst noch mehr sagen: Da $\begin{eqnarray*} S_n \end{eqnarray*}$ nur endlich viele Elemente enthält, existiert eine kleinste Zahl $\begin{eqnarray*} k\in\mathbb{N} \end{eqnarray*}$ so, dass $\begin{eqnarray*} \sigma^k(i)=\sigma^j(i) \end{eqnarray*}$ ist mit $\begin{eqnarray*} 0\leq j<k \end{eqnarray*}$ .
Und jetzt kannst du dein Argument bringen.

31.08.2012, 12:35

monk123

Auf diesen Beitrag antworten »

k muss das kleinste sein, weil es kein größeres oder kleineres k geben kann (für ein spezielles i) welches die Bedingungen erfüllt da ab $\begin{eqnarray*} \sigma^{k}(i) \end{eqnarray*}$ die "Elementsequenz " wieder von vorne beginnt, was auch die Menge $\begin{eqnarray*} \{i, \sigma, \sigma^{2}... \sigma^{k-1} \} \end{eqnarray*}$ erklärt. Nun ist aber nicht für jedes i k gleich, aber da $\begin{eqnarray*} k \in \mathbb N \end{eqnarray*}$ gibt es ein kleinstes k so dass $\begin{eqnarray*} \sigma^{k}(i)= i \end{eqnarray*}$ .

Stimmt das jetzt?

01.09.2012, 10:20

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von monk123
k muss das kleinste sein, weil es kein größeres oder kleineres k geben kann (für ein spezielles i) welches die Bedingungen erfüllt da ab $\begin{eqnarray*} \sigma^{k}(i) \end{eqnarray*}$ die "Elementsequenz " wieder von vorne beginnt, was auch die Menge $\begin{eqnarray*} \{i, \sigma, \sigma^{2}... \sigma^{k-1} \} \end{eqnarray*}$ erklärt. Nun ist aber nicht für jedes i k gleich, aber da $\begin{eqnarray*} k \in \mathbb N \end{eqnarray*}$ gibt es ein kleinstes k so dass $\begin{eqnarray*} \sigma^{k}(i)= i \end{eqnarray*}$ .

Stimmt das jetzt?

Ich hab das jetzt 3 mal durchgelesen, aber versteh einfach nicht, was du uns damit sagen willst... verwirrt

Warum ignorierst du eigentlich beharrlich die Vorschläge der Experten hier, die geduldig versuchen dich immer wieder auf "den rechten Weg zurückzubringen", sondern schlägst dich bei der ersten Gelegenheit sofort in das unwegsame Dickicht deiner eigenen krausen Gedankengänge? geschockt

Dabei ist doch alles so einfach: Wie DP1996 schon gesagt hat, wenn k die kleinste Hochzahl ist, für welche es ein j<k mit

$\begin{eqnarray*} \sigma^k(i)=\sigma^j(i) \end{eqnarray*}$

gibt, so würde doch j>0 sofort auf den Widerspruch

$\begin{eqnarray*} \sigma^{k-1}(i)=\sigma^{j-1}(i) \end{eqnarray*}$

führen.. Es muss daher j=0 sein...

01.09.2012, 12:41

monk123

Auf diesen Beitrag antworten »

das lag wohl daran dass ich irgendwie dachte dass für $\begin{eqnarray*} \sigma^{j} \end{eqnarray*}$ die gleichen Bedingungen gelten wie für $\begin{eqnarray*} \sigma^{k} \end{eqnarray*}$ also dass k,j > 0 sein muss... (und dass ich mit dem zum Widerspruch führen noch so meine Probleme hab :/ )

Zu dem Widerspruch:
Also dies ist ein Widerspruch weil falls $\begin{eqnarray*} \sigma^{k-1}(i)=\sigma^{j-1}(i) \end{eqnarray*}$ wahr sein würde, k nicht das kleinste wäre?
Und $\begin{eqnarray*} \sigma^{-1} \end{eqnarray*}$ nicht mehr erlaubt ist? (weil ansonsten hätte man bei $\begin{eqnarray*} \sigma^{0-1} = \sigma^{k-1} \end{eqnarray*}$ wieder das gleiche Problem. (aber k,j sind ja per definiton >0.

Ich hab ja dann wirklich total in ne andere Richtung gedacht...

Kannst du mir noch kurz erklären wieso j = 0 aber nicht <0 sein darf? (wieso also $\begin{eqnarray*} j \in \mathbb N \end{eqnarray*}$ , weil die ganzen Variablen die 0 eigentlich ausschließen und deswegen bin ich jetzt etwas verwirrt noch, ansonsten ist alles klar)

Danke smile

01.09.2012, 14:02

DP1996

Auf diesen Beitrag antworten »

Zum Widerspruch:

Zitat:

Also dies ist ein Widerspruch weil falls $\begin{eqnarray*} \sigma^{k-1}(i)=\sigma^{j-1}(i) \end{eqnarray*}$ wahr sein würde, k nicht das kleinste wäre?

genau.

Dann Frage ich mich, wie du auf $\begin{eqnarray*} \sigma^{-1} \end{eqnarray*}$ kommst:
Wenn j>0 ist, ist j-1>=0. Und wenn j=0 ist, dann stimmt die Behauptung doch schon, und es wäre nichts mehr zu zeigen.
Exaktes Lesen hilft auch manchmal:

Zitat:

Original von Mystic
so würde doch j>0 sofort auf den Widerspruch

$\begin{eqnarray*} \sigma^{k-1}(i)=\sigma^{j-1}(i) \end{eqnarray*}$

führen.. Es muss daher j=0 sein...

Und zu der Frage, weshalb j<0 nicht sein darf:
Es soll ja k der kleinste Exponent sein, für den

$\begin{eqnarray*} \sigma^k(i)\in\left\{i,\sigma(i),...,\sigma^{k-1}(i)\right\}=\left\{\sigma^n(i)|n\in\mathbb{N}_0,n<k\right\} \end{eqnarray*}$

gilt, also gibt es ein Element dieser Menge, das gleich zu $\begin{eqnarray*} \sigma^k \end{eqnarray*}$ ist, und der Exponent, der zu diesem Element gehört, wird als j bezeichnet. Die Einschrängung $\begin{eqnarray*} j\geq0 \end{eqnarray*}$ ergibt sich sofort, wenn man die Menge etwas anders hinschreibt, ich hab das oben mal gemacht.

02.09.2012, 07:59

monk123

Auf diesen Beitrag antworten »

Auf $\begin{eqnarray*} \sigma^{-1} \end{eqnarray*}$ bin ich gekommen indem ich $\begin{eqnarray*} \sigma^{j-1} \end{eqnarray*}$ für j=0 betrachtet habe. Da mir aber jetzt klar ist dass der Exponent nicht negativ sein darf, fällt das natürlich komplett weg.

In deiner anderen Schreibweise für die Menge bezeichnet das n einfach eine beliebige natürliche Zahl und hat nichts mit dem n aus der Aufgabenstellung zu tun, oder?

Vielen Dank nochmal für eure Hilfe und eure Geduld! Blumen

02.09.2012, 08:16

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von monk123
In deiner anderen Schreibweise für die Menge bezeichnet das n einfach eine beliebige natürliche Zahl und hat nichts mit dem n aus der Aufgabenstellung zu tun, oder?

Hier geht es um den Unterschied zwischen freien und gebundenen Variablen... Das n aus der Aufgabenstellung ist in diesem Sinne "frei", das andere n dagegen "gebunden" (siehe auch die Beispiele dazu in obigem Link!)... Fazit: Es sind zwei verschiedene Variable... Wink

02.09.2012, 08:50

monk123

Auf diesen Beitrag antworten »

Danke, das kannte ich bisher noch nicht =)

Neue Frage »

Antworten »

Probleme bei einer Aufgabe zu symmetrischen Gruppen

Verwandte Themen