cmp_congr_of_balanced
plain-language theorem explainer
Comparison of signed orbits is invariant when either argument is replaced by a balanced representative. Order-theoretic arithmetic on SignedOrbit cites this to transport Ordering results across the balanced equivalence. The proof cases on lt/eq/gt and rewrites via left/right strict-order congruence plus balanced transitivity.
Claim. Let $a,a',b,b'$ be signed orbits. If $a$ is balanced with $a'$ and $b$ is balanced with $b'$, then the internal comparison satisfies $\mathrm{cmp}(a,b)=\mathrm{cmp}(a',b')$ as values in $\{lt,eq,gt\}$.
background
Signed orbits are the primitive integer carriers in the recognition calculus: each carries a signed distinction orbit rather than a bare verifier integer. Two orbits are balanced when they represent the same integer (same length and sign data under the ledger balance relation). The internal comparison selector cmp is defined from that balance test and the nonnegativity flag of the difference: equal when balanced, otherwise ordered by whether $b-a$ is nonnegative.
This lives in the IntegerOrder layer of PrimitiveRecognitionCalculus, which builds a total order on signed orbits without appealing to the display integer. Upstream, cmp_eq_eq_iff and cmp_eq_eq_of_balanced pin the equality case of cmp exactly to balance; companion lt congruence lemmas (left and right under balance) move strict inequalities across balanced replacements. The arithmetic-from-logic strict order on LogicNat is the distant ancestor of the orbit-level lt used here.
proof idea
Tactic proof by cases on cmp a b.
- If
lt: unpack viacmp_eq_lt_iffto getlt a b, push the inequality acrosshbthenhawithlt_congr_right_of_balancedandlt_congr_left_of_balanced, and repack withcmp_eq_lt_of_lt. - If
eq: unpack balance of $a$ with $b$, chainbalanced_symm ha, that balance, andhbbybalanced_transto get balance of $a'$ with $b'$, then applycmp_eq_eq_of_balanced. - If
gt: dual of theltcase, swapping sides and usingcmp_eq_gt_iff/cmp_eq_gt_of_gtwith the congruence lemmas on the reversed pair.
why it matters
This is the basic congruence lemma for the signed-orbit comparison: once balance is an equivalence, cmp descends to the quotient. Downstream it is the workhorse for product and difference stability: cmp_of_product_factors_of_balanced, the one-sided product factor variants, and cmp_of_sub_inputs_of_balanced (plus left/right sub variants) all reduce to replacing balanced factors inside cmp. Multiplicative cancellation forms cmp_mul_ofOrbit_left_of_ne_zero and cmp_mul_ofOrbit_right_of_ne_zero likewise rely on transporting comparisons across balanced rewrites.
In the Recognition foundation this keeps integer order internal to the orbit calculus (not the verifier display), so later forcing and ledger steps can treat order as a recognition primitive. It does not itself touch T5–T8 or the J-cost; it is pure order infrastructure under the arithmetic-from-logic stack.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.