Concept

Provability

The property of having a proof in a stated formal system, which is itself expressible inside the system when the system is strong enough. Read as a modal operator it obeys a complete and surprising set of laws, of which Löb's is the strongest.

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

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 Formal system Incompleteness Self-reference Arithmetisation Consistency Diagonal argument Frame Kripke model Modal logic Undecidable sentence

All concepts