Gehaxelts Blog

IT-Security & Hacking

[Uni]: Halbgruppen, Monoide, Gruppe & Ringe beweisen

Heute folgt mal ein Blogpost über etwas Uni-Mathe, was man als theoretischer Informatiker macht. Die Sachen die ich euch folgend zeige, nennt sich an der TU-Berlin “TheGI - Theoretische Grundlagen der Informatik”.

Ich habe mir überlegt, vielleicht ein wenig mehr (interessante) Sachen aus der Uni zu bloggen. Seien es mathematische Beweise, technische Funktionsoptimierungen, Lambda-Kalküle oder Aufwandsberechnungen. Vielleicht er/entmutigt das ja jemanden sich mit diesen Themen auseinanderzusetzen.

Im ersten Semester ist es als das Modul bekannt, über welches ausgesiebt wird. Das kann ich bestätigen, denn in zwischen sind die Vorlesungsräume um 50% leerer geworden.

Theorie

Zeichenklärung

Für die Leute, die diese Art von Mathe noch nicht kennen, folgt eine kurze Zeicherklärung:

: Allquantor. Aussage gilt für beliebiges Element x der Menge X

: x ist ein Element der Menge X

: Platzhalter für eine Menge

: Platzhalter für einen Operator

: Platzhalter für neutrales Element

: Platzhalter für Inverse Abbildung

: Platzhalter für neutrales Element

: Platzhalter für neutrales Element

: Platzhalter für einen Operator mit geringer Bindungsstärke

: Platzhalter für einen Operator mit höherer Bindungsstärke

Halbgruppe

Für die Halbgruppe (X,o) muss gelten, dass der Operator o auf der Menge assoziativ ist.

Assoziativität:

Für eine kommutative Halbgruppe muss die Kommutativität gelten:

Monoid

Für ein Monoid benötigen wir zunächst ein neutrales Element, welches linksneutral und rechtsneutral ist.

Eine Halbgruppe (X,o) bildet mit einem neutralem Element e ein Monoid (X,o,e).

Gruppe

Um eine Gruppe bilden zu können, benötigen wir eine Abbildung, welche für jedes Element aus X auf ein Inverses abbildet.

Ein Element ist invers zu einem anderen, wenn es links- und rechtsinvers ist:

Dann haben wir eine neue Operation:

Kombieren wir die Inversabbildung mit einem Monoid vom Typ (X,o,e) erhalten wir eine Gruppe (X,o,e,).

Diese Gruppe ist kommutativ, wenn das Monoid kommutativ ist.

Ring

Für einen Ring benötigen wir eine kommutative Gruppe (X,+,0,) und eine weitere Halbgruppe mit einem neuen Operation (X,*).

Danach müssen wir die Distributivität beweisen:

Nun erhalten wir einen Ring (X,+,*,0,).

Diesen kann man noch weiter unterscheiden:

  • Ist (X,*) eine kommutative Halbgruppe, so ist der Ring kommutativ.

  • Ist (X,,1) ein Monoid, so heißt der Ring (X,+,,0,1,) unitärer Ring.

Praxis

Die Theorie möchte ich nun noch an einem Beispiel-Ringbeweis verdeutlichen.

Zunächst definieren wir uns eine Menge:

Wir möchten folgendes Beweisen: (,+,*,0,) ist ein Ring.

Dazu müssen wir erstmal beweisen, dass (,+) eine Halbgruppe ist:

  • Abgeschlossenheit:

Wenn man zwei Element x,y aus der Menge mit dem Operator + verknüpft, dann muss dass Ergebnis ebenfalls in liegen.

  • Assoziativität:

Die Operator muss assoziativ sein. Wir beweisen also:

Seien x,y,z beliebig.

Das gilt nach der Assoziativität von +.

Es ist (,+) eine Halbgruppe.

Nun gehen wir einen Schritt weiter, bis wir beim Monoid sind. Für das Monoid brauchen wir ein neutrales Element. Dieses haben wir uns oben schon vorgegeben (0) und müssen dies nur noch beweisen.

  • Neutrales Element

Sei x beliebig.

Es ist (,+,0) ein Monoid.

Wir haben nun unser neutrales Element, welches wir für die Gruppe benötigen. Eine Gruppe braucht des Weiteren auch eine Inverse Abbildung.

  • Inverse

Wenn man ein wenig nachdenkt kommt man darauf, dass die Negation einer Zahl das Inverse zu dieser bildet. Ein Element verknüpft mit seinem Inversem ergibt das neutrale Element.

Das müssen wir nun noch beweisen:

Sei x beliebig.

Es ist (,+,0,) eine Gruppe.

Wir befinden uns nun fast am Ziel zum Ring. Wir brauchen eine weitere Halbgruppe mit einer weiteren Operation.

Beweise: (,*) ist eine Halbgruppe.

Die Eigenschaften müssen wir auch fix beweisen:

  • Abgeschlossenheit:
  • Assoziativität

Seien x,y,z beliebig.

Das gilt nach der Assoziativität von *.

Es ist (,*) eine Halbgruppe.

Nach diesem Schritt, können wir endlich die Disitributivität beweisen.

  • Distributivität von links

Seien x,y,z beliebig.

Das gilt nach der Distributivität von *.

  • Distributivität von rechts

Das ist analog zur linksseitigen Distributivität.

Seien x,y,z beliebig.

Es ist (,+,*,0,) ein Ring.

Wir haben es geschafft, auch wenn es ein verhältnismäßig einfacher Beweis war, da man fast alles auf die Eigeschaften von + bzw. * zurückführen konnte.

Gruß,

gehaxelt