AFTD Auto-Formalizing Theoretical Domains

op_639_fiber_full_card_le_one

theoremverified

In a 4-uniform hypergraph, if T has size 4, any edge satisfying e ∩ T = T must equal T, so there is at most 1 such edge.

Statement

theorem op_639_fiber_full_card_le_one
    {V : Type*} [DecidableEq V] (F : Finset (Finset V))
    (hunif : ∀ e ∈ F, e.card = 4)
    (T : Finset V) (hT : T.card = 4) :
    (F.filter (fun e => e ∩ T = T)).card ≤ 1
Source
step towards op_639_intersecting_four_uniform_covering_four_card_le_forty_two
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To show that at most one edge e ∈ F satisfies e ∩ T = T, it suffices to show that any two such edges e and f are identical. Because e ∩ T = T implies T ⊆ e, and both e and T have cardinality 4, any such edge must equal T itself. Since both e and f equal T, they must be equal to each other.

  1. To show the filtered set has cardinality at most 1, it suffices to prove that any two edges e, f ∈ F with e ∩ T = T and f ∩ T = T are equal.

    By Finset.card_le_one_iff, a finite set has size at most 1 if and only if any two of its elements are identical. Applying Finset.mem_filter to the membership hypotheses for two elements e and f in the filtered set yields that e, f ∈ F, e ∩ T = T, and f ∩ T = T.

    lines 7–9

    uses Finset.card_le_one_iff, Finset.mem_filter

      rw [Finset.card_le_one_iff]
      intro e f he hf
      simp only [Finset.mem_filter] at he hf
  2. The edge e must equal T.

    The condition e ∩ T = T means T ⊆ e by Finset.inter_eq_right. Since F is 4-uniform and T has cardinality 4, we have |e| = 4 and |T| = 4, so |e| ≤ |T|. Because T ⊆ e and |e| ≤ |T|, Finset.eq_of_subset_of_card_le implies T = e, hence e = T.

    lines 10–14

    uses Finset.inter_eq_right, Finset.eq_of_subset_of_card_le

      have hTe : T ⊆ e := by
        rw [← Finset.inter_eq_right]
        exact he.2
      have he_card : e.card ≤ T.card := by rw [hunif e he.1, hT]
      have heT : e = T := (Finset.eq_of_subset_of_card_le hTe he_card).symm
  3. The edge f must equal T.

    By the exact same reasoning, f ∩ T = T gives T ⊆ f via Finset.inter_eq_right. Because |f| = 4 ≤ |T|, Finset.eq_of_subset_of_card_le implies T = f, so f = T.

    lines 15–19

    uses Finset.inter_eq_right, Finset.eq_of_subset_of_card_le

      have hTf : T ⊆ f := by
        rw [← Finset.inter_eq_right]
        exact hf.2
      have hf_card : f.card ≤ T.card := by rw [hunif f hf.1, hT]
      have hfT : f = T := (Finset.eq_of_subset_of_card_le hTf hf_card).symm
  4. The edges e and f are equal, which completes the proof.

    Since both e = T and f = T, substituting T for both e and f immediately gives e = f.

    line 20

      rw [heT, hfT]
Finset.card_le_one_iff
A finite set has at most one element if and only if any two elements in it are equal.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.inter_eq_right
The intersection of two sets equals the second set if and only if the second set is a subset of the first.
Finset.eq_of_subset_of_card_le
If a finite set s is a subset of t and the cardinality of t is at most the cardinality of s, then s = t.

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

/-- At most one edge of a 4-uniform family can satisfy e ∩ T = T for a 4-element transversal T. -/theorem op_639_fiber_full_card_le_one    {V : Type*} [DecidableEq V] (F : Finset (Finset V))    (hunif : ∀ e ∈ F, e.card = 4)    (T : Finset V) (hT : T.card = 4) :    (F.filter (fun e => e ∩ T = T)).card ≤ 1 := by  rw [Finset.card_le_one_iff]  intro e f he hf  simp only [Finset.mem_filter] at he hf  have hTe : T ⊆ e := by    rw [← Finset.inter_eq_right]    exact he.2  have he_card : e.card ≤ T.card := by rw [hunif e he.1, hT]  have heT : e = T := (Finset.eq_of_subset_of_card_le hTe he_card).symm  have hTf : T ⊆ f := by    rw [← Finset.inter_eq_right]    exact hf.2  have hf_card : f.card ≤ T.card := by rw [hunif f hf.1, hT]  have hfT : f = T := (Finset.eq_of_subset_of_card_le hTf hf_card).symm  rw [heT, hfT]
See it in the graphDiscuss this resultChallenge it