AFTD Auto-Formalizing Theoretical Domains

orderEmbedding_of_diamond_copy

theoremverified

If the colouring χ of the subsets of Fin d has a monochromatic combinatorial j-diamond copy in colour col, then there is an order embedding of DiamondPoset j into Finset (Fin d) all of whose values have colour col. Hence the combinatorial predicate agrees with the order-embedding based definition of a monochromatic induced copy.

Statement

theorem orderEmbedding_of_diamond_copy (j d : ℕ) {k : ℕ} (col : Fin k) (χ : Finset (Fin d) → Fin k)
    (h : has_monochromatic_diamond_copy j d col χ) :
    ∃ e : DiamondPoset j ↪o Finset (Fin d), ∀ x : DiamondPoset j, χ (e x) = col
Source
step towards diamond_poset_ramsey_number_le
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • has_monochromatic_diamond_copyFor a colouring χ of the subsets of Fin d with k colours, has_monochromatic_diamond_copy j d col χ holds if there are sets bot ⊂ top of…
  • DiamondPosetFor a natural number j, DiamondPoset j is the type consisting of a bottom element bot, a top element top, and j middle elements indexed by…
  • inst_partial_order_diamond_posetThe partial order on DiamondPoset j where bot is less than or equal to every element, every element is less than or equal to top, and two…
Used by 2
  • diamond_poset_ramsey_propertyFor j ≥ 2 and k ≥ 1, every colouring of the subsets of Fin (j*k) with k colours has a monochromatic induced copy of the j-diamond…
  • diamond_poset_ramsey_number_leFor all natural numbers j ≥ 2 and k ≥ 1, the k-color poset Ramsey number of the j-diamond DiamondPoset j is at most j * k.

The proof, explained

The proof unpacks the monochromatic combinatorial diamond hypothesis into bottom and top sets B, T and pairwise incomparable middle sets M i, then defines the candidate map g sending bot to B, mid i to M i, and top to T. A 3×3 case analysis verifies that g preserves and reflects the order, allowing OrderEmbedding.ofMapLEIff to promote g to an order embedding. Finally, the monochromaticity of the embedding's image is verified directly on bot, mid i, and top from the color hypotheses.

  1. We unpack the combinatorial diamond copy hypothesis into its constituent subsets and properties.

    From the hypothesis h, we obtain the bottom set B, the top set T, the strict inclusion B ⊂ T, their colours χ B = col and χ T = col, and a family of middle sets M i for each i : Fin j such that B ⊂ M i ⊂ T, χ (M i) = col, and any two distinct middle sets are incomparable (i ≠ i' → ¬ M i ⊆ M i').

    line 5

      obtain ⟨B, T, hBT, hB, hT, M, hMid, hInc⟩ := h
  2. We define the candidate map g from DiamondPoset j to Finset (Fin d).

    We define g by sending DiamondPoset.bot to B, each DiamondPoset.mid i to M i, and DiamondPoset.top to T.

    lines 6–10

      let g : DiamondPoset j → Finset (Fin d) := fun x =>
        match x with
        | .bot => B
        | .mid i => M i
        | .top => T
  3. The map g preserves and reflects the partial order: for all a b : DiamondPoset j, g a ⊆ g b ↔ a ≤ b.

    We evaluate all nine combinations of (a, b) via case analysis on a and b: - When a = bot, bot ≤ b is always true in DiamondPoset j, and g bot = B ⊆ g b holds because B ⊆ B by reflexivity (le_refl), B ⊂ M i implies B ⊆ M i, and B ⊂ T implies B ⊆ T. - When a = mid i: for b = bot, M i ⊆ B is false because B ⊂ M i; for b = mid i', M i ⊆ M i' holds if and only if i = i' by the incomparability hypothesis hInc and reflexivity (le_refl); for b = top, M i ⊆ T holds because M i ⊂ T. - When a = top: for b = bot or b = mid i, T ⊆ g b fails because g b ⊂ T; for b = top, T ⊆ T holds by reflexivity (le_refl).

    lines 11–33

    uses le_refl

      have key : ∀ a b : DiamondPoset j, g a ≤ g b ↔ a ≤ b := by
        intro a b
        cases a with
        | bot =>
          cases b with
          | bot => exact ⟨fun _ => trivial, fun _ => le_refl B⟩
          | mid i => exact ⟨fun _ => trivial, fun _ => (hMid i).1.le⟩
          | top => exact ⟨fun _ => trivial, fun _ => hBT.le⟩
        | mid i =>
          cases b with
          | bot => exact ⟨(hMid i).1.not_ge, fun h => h.elim⟩
          | mid i' =>
            refine ⟨fun hle => ?_, fun heq => ?_⟩
            · by_contra hne
              exact hInc i i' hne hle
            · subst heq
              exact le_refl _
          | top => exact ⟨fun _ => trivial, fun _ => (hMid i).2.1.le⟩
        | top =>
          cases b with
          | bot => exact ⟨hBT.not_ge, fun h => h.elim⟩
          | mid i => exact ⟨(hMid i).2.1.not_ge, fun h => h.elim⟩
          | top => exact ⟨fun _ => trivial, fun _ => le_refl T⟩
  4. We construct the order embedding from g and reduce the remaining goal to monochromaticity.

    Using OrderEmbedding.ofMapLEIff with the order-reflection equivalence key, g is packaged into an order embedding e : DiamondPoset j ↪o Finset (Fin d). It remains to show that χ (e x) = col for all x.

    line 34

    uses OrderEmbedding.ofMapLEIff

      refine ⟨OrderEmbedding.ofMapLEIff g key, fun x => ?_⟩
  5. Every element in the image of the order embedding has colour col.

    By case analysis on x: when x = bot, χ B = col holds by hB; when x = mid i, χ (M i) = col holds by (hMid i).2.2; when x = top, χ T = col holds by hT.

    lines 35–38

      cases x with
      | bot => exact hB
      | mid i => exact (hMid i).2.2
      | top => exact hT
le_refl
reflexivity of a preorder: every element is less than or equal to itself ($a ≤ a$)
OrderEmbedding.ofMapLEIff
constructs an order embedding from a function between preorders that preserves and reflects the order ($f(a) ≤ f(b) ↔ a ≤ b$)

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- A monochromatic combinatorial diamond copy (bot, j incomparable middles, top) is a monochromatic induced copy in the order-embedding sense: it yields an order embedding of DiamondPoset j into the Boolean lattice whose image is constant under the colouring. -/theorem orderEmbedding_of_diamond_copy (j d : ℕ) {k : ℕ} (col : Fin k) (χ : Finset (Fin d) → Fin k)    (h : has_monochromatic_diamond_copy j d col χ) :    ∃ e : DiamondPoset j ↪o Finset (Fin d), ∀ x : DiamondPoset j, χ (e x) = col := by  obtain ⟨B, T, hBT, hB, hT, M, hMid, hInc⟩ := h  let g : DiamondPoset j → Finset (Fin d) := fun x =>    match x with    | .bot => B    | .mid i => M i    | .top => T  have key : ∀ a b : DiamondPoset j, g a ≤ g b ↔ a ≤ b := by    intro a b    cases a with    | bot =>      cases b with      | bot => exact ⟨fun _ => trivial, fun _ => le_refl B⟩      | mid i => exact ⟨fun _ => trivial, fun _ => (hMid i).1.le⟩      | top => exact ⟨fun _ => trivial, fun _ => hBT.le⟩    | mid i =>      cases b with      | bot => exact ⟨(hMid i).1.not_ge, fun h => h.elim⟩      | mid i' =>        refine ⟨fun hle => ?_, fun heq => ?_⟩        · by_contra hne          exact hInc i i' hne hle        · subst heq          exact le_refl _      | top => exact ⟨fun _ => trivial, fun _ => (hMid i).2.1.le⟩    | top =>      cases b with      | bot => exact ⟨hBT.not_ge, fun h => h.elim⟩      | mid i => exact ⟨(hMid i).2.1.not_ge, fun h => h.elim⟩      | top => exact ⟨fun _ => trivial, fun _ => le_refl T⟩  refine ⟨OrderEmbedding.ofMapLEIff g key, fun x => ?_⟩  cases x with  | bot => exact hB  | mid i => exact (hMid i).2.2  | top => exact hT
See it in the graphDiscuss this resultChallenge it