Satisfiability
Named by 3 essays across one field — each of them below, with the objects they name alongside it.
A formula is a corner of a cube
A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.
The tree that closes
To prove a formula, assume it false and take it apart. Every branch ends in a contradiction, or one of them describes exactly how it could have been false — and either way the tree is the answer, drawn.
An infinite tree has an infinite path
A tree that goes on forever, in which every node has only finitely many children, must contain a single branch that goes on forever. The proof is a rule for walking, and the rule is the whole of why finite information can decide an infinite question.
Named alongside it
The objects these essays reach for when they reach for this one.
AssignmentBranchingCompactnessCompletenessConnectiveDecision procedureFinite branchingGraph colouringHypercubeInfinite pathKonig lemmaLiteral