Gruppen, Ringe, Körper

Qunatoren & Aussagenlogik

Verknüpfungen

• Negation
  $\neg a$: nicht $a$
• Implikation
  $a\Rightarrow b$: aus $a$ folgt $b$
• Äquivalenz
  $a\Longleftrightarrow b$: $a$ und $b$ sind äquivalent (gleichwertig)
• Konjunktion
  $a\wedge b$: $a$ und $b$
• Disjunktion
  $a\vee b$: $a$ oder $b$

Wahrheitstabelle:

$a$	$b$	$\neg a$	$a\vee b$	$a\wedge b$	$a\Rightarrow b$	$a\Leftrightarrow b$
f	f	w	f	f	w	w
f	w	w	w	f	w	f
w	f	f	w	f	f	f
w	w	f	w	w	w	w

Quantoren

• Allquantor $\forall x:\varphi(x)$
  für alle $x$ gilt $\varphi(x)$.
  z.B. $\forall x\in\mathbb{N}:x^{2}\in\mathbb{N}=\forall_{\mathbb{N}}^{x}:x^{2}\in\mathbb{N}$
• Existenzquantor $\exists x:\varphi(x)$
  es gibt (mindestens) ein $x$ für das $\varphi(x)$ gilt.
  z.B. $\exists x\in\mathbb{N}:\varphi(x)=\exists_{\mathbb{N}}^{x}:\varphi(x)$
• $\exists!x:\varphi(x)$ oder $\exists^{1}x:\varphi(x)$
  es gibt genau ein $x$ für das $\varphi(x)$ gilt.
• Negation $\forall x:H(x)\Leftrightarrow\neg\exists x:\neg H(x)$
  Es gilt für alle $x$, $H(x)$ $\Leftrightarrow$ Es gibt nicht ein $x$, für das $H(x)$ nicht gilt.

Rechenregeln

• Kommutativgesetz
  $a\wedge b=b\wedge a$
  $a\vee b=b\vee a$
• Assoziativgesetz
  $\left(a\wedge b\right)\wedge c=a\wedge\left(b\wedge c\right)$
  $\left(a\vee b\right)\vee c=a\vee\left(b\vee c\right)$
• Distributivgesetz
  $a\wedge\left(b\vee c\right)=\left(a\wedge b\right)\vee\left(a\wedge c\right)$
  $a\vee\left(b\wedge c\right)=\left(a\vee b\right)\wedge\left(a\vee c\right)$
• De Morgan
  $\neg\left(a\vee b\right)=\left(\neg a\right)\wedge\left(\neg b\right)$
  $\neg\left(a\wedge b\right)=\left(\neg a\right)\vee\left(\neg b\right)$
• doppelte Negation
  $\neg\left(\neg a\right)=a$
• Rechenregeln des logischen Schließens
  • direkter Schluss
    $\left(A\wedge\left(A\Rightarrow B\right)\right)\Rightarrow B$
  • indirekter Schluss
    $\left[\left(\neg B\right)\wedge\left(A\Rightarrow B\right)\right]\Rightarrow\left(\neg A\right)$
  • Kontraposition
    $\left(A\Rightarrow B\right)\Rightarrow\left(\neg B\Rightarrow\neg A\right)$
• Negation von Quantoren
  $\neg\left(\forall a:\varphi\left(a\right)\right)\Leftrightarrow\left(\exists a:\neg\varphi\left(a\right)\right)$
  $\neg\left(\exists a:\varphi\left(a\right)\right)\Leftrightarrow\left(\forall a:\neg\varphi\left(a\right)\right)$
• neutrales Element
  $a\vee\textrm{f}=a$
  $a\wedge\textrm{f}=\textrm{f}$
  $a\vee\textrm{w}=\textrm{w}$
  $a\wedge\textrm{w}=a$
• inverses Element
  $a\vee\left(\neg a\right)=\textrm{w}$
  $a\wedge\left(\neg a\right)=\textrm{f}$

Eigenschaften von Aussagen

Widerspruch

(Symbol: Blitz) heißt eine zusammengesetzte Aussage, wenn sie immer falsch ist.
z.B. $A\wedge\neg A$

Tautologie

heißt eine Aussage, wenn sie immer wahr ist.
z.B. $A\vee\neg A$

Sonstige Definitionen

Potenzmenge

$\mathcal{P}\left(M\right):=\left\{ M'\vert M'\subseteq M\right\}$

Differenzmenge

für $M',M''\subseteq M$ sei
$M'-M'':=\left\{ m\vert m\in M'\wedge m\notin M''\right\}$

Menge aller Abbildungen

Seien $A,B$ beliebige Mengen. Dann bezeichnet $A^{B}:=\left\{ f\vert f:B\rightarrow A\right\}$ die Menge aller Abbildungen von $B$ nach $A$.

Verkettung

Sei $M$ eine beliebige Menge. Die Verkettung von Abbildungen von $M$ in sich ist definiert durch $\circ:M^{M}\times M^{M}\rightarrow M^{M}$ mit $g\circ f:M\rightarrow M:m\mapsto g\left(f\left(m\right)\right)$ für $f,g\in M^{M}$ und $m\in M$.

• Verkettungen sind assoziativ.
• Die Verkettung von bijektiven Abbildungen ist wieder bijektiv

Sym

$\mathrm{Sym}\left(M\right):=\left\{ f\vert f:M\rightarrow M \mathrm{bijektiv}\right\}$

• für $M=\left\{ 1,\ldots,k\right\} \subseteq\mathbb{N}$ schreibe $S_{k}$ (Menge von allen möglichen Permutationen von $k$ Zahlen)

Verknüpfung

Eine (binäre) Verknüpfung $*$ auf einer Menge $M$ ist eine Abbildung $*:M\times M\rightarrow M:\left(m,m'\right)\mapsto m*m'$. Sie heißt

kommutativ

falls $\forall_{M}^{m,m'}:m*m'=m'*m$

assoziativ

falls $\forall_{M}^{m,m',m''}:m*\left(m'*m''\right)=\left(m*m'\right)*m''$

• In diesem Fall ist es nicht nötig Klammern zu setzen.

• Es gibt postfix, infixund suffix Notationen für Verknüpfungen, jenachdem, ob das Zeichen vor, zwischen oder nach den Operanden kommt.
• Verknüpfungen sind eine Teilmenge der Abbildungen

Halbgruppe

Sei $M$ eine beliebige Menge, und $*$ eine assoziative Verknüpfung. Das Paar $\left(M,*\right)$ wird nun als Halbgruppe bezeichnet.

• $\left(M^{M},\circ\right)$ ist eine Halbgruppe
• Eine Halbgruppe mit neutralem Element nennt sich auch ein Monoid.

Gruppe

Eine Halbgruppe $\left(G,*,e\right)$ heißt Gruppe, falls folgene Elemente exisiteren

Neutralelement

$e$

$$\exists_{G}^{e}:\forall_{G}^{g}:e*g=g$$

Inverses Element

$g^{-1}:=h$

$$\forall_{G}^{g}:\exists_{G}^{h}:h*g=e$$

Man sprich von einer kommutativen Gruppe, falls $*$ zusätzlich noch kommutativ ist.

• jede Gruppe besitzt genau ein neutrales Element
• in einer Gruppe existiert zu jedem Element genau ein inverses Element
• Eine Gruppe ohne Inverse Elemente nennt sich Monoid
• Falls $G$ endlich, darf in der Verknüpfungstafel von $*$ in jeder Zeile und in jeder Spalte jedes Element nur genau einmal vorkommen.
• Die Gruppe $\left(\left\{ e\right\} ,*,e\right)$ wird als triviale Gruppe bezeichnet
• $\left(\mathrm{Sym}\left(M\right),\circ,\mathrm{id}_{M}\right)$ ist eine Gruppe mit Neutralelement $\mathrm{id}_{M}:M\rightarrow M:m\mapsto m$
• $\forall x,y\in G:\left(x*y\right)^{-1}=y^{-1}*x^{-1}$

Ring

Sei $R$ eine Menge mit zwei Verknüpfungen $+:R\times R\rightarrow R$ und $*:R\times R\rightarrow R$. $+$ wird mit plus, und $*$ mit mal bezeichnet. Das Tripel $\left(R,+,*,e\right)$ heißt Ring, falls

1. $\left(R,+,e\right)$ eine kommutative Gruppe ist
2. $\left(R,*\right)$ eine Halbgruppe ist
3. Es gelten die Distributivgesetze für alle $a,b,c\in R$
   

   $$\left(a+b\right)*c = a*c+b*c$$

   $$a*\left(b+c\right) = a*b+a*c$$

   
   

• $-\left(-x\right)=x$
• $x+y=x\Rightarrow y=0$
• $\left(-x\right)y=-\left(xy\right)=x\left(-y\right)$

Einen Ring $R$ nennt man Ring mit $1$, wenn er ein neutrales Element bzgl. der Multiplikation hat, welches man mit $1$ bezeichnet. Man nennt ein $x\in R$ invertierbar, wenn es ein $x^{-1}\in R$ gibt, mit $x*x^{-1}=1=x^{-1}*x$.

• In jedem Ring mit $1$ bildet die Menge der invertierbaren Elemente eine Gruppe.
• Wenn für $a,b\in R\backslash\left\{ 0\right\}$ $a*b=0$ gilt, heißt der Ring nullteilerfrei. In nullteilerfreien Ringen kann man eine Division mit Rest definieren.
• In einem Ring mit $1$ ist jedes Element $a$ entweder invertierbar oder Nullteiler (d.h. $\exists x:a*x=0$)

Körper

Ein Ring $\left(K,+,*,0\right)$ mit additivem ($+$) Neutralelement $0\in K$ heißt Körper $\left(K,+,*,0,1\right)$, falls zusätzlich $\left(K-\left\{ 0\right\} ,*,1\right)$eine kommutative Gruppe ist. Das additive ($+$) Neutralelement 0 heißt Nullelement, und das multiplikative ($*$) Neutralelement heißt Einselement.

• falls $\left(K-\left\{ 0\right\} ,*,1\right)$ eine nicht kommutative Gruppe ist, wird $\left(K,+,*,0,1\right)$ als Schiefkörper bezeichnet.
• $\left(\mathbb{F}_{2},+,*\right)$ mit

  +	0	1
  0	0	1
  1	1	0

  und

  *	0	1
  0	0	0
  1	0	1

  ist der kleinste mögliche Körper.
• $0\neq1$ muss gelten
• Körper sind per Nullteilerfrei, d.h. es gilt:
  $a*b=0\;\Leftrightarrow\quad a=0\vee b=0$

$K$-Algebra

Sei $\left(V,+,\cdot\right)$ ein $K$-Vektorraum und $\left(V,+,*\right)$ ein Ring mit $1$. Dann wird $\left(V,+,\cdot,*\right)$ als $K$-Algebra bezeichnet, falls $\left(\lambda\cdot a\right)*b=\lambda\cdot\left(a*b\right)$ für belibige $\lambda\in K$ und $a,b\in V$ gilt.

Relation

Eine (zweistellige) Relation$\sim$ zwischen den Mengen A und B ist eine Teilmenge von $A\times B$.
$a\sim b$ falls $(a,b)\in A\times B$.

• Eigenschaften von Relationen

  reflexiv

   
  $\forall a:a\sim a$

  symmetrisch

   
  $a\sim b\Leftrightarrow b\sim a$

  antisymmetrisch

   
  $a\sim b\wedge b\sim a\Rightarrow a=b$

  transitiv

   
  $a\sim b\wedge b\sim c\Rightarrow a\sim c$

(An-)Ordnung

Wir nennen $<$ Ordnung oder Anordnung falls entweder $x<y$ oder $x=y$ oder $y<x$ gilt (nur eines dieser 3). Zudem muss $<$ transitiv sein.

angeordneter Ring / Körper

Ein Ring oder ein Körper $\left(R,+,*,0,1\right)$ heißt angeordneter Ring bzw. angeordneter Körper, schreibe $\left(R,+,*,0,1,<\right)$, falls $<$ eine Ordnung auf $R$ ist und folgendes für alle $x,y,z\in R$ gilt:

1. $x<y\Rightarrow x+z<y+z$
2. $x<y\wedge0<z\Rightarrow x*z<y*z$

positiv

falls $0<x$

negativ

falls $x<0$

nicht positiv

falls $x<0\vee x=0$

nicht negativ

falls $0<x\vee x=0$

• positiv $*$ positiv = positiv = negativ $*$ negativ
• negativ $*$ positiv = negativ = positiv $*$ negativ
• $x\neq0\Rightarrow0<x^{2}=x*x$
• $0<1$
• ein angeordneter Ring / Körper hat unendlich viele Elemente
• es gelte die Punkt vor Strich-Rechnung, um Klammern zu sparen