AFTD Auto-Formalizing Theoretical Domains

mdfrbf_colour_inj

theoremverified

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

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.

  1. 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).

    lines 9–13

      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⟩)
  2. 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.

    lines 14–20

    uses Fin.ext, Fin.mk.injEq

      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
  3. 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.

    lines 21–29

      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
  4. 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.

    lines 30–43

    uses if_pos, dif_neg, Fin.ext

      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
  5. 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).

    lines 44–51

    uses dif_neg, Fin.ext

      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
  6. 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'.

    lines 52–87

    uses Fin.ext, dif_pos, dif_neg, congrArg, Fin.val_natAdd

      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
  7. 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.

    lines 88–94

    uses dif_pos, Fin.ext, Fin.val_castAdd

      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
  8. 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.

    lines 95–97

      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⟩
  9. 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.

    lines 98–116

    uses dif_pos, congrArg, Fin.val_natAdd, Fin.ext

      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)
  10. 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.

    lines 117–138

    uses dif_pos, Fin.ext, Fin.val_natAdd

      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
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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it