AFTD Auto-Formalizing Theoretical Domains

finset_restricted_family_empty

theoremverified

The restricted family of the empty family is empty.

Statement

theorem finset_restricted_family_empty {α : Type*} [DecidableEq α] (J U : Finset α) : finset_restricted_family (∅ : Finset (Finset α)) J U = ∅
Source
arXiv:2611.06860, Section 2.2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • finset_restricted_familyGiven a family of sets F and sets J and U, the restricted family F_{J,U} consists of all subsets A of J such that A ∪ U is in F.
  • oriented_overlap_multiplicity_budgetSummed multiplicities and charges cost at most three times overlap when multiplicity-two edges have at most one charge.
Used by 1

Read back from the Lean

For any type α with decidable equality and any two finite subsets J and U of α, the restricted family finset_restricted_family ∅ J U of the empty family ∅ (of finite subsets of α) is empty.

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 restricted family of a family ℱ with respect to J and U consists of all subsets A ⊆ J such that A ∪ U ∈ ℱ. When ℱ = ∅, the membership condition A ∪ U ∈ ∅ is false for every subset A. Unfolding the definition of finset_restricted_family and simplifying the resulting filtered power set immediately yields the empty set.

  1. The restricted family of the empty family is empty: finset_restricted_family ∅ J U = ∅. automation

    By definition, the restricted family finset_restricted_family ∅ J U is the collection of subsets A ⊆ J such that A ∪ U ∈ ∅. Since the empty set has no elements, the condition A ∪ U ∈ ∅ is false for every A, so filtering the power set of J produces the empty set ∅. The tactic unfolds the definition of finset_restricted_family and uses the simplifier (via simpa) to evaluate the membership predicate to false and close the equality, ignoring the unrelated lemma provided as an argument.

    line 2

    uses finset_restricted_family, oriented_overlap_multiplicity_budget

    theorem finset_restricted_family_empty {α : Type*} [DecidableEq α] (J U : Finset α) : finset_restricted_family (∅ : Finset (Finset α)) J U = ∅ := by first | exact oriented_overlap_multiplicity_budget | (apply oriented_overlap_multiplicity_budget <;> assumption) | (apply oriented_overlap_multiplicity_budget <;> simp_all) | simpa using oriented_overlap_multiplicity_budget | (simp only [finset_restricted_family] at *; first | exact oriented_overlap_multiplicity_budget | (apply oriented_overlap_multiplicity_budget <;> assumption) | (apply oriented_overlap_multiplicity_budget <;> simp_all) | simpa using oriented_overlap_multiplicity_budget)
finset_restricted_family
the sub-family of subsets A ⊆ J such that A ∪ U ∈ ℱ
oriented_overlap_multiplicity_budget
a combinatorial inequality bounding the sum of multiplicities and capacities over a finite set S

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 restricted family of the empty family is empty. -/theorem finset_restricted_family_empty {α : Type*} [DecidableEq α] (J U : Finset α) : finset_restricted_family (∅ : Finset (Finset α)) J U = ∅ := by first | exact oriented_overlap_multiplicity_budget | (apply oriented_overlap_multiplicity_budget <;> assumption) | (apply oriented_overlap_multiplicity_budget <;> simp_all) | simpa using oriented_overlap_multiplicity_budget | (simp only [finset_restricted_family] at *; first | exact oriented_overlap_multiplicity_budget | (apply oriented_overlap_multiplicity_budget <;> assumption) | (apply oriented_overlap_multiplicity_budget <;> simp_all) | simpa using oriented_overlap_multiplicity_budget)
See it in the graphDiscuss this resultChallenge it