AFTD Auto-Formalizing Theoretical Domains

card_le_of_is_expandable

theoremverified

Every expandable set in a hypergraph with edge size bound r has cardinality at most r.

Statement

theorem card_le_of_is_expandable {V : Type*} {H : Finset (Finset V)} {r : ℕ} {X : Finset V} (hX : IsExpandable H r X) : X.card ≤ r
Source
arXiv:2611.16957, Section 3.1
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • IsExpandableA nonempty set X of vertices is expandable in a hypergraph H with edge size bound r if every edge of H has size at most r, and for every…
Used by 1

Read back from the Lean

For any type V, finite set of finite subsets H of V, natural number r, and finite subset X of V, if X is expandable with respect to H and r (IsExpandable H r X), then the cardinality of X is at most r.

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

By the definition of an expandable set, any set disjoint from X of size at most 2r avoids an edge containing X. Specializing this to the empty set yields an edge e ∈ H containing X. Since all hyperedges in H have cardinality at most r, the subset relation implies |X| ≤ |e| ≤ r.

  1. There exists a hyperedge e ∈ H containing X.

    By the definition of an expandable set, any set Y disjoint from X with |Y| ≤ 2r avoids some edge e ∈ H that contains X. Specializing this condition to Y = ∅, which is disjoint from X by Finset.disjoint_empty_left and has cardinality 0 ≤ 2r, yields an edge e ∈ H with X ⊆ e.

    line 3

    uses Finset.disjoint_empty_left

      obtain ⟨e, heH, hXe, -⟩ := hX.2.2 ∅ (Finset.disjoint_empty_left X) (by simp)
  2. |X| ≤ r

    Because X ⊆ e, Finset.card_le_card gives |X| ≤ |e|. The definition of expandability also specifies that every edge in H has cardinality at most r, so |e| ≤ r. Combining these inequalities with le_trans gives |X| ≤ r.

    line 4

    uses Finset.card_le_card, le_trans

      exact le_trans (Finset.card_le_card hXe) (hX.2.1 e heH)
Finset.disjoint_empty_left
The empty set is disjoint from any finite set.
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
le_trans
If a ≤ b and b ≤ c in a preorder, then a ≤ c.

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

/-- An expandable set in a hypergraph with edge size bound r has cardinality at most r. -/theorem card_le_of_is_expandable {V : Type*} {H : Finset (Finset V)} {r : ℕ} {X : Finset V} (hX : IsExpandable H r X) : X.card ≤ r := by  obtain ⟨e, heH, hXe, -⟩ := hX.2.2 ∅ (Finset.disjoint_empty_left X) (by simp)  exact le_trans (Finset.card_le_card hXe) (hX.2.1 e heH)
See it in the graphDiscuss this resultChallenge it