Skip to main content

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;