[FOM] RE: FOM Digest, Consistency of Formal Theories

[Matt Insall]

Thanks to all who answered my query about a tower of
theories extending number theory by one Rosser formula
(or its negation) at a time.  In the discussion the
notion of a recursive ordinal was mentioned, and the
Church-Kleene ordinal was described as the least non-
recursive ordinal.  It was noted that the Church-Kleene
ordinal is countable, and this makes sense.  Yet, is there
a corresponding notion of ``recursive ordinal'' that allows
the ordinals so described to be uncountable?  My friend
Hitoshi Kitada wonders at this, and it makes sense to
me that something like the definition of recursive for
countable ordinals should be obtainable so that it allows
the ordinal in question to be uncountable, but it seems
then that the Church-Kleene ordinal (if it really is an
ordinal, and not merely an ``ordinal notation'') would
then not be the least nonrecursive ordinal under the
modified definition of recursive.  In fact, would the
modification necessarily include all ordinals, so that
there is no (least) nonrecursive ordinal in this revised
context?  I have another question as well:  Is the proper
modification of ``recursive'' ``constructible''?  If so,
then is it not the case that every ordinal is constructible?
(That is what is shown in _Set Theory and the Continuum Hypothesis_
by R. Smullyan and M. Fitting.)

Note that at least one respondent referred to the ordinals
in question as the ``constructive'' ordinals.  Does this
have to do with a constructibility criterion?

Here is a pair of related notions I came up with over a year ago,
in trying to prove something that turned out to be provably unprovable:

Definition 1:  Let a be an ordinal.  Then a is _constructibly countable_
provided that one of the following holds:
(i)    a=0
(ii)   a=b+1 for some constructibly countable ordinal b
(iii)  there is a constructible set X of constructibly countable
       ordinals, and there is a constructible monotone function
       f: omega ---> X such that a=sup(f[omega]).

(Note:  Here, omega is the least infinite ordinal.)

Definition 2:  Let k be a cardinal, and let a>k be an ordinal.  Then
a is constructibly of cardinality k provided that one of the following
holds:
(i)    a=k
(ii)   a=b+1 for some ordinal b that is constructibly of cardinality k
(iii)  there is a constructible set X of ordinals, each member of which is
       constructibly of cardinality k, and there is a constructible monotone
       function f: k ---> X such that a=sup(f[k]).


For a while, I tried to prove that every countable ordinal is constructibly
countable.  (This would have made it possible to prove that in ZF+CH, the
continuum is well-orderable.  Please don't ask me to reproduce the proof.
I have not messed with this irritating problem for a while and my notes
are buried somewhere.  In any case, I was working on this with a colleague,
David Grow, and in the end, Andreas Blass helped us find out that our
results
were previously known to Tarski.)  This lead to consideration of the least
ordinal
that is not constructibly countable.  Let me denote this ordinal by p.  Then
my
goal at the time was to show that p is uncountable.  After some thought, it
became
clear to me that p is also what in Jech's _Set Theory_ is denoted by

omega_1^L,

and this is (roughly) the least uncountable ordinal **according to L**.
Jech
gives three proofs that it is consistent with ZFC to assume that omega_1^L
is
countable.  My last question is the following, since my path to fom has not
included enough about recursiveness, effectiveness, computability, etc, to
immediately answer this:

Is omega_1^L the Church-Kleene ordinal?

My hunch is that the answer is no, and that this is well-known, to someone
other than me.  Also, a yes answer would appear to contradict the
information
that was tacit in Richard Zach's response to my original query, for he seems
to indicate that the Church-Kleene ordinal is countable, as if this is
well-known.

Thanks in advance to anyone who takes the time to respond, in spite of the
high likelihood that answers to my queries are all to be found in literature
that is fifty years old or so.

Matt Insall
PS:  I now think the right axioms for set theory very strongly
deny the constructibility hypothesis.  In fact, I have already
proposed strong anti-GCH axioms and that set theory should have
urelements.  Currently, the part of the case that I can make is
not especially strong for my proposed axioms, but let me here
state that I also propose very strong denials of consequences of
the constructibility hypothesis that relate to definitions 1 and
2 above.  For example, the following should be an axiom or theorem
of the extension of ZFC that I propose:  There is a countable ordinal
that is not constructibly countable.  (It is an easy consequence of
ZF+V=L that every countable ordinal is constructibly countable.)  More
generally, I would have the following as an axiom or as a theorem:
For each cardinal k, there is an ordinal a>k that is of cardinality
k but is not constructibly of cardinality k.  However, I would not
propose the removal of the axiom of choice from my foundations.
In this last I seem to be in agreement with mainstream mathematics.
(In concerning myself with these matters, I may be swimming against
an incoming tsunami!) - MI