\begin{slide}{Kombinator-Basen}

Def: Eine Menge $M$ von Kombinatoren heißt \emph{Basis},
falls es zu jedem Lambda-Ausdruck
einen äquivalenten Ausdruck nur aus Applikationen
und Kombinatoren aus $M$ gibt.

\bigskip

Satz: $\{S,K,I\}$ ist Basis.

Satz: $\{S,K\}$ ist Basis. --- Beweis? $I = \ldots$

Satz: es gibt eine Basis mit nur einem Element.
(Schwer.)

\bigskip

Literatur: 
\begin{itemize}
\item 
Henk Barendregt: The Lambda Calculus,
its Syntax and Semantics, 1984.
\url{http://www.cs.ru.nl/~henk/}
\item
Raymond Smullyan: How To Mock a Mockingbird, 1985.
\url{http://www.raymondsmullyan.com/}
\end{itemize}


\end{slide}
