Sonata for Unaccompanied Achilles & Topic III — Figure and Ground

Core idea

Some properties of numbers can be generated by a positive rule — you can build a list of all the things with the property. Other properties can only be defined negatively, by what they lack. Composite numbers fall into the first group: a number is composite if you can build it as a × b with a, b ≥ 2. Primes fall into the second: a number is prime if it is not composite (and not 1). The topic introduces the tq-system, which captures composite-ness by direct generation, and shows that the natural attempt to capture prime-ness by the same trick fails. Primes live as the ground, defined only by what surrounds them — the negative space of the composite figure.

The figure-vs-ground distinction borrowed from gestalt psychology and Escher's prints (the topic is illustrated with Mosaic II, Tiling of the Plane with Birds, and Liberation) becomes a rigorous mathematical contrast. Some sets are recursively enumerable — there is a procedure that, run forever, eventually lists every member. A strictly smaller class is recursive — there is a procedure that, given any candidate, decides yes or no in finite time. The composites are both; the primes are only recursive because the composites' complement happens to be recursive, not because we have a positive rule producing them.

Hofstadter's argument: Not every meaningful property of numbers can be reached by a rule that generates the things with that property. Some properties are definable only by exclusion — and the gap between "definable" and "generatable" is one of the deep facts that will, three topics later, become Gödel's theorem.

Why it matters

The tq-system and composite numbers

The tq-system has axiom schema xt-q-x (where x is any string of hyphens) and one rule: from xtyqz derive xty-qz-. Reading hyphens as integers, t as "times", and q as "equals", the system's theorems are exactly the true equations a × b = c with a, b ≥ 1. To check whether a number n is composite, search the theorems for one of the form --t-?q...- where the right side decodes to n and both left factors are 2 or more. Find one and n is composite.

This procedure works because composite-ness is positively definable: a composite is something you can construct. The tq-system generates all composite numbers (by generating all products). The set of composites is recursively enumerable in the most direct way.

Why primes cannot be generated the same way

Now try the natural move: "a number is prime if it is not a theorem of the tq-system that any factorization equals it." That is the right definition — but it is not a rule of inference in a formal system. A formal system can produce theorems; it cannot, in general, certify that a string is not a theorem.

Hofstadter walks through several would-be prime-generating systems and shows each one breaks. Adding a rule "if no theorem produces n then n is prime" smuggles in an unbounded universal quantifier — a check across infinitely many possible derivations. That is not a finite mechanical rule. The naive moves fail. Eventually, with more work, a prime-generating system can be built, but it requires far more machinery than the composite generator. The asymmetry is real.

Recursively enumerable vs recursive

The topic introduces the foundational distinction that organizes the rest of the book. A set of numbers is recursively enumerable (r.e.) if there is a procedure that, run long enough, eventually outputs every member. A set is recursive (or decidable) if there is a procedure that, given a candidate, halts in finite time with the right yes/no answer. Every recursive set is r.e. — run the decision procedure on 0, 1, 2, … and output the ones it says yes to. The converse fails: there are r.e. sets that are not recursive, where you can list members forever but cannot, given a candidate, decide non-membership in finite time.

The composite numbers happen to be both r.e. and recursive (you can decide composite-ness by trial division). The primes are also both — by the same trial division. But there are number-theoretic properties that are r.e. and not recursive, and once such a property is in play, the asymmetry between "positively generatable" and "decidable" becomes inescapable. Topic IX will reveal Gödel's theorem as exactly this asymmetry made unavoidable.

Figure and ground in art and number theory

Escher's print Mosaic II shows a tessellation where every gap between figures is itself a figure. Tiling of the Plane with Birds makes the negative space (between the birds) be more birds. In number theory the analogue is: when is the complement of an r.e. set itself r.e.? When both are r.e., the set is recursive (run both enumerators in parallel; one of them will list any candidate). When the complement is not r.e., the original set is r.e. but undecidable — you can list members but never confidently rule one out.

The book uses Escher to give the reader an image of the asymmetry before the math makes it formal. Some figures pull all the structure to themselves and leave a featureless ground; other figures share the structure with their ground; rarely does the ground silently take all the structure and leave the figure as a passive byproduct. Number theory has all three cases, and the third case is where Gödel will be born.

Key takeaways

Mental model

Copy sourceZoom

Practical application

The topic trains a habit of asking, for any property: can I describe it by what it is, or only by what it is not?

1. Does the definition contain "no", "not", "never", or "for all"? A "for all" quantifier over an infinite domain is the warning sign. "Prime: for all a, b ≥ 2, ab ≠ n" hides an infinite check.

2. Can you offer a positive procedure that builds the thing? For composites you can: just multiply. For primes there is no equally simple positive build — you have to filter the integers through a negative test.

3. Is the property decidable even if not generatable? Sometimes you can decide a property in finite time without being able to enumerate it positively. Trial division decides primality even though it does so by ruling out the composites. The deeper trouble starts when a property is generatable but not decidable — when you can list examples but cannot say "this candidate is definitely not an example." That is where formal systems start to leak.

Most real-world specifications quietly contain negative definitions. "A safe function is one that never accesses freed memory." That is a for all execution paths claim. "A valid input is one that no parser will choke on." Same shape. The topic's question — generatable or only definable? — is the central design question of every type system, validator, and policy engine.

Example

Consider the set of strings a search engine "considers spam." From inside the engine, the procedure is positive: a classifier scans the string and emits a score, and strings above a threshold get flagged. That set is decidable by construction (run the classifier).

Now consider the set of strings the engine "would never flag." That is the complement. Is it also decidable? In principle yes — run the classifier and check that the score is below threshold. But notice the asymmetry of trust: if you want to show a string is spam, you can exhibit the score; if you want to show a string is definitely safe, you have to argue that no future update to the classifier would flag it, that no edge case in the score function fires, that no adversarial input could perturb it across the threshold. The positive case has a witness; the negative case requires an exhaustive search.

This is the figure-and-ground problem in real engineering. Software guarantees are easy when they say "X happens" (find a code path) and hard when they say "X never happens" (rule out every code path). Compiler errors are figure-and-ground duals: a type-check failure exhibits a witness; a type-check success is a claim about the absence of witnesses. The work the engineer has to do in each case differs by orders of magnitude, for exactly the reason the topic explores.

Related lessons