3.1 — no infinite strictly descending chain of ideals below a well-quasi-order
ProvedRobertsonSeymour2010.GM23.Immersion.no_descending_idealsorder-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1well-quasi-order
Let be quasi-orders on subsets of a common ambient set. Write when is an ideal of (a sub-quasi-order closed downwards in ) and . Then there is no sequence such that is a well-quasi-order and
In other words, the relation "is a proper ideal of" is well-founded below any well-quasi-order. The paper calls this a well-known lemma and uses it, through 3.2, to run an induction on shadows.
Formalization Note. Quasi-orders are QO X on a common ambient type X; the sequence is indexed from , so the paper's is Ω 0. "" is the negation of QO.Same (same ground set and same order on it).
Preamble
import Mathlib import Definitions.Def_RobertsonSeymour2010_GM23_Immersion_QuasiOrders
Formal statement
namespace RobertsonSeymour2010.GM23.Immersion
theorem no_descending_ideals (X : Type) (Ω : ℕ → QO X) (hΩ : (Ω 0).IsWQO) :
¬ ∀ i : ℕ, (Ω (i + 1)).IsProperIdeal (Ω i) := by sorry
end RobertsonSeymour2010.GM23.Immersion
Source
Robertson, Seymour, Graph Minors XXIII. Nash-Williams' immersion conjecture (authors' manuscript, rev. Apr. 18, 2011), 3.1, p. 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.