Rekursionssatz

Abbildung 6: Rekursionssatz

Satz 2.8 (Rekursionsatz Dedekind 1887)   Sei $(A,\alpha)$ eine einstellige Algebra mit injektivem $\alpha$. Die zu $\alpha(A)$ disjunkte Teilmenge $U$ von $A$ erzeuge $A$. Dann gibt es zu jeder einstelligen Algebra $(B,\beta)$ und jeder Abbildung $f:U\rightarrow B$ genau einen Homomorphismus $f^{*}$, so dass das folgende Diagramm kommutativ ist:

U	$\hookrightarrow{\iota}$	A
$\Big\downarrow{f}$		$\Big \downarrow{f^{*}}$
B	$=$	B

$\iota:U\ni u\mapsto u\in A$ ist die Inklusionsabbildung.

Erklärung 2.5   Sind die Voraussetzungen des Satzes erfüllt heißt $(A,\alpha)$ freie einstellige Algebra mit Basis $U$.

Beweis:Den Beweis des Satze habe ich dem entsprechenden Beweis im Buch [Ea92, Seite15] nachempfunden.

Wir betrachten $D=\{(u\vert f(u))\vert u \in U\}$. Sie erzeugt eine kleinste Untermenge $[D]$ in $A\times B$, die abgeschlossen gegenüber $(\alpha, \beta)$ ist.

Beh: $[D]$ ist der Graph einer Funktion.

Bew:

1. Zu jedem $a \in A$ gibt es ein Paar $(a,b)\in [D]$.

   Beweis durch Induktion.

   Sei $u\in U$, dann ist $(u\vert f(u))$ nach Definition in $[D]$. Sei

   $$T=\{a\vert a\in A\wedge \exists b\in B: (a\vert b)\in[D]\}.$$
   Wir haben gesehen $U\subset T$. Sei $a\in T$. Dann gibt es ein $b\in B$ mit $(a\vert b)\in [D]$. Daher ist $(\alpha\times \beta)(a\vert b)\in [D]$, da $[D]$ abgeschlossen gegenüber $\alpha\times \beta$ ist. Also ist $\alpha(a)\in T$. Daher ist $T$ gegenüber $\alpha$ abgeschlossen. Daher ist $T=A$.
2. Für jedes $u$ in $U$ liegt nur $(u,f(u))$ in $[D]$.

   Sei $(u\vert f(u))\in [D]$ mit $u\in U$. Angenommen es gibt ein weiteres Paar $(u\vert b)\in [D]$. Dann ist auch noch $[D]\setminus\{(u\vert b)\}$ gegenüber $(\alpha, \beta)$ abgeschlossen. Dazu muss ich nur zeigen, dass $(u\vert b)$ nicht als Bild eines Elementes aus $[D]\setminus\{(u\vert b)\}$ vorkommen kann. Angenommen $(\alpha,\beta)(a',c)=(u,b)$. Dann ist $(\alpha(a'),\beta(c))=(u,b)$. Das bedeutet $u\in \alpha(A)$. Dies kann nach Voraussetzung nicht sein. Also ist $(u\vert f(u))\in T$.

3. $[D]$ ist rechtseindeutig. Beweis durch Induktion:

   Wieder sei

   $$T=\{a\vert a\in A\wedge$$    es gibt genau ein $$b\in B$$ mit $$(a,b)\in [D]\}$$
   Zu zeigen bleibt $T$ ist abgeschlossen gegenüber $\alpha$. Sei $(a,b)\in [D]$ mit $a\in T$. Das heißt nur dieses $b$ existiert, so dass $(a,b)\in [D]$. Dann ist $(\alpha(a),\beta(b))\in [D]$. Angenommen es gibt ein weiteres $(\alpha(a),c)\in [D]$. Dann ist auch noch $[D]\setminus \{(\alpha(a)\vert c)\}$ gegenüber $(\alpha, \beta)$ abgeschlossen. Denn angenommen $(\alpha,\beta)(a'\vert b')=(\alpha(a)\vert c)$. Dann ist $\alpha(a')= \alpha(a)$ und daher (weil $\alpha$ injektiv ist) $a=a'$. Dann ist aber $(a,b')\in [D]$ und $(a,b)\in [D]$. Zu $a$ gab es nur ein $b$ mit $(a,b)\in [D]$. Dann ist $b'=b$. Das heißt $c=\beta(b')=\beta(b)$. Dies widerspricht der Annahme $c\neq \beta(b)$. Also ist $[D]$ der Graph einer Funktion und wegen Satz folgt die Behauptung.

Wir sehen es war unbedingt wichtig, dass $\alpha:A\rightarrow A$ injektiv ist. $\Box$

Satz 2.9 (Basissatz)   Seien $(A,\alpha)$ und $(B,\beta)$ zwei Ketten mit injektivem $\alpha$ und $\beta$. Haben $A$ und $B$ gleichmächtige Basen, so sind sie isomorph.

Beweis:Sei $U$ ein Basis von $A$ und $V$ eine Basis von $B$. Nach Voraussetzung gibt es eine umkehrbare Abbildung $f:U\rightarrow V$. Die Umkehrabbildung sei $g$. Es gibt genau ein $F: A\rightarrow B$, so dass folgendes Diagramm kommutativ ist.

$U$	$\hookrightarrow{\iota}$	A
$\Big\downarrow{f}$		$\Big\downarrow{F}$
$V$
$\downarrow{\iota}$
$B$	$=$	$B$

Genauso gibt es ein $G$, so dass folgendes Diagramm kommutativ ist.

$V$	$\hookrightarrow{\iota}$	B
$\Big\downarrow{g}$		$\Big\downarrow{G}$
$U$
$\downarrow{\iota}$
$A$	$=$	$A$

Man erhält also $G(F(u))= G(f(u))=g(f(u))= u$ für alle $u\in U$. Andererseits ist $Id_{A}(u)=\iota(u)$ für alle $u\in U$. Es gibt nur eine solche Abbildung. Daher ist $GF=Id_{A}$. genauso folgt $FG=Id_{B}$. Das war aber behauptet. $\Box$
So wie wir den Satz formuliert haben besteht eine völlige Analogie etwa zur Theorie der Vektorräume oder der freien Moduln. Auf der Basis ist man frei Homomorphismen zu definieren. Der definierte Homomorphismus ist dann auch eindeutig. Es ist also sinnvoll eine einstellige Algebra $(A,\alpha)$ mit Basis frei zu nennen.

Hinweise:

1. Ist in der Kategegorie der einstelligen Abbildungen jeder Epimorphismus eine surjektive Abbildung?
2. Ist jeder Monomorphismus eine injektive Abbildung?

Satz 2.10   Jede freie einstellige Algebra ist auch projektiv. Das heißt: Ist $f:B\rightarrow C$ ein surjektiver Homomorphismus zwischen einstelligen Algebren und $g:A\rightarrow C$ auch ein Homomorphismus, so gibt es ein $g^{*}:A\rightarrow B$, so dass folgendes Diagramm kommutativ ist.

$\begin{array}[t]{ccc} & & A \\ &\swarrow g^{*}& \Big \downarrow g\\ B&\mbo... ...aystyle \stackrel{f}{\mbox{$\makebox[3em]{\rightarrowfill}$}}$} &C \end{array}$

Beweis:Sei $(A,\alpha)$ eine freie einstellige Algebra mit der Basis $(a_{i}\vert i\in I)$. Wir betrachten die Familie $(g(a_{i})\vert i\in I)\subset C$. Zu dieser Familie gibt es nach dem Auswahlaxiom eine Familie $(b_{i}\vert i\in I)$ mit $f(b_{i})=g(a_{i})$ für alle $i\in I$. Wir erklären $g'(a_{i}):=b_{i}$. Nach dem Rekursionssatz gibt es einen eindeutigen bestimmten Homomorphismus $g^{*}:A\rightarrow B$ mit $g^{*}(a_{i})=b_{i}$. Damit ist $f\circ g^{*}(a_{i})=g(a_{i})$ und damit $f\circ g^{*}= g$. Dies war zu zeigen. $\Box$
Hinweise:

1. Unteralgebren freier Algebren sind auch frei.
2. Damit sind projektive Algebren frei.