At 13:39 +0100 1999/06/03, Jerzy Karczmarczuk wrote:
>... I don't understand
>the Hans remark about making from +, * etc. the primitive basis
>for the set theory. What's so primitive about them?
A set of lambda expressions is called primitive if all other lambda
expressions can be generated from it by finite combinations. Church also
requires that the members of the set are not themselves finite combinations
(of the form AB), and that they contain no free variables. (So this is the
same use of the word when constructing data bases and the like: One has
some kind of algebra, and a primitive set is what generates it.)
So if one has the set S = { I, +, *, ^ }, then the lambda is not needed for
the purpose of constructing formulas with only non-constant variables. If
you want to allow formulas with constant variables, then Peter Hancock
<[EMAIL PROTECTED]> says that { O, +, *, ^ } suffices.
In real life though, it is very difficult to translate an arbitrarily given
lambda expression into a combination of the given primitive set. So for
practical purposes, there is no real gain in attempting to use a primitive
set as a replacement for lambda expressions.
Hans Aberg
* Email: Hans Aberg <mailto:[EMAIL PROTECTED]>
* Home Page: <http://www.matematik.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
