Ordinal Analysis of Well-Ordering Principles, Well Quasi-Orders Closure Properties, and $Σ_n$-Collection Schema Article Swipe

MAKE IMPACT

Buriola, Gabriele , Weiermann, Andreas · YOU? · · 2025 · Open Access ·

The study of well quasi-orders, wqo, is a cornerstone of combinatorics and within wqo theory Kruskal's theorem plays a crucial role. Extending previous proof-theoretic results, we calculate the $Π^1_1$ ordinals of two different versions of labelled Kruskal's theorem: $\forall n \,$ $\mbox{KT}_\ell(n)$ and $\mbox{KT}_ω(n)$; denoting, respectively, all the cases of labelled Kruskal's theorem for trees with an upper bound on the branching degree, and the standard Kruskal's theorem for labelled trees. In order to reach these computations, a key step is to move from Kruskal's theorem, which regards preservation of wqo's, to an equivalent Well-Ordering Principle (WOP), regarding instead preservation of well-orders. Given an ordinal function $g$, WOP$(g)$ amounts to the following principle $\forall X\, [\mbox{WO}(X) \rightarrow \mbox{WO}(g(X))]$, where $WO(X)$ states that ``$X$ is a well-order''. In our case, the two ordinal functions involved are ${g}_{\forall}(X)=\sup_{n}\vartheta(Ω^n \cdot X)$ and ${g}_ω(X)=\vartheta(Ω^ω\! \cdot X)$. In addition to the ordinal analysis of Kruskal's theorem and its related WOP, a series of Well Quasi-orders Principles (WQP) is considered. Given a set operation $G$ that preserves the property of being a wqo, its Well Quasi-orders closure Property, WQP$(G)$, is given by the principle $\forall Q\, [Q\, \mbox{wqo} \rightarrow G(Q)\, \mbox{wqo}]$. Conducting this study, unexpected connections with different principles arising from Ramsey and Computational theory, such as RT$^2_{<\infty}$, CAC, ADS, RT$^1_{<\infty}$, turn up. Lastly, extending and combining previous results, we achieve also the ordinal analysis of the collection schema $\mbox{B}Σ_n$.

Type

article

Landing Page

http://arxiv.org/abs/2511.11196

PDF

https://arxiv.org/pdf/2511.11196

OA Status

green

OpenAlex ID

https://openalex.org/W7105978722

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7105978722

Canonical identifier for this work in OpenAlex

Title

Ordinal Analysis of Well-Ordering Principles, Well Quasi-Orders Closure Properties, and $Σ_n$-Collection Schema

Work title

Type

article

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-11-14

Full publication date if available

Authors

Buriola, Gabriele, Weiermann, Andreas

List of authors in order

Landing page

https://arxiv.org/abs/2511.11196

Publisher landing page

PDF URL

https://arxiv.org/pdf/2511.11196

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2511.11196

Direct OA link when available

Concepts

Mathematics, Schema (genetic algorithms), Closure (psychology), Discrete mathematics, Calculus (dental), Ordinal optimization, Set function, Property (philosophy), Function (biology), Branching (polymer chemistry), Key (lock), Set (abstract data type), Combinatorics, Algebra over a field, Series (stratigraphy), Ordinal data, Formal concept analysis, Order (exchange), Proposition, Algorithm

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload