Skip to main content

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}