Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Positive terms, active-one certificates, and the finite family of short certificates

Definition
NarrowDNF_Certificates

by chenghua.liu · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsnarrow-dnf-authors-importprobabilitystoc-2027

For a finite coordinate set III, a positive term indexed by T⊆IT\subseteq IT⊆I holds at x∈{0,1}Ix\in\{0,1\}^Ix∈{0,1}I when every coordinate in TTT is one. A finite positive DNF holds when at least one of its terms holds. The empty conjunction is true and the empty disjunction is false.

For a local activation family JJJ, let AJ(x)A_J(x)AJ​(x) be its active union and define

TJ(x)={i∈AJ(x):xi=1}.T_J(x)=\{i\in A_J(x):x_i=1\}.TJ​(x)={i∈AJ​(x):xi​=1}.

The bundle represents AJ(x)A_J(x)AJ​(x) as a finite set and calls TJ(x)T_J(x)TJ​(x) the certificate. This name alone does not assert that it certifies acceptance; the appropriate monotonicity and adaptive-measurability hypotheses are used in later proofs of that property.

Given a Boolean readout uuu and natural cutoff www, the truncated term family is exactly

{TJ(x):u(x)=1, ∣TJ(x)∣≤w}.\{T_J(x):u(x)=1,\ |T_J(x)|\le w\}.{TJ​(x):u(x)=1, ∣TJ​(x)∣≤w}.

It is a finite image of qualifying accepted inputs, so repeated copies of the same term are removed. This constructs concrete positive DNFs for the final width approximation.

Definition code
import Mathlib.Data.Bool.Basic
import Mathlib.Data.Finset.Card
import Mathlib.Data.Finset.Image
import Mathlib.Data.Finset.Lattice.Fold
import Mathlib.Data.Fintype.Pi
import Mathlib.Order.Monotone.Basic
import Definitions.Def_NarrowDNF_Adaptive

namespace NarrowDNF
end NarrowDNF

namespace NarrowDNF.Activation
end NarrowDNF.Activation


namespace NarrowDNF

variable {ι : Type*} [Fintype ι] [DecidableEq ι]

/-- A positive conjunction, including the true empty conjunction. -/
def TermHolds (T : Finset ι) (x : Cube ι) : Prop := ∀ i ∈ T, x i = true

/-- A finite monotone DNF, including the false empty disjunction. -/
def DNFHolds (terms : Finset (Finset ι)) (x : Cube ι) : Prop :=
  ∃ T ∈ terms, TermHolds T x





namespace Activation

noncomputable def activeFinset (J : Activation ι) (x : Cube ι) : Finset ι :=
  by classical exact Finset.univ.filter fun i => i ∈ J.active x

noncomputable def certificate (J : Activation ι) (x : Cube ι) : Finset ι :=
  by classical exact (J.activeFinset x).filter fun i => x i = true











/-- Keep exactly the certificates of accepted inputs whose certificate has
cardinality at most the cutoff. This explicitly constructs a finite DNF. -/
noncomputable def truncatedTerms (J : Activation ι) (u : Cube ι → Bool)
    (w : ℕ) : Finset (Finset ι) :=
  by
    classical
    exact (Finset.univ.filter fun x => u x = true ∧ (J.certificate x).card ≤ w).image J.certificate









end Activation
end NarrowDNF
Source
https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Certificates.lean#L36-L37 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Certificates.lean#L9-L10 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Certificates.lean#L70-L76 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Certificates.lean#L12-L14 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Certificates.lean#L33-L34

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me