sweep_candidate_bound_last
For all natural numbers M and N, the sweep candidate bound satisfies sweep_candidate_bound M N (M - 2) (N - 1) = ∅.
Statement
theorem sweep_candidate_bound_last (M N : ℕ) :
sweep_candidate_bound M N (M - 2) (N - 1) = ∅- Source
- arXiv:2611.01281 Section 5
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- sweep_candidate_boundFor natural numbers M, N, r, and j,
sweep_candidate_bound M N r jis the finite subset (Finset (Fin M × Fin N)) of vertices p in Fin M ×…
- sweep_candidate_boundFor natural numbers M, N, r, and j,
Read back from the Lean
For all natural numbers $M$ and $N$, $\mathrm{sweep\_candidate\_bound}(M, N, M - 2, N - 1)$ is the empty finset.
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
To show that the candidate set at the final sweep step $(M - 2, N - 1)$ is empty, we apply set extensionality: no index pair $p \in \mathrm{Fin}\, M \times \mathrm{Fin}\, N$ satisfies the candidate membership condition. Unfolding the definition reveals that any candidate would require either a column index $p.2 > N - 1$ on row $M - 1$ or a row index $p.1 \ge M$. Both conditions contradict the bounds $p.1 < M$ and $p.2 < N$ defining the finite grid, so linear arithmetic finishes the proof.
To show the candidate set is empty, it suffices to show that every index pair $p \in \mathrm{Fin}\, M \times \mathrm{Fin}\, N$ satisfies $(p.1 = M - 2 + 1 \implies p.2 \le N - 1)$ and $p.1 < M - 2 + 2$.
By extensionality (`ext p`), two sets are equal if they have the same members. The condition $p \in \emptyset$ is identically false, so expanding the definition of `sweep_candidate_bound` at step $(M - 2, N - 1)$ and simplifying the negation of its membership condition reduces the goal to requiring that neither $p.1 = M - 2 + 1 \land N - 1 < p.2$ nor $M - 2 + 2 \le p.1$ holds.
uses
sweep_candidate_boundext p simp [sweep_candidate_bound]
The candidate set is empty. automation
The required conditions follow by linear arithmetic on natural numbers (`omega`). Any element $p \in \mathrm{Fin}\, M \times \mathrm{Fin}\, N$ satisfies $p.1 < M$ and $p.2 < N$, which immediately implies $p.2 \le N - 1$, while $p.1 < M$ rules out $p.1 \ge M - 2 + 2$.
omega
sweep_candidate_bound- The finite set of pairs $p \in \mathrm{Fin}\, M \times \mathrm{Fin}\, N$ whose row and column indices satisfy $(p.1 = r + 1 \land j < p.2) \lor (r + 2 \le p.1)$.
- The `omega` tactic automatically extracts and uses the coordinate bounds $p.1 < M$ and $p.2 < N$ implicit in the type $p : \mathrm{Fin}\, M \times \mathrm{Fin}\, N$.
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 candidate set bound at the final sweep step (M-2, N-1) is empty. -/theorem sweep_candidate_bound_last (M N : ℕ) : sweep_candidate_bound M N (M - 2) (N - 1) = ∅ := by ext p simp [sweep_candidate_bound] omega