AFTD Auto-Formalizing Theoretical Domains

op_258_forces_iff

theoremverified

For every decay profile a and k, "a forces a monochromatic K_k" holds if and only if the raw statement "for all sufficiently large n, every a-bounded colouring of K_n has a k-element vertex set all of whose edges share a colour" holds.

Statement

theorem op_258_forces_iff (a : ℕ+ → ℝ) (k : ℕ) :
    op_258_forces a k ↔ ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+,
      (∀ i : ℕ+, ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card ≤ a i * (n.choose 2 : ℝ)) →
      ∃ (s : Finset (Fin n)) (i : ℕ+), s.card = k ∧
        ∀ ⦃u v : Fin n⦄, u ∈ s → v ∈ s → (h : u ≠ v) →
          c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i
Source
step towards op_258_triangle_forcing_implies_decay_ramsey
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • op_258_boundedA colouring c of the edges of the complete graph K_n is a-bounded if for every colour i the number of edges of colour i is at most a i *…
  • op_258_has_mono_cliqueThe colouring c of the edges of K_n has a monochromatic K_k: there are a k-element vertex set s and a colour i such that every edge inside…
  • op_258_forcesThe decay profile a forces a monochromatic K_k if for all sufficiently large n, every a-bounded colouring of the edges of K_n has a…

The proof, explained

The predicate `op_258_forces a k` asserts that for all sufficiently large n, every a-bounded colouring of K_n contains a monochromatic k-clique. By unfolding the definitions of `op_258_forces`, `op_258_bounded`, and `op_258_has_mono_clique`, the left-hand side reduces definitionally to the expanded statement on the right-hand side. Within the statement, an inline simplification using `SimpleGraph.completeGraph_eq_top` confirms that any pair of distinct vertices in K_n spans an edge. The bi-implication is therefore an identity and is closed by reflexivity (`Iff.rfl`).

  1. The forcing predicate `op_258_forces a k` is definitionally equivalent to the explicit quantifier formula on the right-hand side.

    The forcing property `op_258_forces a k` is defined directly as the conjunction of the boundedness condition `op_258_bounded` and the monochromatic clique condition `op_258_has_mono_clique`. Expanding these definitions yields the exact formula on the right-hand side. Within that formula, the edge membership for two distinct vertices `u ≠ v` in the complete graph is settled by simplifying with `SimpleGraph.completeGraph_eq_top` and the inequality hypothesis `h : u ≠ v`. Because both sides of the bi-implication are definitionally identical, the equivalence holds by reflexivity (`Iff.rfl`).

    line 7

    uses SimpleGraph.completeGraph_eq_top, Iff.rfl

              c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i := Iff.rfl
SimpleGraph.completeGraph_eq_top
The complete graph on a vertex set V is the top element ⊤ of the graph lattice, meaning every pair of distinct vertices forms an edge.
Iff.rfl
Logical equivalence is reflexive: any proposition P is equivalent to itself (P ↔ P).

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

/-- The forcing predicate unfolds definitionally to the raw statement used in the target, so the two are interchangeable. -/theorem op_258_forces_iff (a : ℕ+ → ℝ) (k : ℕ) :    op_258_forces a k ↔ ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+,      (∀ i : ℕ+, ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card ≤ a i * (n.choose 2 : ℝ)) →      ∃ (s : Finset (Fin n)) (i : ℕ+), s.card = k ∧        ∀ ⦃u v : Fin n⦄, u ∈ s → v ∈ s → (h : u ≠ v) →          c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i := Iff.rfl
See it in the graphDiscuss this resultChallenge it