The Universe of Disco

Addenda to recent articles 200810

• 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 ℵ₀, 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, ω₀ = ω, and ω₁ = Ω. Then ω_ω is uncountable, but has cofinality ω, since it contains a countable cofinal subset {ω₀, ω₁, ω₂, ...}. 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, ... . 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 ε₀. 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. ]

• Regarding homophones of numeral words, several readers pointed out that in non-rhotic dialects, "four" already has four homophones, including "faw" and "faugh". To which I, as a smug rhotician, reply "feh".

  One reader wondered what should be done about homophones of "infinity", while another observed that a start has already been made on "googol". These are just the sort of issues my proposed Institute is needed to investigate.

  One clever reader pointed out that "half" has the homophone "have". Except that it's not really a homophone. Which is just right!

[Other articles in category /addenda] permanent link