Tricki
a repository of mathematical know-how

Countable but impredicative

Countable but impredicative

I would be most interested to learn of examples of sets which are countable but impredicatively defined. For clarity, I should add that by 'countable', I mean that there exists a surjection from the natural numbers (or the natural numbers excluding zero) to the set.

I look forward to hearing from interested forum members.

This might sound silly, but I think the simplest countable but impredicatively defined set is the set \mathbb{N} of natural numbers itself. It is countable because the identity map is surjective. To see that it is impredicatively defined, call a set X inductive if it contains 0, and if the successor of x belongs to X whenever x belongs to X. The axiom of infinity asserts that an inductive set exists, and the set \mathbb{N} of natural numbers is then defined to be the set of exactly those elements that belong to every inductive set, and one of those inductive sets ends up being the set \mathbb{N} of natural numbers itself. Thus the definition is impredicative.