orderEmbedding_of_diamond_copy
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.
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').
obtain ⟨B, T, hBT, hB, hT, M, hMid, hInc⟩ := hWe 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.
let g : DiamondPoset j → Finset (Fin d) := fun x => match x with | .bot => B | .mid i => M i | .top => T
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).
uses
le_reflhave 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⟩
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.
uses
OrderEmbedding.ofMapLEIffrefine ⟨OrderEmbedding.ofMapLEIff g key, fun x => ?_⟩
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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