[FOM] A computational approach to the countable ordinals

Paul Budnik paul at mtnmath.com
Mon Aug 11 13:20:35 EDT 2008

hendrik at topoi.pooq.com wrote:
> I played with ordinal notations in the 70's, developing 
> algorithms for addition, multiplication, and I think I may have tried 
> exponentiation, too.  The notation(s) resembled the Veblen hierarchy, 
> but were different in details.  I was being minimalist at the time, and 
> thought building addition, multiplication, and exponentiation into the 
> notation was excessive.  Maybe it's time to dig up that stuff and code 
> it in Latex?
I am not so sure about coding it in LaTeX. I use C++ but the code does 
have the ability to generate LaTeX formatted notations. I first worked 
on a closely related problem in the early 70's. Seeing the axioms of ZF 
as one page computer program for enumerating theorems make me think I 
could get an explicit understanding of the combinatorial structures 
implicitly defined by those axioms.
> I definitely didn't go past the constructive.

Just as one can think of the recursive ordinals as the well orderings 
definable by recursive processes that are well founded for any infinite 
sequence of integers, one can define admissible ordinals at a certain 
level as recursive processes well founded for any infinite sequence of 
ordinal notations first for recursive ordinals and then for higher 
levels previously defined. Of course any particular computable system of 
notations will never include all recursive ordinals. A computational 
approach in effect replaces the impredictivity of set theory with 
explicit incompleteness.

Paul Budnik

More information about the FOM mailing list