AFTD Auto-Formalizing Theoretical Domains

sweep_candidate_bound_last

theoremverified

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 j is the finite subset (Finset (Fin M × Fin N)) of vertices p in Fin M ×…

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.

  1. 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.

    lines 4–5

    uses sweep_candidate_bound

      ext p
      simp [sweep_candidate_bound]
  2. 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$.

    line 6

      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)$.

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 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
See it in the graphDiscuss this resultChallenge it