-
Natural sciences
- Order, lattices, ordered algebraic structures
- Combinatorics
- Analysis of algorithms and complexity
Welquasiordes (wqo's) en hun natuurlijke evolutie, beterquasiordes (bqo's), behoren tot de meest fundamentele objecten in de combinatoriek: ze vormen de kern van een rijke theorie die talloze toepassingen kent in andere gebieden van de wiskunde, variërend van theoretische informatica tot topologie. Vanuit een logisch oogpunt zijn wqos en bqos interessant omdat hun alomtegenwoordigheid in de combinatoriek gecombineerd wordt met hun fundamentele belang, vooral in termen van berekenbaarheidstheorie of beschrijvende verzamelingenleer. Maar ondanks hun algemeen erkende relevantie blijven ze in veel opzichten mysterieus, en veel fundamentele vragen hierover zijn onopgelost. Dit project heeft als doel wqos en bqos te bestuderen in het kader van reverse mathematics en Weihrauch-reduceerbaarheid. De kern van het project is om onze recente vorderingen op deze gebieden toe te passen op de studie van vier nauw verwante problemen die overeenkomen met de belangrijkste onbekende aspecten van wqo's en bqos: de stelling van Nash-Williams, het vermoeden van Fraïssé, verschillende versies van de stelling van Kruskal, en de kalibratie van de computationele inhoud van wqos en bqos. De resultaten die we zullen bewijzen en de technieken die we zullen gebruiken, die voortkomen uit een combinatie van bewijstheorie en berekenbaarheidstheorie, hebben het potentieel om grote vooruitgang te boeken in veel verwante gebieden van de wiskundige logica, in het bijzonder de theoretische informatica.