AFTD Auto-Formalizing Theoretical Domains

five_diamond_ramsey_property_iff_sets

theoremverified

A k-colouring of the subsets of Fin d contains a monochromatic induced copy of the j-diamond exactly when it has, in one colour, a set B, a set T with B ⊂ T, and j pairwise incomparable sets M i with B ⊂ M i ⊂ T for all i.

Statement

theorem five_diamond_ramsey_property_iff_sets (j k d : ℕ) :
    poset_ramsey_property (DiamondPoset j) k d ↔
      ∀ c : Finset (Fin d) → Fin k,
        ∃ (col : Fin k) (B T : Finset (Fin d)) (M : Fin j → Finset (Fin d)),
          c B = col ∧ c T = col ∧ (∀ i, c (M i) = col) ∧
            B ⊂ T ∧ (∀ i, B ⊂ M i ∧ M i ⊂ T) ∧
              ∀ i i', i ≠ i' → ¬ (M i ⊆ M i')
Source
step towards op_270_five_diamond_poset_ramsey_number
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • poset_ramsey_propertyFor a preordered type P and natural numbers k and d, poset_ramsey_property P k d asserts that for every coloring c : Finset (Fin d) → Fin…
  • 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

The proof, explained

The proof establishes an equivalence between the Ramsey property for the j-diamond poset and an explicit set-containment condition. In the forward direction, given a monochromatic order embedding f of the j-diamond, its values at the bottom, top, and middle elements directly satisfy the required strict inclusions and antichain property. In the backward direction, given sets B, T, and M i satisfying the conditions, a piecewise function g is defined; verifying that g preserves and reflects the poset order across all nine combinations of elements allows OrderEmbedding.ofMapLEIff to construct the required monochromatic order embedding.

  1. In the forward direction, assume the Ramsey property holds, fix a colouring c, and define the candidate sets as the images of the diamond poset elements under the given order embedding.

    We split the equivalence into two implications. In the forward direction, given the Ramsey property and an arbitrary k-colouring c of the subsets of Fin d, we obtain a monochromatic order embedding f : DiamondPoset j ↪o Finset (Fin d) with colour col. We set B = f(bot), T = f(top), and M i = f(mid i). Each of these sets has colour col because f is monochromatic.

    lines 9–13

      constructor
      · rintro h c
        obtain ⟨f, col, hf⟩ := h c
        refine ⟨col, f DiamondPoset.bot, f DiamondPoset.top, fun i => f (DiamondPoset.mid i),
          hf _, hf _, fun i => hf _, ?_, ?_, ?_⟩
  2. The chosen sets satisfy the strict inclusions B ⊂ T and B ⊂ M i ⊂ T for each i.

    Since f is an order embedding, it reflects and preserves strict inequalities (f.lt_iff_lt). Using lt_iff_le_not_ge, the strict order relations bot < top and bot < mid i < top hold by definition in DiamondPoset j, which implies B ⊂ T and B ⊂ M i ⊂ T for every index i.

    lines 14–17

    uses lt_iff_le_not_ge, id

        · exact f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩)
        · intro i
          exact ⟨f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩),
            f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩)⟩
  3. The middle sets M i form an antichain under subset inclusion.

    For distinct indices i ≠ i', if we had M i ⊆ M i', then f(mid i) ⊆ f(mid i'). Since order embeddings reflect the partial order (f.le_iff_le), this would imply mid i ≤ mid i' in DiamondPoset j. In DiamondPoset j, mid i ≤ mid i' only holds when i = i', which contradicts i ≠ i'.

    lines 18–19

        · intro i i' hne hle
          exact hne (f.le_iff_le.mp hle)
  4. In the backward direction, assume the set-theoretic condition and define the piecewise map g from DiamondPoset j to Finset (Fin d).

    Given a colouring c, the assumption provides a colour col and sets B, T, and M i satisfying the inclusion and antichain conditions, all coloured col. We define g by sending bot to B, mid i to M i, and top to T.

    lines 20–26

      · intro h c
        obtain ⟨col, B, T, M, hB, hT, hM, hBT, hMid, hInc⟩ := h c
        let g : DiamondPoset j → Finset (Fin d) := fun x =>
          match x with
          | .bot => B
          | .mid i => M i
          | .top => T
  5. The function g preserves and reflects the partial order: g a ⊆ g b ↔ a ≤ b for all a, b in DiamondPoset j.

    We verify this equivalence by case analysis on a and b (9 cases): - If a = bot, g(bot) = B ⊆ g(b) holds because B ⊆ B by reflexivity (le_refl), B ⊂ M i, and B ⊂ T; similarly, bot ≤ b always holds. - If a = mid i: - b = bot: M i ⊆ B is false because B ⊂ M i, and mid i ≤ bot is false. - b = mid i': M i ⊆ M i' implies i = i' by the antichain hypothesis, matching mid i ≤ mid i'; conversely, if i = i', reflexivity (le_refl) gives M i ⊆ M i. - b = top: M i ⊆ T holds because M i ⊂ T, and mid i ≤ top holds. - If a = top: - b = bot or mid i: T ⊆ B and T ⊆ M i are false because B ⊂ T and M i ⊂ T, and top ≤ b is false. - b = top: T ⊆ T holds by reflexivity (le_refl), and top ≤ top holds.

    lines 27–49

    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.le⟩
          | top =>
            cases b with
            | bot => exact ⟨hBT.not_ge, fun h => h.elim⟩
            | mid i => exact ⟨(hMid i).2.not_ge, fun h => h.elim⟩
            | top => exact ⟨fun _ => trivial, fun _ => le_refl T⟩
  6. The map g lifts to an order embedding, establishing the monochromatic diamond poset.

    Using OrderEmbedding.ofMapLEIff g key, g is elevated to an order embedding from DiamondPoset j into Finset (Fin d). By definition of g, evaluating it at bot, mid i, or top yields B, M i, or T, each of which has colour col. This verifies that all points of the embedded diamond have colour col, proving the Ramsey property.

    lines 50–54

    uses OrderEmbedding.ofMapLEIff

        refine ⟨OrderEmbedding.ofMapLEIff g key, col, fun x => ?_⟩
        cases x with
        | bot => exact hB
        | mid i => exact hM i
        | top => exact hT
lt_iff_le_not_ge
In a preorder, strict inequality a < b is equivalent to a ≤ b and ¬(b ≤ a).
id
The identity function, which returns its input unchanged.
le_refl
The reflexivity of the order relation ≤ in a preorder: a ≤ a for every element a.
OrderEmbedding.ofMapLEIff
Constructs an order embedding from a map between a partial order and a preorder, given that the map reflects and preserves ≤.

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

/-- Unfolds poset_ramsey_property for DiamondPoset j into an explicit bottom/top/antichain condition on the sets. -/theorem five_diamond_ramsey_property_iff_sets (j k d : ℕ) :    poset_ramsey_property (DiamondPoset j) k d ↔      ∀ c : Finset (Fin d) → Fin k,        ∃ (col : Fin k) (B T : Finset (Fin d)) (M : Fin j → Finset (Fin d)),          c B = col ∧ c T = col ∧ (∀ i, c (M i) = col) ∧            B ⊂ T ∧ (∀ i, B ⊂ M i ∧ M i ⊂ T) ∧              ∀ i i', i ≠ i' → ¬ (M i ⊆ M i') := by  constructor  · rintro h c    obtain ⟨f, col, hf⟩ := h c    refine ⟨col, f DiamondPoset.bot, f DiamondPoset.top, fun i => f (DiamondPoset.mid i),      hf _, hf _, fun i => hf _, ?_, ?_, ?_⟩    · exact f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩)    · intro i      exact ⟨f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩),        f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩)⟩    · intro i i' hne hle      exact hne (f.le_iff_le.mp hle)  · intro h c    obtain ⟨col, B, T, M, hB, hT, hM, hBT, hMid, hInc⟩ := h c    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.le⟩      | top =>        cases b with        | bot => exact ⟨hBT.not_ge, fun h => h.elim⟩        | mid i => exact ⟨(hMid i).2.not_ge, fun h => h.elim⟩        | top => exact ⟨fun _ => trivial, fun _ => le_refl T⟩    refine ⟨OrderEmbedding.ofMapLEIff g key, col, fun x => ?_⟩    cases x with    | bot => exact hB    | mid i => exact hM i    | top => exact hT
See it in the graphDiscuss this resultChallenge it