Logic, Self-Reference, and Category Theory

The previous essay followed the first engine, iteration, to its end. A rule applied again and again produces fixed points, attractors, invariant measures, scaling laws, and finally the invariant tori of KAM theory, held together or torn apart by the arithmetic of a single frequency. Through all of it, arithmetic stayed outside the system. Integers counted returns. Continued fractions measured resonance. The numbers were a ruler we held up against the motion.

This essay turns the hinge. It uses arithmetic the second way: not as a ruler held against the system, but as a language the system speaks about itself.

That turn is the whole subject. The same integers that count returns going around a clock can count symbols inside a formula, because a formula is just a finite string of symbols, and a finite string can be packed into a single number. Once that is possible, a system can encode descriptions of its own statements, rules, and programs, and then act on those descriptions. We call that representational closure, and it is the threshold of the second engine: self-reference.

The payoff is a new family of fixed points. Not attractors and tori, but Gödel sentences, undecidable programs, quines, the Y combinator, and recursive types. The fixed-point question survives the change of engine intact, “what transformation acts here, and what does it leave invariant?”, even though the machinery that answers it is entirely new. By the end, a single categorical theorem due to Lawvere will show Gödel, Turing, Cantor, and Russell to be one argument in four disguises.

This is the point where the word “fixed point” changes level. Earlier, a fixed point was a state that a rule did not move:

$$ f(x^\star)=x^\star. $$

Here, a fixed point is a represented object that survives being fed through a rule about its own representation:

$$ \text{object}\simeq\text{transformation}(\text{description of that object}). $$

That is why the phrase reappears without being redundant. Engine A found fixed points by repeating a rule on states. Engine B finds fixed points, or proves their impossibility, by letting descriptions act on themselves.

#The Minimum Vocabulary

A formal system is a rule-governed language for making proofs. It has symbols, formulas, axioms, and rules of inference that turn formulas into other formulas. Arithmetic, the theory of $0$, successor, addition, and multiplication, is the formal system we will care about, because it is strong enough to be turned on itself.

Encoding means representing one kind of object as another. The encoding at the heart of this essay is Gödel numbering: assigning a number to every formula and every proof, so that statements about formulas become statements about numbers. Once syntax is encoded as arithmetic, arithmetic can talk about syntax.

Diagonalization is the self-reference move, and it recurs so often it deserves a name. You take a construction meant to range over a collection of objects, and you feed it an object built from itself. Sometimes this produces a useful fixed point. Sometimes it produces a contradiction, and the contradiction becomes an impossibility theorem. Cantor, Gödel, Turing, and Russell are all this one move.

Representational closure is the threshold condition: the moment a system can represent enough of its own expressions, rules, or maps for self-application to become possible. Below the threshold, self-reference is just informal wordplay. Above it, it is mathematics.

A category, introduced near the end, is the bookkeeping of objects, arrows between them, and a way to compose arrows. It is the language in which all the self-reference theorems turn out to be the same theorem.

#Two Engines, Recalled

A quick restating of the architecture, because this essay opens the series’ second half.

The claim has never been that everything is the same object. It is that two mechanisms keep forcing invariant objects to appear.

The first is iteration: take a rule $x\mapsto f(x)$ and apply it repeatedly. That alone produced the first four essays. The system does not represent itself; it is simply turned.

The second is self-reference: a system rich enough to represent its own expressions, maps, or proofs, and then apply transformations to those representations. This is the engine of the present essay.

Both engines run the same discipline:

1. choose a space,
2. choose a transformation,
3. apply it repeatedly, or let it act on its own representations,
4. ask what remains invariant,
5. study whether that invariant is stable, unstable, universal, pathological, or expressive.

A fixed point is the simplest invariant, $T(x)=x$. But invariance can also mean a set maps into itself, a distribution keeps its shape under rescaling, a torus survives perturbation, a sentence talks about its own code, or a type unfolds into one layer plus another copy of itself.

The two engines are related but not interchangeable, and the difference is exactly representation:

One theorem sits deepest in the self-reference column, and stating it up front gives the rest of the essay something to aim at. It is Lawvere’s, and informally it says:

once a system can represent its own maps richly enough, fixed points are unavoidable.

The contrapositive is just as important, and it is where the impossibility theorems come from:

if some transformation has no fixed point, then no representation system can be that complete.

That single sentence, read forwards and backwards, is the skeleton behind Cantor, Gödel, Turing, and Tarski, whose theorem says a system strong enough for arithmetic cannot define its own truth. Boolean negation, “swap true and false,” has no fixed point. “Do the opposite of whatever the decider says” has no fixed point. “This sentence is not provable” is the same obstruction written in the language of proof. Self-reference is generative when the relevant fixed point exists, and it becomes a limit theorem when the fixed point cannot exist. We will earn that sentence properly by the end.

One honest caveat about the boundary between the engines. Some iterated systems can become powerful enough to compute, and at that point they cross into representation. Rule 110, a one-dimensional cellular automaton with a trivially simple local update, is rich enough to simulate any computation. So the line between “merely iterated” and “self-referential” is not a wall; iteration can climb into representation. But the distinction still earns its keep: chaos is not automatically self-reference, and self-reference is not automatically chaos. Keeping them separate is what let the first four essays stay clean.

#Why Logic Suddenly Appears

Gödel’s discovery, stripped to a sentence, is that whenever a formal system can talk about its own statements, self-reference appears, and self-reference forces fixed points. Getting there requires seeing how a system talks about itself, which is the encoding trick.

#Encoding syntax as numbers

Recall what a formal system contains: symbols, formulas (strings of symbols), and proofs (lists of formulas). Gödel’s move was to notice that arithmetic, which obviously talks about numbers, can be made to talk about all of that too, by giving everything a number.

There are two levels in play, and naming them prevents confusion:

1. the object language, where ordinary arithmetic statements live (“$2+2=4$”),
2. the meta-language, where we talk about formulas, proofs, and provability (“such-and-such string is a valid proof”).

Gödel showed that a sufficiently strong arithmetic can internalize part of its own meta-language: it can represent statements about formulas as statements about numbers. That representation is Gödel numbering.

The idea is far less mysterious if you first do it crudely. Assign a number to each symbol:

A formula is a finite string of symbols, hence a finite list of these numbers. A proof is a finite list of formulas, hence a finite list of lists of numbers. The only remaining trick is to pack a finite list of numbers into a single number, and there are standard ways to do it. Gödel used prime factorization. The list

$$a_1,a_2,\ldots,a_n$$

becomes

$$2^{a_1}3^{a_2}5^{a_3}\cdots p_n^{a_n}.$$

Because every integer factors into primes in exactly one way, the original list can always be recovered from the product: read off the exponent of $2$, then of $3$, then of $5$, and so on. The encoding is reversible, which is the only property that matters. Any string of syntax can be stored inside a single integer, and pulled back out.

Now the consequence. Once formulas and proofs are numbers, properties of syntax become properties of numbers. “This string is a well-formed formula” becomes an arithmetic property of an integer. “This list of formulas is a valid proof of that formula” becomes an arithmetic relation between two integers. Concretely, write

$$\operatorname{Proof}(p,g)$$

to mean “the number $p$ codes a proof of the formula whose code is $g$.” This looks like a statement about proofs, but after encoding it is an ordinary arithmetic relation, checkable by arithmetic. And then provability itself becomes arithmetic:

$$\operatorname{Provable}(g)\equiv \exists p,\operatorname{Proof}(p,g),$$

read as “there exists some number $p$ that codes a proof of $g$.” This is the crucial turn. Provability sounds like a notion that lives in the meta-language, outside the system. After Gödel numbering, the system can express it internally. Arithmetic can talk about what arithmetic can prove.

#The diagonal, in its rawest form

Before Gödel’s sentence, look at the move underneath it with no logic attached at all. Suppose someone claims to have listed every yes/no property of the natural numbers, one property per row:

Now build a new property $D$ by walking down the diagonal and flipping each entry:

$$D(n)=1-P_n(n).$$

By construction $D$ disagrees with $P_0$ at input $0$, with $P_1$ at input $1$, with $P_2$ at input $2$, and so on down the list. So $D$ differs from every row in at least one place, which means $D$ was never on the list. The claim to have listed all properties fails. That is Cantor’s diagonal argument, and it is the seed of everything in this essay: take the object indexed by $n$, ask what it says about $n$, and then transform that answer. Diagonalization is the place where representation (indexing objects by $n$) meets self-application (asking object $n$ about $n$).

#Gödel’s sentence as a fixed point

Gödel’s construction is a richer version of that flip. The technical engine is the diagonal lemma, which says, roughly, that for any property of codes $\varphi(x)$ you can write down, there is a sentence $G$ that asserts that property of its own code:

$$G \leftrightarrow \varphi(\ulcorner G\urcorner).$$

The corner brackets $\ulcorner G\urcorner$ mean “the code number of the sentence $G$.” So the diagonal lemma is a fixed-point factory: hand it any property of codes, and it returns a sentence that is true exactly when that property holds of itself. The sentence $G$ is a fixed point of the operation “take a code, build a statement about that code.”

Now feed the factory the one property that detonates. Let

$$\varphi(x)=\text{``the sentence coded by }x\text{ is not provable.‘’}$$

The diagonal lemma hands back a sentence $G$ with

$$G \leftrightarrow \text{``}G\text{ is not provable.‘’}$$

That is Gödel’s sentence: a statement asserting, in effect, I am not provable in this system. If the system could prove it, the system would prove a falsehood; if the system is sound, meaning it proves only true statements, it cannot prove $G$, so $G$ is true but unprovable. The system is incomplete, not by a gap that better axioms could fill, but because its own capacity for self-reference manufactured a true sentence it cannot reach.

The same diagonal skeleton appears across the subject with the property $\varphi$ swapped out:

• Gödel feeds it “not provable” and gets an unprovable truth.
• Turing feeds it “the program that halts here does not” and gets the undecidability of the halting problem.
• A quine feeds it the print-yourself operation and gets a program that outputs its own source.

Turing’s entry compresses a construction worth seeing once. Suppose a program $H$ could decide halting: given any program $p$ and input $x$, it answers whether $p$ eventually stops when run on $x$. Build a contrarian program $D$ that, handed a program’s code $p$, asks $H$ what $p$ does when fed its own code, and then does the opposite: $D$ loops forever where $H$ predicts halting, and stops where $H$ predicts looping. Now run $D$ on its own code. If $H$ says it halts, it loops; if $H$ says it loops, it halts. Either way $H$ is wrong, so no such $H$ can exist. The halting problem is undecidable, and the proof is Cantor’s flip with “halts on itself” in place of “is on the list.”

#From logic to running code: quines and the Y combinator

The logical version is intimidating; the programming version is friendly, and it is the same fixed point. A quine is a program $q$ that prints its own source code. Writing $\operatorname{eval}$ for “run the program,” a quine satisfies

$$\operatorname{eval}(q)=q.$$

It is literally a fixed point of the run-and-print pipeline. The trick is exactly the diagonal lemma’s: the program holds a representation of itself as data, and then uses that data to reconstruct itself. Here is the whole idea in three lines of Python, small enough to read:

template = 'template = {!r}\nprint(template.format(template))'
print(template.format(template))

The string template is a description of the program. The last line inserts that description into itself and prints the result, which is the program’s own source. Nothing mystical happens. The program can refer to itself because it can hold a representation of itself and feed that representation back into its own rule. That is representational closure made small enough to run.

Kleene’s recursion theorem is the general statement behind quines: for any computable transformation you might apply to programs, there is a program that obtains its own description and feeds it into that transformation. Programs can always be made to know their own code.

#Simulation: Diagonal Fixed Point Toy

The most famous fixed point in all of programming is the Y combinator, which lives in the lambda calculus, the minimal language of functions. It satisfies

$$Yf=f(Yf).$$

Stare at that for a second: $Yf$ is left unchanged when you apply $f$ to it one more time. It is a genuine fixed-point equation, but for functions rather than numbers. Its purpose is to make recursion possible without ever naming a function. Normally a recursive definition says “define this function in terms of itself,” which seems to require the function to already have a name to refer to. The Y combinator dissolves that apparent circularity into an explicit fixed point: it builds the self-reference out of pure function application. It is the computational sibling of the diagonal lemma, and, as we will see, the type-theoretic sibling of recursive types.

#The same move, five times

So diagonalization keeps reappearing because it is one structural idea, not five coincidences:

1. Cantor diagonalizes against lists of real numbers.
2. Gödel diagonalizes against provability.
3. Turing diagonalizes against halting deciders.
4. Quines diagonalize against the separation of source and output.
5. Lawvere, shortly, abstracts the diagonal itself.

The common shape is always: a system rich enough to encode its own elements, and a transformation that can be turned back on that encoding.

Here is the dictionary between this essay and the iteration engine of the earlier ones. In dynamics, you repeatedly apply a function to a state, $x\mapsto f(x)$. In logic, you encode a statement as a number and build a new statement about that number, $n\mapsto\varphi(\ulcorner n\urcorner)$. The diagonal step feeds the code of the constructed statement back into the construction, which is self-application, the logical analog of iteration.

Different domain, same structure. A system has enough internal expressive power to turn a rule back on its own objects, and once it does, fixed points appear. In dynamics they are attractors and cycles. In logic they are self-referential sentences. In computation they are programs that refer to their own source.

The tenth lesson:

Self-reference generates fixed points in logic just as iteration generates fixed points in dynamics.

The bridge from number theory to logic is coding. Number theory hands you arithmetic objects; Gödel shows those objects can encode syntax; once syntax is encoded, statements can point at themselves through their own codes. Before Gödel, arithmetic looks like a subject about numbers. After Gödel, arithmetic is also a medium in which a formal system represents its own grammar, a mirror in which it can see its own sentences.

#Why Category Theory Appears

Once you have watched fixed points fall out of Banach contractions, Gödel sentences, Turing machines, fractals, renormalization, programming languages, and recursive types, a natural question forms:

What is the most general setting in which fixed points must exist?

That question is what category theory is for, here. It is not abstraction for sport; it is the search for the smallest assumptions that still force a fixed point.

You do not need a course in category theory for what follows. The only habit to borrow is this: when the objects get too different, compare the arrows. A dynamical map, a program, a proof translation, and a type constructor are not the same kind of thing, but each is a transformation that can be composed with another transformation.

#Just enough category theory

A category is a deliberately spare structure:

1. objects,
2. arrows between objects,
3. a way to compose arrows.

That is all. In the category of sets, objects are sets and arrows are functions. In a category of types, objects are types and arrows are programs. In a category of spaces, objects are spaces and arrows are structure-preserving maps. The trick of category theory is to study a subject by its arrows rather than by what its objects are made of: not “what is inside this object” but “what maps into it, what it maps to, and how those maps compose.”

That viewpoint fits here because every essay in this series has been about a transformation acting on a space:

Category theory keeps the transformation and deliberately forgets the material. Forgetting sounds like a loss, but it is what exposes the skeleton: if you stop asking what the objects are made of and keep only how the maps compose, the parts of the fixed-point arguments that were really the same become visibly the same.

The one operation a category insists on is composition. If

$$A\xrightarrow{f}B\xrightarrow{g}C,$$

then there is a composite arrow

$$A\xrightarrow{g\circ f}C.$$

That is already enough to model pipelines, dynamics, program execution, proof translation, and change of coordinates, because each of those is “do one thing, then do the next.”

#Functors and the fixed points that are data structures

A functor is a map between categories that preserves this structure. For a programmer, the cleanest mental model is a type constructor that also knows how to map functions. Take

$$F(X)=1+A\times X.$$

Read the right side as a choice: either the single empty case (the $1$), or a pair of an $A$ and an $X$ (the $A\times X$). If $A$ is the type of elements, then $X$ is the placeholder for “the rest of the list.” That is exactly the shape of a list: a list is either empty, or it is one element of type $A$ followed by another list. The functor $F$ captures “one layer of list-ness.”

An algebra for a functor $F$ is an object $X$ together with a way to collapse one layer $F(X)$ back down into $X$:

$$F(X)\to X.$$

For lists, that means: given either “empty” or “an element plus a list,” produce a list. An inductive data type is the initial such algebra, where initial means every other algebra receives exactly one structure-respecting map from it; it is the category’s way of saying “the smallest one, with nothing extra added.” The initial algebra is a fixed point of the functor. The type of finite lists, written $\mu F$, satisfies

$$\mu F \cong 1 + A\times \mu F,$$

which is the equation “a list is either empty, or an element of $A$ paired with another list,” now read as a fixed-point equation for types. The symbol $\cong$ means the two sides are the same type up to relabeling.

#Simulation: Recursive Type Unfolding

The notation $\mu F$ means “the least fixed point of $F$,” and “least” is doing real work. It is the order-theoretic fixed-point story from the first essay returning in type form. Knaster and Tarski proved that monotone maps on complete lattices have least and greatest fixed points; Kleene showed that, under the right continuity assumptions, you can build the least one by starting from the bottom and iterating upward. A recursive type is built the same way: start with no values, apply the constructor pattern, apply it again, and take the smallest stable solution.

For lists, the upward construction is concrete and worth seeing:

$X_0$ contains no lists at all. $X_1$ contains only the empty list. $X_2$ adds the one-element lists. $X_3$ adds lists of length at most two. Iterating forever, the union of all stages is the least fixed point: exactly the finite lists, and nothing infinite. This is why “least” matters. The same equation $X\cong 1+A\times X$ also has larger solutions if you permit infinite or circular objects; the inductive list type deliberately picks the smallest, which keeps every list finite. It is Kleene’s “iterate up from the bottom” in a different category, and it is the same convergence-from-below picture as a contraction settling onto its fixed point in the first essay.

The pattern is now familiar enough to tabulate:

#Coalgebras: the same idea, run forever

There is a dual story for infinite behavior. A coalgebra has the arrow turned around:

$$X\to F(X).$$

Instead of collapsing one layer into an object, it unfolds an object into one observable layer plus a next state. Streams are the clean example. An infinite stream of values,

$$a_0,a_1,a_2,\ldots,$$

is described by the functor $F(X)=A\times X$ (“a head value, plus the rest”), and a stream is a value of the terminal coalgebra, terminal meaning every other coalgebra maps into it uniquely, the category’s way of saying “the largest one,”

$$\nu F \cong A\times \nu F,$$

read as “a stream is a head element of type $A$ together with another stream.” Unlike a list, there is no empty case to stop it. It unfolds forever.

The practical distinction is simple. An algebra builds finite data by consuming one layer at a time. A coalgebra observes an ongoing system by exposing one layer and a next state. Lists are algebraic; streams, automata, and state machines are coalgebraic.

So the algebra/coalgebra split mirrors a distinction the series has circled before: inductive construction builds finite objects from base cases, while coinductive observation describes ongoing processes observed through time. Both are fixed points of functors, $\mu F$ and $\nu F$, the least and the greatest. And the coalgebraic shape, $\text{state}\to\text{observation plus next state}$, is exactly a dynamical system: automata, transition systems, infinite processes, and feedback loops all fit it. Category theory turns out to be the language in which recursive data and ongoing dynamics are two readings of one fixed-point idea, which is why it can sit at the seam between the logic of this essay and the living, trading systems of the next two.

#Lawvere’s theorem: the bare diagonal

Now we can state the result the whole essay has been aiming at. Lawvere’s fixed-point theorem abstracts the diagonal argument into pure category theory: under suitable conditions, if a category contains enough self-description, fixed points follow. It is why one theorem family touches Gödel, Turing, Cantor, Russell, and program recursion at once.

The skeleton it isolates is four steps:

1. objects can represent maps,
2. represented maps can be evaluated,
3. evaluation can be diagonalized,
4. diagonalization forces a fixed point.

In less compressed language: if a system can name every operation on itself, then one of those named operations can be fed its own name. That self-application is the diagonal move. Lawvere’s theorem says that, under the right structural assumptions, this move forces a fixed point.

One informal phrasing: if every function $A\to B$ can be represented by some element of $A$, then every map $B\to B$ has a fixed point. Let me earn that in set-theoretic clothing, slowly, because the proof is just the diagonal argument with the decoration stripped off.

Suppose there is a surjective map

$$\phi:A\to B^A,$$

where $B^A$ means “the functions from $A$ to $B$.” Surjective means every such function appears as $\phi(a)$ for some $a$; this is the “enough self-description” hypothesis, that $A$ is rich enough to name all the functions $A\to B$. Now take any map $\alpha:B\to B$ and define a new function

$$g(a)=\alpha(\phi(a)(a)).$$

Read $\phi(a)(a)$ as: take the function named by $a$, and feed it $a$ itself, the diagonal move. Then apply $\alpha$. Since $g$ is a function $A\to B$, and $\phi$ names every such function, we have $g=\phi(a_0)$ for some particular $a_0$. Evaluate everything at that $a_0$:

$$\phi(a_0)(a_0)=g(a_0)=\alpha(\phi(a_0)(a_0)).$$

So the value $b=\phi(a_0)(a_0)$ satisfies $b=\alpha(b)$. It is a fixed point of $\alpha$. We did not assume $\alpha$ had one; the richness of $\phi$ manufactured it.

Now run the implication backwards, and the impossibility theorems fall out for free. Take $B={0,1}$ and let $\alpha$ be Boolean negation, which famously has no fixed point (swap $0$ and $1$ and nothing stays put). Lawvere’s theorem then forbids the hypothesis: there can be no surjection $A\to{0,1}^A$. That is Cantor’s theorem, that no set surjects onto its own power set. Gödel, Turing, and Russell are the same move with a richer $B$ and a different fixed-point-free $\alpha$: negate provability, flip the halting decider, negate membership. Russell’s version is worth one sentence, since the essay has not built it yet: form the set of all sets that do not contain themselves, and ask whether it contains itself. Each answer forces the other. That is the diagonal with membership as the flipped property, and it is why naive set theory had to be rebuilt. One theorem, read forward for the positive fixed points and backward for the impossibility results.

#Simulation: Lawvere Diagram

The parallel with Gödel is exact once you line them up:

Gödel did not secretly use category theory; historically he could not have. What category theory adds comes later and from a different direction: it isolates the shape of his argument and shows it was never really about formulas, machines, or sets. It was about a structural configuration: objects representing arrows, arrows composing, and a diagonal that feeds representation back into evaluation.

The eleventh lesson:

Category theory is the general language for recurring fixed-point structures.

The bridge from logic to category theory is forgetting the substrate. Gödel talks about formulas, Turing about machines, programming languages about recursive types, dynamics about iterated maps, renormalization about operators, probability about scale-invariant distributions. Category theory asks what remains once you erase the local material and keep only the arrows. That is abstraction as compression, not decoration: if the same proof shape appears in logic, computation, and set theory, then perhaps the proof was never about any of their particular contents. Depending on the setting, the fixed point it forces shows up as a Gödel sentence, an undecidable program, a recursive definition, a paradox, an initial algebra, or a terminal coalgebra. What is common is the skeleton.

#The Theoretical Arc Is Complete

We have now seen fixed points as the limits of iteration, the attractors of dynamics, the invariant sets of chaos, the scaling laws of distributions, the small-divisor constraints of arithmetic, and the diagonal fixed points of logic and computation. Both engines have been laid out: iteration, which turns a rule until something invariant survives, and self-reference, which lets a system act on its own description until a fixed point becomes unavoidable.

This is the place to say exactly why the two engines rhyme, and exactly why they are not the same. A Hutchinson attractor contains scaled copies of itself because a contractive rule on compact sets satisfies $K=\mathcal{H}(K)$. A Gödel sentence contains a claim about its own code because arithmetic can encode syntax and feed that code back into a formula template. Both produce an infinite regress from a fixed-point equation: copies inside copies on the geometric side, descriptions of descriptions on the logical side. But the theorems are different. The Hutchinson attractor does not refer to itself; the iterated function system describes nothing. The Gödel sentence does not stretch, fold, or contract a metric space. The ladder connects them because both are fixed-point phenomena, not because they are secretly the same object.

There is one transition left to make carefully, and it is the move from blackboard to world.

Formal self-reference happens when a system contains a description of one of its own expressions and can feed that description back into its rules. Living systems and markets are not formal systems, but they have the same three structural ingredients: an internal description, an interpreter for it, and feedback from the interpreter into the system’s future state.

This table is the bridge from formal self-reference to the lived world. A cell is not a theorem, and a market is not a lambda term. But each contains descriptions that participate in the very dynamics they describe. That is why the last two essays are not appendices stapled to a math survey. They are where the two engines visibly run together:

Engine A supplies the attractor structure. Bodies hold themselves inside viable states; markets move through regimes.

Engine B supplies the representational loop. Genomes help build the organisms that carry genomes; market models help create the prices that update the market models.

The final two essays apply this skeleton to the two self-referential systems we actually live inside: biology and markets.

#Further Reading

For logic, computation, and self-reference:

1. Kurt Gödel, On formally undecidable propositions of Principia Mathematica and related systems (1931). The incompleteness paper, where self-reference first becomes a theorem.
2. Alan Turing, On computable numbers, with an application to the Entscheidungsproblem (1936). The halting problem and the modern idea of computation.
3. Douglas Hofstadter, Gödel, Escher, Bach. Not the most formal source, but still one of the best ways to feel why self-reference matters.
4. Raymond Smullyan, Gödel’s Incompleteness Theorems. A gentler logical path into diagonalization.
5. Haskell Curry and Robert Feys, Combinatory Logic. A classical source for fixed-point combinators.
6. Henk Barendregt, The Lambda Calculus. The standard reference for lambda calculus and the Y combinator.

For category theory and the general shape of fixed points:

1. F. William Lawvere, Diagonal arguments and cartesian closed categories (1969). The categorical abstraction of diagonalization that unifies Gödel, Turing, and Cantor.
2. Joachim Lambek, A fixpoint theorem for complete categories (1968). The source of the algebraic view of recursive types.
3. Steve Awodey, Category Theory. A clean modern introduction.
4. Benjamin Pierce, Basic Category Theory for Computer Scientists. Short, practical, and good for programmers.
5. Bart Jacobs, Introduction to Coalgebra. A route from coalgebras to state-based systems and infinite behavior.
6. Alfred Tarski, A lattice-theoretical fixpoint theorem and its applications (1955). The order-theoretic fixed-point theorem behind many least and greatest fixed-point constructions.
7. Stephen Kleene, Introduction to Metamathematics. A classical source for computability and iterative least fixed points.
8. L. E. J. Brouwer, Uber Abbildung von Mannigfaltigkeiten (1911), and Shizuo Kakutani, A generalization of Brouwer’s fixed point theorem (1941). The topological and set-valued fixed-point theorems behind equilibrium arguments.