Concept

Formal system

A set of axioms and rules under which proofs are finite objects a machine could check. What such a system can say about its own proofs is itself a mathematical question, and the answers are the incompleteness theorems.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Also named here as incompleteness, provability — the same set of essays touches all of them, so they are one junction rather than several.

The diagonal, and the row built to be off the list. A table of rows of ones and zeros with the diagonal marked, and beneath it the row obtained by flipping every diagonal entry.

The sentence that says it has no proof

Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable.

logic · Diagonalisation

The frames on which provability makes sense, and the two that are refused. Six small frames marked by whether Löb's axiom is valid on them: transitive frames with no cycles accept it, and any frame in which a world can reach itself does not.

Necessity that means provable

Read the box as "the theory proves" and one modal logic stops being a proposal about what necessity might mean. It becomes a complete description of what a formal system can prove about its own proofs — and its frames run forward, compose, and stop.

logic · Modal logic

Named alongside it

The objects these essays reach for when they reach for this one.

Fixed point Incompleteness Provability Self-reference Arithmetisation Consistency Diagonal argument Frame Kripke model Modal logic Undecidable sentence

All concepts