Tricki

## 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 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 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 of natural numbers itself. Thus the definition is impredicative.