Project

Measuring the logical strength of well quasi-orders and better quasi-orders

Code
1257725N
Duration
01 November 2024 → 31 October 2027
Funding
Research Foundation - Flanders (FWO)
Research disciplines
  • Natural sciences
    • Order, lattices, ordered algebraic structures
    • Combinatorics
    • Analysis of algorithms and complexity
Keywords
reverse mathematics Weihrauch reducibility wqo and bqo theory
 
Project description

Well quasi-orders (wqo’s) and their natural evolution, better quasi-orders (bqo’s), are among the most fundamental objects in combinatorics: they are at the center of a rich theory counting numerous applications in other areas of mathematics, ranging from theoretical computer science to topology. From the logical point of view, wqo's and bqo's are particularly interesting because their ubiquity in combinatorics combines with their foundational importance, especially in terms of computability theory or descriptive set theory. Yet, despite their widely recognized relevance, they remain in many ways mysterious, and many fundamental questions concerning them are wide open. This project aims to address this, by studing wqo’s and bqo’s in the framework of reverse mathematics and Weihrauch reducibility. The core of the project is to apply our recent advancements in these fields to the study of four tightly correlated problems corresponding to the most important yet unknown aspects of wqo’s and bqo’s: Nash-Williams’ theorem, Fraïssé's conjecture, several versions of Kruskal’s theorem, and the calibration of the computational content of wqo's and bqo’s. The results we will prove and the techniques we will use, coming from a combination of proof theory and computability theory, have the potential to bring great advancements in many related fields of mathematical logic, in particular theoretical computer science.