Tree-like structures with the Friedman-style gap-embeddability relation

Jeroen Van der Meeren

Ghent University, Belgio

In 1985, Harvey Friedman introduced a new notion of embeddability between trees, namely the gap-embeddability relation. It give rise to a statement which is very strong, namely a statement not provable in $\Pi^1_1$-comprehension, the strongest theory of the big-five in reverse mathematics. Therefore, it seems natural to study structures with a gap-embeddability relation. Friedman’s statement was one of the first examples of 'natural' combinatorial statements with this unprovability property in $\Pi^1_1$-comprehension. The statement is 'for every natural number n, the set of the finite rooted trees with labels in {0, ..., n−1} is a well-partial-ordering under this gap-embeddability relation'. A partial order (X,≤) is a well-partial-ordering if it is well-founded and does not admit an infinite antichain. The maximal order type of a well-partial-ordering (X, ≤) is an important characteristic of that well-partial-ordering. It is defined as the order type of the largest possible extension of ≤to a well-ordering and it is denoted as o(X,≤). There is a relation between the maximal order type of a well-partial-ordering and the provability of its well-partial-orderedness in a specific theory by comparing the maximal order type with the proof-theoretical ordinal of that theory. 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 a tree-like structure T(W) introduced by Weiermann. All these tree-like structures will have a Friedman-style gap-embeddability relation on it. 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 well-partial-ordering'.