%Division% !TEX TS-program = latexmk
% !TEX encoding =latin 1
\documentclass{scrreprt}
% Mathepakete von mir eingefügt
\usepackage{amsmath,amssymb,amsfonts,amsthm,multicol,longtable,tabularx,fancybox,fancyhdr,lscape}
\usepackage{stmaryrd}
\usepackage[latin 1]{inputenc}
\usepackage[]{fontenc}
\usepackage{lmodern}
\usepackage[ngerman]{babel}
% Um mit Latex zeichnen zu können
\usepackage{tikz}
\usetikzlibrary{positioning,shapes.geometric} 
\tikzset{decision/.style={draw,diamond,text width=3cm,align=center}}

% um über mehrere Zeilen Kommentare schreiben zu können:
\usepackage{verbatim}
\usetikzlibrary{shapes,arrows}

\pagestyle{headings}

%Nummerierung geht bis Tiefe 6
\setcounter{secnumdepth}{6} %Nummerierung subsubsection
\setcounter{tocdepth}{6} % subsubsection ins Inhaltsverzeichnis

% Ränder setzen
\usepackage[left=2cm,right=1cm,top=0cm,bottom=0cm,includeheadfoot]{geometry} 

% hyperref sollte als letztes aller Paktete geladen werden
\usepackage{hyperref}

%Einrücken generell verhindern
\setlength{\parindent}{0em}

%Soll nur bei einen bestimmten Absatz das Einrücken verhindert werden:
% \noindent 


\title{Nützliche Sätze bei induktiven Definitionen}
\date{ \today}

\begin{document}

\maketitle
\tableofcontents

\chapter{Motivation}
\section{Beispiel1: Dualzahlen - Dezimalzahlen } 
Das Rechnen (mit Summe und Prrodukt) von Dualzahlen kann man auf das Rechnen mit Dezimalzahlen zurückführen bzw. reduzieren. \\
Dazu wird jeder Dualzahl eineindeutig eine Dezimalzahl zugeordnet bzw. dann jedem Term aus Dualzahlen ein  Term aus Dezimalzahlen zugeordnet. \\
Man kann diese Zuordnung Substitution (subst) nennen, wie z.B: \\ 
$((\hat{100} \oplus \hat{11}  \otimes \hat{111}) \leftrightarrow ((4 +3) *7)$ \\  \\
Zum Beispiel ist dann $subst(7) = \hat{100}$\\
Die Auswertung (Berechnung des Werts) eines Terms aus Dualzahlen kann dann über die Auswertung (Berechnung des Werts) des zugehörigen Terms aus Dualzahlen erfolgen. \\
Dazu definiert man zuerst die Summe add bzw. das Produkt mul zweier Dualzahlen: \\ 
$b_1 \; add \; b_2 :=   subst^{-1}(subst(b_1) \; \overline{add}\;   subst(b_2))$, also \\ 
$b_1 \; add \; b_2 :=   subst^{-1}(d_1 \; \overline{add}\;   d_2)$ \\ 
wobei $\overline{add}$ die bekannte Addition zweier Dezimalzahlen bedeutet und $b_1$ bzw $b_2$ die zu den Dezimalzahlen $d_1$ bzw. $d_2$ zugehörigen Dualzahlen (Binärzahlen) sind. \\
Umgeformt erinnert das an einen Isomorphismus:\\
$subst(b_1 \; add \; b_2) :=   subst(b_1) \; \overline{add}\;   subst(b_2)$ \\ \\
Intuitiv würde man dann annehmen:\\
$ev1(B_1) = ev1(B_2) \Leftrightarrow ev2(subst(B_1)) = ev2(subst(B_2))$ \\ 
wobei ev1 die Auswertung eines Terms aus Dualzahlen und ev2 die Auswertung eines Terms aus Dezimalzahlen bedeutet.

\section{Beispiel 2: Matrizen - lineare Abbildungen} 
$\hat{z}$
Das Rechnen (mit Summe und Prrodukt) mit Matrizen kann man auf das Rechnen mit linearen Abbildungen zurückführen bzw. reduzieren. \\
Dazu wird jeder Matrix eineindeutig eine lineare Abbildung zugeordnet bzw. dann jedem Matrizenterm ein  linearer Abbildungsterm zugeordnet. \\
Man kann diese Zuordnung Substitution (subst) nennen, wie z.B: \\ 
$((M_1 + M_2) *M_3)  \leftrightarrow ((f_1 \oplus f_2) \otimes f_3) $ \\ \\
Die Auswertung (Berechnung des Werts) eines Matrizenterms kann dann über die Auswertung (Berechnung des Werts) des zugehörigen Terms aus linearen Abbildungen erfolgen. \\
Dazu definiert man zuerst die Summe add bzw. das Produkt mul zweier Matrizen: \\ \\
$M_1 \; add \; M_2 :=   subst^{-1}(subst(M_1) \; \overline{add}\;   subst(M_2))$ \\ \\
wobei $\overline{add}$ die bekannte Addition zweier linearer Abbildungen bedeutet. \\
Umgeformt erinnert das an einen Isomorphismus:\\
$subst(M_1 \; add \; M_2) :=   subst(M_1) \; \overline{add}\;   subst(M_2)$ \\  \\
Intuitiv würde man dann annehmen:\\
$ev1(MT_1) = ev1(MT_2) \Leftrightarrow ev2(subst(MT_1)) = ev2(subst(MT_2))$ \\ 
wobei ev1 die Auswertung eines Matrizenterm und ev2 die Auswertung eines Terms aus linearen Abbildungen bedeutet.



\chapter{Induktive Definitionen}
Die in diesem Skript verwendeten begriffe beziehen sich auf das siehe Skript von Prof. Ekkart Kindler (siehe ab Seite 48): \\
c.web.de/@321555971283359751/eth5kar8UkRRHulj5XfVnQ 

\section{Definitionen} 
\subsection{Regelmenge} 
Eine Menge $R \subset P(X) \times X$  heißt eine Regelmenge über X, wobei für alle $(Y,x) \in R$ gilt, dass 
Y eine endliche Menge ist. Mit P(X) wird die Potenzmenge von X bezeichnet. 

\subsection{Folgerungsmenge (Ableitungsschritt)} 
Für eine Menge $M \subset X$ wird die direkte Folgerungsmenge (Konsequenz) wie folgt definiert: \\
$\widehat{R} = \{x \in X \; \vert \; \exists Y \subset M \; (Y,x) \in R\}$

\subsection{Definition I(R)} 
$Q_0 = \emptyset$ \\
... \\
$Q_{i+1} = \widehat{R} (Q_i)$ für $i \in \mathbb{N}$ \\ \\
$I(R) := \bigcup_{n=0}^{\infty} Q_n$ \\
bezeichnet die durch die Regelmenge R  induktiv definierte Menge. 

\section {Regelinduktion}
Sei R eine Menge von Regeln über X und P ein Prädikat über $I(R)$. \\
Um zu beweisen, dass für alle $z \in I(R)$ P(z) gilt, genügt Folgendes zu zeigen:\\
1) Induktionsanfang:\\
Zeige P(x) für alle x mit $(\emptyset,x) \in R$ \\
2) Induktionsannahme:\\
Sei $(\{y_1, ... ,y_n\}, x) \in R$ mit $n \ge 1$ eine beliebige Regel aus R mit folgenden Eigenschaften: \\
$P(y_1), ..., P(y_n)$  und  $y_1 \in I(R), ... ,  y_n \in I(R) $ \\
Zeige: P(x)

\section{Definition Konstruktortupel} 
1) \\
A ist eine beliebige Menge.\\
$F_0 \subset A$ mit $F_0 \neq \emptyset$ ist eine Menge von 0-stelligen Funktionen (0-stelligen inneren Verknüpfungen), also Konstanten aus A \\
$F_1$ ist eine Menge von 1-stelligen Funktionen (1-stelligen inneren Verknüpfungen) $f: A  \rightarrow A$  \\
$F_2$ ist eine Menge von 2-stelligen Funktionen (2-stelligen inneren Verknüpfungen) $f: A \times A \rightarrow A$  \\
$F := F_0 \cup F_1 \cup F_2$ \\
Dann nennt man $(A,F)$ das Konstruktortupel, das die Regelmenge $R(A,F)  \subset P(A) \times A$ erzeugt: \\
$R(A,F) := \{(\emptyset,a) \; \vert \; a \in F_0 \} \cup \{ (\{a\}, f_1(a)) \; \vert \; a \in A, f_1 \in F_1 \}  \cup \{ (\{a_1,a_2\}, f_2(a_1,a_2)) \; \vert \; a_1, a_2 \in A, f_2 \in F_2 \} $ \\ 
Die Elemente von F nennt man auch Konstruktorfunktionen.\\ \\

2) \\
k sei eine bijektive Abbildung (Korrespondenz) $k \colon F \to G$, die jeder n-stelligen Funktion $f_n \in F$ genau eine n-stellige Funktion $g_n \in G$ zuordnet mit: \\
$k(f_n) := g_n$ \\ \\
3) \\
Die Konstruktortupel $(A,F)$ und $(B,G)$ und die Korrespondenz k erzeugen die Regelmenge $R(A,F,B,G,k) \subset P(A \times B) \times B$:
$R(A,F,B,G,k) := \{(\emptyset,(f,k(f)) \; \vert \; f \in F_0 \} \; \cup \; \{ (\{(a, b)\}, (f(a), k(f)(b))) \; \vert \; a \in A, f \in F_1 \}  \; \cup \\
\hspace*{1.1cm}  \{ (\{(a_1,b_1),(a_2,b_2)\}, (f(a_1,a_2), k(f)(b_1,b_2))) \; \vert \; a_1, a_2 \in A, b_1, b_2 \in B, f_2 \in F_2 \} $  \\
Diese Regelmenge erzeugt die induktiv definierte Menge $I(A,F,B,G,k)$ \\ \\
4) \\
Das durch A, B, F, G erzeugte Tupel (A, B, F, G, k)  nennt man eine Regelbasis (Erzeugendensystem) für die Regelmengen $R(A,F), R(B,G), R(A,F,B,G,k)$     \\ \\
5) Definition: eindeutige Lesbarkeit \\
$I(A,F)$ ist eindeutig lesbar : $\Leftrightarrow$ \\
Für alle $a \in I(A,F)$ existiert genau eine Regel $(\{a_1, ... , a_r \},a) \in R(A,F)$ mit genau einer Konstrukorfunktion $f \in F$ mit genau jeweils den Argumenten $a_1, ... , a_r \in A$ mit $a= f(a_1, ... , a_r)$

\section{Definition Termmenge} 
$OP_i$ ist eine Menge von i-stelligen Funktionszeichen (Operatoren) $(0 \le i \le 2)$ \\
Diese sind jeweils paarweise verschieden.\\
$OP := OP_0 \cup OP_1 \cup OP_2$ \\
$A := (\{( \; ) \; (\} \cup OP)^*$   (Menge von Zeichenfolgen) \\
F ist eine Menge von i-stelligen Funktionen $f \colon A \times ... \times A \to A$ \quad (i - mal) \quad  $(0 \le i \le 2)$\\
$E \colon OP \to F$ ist eine bijektive Abbildung mit folgenden Eigenschaften:\\
$E(op) = op$ \quad für 0-stellige Funktionszeichen\\
$E(op)(a) = op(a)$ \quad für 1-stellige Funktionszeichen und $a \in A$\\
$E(op)(a_1,a_2) = (a_1 \; op \; a_2)$ \quad  für 2-stellige Funktionszeichen und $a_1,a_2 \in A$\\ 
Jedem n-stelligen Funktionszeichen op aus $OP_n$ wird also genau eine (korrespondierende, entsprechende) n-stellige Funktion $E(op_n) \colon A \times ... \times A \to A$ \quad (n - mal) zugeordnet:\\
$F_0 := E(OP_0)$ \\
$F_1 := E(OP_1)$ \\
$F_2 := E(OP_2)$ \\
Damit gilt:\\
$F := E(OP_0) \cup E(OP_1) \cup E(OP_2)=F_0 \cup F_1 \cup F_2$ \\
Die durch $(A,OP)$ induzierte Regelmenge $R(A,F) \subset P(A) \times A$ ist also: \\
$R(A,F) := \{(\emptyset,a) \; \vert \; a \in F_0 \} \cup \{ (\{a\}, f(a)) \; \vert \; a \in A, f \in F_1 \}  \cup \{ (\{a_1,a_2\}, f(a_1,a_2)) \; \vert \; a_1, a_2 \in A, f \in F_2 \} $ = \\ 
$\{(\emptyset,a) \; \vert \; a \in E_0 \} \cup \{ (\{a\}, op(a)) \; \vert \; a \in A, op \in E_1 \}  \cup \{ (\{a_1,a_2\}, (a_1 \;  op   \; a_2)) \; \vert \; a_1, a_2 \in A, op \in E_2 \} $\\  \\
Die durch $R(A,F) $ induktive definierte Menge $I(A,F)$ heißt eine Termmenge. \\
Die Menge der Primterme (Atome) einer Termmenge $I(A,F)$ wird mit $\Pi(I(A,F))$ bezeichnet.

\subsection{Lesbarkeit einer Termmenge} 
Jede Termmenge ist lesbar.

\subsection{Lemma 1} 
(A, B, F, G, k) sei eine Regelbasis. \\
1)
Für alle $a_1, a_2, a \in A$, $b_1, b_2, b \in B$, $f \in F$ gilt:\\
$ (\{(a_1,b_1), ... ,(a_r,b_r)\}, (f(a_1, ... , a_r), k(f)(b_1, ... , b_r)) \in R(A,F,B,G,k) \implies$ \\
$(\{a_1, ... ,a_r \},a) \in R(A,F) $ und $(\{b_1, ... ,b_r \},b) \in R(B,G) $ \\ \\


\section{Satz 1 (Funktionen erzeugen)} 
(A, B, F, G, k) sei eine Regelbasis. \\
1) \\
für alle $a \in A$, $b \in B$ gilt: \\
$(a,b) \in I(A,F,B,G,k) \implies a \in I(A,F)$ und $b \in I(B,G)$\\ \\
2) \\
Voraussetzungen:\\
$I(A,F)$ ist eindeutig lesbar.\\ \\
Behauptung:\\
2.1) $I(A,F,B,G,k)$ ist rechtseindeutig und \\
der Definitionsbereich $Db(I(A,F,B,G,k))=I(A,F)$ und \\ 
der Wertebereich $Wb(I(A,F,B,G,k))=I(B,G)$ \\ \\
Das bedeutet: \\
$I(A,F,B,G,k)$ ist rechtseindeutig auf $I(A,F,B,G,k) \Big|_{I(A,F)}$ mit Wertebereich $Wb(I(A,F,B,G,k))=I(B,G)$ \\ 
Damit gilt:\\
$I(A,F,B,G,k) \Big|_{I(A,F)} \colon I(A1,F1) \to B$ \quad ist eine Funktion \\
mit dem Definitionsbereich $I(A,F)$ und dem Wertebereich $I(B,G)$ \\  \\
2.2) Für alle $a \in I(A,F)$ gilt:\\
wenn $f_r$ eine $r > 0$ - stellige Funktion ist mit $a = f_r(a_1, ... , a_r)$ und $g_r = k(f_r$ die zu $f_r$ korrespondierende Funktion ist: \\ 
$I(A,F,B,G,k)(a) = g_r(I(A,F,B,G,k)(a_1), ... , I(A,F,B,G,k)(a_r))$ \\   
$I(A,F,B,G,k)(a) = k(a)$ \quad sonst, also $r=0$ \\ \\
3) \\
Vorraussetzungen:\\
$I(A,F)$ und $I(B,G)$ ist eindeutig lesbar. \\
Behauptung:\\
$I(A,F,B,G,k)$ ist bijektiv. \\ \\
Beweis: \\
1) \\
B1) Induktion über $I(A,F,B,G,k)$ \\
$B((a,b)) :\Leftrightarrow (a,b) \in I(A,F,B,G,k)  \implies a \in I(A,F)$ und $b \in I(B,G)$\\ 
Induktionsanfang:\\
sei $\emptyset, (a,b) \in R(A,F,B,G,k)$, also $a \in F_0$ und $b=k(f) \in G_0$, also $\emptyset, a \in R(A,F)$ und $\emptyset, b \in R(B,G)$, also $a \in I(R(A,F)$ und also $b \in I(R(B,G)$ \\
Induktionsannahme: \\
für alle Regeln $(M,(a,b)) \in R(A,F,B,G,k)$ und für alle $m \in M$ gilt B(m) \\ 
zeige B((a,b)) \\
Dazu sei $(a,b) \in R(A,F,B,G,k)$ \\
Dann existiert eine Regel mit $\{(a_1,b_1), ... ,(a_r,b_r)\},(a,b) \in R(A,F,B,G,k)$ und $(a_i,b_i) \in I(A,F,B,G,k)$ für alle $i \le r$.
Mit der Induktionsannahme gilt außerdem für alle $i \le r$: \\
$(a_i,b_i) \in I(A,F,B,G,k) \implies a_i \in I(A,F)$ und $b_i \in I(B,G)$\\   
Damit folgt für alle $i \le r$: $a_i \in I(A,F)$ und $b_i \in I(B,G)$\\   
Da nach Lemma 1 folgt: \\
$(\{a_1,a_2 \},a) \in R(A,F) $ und $(\{b_1,b_2 \},b) \in R(B,G) $, folgt also: \\
$a \in I(A,F)$ und $b \in I(B,G)$ \\ \\ 
2) \\
2.1) \\
a) \\
Induktion über $I(A,F))$ \\
$B(a) :\Leftrightarrow a \in I(A,F) \implies$ es existiert genau ein $b \in B$ mit $(a,b) \in I(A,F,B,G,k)$ \\ 
Induktionsanfang:\\
Sei $(\emptyset, a) \in R(A,F)$, also $k(a) \in G_0$, also $\emptyset, (a,k(a)) \in R(A,F,B,G,k)$, also $(a,k(a)) \in I(A,F,B,G,k)$\\ 
Induktionsannahme:\\
für alle Regeln $(M,x) \in R(A,F)$ mit $M \subset I(A,F)$ und für alle $m \in M$ gilt B(m) \\ 
zeige: B(a) \\ 
Dazu sei $a \in I(A,F))$. Da  $I(A,F))$ lesbar gilt:\\
Für alle $a \in I(A,F)$ existiert genau eine Regel $(\{a_1, ... , a_r \},a) \in R(A,F)$ mit genau einer Konstrukorfunktion $f \in F$ mit genau jeweils den Argumenten $a_1, ... , a_r \in A$ und $a_1, ... , a_r \in I(A,F) $ mit $a= f(a_1, ... , a_r)$ \\
Mit der Induktionsannahme gilt außerdem für alle $i \le r$ (wegen $a_i \in I(A,F))$ : \\
es existiert genau ein $b_i \in B$ mit $(a_i,b_i) \in I(A,F,B,G,k)$. \\
Da $(\{(a_1,b_1), ... , (a_r,b_r)\}, (f(a_1, ... , a_r), k(f)(a_1, ... , a_r))) \in R(A,F,B,G,k)$ und \\
$(a_i,b_i) \in I(A,F,B,G,k)$ für alle $i \le r$, folgt:\\
$((k(f))(a_1, ... , a_r), g(b_1, ... , b_r)) \in I(A,F,B,G,k)$ \\  \\
b) \\
Zeige: $Db(I(A,F,B,G))=I(A,F)$ \\ 
$"\Rightarrow"$: \\
sei $a \in Db(I(A,F,B,G)$, also existiert ein b mit $(a,b) \in I(A,F,B,G,k)$, also gilt nach 1) auch $a \in I(A,F)$ \\
$"\Leftarrow"$: \\
Sei $a \in I(A,F))$, dann existiert nach dem 1. Teil des Beweises (genau) ein b mit $(a,b) \in I(A,F,B,G,k)$, \\
also $a \in Db(I(A,F,B,G.k))$ \\ \\
c) \\
Zeige: $Wb(I(A,F,B,G,k))=I(B,G)$ \\
$"\Rightarrow"$: \\
sei $b \in Wb(I(A,F,B,G,k)$, also existiert ein $a \in A$ mit $(a,b) \in I(A,F,B,G,k)$, also gilt nach 1) auch $b \in I(B,G)$ \\
$"\Leftarrow"$: \\
Induktion über $I(R(B,G))$ \\
$B(a) :\Leftrightarrow b \in I(R(B,G))  \implies \exists$ ein $a \in A$ mit $(a,b) \in I(A,F,B,G,k)$ \\ 
Induktionsanfang:\\
Sei $(\emptyset, b) \in R(B,G)$, also $k^{-1}(b) \in F_0$, also $\emptyset, (k^{-1}(b),b) \in R(A,F,B,G,k)$, also $(k^{-1}(b),b) \in I(A,F,B,G,k)$, also $b \in Wb(I(A,F,B,G,k))$ \\ 
Induktionsannahme:\\
für alle Regeln $(M,x) \in R(A,F)$ mit $M \subset I(A,F)$ und für alle $m \in M$ gilt B(m) \\ 
zeige: B(a) \\ 
Dazu sei $b \in I(B,G)$ \\
Dann existiert eine Regel mit $(\{b_1, ... ,b_r\},b) \in R(B,G)$ und für alle $i \le r$ gilt $b_i \in I(B,G)$ \\
und es existiert ein $g \in G$ mit $b=g(b_1, ... , b_r)$ \\
Mit der Induktionsannahme gilt außerdem für alle $i \le r$ (wegen $b_i \in I(B,G))$: \\
es existiert ein $a_i \in A$ mit $(a_i,b_i) \in I(A,F,B,G,k)$. \\
Da $ (\{(a_1,b_1), ... ,(a_r,b_r)\}, (k^{-1}(g))(a_1, ... , a_r), g(b_1, ... , b_r)) \in R(A,F,B,G,k)$ und\\
$(a_i,b_i) \in I(A,F,B,G,k)$ für alle $i \le r$, folgt:\\
$((k^{-1}(g))(a_1, ... , a_r), g(b_1, ... , b_r)) \in I(A,F,B,G,k)$

\section{Beispiele induktiv definierter Mengen} 
\subsection{Beispiel:  \glqq einfachste Zahlenterme\glqq} 
Informal: \\
Ein Zahlenterm, der nur aus der öffnenden und der schließenden Klammer, den Zahlen 3 und 5 und dem Pluszeichen besteht, wie z.B:  8, 20, (3+5), (3-(5+3))\\ \\
Formal: \\
$OP_0 = \{ 3 , 5 \}$ \\
$OP_1 = \emptyset$ \\
$OP_2 = \{ + \}$ \\
$OP := OP_0 \cup OP_1 \cup OP_2$ \\
$A := (\{( \; )\} \cup OP)^*$    \quad (Menge von Zeichenfolgen) \\
$R(A,F):=$  \\
$\{ (\emptyset, E(3)), (\emptyset, E(5)) \} \cup \{   (\{a_1, a_2\} , E(+)(a_1,a_2)) \; \vert \; a_1 \in A, a_2 \in A\}$ = \\
$\{ (\emptyset, 3), (\emptyset, 5) \} \cup \{   (\{a_1, a_2\} , (a_1+a_2)) \; \vert \; a_1 \in A, a_2 \in A\}$\\ \\
Anschaulich:\\ 
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \\
$3$ \\ \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$   \\
$5$ \\ \\
$\{a_1, a_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $a_1, a_2 \in A$   \\ 
$(a_1 + a_2) $ \\ \\
Mögliche Terme: \\
3 \\
(((3+5) + 5) + 5) \\
5

\subsection{Beispiel:  \glqq Zahlenterme\glqq} 
Informal: \\
Ein Zahlenterm, der nur aus der öffnenden und der schließenden Klammer, den ganzen Zahlen, dem hochzwei Zeichen, dem Pluszeichen und dem Minuszeichen besteht, wie z.B:  8, 20, (3+5), (3-(5+3)) \\ \\
Die Regelbasis (A, B, F, G, k) wird wie folgt festgelegt: 

\subsubsection{Regelmenge $R(A,F)$}  
$OP_0 = \mathbb{Z}$ \\
$OP_1 = \{ q \}$ \quad q steht für Quadratzahl \\
$OP_2 = \{ +, - \}$ \\
$OP := OP_0 \cup OP_1 \cup OP_2$ \\
$A := (\{( \; )\} \cup OP)^*$   \quad  (Menge von Zeichenfolgen) \\ 
$R(A,F):=$  \\
$\{ (\emptyset, E(a)) \; \vert \; z \in OP_0\} \cup \{ (\{a\} , E(q)(a)) \; \vert \; a \in A\} \cup \{ (\{a_1, a_2\} , E(+)(a_1,a_2)) \; \vert \; a_1 \in A, a_2 \in A\} \cup$ \\ 
$\{ (\{a_1, a_2\} , E(-)(a_1,a_2)) \; \vert \; a_1 \in A, a_2 \in A\}$= \\ 
$\{ (\emptyset, a) \; \vert \; a \in OP_0\} \cup \{ (\{a\} , q(a)) \; \vert \; a \in A\} \cup \{ (\{a_1, a_2\} , (a_1+a_2)) \; \vert \; a_1 \in A, a_2 \in A\} \cup$ \\ 
$\{ (\{a_1, a_2\} , (a_1-a_2)) \; \vert \; a_1 \in A, a_2 \in A\}$\\ \\
Anschaulich: \\ 
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad    für jedes $z \in OP_0$  \\
$z$ \\ \\
$\{a\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $a_1, a_2 \in A$   \\ 
$q(a)$ \\ \\
$\{a_1, a_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $T_1, T_2 \in A$   \\ 
$(a_1 + a_2) $ \\ \\
$\{a_1, a_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $a_1, a_2 \in A$   \\ 
$(a_1 - a_2) $  \\ \\
Mögliche Terme: \\
(3-6) \\
((5+q(6))-(2+5))

\subsubsection{Regelmenge $R(B,G)$  bzgl. $R(A,F)$}  
Auswertung der Zahlenterme (informal): \\
Ein Zahlenterm aus dem Beispiel \glqq Zahlenterme\glqq \; wie z.B. (7+9), 8, (3-4), usw. soll ausgewertet werden. \\
Z.B. gibt die Auswertung von (7+9) den Wert 16.  \\ \\
Formal:\\
$B := \mathbb{Z} $\\
$G_0 = \mathbb{Z}$ \\
$G_1 = \{ h2\}$  \\
$G_2 = \{add, sub\}$ \\  
$k \colon F \to G$ mit:\\
$k(E(f)) = k(f)=f$ \quad für $f \in OP_0 \; (= G0 =\mathbb{Z})$ \\
$k(E(q))=h2$   \quad h2 bedeutet hochzwei berechnen \\
$k(E(+)) = add$  \quad add bedeutet übliche Addition zweier Zahlen \\
$k(E(-)) = sub$  \quad sub bedeutet übliche Subtraktion zweier Zahlen \\ 
Damit ist die Regelmenge $R(B,G)$ wie folgt festgelegt: \\ \\
$R(B,G):=$  \\
$\{ (\emptyset, z) \; \vert \; z \in G_0\} \cup \{ (\{b\} , E(q))(b) \; \vert \; b \in B\} \cup \{ (\{b_1, b_2\} , E(+))(b_!,b_2) \; \vert \; b_1 \in B, b_2 \in B\}$ \\
$\cup \{ (\{b_1, b_2\} , E(-))(b_1,b_2) \; \vert \; b_1 \in B, b_2 \in B\}$ \\
Anschaulich:\\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad    für jedes $z \in G_0$  \\
$z$ \\ \\
$\{z\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $z \in B$   \\ 
$h2(z) (=z^2)$ \\ \\ 
$\{z_1, z_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $z_1, z_2 \in B$   \\ 
$(z_1 \; sub \; z_2) $ \\ \\ 
$\{z_1, z_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $z_1, z_2 \in B$   \\ 
$(z_1 \; add \; z_2) $ 

\subsubsection{Regelmenge $R(A,F,B,G,k)$}  
Damit ist die Regelmenge $R(A,F,B,G,k)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in \mathbb{Z})$  \\
$(z, z) $ \\ \\
$\{(T, z)\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $(T, z) \in A$   \\ 
$(q(T), z^2)$ \\ \\
$\{(T_1, z_1), (T_2, z_2) \}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $(T_1, z_1), (T_2, z_2)  \in A$   \\ 
$( (T_1 + T_2) , z_1 \; add \; z_2 )$ \\ \\
$\{(T_1, z_1), (T_2, z_2) \}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $(T_1, z_1), (T_2, z_2)  \in A$   \\ 
$( (T_1 - T_2) , z_1 \; sub \; z_2 )$  \\ \\
Definiere:\\
$ev := R(A,F,B,G,k) \Big|_{I(A,F)}$ 


\subsubsection{Behauptungen}  
$ev((a_1 + a_2)) = add(ev(a_1),ev(a_2))$  \\
$ev( (a_1-a_2)) = sub(ev(a_1),I(R_2)(a_2))$  \\
$ev(q(a)) = h2(ev(a))$  \\
$ev(f) = f$ für $f \in F_0$ \\ \\
also, z.B: \\
$ev( (3+5) ) = add(3,5) = 8$  \\
$ev( q(8) ) = h2(ev(8) = h2(8) = 64$ \\
$ev( 123 ) = 123$ 

\subsection{Beispiel:  \glqq Zahlenterme mit Division durch 0\glqq} 
Informal: \\
Ein Zahlenterm, der nur aus der öffnenden und der schließenden Klammer, den ganzen Zahlen, dem hochzwei Zeichen, dem Pluszeichen und dem Minuszeichen besteht, wie z.B:  8, 20, (3+5), (3-(5+3)) \\ \\
Die Regelbasis (A, B, F, G, k) wird wie folgt festgelegt: 

\subsubsection{Regelmenge $R(A,F)$}  
$OP_0 = \mathbb{R}$ \\
$OP_1 = \{ q \}$ \quad q steht für Quadratzahl \\
$OP_2 = \{ +, -, / \}$ \\
$OP := OP_0 \cup OP_1 \cup OP_2$ \\
$A := (\{( \; )\} \cup OP)^*$   \quad  (Menge von Zeichenfolgen) \\ 

\subsubsection{Regelmenge $R(B,G)$  bzgl. $R(A,F)$}  
Auswertung der Zahlenterme (informal): \\
Ein Zahlenterm aus dem Beispiel \glqq Zahlenterme\glqq \; wie z.B. (7+9), 8, (3-4), usw. soll ausgewertet werden. \\
Z.B. gibt die Auswertung von (7+9) den Wert 16.  \\ \\
Formal:\\
$B := \mathbb{R} \cup \{\# \}$\\
$G_0 = \mathbb{R} \cup \{\# \}$\\
$G_1 = \{ h2\}$  \\
$G_2 = \{add, sub, div\}$ \\  
$k \colon F \to G$ mit:\\
$k(E(f)) = k(f)=f$ \quad für $f \in OP_0 $ \\
$k(E(q))\colon G_0 \to G_0, \ h2(z)=\begin{cases}  \text{bekannte Quadratfunktion}, & z \neq \# \ \\ \#, & \text{sonst} \end{cases}.
$ \\ \\ 
$k(E(+))\colon G_0 \times G_0 \to G_0, \ add(z_1,z_2)=\begin{cases}  \text{bekannte Addition}, & z_1\neq \#  \;  \text{und} z_2 \neq \# \\ \#, & \text{sonst} \end{cases}.
$ \\ \\ 
$k(E(-))\colon G_0 \times G_0 \to G_0, \ sub(x)=\begin{cases}  \text{bekannte Subtraktion}, & z_1\neq \# \;  \text{und} z_2 \neq \# \\ \#, & \text{sonst} \end{cases}.
$ \\ \\ 
$k(E(/))\colon G_0 \times G_0 \to G_0, \ div(z1,z_2)=\begin{cases} bekannte \; Division, & z_1\neq \# \;  \text{und} \; z_2 \neq \# \\  \#, & z_2=0
\\  \#, & z_1=\# \; oder \; z_2=\#
\end{cases}.
$ \\ \\ 
Damit ist die Regelmenge $R(B,G)$ wie folgt festgelegt: \\ \\
$R(B,G):=$  \\
$\{ (\emptyset, z) \; \vert \; z \in G_0\} \cup \{ (\{b\} , E(q))(b) \; \vert \; b \in B\} \cup \{ (\{b_1, b_2\} , E(+))(b_!,b_2) \; \vert \; b_1 \in B, b_2 \in B\}$ \\
$\cup \{ (\{b_1, b_2\} , E(-))(b_1,b_2) \; \vert \; b_1 \in B, b_2 \in B\} \cup 
\{ (\{b_1, b_2\} , E(/))(b_1,b_2) \; \vert \; b_1 \in B, b_2 \in B\}$ \\


Anschaulich:\\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad    für jedes $z \in G_0$  \\
$z$ \\ \\
$\{z\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $z \in B$   \\ 
$h2(z) (=z^2)$ \\ \\ 
$\{z_1, z_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $z_1, z_2 \in B$   \\ 
$(z_1 \; sub \; z_2) $ \\ \\ 
$\{z_1, z_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $z_1, z_2 \in B$   \\ 
$(z_1 \; add \; z_2) $  \\ \\
$\{z_1, z_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $z_1, z_2 \in B$  \\ 
$(z_1 \; div \; z_2) $  

\subsubsection{Regelmenge $R(A,F,B,G,k)$}  
Damit ist die Regelmenge $R(A,F,B,G,k)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in \mathbb{Z})$  \\
$(z, z) $ \\ \\
$\{(T, z)\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $(T, z) \in A$   \\ 
$(q(T), z^2)$ \\ \\
$\{(T_1, z_1), (T_2, z_2) \}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $(T_1, z_1), (T_2, z_2)  \in A$   \\ 
$( (T_1 + T_2) , z_1 \; add \; z_2 )$ \\ \\
$\{(T_1, z_1), (T_2, z_2) \}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $(T_1, z_1), (T_2, z_2)  \in A$   \\ 
$( (T_1 - T_2) , z_1 \; sub \; z_2 )$  \\ \\
$\{(T_1, z_1), (T_2, z_2) \}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $(T_1, z_1), (T_2, z_2)  \in A$  und $z_1 \neq \#$ und $z_2 \neq \#$ \\
$( (T_1 / T_2) , z_1 \; div \; z_2 )$  \\ \\
$\{(T_1, z_1), (T_2, z_2) \}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $(T_1, z_1), (T_2, z_2)  \in A$  und $z_1 = \#$ oder $z_2 = \#$ \\
$( (T_1 / T_2) , \#)$  \\ \\
Definiere:\\
$ev := R(A,F,B,G,k) \Big|_{I(A,F)}$ 


\subsubsection{Behauptungen}  
$ev((a_1 + a_2)) = add(ev(a_1),ev(a_2))$  \\
$ev( (a_1-a_2)) = sub(ev(a_1),I(R_2)(a_2))$  \\
$ev(q(a)) = h2(ev(a))$  \\
$ev(f) = f$ für $f \in F_0$ \\ \\
also, z.B: \\
$ev( (3+5) ) = add(3,5) = 8$  \\
$ev( q(8) ) = h2(ev(8) = h2(8) = 64$ \\
$ev( 123 ) = 123$ 


\chapter{Zusammenhang (erweiterter Isomorphismus)}
\section{Satz 2} 
Voraussetzungen:\\
V1) $(A1, F1, A2, F2, k12) )R_{F1} $ ist eine Regelbasis (Erzeugendensystem), wobei I(A1,F1) und I(A2,F2) eindeutig lesbar und Termmengen sind.\\
V2) $(A1, F1, B1, G1, k11) )$ ist eine Regelbasis (Erzeugendensystem) \\
V3) $(A2, F2, B2, G2, k2) )$ ist eine Regelbasis (Erzeugendensystem) \\
V4) $B1 = \Pi(I(A1,F1))$ \\
V5) $B2 = \Pi(I(A2,F2) )$ \\
V6) $k11(f)=f$ \quad für alle $f \in F1_0$, d.h. $f \in \Pi(I(A1,F1)) $ \\
V7) $k2(f)=f$ \quad für alle $f \in F2_0$ d.h. $f \in \Pi(I(A2,F2)) $ \\
V8) Für alle $f \in F1$ gilt:\\
$k11(f) := subst^{-1} \circ k2(k11(f)) \circ (subst\Big|_{\Pi(TM1)}, ... , subst\Big|_{\Pi(TM1)})$  \\
wobei n - mal subst vorkommt und n die Stellenzahl von f ist. \\ \\
Abkürzungen:\\
$subst := I(R_{F1,F2})\Big|_{I(A1,F1)}$  \quad subst  steht für Substitution \\
$ev1 := I(R_{F1,G1})\Big|_{I(A1,F1)}$   \quad ev1 steht für Evaluation (Auswertung, also Interpretation eines Terms) \\
$ev2 := I(R_{F2,G2})\Big|_{I(A2,F2)}$   \quad ev2  steht für Evaluation (Auswertung, also Interpretation eines Terms) \\ \\
Behauptungen:\\
1) \\
$subst \colon I(A1,F1) \to I(A2,F2)$ \quad ist eine bijektive Funktion \\
$ev1 \colon I(A1,F1) \to \Pi(I(A1,F1))$ \quad ist eine Funktion \\
$ev2 \colon I(A2,F2) \to \Pi(I(A2,F2))$ \quad ist eine Funktion \\ \\
2) \\
Für alle $T \in TM1$ gilt:\\
$subst(ev1(T)) = ev2(subst(T))$ \\ \\
Beweis:  \\
1) \\
a) I(A1,F1) und I(A2,F2) sind eindeutig lesbar. Dann folgt Behauptung mit Satz 1. \\
b) I(A1,F1) ist eindeutig lesbar. Dann folgt Behauptung mit Satz 1. \\
c) I(A2,F2) ist eindeutig lesbar. Dann folgt Behauptung mit Satz 1. \\ \\
2) \\
(Induktion über $I(A,F))$ \\
$B(a) :\Leftrightarrow T \in I(A,F)  \implies subst(ev1(T)) = ev2(subst(T))$ \\ 
Induktionsanfang:\\
Sei $(\emptyset, T) \in R(A,F)$, also $ev1(T) = k(T)=T$, also:\\
$subst(ev1(T)) = subst(T)$ \\ 
$ev2(subst(T)) = subst(T)$ , da $subst(T) = k3(T) \in G3_0 = B2$ \\ \\
Induktionsannahme:\\
für alle Regeln $(M,x) \in R_{F1}$ mit $M \subset I(R(A,F)1)$ und für alle $m \in M$ gilt B(m) \\ 
zeige: B(T) \\ 
Dazu sei $T \in I(R_{F1})$ \\
Dann existiert genau eine Regel und genau ein f mit $(\{T_1, ... ,T_r\},T) \in R_{F1}$ und $T=f(T_1, ... ,T_r)$ und für alle $i \le r$ gilt $T_i \in I(A,F)$ \\
Mit der Induktionsannahme gilt außerdem für alle $i \le r$: \\
$subst(ev1(T_i)) = ev2(subst(T_i))$ \\ 
Zeige:  $subst(ev1(T)) = ev2(subst(T))$ \\ 
Es gilt: (Satz 1 2.2):\\
$subst(ev1(T)=f(T_1, ... ,T_r))) =  subst \big( k11(f) \big (ev1(T_1), ... , ev2(T_r)) \big)=$ \\ 
$subst \big(\; subst^{-1} \circ k2(k11(f)) \circ (subst, ... , subst) \; \big (ev1(T_1), ... , ev2(T_r)) \big)=$ \\ 
$subst \big(\; subst^{-1} ( k2(k11(f)) ( (subst, ... , subst)      \; \big (ev1(T_1), ... , ev2(T_r))))  \big)=$ \\ 
$k2(k11(f)) ( (subst, ... , subst)      \; \big (ev1(T_1), ... , ev2(T_r)))=$ \\ 
$k2(k11(f)) (subst(ev1(T_1)), ... , subst(ev1(T_r)))=$ \\ 
andererseits gilt: \\
$ev2(subst(f(T_1, ... ,T_r))) = ev2( k12(f) (subst(T_1), ... , subst(T_r))) = $ \\
$k2(k12(f)) (ev2(subst(T_1)), ... , ev2(subst(T_r))) $
Da mit der Induktionsannahme für alle $i \le r$ gilt: \\
$subst(ev1(T_i)) = ev2(subst(T_i))$ \\ 
folgt die Behauptung.


\section{Skizze} 
Termmenge I(A1,F1)  \hspace{3cm}  $\xrightarrow {\text{k12}}$ \hspace{3cm}  Termmenge Termmenge I(A2,F2) \\ \\
\hspace*{1cm}  $\downarrow$ \hspace{10cm} $\downarrow$ \\
\hspace*{1cm}  $\downarrow$ \hspace{10cm} $\downarrow$ \\
\hspace*{1cm}  $\downarrow$ k11 \hspace{9.3cm} $\downarrow$ k2\\
\hspace*{1cm}  $\downarrow$ \hspace{10cm} $\downarrow$ \\
\hspace*{1cm}  $\downarrow$ \hspace{10cm} $\downarrow$ \\ \\
Atome $\Pi(I(A1,F1))$   \hspace{7cm} Atome $\Pi(TM2)$ von $\Pi(I(A2,F2))$  \\ \\ \\
$k11(f) := subst^{-1} \circ k2(k11(f)) \circ (subst, ... , subst)$  \\
wobei n - mal subst vorkommt und n die Stellenzahl von f ist. \\


\section{Satz 3} 
Voraussetzungen: \\
wie in Satz 2 \\ \\
Behauptung:\\
Für alle $T_1, T_2  \in TM1$ gilt:\\
$ev1(T_1) = ev1(T_2) \Leftrightarrow ev2(subst(T_1)) = ev2(subst(T_2))$ \\ \\
Beweis:\\
Mit Satz 2 folgt:\\
$ev2(subst(T_1)) = ev2(subst(T_2)) \Leftrightarrow subst(ev1(T_1)) = subst(ev1(T_2))$ \\ 
Es gilt aber:\\
$subst(ev1(T_1)) = subst(ev1(T_2)) \Leftrightarrow ev1(T_1)) = ev1(T_2))$


\newpage
\section{Beispiel zu Satz 3: Dualzahlen - Dezimalzahlen} 
$(A1, F1, A2, F2, k12) )R_{F1} $ ist eine Regelbasis (Erzeugendensystem), wobei I(A1,F1) und I(A2,F2) eindeutig lesbar und Termmengen sind.\\
$(A1, F1, B1, G1, k11) )$ ist eine Regelbasis (Erzeugendensystem) \\
$(A2, F2, B2, G2, k2) )$ ist eine Regelbasis (Erzeugendensystem) \\
mit den dazugehörigen Eigenschaften:\\ \\
1) Definition von A1 und F1:\\
$OP_0 =$ Menge aller Dualzahlen (=Binärzahlen)\\ 
$OP_1 = \emptyset$ \\
$OP_2 = \{ +_2 , *_2 \}$ \\
$OP = OP_0 \cup OP_1 \cup OP_2$ \\
$f_{+_2} := E(+_2)$\\
$f_{*_2} := E(*_2)$ \\
$A1 := (\{( \; )\} \cup OP)^*$   \quad  (Menge von Zeichenfolgen) \\ \\
Damit ist die Regelmenge $R(A1,F1)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in Z$  \\
$z$ \\ \\
$\{BT_1, BT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $BT_1, BT_2 \in A1$   \\ 
$(BT_1 +_2 BT_2) $ \\ \\
$\{BT_1, BT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $BT_1, BT_2 \in A1$   \\ 
$(BT_1 *_2 BT_2) $  \\ \\
2) Definition von A2 und F2:\\
$OP_0 =$ Menge aller Dezimalzahlen  \\
$OP_1 = \emptyset$ \\
$OP_2 = \{ +, * \}$ \\ 	
$OP = OP_0 \cup OP_1 \cup OP_2$ \\
$f_{+} := E(+)$ \\
$f_{*} := E(*)$ \\
$A2 := (\{( \; )\} \cup OP)^*$   \quad  (Menge von Zeichenfolgen) \\ \\
Damit ist die Regelmenge $R(A2,F2)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in Z$  \\
$z$ \\ \\
$\{DT_1, DT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $DT_1, DT_2 \in A2$   \\ 
$(DT_1 + DT_2) $ \\ \\
$\{DT_1, DT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $DT_1, DT_2 \in A2$   \\ 
$(DT_1 * DT_2) $  \\ \\
3) Definition von B1 und G1:\\
$B1 = \Pi(I(A1,F1))$ = Menge aller Primterme von I(A1,F1) = Menge aller Binärzahlen\\
$k11(f) = f$ \quad für alle $f \in F1_0$ \\
$k11(f_{+2}) = add_2$ \quad für alle $f \in F1_2$ \\
$k11(f_{*2}) = mul_2$ \quad für alle $f \in F1_2$ \\
Damit ist die Regelmenge $R(B1,G1)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in B1$  \\
$z$ \\ \\
$\{b_1, b_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $b_1, b_2 \in B1$   \\ 
$(b_1 \; add_2 \; b_2) $ \\ \\
$\{b_1, b_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $b_1, b_2 \in B1$   \\ 
$(b_1 \; *_2 \; b_2) $  \\ \\
4) Definition von B2 und G2:\\
$B2 = \Pi(I(A2,F2))$ = Menge aller Primterme von I(A2,F2) = Menge aller Dezimalzahlen $\ge 0$\\
$k2(f) = f$ \quad für alle $f \in F2_0$ \\
$k2(f_{+}) = add_{10}$ \quad für alle $f \in F2_2$ \\
$k2(f_{*}) = mul_{10}$ \quad für alle $f \in F2_2$ \quad wobei\\
$add_{10}$ und $ mul_{10}$ die bekannte Addition bzw. Multiplikation von Dezimalzahlen bedeutet.\\
Damit ist die Regelmenge $R(B2,G2)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in B2$  \\
$z$ \\ \\
$\{d_1, d_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $d_1, d_2 \in B2$   \\ 
$(d_1 \; add_{10} \; d_2) $ \\ \\
$\{d_1, d_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $d_1, d_2 \in B2$   \\ 
$(d_1 \; *_{10} \;d_2) $  \\ \\
$k11(f) := subst^{-1} \circ k2(k11(f)) \circ (subst\Big|_{\Pi(TM1)}, ... , subst\Big|_{\Pi(TM1)})$  \\
wobei n - mal subst vorkommt und n die Stellenzahl von f ist. \\ \\
Damit sind die Voraussetzungen von Satz 3 erfüllt.\\ \\
Dann gilt z.B:\\
$ev1(((101_2 +_2 10_2) *_2 (100_2 + 11_2))) = ev1( (1001_2 +_2 10_2) )$ gdw \\
$ev2(subst((101_2 +_2 10_2) *_2 (100_2 + 11_2))) = ev2(subst(1001_2 +_2 11_2) )$ gdw \\
$ (5 \; add_{10} \; 2)  *_{10} (4 \; add_{10} \; 3) =  9 \; add_{10} \; 3$ gdw \\
$49  = 12$ 


\newpage
\section{Beispiel zu Satz 3: Matrizen - Lineare Abbildungen} 
$(A1, F1, A2, F2, k12) )R_{F1} $ ist eine Regelbasis (Erzeugendensystem), wobei I(A1,F1) und I(A2,F2) eindeutig lesbar und Termmengen sind.\\
$(A1, F1, B1, G1, k11) )$ ist eine Regelbasis (Erzeugendensystem) \\
$(A2, F2, B2, G2, k2) )$ ist eine Regelbasis (Erzeugendensystem) 
mit den dazugehörigen Eigenschaften:

\subsection{Definition von A1 und F1}
$OP_0 = {Mat(\mathbb{K}) := \bigcup_{n,m\in\mathbb{N}}Mat(n,m,\mathbb{K})}$ \\
$OP_1 = \emptyset$ \\
$OP_2 = \{ +_M , *_M \}$ \\
$OP = OP_0 \cup OP_1 \cup OP_2$ \\
$f_{+_M} := E(+_M)$\\
$f_{*_M} := E(*_M)$ \\
$A1 := (\{( \; )\} \cup OP)^*$   \quad  (Menge von Zeichenfolgen) \\ \\
Damit ist die Regelmenge $R(A1,F1)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in Mat(\mathbb{K})$  \\
$z$ \\ \\
$\{MT_1, MT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $MT_1, MT_2 \in A1$   \\ 
$(MT_1 +_M MT_2) $ \\ \\
$\{MT_1, MT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $MT_1, MT_2 \in A1$   \\ 
$(MT_1 *_M MT_2) $  

\subsection{Definition von A2 und F2}
$OP_0 ={Lin(\mathbb{K}) := \bigcup_{n,m\in\mathbb{N}}Lin(\mathbb{K}^n,K^m)}$ \\
$OP_1 = \emptyset$ \\
$OP_2 = \{ +_L, *_L \}$ \\ 	
$OP = OP_0 \cup OP_1 \cup OP_2$ \\
$f_{+_M} := E(+_M)$ \\
$f_{*_M} := E(*_M)$ \\
$A2 := (\{( \; )\} \cup OP)^*$   \quad  (Menge von Zeichenfolgen) \\ \\
Damit ist die Regelmenge $R(A2,F2)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in Lin(\mathbb{K})$  \\
$z$ \\ \\
$\{LT_1, LT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $DT_1, DT_2 \in A2$   \\ 
$(LT_1 + LT_2) $ \\ \\
$\{LT_1, LT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $DT_1, DT_2 \in A2$   \\ 
$(LT_1 * LT_2) $  

\subsection{Definition von B2 und G2}
$B2 = \Pi(I(A2,F2))$ = Menge aller Primterme von I(A2,F2) = ${Lin(\mathbb{K}) := \bigcup_{n,m\in\mathbb{N}}Lin(\mathbb{K}^n,K^m)} \cup \{\#\}$ \\
$k2(f) = f$ \quad für alle $f \in F2_0$ \\
$k2(f_{+L}) = add_{L}$ \quad für alle $f \in F2_2$ \\
$k2(f_{*L}) = mul_{L}$ \quad für alle $f \in F2_2$ \quad wobei\\
$add_{L}$ und $ mul_{L}$ die bekannte Addition bzw. Multiplikation von linearen Abbildungen bedeutet:\\
$add_L \colon B_2 \times B_2 \to B_2, \ add_L(l_1, l_2)=\begin{cases}  \text{BA}, & l_1\neq \# \;  \text{und} l_2 \neq \# \; \text{und Abbildungen passen zusammen}   \\ \#, & l_1\neq \# \;  \text{und} l_2 \neq \# \; \text{und Abbildungen passen nicht zusammen} \\ \#, & l_1 = \#  \; \text{oder} \; l_2=\#\end{cases}.$ \\ 
wobei BA die bekannte Addition von linearen Abbildungen bedeutet. \\ \\
$mul_L \colon B_2 \times B_2 \to B_2, \ mul_L(l_1, l_2)=\begin{cases}  \text{BM}, & l_1\neq \# \;  \text{und} l_2 \neq \# \; \text{und Abbildungen passen zusammen}   \\ \#, & l_1\neq \# \;  \text{und} l_2 \neq \# \; \text{und Abbildungen passen nicht zusammen} \\ \#, & l_1 = \#  \; \text{oder} \; l_2=\#\end{cases}.$ \\ 
wobei BM die bekannte Multiplikation von linearen Abbildungen bedeutet. 

\subsection{Definition von B1 und G1}
$B1 = \Pi(I(A1,F1))$ = Menge aller Primterme von I(A1,F1) = $Mat(K) := \bigcup_{n,m\in\mathbb{N}}Mat(n,m,K) \cup \{\#\}$ \\
$k11(f) = f$ \quad für alle $f \in F1_0$ \\
$k11(f_{+M}) = add_M$ \quad für alle $f \in F1_2$ \\
$k11(f_{*M}) = mul_M$ \quad für alle $f \in F1_2$ \\ \\
Damit ist die Regelmenge $R(B1,G1)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $M \in B1$  \\
$M$ \\ \\
$\{M_1, M_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $b_1, b_2 \in B1$   \\ 
$(M_1 \; add_M \; M_2) $ \\ \\
$\{M_1, M_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $M_1, M_2 \in B1$   \\ 
$(M_1 \; *_M \; M_2) $  \\ \\
wobei definiert wird:\\
$add_M := k11(f_{+M}) := subst^{-1} \circ k2(k11(f_{+M}) \circ (subst\Big|_{\Pi(TM1)}, ... , subst\Big|_{\Pi(TM1)})$ = \\
$subst^{-1} \circ k2(add_{M}) \circ (subst\Big|_{\Pi(TM1)}, ... , subst\Big|_{\Pi(TM1)})$ = \\
$subst^{-1} \circ add_{L} \circ (subst\Big|_{\Pi(TM1)}, ... , subst\Big|_{\Pi(TM1)})$ = \\
wobei n - mal subst vorkommt und n die Stellenzahl von f ist. \\



$mul_M := k11(*_M) := subst^{-1} \circ k2(k11(*_M)) \circ (subst\Big|_{\Pi(TM1)}, ... , subst\Big|_{\Pi(TM1)})$  \\
wobei n - mal subst vorkommt und n die Stellenzahl von f ist. 








Damit ist die Regelmenge $R(B2,G2)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $z \in B2$  \\
$z$ \\ \\
$\{l_1, l_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $l_1,l_2 \in B2$   \\ 
$(l_1 \; add_{L} \; l_2) $ \\ \\  
$\{l_1, l_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $l_1, l_2 \in B2$   \\ 
$(l_1 \; *_{L} \;l_2) $  \\ \\
Damit sind die Voraussetzungen von Satz 3 erfüllt.\\ \\
Dann gilt z.B:\\







$ev1(((\left[ \begin{array}{rr}
1 & 6  \\
2 & 7  \\
\end{array}\right] 
 +_M  \left[ \begin{array}{rrr}
1 & 6 & 7 \\
2 & 7  & 4\\
\end{array}\right] 
) *_M 
\left[ \begin{array}{rrr}
2 & 3 & 5 \\
1 & 2  & 3\\
\end{array}\right] 
)
)=ev1(\left[ \begin{array}{rr}
1 & 6  \\
2 & 7  \\
\end{array}\right]) 
$ gdw \\
$ev2(subst((((\left[ \begin{array}{rr}
1 & 6  \\
2 & 7  \\
\end{array}\right] 
 +_M  \left[ \begin{array}{rrr}
1 & 6 & 7 \\
2 & 7  & 4\\
\end{array}\right] 
) *_M 
\left[ \begin{array}{rrr}
2 & 3 & 5 \\
1 & 2  & 3\\
\end{array}\right] 
)
))=ev2(subst((\left[ \begin{array}{rr}
1 & 6  \\
2 & 7  \\
\end{array}\right])) 
$ gdw \\
$ev2((((\left[ \begin{array}{rr}
1 & 6  \\
2 & 7  \\
\end{array}\right]_L 
 +_M  \left[ \begin{array}{rrr}
1 & 6 & 7 \\
2 & 7  & 4\\
\end{array}\right]_L 
) *_M 
\left[ \begin{array}{rrr}
2 & 3 & 5 \\
1 & 2  & 3\\
\end{array}\right]_L 
)
)=ev2((\left[ \begin{array}{rr}
1 & 6  \\
2 & 7  \\
\end{array}\right])_L 
$ gdw \\
$\# =
\left[ \begin{array}{rr}
1 & 6  \\
2 & 7  \\
\end{array}\right]_L 
$




chapter{Schrott}
$X := \operatorname{Lin}(K^n,K^m) \times \operatorname{Lin}(K^k,K^p)$ \\

$mul_L \colon B_2 \times B_2 \to B_2, \ mul_L(l_1, l_2)=\begin{cases}  \text{bekannte Multiplikation}, & z_1\neq \# \;  \text{und} z_2 \neq \# \;  \text{und} \; m=k  \\ \#, & z_1\neq \# \;  \text{und} z_2 \neq \# \; \text{und} \; m \neq k \\ \#, & l_1 = \#  \; \text{oder} \; z_2=\#\end{cases}.$ \\ \\

$add_L \colon B_2 \times B_2 \to B_2, \ add_L(l_1, l_2)=\begin{cases}  \text{bekannte Addition}, & z_1\neq \# \;  \text{und} z_2 \neq \# \;  \text{und} \; m=k  \\ \#, & z_1\neq \# \;  \text{und} z_2 \neq \# \; \text{und} \; m \neq k \\ \#, & l_1 = \#  \; \text{oder} \; z_2=\#\end{cases}.$ \\ \\

$add_L\colon \operatorname{Lin}(K^n,K^m) \times \operatorname{Lin}(K^k,K^p), \ add_L(l_1, l_2)=\begin{cases} bekannte Addition, & n=k \;und \;  m=p \\ \#, & sonst\end{cases}.
$ \\ 





\end{document}
