op_1611_target_of_eight_and_three
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
- op_1611_min_max_degree_le_eightThe natural number 8 satisfies simple_graph_reconfiguration_diam_gt_matching 8.
- simple_graph_reconfiguration_diam_gt_matchingThe predicate on a natural number Δ asserting that there exists a finite simple graph G on a finite type V with decidable equality and…
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.
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.
classical have hne : ∃ d, simple_graph_reconfiguration_diam_gt_matching d := ⟨8, h8⟩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.
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⟩
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.
uses
Nat.find_min'refine ⟨Nat.find hne, ⟨?_, Nat.find_min' hne h8, hL⟩, fun y hy => hy.2.2.unique hL⟩
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.
uses
Nat.find_specby_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
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.
/-- 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)