AFTD Auto-Formalizing Theoretical Domains

is_partial_transversal_empty

theoremverified

For any dimension δ : ℕ and any finset of cells S in Fin δ × Fin δ, the empty finset ∅ is a partial transversal of S (is_partial_transversal S ∅).

Statement

theorem is_partial_transversal_empty {δ : ℕ} (S : Finset (Fin δ × Fin δ)) : is_partial_transversal S ∅
Source
folklore
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_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 S…
  • in715_deficit_private_tipFinite certificate for the explicit fourteen-vertex graph.

Read back from the Lean

For any natural number δ and any finite subset S of Fin δ × Fin δ, the empty set ∅ is a partial transversal of S.

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 empty set ∅ is a partial transversal of any cell set S, we unfold the definition of a partial transversal. This requires verifying that ∅ is a subset of S and that no two elements in ∅ share a row or column. Both requirements hold vacuously because ∅ contains no elements, so simplification immediately closes the goal.

  1. The empty set ∅ is a partial transversal of S. automation

    Unfolding the definition of a partial transversal (`is_partial_transversal`), the goal becomes showing that ∅ ⊆ S and that no two distinct elements in ∅ share a row or a column. The simplifier (`simpa`) closes this automatically: the empty set is trivially a subset of S, and the conditions on pairs of elements in ∅ are vacuously satisfied since ∅ contains no elements.

    line 2

    uses is_partial_transversal, in715_deficit_private_tip

    theorem is_partial_transversal_empty {δ : ℕ} (S : Finset (Fin δ × Fin δ)) : is_partial_transversal S ∅ := by first | exact in715_deficit_private_tip | (apply in715_deficit_private_tip <;> assumption) | (apply in715_deficit_private_tip <;> simp_all) | simpa using in715_deficit_private_tip | (simp only [is_partial_transversal] at *; first | exact in715_deficit_private_tip | (apply in715_deficit_private_tip <;> assumption) | (apply in715_deficit_private_tip <;> simp_all) | simpa using in715_deficit_private_tip)
is_partial_transversal
A set of cells T is a partial transversal of S if T ⊆ S and no two distinct cells in T share their first or second coordinate.
in715_deficit_private_tip
An unrelated lemma stating that {0, 4, 9} is in P and is the unique set in P containing 9.

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 empty set is a partial transversal of any set of cells. -/theorem is_partial_transversal_empty {δ : ℕ} (S : Finset (Fin δ × Fin δ)) : is_partial_transversal S ∅ := by first | exact in715_deficit_private_tip | (apply in715_deficit_private_tip <;> assumption) | (apply in715_deficit_private_tip <;> simp_all) | simpa using in715_deficit_private_tip | (simp only [is_partial_transversal] at *; first | exact in715_deficit_private_tip | (apply in715_deficit_private_tip <;> assumption) | (apply in715_deficit_private_tip <;> simp_all) | simpa using in715_deficit_private_tip)
See it in the graphDiscuss this resultChallenge it