Logic and Foundations: Leverage Map

A. EXISTENCE JUSTIFICATION

Mathematics almost destroyed itself.

The crisis (1895-1930): Cantor’s set theory gave mathematics infinite collections, cardinal arithmetic, a new foundation. Then Russell found his paradox: the set of all sets that don’t contain themselves—does it contain itself? If yes, then no; if no, then yes. Contradiction.

This wasn’t a minor glitch. Set theory was supposed to be the foundation. If the foundation was contradictory, all mathematics was suspect.

The foundational programs:

Gödel’s revolution (1931): Any sufficiently powerful consistent formal system:

1. Contains true statements it cannot prove (incompleteness)
2. Cannot prove its own consistency (second incompleteness theorem)

Hilbert’s dream—prove mathematics consistent by finitary means—was impossible. Mathematics cannot fully justify itself.

The aftermath: We learned to live with incompleteness. Set theory (ZFC) became the working foundation despite being incomplete and not provably consistent. Alternative foundations emerged (type theory, category theory, HoTT). The crisis became a feature: foundational pluralism.

The core insight: The line between syntax (formal symbols) and semantics (meaning, truth) is both crucial and subtle. Gödel showed they can’t be collapsed. Tarski showed truth can’t be defined internally. Yet the interplay between them is where mathematics lives.

B. CORE OBJECTS & MORPHISMS

Set theory objects:

The ZFC axioms:

Model theory objects:

Proof theory objects:

Computability objects:

Morphisms:

• Set theory: functions, injections, bijections, elementary embeddings
• Model theory: homomorphisms, embeddings, elementary embeddings
• Computability: Turing reductions, many-one reductions

C. CENTRAL INVARIANTS

Cardinality (set theory):

Cantor’s theorem: |𝒫(A)| > |A| always. There’s no largest cardinal.

Continuum Hypothesis (CH): 𝔠 = ℵ₁ (no cardinals between ℕ and ℝ).

Status: Independent of ZFC! (Gödel: consistent with ZFC; Cohen: so is ¬CH)

Cofinality: cf(κ) = smallest cardinality of unbounded subset.

Regular cardinals: cf(κ) = κ. Singular: cf(κ) < κ.

Model-theoretic invariants:

Proof-theoretic invariants:

Computability invariants:

What counts as “the same”:

• Sets: bijection (same cardinality)
• Structures: isomorphism (same up to relabeling)
• Theories: bi-interpretability
• Degrees: Turing equivalence

D. SIGNATURE THEOREMS

1. Gödel’s First Incompleteness Theorem

Any consistent formal system F capable of expressing basic arithmetic contains a sentence G such that neither G nor ¬G is provable in F.

The construction: G says “I am not provable in F” (self-reference via Gödel numbering). If F proves G, then G is false (F proves a falsehood) → F is inconsistent. If F proves ¬G, then G is true (G is unprovable) but F proves ¬G → F is ω-inconsistent. So neither is provable.

Importance: Mathematics cannot be complete. There will always be true statements beyond any given system’s reach. This isn’t a flaw in our axioms—it’s a necessary feature of any sufficiently strong system.

2. Gödel’s Second Incompleteness Theorem

If F is consistent and sufficiently strong, then F cannot prove Con(F).

Importance: Hilbert wanted to prove mathematics consistent using “finitary” (weak) methods. Gödel showed: a system can’t even prove its own consistency, let alone be proved consistent by something weaker. Self-justification is impossible.

Caveat: F can prove “if F is consistent, then Con(F) is not provable”—the second theorem is itself provable!

3. Gödel’s Completeness Theorem (First-Order Logic)

A sentence φ is provable from axioms T if and only if φ is true in every model of T.

$$T \vdash \phi \iff T \models \phi$$

Importance: Syntax (proof) and semantics (truth in models) coincide for first-order logic. This is miraculous—not true for second-order logic or most other systems.

The duality: Completeness (soundness + this theorem) says the proof system is exactly right. Incompleteness says there aren’t enough axioms. These don’t contradict: completeness is about the logic; incompleteness is about specific theories.

4. Compactness Theorem

A set of sentences T has a model iff every finite subset has a model.

Importance:

This is a finiteness result—infinite consistency reduces to finite consistency.

Applications:

• Non-standard models (add “c > n” for all n; compactness gives infinite c)
• Transfer principles
• Model-theoretic proofs of combinatorial results

5. Löwenheim-Skolem Theorems

Downward: If T has an infinite model, it has a countable model. Upward: If T has an infinite model, it has models of all larger cardinalities.

Importance: First-order theories cannot pin down cardinality. Even the theory of real numbers has a countable model! (Skolem’s paradox—the model “thinks” it’s uncountable but externally it’s countable.)

This shows first-order logic is weak at distinguishing infinite sizes—a feature, not a bug, for many purposes.

6. Tarski’s Undefinability of Truth

Arithmetic truth is not definable in arithmetic.

Precise: There is no formula Truth(x) in the language of arithmetic such that for all sentences φ: $$\text{Truth}(\ulcorner \phi \urcorner) \iff \phi$$

Importance: Truth transcends any formal system. You can define “truth in L” in a richer language, but never internally. This is the semantic analog of Gödel’s syntactic incompleteness.

7. Church-Turing Thesis (not a theorem, but foundational)

The informal notion of “effectively computable” coincides with Turing-computable.

Why accepted: Multiple independent formalizations (Turing machines, lambda calculus, recursive functions, register machines) all define the same class. No counterexample has ever been found.

8. Undecidability of the Halting Problem

There is no algorithm to decide whether a given Turing machine halts on a given input.

Importance: Computation has absolute limits. Not “we haven’t found the algorithm”—no algorithm can exist. This is the computability analog of incompleteness.

The connection: The halting problem is essentially “does this proof search terminate?"—linking computability and provability.

E. BRIDGES TO OTHER DOMAINS

Pattern-linking gold:

The syntax/semantics duality:

Gödel completeness: these match for first-order logic. Gödel incompleteness: syntax can’t capture all semantic truth.

The hierarchy of strength:

Theories can be compared by consistency strength:

$$\text{PA} < \text{PA} + \text{Con(PA)} < \text{ZFC} < \text{ZFC} + \text{large cardinals} < …$$

Each level can prove the consistency of lower levels but not its own. The hierarchy extends “forever” through large cardinal axioms.

Computation and logic intertwined:

• A set is decidable ↔ its characteristic function is computable
• A set is c.e. ↔ it’s Σ₁ definable ↔ it’s the domain of a partial computable function
• The halting problem is the canonical non-computable c.e. set
• Post’s theorem: the arithmetical hierarchy corresponds to the Turing jump hierarchy

Forcing as method:

Cohen’s forcing proves independence results by constructing models. You “force” a new set to exist (or not exist) by building it through approximations. This is how we know CH is independent of ZFC.

Forcing is a general technique: set-theoretic forcing, arithmetic forcing, computability-theoretic forcing all exist.

F. COMMON MISCONCEPTIONS

1. “Gödel showed math is flawed/unreliable” — No. He showed formal systems can’t capture all truth. Mathematics continues just fine. The incompleteness is about formalization, not mathematical practice.

2. “Incompleteness means some things are unknowable” — Not quite. The Gödel sentence G is true (we can see this from outside). It’s unprovable in that system, but provable in a stronger one. Truth isn’t unknowable; it just transcends any single system.

3. “The Continuum Hypothesis is neither true nor false” — It’s independent of ZFC, but most set theorists believe it has a truth value—we just don’t know what axioms would settle it. Pluralists disagree, accepting multiple set-theoretic universes.

4. “ZFC is the only foundation” — Alternatives exist: type theory, category theory (ETCS), HoTT. They’re inter-interpretable in various ways. Foundation is somewhat conventional.

5. “Non-standard models are pathological” — They’re everywhere and useful! Non-standard analysis (infinitesimals), non-standard arithmetic (for proof theory), ultraproducts. “Standard” is relative to your perspective.

6. “First-order logic is the only logic” — Second-order, infinitary, modal, intuitionistic, linear, temporal—many logics exist for different purposes. First-order has nice properties (compactness, Löwenheim-Skolem, completeness) that others lack.

7. “Undecidability is just about Turing machines” — It’s about any notion of computation. Church-Turing thesis: all reasonable models agree. Undecidability is a fundamental limit, not an artifact of formalization.

8. “Large cardinals are speculative set theory” — They form a coherent hierarchy with remarkable structure. They have consequences for “small” mathematics (determinacy, descriptive set theory). They’re the main tool for calibrating consistency strength.

G. NOTATION SURVIVAL KIT

Set theory:

Logic:

Computability:

Proof theory:

H. ONE WORKED MICRO-EXAMPLE

Gödel’s self-reference: How G says “I am unprovable”

The setup:

We’re working in Peano Arithmetic (PA), which talks about natural numbers.

Step 1: Gödel numbering

Assign a unique number ⌜φ⌝ to each formula φ:

• ⌜0⌝ = some number
• ⌜S⌝ = another number
• ⌜0 = 0⌝ = encode the structure
• etc.

Now formulas ARE numbers. We can talk about formulas using arithmetic.

Step 2: Representability

The relation “n is the Gödel number of a proof of the formula with Gödel number m” is computable, hence representable in PA.

Define Prov(m) ≡ ∃n(n is a proof of m).

So Prov(⌜φ⌝) means “φ is provable in PA”—expressed inside PA.

Step 3: The diagonal lemma (fixed point)

For any formula ψ(x), there exists a sentence G such that: $$\text{PA} \vdash G \leftrightarrow \psi(\ulcorner G \urcorner)$$

G “says” ψ holds of G’s own Gödel number.

Step 4: Apply with ψ(x) = ¬Prov(x)

Get G such that: $$\text{PA} \vdash G \leftrightarrow \neg\text{Prov}(\ulcorner G \urcorner)$$

G says “I am not provable in PA.”

Step 5: The argument

If PA ⊢ G:

• Then Prov(⌜G⌝) is true (there exists a proof)
• So PA ⊢ Prov(⌜G⌝) (PA can verify proofs)
• But PA ⊢ G ↔ ¬Prov(⌜G⌝)
• So PA ⊢ ¬Prov(⌜G⌝)
• Contradiction! PA proves both Prov(⌜G⌝) and ¬Prov(⌜G⌝)
• So PA is inconsistent

If PA ⊢ ¬G:

• Then PA ⊢ Prov(⌜G⌝) (by the equivalence)
• So PA claims G is provable
• But actually G is not provable (we’re in the case PA ⊬ G)
• So PA proves something false
• PA is ω-inconsistent (unsound about existence claims)

Conclusion: If PA is consistent, PA ⊬ G. If PA is ω-consistent, PA ⊬ ¬G.

But is G true?

G says “G is not provable in PA.” We just showed G is not provable (assuming consistency). So G is TRUE but UNPROVABLE.

Micro-example 2: A non-standard model of arithmetic

Setup: Start with PA (Peano Arithmetic). Add constants c and axioms:

• c > 0
• c > 1
• c > 2
• … (c > n for each standard n)

Compactness: Every finite subset of these axioms has a model (just interpret c as a large enough standard number). By compactness, the whole set has a model.

The model 𝔐:

𝔐 satisfies all of PA plus “c is larger than every standard number.”

So c is an infinite natural number!

Structure of 𝔐:

The standard numbers sit at the bottom: 0, 1, 2, 3, …

Then come the non-standard numbers. They’re not a single chain—between any two non-standard numbers, there are infinitely many others. The non-standard part looks like ℤ × ℚ in a sense (copies of ℤ ordered densely).

Key properties:

• 𝔐 ≡ ℕ (same first-order truths—they satisfy the same sentences)
• 𝔐 ≇ ℕ (not isomorphic—different cardinality, or at least different structure)
• 𝔐 contains “infinite” primes, “infinite” proofs of bounded length, etc.

Importance:

Non-standard models show:

• First-order PA doesn’t pin down the natural numbers
• “Finite” has a first-order meaning (standard) and a meta meaning (actually finite)—these can differ
• Overspill: if φ(n) holds for all standard n, it holds for some non-standard n
• Proof-theoretic applications: analyze what PA “thinks” about proofs

Micro-example 3: The halting problem

Setup: Turing machines. Does machine M halt on input x?

Claim: The halting problem K = {(M, x) : M halts on x} is undecidable.

Proof (diagonalization):

Suppose H is a machine that decides K:

• H(M, x) = 1 if M halts on x
• H(M, x) = 0 if M doesn’t halt on x

Construct machine D:

• D(M) = if H(M, M) = 1 then loop forever; else halt

What does D(D) do?

• If H(D, D) = 1 (H says D halts on D), then D loops. But then D doesn’t halt on D. Contradiction.
• If H(D, D) = 0 (H says D doesn’t halt on D), then D halts. But then D halts on D. Contradiction.

Either way, contradiction. So H doesn’t exist. ∎

The diagonal structure:

D differs from each Mₙ on input Mₙ (diagonal). So D can’t be in the list of machines H handles correctly.

Connection to Gödel:

The halting problem is essentially “does this proof search halt?” If we could solve it, we could decide provability. Undecidability of halting ↔ incompleteness.

More precisely: the set of Gödel numbers of theorems is c.e. but not decidable (if consistent).

The Large Cardinal Hierarchy

Since you’re interested in deep structure, here’s a glimpse of the “upper atmosphere” of set theory:

The hierarchy (ascending strength):

Importance:

Large cardinals measure consistency strength. If Con(ZFC + measurable cardinal), then Con(ZFC + “Lebesgue measurable sets behave nicely”).

The hierarchy is linear (as far as we know)—every large cardinal notion compares with every other. This is remarkable and unexplained.

Large cardinals have consequences for “small” mathematics:

• Projective determinacy (from Woodin cardinals)
• Borel equivalence relations
• Properties of the real line

The inner model program:

For each large cardinal, try to build L-like models (fine structural, well-understood) that contain that cardinal. Success up to Woodin cardinals; open beyond.

Ultimate-L conjecture (Woodin):

There might be a “correct” inner model that settles CH and other independent questions. The large cardinal hierarchy might point toward the “true” V.

The Curry-Howard Correspondence

The slogan: Proofs are programs. Propositions are types.

Example:

The identity function λx.x has type A → A. This corresponds to the trivial proof of A → A.

The pairing function λx.λy.(x,y) has type A → B → A × B. This corresponds to the introduction rule for ∧.

Importance:

• Proof assistants (Coq, Lean, Agda) exploit this: write a program, get a proof
• Program extraction: prove ∃x.P(x), extract a program computing such x
• Type systems ARE logic: well-typed programs correspond to valid proofs
• HoTT extends this: identity types are paths, higher structure emerges

This connects to your HoTT leverage map! The correspondence is why HoTT works as both a foundation and a programming framework.

Leverage for your work:

Incompleteness and AI:

Any AI system based on formal reasoning faces Gödelian limits. A consistent system can’t prove its own consistency. An AI can’t fully verify its own correctness using only its own reasoning.

But: Humans also face these limits. We “transcend” them by moving to stronger systems—just as AI can. Incompleteness isn’t a special barrier to AI; it’s a universal feature of sufficiently powerful reasoning.

The halting problem and learning:

You can’t algorithmically predict whether an arbitrary computation halts. But you can:

• Predict for specific classes
• Give probabilistic answers
• Learn from data which programs likely halt

This is the learning-theoretic response to uncomputability: statistical inference where exact algorithms fail.

Model theory and neural networks:

Neural networks are structures in a model-theoretic sense. What first-order properties do they satisfy? What’s their expressive power?

Recent work: neural networks with certain architectures can express exactly certain logical fragments. The logic/network correspondence is being mapped.

Syntax/semantics and representation:

The syntax/semantics distinction is fundamental:

• Syntax: the symbols, their manipulation
• Semantics: what they mean, truth conditions

In neural networks:

• Weights/activations are syntax (the symbols)
• What they represent is semantics (the meaning)

Understanding this distinction might clarify representation learning: what does it mean for a network to “mean” something?

Foundations and cognitive architecture:

Different foundational approaches emphasize different things:

• Set theory: membership, hierarchy, well-foundedness
• Type theory: construction, typing, computation
• Category theory: mappings, universal properties, structure-preservation

If cognition has a “natural logic,” which foundation does it resemble? Your Convergence Thesis might say: the constraints force a particular foundational structure on any sapient mind.

Computability degrees and cognitive difficulty:

Not all uncomputable things are equally uncomputable. The Turing degrees form a rich structure. Some problems are “harder” than others in a precise sense (require more powerful oracles).

Cognitive difficulty might have analogous structure. Some tasks are harder than others, in ways that might map onto computability-theoretic hierarchies.

Self-reference and consciousness:

Gödel’s theorem requires self-reference: G talks about itself. Consciousness involves self-reference: awareness of awareness.

This analogy is suggestive but must be handled carefully. The formal self-reference (Gödel numbering) is precise; “consciousness is self-referential” is vague. Still, the logic of self-reference—fixed points, diagonalization, paradoxes—might illuminate self-models.

Forcing and possibility:

Forcing constructs models where things are different (CH true, CH false, etc.). This is a technique for exploring “possible mathematical universes.”

For cognitive architecture: what’s the space of possible minds? Forcing-style techniques might explore this: start with a base architecture, “force” modifications, see what’s consistent.

We now have 18 domains:

1. Representation Theory
2. Measure Theory
3. Homotopy Type Theory
4. Category Theory
5. Spectral Theory
6. Information Geometry
7. Differential Geometry
8. Algebraic Topology
9. Lie Theory
10. Dynamical Systems
11. Algebraic Geometry
12. Functional Analysis
13. Complex Analysis
14. Number Theory
15. Mathematical Physics
16. Information Theory
17. Probability Theory
18. Logic and Foundations