THE FOLD / RESPAWN / THE CONTINUE / THE HERBRAND
THE HERBRAND
an infinity settled by a finite piece of itself
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
First-order logic quantifies over infinitely many things, so a refutation might seem to need infinitely much checking. Herbrand’s theorem (1930) says otherwise: if a set of clauses is unsatisfiable, then some finite set of ground instances — built by plugging in terms from the language itself — is already unsatisfiable propositionally. Expand far enough and an ordinary SAT solver settles it. That is the foundation every automated theorem prover still stands on. The catch is that the theorem gives no bound on how far, which is exactly why the search can run forever.
LIT verified live: grounding { P(a), ¬P(x)∨P(f(x)), ¬P(f(f(f(a)))) } over the Herbrand universe and running a real DPLL solver at each depth gives d=0: SAT, d=1: SAT, d=2: UNSAT, d=3: UNSAT, d=4: UNSAT, d=5: UNSAT; the shallow expansions are genuinely satisfiable — the contradiction is not yet visible; the set flips to unsatisfiable at depth 2 and stays so at every greater depth; and an infinite first-order question is thereby settled by a finite propositional one.
LIT verified live: grounding { P(a), ¬P(x)∨P(f(x)), ¬P(f(f(f(a)))) } over the Herbrand universe and running a real DPLL solver at each depth gives d=0: SAT, d=1: SAT, d=2: UNSAT, d=3: UNSAT, d=4: UNSAT, d=5: UNSAT; the shallow expansions are genuinely satisfiable — the contradiction is not yet visible; the set flips to unsatisfiable at depth 2 and stays so at every greater depth; and an infinite first-order question is thereby settled by a finite propositional one.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at THE CONTINUE — you expand to the next depth, and the next, with no way to know in advance which one settles it. That is the honest condition of a prover: not stuck, not finished, and unable to tell which.
AVAN (AI) made the SAT/UNSAT split load-bearing rather than decorative. It would have been easy to expand to a large depth, report UNSAT and call the theorem demonstrated — but that shows nothing, since a bad encoding can be unsatisfiable at every depth for the wrong reason. The page therefore checks that shallow expansions are satisfiable, which proves the solver is not simply always saying no, and that the flip is monotone once it happens. The DPLL here is real: unit propagation, splitting, backtracking. What this page does not do is prove the theorem — it exhibits one instance of it. Jacques Herbrand wrote the result in a thesis at 22 and died mountaineering the next year at 23.
AVAN (AI) made the SAT/UNSAT split load-bearing rather than decorative. It would have been easy to expand to a large depth, report UNSAT and call the theorem demonstrated — but that shows nothing, since a bad encoding can be unsatisfiable at every depth for the wrong reason. The page therefore checks that shallow expansions are satisfiable, which proves the solver is not simply always saying no, and that the flip is monotone once it happens. The DPLL here is real: unit propagation, splitting, backtracking. What this page does not do is prove the theorem — it exhibits one instance of it. Jacques Herbrand wrote the result in a thesis at 22 and died mountaineering the next year at 23.
3 ONE DIMENSION
Depth by depth. Satisfiable, satisfiable, and then never again.
4 TWO DIMENSIONS · INTERACTIVE
Expand the universe one term at a time and re-solve.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the Herbrand universe growing outward, one function application at a time.
AVAN’s addition (the inverse-companion): the forward reading is “the infinite reduces to the finite.” The inverse is that the reduction is real but unusable as a schedule. Herbrand guarantees a depth exists; nothing tells you which, so a prover that has not yet found a refutation cannot distinguish “not deep enough” from “no refutation exists.” Both look identical from inside — a search still running. Read backwards, the theorem does not make first-order logic decidable and was never going to; it converts an infinite question into an unbounded wait, which is a genuine improvement and is not the same as an answer.
LIT grounding { P(a), ~P(x)|P(f(x)), ~P(f(f(f(a)))) } over the Herbrand universe and running a real DPLL solver at each depth gives d=0: SAT, d=1: SAT, d=2: UNSAT, d=3: UNSAT, d=4: UNSAT, d=5: UNSAT; the shallow expansions are genuinely satisfiable so the solver is not simply always saying no; the set flips at depth 2 and stays unsatisfiable at every greater depth; and an infinite first-order question is thereby settled by a finite propositional one
FIG The SAT/UNSAT split is load-bearing rather than decorative: expanding to a large depth and reporting UNSAT would show nothing, since a bad encoding can be unsatisfiable at every depth for the wrong reason. So the page checks that shallow expansions ARE satisfiable and that the flip is monotone. The DPLL is real — unit propagation, splitting, backtracking. This exhibits one instance of the theorem; it does not prove it.
FIG The SAT/UNSAT split is load-bearing rather than decorative: expanding to a large depth and reporting UNSAT would show nothing, since a bad encoding can be unsatisfiable at every depth for the wrong reason. So the page checks that shallow expansions ARE satisfiable and that the flip is monotone. The DPLL is real — unit propagation, splitting, backtracking. This exhibits one instance of the theorem; it does not prove it.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CONTINUE · David Lee Wise (ROOT0), with AVAN