Lesson 4.2 · Chapter 4: How bindings behave

Requirement and choice

Watch a requirement force one least world, while a choice leaves alternatives.

From John Cullen’s knotlab guide

Explore the idea

What must exist, and what remains a choice?

Select the rule, then change which facts are already present. An unselected fact is left open, not required to be absent.

Facts already present

A minimal world contains no extra item that could be removed while still satisfying the facts and rule.

starting factadded by the rule

One least world

{ A, B, c }

Each card includes the starting facts. In the choice example with c present, the alternatives are to add A or to add B; neither alternative is selected by the rule.

Worlds. This lesson reads 1 as "exists" and 0 as "does not exist". A world is then the set of things that exist in an allowed state: the variables that are 1. A world is minimal when no other allowed world lies inside it, and least when it lies inside every allowed world. Requirements are written as Horn clauses, clauses with at most one un-negated letter, such as ¬A ∨ ¬B ∨ c.

A requirement says what must exist when other things do: A ∧ B → c. A system of requirements has exactly one least world, and propagation finds it in linear time. Classical: van Emden and Kowalski 1976; Dowling and Gallier 1984.
Computation is a forced world. Carry each bit as which of two things exists, "x = 0" or "x = 1". Every gate then becomes four atoms, so every circuit runs as a least world. Classical: Horn satisfiability and monotone circuit value are complete for polynomial time. Checked: 4-bit addition comes out right for all 256 input pairs.
A choice says that when something exists, one of several things must: c → A ∨ B. With c present there are two minimal worlds, {A} and {B}, and nothing ranks them.
Requirement and choice are one knot read two ways. "A and B require c" becomes "c requires A or B" when false is read as "exists". 16 of the 34 two-loop knots are a pure requirement under one reading and a pure choice under the other. The other 18, parity among them, offer choices under both. Checked (knotlab choice).
Knots never select. Every variable of a knot takes both values, and fixing one loop's value removes it from the binding.

Propagation, in the first point, starts from the facts and adds whatever a requirement forces until nothing changes. Complete for polynomial time, in the second, means that every question in P translates into these two.

Reading. Requirements never select, since their world is unique. A choice leaves alternatives that the constraints do not rank. The program's interpretive stance is that coherent alternatives are equally real, with no global selector. The mathematics shows only that the constraints do not select. It neither proves nor refutes that stance.