finset_contains_trace_powerset_univ
The full power set of {0,…,h−1} contains every set system on {0,…,h−1} as a trace.
Statement
theorem finset_contains_trace_powerset_univ {h : ℕ} (𝓗 : Finset (Finset (Fin h))) :
finset_contains_trace (Finset.univ : Finset (Fin h)).powerset 𝓗- 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
A set system 𝓕 contains 𝓗 as a trace if some embedding of the ground set realizes every element of 𝓗 as an intersection with a member of 𝓕. Here both systems share the ground set {0, …, h - 1}, so we choose the identity embedding. Each e ∈ 𝓗 belongs to the full power set of the universe, and its intersection with the universe is e itself, satisfying the trace condition immediately.
To show that 𝓗 is a trace of the full power set, it suffices to check the trace condition using the identity embedding and taking each set in 𝓗 as its own witness.
By definition of `finset_contains_trace`, we must provide an embedding φ : Fin h ↪ Fin h and, for each e ∈ 𝓗, a set A in the power set of Finset.univ such that A ∩ φ(univ) = φ(e). We choose φ to be the identity embedding (`Function.Embedding.refl`), and for each e ∈ 𝓗, we choose A = e. The requirement that e belongs to the power set of Finset.univ holds trivially since every subset of Fin h is contained in the universal set, which is discharged inline by `simp`.
uses
Function.Embedding.reflrefine ⟨Function.Embedding.refl _, fun e _ => ⟨e, by simp, ?_⟩⟩
For each e ∈ 𝓗, the intersection e ∩ id(univ) equals id(e). automation
Because the embedding is the identity, the image of Finset.univ is Finset.univ and the image of e is e. The trace condition therefore simplifies to e ∩ Finset.univ = e, which is an identity for finite sets. The simplifier reduces both sides and closes the goal.
simp
Function.Embedding.refl- The identity embedding from a type to itself, sending every element to itself.
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_powerset_univ {h : ℕ} (𝓗 : Finset (Finset (Fin h))) : finset_contains_trace (Finset.univ : Finset (Fin h)).powerset 𝓗 := by refine ⟨Function.Embedding.refl _, fun e _ => ⟨e, by simp, ?_⟩⟩ simp