Kombinator-Basen

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

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

Satz: {S, K} ist Basis. -- Beweis? I = …

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

Literatur:

• Henk Barendregt: The Lambda Calculus, its Syntax and Semantics, 1984. http://www.cs.ru.nl/~henk/
• Raymond Smullyan: How To Mock a Mockingbird, 1985. http://www.raymondsmullyan.com/