Foundation Primitive Recognition Calculus Grow Signed Orbit Order Choice Free Le

Choice-free order

A signed orbit is a pair of natural-number positions, representing a difference between two counts. The order on such orbits says one orbit is at most another when the difference between them is nonnegative. The declaration le_iff_nonnegFlag_sub_cf establishes that this order is exactly equivalent to checking whether a structural Boolean flag on the difference is true. It is a theorem in the machine-checked library of formal theorems, and it is proved without using the axiom of choice.

The theorem is part of a larger effort to re-ground the order on signed orbits entirely in the natural numbers, avoiding the integers. The integers carry a choice principle through their standard library, which the framework's library treats as taint it does not need. By proving the order through natural-number inequalities on the orbit positions, the library shows that reflexivity, transitivity, totality, and antisymmetry up to balanced length all hold with only the two axioms propext and Quot.sound. This is the choice-free base that the later ordered-field tower of ratio rungs requires.

The theorem does not claim that the order is total in the sense of a classical trichotomy, nor does it claim that every property of the signed-orbit order can be proved without choice. It specifically replaces an earlier, choice-tainted route through the integer display. It also does not claim that the structural Boolean flag itself is defined without choice; the flag's definition may still use classical decidability, but the equivalence here is proved by structural induction plus arithmetic over the natural numbers.

/-- The order via the structural nonnegative flag of the difference: the choice-free
foundation the `ratio_*` rungs need (replaces the tainted `le_iff_nonnegFlag_sub`). -/
theorem le_iff_nonnegFlag_sub_cf (a b : SignedOrbit) :
    SignedOrbit.le a b ↔ (SignedOrbit.sub b a).nonnegFlag = true := by
  unfold SignedOrbit.le
  rw [nonnegFlag_iff_nonneg_cf]

/-- The order via the structural nonnegative flag of the difference: the choice-free
foundation the `ratio_*` rungs need (replaces the tainted `le_iff_nonnegFlag_sub`). -/
theorem le_iff_nonnegFlag_sub_cf (a b : SignedOrbit) :
    SignedOrbit.le a b ↔ (SignedOrbit.sub b a).nonnegFlag = true := by
  unfold SignedOrbit.le
  rw [nonnegFlag_iff_nonneg_cf]

What this page does not claim

The theorem does not claim that the structural Boolean flag itself is defined without choice. It does not claim that every property of the signed-orbit order can be proved without choice.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Foundation/PrimitiveRecognitionCalculus/Grow/SignedOrbitOrderChoiceFree.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: