%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 (diese werden hier nochmals kurz erklärt) beziehen sich auf das siehe Skript von Prof. Ekkart Kindler (siehe ab Seite 48): \\
\url{https://umaterialien.de/THEORETISCHEINFORMATIK/Kapitel4.pdf}


\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} 
\subsection{} 
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 oder Konstruktoren.

\subsection{} 
k sei eine bijektive Abbildung (Korrespondenz, Kopplung) $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$ 

\subsection{} 
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 (A \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*{3.3cm}  \{ (\{(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)$ 

\subsection{} 
Das Tupel (A, B, F, G, k)  nennt man einen Relationsgenerator für die Relation $I(A,F,B,G,k)$. \\
Ist $I(A,F,B,G,k)$ rechtseindeutig, nennt man das Tupel (A, B, F, G, k)  einen Funktionsgenerator von $I(A,F,B,G,k)$. 

\subsection{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}\},a) \in R(A,F)$ mit genau einer Konstrukorfunktion $f_a \in F$ mit genau jeweils den Argumenten $a_1, ... , a_{r_a} \in A$ mit $a= f_a(a_1, ... , a_{r_a})$ \\
Bem: Für $r_a=0$ wird definiert:\\
$\{a_1, ... , a_{r _a}\} := \emptyset$ und $f_a(a_1, ... , a_{r_a}) := f_a =a$

\section{Definition Termmenge} 
$OP_i$ ist eine Menge von i-stelligen Funktionszeichen (Operatoren) $(0 \le i \le 2)$ \\
Diese sind jeweils paarweise verschieden.\\
$OP_S$ ist eine Menge mit genau einem 2-stelligen Funktionszeichen (S intendiert Skalarmultiplikation) oder die leere Menge (wenn keine Skalarmultiplikation vorkommt).\\
V (soll Vektoren intendieren) ist eine beliebige Menge, die auch leer sein kann. \\
$OP := OP_0 \cup OP_1 \cup OP_2$ \\
$A := (\{( \; , ) \} \cup OP)^*$   (Menge von Zeichenfolgen) \\
$F_0 := OP_0$ \\
$F_1 :=\{f_{op}: A \rightarrow A   \; \vert \; f_{op}(a) = op(a) \; \text{und} \; op \in OP_1\} \; \cup$ \\
$F_2 :=\{f_{op}: A \times A \rightarrow A   \; \vert \; f_{op}(a_1, a_2) = (a_1 \; op \; a_2) \; \text{und} \; op \in OP_2\}$ \\
$F := F_0 \cup F_1 \cup F_2$ \\ \\
Die durch $R(A,F) $ induktive definierte Menge $I(A,F)$ heißt eine Termmenge. \\
$\Pi(I(A,F))$ := $F_0$ wird auch als Menge der Primterme (Atome) einer Termmenge $I(A,F)$ bezeichnet

\subsection{Option Skalarmultiplikation} 
Falls $OP_S \neq \emptyset$, dann wird definiert: \\
$(\mathbb{K} , \fbox{+},  \boxed{\cdot})$ ist ein mathematischer Körper.\\
$\mathbb{KT}$ ist - informal beschrieben - die zugehörige Menge aus Termen, die mit Elementen aus $\{ ( , ), \fbox{+},  \boxed{\cdot} \} \cup \mathbb{K}$ aufgebaut ist. (formal analog zu dem Beispiel unten mit Zahlenterme)\\ 
und es wird festgelegt: \\
$A := (\{( \; , ) \} \cup OP \cup OP_S \cup \mathbb{KT} )^*$   (Menge von Zeichenfolgen) \\
$F_S = \{f_{kt} : A \rightarrow A \; \vert \;  f_{kt}(a) = (kt \; op \; a) \; \text{und} \; kt \in \mathbb{KT} , a \in OP_S \}$ \\
$F_1$ wird wie folgt neu definiert:\\
$F_1 :=\{f_{op}: A \rightarrow A   \; \vert \; f_{op}(a) = op(a) \; \text{und} \; op \in OP_1\} \; \cup F_S$ 
 
\subsection{Lesbarkeit einer Termmenge} 
Jede Termmenge ist lesbar.

\subsection{Lemma 1} 
(A, B, F, G, k) sei ein Relationsgenerator. \\
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 ein Relationsgenerator. \\
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 ist (A,F,B,G,k) ein Funktionsgenerator von $I(A,F,B,G,k)$. \\
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:\\
$I(A,F,B,G,k)(a) = k(f_a)(I(A,F,B,G,k)(a_1), ... , I(A,F,B,G,k)(a_{r_a}))$ \quad falls $r_a > 0$\\   
$I(A,F,B,G,k)(a) = k(a)$ \quad sonst, also $r_a=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)$ \\ 
2.2) \\
Da $I(A,F)$ eindeutig lesbar, gilt: \\
Fall 1: $r_a > 0$:\\
$a=f_a(a_1, ... , a_{r_a})$,  also: \\
$(\{(a_1, I(A,F,B,G,k)(a_1)), ... , (a_r, I(A,F,B,G,k)(a_{r_a}))\},\\
\hspace*{4.0cm}   (f_a(a_1, ..., a_{r_a}) , k(f_a)(I(A,F,B,G,k)(a_1),I(A,F,B,G,k)(a_{r_a})))) \in R(A,F,B,G,k) $ \\
Da gilt: \\
$(a_1, I(A,F,B,G,k)(a_1)) \in I(A,F,B,G,k)$, ... , $(a_{r_a}, I(A,F,B,G,k)(a_{r_a})) \in I(A,F,B,G,k)$, also:\\
$(f_a(a_1, ..., a_{r_a}) , k(f_a)(I(A,F,B,G,k)(a_1),I(A,F,B,G,k)(a_{r_a}))) \in I(A,F,B,G,k) $, also: \\
$(a , k(f_a)(I(A,F,B,G,k)(a_1),I(A,F,B,G,k)(a_{r_a}))) \in I(A,F,B,G,k) $, also: \\
$I(A,F,B,G,k)(a) = k(f_a)(I(A,F,B,G,k)(a_1), ... , I(A,F,B,G,k)(a_{r_a}))$ \\   
Fall 2: $r_a = 0$:\\
also $f_a=a \in F_0$ und deshalb $k(f_a) \in G_0$, also $(\emptyset, (f_a,k(f_a)) \in R(A,F,B,G,k)$, also:\\
$(f_a,k(f_a)) \in I(A,F,B,G,k)$, also: $(a,k(a)) \in I(A,F,B,G,k)$, also: \\
$I(A,F,B,G,k)(a) = k(a)$

\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:  3, 5, (3+5), (3-(5+3))\\ \\
Formal: \\
$OP_S = \emptyset$ \\
$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, f_3), (\emptyset, f_5) \} \cup \{   (\{a_1, a_2\} , f_+(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, (13+15), (2-(8+11)) \\ \\
Der Funktionsgenerator (A, B, F, G, k) wird wie folgt festgelegt: 

\subsubsection{Regelmenge $R(A,F)$}  
$OP_S = \emptyset$ \\
$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, f_a) \; \vert \; a \in OP_0\} \cup \{ (\{a\} , f_q(a)) \; \vert \; a \in A\} \cup \{ (\{a_1, a_2\} , f_+(a_1,a_2)) \; \vert \; a_1 \in A, a_2 \in A\} \; \cup$ \\ 
$\{ (\{a_1, a_2\} , f_-(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 vorigen 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(f)=f$ \quad für $f \in OP_0 \; (= G0 =\mathbb{Z})$ \\
$k(f_q)=h2$   \quad h2 bedeutet hochzwei berechnen \\
$k(f_+) = add$  \quad add bedeutet übliche Addition zweier Zahlen \\
$k(f_-) = 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\} , f_q(b) \; \vert \; b \in B\} \; \cup \; \{ (\{b_1, b_2\} , f_+(b_!,b_2)) \; \vert \; b_1 \in B, b_2 \in B\}$ \\
$\; \cup \; \{ (\{b_1, b_2\} , f_-(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 \times B $   \\ 
$(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 \times B$   \\ 
$( (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 \times B$   \\ 
$( (T_1 - T_2) , z_1 \; sub \; z_2 )$  \\ \\
Definiere:\\
$ev := R(A,F,B,G,k) \Big|_{I(A,F)}$ \quad ev steht für evaluieren


\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(ev(3),ev(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: \\
Zahlenterme wie oben, nur dass noch die Division dazukommt. \\ \\
Der Funktionsgenerator  (A, B, F, G, k) wird wie folgt festgelegt: 

\subsubsection{Regelmenge $R(A,F)$}  
$OP_S = \emptyset$ \\
$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): \\
Auswertung der Zahlenterm wie im vorigen Beispiel und der Besonderheit, dass bei Division durch 0 dieser das Sonderzeichen $\#$ zugewiesen wird. Dadurch kommt der Wert $\#$ ins Spiel. Mit diesem müssen deshalb auch die anderen Rechenoperationen zurecht kommen können.\\
Beispiel:\\
$ ((3+(7/0)) - 9)$ hat dier Auswertung $\#$ \\ \\
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(f)=f$ \quad für $f \in OP_0 $ \\
$k(f_q) := h2(z), \quad k(f_+) := add, \quad k(f_-) := sub, \quad k(f_/) := div$ \quad mit jeweils:\\
$h2 \colon G_0 \to G_0, \ h2(z)=\begin{cases}  \text{bekannte Quadratfunktion}, & z \neq \# \ \\ \#, & \text{sonst} \end{cases}.
$ \\ \\ 
$add \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}.
$ \\ \\ 
$sub \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}.
$ \\ \\ 
$div \colon G_0 \times G_0 \to G_0, \ div(z_1,z_2)=\begin{cases} bekannte \; Division, & z_1\neq \# \;  \text{und} \; z_2 \neq \#  \; \text{und} \; z_2 \neq 0\\  \# , & \text{sonst}
\end{cases}.
$ \\ \\ 
Damit ist die Regelmenge $R(B,G)$ wie folgt festgelegt: \\ \\
$R(B,G):=$  \\
$\{ (\emptyset, z) \; \vert \; z \in G_0\} \cup \{ (\{b\} , h2(b)) \; \vert \; b \in B\} \cup \{ (\{b_1, b_2\} , add(b_!,b_2)) \; \vert \; b_1 \in B, b_2 \in B\}$ \\
$\cup \{ (\{b_1, b_2\} , sub(b_1,b_2)) \; \vert \; b_1 \in B, b_2 \in B\} \cup 
\{ (\{b_1, b_2\} , div(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 \times B$   \\ 
$(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 \times B$   \\ 
$( (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 \times B$   \\ 
$( (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 \times B$  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 \times B$  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 / 0) ) = div(ev(3), ev(0)) = div(3,0) = \#$  \\
$ev( ((3 / 0) + 7) = add( ev( (3/0), ev(7))) = add( \#, 7) = \#$  \\ \\

\chapter{Zusammenhang (erweiterter Isomorphismus)}
\section{Satz 2} 
Voraussetzungen:\\
V1) $(A1, F1, A2, F2, k12) )$ ist ein Funktionsgenerator mit I(A1,F1) und I(A2,F2) Termmengen (also eindeutig lesbar).\\
V2) $(A1, F1, B1, G1, k11) )$ ist ein Relationsgenerator und mit V1) auch ein Funktionsgenerator. \\
V3) $(A2, F2, B2, G2, k2) )$ ist ein Relationsgenerator und mit V1) auch ein Funktionsgenerator. \\
V4) $B1 = F1_0 = \Pi(I(A1,F1))$ \\
V5) $B2 = F2_0 = \Pi(I(A2,F2) )$ \\
V6) $k2(f)=f$ \quad für alle $f \in B2 = \Pi(I(A2,F2)) $ \\
V7) $k11 \colon F1 \to G1, \ k11(f_n)=\begin{cases}  subst^{-1} \circ (k2(k12(f_n))) \circ ({\overset{n}{subst}\Big|_{B1} }), & n>0
 \\ subst^{-1} \circ (k2(k12(f_n))) \quad (=f_n), & n=0 \end{cases}.$ \\ 
mit folgenden Abkürzungen:\\
$subst := I(A1, F1, A2, F2, k)\Big|_{I(A1,F1)}$  \quad subst  steht für Substitution \\
$ev1 := I(A1, F1, B1, G1, k)\Big|_{I(A1,F1)}$   \quad ev1 steht für Evaluation (Auswertung, Interpretation) eines Terms 
\\
$ev2 := I(A2, F2, B2, G2, k)\Big|_{I(A2,F2)}$   \quad ev2  steht für Evaluation (Auswertung, Interpretation) eines Terms \\
$\overset{n}{subst } \; :=\;  subst , ... , subst$ \\
wobei n - mal subst vorkommt und n die Stellenzahl von f ist. \\ 
$subst := \overset{1}{subst } $ \\ 
${\overset{n}{subst}\Big|_{B1} } \; :=\;  subst\Big|_{B1} , ... , subst\Big|_{B1}$ \\
Falls es im Kontext klar ist, kann man auch statt ${\overset{n}{subst}\Big|_{B1}}$ einfach nur $\overset{n}{subst}$ schreiben.\\ \\
Behauptungen:\\
1) \\
$subst \colon I(A1,F1) \to I(A2,F2)$ \quad ist eine bijektive Funktion \\
(also $B1 = subst^{-1}(B2)) $\\
$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 I(A,F)$ gilt:\\
$subst(ev1(T)) = ev2(subst(T))$ \\ \\
Beweis:  \\
$\overset{n}{T}$ ist eine Abkürzung für  $T_1, ..., T_n$ \\
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) \\
a) \\
 Wenn $h_n := subst^{-1} \circ (k2(k12(f_n))) \circ ({\overset{n}{subst}\Big|_{B1} })$ und $n>0$, dann gilt: $h_n(B1^n)  \subset B1$ \\ 
Unterbeweis:\\ 
$({\overset{n}{subst}\Big|_{B1} }): B1^n \rightarrow B2^n $\\
$subst: B1 \rightarrow B2 $\\
$subst^{-1}: B2 \rightarrow B1 $\\
$(\overset{n}{subst}) \in Abb(B1^n , B2^n) $\\
b) \\
$f_n : I(A1,F1)^n \rightarrow I(A1,F1)$ \\
$k12: (I(A1,F1)^n \rightarrow I(A1,F1)) \quad \rightarrow \quad (I(A2,F2)^n \rightarrow I(A2,F2)) $ \\
$k2: (I(A2,F2)^n \rightarrow I(A2,F2)) \quad \rightarrow \quad B2^n \rightarrow B2 $, also: \\
c) \\
$(k2(k12(f_n))) \in  B2^n \rightarrow B2$ \quad und \\
$(k2(k12(f_n))) \circ ({\overset{n}{subst}\Big|_{B1} })  \in   B1^n \rightarrow B2 \quad und $  \\
$subst^{-1}  \circ (k2(k12(f_n))) \circ ({\overset{n}{subst}\Big|_{B1} })  \in  B1^n \rightarrow B1 $  \\ \\
3) \\
(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))$ \\ 
$subst(ev1(T))=$ \\ 
$subst(ev1(f(\overset{n}{T}))=$ \quad da nach Satz 1 ein f und $\overset{n}{T}$ existiert mit $a = f(\overset{n}{T})$ \\
$subst \big( \; (k11(f))  (\overset{n} {ev1(T})) \; \big)=$ \\ 
$subst \big( \; (subst^{-1} \circ ((k2(k12(f_n))) \circ (\overset{n}{subst}) )  (\overset{n} {ev1(T})) \; \big)=$ \\ 
$((k2(k12(f_n))) \circ \overset{n}{subst})  (\overset{n} {ev1(T})) \; \big)=$ \\ 
$(k2(k12(f_n))) (\overset{n}{subst (ev1(T)}) \big)=$ \\ 
andererseits gilt: \\
$ev2(subst(f_n(\overset{n}{T}))) = $ \\
$ev2( (k12(f_n))(\overset{n}{subst(T)})) = $ \\
$(k2(k12(f_n))) (\overset{n}{ev2(subst(T)}) \big)=$ \\ 
Da mit der Induktionsannahme für alle $i \le n$ 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 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(k12(f)) \circ (\overset{n}{subst})$  \\
wobei 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) $ ist ein Funktionsgenerator, wobei I(A1,F1) und I(A2,F2) eindeutig lesbar und Termmengen sind.\\
$(A1, F1, B1, G1, k11) )$ ist ein Funktionsgenerator. \\
$(A2, F2, B2, G2, k2) )$ ist ein Funktionsgenerator.\\
mit den dazugehörigen Eigenschaften:\\ \\
1) Definition von A1 und F1:\\
$OP_S = \emptyset$ \\
$OP_0 =$ Menge aller Dualzahlen (=Binärzahlen)\\ 
$OP_1 = \emptyset$ \\
$OP_2 = \{ +_2 , *_2 \}$ \\
$OP = OP_0 \cup OP_1 \cup OP_2$ \\
$F1_0 = OP_0$ \\
$F1_2 = \{f_{+_2} , f_{*_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 OP_0$  \\
$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_S = \emptyset$ \\
$OP_0 =$ Menge aller Dezimalzahlen  \\
$OP_1 = \emptyset$ \\
$OP_2 = \{ +, * \}$ \\ 	
$OP = OP_0 \cup OP_1 \cup OP_2$ \\
$F2_0 = OP_0$ \\
$F2_2 = \{f_{+_{10}} , f_{*_{10}}\}$ \\
$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 OP_0$  \\
$z$ \\ \\
$\{DT_1, DT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $DT_1, DT_2 \in A2$   \\ 
$(DT_1 +_{10} 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 *_{10} 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 \; mul_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 \; mul_{10} \;d_2) $  \\ \\
$k11(f_n) := subst^{-1} \circ (k2(k12(f_n))) \circ (\overset{n}{subst})$  \\
wobei n die Stellenzahl von $f_n$ 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) $ ist ein Funktionsgenerator, wobei I(A1,F1) und I(A2,F2) eindeutig lesbar und Termmengen sind.\\
$(A1, F1, B1, G1, k11) )$ ist ein Funktionsgenerator. \\
$(A2, F2, B2, G2, k2) )$ ist ein Funktionsgenerator.\\
mit den dazugehörigen Eigenschaften:

\subsection{Definition von A1 und F1}
$OP_S := \{ \odot_M \} $\\
$(\mathbb{K} , \fbox{+},  \boxed{\cdot})$ ist ein mathematischer Körper.\\
$\mathbb{KT}$ ist die zugehörige Termenge.\\
$Mat(\mathbb{K}) := \bigcup_{n,m\in\mathbb{N}} Mat(n,m,\mathbb{K})  $ \\
$OP_0 = Mat(\mathbb{K})  \cup \{\#\}$ \\
$OP_1 = \{i_M\}$ \quad Inverse\\
$OP_2 = \{ +_M , *_M\}$ \\
$OP = OP_0 \cup OP_1 \cup OP_2$ \\
Also gilt:\\
$A1 := (\{( \; , ) \} \cup OP \cup OP_S \cup \mathbb{KT} )^*$   (Menge von Zeichenfolgen) \\
$F1_0 = OP_0$\\
$F1_1 = \{f_{i_M} \}  \; \cup \; \{f_{kt_M} : A1 \rightarrow A1 \; \vert \;  f_{kt_M}(a) = (kt \odot_M a) \; \text{und} \; kt \in \mathbb{KT} , a \in A1 \}$ \\
$F1_2 = \{f_{+_M}, f_{*_M} \}$\\ \\
Damit ist die Regelmenge $R(A1,F1)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad    für jedes $M \in F1_0$  \\
$M$ \\ \\
$\{MT\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $MT \in A1$   \\ 
$i(MT) $ \\ \\
$\{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) $  \\ \\
$\{MT\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $MT \in A1$ und  jedes $kt \in \mathbb{KT}$   \\ 
$f_{kt_M}(MT) $ 

\subsection{Definition von A2 und F2}
$OP_S := \{ \odot_L \} $\\
$(\mathbb{K} , \fbox{+},  \boxed{\cdot})$ ist der gleiche mathematischer Körper wie oben.\\
$\mathbb{KT}$ ist die zugehörige Termenge.\\
$Lin(\mathbb{K}) := \bigcup_{n,m\in\mathbb{N}} Lin(\mathbb{K}^n,K^m)  $ \\
$OP_0 = Lin(\mathbb{K})  \cup \{\#\}$ \\ 
$OP_1 = \{i_L\}$ \quad Inverse\\
$OP_2 = \{ +_L, *_L, \odot_L \}$ \\ 	
$OP = OP_0 \cup OP_1 \cup OP_2$ \\
Also gilt:\\
$A2 := (\{( \; , ) \} \cup OP \cup OP_S \cup \mathbb{KT} )^*$   (Menge von Zeichenfolgen) \\
$F2_0 = OP_0$\\
$F2_1 = \{f_{i_L} \}  \; \cup \; \{f_{kt_L} : A2 \rightarrow A2 \; \vert \;  f_{kt_L}(a) = (kt \odot_L a) \; \text{und} \; kt \in \mathbb{KT} , a \in A2 \}$ \\
$F2_2 = \{f_{+_L}, f_{*_L} \}$\\ 
$k12(f_{iM}) :=f_{i_L }$  \\
$k12(f_{+M}) :=f_{+_L }$  \\
$k12(f_{*M}) :=f_{*_L }$  \\ 
$k12(f_{kt_M}) :=f_{kt_L }$  \\ \\
Damit ist die Regelmenge $R(A2,F2)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad    für jedes $l \in IP_0 $  \\
$l$ \\ \\
$\{LT\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $LT \in A2$   \\ 
$i_L(LT) $ \\ \\
$\{LT_1, LT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $LT_1, LT_2 \in A2$   \\ 
$(LT_1 +_L LT_2) $ \\ \\
$\{LT_1, LT_2\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $LT_1, LT_2 \in A2$   \\ 
$(LT_1 *_L LT_2) $  \\ \\
$\{LT\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad     für jedes $LT \in A2$ und  jedes $kt \in \mathbb{KT}$   \\ 
$f_{kt_L}(LT) $ 


\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(i_L) = inv_L$  \\
$k2(f_{+L}) = add_{L}$  \\
$k2(f_{*L}) = mul_{L}$  \\
$k2(f_{kt_L}) =  smul_{kt_L}$ \\
wobei:\\
$inv_{L}$ und $add_{L}$ und $ mul_{L}$ die bekannte Umkehrabbildung, Addition bzw. Multiplikation von linearen Abbildungen bedeutet:\\
$inv_L \colon B_2 \times B_2 \to B_2, \ inv_L(l)=\begin{cases}  \text{UA}, & l\neq \# \;  {und \; Umkehrabbildung \; von \; l \; existiert} \\ \#, & \text{sonst} \end{cases}.$ \\ 
\hspace*{1.1cm} wobei UA die bekannte Umkehrabbildung 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}   \\ \#, & \text{sonst} \\ \end{cases}.$ \\ 
\hspace*{1.1cm} 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}   \\ \#, &   \text{sonst} \end{cases}.$ \\ 
\hspace*{1.1cm} wobei BM die bekannte Multiplikation von linearen Abbildungen bedeutet. \\ \\
$smul_{kt_L} \colon B_2 \to B_2, \ smul_{kt_L}(l)=\begin{cases}  \text{BSL}, & l \neq \# \;  \text{und \;  l  ist eine lineare Abbildung}
 \\ \#, &   \text{sonst} \end{cases}.$ \\ 
\hspace*{1.1cm} wobei BSL die bekannte Skalarmultiplikation eines Elements eines Körpers  \\
\hspace*{1.1cm} (z.B. einer reellen Zahl) mit einer linearen Abbildungen bedeutet, wie z.B:  \\
\hspace*{1.1cm} $ 3 \odot f $  \\ \\
Damit ist die Regelmenge $R(B2,G2)$ wie folgt festgelegt: \\
$\emptyset$   \\
$\rule {2 cm } { 0.02 cm }$ \quad :   für jedes $l \in B2$  \\
$l$ \\ \\
$\{l\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $l \in B2$   \\ 
$inv_L(l) $ \\ \\  
$\{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 \; mul_{L} \;l_2) $  \\ \\
$\{ l  \}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $l\in B2$ und jedes $kt \in \mathbb{KT}$   \\ 
$ smul_{kt_L} (l)$  

\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_{i_M}) = inv_M$  \\
$k11(f_{+_M}) = add_M$  \\
$k11(f_{*_M}) = mul_M$  \\ 
$k11(f_{kt_M}) =  smul_{kt_M}$ \\ \\
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\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $M \in B1$   \\ 
$inv_M(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 \; mul_M \; M_2 $  \\ \\
$\{M\}$   \\ 
$\rule {3.5 cm } { 0.02 cm }$ \quad :    für jedes $M \in B1$ und  jedes $kt \in \mathbb{KT}$  \\ 
$smul_{kt_M}(M) $  \\ \\
mit: \\
$k11 \colon A1 \to B1, \ k11(f_n)=\begin{cases}  subst^{-1} \circ (k2(k12(f_n))) \circ (\overset{n}{subst}), & n>0
 \\ subst^{-1} \circ (k2(k12(f_n))) , & n=0 \end{cases}.$ \\ 
also konkret:\\
$add_M := k11(f_{+_M}) := subst^{-1} \circ k2(k12(f_{+_M}) \circ (\overset{n}{subst})$ = \\
$subst^{-1} \circ k2(f_{+_L}) \circ (\overset{n}{subst})$ = \\
$subst^{-1} \circ add_{L} \circ (\overset{n}{subst})$  \\
$mul_M := k11(f_{*_{M}}) := subst^{-1} \circ k2(k12(*_M)) \circ (\overset{n}{subst})$ = \\
$subst^{-1} \circ k2(f_{*_L}) \circ (\overset{n}{subst})$ = \\
$subst^{-1} \circ mul_{L} \circ (\overset{n}{subst})$  \\
$inv_M := k11(f_{i_{M}}) := subst^{-1} \circ k2(k12(i_M)) \circ subst = $  \\
$subst^{-1} \circ k2(f_{i_L}) \circ (\overset{n}{subst})$ = \\
$subst^{-1} \circ inv_{L} \circ subst$  \\
$smul_{kt_M} := k11(smul_{kt_M}) := subst^{-1} \circ k2(k12(f_{kt_M})) \circ subst = $  \\
$subst^{-1} \circ k2(f_{kt_L}) \circ subst$ = \\
$subst^{-1} \circ smul_{kt_L} \circ subst$  \\

\subsection{Skizze} 
Termmenge I(A1,F1) aus Matrizen \hspace{2cm}  $\xrightarrow {\text{k12}}$ \hspace{2cm}  Termmenge aus lin. Abb I(A2,F2) \\ 
$f_{i_M}, f_{+_M}, f_{*_M}, f_{kt_M}$   \hspace{7.6cm} $f_{i_L}, f_{+_L}, f_{*_L}, f_{kt_L}$  \\ 
\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$ \\ 
$inv_M, add_M, mul_M, smul_{kt_M}$   \hspace{7cm} $inv_L, add_L, mul_L, smul_{kt_L}$  \\ 
Atome $\Pi(I(A1,F1))$   \hspace{7cm} Atome $\Pi(TM2)$ von $\Pi(I(A2,F2))$  \\ \\
$k11(f) := subst^{-1} \circ k2(k12(f)) \circ (\overset{n}{subst})$  \\
wobei n die Stellenzahl von f ist. \\



\subsection{Anwendung von Satz 3}
Damit sind die Voraussetzungen von Satz 3 erfüllt.\\ \\
Beispiel1:\\
$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 
$ \\ \\ \\
Beispiel2:\\
$ev1(((3 \fbox{+} 7) \odot_M  (\left[ \begin{array}{rr}
1 & 2  \\
3 & 4  \\
\end{array}\right] 
 +_M  \left[ \begin{array}{rrr}
5 & 6  \\
7 & 8  \\
\end{array}\right] 
) ))=
$ \\
$smul_{(3 \fbox{+} 7)} (ev1(  (\left[ \begin{array}{rr}
1 & 2  \\
3 & 4  \\
\end{array}\right] 
 +_M  \left[ \begin{array}{rrr}
5 & 6  \\
7 & 8  \\
\end{array}\right] 
)))=$ \\
$smul_{(3 \fbox{+} 7)} (\left[ \begin{array}{rr}
6 & 8  \\
10 & 12  \\
\end{array}\right] 
)=$ \\
$ \\
\left[ \begin{array}{rr}
60 & 80  \\
100 & 120  \\
\end{array}\right] 
$








\end{document}