AFTD Auto-Formalizing Theoretical Domains

is_partial_transversal

def

Given a dimension δ : ℕ, an ambient finset of cells S in Fin δ × Fin δ, and a finset of cells T in Fin δ × Fin δ, is_partial_transversal S T asserts that T is a subset of S, and the coordinate projections from T to Fin δ are injective: for all p, q ∈ T, p.1 = q.1 implies p = q, and for all p, q ∈ T, p.2 = q.2 implies p = q.

Statement

def is_partial_transversal {δ : ℕ} (S : Finset (Fin δ × Fin δ)) (T : Finset (Fin δ × Fin δ)) : Prop
Defined in
arXiv:2611.13961, Section 2
Verified
12 Nov 2026
Axioms
none listed
Used by 2
  • is_max_partial_transversalGiven a dimension δ : ℕ, an ambient finset of cells S in Fin δ × Fin δ, and a finset of cells T in Fin δ × Fin δ,…
  • is_partial_transversal_emptyFor any dimension δ : ℕ and any finset of cells S in Fin δ × Fin δ, the empty finset ∅ is a partial transversal of S…

Read back from the Lean

For a natural number δ and finite sets S, T ⊆ Fin δ × Fin δ, is_partial_transversal S T asserts that T is a subset of S, no two elements of T share the same first component (for all p, q ∈ T, if p.1 = q.1 then p = q), and no two elements of T share the same second component (for all p, q ∈ T, if p.2 = q.2 then p = q).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A set of cells T is a partial transversal of S if T ⊆ S and no two cells share a row or column. -/
def is_partial_transversal {δ : ℕ} (S : Finset (Fin δ × Fin δ)) (T : Finset (Fin δ × Fin δ)) : Prop :=
  T ⊆ S ∧ (∀ p ∈ T, ∀ q ∈ T, p.1 = q.1 → p = q) ∧ (∀ p ∈ T, ∀ q ∈ T, p.2 = q.2 → p = q)
See it in the graphDiscuss this resultChallenge it