logicaffeine_proof/proof_rewrite.rs
1//! The **proof-rewrite 2-cells** — independent refutation steps commute, and the commutation squares
2//! make the space of proof-orderings a *contractible* `CAT(0)` cube complex. This is the honest higher
3//! structure the symmetry tower pointed at, and it is genuine 2-dimensional homotopy: not a faked `π₂`,
4//! but the **coherence theorem** for proofs — every way of reordering independent steps is coherently
5//! the same, up to all higher homotopies.
6//!
7//! ## The structure
8//!
9//! A refutation is a DAG: each step derives a clause from earlier ones. Steps with no dependency
10//! either way are **independent** — swapping two adjacent independent steps yields another valid
11//! refutation (checked here against the real PR checker, which is the oracle). The rewrites are the
12//! 1-cells; the **commutation squares** (two disjoint independent swaps done in either order reach the
13//! same ordering) are the **2-cells**.
14//!
15//! Model the executions as a cube complex: vertices = order ideals (the reachable "states"), edges =
16//! single steps, and a `k`-cube for every set of `k` pairwise-independent steps enabled at a state.
17//! Three facts, all checked:
18//!
19//! 1. **Connected** (`π₀ = 1`): any ordering is reachable from any other by commutation moves.
20//! 2. **The cube condition** (Gromov flagness): every pairwise-independent enabled set is jointly a
21//! cube — so the complex is `CAT(0)`, hence (Cartan–Hadamard) contractible.
22//! 3. **Euler characteristic `χ = 1`**: the contractibility invariant, computed cell by cell.
23//!
24//! ## Why this is the same mathematics as concurrency
25//!
26//! This *is* the Mazurkiewicz-trace / higher-dimensional-automata model: independent proof steps
27//! commute exactly as independent concurrent operations commute, and the contractible cube complex is
28//! the trace's domain. The homotopy theory of proofs and the homotopy theory of concurrent execution
29//! are one theory — the same 2-cells that certify "reordering independent proof steps doesn't matter"
30//! certify "interleaving independent concurrent ops is deterministic." The symmetry group still acts:
31//! `Aut(F)` permutes this contractible complex, and the homotopy quotient is again `K(Aut(F), 1)` — the
32//! recursion closes.
33
34use crate::cdcl::Lit;
35use crate::cubical::{Cube, CubicalComplex};
36
37/// A dependency poset on `n` proof steps. `prec[i][j]` means step `i` must come strictly before step
38/// `j` in any valid ordering (its transitive antecedent). Two steps are **independent** iff neither
39/// precedes the other — they commute. Small `n` only (`≤ 20`); it enumerates ideals and cubes, which
40/// is the point: it makes the coherence *visible and checkable*.
41pub struct ProofPoset {
42 pub n: usize,
43 prec: Vec<Vec<bool>>,
44}
45
46impl ProofPoset {
47 /// Build from direct dependency edges `(i, j)` = "`i` must precede `j`", then transitively close.
48 pub fn new(n: usize, edges: &[(usize, usize)]) -> Self {
49 let mut prec = vec![vec![false; n]; n];
50 for &(a, b) in edges {
51 prec[a][b] = true;
52 }
53 for k in 0..n {
54 for i in 0..n {
55 if prec[i][k] {
56 for j in 0..n {
57 if prec[k][j] {
58 prec[i][j] = true;
59 }
60 }
61 }
62 }
63 }
64 ProofPoset { n, prec }
65 }
66
67 pub fn precedes(&self, i: usize, j: usize) -> bool {
68 self.prec[i][j]
69 }
70
71 /// Neither step precedes the other: they commute, and that commutation is a 2-cell.
72 pub fn independent(&self, i: usize, j: usize) -> bool {
73 i != j && !self.prec[i][j] && !self.prec[j][i]
74 }
75
76 /// Is `mask` a down-closed set (order ideal)? — a reachable state of the execution.
77 fn is_ideal(&self, mask: u64) -> bool {
78 (0..self.n).all(|j| {
79 mask & (1 << j) == 0 || (0..self.n).all(|i| !self.prec[i][j] || mask & (1 << i) != 0)
80 })
81 }
82
83 /// All order ideals — the vertices of the cube complex.
84 pub fn ideals(&self) -> Vec<u64> {
85 (0..(1u64 << self.n))
86 .filter(|&m| self.is_ideal(m))
87 .collect()
88 }
89
90 /// The steps enabled at `ideal`: not yet taken, with every predecessor already taken.
91 pub fn enabled(&self, ideal: u64) -> Vec<usize> {
92 (0..self.n)
93 .filter(|&j| {
94 ideal & (1 << j) == 0
95 && (0..self.n).all(|i| !self.prec[i][j] || ideal & (1 << i) != 0)
96 })
97 .collect()
98 }
99
100 fn is_pairwise_independent(&self, s: &[usize]) -> bool {
101 (0..s.len()).all(|a| (a + 1..s.len()).all(|b| self.independent(s[a], s[b])))
102 }
103
104 /// `Σ_{S ⊆ items, S pairwise-independent} (-1)^{|S|}` — the local Euler contribution.
105 fn signed_independent_subsets(&self, items: &[usize]) -> i64 {
106 let k = items.len();
107 let mut total = 0i64;
108 for mask in 0u64..(1 << k) {
109 let subset: Vec<usize> = (0..k)
110 .filter(|&b| mask & (1 << b) != 0)
111 .map(|b| items[b])
112 .collect();
113 if self.is_pairwise_independent(&subset) {
114 total += if subset.len() % 2 == 0 { 1 } else { -1 };
115 }
116 }
117 total
118 }
119
120 /// Euler characteristic of the commutation cube complex: a `k`-cube for every state and every
121 /// pairwise-independent set of `k` steps enabled there. `χ = 1` ⟺ contractible (with the cube
122 /// condition below ruling out the alternatives).
123 pub fn euler_characteristic(&self) -> i64 {
124 self.ideals()
125 .iter()
126 .map(|&ideal| self.signed_independent_subsets(&self.enabled(ideal)))
127 .sum()
128 }
129
130 /// **Gromov's cube condition** (flagness): every pairwise-independent set of enabled steps is
131 /// *jointly* addable — the 1-skeleton of a cube is always filled to the solid cube. A simply
132 /// connected cube complex satisfying this is `CAT(0)`, hence contractible. For a commutation poset
133 /// it holds structurally; we check it as confirmation (and as a guard on `enabled`/`independent`).
134 pub fn satisfies_cube_condition(&self) -> bool {
135 self.ideals().iter().all(|&ideal| {
136 let en = self.enabled(ideal);
137 let k = en.len();
138 (0u64..(1 << k)).all(|mask| {
139 let subset: Vec<usize> = (0..k)
140 .filter(|&b| mask & (1 << b) != 0)
141 .map(|b| en[b])
142 .collect();
143 if !self.is_pairwise_independent(&subset) {
144 return true;
145 }
146 let mut m = ideal;
147 for &s in &subset {
148 m |= 1 << s;
149 }
150 self.is_ideal(m)
151 })
152 })
153 }
154
155 /// The **execution complex** of this commutation poset, as a [`CubicalComplex`]: states (order
156 /// ideals) are corners in `{0,1}ⁿ`, and at each state the enabled steps — which are automatically
157 /// pairwise independent — span a cube. This is the proof-rewrite complex of `proof_rewrite` handed
158 /// to the *same* general homology engine that produced `π₁, π₂, π₃` from concurrency, so the whole
159 /// ladder runs through one engine, from `π₀ =` symmetry breaking on up.
160 pub fn execution_complex(&self) -> CubicalComplex {
161 let top: Vec<Cube> = self
162 .ideals()
163 .into_iter()
164 .map(|ideal| {
165 let corner: Vec<usize> = (0..self.n).map(|s| ((ideal >> s) & 1) as usize).collect();
166 Cube {
167 corner,
168 dirs: self.enabled(ideal),
169 }
170 })
171 .collect();
172 CubicalComplex::from_top_cells(top)
173 }
174
175 /// All linear extensions (valid total orderings) of the poset.
176 pub fn linear_extensions(&self) -> Vec<Vec<usize>> {
177 let mut out = Vec::new();
178 self.le_rec(0, &mut Vec::new(), &mut out);
179 out
180 }
181
182 fn le_rec(&self, mask: u64, cur: &mut Vec<usize>, out: &mut Vec<Vec<usize>>) {
183 if cur.len() == self.n {
184 out.push(cur.clone());
185 return;
186 }
187 for j in self.enabled(mask) {
188 cur.push(j);
189 self.le_rec(mask | (1 << j), cur, out);
190 cur.pop();
191 }
192 }
193
194 /// The canonical (lexicographically-least) linear extension — the orbit representative under
195 /// commutation. This is **symmetry breaking applied to the orderings**: one schedule per trace, the
196 /// `π₀` representative, exactly as a lex-leader picks one assignment per symmetry orbit.
197 pub fn canonical_extension(&self) -> Vec<usize> {
198 let mut mask = 0u64;
199 let mut order = Vec::with_capacity(self.n);
200 while order.len() < self.n {
201 let next = *self
202 .enabled(mask)
203 .iter()
204 .min()
205 .expect("a finite poset always has an enabled step");
206 order.push(next);
207 mask |= 1 << next;
208 }
209 order
210 }
211
212 /// Does the step-relabeling `perm` (`perm[i]` = image of step `i`) preserve the whole order — both
213 /// precedence and commutation? Such a `perm` is a **cellular automorphism** of the cube complex: it
214 /// carries cubes to cubes and is exactly how a symmetry of `F` acts on the space of its proofs.
215 pub fn is_complex_automorphism(&self, perm: &[usize]) -> bool {
216 (0..self.n).all(|i| {
217 (0..self.n).all(|j| {
218 self.precedes(i, j) == self.precedes(perm[i], perm[j])
219 && self.independent(i, j) == self.independent(perm[i], perm[j])
220 })
221 })
222 }
223
224 fn relabel(&self, perm: &[usize], ext: &[usize]) -> Vec<usize> {
225 ext.iter().map(|&s| perm[s]).collect()
226 }
227
228 /// Does `perm` act **freely** on the linear extensions — fixing none? A free cellular action of a
229 /// group on a *contractible* complex has homotopy quotient `BG` (the Borel construction degenerates),
230 /// which is how symmetry-breaking the proof complex recovers a classifying space.
231 pub fn acts_freely_on_extensions(&self, perm: &[usize]) -> bool {
232 self.linear_extensions()
233 .iter()
234 .all(|e| self.relabel(perm, e) != *e)
235 }
236
237 /// Are all linear extensions connected by adjacent-independent commutation moves? (`π₀ = 1` of the
238 /// reordering graph — the coherence base: every ordering is reachable from every other.)
239 pub fn extensions_connected_by_commutation(&self) -> bool {
240 let exts = self.linear_extensions();
241 if exts.len() <= 1 {
242 return true;
243 }
244 let index: std::collections::HashMap<Vec<usize>, usize> = exts
245 .iter()
246 .cloned()
247 .enumerate()
248 .map(|(i, e)| (e, i))
249 .collect();
250 let mut seen = vec![false; exts.len()];
251 let mut stack = vec![0usize];
252 seen[0] = true;
253 let mut count = 1;
254 while let Some(u) = stack.pop() {
255 let e = exts[u].clone();
256 for p in 0..self.n.saturating_sub(1) {
257 if self.independent(e[p], e[p + 1]) {
258 let mut ne = e.clone();
259 ne.swap(p, p + 1);
260 let v = index[&ne];
261 if !seen[v] {
262 seen[v] = true;
263 count += 1;
264 stack.push(v);
265 }
266 }
267 }
268 }
269 count == exts.len()
270 }
271}
272
273/// Every permutation of `0..k` — the orderings to feed the real checker.
274pub fn permutations(k: usize) -> Vec<Vec<usize>> {
275 let mut out = Vec::new();
276 let mut cur: Vec<usize> = (0..k).collect();
277 fn rec(arr: &mut Vec<usize>, i: usize, out: &mut Vec<Vec<usize>>) {
278 if i == arr.len() {
279 out.push(arr.clone());
280 return;
281 }
282 for j in i..arr.len() {
283 arr.swap(i, j);
284 rec(arr, i + 1, out);
285 arr.swap(i, j);
286 }
287 }
288 rec(&mut cur, 0, &mut out);
289 out
290}
291
292/// Two var-disjoint contradictions: vars `{0,1}` and `{2,3}`, each an unsatisfiable 2-variable block.
293/// Its four RUP lemmas `(1), (¬1), (3), (¬3)` are derived from the originals alone — pairwise
294/// independent proof steps, the cleanest place to *see* the commutation 2-cells on a real refutation.
295pub fn disjoint_double_contradiction() -> (usize, Vec<Vec<Lit>>) {
296 let block = |x: u32, y: u32| {
297 vec![
298 vec![Lit::pos(x), Lit::pos(y)],
299 vec![Lit::neg(x), Lit::pos(y)],
300 vec![Lit::pos(x), Lit::neg(y)],
301 vec![Lit::neg(x), Lit::neg(y)],
302 ]
303 };
304 let mut f = block(0, 1);
305 f.extend(block(2, 3));
306 (4, f)
307}
308
309#[cfg(test)]
310#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/proof_rewrite/tests.rs"]
311mod tests;