[FOM] FOM] Naturalness

[weiermann@math.uu.nl]

In a previous posting from 27th January Harvey Friedman
suggested lengths as a mathematical
criterion for naturalness. Ozkural
commented on that and I feel encouraged
to to contribute to the discussion too.

I find this topic very intriguing
and Friedman's suggestion
leads to interesting and profound questions.
I also consider shortness of concepts or
definitions as a reasonable
measure. My favourite examples stem from Feferman's natural
well-ordering problem for which no satisfactory solution
is known. But the known examples of natural well-orderings
(as long as ordinals below the ordinal for KPM are concerned)
all come with short definitions. So it might be interesting
to chose a goedelnumbering of the prim rec functions
from some textbook and check what is the least code
of a primitive recursive well ordering for epsilon_0.
(This question is in some sense related to Kolmogorov complexity.)

If one codes a consistency statement for PA and builts
it into the definition of an ordering the definition
will quickly become quite long when written out in full.

Taking shortness into account several independence results
for PA like Paris Harrington, Kanamori McAloon, Hydra games,
Goodstein sequences, Friedman style miniaturizations of
well-quasiorderedness principles and well-foundedness principles,
Friedman style Ramsey theorems, Pudlak's principle, and other related
assertions all satisfy this naturalness requirement.
Again the Goedel statement stands apart since it becomes
quite long when written out in full.

Another feature of naturalness is having "natural properties".
(A related phenomen is also known in random graph theory.
Natural properties of graphs have a natural threshold.)
For example a natural well ordering should always come with
a natural independence phenomenon. What really is surprising
here is that Friedman's extended Kruskal theorem (which emerges
from ordinal notations in some natural way) have striking
applications outside logic, e.g.
in the proof of the Graph Minor theorem.

I have the working hypothesis that
 natural well-quasi orders emerge from natural
well orders by restricting the linear ordering
on the well order to a partial ordering which
is motivated by graph theoretic properties
(like subterm property or monotonicity).
Quite often the new partial order will be a wqo
having maximal order type equal to the order
type of the ordering we started with. If this
holds a bunch of independence results can
be concluded and these will all be natural
ones.

Best regards,

Andreas Weiermann (Utrecht University)





--