Skip to main content

logicaffeine_proof/
coalgebra.rs

1//! The **coalgebraic / `Poly` view**, made into checked code rather than narration.
2//!
3//! A certified refutation is a *discrete dynamical system* — a coalgebra `S → p(S)` for a polynomial
4//! functor `p` (positions = states, directions = the certified moves available there), exactly
5//! Spivak's model of dynamical systems in `Poly`. A Lyapunov measure is then a **coalgebra morphism
6//! to the countdown coalgebra** `(ℕ, n ↦ n-1)` — the canonical well-founded object: it intertwines
7//! the system's dynamics with the countdown's, i.e. every transition strictly decreases it.
8//!
9//! The load-bearing theorem (Taylor; Adámek–Milius–Moss on *well-founded coalgebras*): **a finite
10//! system is well-founded (terminating — no infinite forward trajectory) iff it admits a morphism to
11//! a well-founded object.** That equivalence *is* the synthesis–impossibility duality at the
12//! categorical level: a collapsing measure is a countdown morphism, and its non-existence is the
13//! presence of a cycle. We make both directions constructive and machine-checked here, and connect
14//! it back: every Lyapunov trajectory this crate produces is a countdown morphism on its path system.
15
16/// A finite transition system: a coalgebra `S → 𝒫(S)` for the finite-powerset polynomial functor.
17/// `successors[s]` lists the states reachable from `s` in one step.
18#[derive(Clone, Debug)]
19pub struct TransitionSystem {
20    pub n_states: usize,
21    pub successors: Vec<Vec<usize>>,
22}
23
24impl TransitionSystem {
25    /// A linear "path" system `0 → 1 → … → n-1` — the shape of a (deterministic) proof trajectory.
26    pub fn path(n: usize) -> TransitionSystem {
27        TransitionSystem {
28            n_states: n,
29            successors: (0..n)
30                .map(|s| if s + 1 < n { vec![s + 1] } else { vec![] })
31                .collect(),
32        }
33    }
34}
35
36/// Is `measure` a **coalgebra morphism to the countdown coalgebra**? Every transition `s → t` must
37/// strictly decrease it (`measure[t] < measure[s]`) — the morphism square commuting with `n ↦ n-1`.
38/// Because the countdown is well-founded, a `true` here *witnesses* that the system is well-founded.
39pub fn is_countdown_morphism(system: &TransitionSystem, measure: &[u64]) -> bool {
40    if measure.len() != system.n_states {
41        return false;
42    }
43    system.successors.iter().enumerate().all(|(s, succ)| {
44        succ.iter()
45            .all(|&t| t < measure.len() && measure[t] < measure[s])
46    })
47}
48
49/// Is the system **well-founded** (acyclic — no infinite forward trajectory)? Equivalent, for a
50/// finite system, to "is a DAG". Computed by Kahn's algorithm: a full topological order exists iff
51/// there is no cycle.
52pub fn is_well_founded(system: &TransitionSystem) -> bool {
53    let n = system.n_states;
54    let mut indeg = vec![0usize; n];
55    for succ in &system.successors {
56        for &t in succ {
57            if t < n {
58                indeg[t] += 1;
59            }
60        }
61    }
62    let mut queue: Vec<usize> = (0..n).filter(|&s| indeg[s] == 0).collect();
63    let mut seen = 0;
64    let mut qi = 0;
65    while qi < queue.len() {
66        let s = queue[qi];
67        qi += 1;
68        seen += 1;
69        for &t in &system.successors[s] {
70            if t < n {
71                indeg[t] -= 1;
72                if indeg[t] == 0 {
73                    queue.push(t);
74                }
75            }
76        }
77    }
78    seen == n // all states ordered ⇒ no cycle ⇒ well-founded
79}
80
81/// The **canonical countdown morphism** of a well-founded system: the longest forward path from each
82/// state (sinks = 0). This is the *terminal* such morphism — the existence half of the theorem made
83/// constructive. Returns `None` if the system is not well-founded (no morphism exists).
84pub fn canonical_countdown_morphism(system: &TransitionSystem) -> Option<Vec<u64>> {
85    if !is_well_founded(system) {
86        return None;
87    }
88    let n = system.n_states;
89    let mut rank = vec![0u64; n];
90    let mut done = vec![false; n];
91    // Memoised longest-path via an explicit stack (the system is a DAG, so this terminates).
92    for start in 0..n {
93        if done[start] {
94            continue;
95        }
96        let mut stack = vec![start];
97        while let Some(&s) = stack.last() {
98            let pending: Option<usize> = system.successors[s]
99                .iter()
100                .copied()
101                .find(|&t| t < n && !done[t]);
102            match pending {
103                Some(t) => stack.push(t),
104                None => {
105                    let r = system.successors[s]
106                        .iter()
107                        .filter(|&&t| t < n)
108                        .map(|&t| rank[t] + 1)
109                        .max()
110                        .unwrap_or(0);
111                    rank[s] = r;
112                    done[s] = true;
113                    stack.pop();
114                }
115            }
116        }
117    }
118    Some(rank)
119}
120
121#[cfg(test)]
122#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/coalgebra/tests.rs"]
123mod tests;