\begin{slide}{Beispiele f. Presburger-Formeln}

Beispiele:
  \begin{itemize} \itemsep 0pt
  \item es gibt eine gerade Zahl:
    $\exists x:\exists y : x = y+y$
  \item jede Zahl ist gerade oder ungerade: \dots
  \end{itemize}
definierbare Funktionen und Relationen:
\begin{itemize} \itemsep 0pt
\item Minimum, Maximum
\item Differenz? Produkt?
\item kleiner-als ($<$) nur mit Gleichheit ($=$)?
\item 0, 1, 2, 4, 8, \dots $x=2^k$ durch eine
  Formel der Größe $O(k)$
\end{itemize}
kann man noch größere Zahlen durch kleine
Formeln definieren?


\end{slide}
