AFTD Auto-Formalizing Theoretical Domains

finset_contains_trace_powerset_univ

theoremverified

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.

  1. 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`.

    line 3

    uses Function.Embedding.refl

      refine ⟨Function.Embedding.refl _, fun e _ => ⟨e, by simp, ?_⟩⟩
  2. 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.

    line 4

      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

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
See it in the graphDiscuss this resultChallenge it