[FOM] Countable sets with imprediicative definitions

Harvey Friedman friedman at math.ohio-state.edu
Thu Nov 18 11:20:28 EST 2010


On Nov 18, 2010, at 5:58 AM, 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.

Is this the kind of thing you are looking for?

The set of all finitely presented structures with domain N, in a  
finite relational type, all of whose substructures are finitely  
generated.

Harvey Friedman



More information about the FOM mailing list