finset_contains_trace_of_subset
Containing H as a trace is monotone: if F ⊆ F' and F contains H as a trace, so does F'.
Statement
theorem finset_contains_trace_of_subset {α : Type*} [DecidableEq α] {h : ℕ} {𝓕 𝓕' : Finset (Finset α)} {𝓗 : Finset (Finset (Fin h))} (hsub : 𝓕 ⊆ 𝓕') (hc : finset_contains_trace 𝓕 𝓗) : finset_contains_trace 𝓕' 𝓗
- 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 containing 𝓗 as a trace is monotone under inclusion, we reuse the embedding φ : Fin h ↪ α that witnesses 𝓗 being a trace of 𝓕. Every element e ∈ 𝓗 is realized by some set A ∈ 𝓕. Since 𝓕 ⊆ 𝓕', that same set A belongs to 𝓕', thereby witnessing the trace condition for 𝓕'.
To show that 𝓕' contains 𝓗 as a trace, it suffices to test an arbitrary e ∈ 𝓗 using the same embedding φ that witnesses the trace for 𝓕.
Unpacking the assumption that 𝓕 contains 𝓗 as a trace provides an embedding φ : Fin h ↪ α such that every element of 𝓗 is induced by some set in 𝓕. We use this same φ as the witness for 𝓕', which reduces the goal to finding, for any given e ∈ 𝓗, a set in 𝓕' whose trace under φ is φ(e).
obtain ⟨φ, hφ⟩ := hc refine ⟨φ, fun e he => ?_⟩
Every element e ∈ 𝓗 is realized by a set in 𝓕'.
Applying the trace property of 𝓕 to e yields a set A ∈ 𝓕 such that A ∩ φ(univ) = φ(e). Since 𝓕 ⊆ 𝓕', this set A is also a member of 𝓕', thus serving as the required witness.
obtain ⟨A, hA, hAe⟩ := hφ e he exact ⟨A, hsub hA, hAe⟩
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 finset_contains_trace_of_subset {α : Type*} [DecidableEq α] {h : ℕ} {𝓕 𝓕' : Finset (Finset α)} {𝓗 : Finset (Finset (Fin h))} (hsub : 𝓕 ⊆ 𝓕') (hc : finset_contains_trace 𝓕 𝓗) : finset_contains_trace 𝓕' 𝓗 := by obtain ⟨φ, hφ⟩ := hc refine ⟨φ, fun e he => ?_⟩ obtain ⟨A, hA, hAe⟩ := hφ e he exact ⟨A, hsub hA, hAe⟩