Lemma 5.81 with ¶5.82 — at most a tower of reduced hypotheticals over a bag
ProvedCoDecompFO.lemma_5_81co-decompositionsfirst-order-logicmodel-checkingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexity
Fix a signature , a formula with alternations, and a width . Over a bag of size , the set of -hypotheticals on is finite and has at most elements, where , and
At this is the printed tower with exponential layers, a function of and .
It bounds the work per node by a function of the parameters alone, which is the source of the running time.
Differences from the source:
- generalization: the bound h_ℓ at the top level ℓ → the bound at every level m, for any ℓ, with finiteness stated; reason: the printed bound is the case m = ℓ
- encoding: reduced hypotheticals (¶5.37), counted through "reduced families" → the set-level recursive type; reason: Prop. 5.38 identifies the two, and sets carry one entry per subset
Preamble
import Mathlib import Definitions.Def_CoDecompFO_HTh set_option autoImplicit false
Formal statement
namespace CoDecompFO
open FirstOrder
/-- **Lemma 5.81 with ¶5.82** (Bumpus et al., arXiv:2611.04658, held file sha256 d550d7af…, p.41): "For
fixed signature σ, formula φ, and width w, the number of reduced hypotheticals that can occur over a bag
of size at most w is bounded by a function of w and |φ|", explicitly `h_ℓ ≤ 2^{w 2^{w 2^{⋯ w 2^{w 2^{2^q}}}}}`
(`2ℓ+2` exponential layers), where `q := ∑_{R∈σ} (2ℓ)^{ar(R)}`.
**Formalization Note** The type of `m`-hypotheticals over a bag of `n ≤ w` points is finite, with at most
`tower w q m` elements, at every level `m`; `m = ℓ` is the printed bound. -/
theorem lemma_5_81 (σ : Sig) (n w ℓ m : ℕ) (hn : n ≤ w) :
Finite (HTh σ (Fin n) (2 * ℓ) m) ∧
Nat.card (HTh σ (Fin n) (2 * ℓ) m) ≤ tower w (∑ i, (2 * ℓ) ^ σ.ar i) m := by sorry
end CoDecompFO
Source
Bumpus, Gomes, Larios-Jones, Turner, Co-Decompositions and FO Model Checking, arXiv:2611.04658 (held file sha256 d550d7af…), Lemma 5.81, ¶5.82, p.41
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.