[FOM] Are Friedman's indepence results natural?

[Andreas Weiermann]

Dear all,

some days ago Harvey commented a bit on the naturality of
his statements and he referred a bit to my work. So I feel
encouraged to comment a bit on this issue from my point of view.

>b. I found that Weiermann (and others) studied, very carefully for its own
>sake, just what happens when you look at finite sequences of trees and other
>objects with various bounds on rates of growth. They found various exciting
>threshold phenomena, and this is now a little bit of a cottage industry. If
>Weiermann and company would have taken Feferman's negative comments
>seriously, I don't see how they would have developed this mathematically
>beautiful and intricate threshold theory for growth rates. Weiermann has
>written a number of interesting papers and given a number of plenary talks
>on this. 

First of all, yes, I agree with Harvey.
His FKT is natural in my opinion
(and I know a lot of more people who agree on this too).

In particular I consider results which lead
to a rich and intriguing mathematics as
natural without questioning them further.

Now what is the intriguing math behind ordinals
or trees?

Let me give two examples for small ordinals:

To $\alpha=\omega^{a_1}+\cdots+\omega^{a_n}$ in Cantor normal form
associate the Goedel number $gn(\alpha)=p_1^{a_1}\cdot\ldots\cdot p_n^{a_n}$
where $0$ gets Goedel number $gn(0)=1$.
This is a natural coding, as I hope.
Let $c(n)=\#\{\alpha<\omega^\omega:gn(\alpha)\leq n\}$
and $c_d(n)=\#\{\alpha<\omega^d:gn(\alpha)\leq n\}$.

Then $\log(c(n)\sim \pi\cdot\frac{2}{3}\sqrt{\frac{\log(n)}{\log\log(n))}}$
(folklore!)
and $\log(c_d(n)\sim \frac{1}{(d!)^2}({\frac{\log(n)}{\log\log(n))}})^d$
(exercise!).

I showed these things to Jaap Korevaar in Amsterdam who
is one of the grandmasters in Tauberian theory and
he got excited. Also Anatoly Vershik from St. Petersburg
liked these and people in analytic combinatorics liked these too.

Such analytic results arise naturally in the context of statements like 
FKT. Now let us have a look at some places in the literature:
First, there is a recent book by Burris on numbertheoretic
densities and logical limit laws. If one scans through
it then it appears that ordinals form an additive number
system and the theory applies. That's appealing and
leads (with results of Woods)
to logical limit laws for ordinals (joint with Woods).
Second, there are papers by Parameswaran and Kohlbecker
in TAMS on Tauberian results. Well these are tailor made
for ordinal counting.
Third, after scanning through Ramanujans collected papers 
one finds the folklore result mentioned above (with 
a proof using Tauberian theorems of exponential type).
Finally scanning through the book on regular variation
by Bingham et al. one solves the exercise above easily
(but without it the exercise is not that obvious).
Forth, take a look at Flajolet's and Sedgewick's online
book on analytic combinatorics. All the stuff there
on random trees applies to ordinal notations. Natural parameters
of random ordinals will usually
obey a Gaussian law. Moreover countour
processes for ordinal terms are related to Brownian
excursions. I believe that these phenomena promise further interesting
applications.

Now it has been critizised that FKT till yet 
did not have applications within math.
I conjecture that they will come. 

Anyway, it might be good to give a concrete application in logic:
In September 2005 I visited Alan Woods in Perth and I met there
Martin Bunder there at the AMS meeting. He asked me
on the following problem (Miniaturized Dickson's Lemma).
Let $(a^i)_{i=1}^M$ be a sequence of $k$-tuples of non negative
integers such that 
1) $a^{i+1}\leq a^i+1$ for all $i<M $ and $l\leq k$,
2) For all $i<j\leq M$ there is $l\leq k$ with $a^i_l>a^j_l$.
How large can $M$ become as a function of $a^1$?

This is a problem related to relevance logic and appears
there naturally. 
According to Martin Bunder, George Szekeres had worked for some 
time on it.

Armed with knowledge on Friedman style miniaturizations I
solved it and proved
Ackermannian lower bounds on M by direct calculations.
Of course, a similar result holds for Higman's Lemma too.


At the moment some of my coworkers and
I also consider Ramsey theory in general and we
expect rich and intriguing output. In particular
Friedman's Ramseyan statements 
and the canonical Ramsey theorem will come with a nice
phase transition. 



To sum up, for me it's in particular the intriguing 
underlying mathematics
which makes Friedman's miniaturizations and independence
results (for PA) natural
and I still believe that the mathematical
potential of these are underestimated to a large extent.






Best whishes,
Andreas Weiermann