A Combinatorial Approach to Complexity Theory via Ordinal Hierarchies

Summary

Long regressive sequences in well-quasi-ordered sets contain ascending subsequences of length n. The complexity of the corresponding function H(n) is studied in the Grzegorczyk–Wainer hierarchy. An extension to regressive canonical colourings is indicated.

Introduction

For many mathematicians the most noble activity lies in proving theorems. It must have come as a blow for them when Gödel [7] showed that there are unprovable theorems. At the beginning they still could find some consolation in hoping that such culprits might only occur in Peano arithmetics through esoteric diagonalization arguments. Nowadays there is a wealth of the most natural valid theorems that can be stated in the language of finite combinatorics but are not provable within that system.

Mathematicians understand to a certain extent how to find unprovable theorems and how to prove their unprovability within a formal system. In that sense we are relying on the classical work by Gentzen [5], Kreisel [15] and Wainer [31]. Moreover, we shall apply their beautiful ideas to something that seems to be well understood, viz to well-quasi-orderings. This is an old concept found in Gordan [6], and Kruskal [16] correctly pointed out that it was ‘a frequently discovered concept’. That is why we are not reinventing it and are well aware that any sequence (s_i) of specialists starting with the author must contain an arbitrary long subsequence of experts knowing more than s₀, a fact, which gives a nice theme for this paper.