[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
More information about the FOM
mailing list