[FOM] reply to Charles Volkstorf re function definitions

Randall Holmes holmes at diamond.boisestate.edu
Mon Sep 9 10:13:30 EDT 2002

Dear Charlie Volkstorf,

You wrote (to FOM):

Define the following three functions from the set of functions to the set of 
sets of functions.  That is, each takes in one or two functions and returns a 
set of functions:

s1(x) = { x(x) }
s2(x,y) = { x(x,y) }
s3(x) = { x(x), 0 }

For example, s1 takes in function x, applies x to x, and returns the set 
containing the value of x applied to x.

1. Consider the following specific set:

s1(s1) = { s1(s1) }

I comment:

Well, no, this isn't what happens.  The problem is that s1 is a proper
class, so s1(s1) is not defined (functions can only have values at
sets).  The same comments apply to all the subsequent computations in
your posting.

This kind of construction cannot be allowed in general:  a "definition"
of the same form

S(x) = x(x)^c (S being again a supposed function from the set of
functions to the set of sets of functions) would yield as a

S(S) = S(S)^c

and a set cannot be its own complement.

The particular definitions given above may define sets in some consistent
set theory (perhaps some variant of positive set theory), but not in
any variant of ZFC.

I suppose you know that you are applying the fixed point combinator
construction from lambda-calculus or combinatory logic?  In these
theories, functions with universal domain can themselves occur as
arguments and values of functions, but this is not possible in
standard set theory (it is possible in New Foundations, but the fixed
point combinator construction will not work there for other reasons).

                                 --Randall Holmes
                                 Dept of Math
                                 Boise State University

More information about the FOM mailing list