[FOM] Countable sets with imprediicative definitions
jeffrey.sarnat at gmail.com
Thu Nov 18 13:10:37 EST 2010
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).
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
More information about the FOM