# [FOM] Countable sets with impredicative definitions

Dana Scott dana.scott at cs.cmu.edu
Sat Nov 20 14:07:33 EST 2010

```Several FOMers have commented on this question of Margaret MacDougall:

> 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.

I wonder if this might be a simpler example than some others suggested.

The set of formulae of second-order arithmetic is countable.  Divide
them into equivalence classes, where two formulae are equivalent iff
the universal generalization of their biconditional is TRUE in second-
order arithmetic.  The set of equivalence classes is countable in the
sense required (because any quotient of a countable set is countable
in this sense).  I cannot see that this equivalence relation has a
predicative definition.  (A worse example uses third-order arithmetic.)
Am I wrong?

Since the surjection is not apparently required to be predicative, what
about the two-element set {T, F} consisting of the true sentences and
the false sentences.  Anything wrong with this?

Prof. Dana S. Scott
1149 Shattuck Avenue
Berkeley, CA 94707-2609
------
Tel: (510) 527-5287

```