AFTD Auto-Formalizing Theoretical Domains

op_1611_target_of_eight_and_three

theoremverified

If 8 satisfies the witness predicate and no Δ ≤ 3 does, then there is a unique Δ with 4 ≤ Δ ≤ 8 that is least in the set of witnesses.

Statement

theorem op_1611_target_of_eight_and_three (h8 : simple_graph_reconfiguration_diam_gt_matching 8) (h4 : ∀ Δ : ℕ, Δ ≤ 3 → ¬ simple_graph_reconfiguration_diam_gt_matching Δ) : ∃! Δ : ℕ, 4 ≤ Δ ∧ Δ ≤ 8 ∧ IsLeast {d : ℕ | simple_graph_reconfiguration_diam_gt_matching d} Δ
Source
step towards op_1611_min_max_degree_superlinear_matching_recoloring_diameter
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The hypothesis that 8 satisfies the reconfiguration property guarantees that the set of witnesses is non-empty, so by the well-ordering of the natural numbers it has a least element Δ. Since 8 is in the set, Δ ≤ 8, and because no Δ ≤ 3 is a witness, we must have 4 ≤ Δ. Uniqueness follows from the general fact that the least element of a partially ordered set is unique.

  1. The set of natural numbers satisfying the reconfiguration property is non-empty.

    Working in a classical setting where all predicates are decidable, hypothesis h8 shows that Δ = 8 satisfies the property, yielding an existential witness hne.

    lines 3–4

      classical
      have hne : ∃ d, simple_graph_reconfiguration_diam_gt_matching d := ⟨8, h8⟩
  2. The minimal witness Nat.find hne is the least element of the set of witnesses.

    By the well-ordering principle of the natural numbers via Nat.find, the candidate Nat.find hne satisfies the property by Nat.find_spec and is bounded above by any other witness by Nat.find_min'. Together, these show that it is a least element (IsLeast) of the witness set.

    lines 5–6

    uses Nat.find_spec, Nat.find_min'

      have hL : IsLeast {d : ℕ | simple_graph_reconfiguration_diam_gt_matching d} (Nat.find hne) :=
        ⟨Nat.find_spec hne, fun d hd => Nat.find_min' hne hd⟩
  3. Supplying Nat.find hne as the witness reduces the goal to proving the lower bound 4 ≤ Nat.find hne.

    We instantiate the unique existence goal with Δ = Nat.find hne. It satisfies Δ ≤ 8 by Nat.find_min' applied to 8 (h8), and it is a least element by hL. Uniqueness holds because any other witness y must also be a least element of the same set, and least elements in a partial order are unique. This leaves only the lower bound 4 ≤ Nat.find hne to show.

    line 7

    uses Nat.find_min'

      refine ⟨Nat.find hne, ⟨?_, Nat.find_min' hne h8, hL⟩, fun y hy => hy.2.2.unique hL⟩
  4. The minimal witness satisfies 4 ≤ Nat.find hne.

    We proceed by contradiction (by_contra h), assuming ¬(4 ≤ Nat.find hne). Linear arithmetic on ℕ (omega) simplifies this assumption to Nat.find hne ≤ 3. But hypothesis h4 states that no Δ ≤ 3 satisfies the property, which directly contradicts Nat.find_spec hne.

    lines 8–9

    uses Nat.find_spec

      by_contra h
      exact h4 _ (by omega) (Nat.find_spec hne)
Nat.find_spec
If there exists a natural number satisfying a predicate p, then Nat.find returns a natural number that satisfies p.
Nat.find_min'
The value Nat.find returns is less than or equal to any natural number that satisfies the predicate 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 uniqueness/existence target follows from P(8) together with the failure of P on all Δ ≤ 3. -/theorem op_1611_target_of_eight_and_three (h8 : simple_graph_reconfiguration_diam_gt_matching 8) (h4 : ∀ Δ : ℕ, Δ ≤ 3 → ¬ simple_graph_reconfiguration_diam_gt_matching Δ) : ∃! Δ : ℕ, 4 ≤ Δ ∧ Δ ≤ 8 ∧ IsLeast {d : ℕ | simple_graph_reconfiguration_diam_gt_matching d} Δ := by  classical  have hne : ∃ d, simple_graph_reconfiguration_diam_gt_matching d := ⟨8, h8⟩  have hL : IsLeast {d : ℕ | simple_graph_reconfiguration_diam_gt_matching d} (Nat.find hne) :=    ⟨Nat.find_spec hne, fun d hd => Nat.find_min' hne hd⟩  refine ⟨Nat.find hne, ⟨?_, Nat.find_min' hne h8, hL⟩, fun y hy => hy.2.2.unique hL⟩  by_contra h  exact h4 _ (by omega) (Nat.find_spec hne)
See it in the graphDiscuss this resultChallenge it