TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 416

Aus VoWi
Zur Navigation springen Zur Suche springen

Man zeige, dass für eine beliebige Menge M die Algebra \langle(\mathfrak{P}(M),\bigtriangleup,\cap\rangle ein kommutativer Ring mit Einselement ist. Für welche M ist dieser Ring sogar ein Körper?

Definition der symmetrischen Differenz[Bearbeiten]

A \bigtriangleup B = (A \setminus B) \cup (B \setminus A)

C heißt symmetrische Differenz der Mengen A und B,

 C = A \triangle B ,

wenn C alle Elemente aus A enthält, die nicht zu B gehören und alle Elemente aus B, die nicht zu A gehören, d.h.:

 A \triangle B = (A \backslash B) \cup (B \backslash A) = (A \cup B) \backslash (A \cap B)

VENN-Diagramm:

Praes22 symmdiff.png

Theoretische Grundlagen (Zusammenfassung von mnemetz)[Bearbeiten]

Gesetze und Eigenschaften von algebraischen Strukturen

Eine algebraische Struktur ist eine nichtleere Menge G mit einer oder mehreren Operationen.

Folgende Eigenschaften kann eine solche Struktur annehmen:

  1. Abgeschlossenheit: G \times G = G, für a,b \in G \rightarrow a \circ b \in G (d.h. ist eindeutig zugeordnet). Das \circ entspricht einer Funktion von  \circ : G \times G \rightarrow G
  2. Assoziativgesetz: a \circ (b \circ c) = (a \circ b) \circ c für alle a,b,c \in G.
  3. Einheitselement: Es existiert ein e \in G, so dass für alle a \in G gilt: a \circ e = e \circ a = a.
  4. Inverses Element: Für jedes a \in G gibt es ein inverses Element a' \in G (oder auch a^{-1}) so, dass gilt a \circ a' = a' \circ  a = e. Wobei das e das Einheitselement ist.
  5. Kommutativgesetz: a \circ b = b \circ a für alle a,b \in G.
  Nr.   Gruppoid   Halbgruppe   Monoid   Gruppe   Abelsche Gruppe
  1     X          X            X        X        X
  2                X            X        X        X
  3                             X        X        X
  4                                      X        X
  5                                               X

Lösungsvorschlag von mnemetz[Bearbeiten]

Basierend auf f.thread:38144, etwas editiert und erweitert. --Mnemetz 03:33, 19. Dez 2005 (CET)

Für die symmetrische Differenz[Bearbeiten]

Abgeschlossenheit[Bearbeiten]

Wie schon aus den VENN-Diagrammen hervorgeht, ist eine Abgeschlossenheit gegeben.

Assoziativität[Bearbeiten]

 (A \triangle B) \triangle C   = A \triangle ( B \triangle C )

Praes22 assoziativ2.png

Es liegt die Assoziativität vor!

Man könnte dies mit der Elementtafel nachweisen (Auszug):

A B C \ A \triangle B  (A \triangle B) \triangle C \ B \triangle C  A \triangle (B \triangle C)
\in \in \in \ \notin \in \ \notin \in
\in \in \notin \ \notin \notin \ \in \notin

neutrales Element (Einheitselement)[Bearbeiten]

Das neutrale Element existiert', es ist die leere Menge \varnothing, denn A \bigtriangleup \varnothing = \varnothing \bigtriangleup A = A \qquad \forall A \in \mathfrak{P}(M).

Inverses Element[Bearbeiten]

Auch das inverse Element existiert, und zwar A' = A: jedes Element ist zu sich selbst invers.

Kommutativität[Bearbeiten]

Auch eine Kommutativität liegt vor.

\mathfrak{P}(M): (A \bigtriangleup B) = (A \backslash B) \cup (B \backslash A) =  (B \backslash A) \cup (A \backslash B)  = (A \cup B) \backslash (A \cap B)) - die symmetrische Differenz ist daher kommutativ

Schlussfolgerung[Bearbeiten]

Es liegt ein Abelsche Gruppe vor mit Nullelement \emptyset.

Für den Durchschnitt[Bearbeiten]

Abgeschlossenheit[Bearbeiten]

Falls A,B \in \mathfrak{P}(M) \Rightarrow A \cap B \in \mathfrak{P}(M): erfüllt

Assoziativität[Bearbeiten]

A \cap (B \cap C) = (A \cap B) \cap C \forall A,B \in \mathfrak{P}(M): erfüllt

neutrales Element (Einheitselement)[Bearbeiten]

\exists A \cap e = e \cap A = A \qquad \forall A \in \mathfrak{P}(M): erfüllt für e = M -> Einselement

Inverses Element[Bearbeiten]

\exists A \cap A' = A' \cap A = e \qquad \forall A,A' \in \mathfrak{P}(M)

Existiert i.A. nicht, da A \cap B \subseteq A für alle A,B \in \mathfrak{P}(M), d,h, für A \subsetneq M ist auch A \cap B \subsetneq M --- also ist A \cap B \neq M für alle A,B \in \mathfrak{P}(M), A \neq M

Für A = M ist allerdings M \cap M = M, d.h. M hat ein Inverses.

Kommutativität[Bearbeiten]

A \cap B = B \cap A \qquad \forall A,B \in \mathfrak{P}(M): erfüllt

Schlussfolgerung[Bearbeiten]

\langle(\mathfrak{P}(M),\cap\rangle ist ein kommutatives Monoid mit Einselement M.

Distributivgesetze müssen gelten[Bearbeiten]

  1. a*(b+c) = a*b + a*c
  2. (a+b)*c = a*c+ b*c

Am besten überprüft man das Gesetz, indem man die Mengen aufzeichnet, die Schnittmengen markiert und miteinander vergleicht. Analog dazu überprüft man auch das 2. Gesetz -> erfüllt.

Um ganz sicher zu gehen, sollte man sich die Elementtafel (s.o.) aufzeichnen. Man braucht auch nur eines der beiden Gesetze nachzuweisen, da \langle \mathfrak{P}(M), \cap \rangle abelsch ist.

Bei der algebraischen Struktur \langle\mathfrak{P}(M),\bigtriangleup ,\cap\rangle handelt es sich um einen kommutativen Ring mit Einselement.

Körperaxiome[Bearbeiten]

Das ist genau dann ein Körper, wenn |M| = 1

Beweis:

Sei M = \{ a \}, dann ist \mathfrak{P}(M) = \{ \emptyset , \{ a \} \}. Es genügt zu zeigen, dass \langle \mathfrak{P}(M) \backslash \{ \emptyset \} ,\cap \rangle abelsche Gruppe ist. Es ist \{ a \} \cap \{ a \} = \{ a \} \in \{ \{ a \} \}. Damit ist das bereits eine abelsche Gruppe.

Sei umgekehrt \langle \mathfrak{P}(M) \backslash \{ \emptyset \} ,\cap \rangle abelsche Gruppe, dann existiert zu jedem A \in \mathfrak{P}(M) \backslash \{ \emptyset \} ein Inverses in \mathfrak{P}(M) \backslash \{ \emptyset \}, was nach 4.2.4 bedeutet, dass \mathfrak{P}(M) \backslash \{ \emptyset \} = \{ M \}, d.h. |M| = 1.

(Für |M| = 0 ist \mathfrak{P}(M) \backslash \{ \emptyset \} = \emptyset, d.h. kein Gruppoid.)