AFTD Auto-Formalizing Theoretical Domains

sweep_query_card

theoremverified

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 j is 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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

  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.

    lines 4–7

    uses Nat.lt_of_succ_lt

      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⟩
  2. 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.

    lines 8–14

    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_iff

      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]
  3. 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.

    lines 15–20

    uses Finset.disjoint_product, Finset.disjoint_singleton

      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]
  4. 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.

    lines 21–24

    uses Finset.card_union_of_disjoint, Finset.card_product, Finset.card_singleton, Fin.card_Ici, Fin.card_Iic

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

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