Positive terms, active-one certificates, and the finite family of short certificates
DefinitionNarrowDNF_CertificatesFor a finite coordinate set , a positive term indexed by holds at when every coordinate in 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 , let be its active union and define
The bundle represents as a finite set and calls 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 and natural cutoff , the truncated term family is exactly
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.
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