Concept guide · δ & recognition
From distinctionto loop order
Repeating one step gives us counting. With several ways to make a round trip, the order of those steps carries information that a count cannot keep.
This guide follows that change: from the arithmetic generated by δ to walks on a cube, and from simple summaries to a memory that can retain loop order. Each new object answers a question left by the one before it.
This is the mathematical route through two studies of recognition. The cube below is a graph used to study histories. The physical identification of three-dimensional space in Recognition Science belongs to a separate argument.
A distinction becomes arithmetic when a step can repeat
A distinction says that two things differ. If a collection K contains unequal elements x and y, we write Dist(K). A coin’s two faces give an example. Their difference alone supplies no rule for counting coins.
The next ingredient is a repeatable operation. Start with an empty record, written 0. Extend any record r by one mark to obtain Sr. This one-step extension is called δ. Applying it repeatedly generates the δ-orbit.
Every record comes from those two rules: there is a start, and another step can follow any record. Once addition and multiplication are defined on this carrier, we write it as ℕδ.
Structural induction follows the same construction. Prove a property at 0, then prove that one more step preserves it. The property holds throughout the generated orbit. A successor is never 0, and equal successors have equal predecessors.
One source, many realizations
A δ-algebra is any system with a chosen start and a next-step operation. A light switch qualifies: start off, then flip. The generated records map to off, on, off, on, and so on.
Initiality says there is exactly one map from the δ-orbit into any such system that preserves the start and the step. That map may merge records, as the switch does. If the target’s step never merges states and never returns to its start, the map is injective. If the target also satisfies induction for every predicate, the map is a unique isomorphism. This stronger result is rigidity.
The exact structure
A δ-algebra is (|A|, 0A, SA). Its unique map recA satisfies recA(0) = 0A and recA(Sr) = SA(recA(r)). The rigidity conditions are successor injectivity, 0A outside the successor image, and induction for all predicates.
The construction takes place in a metatheory that supports inductive generation, recursion, and equality. It establishes a canonical arithmetic within that setting.
Read further: The δ-calculus, §1; the generated orbit and initiality and rigidity.
What can a summary of counting remember?
A monoid is a collection with an associative combining operation and a neutral element. Adding records, with the empty record as zero, gives one example. Joining strings, with the empty string as neutral, gives another. Associative means that changing brackets leaves the result unchanged.
A recognizer is a summary that respects combination: a monoid homomorphism r : M → N. Parity is a recognizer of counting. It reports even or odd, and the parity of a sum is determined by the parities of its parts. The target N need not be finite.
When r(x) = r(y), the recognizer cannot distinguish x from y. These equal-output classes form its recognition quotient. The underlying relation, x ∼r y, is the recognizer’s kernel congruence. The quotient is isomorphic to the recognizer’s image.
Explore 01 · A counting summary
Count to two, then repeat a three-state cycle
This tail-and-cycle pattern is written M(i, p). The threshold i can be zero; the period p is at least one. There are i + p states. A twelve-hour clock gives M(0, 12). The summary “zero, one, or many” gives M(2, 1).
Classification and its precise equivalence relation
Under excluded middle, every congruence on (ℕδ, +, 0) is either equality or ≡i,p for a unique i ≥ 0 and p ≥ 1. Thus every recognizer is injective or has image isomorphic to M(i, p).
There is only one generator. A record carries the number of repeated steps; it has no independent order information. This is why the possible quotients have such a restricted form.
The same classification has different logical prices
A constructive proof of existence supplies a witness or a way to obtain one. A decidable question has a procedure that terminates with yes or no. Those two ideas matter when the task is to find the first pair of counts a recognizer merges.
- A decidable rule + a known merged pairYou can find the threshold and period by bounded search. No additional nonconstructive principle is needed.
- A decidable rule, known only to be nonfaithfulMarkov’s principle (MP) converts double-negated existence into a witness for a decidable test. It supplies the merged pair needed by the search.
- An arbitrary congruenceExcluded middle (EM) permits “P or not P” for every proposition, even without a decision procedure. It supplies the general equality-or-lasso classification.
These last two prices are exact: each classification principle also implies the corresponding logical principle. They are required by the theorem at that level of generality, rather than merely used by one convenient proof.
LPO, the derivation ledger, and soundness
The limited principle of omniscience (LPO) says that a decidable sequence either succeeds somewhere or never succeeds. EM implies LPO, and LPO implies MP in the constructive setting used here. LPO is tracked but has no separate role in the final classification prices.
Inside the δ-calculus, each derivation carries a ledger, a subset of {EM, LPO, MP, QInd}. QInd records induction on quantified formulas. A derivation is called forced when EM, LPO, and MP are absent; QInd does not affect this designation.
The ledger belongs to a derivation in the calculus. Logical price concerns proofs in the surrounding metatheory. Keeping those two levels separate is essential.
Soundness: every closed formula with a forced derivation from the empty context is true in the ordinary natural-number model (ℕ, 0, S, +, ·).
Read further: The δ-calculus, §§3 and 7; classification and reversal proofs.
Build negatives and fractions from the records
Integers arise from pairs of natural records interpreted as credit and debit. Two pairs represent the same difference exactly when their cross-sums agree.
For example, (2, 5) and (4, 7) both represent −3: 2 + 7 = 4 + 5. Quotienting by this relation constructs ℤδ. Fractions then use signed numerators and nonzero denominators, identified by cross-multiplication, to construct ℚδ.
The number tower
Both constructions are choice-free: they require no arbitrary selection of representatives. They give explicit counterparts of the usual integers and rationals.
The first paper stops at the rationals. Constructing the reals raises a further question: under weak constructive assumptions, Cauchy and Dedekind constructions need not agree.
What “δ-encodable” means
A set X is δ-encodable when there is an injection X ↪ ℕδ. The paper supplies such encodings for ℕ, ℤ, and ℚ. An encoding labels distinct objects with distinct records; it does not identify their arithmetic operations.
Order enters when there is more than one way around
With one repeated operation, three steps followed by two gives the same record as two followed by three. This operation is commutative. To study information in order, change the carrier to round trips on a graph.
Use the edges and vertices of a cube, its 1-skeleton. The graph Q3 has eight vertices and twelve edges. Label each vertex with three bits. One step flips one coordinate, numbered 0, 1, or 2. Coordinate 0 is the rightmost bit in the labels below.
A based closed walk starts at a fixed vertex and returns there. Each coordinate must be flipped an even number of times. Write A = (000; 0101) for a walk around one square face, where 0101 is the sequence of coordinates flipped.
All these walks form a monoid W under concatenation. Its neutral element is the empty trip. Cutting at every return to the basepoint gives a unique sequence of first-return loops, so W is the free monoid on those loops. For example, 00101101 splits as (00)(101101).
A loop word keeps the order of crossings
Choose a spanning tree: seven edges that connect all eight vertices without closing a cycle. The remaining five cotree edges each create an independent loop. Label them x₁ through x₅.
Write a letter when a walk crosses a cotree edge: xᵢ in one direction, xᵢ⁻¹ in the other. Tree edges write nothing. Cancel adjacent inverse pairs. The result is the reduced loop word ρ(w), an element of the free group F₅. Only inverse cancellation is imposed in this group; changing the order usually changes the element.
Explore 02 · Walk the graph
Follow the edges. Read the word.
Reduced word · bottom to top of stack
Start at 000. No edges read.
For A = 0101, the final word is x₁⁻¹.
The free-group rank is edges − vertices + 1 = 12 − 8 + 1 = 5. For a square Q₂, the rank is one and the loop group is ℤ, which is commutative. Q₃ is therefore the first hypercube with noncommuting loop words. Smaller graphs outside the hypercube family can also have them.
Three readings of the same trip
Abelianization a(w) keeps the net signed tally of the five generators and forgets their order. The commutator x₁x₂x₁⁻¹x₂⁻¹ has zero signed tally but a nonempty reduced word.
The directed transition tally τ(w) counts uses of each directed edge. Any additive one-step reading assigns a weight to each directed edge and sums it along the walk. It factors through τ, so equal directed tallies force equal readings for every choice of weights in an abelian group.
A potential reading is a special case: assign a height φ(v) to each vertex and sum the changes. The intermediate terms cancel, leaving φ(end) − φ(start), which is zero on a closed walk.
Same edge counts · different order
AB
Face A first, then face B.
BA
Face B first, then face A.
Which readings contain which information?
These are relations of indistinguishability. Moving right merges more histories: exact equality retains everything, the reduced word forgets backtracking, and abelianization also forgets order. Both inclusions are strict.
ρ and τ are incomparable. AB and BA share a tally but have different words. The out-and-back trip 00 shares the empty word with the empty trip, but has a different tally. Neither reading determines the other.
A little memory sees some order. No fixed bound sees it all.
A sequential reading, also called a clock here, carries an internal state. Each directed edge updates that state, and an output is read at the end. A k-state fold has at most k possible states.
One bit is enough to separate AB from BA. Let a directed edge private to A set the bit to 0, and one private to B set it to 1. The final bit remembers which face came last. Additive readings cannot do this.
But every fixed finite-state reader misses some order. Repeating a block eventually enters a cycle of length at most k. Every possible cycle length divides k!, and k! is long enough to pass the initial tail. Thus k! and 2k! repetitions act identically on every state.
The equal-count pair, and the stronger nonconjugate pair
Set N = k!, with k ≥ 1. Use A = 0101 and C = 01020102, whose reduced words are x₁⁻¹ and x₂⁻¹.
Both walks have length 20N and tally 3Nτ(A) + Nτ(C). Every reader with at most k states ends in the same state on both, from every initial state. Their reduced words differ at letter N + 1.
Those two words are conjugate: they describe the same free-homotopy class after the basepoint is forgotten. A stronger pair removes that dependence on the starting point:
These have equal length 16N + 16, equal directed tallies, and the same universal k-state collision. Their words are not conjugate.
To check nonconjugacy, send x₁⁻¹ to X = [[1,1],[0,1]] and x₂⁻¹ to Y = [[1,0],[1,1]], with the other generators sent to the identity. The trace of XʳYXˢY is 2 + 2(r+s) + rs. For Pk and Qk, the traces are 2 + 8N + 3N² and 2 + 8N + 4N². Different traces rule out conjugacy.
What the memory bound says. For each k there is a pair that defeats every reader with at most k states. The pair grows with k. A larger finite reader can distinguish a particular pair; no single fixed bound recovers the reduced word for all histories.
The reader may receive the exact tally at the end and still fails. Its updates use only its bounded state and the current edge; they do not consult unbounded live counters.
A stack can grow with the history
Keep the reduced word on a stack. For each incoming letter, compare it with the top. If they are inverses, pop the top. Otherwise push the letter. Tree edges leave the stack unchanged. At the end, reading from bottom to top gives ρ(w).
One reduction, step by step
A sequential reading need not be a monoid recognizer: its final output may not preserve concatenation. The term “recognition quotient” applies when the reading is a genuine homomorphism. The reduced-word map is one.
Fourteen steps hide order from signed counts
How short can a nontrivial loop be if all its signed cycle counts vanish? On every hypercube Qn with n ≥ 3, the answer is fourteen.
Select the fourteen-step example in the graph to follow it. The walk returns home, with every signed count back at zero, while six letters remain in its reduced word. Its full directed tally is nonzero; zero signed counts do not make it invisible to every additive reading.
Why a shorter walk cannot work
- The edges it uses must contain at least two independent cycles. With only one, signed cycle count already determines the loop element.
- At least seven distinct edges are needed. In a simple bipartite graph, fitting two independent cycles into six edges would require K₂,₃: two vertices sharing three neighbours. Hypercubes cannot contain this shape because two distinct cube vertices have at most two common neighbours.
- Zero net flow requires every used edge to be traversed equally often in both directions. Seven edges therefore require at least fourteen steps.
The displayed walk attains the bound. This minimum is the hypercube’s abelian girth, the length of its shortest nontrivial edge-neutral closed walk after backtracking reduction.
The first order coordinate and the lower central series
A commutator [g,h] = ghg⁻¹h⁻¹ measures failure to commute. The lower central series starts with γ₁(F₅) = F₅ and continues with γn+1(F₅) = [γn(F₅), F₅]. Membership in γ₂ means zero abelianization. Deeper levels record order effects that survive further simplification.
Let si(k) be the signed contribution of step k to generator i, and ai(k−1) its running count before that step. Define
This order coordinate behaves like signed area and is unchanged by free reduction. When a(w) = 0, the values μij/2 give the class in γ₂/γ₃. The fourteen-step witness has μ₁₂ = −2, so it already lies in γ₂ outside γ₃.
Changing the spanning tree changes the labels and individual coordinates. It preserves triviality, lower-central-series membership, and the minimum length fourteen.
Different order readings can retain different information
Here is another way to read a walk. Attach quaternion factors q₀ = 1 + i, q₁ = 1 + j, and q₂ = 1 + k to the coordinate directions. Multiply them in traversal order and keep the directed tally alongside the product:
Quaternion multiplication is noncommutative, so the product can detect order. These factors are declared extra structure. They are chosen as part of this model; the preceding walk construction does not force them.
This reading treats an edge and its reverse with the same factor. An immediate backtrack in direction 0 contributes (1+i)² = 2i, whereas ρ cancels it. Thus the quaternion reading does not factor through the reduced loop word.
The clock separates
The pure-backtracking walks 001122 and 002211 have empty reduced words and equal directed tallies, but different quaternion products.
The loop word separates
AB and BA have different reduced words, but the declared clock c gives them the same reading.
Neither reading determines the other. In quotient notation, ΔW ⊊ ∼c ⊊ ∼τ, while ∼c and ∼ρ are incomparable.
Why 24 endpoints and 48 prefix states?
After removing the common size factor, the quaternion part takes exactly 24 possible values on closed walks. They form the binary tetrahedral group 2T. Computing the normalized component sequentially uses 48 possible prefix states, since a prefix need not be closed.
The full clock also retains the unbounded directed tally. The numbers 24 and 48 describe the normalized quaternion component, not the number of values of c. These counts and the cube’s three directions belong to this declared graph model.
When a state must match its history
Now attach an integer to each cube vertex. This declared state is α ∈ A = ℤV. A constraint decides which pairs (α,w) of state and history are allowed.
A constraint is rectangular, or projection-separable, if it has the form PA × PW. One independent test checks the state and another checks the history. Every accepted state can pair with every accepted history.
Independent tests or a matching rule?
Rectangular
Occupation binding
The occupation vector occ(w) counts how often the walk occupies each vertex. In the formal convention, it counts the departure vertex of each step, so a closed walk’s final return is not counted again. Occupation binding requires α = occ(w), directly coupling the state to its history.
There is an exact criterion on any fixed class S of histories: every occupation-based constraint is rectangular on A × S if and only if occupation is constant on S. When all allowed histories share one occupation vector, the occupation carries no information that varies within that class.
Recognition therefore depends on both the object being read and the information the reading retains. Repetition, signed counts, reduced order, and occupation answer different questions about a history.
Notation at a glance
- δ; 0; Sr
- One-step extension; empty record; record r extended once.
- ℕδ, ℤδ, ℚδ
- Generated natural records, their integer completion, and their fractions.
- M(i,p)
- A counting quotient with an initial tail of i states and a cycle of p states.
- EM, LPO, MP
- Excluded middle, limited omniscience, and Markov’s principle.
- Qn; W; L
- The n-cube graph; based closed walks; first-return loops.
- ρ; F₅
- The reduced loop word; the free group on five generators.
- a; τ
- Signed cycle counts; full directed-edge counts.
- μij; γn
- A degree-two order coordinate; the lower central series.
- c = (τ,h); 2T
- The declared tally-plus-quaternion clock; its 24-element normalized closed-loop group.
- A; occ; O
- Integer-valued vertex states; occupation vector; the rule α = occ(w).
- ΔW; ∼r
- Exact equality of histories; histories indistinguishable to reading r.
Sources and next reading
- The δ-calculus: from distinction to arithmetic, Jonathan Washburn and Milan Lj. Zlatanović. The manuscript supplies the generated carrier, number tower, and exact classification prices. arXiv record.
- From Distinction to Loop Order: A Concept Guide. The source guide for this webpage, including its account of From One Generator to Loop Order: Recognition and Memory on Hypercubes.
- δ mathematics in Lean. Start with the repository’s paper map for the arithmetic results.
- Recognition Science’s public physics formalization, and the Recognition Encyclopedia for the wider framework.
The arithmetic and the cube-walk results have different source routes. The arithmetic links above lead to the public δ library. The loop discussion follows the source guide and its associated manuscript; the interactive examples display explicit walks rather than certify the general theorems.