mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours
Base case a = 0 (b ≥ 1): if d ≥ (j-1)*b + 1 then every colouring of the subsets of Fin d with 0 + b colours has a monochromatic induced F_j in one of the b colours.
Statement
theorem mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours (j b d : ℕ) (hj : 2 ≤ j)
(hb : 1 ≤ b) (hd : (j - 1) * b + 1 ≤ d) : mixed_ramsey_property j 0 b d- Source
- step towards mixed_diamond_fan_ramsey_bound
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- has_monochromatic_fan_copyFor a colouring χ of the subsets of Fin d with k colours, has_monochromatic_fan_copy j d col χ holds if there is a set top of colour col…
- mixed_ramsey_propertymixed_ramsey_property j a b d asserts that every colouring of the subsets of Fin d with a + b colours has a monochromatic induced copy of…
- fan_ramsey_boundFor j ≥ 2 and k ≥ 1, every colouring of the subsets of Fin d with k colours, where d ≥ k(j-1)+1, contains a monochromatic induced copy of…
- Used by 1
- mixed_diamond_fan_ramsey_boundFor j ≥ 2, a colouring of the subsets of Fin d with a + b colours contains a monochromatic induced j-diamond in one of the first a…
The proof, explained
This theorem establishes the base case a = 0 of the mixed diamond-fan Ramsey bound, where no colours are reserved for diamonds and all b colours are fan colours. Because the dimension d satisfies d ≥ (j - 1) * b + 1, the general fan Ramsey theorem (`fan_ramsey_bound_general`) applies directly to any colouring with 0 + b colours. Identifying the resulting monochromatic colour with a colour in Fin b via `Fin.natAdd 0` produces the desired monochromatic fan.
To establish `mixed_ramsey_property j 0 b d`, it suffices to find a monochromatic fan copy for any (0 + b)-colouring χ.
Given an arbitrary colouring χ of the subsets of `Fin d` using 0 + b colours, the definition of `mixed_ramsey_property` offers a disjunction: either a monochromatic diamond in one of the first 0 colours, or a monochromatic fan in one of the b fan colours. Since there are 0 diamond colours, the tactic `right` selects the second alternative, leaving the goal of finding a monochromatic fan in some colour `Fin.natAdd 0 col'`.
intro χ right
The number of colours 0 + b is at least 1, and the cardinality condition (0 + b) * (j - 1) + 1 ≤ |Fin d| holds.
Since b ≥ 1, linear arithmetic (`omega`) shows 1 ≤ 0 + b. Furthermore, using |Fin d| = d (`Fintype.card_fin`), simplifying 0 + b to b (`Nat.zero_add`), and commutativity of multiplication (`Nat.mul_comm`), the cardinality requirement (0 + b) * (j - 1) + 1 ≤ |Fin d| reduces to (j - 1) * b + 1 ≤ d, which is exactly the hypothesis `hd`.
uses
Fintype.card_fin,Nat.zero_add,Nat.mul_commhave hk : 1 ≤ 0 + b := by omega have hcard : (0 + b) * (j - 1) + 1 ≤ Fintype.card (Fin d) := by rw [Fintype.card_fin, Nat.zero_add, Nat.mul_comm] exact hd
There exists a monochromatic fan copy of size j in some colour col ∈ Fin (0 + b).
Applying the general fan Ramsey theorem `fan_ramsey_bound_general` with k = 0 + b colours on the universe `Fin d` produces a colour `col : Fin (0 + b)`, a top subset `top`, and j pairwise incomparable subsets `mid i ⊂ top` that all share the colour `col`.
uses
fan_ramsey_bound_generalhave h := fan_ramsey_bound_general j hj (0 + b) hk (Fin d) hcard χ rcases h with ⟨col, top, htop, mid, hmid, hinc⟩
The colour col ∈ Fin (0 + b) is equal to Fin.natAdd 0 col' for some col' ∈ Fin b.
Since `col.val < 0 + b = b`, the underlying integer value of `col` defines a valid element `col' : Fin b`. Shifting this index by 0 via `Fin.natAdd 0` produces `col`, so we can substitute `col` with `Fin.natAdd 0 col'`.
have hcol : ∃ col' : Fin b, Fin.natAdd 0 col' = col := by use ⟨col.val, by omega⟩ ext simp rcases hcol with ⟨col', rfl⟩
The monochromatic fan copy witnessed by col', top, and mid satisfies the goal.
Supplying the re-indexed colour `col'`, the top set `top`, and the collection of subsets `mid` witnesses `has_monochromatic_fan_copy j d (Fin.natAdd 0 col') χ`, completing the proof.
refine ⟨col', top, htop, mid, hmid, hinc⟩
Fintype.card_fin- The cardinality of the standard finite type `Fin n` with n elements is n.
Nat.zero_add- Adding zero on the left is the identity: `0 + n = n`.
Nat.mul_comm- Multiplication of natural numbers is commutative: `n * m = m * n`.
fan_ramsey_bound_general- For any finite set α with |α| ≥ k * (j - 1) + 1 and j ≥ 2, k ≥ 1, any k-colouring of the subsets of α contains a monochromatic induced fan copy of size j.
- Lines 12–16 perform a purely formal re-indexing between `Fin (0 + b)` and `Fin b` using `Fin.natAdd 0`, which has no mathematical content beyond 0 + b = b but is required by Lean's dependent type system to match the signature of `mixed_ramsey_property`.
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.
/-- Base case a = 0: only fan colours, so this is fan_ramsey_bound up to the Fin (0+b) ≃ Fin b reindexing. -/theorem mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours (j b d : ℕ) (hj : 2 ≤ j) (hb : 1 ≤ b) (hd : (j - 1) * b + 1 ≤ d) : mixed_ramsey_property j 0 b d := by intro χ right have hk : 1 ≤ 0 + b := by omega have hcard : (0 + b) * (j - 1) + 1 ≤ Fintype.card (Fin d) := by rw [Fintype.card_fin, Nat.zero_add, Nat.mul_comm] exact hd have h := fan_ramsey_bound_general j hj (0 + b) hk (Fin d) hcard χ rcases h with ⟨col, top, htop, mid, hmid, hinc⟩ have hcol : ∃ col' : Fin b, Fin.natAdd 0 col' = col := by use ⟨col.val, by omega⟩ ext simp rcases hcol with ⟨col', rfl⟩ refine ⟨col', top, htop, mid, hmid, hinc⟩