18
$\begingroup$

I am working on a calculator for ordinal arithmetic.

Ordinal arithmetic is extremely tricky. So much so that there have been academic papers on the very subject that got some results wrong. Not to point fingers or anything, but for example, in this paper, table 24 lists $4^{\omega^7+3}$ as $\omega^7\cdot64$, where it should be $\omega^{\omega^6}\cdot64$.

Long ago I tried using the software associated with that paper as a reference for a similar project, only to discover it is not actually accurate itself.

This being the case, I am interested in a comprehensive and known good reference table of ordinal arithmetic expressions and their evaluation in Cantor Normal Form, to serve as a unit test for my calculator.

Is there some place where I can find such a table?

Update: Well, I didn't find the reference table I was looking for. But I did compare my results to this calculator, with which I couldn't find any problem. So I'll assume they're correct until suggested otherwise.

So I've uploaded the first version of My website. If anyone is so inclined, you can try it out and see if you find any error. It currently supports only ordinals smaller than $\epsilon_0$, it might be upgraded with new features in the future.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
16
$\begingroup$

I'm not sure what you mean or what you expect from a “reference table”, but your question prompted me to dig up this Haskell code I had written a dozen years ago: it's an implementation of the ordinals up to the countable collapse of $\Omega_\omega$ (following essentially the definitions and notations of W. Buchholz, “A New System of Proof-Theoretic Ordinal Functions”, Ann. Pure. Appl. Logic 32 (1986) 195–207: the system goes up to the ordinal $\psi_0(\Omega_\omega)$ in the notations of that paper). Usual addition, multiplication and exponentiation are implemented, as well as the Cantor Normal Form, standard sequences and a few other things (also the fast and slow growing hierarchy, but they are too slow to be usable for anything). There is no documentation, but the comments explain what the main user-serviceable parts are supposed to do.

The fact that $4^{\omega^7+3} = \omega^{\omega^6}\cdot 64$ can be checked as follows (using a Unix machine with access to the GHC Haskell interpreter as ghci):

vega david ~/haskell $ ghci Ordinal.hs GHCi, version 9.0.2: https://www.haskell.org/ghc/ :? for help [1 of 1] Compiling Ordinal ( Ordinal.hs, interpreted ) Ok, one module loaded. ghci> usualPower (nat 4) (usualPlus (finitePower omega 7) (nat 3)) == usualTimes (usualPower omega (finitePower omega 6)) (nat 64) True ghci>

This code hasn't undergone extensive testing (and since I mostly forgot how it all works I can't say much about it), let alone peer-review, but if you want to test whether another implementation works, it can probably be of some use.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Here's a pastebin with an example of what such a "reference table" might look like - pastebin.com/bg6AnH3x . My problems with it are 1. I'm not sure it's all 100% accurate, and 2. It is not extensive enough, I'd like to test with more difficult cases. $\endgroup$ Commented May 8 at 22:22
  • $\begingroup$ @MeniRosenfeld I used my Haskell code to confirm that the 20 lines in your file are indeed equalities, so this is accurate (or if it's not, then we're both independently wrong). Since you seem interested in ordinals $<\varepsilon_0$ only, you can easily generate lots of test cases by creating two Cantor normal forms of desired complexity with random coefficients and computing their main arithmetic operations. $\endgroup$ Commented May 9 at 22:37
  • 1
    $\begingroup$ Random (not very interesting) example: if $z_1=ω^{ω^ω+1}·2+3$ and $z_2=ω^{ω^2+ω·2}·3+2$ then $z_1^{z_2}=ω^{ω^{ω^2+ω·2}·3+ω^ω·2+1}·2+ω^{ω^{ω^2+ω·2}·3+ω^ω+1}·6+ω^{ω^{ω^2+ω·2}·3}·3$. $\endgroup$ Commented May 9 at 23:02
  • $\begingroup$ It's not so much that I'm only interested in ordinals below $\varepsilon_0$, rather that it adds complexity (not only in computation, but also in parsing and visualization), and I haven't gotten to it yet. I'm letting Gemini 2.5 do most of the coding, and it seemed apprehensive when I talked to it about implementing epsilon numbers. But we'll see if using your code as a reference will help simplify things. $\endgroup$ Commented May 10 at 23:08
  • $\begingroup$ This example seems to work. I added functionality to input the calculation as a parameter in the URL for easy sharing, but it seems Stackexchange cuts off the link. But putting (w^(w^w+1)*2+3)^(w^(w^2+w*2)*3+2) in the website should do the trick. $\endgroup$ Commented May 10 at 23:11

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.