Prove in first-order logic
First-order logic adds quantifiers over terms: forall x. A (∀x. A)
says that A holds for every x, and exists x. A (∃x. A) that it
holds for some x. prove decides such a sequent as it decides any
other. A proof names, for each ∃ it opens, the term it chose for x,
called the witness:
$ deduxit prove "p(a) & p(b), q(b) |- exists x. (p(x) * q(x))"
provable (MALL1, classical, focus engine)
───────────── ax ───────────── ax
⊢ ~p(b), p(b) ⊢ ~q(b), q(b)
──────────────────────────────── ⊗
⊢ ~p(b), ~q(b), p(b) ⊗ q(b)
───────────────────────────────── ∃
⊢ ~p(b), ~q(b), ∃x. (p(x) ⊗ q(x))
───────────────────────────────────────── ⊕₂
⊢ ~p(a) ⊕ ~p(b), ~q(b), ∃x. (p(x) ⊗ q(x))
The ∃ step fills x with the witness b. The proof passes the checker
before it is shown, as every proof deduxit reports does.
Write a first-order sequent
- An atom may be a predicate applied to terms, as in
p(x, f(a)). - A name bound by an enclosing quantifier is a variable. Any other name is a constant, or a function symbol when a bracket follows it.
- A symbol has one arity (number of arguments) throughout the sequent, and a name is a predicate or a function symbol, not both.
- A quantifier binds loosest. Its scope runs to the right as far as it can: to a closing bracket, a comma, the turnstile or the end.
- Every sequent is closed: it has no free variable.
seq print writes the one-sided form, where a negation swaps the
quantifiers. seq fragment names a first-order fragment with a 1 after
it, as in MLL1. A sequent whose atoms have arguments but which has no
quantifier is propositional, so its fragment has no 1 and every engine
decides it:
$ deduxit seq print "forall x. p(x) -o q(x), p(a) |- exists y. q(y)"
⊢ ∃x. (p(x) ⊗ ~q(x)), ~p(a), ∃y. q(y)
$ deduxit seq print "|- ∀x y. ~r(x, f(y)) ⅋ r(x, f(y)), (exists z. p(z))^"
⊢ ∀x. (∀y. (~r(x, f(y)) ⅋ r(x, f(y)))), ∀z. ~p(z)
$ deduxit seq fragment "forall x. p(x) |- p(a)"
MLL1
$ deduxit seq fragment "p(a), !p(a) -o q(f(a)) |- q(f(a))"
MELL
The syntax chapter lists every connective (The syntax).
Read the verdict
Without the exponentials ! and ?, the search decides every sequent,
since MLL1 and MALL1 are decidable: "unprovable" means that no proof
exists. The order of quantifiers matters. ∀x. ∃y. r(x, y) does not give
∃y. ∀x. r(x, y), while the converse holds:
$ deduxit prove "p(a), p(a) -o q(f(a)) |- q(f(a))"
provable (MLL, classical, focus engine)
───────────── ax ─────────────────── ax
⊢ ~p(a), p(a) ⊢ ~q(f(a)), q(f(a))
────────────────────────────────────── ⊗
⊢ ~p(a), p(a) ⊗ ~q(f(a)), q(f(a))
$ deduxit prove "forall x. exists y. r(x, y) |- exists y. forall x. r(x, y)"; echo "exit $?"
unprovable (MLL1, classical, focus engine): the search was exhaustive
exit 1
$ deduxit prove -i "exists y. forall x. r(x, y) |- forall x. exists y. r(x, y)"
provable (IMLL1, intuitionistic, two-sided engine)
───────────────── ax
r(b, a) ⊢ r(b, a)
───────────────────── ∃R
r(b, a) ⊢ ∃y. r(b, y)
───────────────────────── ∀L
∀x. r(x, a) ⊢ ∃y. r(b, y)
─────────────────────────────── ∀R
∀x. r(x, a) ⊢ ∀x. (∃y. r(x, y))
───────────────────────────────────── ∃L
∃y. (∀x. r(x, y)) ⊢ ∀x. (∃y. r(x, y))
The focused engine decides a sequent with a quantifier in the classical modes, with Mix and in affine mode too. The two-sided engine decides it in the intuitionistic modes, affine included. Both find witnesses the same way:
- The witness of each
∃stays open as a variable until an axiom matches two atoms. The match fills it in (unification), never with a term that holds the variable itself. - Each
∀opens its formula with an eigenvariable: a fresh constant that stands for any term. It is kept out of every witness chosen before it. - Where one premise's witness fails the other premise, the search asks the first premise for another witness, and resumes that premise's search where it stopped.
A refutation may count atoms, as it does without quantifiers. A predicate with a bound variable in one of its atoms is counted over all its atoms, since an instance may be any of them:
$ deduxit prove "forall x. p(x), p(a) |- p(b)"; echo "exit $?"
unprovable (MLL1, classical, focus engine): p(…) occurs 1 more time on the left than on the right, every atom of the predicate counted, since one has a bound variable, so they cannot all meet in axioms; with -a (affine), an unused hypothesis is allowed
exit 1
With exponentials
First-order linear logic with exponentials is undecidable. The copy
bound and the three verdicts work as they do without quantifiers (Decide
a sequent): --copies N bounds how often a ? formula is
copied on one branch, and --copies none, the default, deepens the bound
while the time limit lasts. A sequent the search can neither prove nor
refute ends at the time limit as unknown.
$ deduxit prove --copies 2 "p(z), !forall x. (p(x) -o p(s(x))) |- p(s(s(z)))" | head -1
provable (MELL1, classical, focus engine)
$ deduxit prove -i --copies 6 "!(forall x. (p(x) -o p(x))), !(q -o r), !(r -o q), p(e) |- r"; echo "exit $?"
unprovable (IMELL1, intuitionistic, two-sided engine): the search was exhaustive
exit 1
The second sequent is refuted by the loop check. A sequent met again on
its own branch, as the same instance, is a loop, so a hypothesis under
! that leads back to where it started is refuted instead of being cut
at the copy bound. The memo remembers a failure for every renaming of
the witnesses it leaves open. --memo-limit 0 switches both off, and the
second sequent is then unknown at its copy bound.
Two bounds of their own cut a branch where the search would go further. A search that cut one is unknown, not unprovable:
--witness-depth N(64 by default) is the deepest term a witness is filled in with.--instances N(65536 by default) is the most instances of quantified formulas the search holds at once.
$ deduxit prove --witness-depth 2 "|- exists x. p(x), ~p(f(f(f(a))))" | sed 's/after .*;/after …;/'; echo "exit $?"
unknown (MLL1, classical, focus engine): the witness depth of 2 was reached after …; raise it with --witness-depth N
exit 3
For the same verdict on every machine, bound the search with --work-limit N or --copies N and lift the time limit with --timeout none.
--deterministic also makes the proof and --stats the same on every run.
Statistics and threads
On a first-order sequent --stats adds two counters: the unifications of
two literals tried, and the witnesses bound. In JSON they are
unifications and bindings, written only where they are not zero.
$ deduxit prove -q --deterministic --stats "p(a), p(b) & q(c) |- exists x. (p(x) * p(b))"
provable (MALL1, classical, focus engine)
stable sequents visited: 2
from the memo: 0
memo entries at most: 0
splits examined: 6
unifications tried: 5
metavariables bound: 3
units of work: 36
time: 391.45µs
On several threads (--jobs, and the pool that joins the first thread
by default), a first-order sequent is searched as a propositional one is:
the threads share the choices nearest the root. Only a choice where no
rule around it may ask its premise for another witness is shared:
$ deduxit prove -q -j 4 "p(a1), p(a2), p(a3), p(a4), q(b) |- (exists x. (p(x) * q(x))) * (exists x. p(x)) * (exists x. p(x)) * (exists x. p(x))"; echo "exit $?"
unprovable (MLL1, classical, focus engine): the search was exhaustive
exit 1
Prove step by step
In interact (Prove step by step) the quantifier
rules come in two kinds:
∀Rand∃L(∀one-sided) open the formula with a fresh eigenvariable, writtena,b, … (a letter no symbol of the sequent takes).∃Rand∀L(∃one-sided) take their witness after the rule's name. The witness is a term of the sequent's function symbols and of the eigenvariables of the∀Rand∃Lsteps below the goal. With no term, the witness stays open as$1,$2, … (a$that no formula holds), and a later axiom fills it by unification, orcloseby the search.
An open witness never takes an eigenvariable made after it, which would
stand in the conclusion of its own step. This is the eigenvariable
condition, and apply reports a breach by the eigenvariable's name.
undo of the step that filled a witness leaves it open again. save
keeps the witnesses and what fills them (the session's JSON at wire level
7, its instances, with each step's mark), so that undo in a session
resumed from its file drops what the step made, as in the session saved:
$ deduxit interact -i "exists y. forall x. r(x, y) |- forall x. exists y. r(x, y)"
> apply 0 0 ∃L
opened goal 1: 1: ∀x. r(x, a) ⊢ 0: ∀x. (∃y. r(x, y))
> apply 1 0 ∀R
opened goal 2: 0: ∀x. r(x, a) ⊢ 1: ∃y. r(b, y)
> rules 2 0
∀L (with a witness or none)
> apply 2 0 ∀L
opened goal 3: 1: r($1, a) ⊢ 0: ∃y. r(b, y)
> apply 3 0 ∃R a
opened goal 4: 0: r($1, a) ⊢ 1: r(b, a)
> apply 4 0 ax
closed; no goal is open: `proof` checks the proof
> undo
reopened goal 4: 0: r($1, a) ⊢ 1: r(b, a)
> close
goal 4: provable (IMLL1, intuitionistic, two-sided engine)
no goal is open: `proof` checks the proof
> proof
valid proof (intuitionistic)
───────────────── ax
r(b, a) ⊢ r(b, a)
───────────────────── ∃R
r(b, a) ⊢ ∃y. r(b, y)
───────────────────────── ∀L
∀x. r(x, a) ⊢ ∃y. r(b, y)
─────────────────────────────── ∀R
∀x. r(x, a) ⊢ ∀x. (∃y. r(x, y))
───────────────────────────────────── ∃L
∃y. (∀x. r(x, y)) ⊢ ∀x. (∃y. r(x, y))
A cut formula, like a witness, may use only the sequent's symbols (with
their arities) and the eigenvariables of the ∀R and ∃L steps below
the goal, quantifiers included. A cut on p(a) is then the lemma about
the a at hand, the instance of ∀x. p(x)'s body. cut refuses a name
the sequent lacks or has with another arity, and an eigenvariable of
another branch, by name:
$ printf 'apply 0 2 forallR\ncut 1 "r(a)" 1\ncut 1 "p(a)" 1\nclose\nproof\n' | deduxit interact -i "forall x. (p(x) -o q(x)), forall x. p(x) |- forall y. q(y)"
opened goal 1: 0: ∀x. (p(x) ⊸ q(x)), 1: ∀x. p(x) ⊢ 2: q(a)
error: the cut formula names r, which the sequent does not have with this arity and role: in a session with quantifiers, a cut formula may use only the sequent's symbols and the goal's eigenvariables
opened goal 2: 0: ∀x. p(x) ⊢ 1: p(a)
opened goal 3: 0: ∀x. (p(x) ⊸ q(x)), 2: p(a) ⊢ 1: q(a)
goal 2: provable (IMLL1, intuitionistic, two-sided engine)
goal 3: provable (IMLL1, intuitionistic, two-sided engine)
no goal is open: `proof` checks the proof
valid proof (intuitionistic)
─────────── ax ─────────── ax
p(a) ⊢ p(a) q(a) ⊢ q(a)
─────────── ax ──────────────────────────── ⊸L
p(a) ⊢ p(a) p(a), p(a) ⊸ q(a) ⊢ q(a)
─────────────── ∀L ────────────────────────────── ∀L
∀x. p(x) ⊢ p(a) ∀x. (p(x) ⊸ q(x)), p(a) ⊢ q(a)
─────────────────────────────────────────────────── cut
∀x. (p(x) ⊸ q(x)), ∀x. p(x) ⊢ q(a)
────────────────────────────────────── ∀R
∀x. (p(x) ⊸ q(x)), ∀x. p(x) ⊢ ∀y. q(y)
Check a first-order proof
The JSON form of a first-order sequent is written at wire level 7. Beside the propositional form's keys it has:
symbols: each symbol's name with its arity;fo: the first-order terms,{"B": n}a bound variable (0for the innermost quantifier's) and{"F": [symbol, [terms]]}an application;- the atoms as
{"P": [symbol, [terms]]}, and a quantifier as{"∀": body}or{"∃": body}; binders: the quantifiers' variable names, one per quantifier in the order of the terms.
$ deduxit seq json "forall x. p(x) |- p(a)"
{"version":7,"terms":[{"D":0},{"∃":0},{"V":1}],"roots":[1,2],"atoms":[{"P":[0,[0]]},{"P":[0,[1]]}],"symbols":[["p",1],["a",0]],"fo":[{"B":0},{"F":[1,[]]}],"binders":["x"],"antecedents":1}
A proof of a first-order sequent names, for every member under quantifiers, the terms its quantifiers were opened with:
- a
∀step its eigenvariable, a fresh constant the proof numbers, as{"∀": [member, eigenvariable, premise]}; - a
∃step its witness, a closed term, as{"∃": [member, term, premise]}.
The proof's instances list each member past the sequent's occurrences
as [occurrence, frame], and each frame as [parent, term]: the
innermost quantifier's term first, null past the outermost. The proof's
own terms follow the sequent's fo (an eigenvariable is {"E": k}).
check checks such a proof with the eigenvariable condition. An
eigenvariable that a ∀ step introduces is introduced by that step
alone, and only witnesses above it name it. One that no step introduces
is a constant outside the signature, a witness like any other. The
derivation writes every instance with its terms, the eigenvariables named
after letters no symbol takes:
$ echo '{"version":7,"sequent":{"terms":[{"D":0},{"∃":0},{"V":1}],"roots":[1,2],"atoms":[{"P":[0,[0]]},{"P":[0,[2]]}],"symbols":[["p",1],["a",0],["f",1]],"fo":[{"B":0},{"F":[1,[]]},{"F":[2,[1]]}],"binders":["x"],"antecedents":1},"nodes":[{"ax":[3,2]},{"∃":[0,2,0]}],"instances":{"members":[[1,0]],"frames":[[null,2]],"terms":[]}}' | deduxit check
valid proof of ⊢ ∃x. ~p(x), p(f(a)) (classical)
─────────────────── ax
⊢ p(f(a)), ~p(f(a))
──────────────────── ∃
⊢ ∃x. ~p(x), p(f(a))
Eliminate cuts
eliminate (Eliminate cuts) eliminates the cuts of a
first-order proof as it does a propositional one, in every mode that has
the cut. A cut may be on a formula with quantifiers or on an instance of
one. The key case of ∀ and ∃ cuts the instance of the ∀ formula's
body at the ∃ step's witness: the witness takes the eigenvariable's
place throughout the ∀ step's premise, its instances and the witnesses
above included. Where another cut still reads that premise, this happens
in a copy, and a copied ∀ step takes an eigenvariable of its own. A
copy is counted against --node-limit before it is made. Every step's
line writes the instance it cut with its terms.
Here cut.json proves ∀x. p(x) ⊢ p(a) through the cut formula
∀x. p(x), by a ∀ step against a ∃ step with the witness a:
$ echo '{"version":7,"sequent":{"terms":[{"D":0},{"∃":0},{"V":1},{"V":0},{"∀":3}],"roots":[1,2],"atoms":[{"P":[0,[0]]},{"P":[0,[1]]}],"symbols":[["p",1],["a",0]],"fo":[{"B":0},{"F":[1,[]]}],"binders":["x","x"],"antecedents":1,"cuts":[4]},"nodes":[{"ax":[7,8]},{"∃":[0,2,0]},{"∀":[3,0,1]},{"ax":[9,2]},{"∃":[5,1,3]},{"cut":[3,2,4]}],"instances":{"members":[[1,0],[4,0],[6,1]],"frames":[[null,2],[null,1]],"terms":[{"E":0}]}}' > cut.json
$ deduxit eliminate cut.json
1. the key case of ∀ and ∃ on the cut of ∀x. p(x)
2. the axiom case on the cut of p(a)
cut-free proof of ⊢ ∃x. ~p(x), p(a) (classical) after 2 steps
───────────── ax
⊢ p(a), ~p(a)
───────────────── ∃
⊢ ∃x. ~p(x), p(a)
$ deduxit eliminate -i --steps=1 cut.json
1. the key case of ∀ and ∃ on the cut of ∀x. p(x)
proof of ∀x. p(x) ⊢ p(a) (intuitionistic) with 1 cut left after 1 step: the elimination took the most steps allowed, 1; --steps N allows more
─────────── ax
p(a) ⊢ p(a)
─────────────── ∀L ─────────── ax
∀x. p(x) ⊢ p(a) p(a) ⊢ p(a)
──────────────────────────────── cut
∀x. p(x) ⊢ p(a)
What quantifiers do not have yet
- Proof nets refuse a quantifier, with the exit status 2 of an error.
- A Rocq certificate of a first-order proof is written for deduxit's own Rocq library (Check a certificate in Rocq); NanoYalla's kernel has no quantifiers.
- A first-order proof has no lambda-term (Read a proof as a program).
$ deduxit prove --net "forall x. p(x) |- p(a)"; echo "exit $?"
error: proof nets exist for MLL without units only, not for MLL1
exit 2