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;