Concept

Decidability

Whether some procedure settles every instance of a question in finite time. A logic is decidable when a non-theorem always fails in a small enough model to be found by search, which propositional systems manage and systems with quantifiers generally do not.

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

How many colourings each knot allows. Three knots, and the number of ways their arcs can be coloured with three, five and seven colours under the crossing rule, beside the determinant computed separately from the same crossings.

Colours that count more than three

Three colours prove the trefoil is knotted and say nothing at all about the figure-eight, which refuses them exactly as an unknotted loop does. The repair is to stop colouring and start counting — with five colours, or seven, and with the arithmetic done modulo the number of them.

topology · Knots

The smallest algebra that refutes each formula. A table of formulas against the smallest finite Heyting algebra refuting each, found by searching every order on a few points, with the formulas no such algebra refutes marked.

Refutable in something small

A formula that is not a theorem of the constructive system fails in some finite algebra, and the algebra can be found by search. That single property is what makes the propositional logic decidable — and the predicate version loses the property and the decidability with it.

logic · Non classical logic

Named alongside it

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

Counting argument Double negation Excluded middle Exhaustive search Heyting algebra Intuitionistic logic Invariant Knot Knot determinant Linear system Modular arithmetic Open set

All concepts