\begin{slide}{Presburger-Arithmetik (PA)}

Wir definieren eine Folge $F_0, F_1,\ldots$
von Formeln durch

$F_0(x,z)=(x+1=z),
F_{k+1}(x,z) = \exists y: F_k(x,y)\wedge F_k(y,z)$.

\begin{itemize}
\item Für welche $z$ gilt $F_3(0,z)$ ?
\item Beschreiben Sie die Bedeutung von $F_k(x,z)$
durch eine nicht rekursive Formel,
bei der Sie zusätzlich die Funktionssymbole
für Multiplikation und Potenzierung
verwenden dürfen.
\item Reduzieren Sie die Formelgröße von $F_k$
(innerhalb PA), indem Sie eine äquivalente
Definition von $F_{k+1}$ angeben,
in  der $F_k$ nur einmal vorkommt.

\end{itemize}

\end{slide}
