Theory of Concatenation (TC)

Origin. Quine, "Concatenation as a basis for arithmetic" (JSL 11, 1946), took the syntactic operation as primitive and built arithmetic on it; Tarski formulated the editor axiom. Andrzej Grzegorczyk revived the programme in "Undecidability without arithmetization" (Studia Logica 79, 2005), where TC is introduced and proved undecidable; Grzegorczyk and Zdanowski (2008) proved it essentially undecidable. Švejdar (2007), Ganea (2007), and Visser independently settled the open question left there: TC and Q are mutually interpretable.

Models. Strings, not numbers. The domain is the free semigroup on two generators, with concatenation as the only operation and two irreducible one-letter strings as the only constants. The motivation is philosophical and it is precise: computation manipulates text, so incompleteness and undecidability ought to be statable without ever coding syntax as numbers. Gödel's arithmetization is a detour, and TC shows what the destination looks like without it.

Formalism.

Language: constants a, b; binary function ⌢ (concatenation). Some presentations use 0, 1 and add the empty string ε or a prefix relation ⪯.

Axioms (TC^{−ε}, Grzegorczyk 2005): TC1. (x⌢y)⌢z = x⌢(y⌢z) (associativity — the editor axiom) TC2. x⌢y = z⌢w → ∃u ((x⌢u = z ∧ u⌢w = y) ∨ (x = z⌢u ∧ w = u⌢y)) (overlap/unique parsing) TC3. x⌢y ≠ a TC4. x⌢y ≠ b TC5. a ≠ b

Five axioms. No induction, no numbers, no coding.

Interpretation results: Grzegorczyk (2005): TC undecidable. Grzegorczyk–Zdanowski (2008): TC essentially undecidable. Švejdar (2007): Q⁻ interpretable in TC, hence Q interpretable in TC. Visser (2007), Ganea (2007): further proofs; Visser's avoids the Q⁻ detour. TC is interpretable in IΔ₀. Hence TC ≡ᵢ Q: the weakest arithmetic and the weakest string theory are the same theory in different clothes.

Minimality: Higuchi and Horihata (2014): TC^{−ε} is a minimal essentially undecidable theory — remove any axiom and essential undecidability fails. They prove the same for the weak subtheory WTC^{−ε}, confirming Grzegorczyk and Zdanowski's conjecture.

Relatives: WD, D (Kristiansen–Murwanashyaka) in ⟨0, 1, ∘, ⪯⟩, mutually interpretable with R and with Q respectively. QT⁺ (Damnjanović 2017): an elementary concatenation theory mutually interpretable with Q, Minimal Predicative Set Theory, the quantifier-free part of Kirby's finitary set theory, and Adjunctive Set Theory with or without extensionality.

Symbols.

Metatheory. The mutual interpretability of TC and Q is the result the entry exists for: essential undecidability does not depend on arithmetic, on numbers, or on Gödel numbering, and the string theory reaches it with five axioms and no schema. What incompleteness requires turns out to be a structure that can parse — associativity plus unique decomposition — and everything else in Q is packaging. Minimality (Higuchi–Horihata) sharpens this: nothing in TC is spare. Damnjanović's theorem extends the identification sideways, making Robinson arithmetic, adjunctive set theory, and concatenation theory into three presentations of a single degree of interpretability. Numbers and sets are, at this level, variants of strings.

Applies to. Undecidability proofs without arithmetization. Formal syntax and metamathematics done directly on expressions. The theory of interpretability at the bottom of the hierarchy. Word problems and semigroup theory — TC is interpretable in Tarski and Szmielew's theory F. Weak arithmetic generally, as the string-side coordinate of the Q-degree.

Limitations. TC proves almost nothing about strings: no length, no induction, no numeral order except through interpretation. Its axioms are chosen for the theorems, exactly as Q's are, and no one computes in it. The philosophical claim that concatenation is more basic than number does not follow from the mutual interpretability, which is symmetric and licenses the converse reading equally. TC^{−ε} and TC differ over the empty string, and results must be checked against which is meant.

© 2026 Lingenic LLC