logicaffeine_proof/omega_solve.rs
1//! `omega` — linear INTEGER arithmetic, the discreteness-aware layer over the
2//! rational Farkas core.
3//!
4//! Rational Fourier-Motzkin ([`crate::linarith_solve`]) decides satisfiability
5//! over ℚ; it is sound for ℤ but INCOMPLETE, because it cannot use the one fact
6//! that distinguishes the integers: a strict `a < b` is a non-strict `a+1 ≤ b`,
7//! since nothing lives strictly between consecutive integers. The classic
8//! witness is `x < y ∧ y < x+1` — rationally satisfiable (`x=0, y=½`), integer
9//! UNSAT.
10//!
11//! This module supplies exactly that missing step. It rewrites every strict
12//! hypothesis `a < b` to `a+1 ≤ b` through the kernel axiom `lt_succ_le` (a
13//! certified [`InferenceRule::LtSuccLe`] node), then hands the enlarged set of
14//! `≤`-facts to the existing Farkas refutation (`crate::engine::cert_farkas`).
15//! The result is one kernel-checked `⊥` derivation, so `omega` is exactly as
16//! trusted as `linarith` — it just sees more contradictions.
17
18use crate::engine::{as_le_pair, cert_farkas, le_eq};
19use crate::{DerivationTree, InferenceRule, ProofExpr, ProofTerm};
20
21/// The strict inequality `a < b`, encoded as the Prop `lt(a, b) = true`.
22pub(crate) fn lt_eq(a: ProofTerm, b: ProofTerm) -> ProofExpr {
23 ProofExpr::Identity(
24 ProofTerm::Function("lt".to_string(), vec![a, b]),
25 ProofTerm::Constant("true".to_string()),
26 )
27}
28
29/// If `e` is a strict inequality `lt(a, b) = true`, return `(a, b)`.
30pub(crate) fn as_lt_pair(e: &ProofExpr) -> Option<(ProofTerm, ProofTerm)> {
31 if let ProofExpr::Identity(lhs, rhs) = e {
32 if let (ProofTerm::Function(name, args), ProofTerm::Constant(t)) = (lhs, rhs) {
33 if name == "lt" && args.len() == 2 && t == "true" {
34 return Some((args[0].clone(), args[1].clone()));
35 }
36 }
37 }
38 None
39}
40
41/// `a + 1` as a proof term.
42pub(crate) fn succ(a: &ProofTerm) -> ProofTerm {
43 ProofTerm::Function(
44 "add".to_string(),
45 vec![a.clone(), ProofTerm::Constant("1".to_string())],
46 )
47}
48
49/// If `t` is `add(b, 1)`, return `b` — the shape `lt_add1_le` cancels.
50fn as_succ(t: &ProofTerm) -> Option<ProofTerm> {
51 if let ProofTerm::Function(name, args) = t {
52 if name == "add" && args.len() == 2 && args[1] == ProofTerm::Constant("1".to_string()) {
53 return Some(args[0].clone());
54 }
55 }
56 None
57}
58
59/// Rewrite a known fact to an equivalent (or stronger) `≤`-fact for the Farkas
60/// core. A `≤`-fact passes through. A strict `a < b` becomes `≤` via integer
61/// discreteness: when the bound is already `b′+1` we cancel it to the clean
62/// `a ≤ b′` (`lt_add1_le`), keeping the reconstructed terms small; otherwise it
63/// tightens to `a+1 ≤ b` (`lt_succ_le`). Anything else is dropped.
64pub(crate) fn to_le_fact(
65 prop: &ProofExpr,
66 proof: &DerivationTree,
67) -> Option<(ProofExpr, DerivationTree)> {
68 if as_le_pair(prop).is_some() {
69 return Some((prop.clone(), proof.clone()));
70 }
71 if let Some((a, b)) = as_lt_pair(prop) {
72 if let Some(b_inner) = as_succ(&b) {
73 // a < b′ + 1 ⊢ a ≤ b′
74 let concl = le_eq(a, b_inner);
75 let tree =
76 DerivationTree::new(concl.clone(), InferenceRule::LtAdd1Le, vec![proof.clone()]);
77 return Some((concl, tree));
78 }
79 // a < b ⊢ a + 1 ≤ b
80 let concl = le_eq(succ(&a), b);
81 let tree = DerivationTree::new(concl.clone(), InferenceRule::LtSuccLe, vec![proof.clone()]);
82 return Some((concl, tree));
83 }
84 None
85}
86
87/// Refute a set of integer hypotheses (`≤` and strict `<`), returning a
88/// kernel-checked `⊥` derivation when they are jointly unsatisfiable over ℤ.
89///
90/// Strictly stronger than [`cert_farkas`]: it first discreteness-tightens every
91/// strict hypothesis, so it catches contradictions the rational core misses.
92/// Returns `None` when the (tightened) system is rationally satisfiable — i.e.
93/// genuinely has an integer model on the fragment covered here.
94pub(crate) fn omega_close(known: &[(ProofExpr, DerivationTree)]) -> Option<DerivationTree> {
95 let le_facts: Vec<(ProofExpr, DerivationTree)> =
96 known.iter().filter_map(|(p, t)| to_le_fact(p, t)).collect();
97 // Only worth the extra pass if at least one strict fact was tightened;
98 // otherwise the caller's own `cert_farkas` already tried this exact set.
99 let tightened = known.iter().any(|(p, _)| as_lt_pair(p).is_some());
100 if !tightened {
101 return None;
102 }
103 cert_farkas(&le_facts)
104}
105
106/// Does `omega_close` see hypotheses at all — any `≤`/`<` fact? Used by the
107/// tactic to give a precise "not an arithmetic goal" error.
108pub(crate) fn has_arith_facts(known: &[(ProofExpr, DerivationTree)]) -> bool {
109 known
110 .iter()
111 .any(|(p, _)| as_le_pair(p).is_some() || as_lt_pair(p).is_some())
112}
113
114// =============================================================================
115// THE GOAL-DIRECTED HALF
116//
117// A refutation engine proves `⊥`. A DECISION PROCEDURE proves the goal — Lean's
118// `omega` negates it, adds it to the hypothesis set and refutes. Everything
119// below is that half, and it adds NO axiom: the case split runs on `le_total`,
120// which the trusted base already registers and whose own comment in
121// `prelude.rs` names this exact use.
122//
123// The one thing totality does not give is the STRICT negation. Over ℤ,
124// `¬(a ≤ b)` is `b + 1 ≤ a`; `le_total a b` yields the weaker `b ≤ a`, so the
125// fragment reached here is "every goal whose negation-by-totality is
126// refutable" rather than all of Presburger. Closing that last unit needs a new
127// `Int` axiom (`¬(a ≤ b) → b + 1 ≤ a`, or antisymmetry), and buying tactic
128// reach with trust is the one trade this campaign forbids — so it is named
129// here and not taken.
130// =============================================================================
131
132/// Is `t` an integer-valued term on its face — an arithmetic operator or a
133/// numeral? Mirrors `certifier::term_domain`'s `Int` classification (which is
134/// what decides the `Eq` domain of the goal type), so the two agree on which
135/// equalities `omega` may claim.
136fn is_int_valued(t: &ProofTerm) -> bool {
137 match t {
138 ProofTerm::Function(n, _) => matches!(
139 n.as_str(),
140 "add" | "sub" | "mul" | "div" | "mod" | "Add" | "Sub" | "Mul" | "Div"
141 ),
142 ProofTerm::Constant(s) => crate::numeral::is_numeral(s),
143 _ => false,
144 }
145}
146
147/// If `e` is an `Int` equality goal (`n + 0 = n`), return its two sides.
148fn as_int_identity(e: &ProofExpr) -> Option<(ProofTerm, ProofTerm)> {
149 if let ProofExpr::Identity(l, r) = e {
150 if is_int_valued(l) || is_int_valued(r) {
151 return Some((l.clone(), r.clone()));
152 }
153 }
154 None
155}
156
157/// Is this a goal `omega` has any business attacking? The old gate asked only
158/// about the HYPOTHESES, so `⊢ n + 0 = n` — an `omega` goal in Lean with no
159/// hypotheses whatever — was declined for having no hypotheses.
160pub(crate) fn is_arith_goal(e: &ProofExpr) -> bool {
161 as_le_pair(e).is_some() || as_lt_pair(e).is_some() || as_int_identity(e).is_some()
162}
163
164/// An integer literal operand, if this term is one.
165fn as_literal(t: &ProofTerm) -> Option<logicaffeine_base::BigInt> {
166 match t {
167 ProofTerm::Constant(s) => crate::numeral::int_of_constant(s),
168 _ => None,
169 }
170}
171
172/// Prove `a ≤ b` (as the `Identity` `goal`) from the known facts, WITHOUT any
173/// case split: by computation when both operands are literals, else by chaining
174/// the in-scope `≤` facts through `le_trans`/`le_refl`.
175fn prove_le_directly(
176 known: &[(ProofExpr, DerivationTree)],
177 a: &ProofTerm,
178 b: &ProofTerm,
179 goal: &ProofExpr,
180) -> Option<DerivationTree> {
181 if let (Some(av), Some(bv)) = (as_literal(a), as_literal(b)) {
182 // `le m n` δ-reduces, so `refl` closes the goal exactly when it holds.
183 return (av <= bv).then(|| DerivationTree::leaf(goal.clone(), InferenceRule::Reflexivity));
184 }
185 crate::engine::cert_le_chain(known, a, b)
186}
187
188/// Decide a positive linear goal. `None` means "not proved" — never "false".
189///
190/// * a ground `≤`/`<` by computation;
191/// * a `≤` goal by chaining the in-scope `≤` facts;
192/// * an `Int` EQUALITY by the proof-producing ring oracle (the `ArithDecision`
193/// channel), which is how `n + 0 = n` is discharged;
194/// * otherwise, for a `≤` goal, SPLIT on `le_total a b`: the left disjunct IS
195/// the goal, and the right (`b ≤ a`) is refuted together with the hypotheses,
196/// discharging the goal by ex falso. Both branches certify, so the whole
197/// `DisjunctionCases` node is one kernel-checked object.
198pub(crate) fn omega_prove(
199 known: &[(ProofExpr, DerivationTree)],
200 goal: &ProofExpr,
201) -> Option<DerivationTree> {
202 if let Some((a, b)) = as_le_pair(goal) {
203 if let Some(direct) = prove_le_directly(known, &a, &b, goal) {
204 return Some(direct);
205 }
206 // `(a ≤ b) ∨ (b ≤ a)` — totality, a certified leaf.
207 let flipped = le_eq(b.clone(), a.clone());
208 let disjunction = ProofExpr::Or(Box::new(goal.clone()), Box::new(flipped.clone()));
209 let totality = DerivationTree::leaf(disjunction, InferenceRule::LeTotal);
210 // Left: the disjunct assumed IS the goal.
211 let left = DerivationTree::leaf(goal.clone(), InferenceRule::PremiseMatch);
212 // Right: `b ≤ a` alongside the hypotheses. Refute them (then ex falso), or
213 // — when the extra edge completes a chain — prove the goal outright.
214 let mut extended = known.to_vec();
215 extended.push((
216 flipped.clone(),
217 DerivationTree::leaf(flipped, InferenceRule::PremiseMatch),
218 ));
219 let right = match crate::engine::cert_farkas(&extended).or_else(|| omega_close(&extended)) {
220 Some(bot) => DerivationTree::new(goal.clone(), InferenceRule::ExFalso, vec![bot]),
221 None => prove_le_directly(&extended, &a, &b, goal)?,
222 };
223 return Some(DerivationTree::new(
224 goal.clone(),
225 InferenceRule::DisjunctionCases,
226 vec![totality, left, right],
227 ));
228 }
229 if let Some((a, b)) = as_lt_pair(goal) {
230 // Ground strict comparison: `lt m n` δ-reduces. A SYMBOLIC `<` conclusion
231 // has no image in the trusted base at all — of the Int order axioms none
232 // CONCLUDES a `lt` (`lt_succ_le`/`lt_add1_le` both take one as a premise) —
233 // so the tightened `a + 1 ≤ b` is the strongest thing provable here. See
234 // the module comment: the converse `le_succ_lt` is the missing axiom.
235 if let (Some(av), Some(bv)) = (as_literal(&a), as_literal(&b)) {
236 return (av < bv)
237 .then(|| DerivationTree::leaf(goal.clone(), InferenceRule::Reflexivity));
238 }
239 return crate::engine::cert_lt_chain(known, &a, &b);
240 }
241 if let Some((l, r)) = as_int_identity(goal) {
242 if crate::tactic::int_identity_holds(&l, &r) {
243 return Some(DerivationTree::leaf(
244 goal.clone(),
245 InferenceRule::ArithDecision,
246 ));
247 }
248 }
249 None
250}