Well-partial-orderings and their Strengths

Jeroen Van der Meeren

(Ghent University)

Well-partial-orderings are widely usedin for example logic, computer science and mathematics. They are the essential ingredients of famous theorems like Higman’s lemma, Kruskal’s theorem and the graph minor relation. In computer science, they can be used for proving the termination of certain algorithms. Additionally, they have connections with the computation of the running times of these algorithms. In logic, well-partial-orderings are quite often related with the proof-theoretical ordinal of an axiomatic system. Moreover, they can be used in for example proof theory and reverse mathematics.

A well-partial-ordering (hereafter wpo) is a well-founded partial ordering (X,≤X)with no infinite antichains. Hence, wpo’s are the natural generalizations of well-orderings. The maximal order type of a well-partial-ordering (X,≤X) is an important characteristic of the wpo which captures a lot of information about it. It is defined as the maximum of the order types of all well-orderings which are extensions of the ordering ≤X on X. There is a relation between the proof-theoretical strength of the sentence ‘X is a wpo’ and the maximal order type of X.

The maximal order type of the famous set of trees with Friedman’s gap-embeddability relation is unknown. In this talk, I will tackle this problem by discussing tree-like structures T(W), depending on a parameter W (introduced by Weiermann). I will talk about a general conjecture to compute its maximal order type and some new recent developments concerning this topic. Furthermore, I will discuss results on the proof-theoretical strength of the statement ‘T(W) is a wpo’.
Tuesday 12th November 2013, 15:00
Robert Recorde Room
Department of Computer Science