not_finset_contains_trace_empty
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.
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 ∈ ∅.
rintro ⟨φ, hφ⟩
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).
obtain ⟨e, he⟩ := h𝓗 obtain ⟨A, hA, -⟩ := hφ e he
Contradiction. automation
The empty finset contains no members, so simplifying the hypothesis A ∈ ∅ reduces it to False and closes the goal.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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