mdfrbf_colour_inj
There is a bijection from Fin (a + (b-1)) onto the colours of Fin (a+b) other than the fan colour Fin.natAdd a c, which fixes the a diamond colours (Fin.castAdd (b-1) col ↦ Fin.castAdd b col), sends fan colours to fan colours, and never takes the value Fin.natAdd a c.
Statement
theorem mdfrbf_colour_inj (a b : ℕ) (ha : 1 ≤ a) (hb : 2 ≤ b) (c : Fin b) :
∃ f : Fin (a + (b - 1)) → Fin (a + b),
Function.Injective f ∧
(∀ v : Fin (a + b), v ≠ Fin.natAdd a c → ∃ u : Fin (a + (b - 1)), f u = v) ∧
(∀ col : Fin a, f (Fin.castAdd (b - 1) col) = Fin.castAdd b col) ∧
(∀ u : Fin (b - 1), ∃ col' : Fin b, f (Fin.natAdd a u) = Fin.natAdd a col') ∧
(∀ u : Fin (a + (b - 1)), f u ≠ Fin.natAdd a c)- Source
- step towards mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- mixed_diamond_fan_ramsey_bound_all_singletons_fan_coloursCase b ≥ 2 with every singleton fan-coloured: if d ≥ j*a + (j-1)*b + 1 and the statement holds at (a, b-1) in dimension d-(j-1), then χ…
The proof, explained
The theorem constructs a colour bijection f from the a + (b - 1) colours surviving the deletion of the fan colour c into the original a + b colours, fixing the a diamond colours and avoiding the deleted fan colour a + c. The construction first defines an auxiliary map g from Fin (b - 1) to Fin b that skips c (by mapping u to u when u < c and to u + 1 when u ≥ c), and then defines f to be the identity on diamond colours and a + g(v - a) on fan colours. The proof verifies that g is an injective map avoiding c with image Fin b \ {c}, from which the injectivity, range constraints, and surjectivity of f onto all colours except a + c follow directly.
Define the fan-colour skipping map g and the full colour map f.
The fan has b - 1 colours after deleting c, which need to be mapped into the original b colours skipping c. We define g : Fin (b - 1) → Fin b by g(u) = u if u < c and g(u) = u + 1 if u ≥ c. Then we define f : Fin (a + (b - 1)) → Fin (a + b) piecewise: on the first a colours (the diamond colours), f acts as the identity; on the remaining b - 1 colours (the fan colours), f(v) = a + g(v - a).
let g : Fin (b - 1) → Fin b := fun u => if h : u.val < c.val then ⟨u.val, by omega⟩ else ⟨u.val + 1, by have := u.isLt; omega⟩ let f : Fin (a + (b - 1)) → Fin (a + b) := fun v => if h : v.val < a then ⟨v.val, by omega⟩ else Fin.natAdd a (g ⟨v.val - a, by have := v.isLt; omega⟩)
The auxiliary fan map g is injective.
Suppose g(u) = g(u'). By Fin.ext, their underlying numerical values are equal. Case analysis on whether u < c and u' < c yields four cases: if both are less than c, u = u'; if both are at least c, u + 1 = u' + 1, so u = u'; and the mixed cases (u < c ≤ u' with u = u' + 1, or vice versa) are contradictions by linear arithmetic.
uses
Fin.ext,Fin.mk.injEqhave g_inj : Function.Injective g := by intro u u' h apply Fin.ext dsimp [g] at h split_ifs at h with h1 h2 h1 h2 all_goals simp only [Fin.mk.injEq] at h ⊢ all_goals omega
The auxiliary map g never takes the value c.
For any u, if u < c then g(u) = u < c, so g(u) ≠ c; if u ≥ c then g(u) = u + 1 > c, so again g(u) ≠ c.
have g_ne : ∀ u : Fin (b - 1), (g u).val ≠ c.val := by intro u have g_val : (g u).val = if u.val < c.val then u.val else u.val + 1 := by dsimp [g] split_ifs <;> rfl rw [g_val] split_ifs with h · omega · omega
The map g is surjective onto Fin b \ {c}.
Given w : Fin b with w ≠ c, we construct its pre-image under g. If w < c, we choose u = w; then u < c, so g(u) = w by if_pos. If w > c, we choose u = w - 1; then u ≥ c, so g(u) = (w - 1) + 1 = w by dif_neg.
uses
if_pos,dif_neg,Fin.exthave g_surj : ∀ w : Fin b, w.val ≠ c.val → ∃ u : Fin (b - 1), g u = w := by intro w hw by_cases hwlt : w.val < c.val · refine ⟨⟨w.val, by omega⟩, ?_⟩ dsimp [g] rw [if_pos hwlt] · have hle : c.val < w.val := by omega refine ⟨⟨w.val - 1, by have := w.isLt; omega⟩, ?_⟩ dsimp [g] have hnot : ¬ w.val - 1 < c.val := by omega rw [dif_neg hnot] apply Fin.ext simp omega
On fan colours, f(a + u) = a + g(u).
Since a + u ≥ a, unfolding the definition of f selects the second branch via dif_neg. The argument passed to g is (a + u) - a = u, yielding f(a + u) = a + g(u).
uses
dif_neg,Fin.exthave f_natAdd : ∀ u : Fin (b - 1), f (Fin.natAdd a u) = Fin.natAdd a (g u) := by intro u dsimp [f] rw [dif_neg (by omega)] congr 1 congr 1 apply Fin.ext simp
The colour map f is injective.
Suppose f(v) = f(v'). We branch on whether v < a and v' < a. If both are < a, both evaluate to their identity values, so v = v'. If v < a ≤ v', then v = a + g(v' - a) ≥ a, contradicting v < a. Symmetrically, v' < a ≤ v is impossible. If both are ≥ a, then a + g(v - a) = a + g(v' - a), which gives g(v - a) = g(v' - a); by the injectivity of g (g_inj), v - a = v' - a, so v = v'.
uses
Fin.ext,dif_pos,dif_neg,congrArg,Fin.val_natAddhave f_inj : Function.Injective f := by intro v v' h by_cases hv : v.val < a · by_cases hv' : v'.val < a · apply Fin.ext dsimp [f] at h rw [dif_pos hv, dif_pos hv'] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h simpa using hval · dsimp [f] at h rw [dif_pos hv, dif_neg hv'] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd] at hval have hval' : v.val = a + (g ⟨v'.val - a, by have := v'.isLt; omega⟩).val := by simpa using hval omega · by_cases hv' : v'.val < a · dsimp [f] at h rw [dif_neg hv, dif_pos hv'] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd] at hval have hval' : a + (g ⟨v.val - a, by have := v.isLt; omega⟩).val = v'.val := by simpa using hval omega · dsimp [f] at h rw [dif_neg hv, dif_neg hv'] at h have hg : g ⟨v.val - a, by have := v.isLt; omega⟩ = g ⟨v'.val - a, by have := v'.isLt; omega⟩ := by apply Fin.ext have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd, Fin.val_natAdd] at hval omega have hsub : v.val - a = v'.val - a := congrArg (fun x : Fin (b - 1) => x.val) (g_inj hg) apply Fin.ext omega
f fixes the diamond colours.
For col : Fin a, since col < a, f takes the first branch via dif_pos, leaving col unchanged. Its value in Fin (a + b) matches Fin.castAdd b col by Fin.val_castAdd.
uses
dif_pos,Fin.ext,Fin.val_castAddhave f_cast : ∀ col : Fin a, f (Fin.castAdd (b - 1) col) = Fin.castAdd b col := by intro col dsimp [f] have h : col.val < a := col.isLt rw [dif_pos h] apply Fin.ext simpa using (Fin.val_castAdd b col).symm
f sends fan colours to fan colours.
For u : Fin (b - 1), f(a + u) = a + g(u) by f_natAdd, so col' = g(u) : Fin b is the desired witness.
have f_fan : ∀ u : Fin (b - 1), ∃ col' : Fin b, f (Fin.natAdd a u) = Fin.natAdd a col' := by intro u exact ⟨g u, f_natAdd u⟩
f never takes the deleted fan colour a + c.
Suppose f(u) = a + c. If u < a, f(u) = u < a while a + c ≥ a, a contradiction. If u ≥ a, write u = a + u0 where u0 = u - a. Then f(u) = a + g(u0) = a + c, which implies g(u0) = c, contradicting g_ne.
uses
dif_pos,congrArg,Fin.val_natAdd,Fin.exthave f_ne : ∀ u : Fin (a + (b - 1)), f u ≠ Fin.natAdd a c := by intro u h by_cases hu : u.val < a · dsimp [f] at h rw [dif_pos hu] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd] at hval have hval' : u.val = a + c.val := by simpa using hval omega · let u0 : Fin (b - 1) := ⟨u.val - a, by have := u.isLt; omega⟩ have hu_eq : u = Fin.natAdd a u0 := by apply Fin.ext simp [u0] omega rw [hu_eq, f_natAdd] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd, Fin.val_natAdd] at hval exact g_ne u0 (by omega)
Package the bijection f and verify that every colour other than a + c is in the range.
We instantiate the existential goal with f and the properties established above. For surjectivity onto Fin (a + b) \ {a + c}, let v ≠ a + c. If v < a, u = v gives f(u) = v. If v ≥ a, let w = v - a : Fin b. Since v ≠ a + c, w ≠ c. By the surjectivity of g (g_surj), there is u0 with g(u0) = w. Then u = a + u0 satisfies f(u) = a + g(u0) = a + w = v.
uses
dif_pos,Fin.ext,Fin.val_natAddrefine ⟨f, f_inj, ?_, f_cast, f_fan, f_ne⟩ intro v hv by_cases hvlt : v.val < a · refine ⟨⟨v.val, by have := v.isLt; omega⟩, ?_⟩ dsimp [f] rw [dif_pos hvlt] · have hvge : a ≤ v.val := by omega let w : Fin b := ⟨v.val - a, by have := v.isLt; omega⟩ have hw_ne : w.val ≠ c.val := by intro hw apply hv apply Fin.ext rw [Fin.val_natAdd] dsimp [w] at hw omega obtain ⟨u0, hu0⟩ := g_surj w hw_ne refine ⟨Fin.natAdd a u0, ?_⟩ rw [f_natAdd, hu0] apply Fin.ext rw [Fin.val_natAdd] dsimp [w] omega
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Fin.mk.injEq- Two elements of Fin n formed by Fin.mk are equal if and only if their numerical values are equal.
if_pos- An if-then-else expression reduces to its positive branch when the condition holds.
dif_neg- A dependent if-then-else expression reduces to its negative branch when the condition is refuted.
dif_pos- A dependent if-then-else expression reduces to its positive branch when the condition holds.
congrArg- Functions send equal inputs to equal outputs: if a = b then f(a) = f(b).
Fin.val_natAdd- The numerical value of Fin.natAdd n i equals n plus the numerical value of i.
Fin.val_castAdd- The numerical value of Fin.castAdd m i equals the numerical value of i.
- While mathematically this proof simply shifts fan colour indices at or above c by 1 to skip the deleted colour, Lean formalises colours as elements of finite types Fin n. Working with dependent subtypes requires explicit boundary arithmetic via omega, case splits on dependent conditionals (dif_pos, dif_neg), and congruence/extensionality lemmas relating Fin elements to their underlying natural numbers (Fin.ext, Fin.val_natAdd, Fin.val_castAdd).
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.
/-- Colour bijection from the a+b-1 colours surviving deletion of the fan colour c into the a+b colours, fixing the a diamond colours. -/theorem mdfrbf_colour_inj (a b : ℕ) (ha : 1 ≤ a) (hb : 2 ≤ b) (c : Fin b) : ∃ f : Fin (a + (b - 1)) → Fin (a + b), Function.Injective f ∧ (∀ v : Fin (a + b), v ≠ Fin.natAdd a c → ∃ u : Fin (a + (b - 1)), f u = v) ∧ (∀ col : Fin a, f (Fin.castAdd (b - 1) col) = Fin.castAdd b col) ∧ (∀ u : Fin (b - 1), ∃ col' : Fin b, f (Fin.natAdd a u) = Fin.natAdd a col') ∧ (∀ u : Fin (a + (b - 1)), f u ≠ Fin.natAdd a c) := by let g : Fin (b - 1) → Fin b := fun u => if h : u.val < c.val then ⟨u.val, by omega⟩ else ⟨u.val + 1, by have := u.isLt; omega⟩ let f : Fin (a + (b - 1)) → Fin (a + b) := fun v => if h : v.val < a then ⟨v.val, by omega⟩ else Fin.natAdd a (g ⟨v.val - a, by have := v.isLt; omega⟩) have g_inj : Function.Injective g := by intro u u' h apply Fin.ext dsimp [g] at h split_ifs at h with h1 h2 h1 h2 all_goals simp only [Fin.mk.injEq] at h ⊢ all_goals omega have g_ne : ∀ u : Fin (b - 1), (g u).val ≠ c.val := by intro u have g_val : (g u).val = if u.val < c.val then u.val else u.val + 1 := by dsimp [g] split_ifs <;> rfl rw [g_val] split_ifs with h · omega · omega have g_surj : ∀ w : Fin b, w.val ≠ c.val → ∃ u : Fin (b - 1), g u = w := by intro w hw by_cases hwlt : w.val < c.val · refine ⟨⟨w.val, by omega⟩, ?_⟩ dsimp [g] rw [if_pos hwlt] · have hle : c.val < w.val := by omega refine ⟨⟨w.val - 1, by have := w.isLt; omega⟩, ?_⟩ dsimp [g] have hnot : ¬ w.val - 1 < c.val := by omega rw [dif_neg hnot] apply Fin.ext simp omega have f_natAdd : ∀ u : Fin (b - 1), f (Fin.natAdd a u) = Fin.natAdd a (g u) := by intro u dsimp [f] rw [dif_neg (by omega)] congr 1 congr 1 apply Fin.ext simp have f_inj : Function.Injective f := by intro v v' h by_cases hv : v.val < a · by_cases hv' : v'.val < a · apply Fin.ext dsimp [f] at h rw [dif_pos hv, dif_pos hv'] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h simpa using hval · dsimp [f] at h rw [dif_pos hv, dif_neg hv'] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd] at hval have hval' : v.val = a + (g ⟨v'.val - a, by have := v'.isLt; omega⟩).val := by simpa using hval omega · by_cases hv' : v'.val < a · dsimp [f] at h rw [dif_neg hv, dif_pos hv'] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd] at hval have hval' : a + (g ⟨v.val - a, by have := v.isLt; omega⟩).val = v'.val := by simpa using hval omega · dsimp [f] at h rw [dif_neg hv, dif_neg hv'] at h have hg : g ⟨v.val - a, by have := v.isLt; omega⟩ = g ⟨v'.val - a, by have := v'.isLt; omega⟩ := by apply Fin.ext have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd, Fin.val_natAdd] at hval omega have hsub : v.val - a = v'.val - a := congrArg (fun x : Fin (b - 1) => x.val) (g_inj hg) apply Fin.ext omega have f_cast : ∀ col : Fin a, f (Fin.castAdd (b - 1) col) = Fin.castAdd b col := by intro col dsimp [f] have h : col.val < a := col.isLt rw [dif_pos h] apply Fin.ext simpa using (Fin.val_castAdd b col).symm have f_fan : ∀ u : Fin (b - 1), ∃ col' : Fin b, f (Fin.natAdd a u) = Fin.natAdd a col' := by intro u exact ⟨g u, f_natAdd u⟩ have f_ne : ∀ u : Fin (a + (b - 1)), f u ≠ Fin.natAdd a c := by intro u h by_cases hu : u.val < a · dsimp [f] at h rw [dif_pos hu] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd] at hval have hval' : u.val = a + c.val := by simpa using hval omega · let u0 : Fin (b - 1) := ⟨u.val - a, by have := u.isLt; omega⟩ have hu_eq : u = Fin.natAdd a u0 := by apply Fin.ext simp [u0] omega rw [hu_eq, f_natAdd] at h have hval := congrArg (fun x : Fin (a + b) => x.val) h rw [Fin.val_natAdd, Fin.val_natAdd] at hval exact g_ne u0 (by omega) refine ⟨f, f_inj, ?_, f_cast, f_fan, f_ne⟩ intro v hv by_cases hvlt : v.val < a · refine ⟨⟨v.val, by have := v.isLt; omega⟩, ?_⟩ dsimp [f] rw [dif_pos hvlt] · have hvge : a ≤ v.val := by omega let w : Fin b := ⟨v.val - a, by have := v.isLt; omega⟩ have hw_ne : w.val ≠ c.val := by intro hw apply hv apply Fin.ext rw [Fin.val_natAdd] dsimp [w] at hw omega obtain ⟨u0, hu0⟩ := g_surj w hw_ne refine ⟨Fin.natAdd a u0, ?_⟩ rw [f_natAdd, hu0] apply Fin.ext rw [Fin.val_natAdd] dsimp [w] omega