AFTD Auto-Formalizing Theoretical Domains

set_coloring_ramsey_number_mono_t

theoremverifiedformalization

For any simple graph G on a type V and natural numbers r, s, t, if there exists N such that set_coloring_ramsey_property G r s (t + 1) N holds, then set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1).

Statement

open scoped Classical in
theorem set_coloring_ramsey_number_mono_t
    {V : Type*} (G : SimpleGraph V) (r s t : ℕ)
    (h_ex : ∃ N, set_coloring_ramsey_property G r s (t + 1) N) :
    set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1)
Formalizes
arXiv:2611.15376 Section 7, Eq (37)
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • set_coloring_ramsey_numberGiven a type V, a simple graph G on V, and natural numbers r, s, t, set_coloring_ramsey_number G r s t is the infimum in ℕ of the set of…
  • set_coloring_ramsey_property_of_succFor any simple graph G on a type V and natural numbers r, s, t, N, if set_coloring_ramsey_property G r s (t + 1) N holds, then…
  • set_coloring_ramsey_propertyGiven a type V, a simple graph G on V, and natural numbers r, s, t, N, set_coloring_ramsey_property G r s t N asserts that for every…

Read back from the Lean

For any type $V$, any simple graph $G$ on $V$, and any natural numbers $r$, $s$, and $t$: if there exists a natural number $N$ satisfying set_coloring_ramsey_property G r s (t + 1) N, then set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The generalized set-coloring Ramsey number for parameters (r, s, t) is defined as the infimum of the set of graph orders N satisfying the corresponding Ramsey property. By assumption, the set of such orders for t + 1 is nonempty, so its infimum—the Ramsey number for t + 1—is attained and satisfies the property for t + 1. Because satisfying the Ramsey property for t + 1 implies satisfying it for t, this number also belongs to the set for t, and hence cannot be smaller than the infimum for t.

  1. The set-coloring Ramsey number for parameter t + 1 achieves the Ramsey property for t + 1.

    The assumption h_ex provides an order N satisfying the Ramsey property for t + 1, so the set of such orders is nonempty (h_ne). Since every nonempty set of natural numbers contains its infimum (by Nat.sInf_mem), the infimum of this set—which is the Ramsey number for parameter t + 1—itself satisfies the Ramsey property for t + 1.

    lines 7–8

    uses Nat.sInf_mem

      have h_ne : {N : ℕ | set_coloring_ramsey_property G r s (t + 1) N}.Nonempty := h_ex
      have h_mem := Nat.sInf_mem h_ne
  2. The Ramsey number for parameter t + 1 also satisfies the Ramsey property for parameter t.

    By set_coloring_ramsey_property_of_succ, any order N that satisfies the set-coloring Ramsey property for parameter t + 1 also satisfies the property for parameter t. Therefore, the Ramsey number for t + 1 belongs to the set of orders satisfying the property for t.

    lines 9–10

    uses set_coloring_ramsey_property_of_succ

      have h_sub : set_coloring_ramsey_number G r s (t + 1) ∈ {N : ℕ | set_coloring_ramsey_property G r s t N} :=
        set_coloring_ramsey_property_of_succ G r s t _ h_mem
  3. set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1)

    By definition, the Ramsey number for parameter t is the infimum of the set of orders satisfying the property for t. Since the Ramsey number for t + 1 belongs to this set, Nat.sInf_le implies that the infimum is less than or equal to it.

    line 11

    uses Nat.sInf_le

      exact Nat.sInf_le h_sub
Nat.sInf_mem
Every nonempty set of natural numbers contains its infimum (that is, its minimum element).
set_coloring_ramsey_property_of_succ
If the generalized set-coloring Ramsey property holds for parameter t + 1 on a graph of order N, then it also holds for parameter t on the same order N.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element belonging to the set.

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

open scoped Classical in/-- Weak monotonicity of the generalized set-coloring Ramsey number in the intersection parameter t (the intersection spectrum inequality). -/theorem set_coloring_ramsey_number_mono_t    {V : Type*} (G : SimpleGraph V) (r s t : ℕ)    (h_ex : ∃ N, set_coloring_ramsey_property G r s (t + 1) N) :    set_coloring_ramsey_number G r s t ≤ set_coloring_ramsey_number G r s (t + 1) := by  have h_ne : {N : ℕ | set_coloring_ramsey_property G r s (t + 1) N}.Nonempty := h_ex  have h_mem := Nat.sInf_mem h_ne  have h_sub : set_coloring_ramsey_number G r s (t + 1) ∈ {N : ℕ | set_coloring_ramsey_property G r s t N} :=    set_coloring_ramsey_property_of_succ G r s t _ h_mem  exact Nat.sInf_le h_sub
See it in the graphDiscuss this resultChallenge it