Endliche Gruppen?
Hallo,
Ich habe eine endliche Halbgruppe S. Ich soll zeigen das es für alle elemente a der Halbgruppe eine natürliche Zahl m gibt, so dass a^m idempotent ist. (wobei a^m einfach bedeutet, dass das Element a, m mal mit einander verknüpft wird.
Was mir direkt einfällt ist da S endlich ist muss es 2 (natürliche) Zahlen geben so das a^n = a^m gilt. (ansonsten wäre sie nicht zyklisch und somit nicht endlich ?) aber ich bin mir nicht ganz sicher wie ich das jetzt darauf erweitern soll das es ein m gibt mit (a^m)^2 = a ^m ?
Dankeschön :)
1 Antwort
Naja du bist schon gar nicht so schlecht. Betrachte die Folge a^n für jedes a. Entweder die Menge ist unendlich, oder die Folge endet in einem Zykel. Sei a^x das erste Element, der Folge, das zu diesem Zykel gehört. Insbesondere gibt es ein kleinstes y, mit x<y sodass a^(y+1)=a^x.
Es gilt also a^x -> a^(x+1) -> ... -> a^y -> a^x.
Ich behaupte: Das Element a^(y-x+1) erfüllt die geforderte Bedingung.
Beweis:
(a^(y-x+1))^2
= a^(2y-2x+2)
= a^(y+1) * a^(y-2x+1)
=a^x * a^(y-2x+1)
=a^(y-x+1)
Sag du mir bitte, ob das alles so geht. Den Begriff "Halbgruppe" haben wir im Studium noch nicht eingeführt. Ist das höher als das 3. Semester?
Mhm. Guter Einwand, lass mich überlegen. Ich wollte a^(y+1)=a^x haben.
Kann ich den Kram nicht einfach direkt im Exponenten lassen? Also ohne es auseinander zu ziehen und einfach y+1 mit x tauschen?
a^x -> a^(x+1) -> ... -> a^y -> a^x
Die Länge des Zykels ist also z = y-x+1 und er umfasst die Potenzen a^(x+j) für j = 0, 1, y-x.
Es gilt also für diese j
a^(x+j+n*z) = a^(x+j)
Wir suchen ein j, so dass gilt
a^(x+j+n*z) = a^2(x+j), n >1
wozu es ausreichend ist, dass
x+j+n*z = 2(x+j), oder n*z = x+j
Die Wahl fällt auf
j = n*z - x
mit n so, dass 0 <= n*z - x < z
Hier ein Rettungsversuch:
Lemma1: Für jede positive natürliche Zahl n gilt: a^(n * (y-x+1)) * a^x = a^x.
Beweis: Per Induktion nach n.
IA: a^(y-x+1) * a^x = a^(y-x+1+x) = a^(y+1) = a^x.
IS:
a^((n+1)(y-x+1)) * a^x
= a^(y-x+1) * a^(n * (y-x+1)) * a^x
= a^(y-x+1) * a^x = a^x.
Lemma2: Es gibt genau eine natürliche Zahl k mit x <= k <= y, sodass
a^k * a^x = a^x.
Beweis der Existenz:
Da y-x+1 > 0, ist die Folge (n * (y-x+1)) unbeschränkt.
Insbesondere gibt es ein N mit N * (y-x+1) >= x, weswegen a^(N * (y-x+1)) irgendwo in dem Tupel (a^x, ..., a^y) auftritt (selbst wenn N * (y-x+1) > y sein sollte, ist diese Aussage wahr aufgrund der zyklischen Natur der Potenzen von a ab diesem Punkt).
Wähle also das k mit x <= k <= y, sodass a^(N * (y-x+1)) = a^k, so folgt mithilfe von Lemma1:
a^k * a^x = a^x.
Beweis der Eindeutigkeit:
Sei k eine solche Zahl. Seien n, r natürliche Zahlen mit 0 <= r < (y-x+1) und
k = r + n * (y-x+1) [existiert dank Division mit Rest].
Angenommen r > 0.
Wegen a^k * a^x = a^x folgern wir:
a^x
= a^k * a^x
= a^r * a^(n * (y-x+1)) * a^x
= a^r * a^x.
Definiere nun y' := r+x-1. Es folgt:
- a^(y'+1) = a^(r+x-1+1) = a^(r+x) = a^r * a^x = a^x,
- y' = r+x-1 < (y-x+1)+x-1 = y.
Dies ist ein Widerspruch zur Minimalitätsbedingung von y.
Daher muss r = 0 sein.
Insbesondere ist k von der Form n * (y-x+1).
Sei nun k' eine weitere natürliche Zahl mit a^k' * a^x = a^x und x <= k' <= y.
Wir wissen nun, dass auch k' von der Form n' * (y-x+1) sein muss.
Angenommen k und k' wären ungleich, oBdA sei k > k'.
Dann ist k-k' = n-n' * (y-x+1) >= (y-x+1), also k >= k' + (y-x+1). Damit haben wir aber:
- k <= y, nach Voraussetzung
- k >= k' + (y-x+1) >= x + (y-x+1) = y+1, nach obiger Schlussfolgerung. Ein Widerspruch.
Daher ist k = k'. Mithin ist k eindeutig.
Satz: Sei k die nach Lemma2 eindeutig bestimmte Zahl mit
a^k * a^x = a^x und x <= k <= y. Dann ist a^k idempotent.
Beweis:
Da 2k >= k >= x gilt, muss es ein x <= k' <= y geben mit a^(2k) = a^k'.
Da a^(2k) * a^x = (a^k)^2 * a^x = a^k * a^k * a^x = a^k * a^x = a^x ist, gilt nach Lemma2: k = k'.
Insbesondere ist (a^k)^2 = a^(2k) = a^k' = a^k.
Danke :). Eine Halbgruppe ist allgemeiner wie eine Gruppe, denn es wird nur verlangt das assoziativität gilt. (es muss also kein neutrales Element geben und keine inversen). Dein Beweis sollte also funktionieren. Das ist tatsächlichen schon im Master (allerdings in Informatik mit Schwerpunkt auf Kryptographie). Kannst du mir noch verraten wie du darauf gekommen bist das a^(y-x+1) die Bedingung erfüllt, damit ich ähnliche aufgaben besser lösen kann :D?
Ich habe mir einfach ein paar Folgen genommen, z.B.
(a², a³, a⁴, a⁵), angenommen das wird ein Zirkel und geschaut, welches Element beim quadrieren in Reihe immer auf sich selbst abgebildet wird. Als ich dann immer eins mehr (a⁶; a⁷) dazu genommen habe, hat sich das Element um 1 nach rechts verschoben, dadurch kam ich darauf, dass es irgendwas mit Anfang und Ende und +1 zu tun hat, der Rest war dann probieren. :)
Schöne Idee, wo ich noch hänge ist der Exponent y-2x+1. In der Halbgruppe gibt es im allgemeinen nur eine assoziative Verknüpfung, keine Invertierung, kein Neutrales. Wenn genannter Exponent <= 0 wird, dann ist a^(y-2x+1) nicht definiert. Vielleicht kann man es irgendwie retten.
(Ausserdem, meintest du a^y=a^x oder a^(y+1) =a^x ?)