The bottom-up computation of hypothetical tables on a rooted tree co-decomposition
DefinitionCoDecompFO_FoldLet be a tree co-decomposition of -structures with bags , adhesions and maps . Fix a root , a number of variables and a level . The relation says that the -hypothetical over the bag is the table held at the node once the set of nodes has been absorbed. It is generated by two rules.
- Leaf. , where is the induced hypothetical of the full strategy on the bag .
- Join. Let be an edge from to a child of with . If and , then
where is the reduced pullback of hypotheticals over the adhesion, along and , and is the projection of hypotheticals along .
The table of the root is any with .
This is the recurrence by which the proof of Theorem 1.16 processes the co-decomposition from the leaves towards the root: one pullback and one projection per edge, starting from the induced hypotheticals on the bags. The rules use the bags, the adhesions and their maps only, so they describe what an algorithm that is not given the limit has to compute.
Formalization Note The table holds one hypothetical per node, the projection of the induced hypothetical of the full strategy, as in the corrected form of Observation 5.79 published as CoDecompFO.observation_5_79 (clauses (2) and (3)). The children of a node may be joined in any order.
import Mathlib
import Definitions.Def_CoDecompFO_HTh
import Definitions.Def_CoDecompFO_Lim
set_option autoImplicit false
namespace CoDecompFO
open FirstOrder
variable {σ : Sig}
/-- **The bottom-up computation** of the proof of Theorem 1.16 (Bumpus et al., *Co-Decompositions and FO
Model Checking*, arXiv:2611.04658, held file sha256 d550d7af…, p.41): "process the co-decomposition from
the leaves towards the root, maintaining at each node the reduced supported hypotheticals"; Observation
5.79 (p.41): "the supported hypotheticals at every node can be computed bottom-up using only projections,
the canonical comparison maps S[f]: f_*(S[G]) → f_*(S)[H], and pullbacks in the total category of
hypotheticals"; ¶5.80 (p.41): "at a leaf, supported hypotheticals are simply induced hypotheticals on the
bag".
`T.IsFold r k m t S H` says that `H`, a hypothetical over the bag of `t`, is the table obtained at the
node `t` after the nodes of `S` have been absorbed, in the tree rooted at `r`. A node alone has the
induced hypothetical of the full strategy on its bag (`leaf`). If `t` has the table `H` on `S`, and a
child `c` of `t` outside `S` has the table `Hc` on its whole subtree, then `t` has on `S` together with
that subtree the projection to the bag of `t` of the reduced pullback of `Hc` and `H` over the adhesion
of the edge (`join`). The table of the root on all nodes is `T.IsFold r k m r Set.univ H`.
**Formalization Note** The table holds one hypothetical per node, the projection of the full strategy's
induced hypothetical, as in the corrected form of Observation 5.79 (`observation_5_79`, clauses (2) and
(3)), and the canonical comparison maps are not needed. The children of a node may be joined in any
order. The definition refers to the bags, the adhesions and their maps only, not to the limit. -/
inductive CoDecomp.IsFold (T : CoDecomp σ) (r : Fin T.b) (k m : ℕ) :
(t : Fin T.b) → Set (Fin T.b) → HTh σ (Fin (T.bag t).n) k m → Prop
| leaf (t : Fin T.b) :
CoDecomp.IsFold T r k m t {t} (ind σ k m (Strat.full (Fin (T.bag t).n) m) [])
| join (t : Fin T.b) (S : Set (Fin T.b)) (e : Fin T.m) (he : T.IsChildEdge r t e)
(H : HTh σ (Fin (T.bag t).n) k m) (Hc : HTh σ (Fin (T.bag (T.child e t)).n) k m) :
CoDecomp.IsFold T r k m t S H → T.child e t ∉ S →
CoDecomp.IsFold T r k m (T.child e t) (T.subtree r (T.child e t)) Hc →
CoDecomp.IsFold T r k m t (S ∪ T.subtree r (T.child e t))
(push (Fib.snd :
Fib (T.edgeMap e (T.child e t) he.child_mem) (T.edgeMap e t he.top_mem) →
Fin (T.bag t).n) m
(pb (T.edgeMap e (T.child e t) he.child_mem) (T.edgeMap e t he.top_mem) m Hc H))
end CoDecompFO