[FOM] Countable sets with impredicative definitions

Nik Weaver nweaver at math.wustl.edu
Thu Nov 18 12:33:07 EST 2010

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

More information about the FOM mailing list