English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The minimal bad sequence argument due to Nash-Williams is a powerful tool incombinatorics with important implications for theoretical computer science. Inparticular, it yields a very elegant proof of Kruskal's theorem. At the sametime, it is known that Kruskal's theorem does not require the full strength ofthe minimal bad sequence argument. This claim can be made precise in theframework of reverse mathematics, where the existence of minimal bad sequencesis equivalent to a principle known as $\Pi^1_1$-comprehension, which is muchstronger than Kruskal's theorem. In the present paper we give a uniform versionof Kruskal's theorem by relativizing it to certain transformations of wellpartial orders. We show that $\Pi^1_1$-comprehension is equivalent to ouruniform Kruskal theorem (over $\mathbf{RCA}_0$ together with thechain-antichain principle). This means that any proof of the uniform Kruskaltheorem must entail the existence of minimal bad sequences. As a by-product ofour investigation, we obtain uniform proofs of several Kruskal-typeindependence results.

Minimal bad sequences are necessary for a uniform Kruskal theorem