[FOM] Counted sets (reply to Rempe)

joeshipman@aol.com joeshipman at aol.com
Mon Aug 24 15:26:13 EDT 2009

That's a good point -- to avoid something like this we would need a set 
of reals whose rank (in the sense of taking limit points transfinitely 
until you reached a perfect set) was a nonrecursive ordinal. Perhaps 
the work of Nabutovsky and Weinberger on computability theory and 
differential geometry could be used to find such a set in a natural way.

Bill Taylor's example of the recursive ordinals is a good one -- you 
can DEFINE a counting of that set without choice (in terms of the index 
of the first Turing machine that calculates a well-ordering of the 
given order type), but it is not a very satisfactory counting because 
it can't be related to the natural structure of that set (the order 
relation) in a useful way [given two integers  i and j, you can't 
effectively tell whether the ith recursive ordinal less than the jth  
recursive ordinal].

-- JS

-----Original Message-----
From: Lasse Rempe
>> I suppose if there were a set of real numbers which was
>> not obviously countable from its definition, but for which there was 
>> nontrivial proof that its points were all isolated, one would have a
>> countable set that was not "counted".
>It seems to me that would also not require choice, since we can write
>down an explicit injection of some countable basis of the topology of
>the real numbers (e.g. open intervals with rational endpoints) into N.
>This then leads to an injection of the given set into N.

More information about the FOM mailing list