[FOM] impredicative definitions/paper announcement

Vaughan Pratt pratt at cs.stanford.edu
Fri Nov 26 15:03:10 EST 2010

On 11/25/2010 7:19 AM, John Baldwin wrote:
> http://math.stanford.edu/~feferman/papers/predicativity.pdf

Among these and other notions of predicativity, is there one (or more) 
such that the set of quotients of N by an equivalence relation that is 
r.e. but not recursive is impredicative?

(This is relevant to the discussion by virtue of being a countable set.)

Intuitively I would tend to think of this as a predicative set, but I'm 
having difficulty seeing why a proof of (or argument for) its 
predicativity could not be adapted to at least some of the other 
examples suggested, e.g. Dana's.  What is the essential feature(s) of 
those examples that makes them impredicative and this one not?

Vaughan Pratt

More information about the FOM mailing list