I discussed representing
ordinal numbers in the computer and expressed doubt that the
following representation truly captured the awesome complexity of the
ordinals:
data Nat = Z | S Nat
data Ordinal = Zero
| Succ Ordinal
| Lim (Nat → Ordinal)
In particular, I asked
"What about Ω, the first uncountable ordinal?" Several readers
pointed out that the answer to this is quite obvious: Suppose
S is some countable sequence of (countable) ordinals. Then the
limit of the sequence is a countable union of countable sets, and so
is countable, and so is not Ω. Whoops! At least my intuition
was in the right direction.
Several people helpfully pointed out that the notion I was looking for
here is the "cofinality" of the ordinal, which I had not heard of
before. Cofinality is fairly simple. Consider some ordered set S. Say
that an element b is an "upper bound" for an element a
if a ≤ b. A subset of S is
cofinal if it contains an upper bound for every element of
S. The cofinality of S is the minimum
cardinality of its cofinal subsets, or, what is pretty much the
same thing, the minimum order type of its cofinal subsets.
So, for example, the cofinality of ω is ℵ_{0}, or, in the language
of order types, ω. But the cofinality of ω + 1 is only 1
(because the subset {ω} is cofinal), as is the cofinality of
any successor ordinal. My question, phrased in terms of cofinality,
is simply whether any ordinal has uncountable cofinality. As we saw,
Ω certainly does.
But some uncountable ordinals have countable cofinality. For example,
let ω_{n} be the smallest ordinal with
cardinality ℵ_{n} for each n. In
particular, ω_{0} = ω, and ω_{1} =
Ω. Then ω_{ω} is uncountable, but has
cofinality ω, since it contains a countable cofinal subset
{ω_{0}, ω_{1}, ω_{2}, ...}.
This is the kind of bullshit that set theorists use to occupy their
time.
A couple of readers brought up George Boolos, who is disturbed by
extremely large sets in something of the same way I am. Robin Houston
asked me to consider the ordinal number which is the least fixed point
of the ℵ operation, that is, the smallest ordinal number
κ such that |κ| = ℵ_{κ}. Another
way to define this is as the limit of the sequence 0, ℵ_{0}
ℵ_{ℵ0}, ... . M. Houston describes κ as
"large enough to be utterly mind-boggling, but not so huge as to defy
comprehension altogether". I agree with the "utterly mind-boggling"
part, anyway. And yet it has countable cofinality, as witnessed by
the limiting sequence I just gave.
M. Houston says that Boolos uses κ as an example of a set
that is so big that he cannot agree that it really exists. Set theory
says that it does exist, but somewhere at or before that point, Boolos
and set theory part ways. M. Houston says that a relevant essay,
"Must we believe in set theory?" appears in Logic, Logic, and
Logic. I'll have to check it out.
My own discomfort with uncountable sets is probably less nuanced, and
certainly less well thought through. This is why I presented it as a
fantasy, rather than as a claim or an argument. Just the sort of
thing for a future blog post, although I suspect that I don't have
anything to say about it that hasn't been said before, more than once.
Finally, a pseudonymous Reddit user brought up a paper of
Coquand, Hancock, and Setzer that discusses just which ordinals
are representable by the type defined above. The answer turns
out to be all the ordinals less than ω^{ω}. But
in Martin-Löf's type theory (about which more this month, I hope)
you can actually represent up to ε_{0}. The paper is
Ordinals
in Type Theory and is linked from here.
Thanks to Charles Stewart, Robin Houston, Luke Palmer, Simon Tatham,
Tim McKenzie, János Krámar, Vedran Čačić,
and Reddit user "apfelmus" for discussing this with me.
[ Meta-addendum 20081130: My summary of Coquand, Hancock, and Setzer's
results was utterly wrong. Thanks to Charles Stewart and Peter
Hancock (one of the authors) for pointing this out to me. ]