AFTD Auto-Formalizing Theoretical Domains

not_finset_contains_trace_empty

theoremverified

The empty set system contains no nonempty set system as a trace.

Statement

theorem not_finset_contains_trace_empty {α : Type*} [DecidableEq α] {h : ℕ}
    {𝓗 : Finset (Finset (Fin h))} (h𝓗 : 𝓗.Nonempty) :
    ¬ finset_contains_trace (∅ : Finset (Finset α)) 𝓗
Source
Sanity lemma for finset_contains_trace (arXiv:2610.08151 (Polynomial-in-r bounds for forbidden traces of uniform hypergraphs), Sec. 1.1).
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • finset_contains_traceA set system F contains the set system H on the ground set {0,…,h−1} as a trace if there is an injection φ of the ground set of H into…

The proof, explained

To show that the empty set system ∅ cannot contain any nonempty set system 𝓗 as a trace, we argue by contradiction. If ∅ contained 𝓗 as a trace, then every member of 𝓗 would be realized as the trace of some set in ∅. Since 𝓗 is nonempty, choosing any element of 𝓗 forces the existence of an element in ∅, which is impossible.

  1. Assume for contradiction that the empty family ∅ contains 𝓗 as a trace.

    To prove the negation, we assume for contradiction that ∅ contains 𝓗 as a trace. By the definition of finset_contains_trace, this gives an embedding φ : Fin h ↪ α such that every e ∈ 𝓗 is the trace of some member A ∈ ∅.

    line 4

      rintro ⟨φ, hφ⟩
  2. There exists a set A in the empty family ∅.

    Since 𝓗 is assumed to be nonempty, we can pick an element e ∈ 𝓗. Applying the trace condition to this e produces a set A ∈ ∅ whose intersection with the image of φ equals φ(e).

    lines 5–6

      obtain ⟨e, he⟩ := h𝓗
      obtain ⟨A, hA, -⟩ := hφ e he
  3. Contradiction. automation

    The empty finset contains no members, so simplifying the hypothesis A ∈ ∅ reduces it to False and closes the goal.

    line 7

      simp at hA

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

theorem not_finset_contains_trace_empty {α : Type*} [DecidableEq α] {h : ℕ}    {𝓗 : Finset (Finset (Fin h))} (h𝓗 : 𝓗.Nonempty) :    ¬ finset_contains_trace (∅ : Finset (Finset α)) 𝓗 := by  rintro ⟨φ, hφ⟩  obtain ⟨e, he⟩ := h𝓗  obtain ⟨A, hA, -⟩ := hφ e he  simp at hA
See it in the graphDiscuss this resultChallenge it