sweep_query_card
For all natural numbers M, N, r, and j with r + 1 < M and j < N, the cardinality of the sweep query satisfies (sweep_query M N r j).card = N + 1.
Statement
theorem sweep_query_card (M N : ℕ) (r j : ℕ) (hr : r + 1 < M) (hj : j < N) :
(sweep_query M N r j).card = N + 1- Source
- arXiv:2611.01281 Section 5
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- sweep_queryFor natural numbers M, N, r, and j,
sweep_query M N r jis the finite subset (Finset (Fin M × Fin N)) of vertices p in Fin M × Fin N… - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- sweep_queryFor natural numbers M, N, r, and j,
- Used by 1
- moving_target_grid_accuracy_le_minFor all M, N ≥ 1, on the M × N rectangular grid (vertices Fin M × Fin N, adjacent when they differ by one in exactly one coordinate) there…
Read back from the Lean
For all natural numbers $M$, $N$, $r$, and $j$, if $r + 1 < M$ and $j < N$, then the cardinality of sweep_query M N r j is equal to $N + 1$.
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
The sweep query is partitioned into two disjoint cylinder subsets of Fin M × Fin N: the set {r} × [j, N - 1] and the set {r + 1} × [0, j]. These two sets are disjoint because their first coordinates r and r + 1 are distinct. The total cardinality is therefore the sum of their sizes, 1 · (N - j) + 1 · (j + 1), which simplifies to N + 1.
Represent r and r + 1 as elements a, b ∈ Fin M, and j as an element c ∈ Fin N.
From the hypothesis r + 1 < M (hr), we obtain r < M by Nat.lt_of_succ_lt. This allows us to define the bounded indices a = r and b = r + 1 in Fin M. Similarly, j < N (hj) yields c = j in Fin N.
uses
Nat.lt_of_succ_lthave hrM : r < M := Nat.lt_of_succ_lt hr let a : Fin M := ⟨r, hrM⟩ let b : Fin M := ⟨r + 1, hr⟩ let c : Fin N := ⟨j, hj⟩
Decompose the sweep query into the union of two cylinder sets, ({a} × Ici c) ∪ ({b} × Iic c), and rewrite the goal with this decomposition.
By set extensionality, a pair p belongs to sweep_query M N r j if and only if it belongs to ({a} × Ici c) ∪ ({b} × Iic c). This is verified by expanding the definition of sweep_query alongside the membership criteria for products, unions, singletons, and intervals. Rewriting with this set equality transforms the query in the goal into the cardinality of this union.
uses
sweep_query,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_union,Finset.mem_product,Finset.mem_singleton,Finset.mem_Ici,Finset.mem_Iic,Fin.le_def,Fin.ext_iffhave hset : sweep_query M N r j = ({a} : Finset (Fin M)) ×ˢ (Finset.Ici c) ∪ ({b} : Finset (Fin M)) ×ˢ (Finset.Iic c) := by ext p simp only [sweep_query, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_product, Finset.mem_singleton, Finset.mem_Ici, Finset.mem_Iic, a, b, c, Fin.le_def, Fin.ext_iff] rw [hset]
The two cylinder sets {a} × Ici c and {b} × Iic c are disjoint.
Two Cartesian products are disjoint if their first components are disjoint. The first components are the singletons {a} and {b}, which are disjoint because their underlying natural values r and r + 1 are distinct.
uses
Finset.disjoint_product,Finset.disjoint_singletonhave hdisj : Disjoint (({a} : Finset (Fin M)) ×ˢ (Finset.Ici c)) (({b} : Finset (Fin M)) ×ˢ (Finset.Iic c)) := by rw [Finset.disjoint_product] left rw [Finset.disjoint_singleton] simp [a, b]
The cardinality of the union is N + 1.
Because the two cylinder sets are disjoint, the cardinality of their union is the sum of their individual sizes. Each cylinder is the product of a singleton (size 1) with an order interval in Fin N, having sizes |Ici c| = N - c and |Iic c| = c + 1 respectively. This reduces the total size to 1 * (N - c) + 1 * (c + 1), which simplifies to (N - c) + (c + 1) = N + 1 by linear arithmetic since c < N.
uses
Finset.card_union_of_disjoint,Finset.card_product,Finset.card_singleton,Fin.card_Ici,Fin.card_Iicrw [Finset.card_union_of_disjoint hdisj, Finset.card_product, Finset.card_product, Finset.card_singleton, Finset.card_singleton, Fin.card_Ici, Fin.card_Iic] simp omega
Nat.lt_of_succ_lt- If n + 1 < m, then n < m.
sweep_query- The finset of pairs (i, k) in Fin M × Fin N where either i = r and j ≤ k, or i = r + 1 and k ≤ j.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The conjunction True ∧ p is logically equivalent to p.
Finset.mem_union- An element belongs to the union of two finsets if and only if it belongs to the first or the second.
Finset.mem_product- An ordered pair belongs to a Cartesian product of two finsets if and only if its first component belongs to the first set and its second component to the second.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Finset.mem_Ici- An element x belongs to the weakly upper interval Ici a if and only if a ≤ x.
Finset.mem_Iic- An element x belongs to the weakly lower interval Iic a if and only if x ≤ a.
Fin.le_def- Inequality between two Fin elements is equivalent to the inequality between their underlying natural numbers.
Fin.ext_iff- Two Fin elements are equal if and only if their underlying natural numbers are equal.
Finset.disjoint_product- Two Cartesian products are disjoint if and only if their first projections or their second projections are disjoint.
Finset.disjoint_singleton- Two singletons {a} and {b} are disjoint if and only if a ≠ b.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finsets is the sum of their individual cardinalities.
Finset.card_product- The cardinality of the Cartesian product of two finsets is the product of their cardinalities.
Finset.card_singleton- The cardinality of any singleton finset is 1.
Fin.card_Ici- The cardinality of the interval Ici a in Fin n is n - a.
Fin.card_Iic- The cardinality of the interval Iic b in Fin n is b + 1.
- In the final step, simplifying (N - c) + (c + 1) to N + 1 uses truncated subtraction on ℕ, which requires the hypothesis c < N (hj) handled automatically by omega.
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 cardinality of the sweep query T_{r,j} is N + 1. -/theorem sweep_query_card (M N : ℕ) (r j : ℕ) (hr : r + 1 < M) (hj : j < N) : (sweep_query M N r j).card = N + 1 := by have hrM : r < M := Nat.lt_of_succ_lt hr let a : Fin M := ⟨r, hrM⟩ let b : Fin M := ⟨r + 1, hr⟩ let c : Fin N := ⟨j, hj⟩ have hset : sweep_query M N r j = ({a} : Finset (Fin M)) ×ˢ (Finset.Ici c) ∪ ({b} : Finset (Fin M)) ×ˢ (Finset.Iic c) := by ext p simp only [sweep_query, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_product, Finset.mem_singleton, Finset.mem_Ici, Finset.mem_Iic, a, b, c, Fin.le_def, Fin.ext_iff] rw [hset] have hdisj : Disjoint (({a} : Finset (Fin M)) ×ˢ (Finset.Ici c)) (({b} : Finset (Fin M)) ×ˢ (Finset.Iic c)) := by rw [Finset.disjoint_product] left rw [Finset.disjoint_singleton] simp [a, b] rw [Finset.card_union_of_disjoint hdisj, Finset.card_product, Finset.card_product, Finset.card_singleton, Finset.card_singleton, Fin.card_Ici, Fin.card_Iic] simp omega