-well-quasi-ordering pulls back along order-reflecting maps
ProvedTenChallenges.isAlphaWQO_of_reflecting_mapLet and be sets with binary relations, and let be a map that reflects the order:
Then for every ordinal , if is -well-quasi-ordered, so is . Here -WQO means that level of the Nash-Williams cumulative hierarchy (nonempty subsets at successor levels, disjoint unions at limit levels) is well-quasi-ordered under the game relation , as in the definition IsAlphaWQO.
The case is the familiar fact that a well-quasi-order restricts to subsets. In general, induces a map (apply at level , take images at successor levels, keep the tag at limit levels), and this map reflects . A bad sequence in would therefore push forward to a bad sequence in . In particular, applied to the inclusion of planar graphs into all finite graphs, it shows that whenever finite graphs are -WQO under minors, so are finite planar graphs.
import Definitions.Def_TenChallenges_AlphaWQO universe u
namespace TenChallenges
theorem isAlphaWQO_of_reflecting_map {P Q : Type u} (leP : P → P → Prop) (leQ : Q → Q → Prop)
(e : P → Q) (he : ∀ x y, leQ (e x) (e y) → leP x y) (α : Ordinal.{u}) :
IsAlphaWQO leQ α → IsAlphaWQO leP α := by sorry
end TenChallenges