[FOM] Countable sets with impredicative definitions

[Dana Scott]

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