Foundation Cycle Operator Cycle Step Is Bitflip

The one-bit step

A Gray code is a way of ordering binary numbers so that consecutive values differ in exactly one bit. The classic example for three bits runs 000, 001, 011, 010, 110, 111, 101, 100. In the Recognition Science framework, this ordering is not a curiosity: it is the skeleton of an eight-step cycle that the framework treats as the basic rhythm of recognition events. The declaration cycle_step_is_bitflip is a machine-checked theorem stating that every step in this cycle, from one vertex of the three-bit cube to the next, flips exactly one bit. The proof is computational: the framework's library checks all eight cases directly, so the result carries the full weight of a formal proof rather than a hand-waved pattern match.

The statement is precise about what it covers. It says that for each tick t in the cycle, the permutation that moves the current vertex to the next one equals the operation that flips the bit specified by a function called flippedBit. The theorem does not say which bit gets flipped at which step; that information lives in a separate definition. It also does not say anything about why the cycle has eight steps, why the Gray code order is the right one, or what the cycle means physically. Those are separate claims in the framework, each with its own proof or definition. The theorem is a structural fact about the cycle operator, not an interpretation of it.

What the theorem does establish is a clean bridge between two ways of describing the cycle. On one side, the cycle is a permutation of eight vertices, a closed loop that returns to its start after eight steps. On the other side, each step is a local operation: flip one bit, move to a neighbor. The equivalence matters because the framework uses the cycle to model how recognition events accumulate, and the bit-flip description is what lets it attach numbers to each axis. The theorem guarantees that the two descriptions never disagree, which is the kind of consistency a formal library exists to certify.

The theorem does not claim that the cycle is the only Gray code on three bits, nor that the specific order chosen is forced by anything. It does not claim that flipping one bit per step is a law of physics; it is a property of a mathematical object the framework defines. And it does not claim that the cycle operator itself is derived from first principles. The cycle is constructed, not proved. What is proved is that the construction has the bit-flip property at every step, and that the cycle has period eight with no smaller period. Those are the facts a reader can rely on as machine-checked.

/-- Each step of the cycle equals a single bit flip (the one identified by flippedBit). -/
theorem cycle_step_is_bitflip (t : Fin 8) :
    cyclePerm (grayOrder t) = bitFlipOp (flippedBit t) (grayOrder t) := by
  fin_cases t <;> native_decide

/-- Each step of the cycle equals a single bit flip (the one identified by flippedBit). -/
theorem cycle_step_is_bitflip (t : Fin 8) :
    cyclePerm (grayOrder t) = bitFlipOp (flippedBit t) (grayOrder t) := by
  fin_cases t <;> native_decide

/-- The cycle permutation has period exactly 8. -/
theorem cyclePerm_period : ∀ v, (cyclePerm^[8]) v = v := by
  intro v; fin_cases v <;> native_decide

/-- After fewer than 8 iterations, the permutation is NOT the identity. -/
theorem cyclePerm_not_identity_before_8 :
    ∀ k, 0 < k → k < 8 → ∃ v, (cyclePerm^[k]) v ≠ v := by
  intro k hk hk8
  interval_cases k <;> exact ⟨0, by native_decide⟩

What this page does not claim

The theorem does not state which bit flips at which step. The theorem does not derive the eight-step cycle from first principles. The theorem does not assign physical meaning to the bit flips.

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/CycleOperator.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: