Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

α\alphaα-well-quasi-ordering is monotone in α\alphaα

Proved
TenChallenges.isAlphaWQO_mono

by Davide · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

bqoorder-theoryten-challengeswqo

Let (Q,≤)(Q,\le)(Q,≤) be a set with a binary relation and let β≤α\beta\le\alphaβ≤α be ordinals. If (Q,≤)(Q,\le)(Q,≤) is α\alphaα-well-quasi-ordered, then it is β\betaβ-well-quasi-ordered:

β≤α  and  (Vα∗(Q),≤∗) WQO ⟹ (Vβ∗(Q),≤∗) WQO.\beta\le\alpha\ \text{ and }\ (V^*_\alpha(Q),\le^*)\ \text{WQO}\ \Longrightarrow\ (V^*_\beta(Q),\le^*)\ \text{WQO}.β≤α  and  (Vα∗​(Q),≤∗) WQO ⟹ (Vβ∗​(Q),≤∗) WQO.

Here Vα∗(Q)V^*_\alpha(Q)Vα∗​(Q) is the Nash-Williams cumulative hierarchy (nonempty subsets at successor levels, disjoint unions at limit levels) with the game relation ≤∗\le^*≤∗, as in the definition IsAlphaWQO.

So the α\alphaα-WQO properties form a hierarchy of strengthenings of well-quasi-ordering (000-WQO), with better-quasi-ordering at the top. For the minor order this means, for instance, that each rung of Challenge 6 implies the lower rungs of the same parity; in particular WQO(2)\mathrm{WQO}(2)WQO(2) implies WQO(0)\mathrm{WQO}(0)WQO(0).

Preamble
import Definitions.Def_TenChallenges_AlphaWQO

universe u
Formal statement
namespace TenChallenges
theorem isAlphaWQO_mono {Q : Type u} (le : Q → Q → Prop) {α β : Ordinal.{u}} (h : β ≤ α) :
    IsAlphaWQO le α → IsAlphaWQO le β := by sorry
end TenChallenges
Source
Standard property of the α-WQO hierarchy (Marcone, 'Foundations of bqo theory', Trans. AMS 345 (1994)); stated for the hierarchy and game relation of the definition TenChallenges_AlphaWQO, used by Ten Challenges 06.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me