Zulip Chat Archive

Stream: Is there code for X?

Topic: Dependent Set.PartiallyWellOrderedOn


Daniel Weber (Aug 18 2024 at 06:24):

For proving Kruskal's theorem I needed the following lemma:

def Set.embeddingRel {α β : Type*} (r : α  β  Prop) (a : Set α) (b : Set β) : Prop :=
   f : a  b,  x : a, r x (f x)

theorem Set.PartiallyWellOrderedOn.partiallyWellOrderedOn_finiteSetEmbedding {α : Type*}
    {β :   Type*} ( : {n : }  β n  α)
    (r : α  α  Prop) [IsRefl α r] [IsTrans α r] {s : Set α}
    (h : s.PartiallyWellOrderedOn r) :
     f : (n : )  Set (β n), ( n, (f n).Finite   '' (f n)  s) 
       m n : , m < n  Set.embeddingRel (fun a b  r ( a) ( b))
      (f m) (f n)

This is a fairly direct consequence of Higman's lemma (Set.PartiallyWellOrderedOn.partiallyWellOrderedOn_sublistForall₂), and I managed to prove it. However, due to the dependent types I can't use docs#Set.PartiallyWellOrderedOn and therefore I can't use lemmas about it.
Is there a way to state this directly using docs#Set.PartiallyWellOrderedOn ?


Last updated: May 02 2025 at 03:31 UTC