[FOM] counted sets

[Bill Taylor]

Apologies for this rather basic follow-up, but I had a private reply asking
for elucidation, so maybe there are others who would appreciate one as well.


->> [for a non-counted but countable union of counted sets]
....
->> The obvious try is w_1^CK, the set of recursive ordinals.

->I like this so very much that I want to use it in future.  But I'm embarrassed
->to admit that I don't know to what "CK" refers.  "K"onig'sc-something"?

The CK is for Church & Kleene.

w_1^CK is the first non-recursive ordinal, equivalently, the set of all
recursive ordinals.  A recursive ordinal is one whose members can be given
notations so that one can effectively tell from the notation whether it
is a limit or successor, and (respectively) what its predecessor was or
what is a sequence of lesser ones whose limit it is.  This description also
means (trivially) that one can tell what the successor of any ordinal is.
Equivalently, (though harder to prove), is that a recursive ordinal is
the order type of an effectively given (i.e, machine-testable) ordering on
(say) N, whose order type happens to be a well-ordering. This latter definition
is somew3hat more non-constructive, but is easier to use in some contexts.

As I noted, the set of all recursive ordinals is necessarily non-recursive!
There can be no effective notation for it, though there can be for any lesser
ordinal.  The thing is, there is no "uniform" way of notating the ordinals
less than it - every so often one must adopt a whole new procedure,
largely unrelated to but engulfing the prior ones.

Hartley Davidson's book has a nice little section on it.

-- Bill Taylor