Lawvere's Fixed-point Theorem blows my mind

Lawvere's fixed-point theorem explains why self-reference is unavoidable in any system that allows for functions to be applied to themselves. It provides a mathematical way to understand the idea of "I" in self-reference.

Think of it like this:

• A statement that refers to itself.
• A program that reads and modifies its own code.
• A formula that says, "If proving me means I'm true, then I'm proved."

These kinds of self-referential structures often seem paradoxical or nonsensical. Lawvere's theorem helps us understand why these paradoxes arise.

The Core Idea: Russell's Paradox and Self-Reference

Imagine a set that contains descriptions of everything. Now, try to define the set of all things that don't describe themselves. Here's the problem:

• If the description includes itself, then it shouldn't be in the set.
• If it doesn't include itself, then it should be in the set.

This is Russell's paradox. The same kind of paradox appears in many areas of logic, mathematics, and even computer science.

Cartesian Closed Categories: The Setting for Lawvere's Theorem

Lawvere's theorem applies in a structure called a Cartesian closed category (CCC). Here's what that means:

1. Multiplication of objects (taking products).
2. A special object (terminal object) that acts like a "unit."
3. Exponentials: For any objects X and Y, you can form an object Y^X, which represents all possible maps from X to Y.

In standard set theory, Y^X represents all functions X → Y. In category theory, exponentials serve the same purpose, but in a more general setting.

There is also an evaluation map:

ev:(YX)×X→Y

which takes a function from X to Y and applies it to an input X. This evaluation behaves in a universal way, meaning it can describe every function application in the category.

Category theorists use this abstract approach because they prefer not to "look inside" objects. It's like how a strict vegan insists on keeping their lifestyle separate from certain foods—they avoid breaking the rules even when it might be convenient.

How Lawvere's Theorem Works

Lawvere's theorem uses exponentials to model self-reference. Here's how:

• Suppose we have an object X in a CCC and a function

  f:X→XX

  This means each element of X is assigned a function from X to X.

• Now, combine f with the evaluation map to define:

  δ:X→X

  This δ is called the diagonal map or self-application map.

• Lawvere's theorem states that if δ acts like a fixed-point operator (meaning there exists an x such that δ(x) = x), then there must be an element x such that f(x) maps x to itself.

In simpler terms:

• The object X contains a self-referential element.
• This element must describe itself in the way f defines.
• Self-reference is forced by the structure of the system.

Why This Matters: Gödel, Tarski, and Halting Problems

In set theory, this theorem explains diagonal arguments, like those used in:

• Gödel's incompleteness theorem: "This statement is unprovable."
• Tarski's undefinability theorem: "Truth cannot be defined within the same system."

The key idea is that once functions themselves become objects (via exponentials), self-reference becomes inevitable.

For example:

• Gödel's theorem builds a function from X to X^X that represents "provability" inside the system.
• Tarski's theorem does the same for "truth" inside the system.
• The Halting problem constructs a function that tries to analyze its own ability to decide halting.

Each case involves embedding a system inside itself, forcing it to evaluate its own rules. This always leads to contradictions or limitations.

The Big Picture

Lawvere's theorem tells us that any system capable of defining functions from objects to themselves will eventually run into paradoxes. You cannot build a system that fully captures its own behavior without creating a self-referential feedback loop.

If you try to define something like "this program decides if another program halts," you're inherently creating an arrow X → X^X, which lets the system analyze itself. That's exactly how Gödel's and Tarski's results work.

In the end, Lawvere's theorem formalizes why self-reference is inescapable. It proves that if you have a system rich enough to describe itself, paradoxes aren't just possible—they're guaranteed.

Growth: From microorganisms to megacities by Vaclav Smil (2019)

Not one of his Smil's best efforts but still very interesting. I appreciate the first chapter that outlines the math models of growth for fitting observations to the data and extrapolating. The author's scathing attacks against GDP growth as an indicator are also fantastic. 3/5 Stars.

A short stay in hell by Steven L. Peck (2012)

My youngest daughter told me to read this one, so I dropped what I was reading and read it in two days (it's short).  I claim to understand Georg Cantor's infinite orders of infinity and I also claim to understand the set theoretical difference between finite and infinite. I normally don't consider subjectively what it is like to live for a googolplex of years, before going on to a different existence for eternity.  This novella goes into enormous detail of one such experience.  I was obsessed with the story's concepts and even dreamed about the events in the story for a few days after reading it. The writing is not particularly good, but the ideas are well presented. 5/5 Stars.