[FOM] Countable sets with impredicative definitions

[Nik Weaver]

Margaret MacDougall wrote:

> Can anyone provide examples of countable sets with impredicative
> definitions and apparently no alternative predicative definitions?

I guess the standard example would be Kleene's O.  It is a subset of
the natural numbers, and hence is countable.  But to diagnose whether
a given number belongs to O you may need to determine whether a certain
countable poset is well-founded, which requires quantifying over all
subsets of the natural numbers, including O.

Nik Weaver
Math Dept.
Washington University
St. Louis, MO 63130 USA
nweaver at math.wustl.edu