[FOM] Countable sets with imprediicative definitions

[Jeffrey Sarnat]

Although I may be mistaken, someone here will probably reply saying that 
the ordinal Gamma_0 (or, equivalently, the set of ordinals smaller than 
Gamma_0) is the canonical example of such a set. I've never understood 
this, so I won't be that person. Instead, I'd like to ask you to clarify a 
subtle point in your question: do you consider the identity of a set to be 
defined only by its elements, or by the properties it satisfies? This 
makes a difference.

For example, the set of well-typed System F terms and the set of 
normalizing System F terms can both be given predicative definitions, but 
to show that the former is a subset of the latter it is absolutely 
essential to make use of impredicative reasoning, most commonly in the 
form of an impredicatively-defined logical relation (e.g. using 
reducibility candidates or saturated sets).

 	Jeff

On Thu, 18 Nov 2010, Margaret MacDougall wrote:

> Can anyone provide examples of countable sets with impredicative
> definitions and apparently no alternative predicative definitions? Just
> to clarify, my intended notion of countable in relation to a set refers
> to the existence of a surjection from the natural numbers (or from the
> natural numbers excluding zero) to that set.
>
>
> -- 
> The University of Edinburgh is a charitable body, registered in
> Scotland, with registration number SC005336.
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>