Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Translate a sequent and find its interpolant

deduxit turns a sequent of ordinary logic into another and checks what the change promises before it prints the result. Two changes are built: the negative translations of classical logic into intuitionistic and minimal logic, and Craig interpolants.

Translate classical logic into a weaker one

A negative translation turns a classical sequent into one that a weaker logic proves exactly when classical logic proves the first. seq translate prints the translation, decides the sequent in classical logic and its translation in the weaker logic, and prints both verdicts:

$ deduxit seq translate 'a \/ ~a'
Kolmogorov's translation into minimal logic: ⊢ ¬¬(¬¬a ∨ ¬¬¬¬¬a)
classical logic: valid, a checked derivation of LK (3 inferences)
minimal logic: valid, a checked derivation of LJ (65 inferences)
The verdicts agree, as Kolmogorov's translation claims.

--by names the translation:

--bywhat it doesthe logic it reaches
kolmogorov (the default)¬¬ before every subformulaminimal logic
godel-gentzen¬¬ before every atom, and A ∨ B as ¬(¬A ∧ ¬B)minimal logic
kuroda¬¬ before every formula of the sequentintuitionistic logic
glivenko¬¬ before the formula right of ⊢intuitionistic logic

Several formulas right of ⊢ are translated as their disjunction. In propositional logic Kuroda's translation adds no more than ¬¬ before each formula: the rest of it acts on quantifiers. Glivenko's theorem says that ⊢ A holds classically exactly when ⊢ ¬¬A holds intuitionistically:

$ deduxit seq translate --by glivenko '~~a -> a'
Glivenko's translation into intuitionistic logic: ⊢ ¬¬(¬¬a → a)
classical logic: valid, a checked derivation of LK (4 inferences)
intuitionistic logic: valid, a checked derivation of LJ (16 inferences)
The verdicts agree, as Glivenko's translation claims.

--to intuitionistic translates by Kolmogorov's or Gödel and Gentzen's translation into intuitionistic logic, which proves what minimal logic proves. Kuroda's and Glivenko's translations do not reach minimal logic, and --to minimal with them is an error.

A sequent that is not valid stays not valid, and each verdict comes with the countermodel that shows it:

$ deduxit seq translate --by godel-gentzen 'a |- b'; echo "exit $?"
Gödel and Gentzen's translation into minimal logic: ¬¬a ⊢ ¬¬b
classical logic: not valid, a checked Kripke model refutes it:
  world 0 (the model's world): forces a
minimal logic: not valid, a checked Kripke model refutes it:
  world 0 (the model's world): forces nothing; below 1
  world 1: forces a; below 2
  world 2: forces a
The verdicts agree, as Gödel and Gentzen's translation claims.
exit 1

The exit status is 0 where both verdicts are valid, 1 where neither is and 3 where a search stopped at a limit. Verdicts that differ would be a defect of deduxit; the command reports it as an error, exit status 2.

Find an interpolant

Split a valid sequent into two halves. An interpolant is a formula I that the first half proves, that proves the second half, and whose atoms are in both halves. For A ⊢ B that is A ⊢ I and I ⊢ B:

$ deduxit interpolate 'a /\ b |- b \/ c'
interpolant: b
a ∧ b ⊢ b: valid, a checked derivation of LK (3 inferences)
b ⊢ b ∨ c: valid, a checked derivation of LK (3 inferences)

By default the formulas left of ⊢ are the first half and those right of it the second. --first names the first half's formulas instead, L0 being the first formula left of ⊢ and R0 the first right of it. In classical logic the first half may hold formulas right of ⊢: the interpolant then goes right of ⊢ in the first half.

$ deduxit interpolate --first L0,R0 'a, b |- a /\ b, c'
interpolant: ¬b
a ⊢ a ∧ b, ¬b: valid, a checked derivation of LK (6 inferences)
¬b, b ⊢ c: valid, a checked derivation of LK (3 inferences)

--logic names the logic, classical by default. In intuitionistic and minimal logic the formula right of ⊢ is always in the second half:

$ deduxit interpolate --logic intuitionistic --first L1 'a, a -> b |- b'
interpolant: a → b
a → b ⊢ a → b: valid, a checked derivation of LJ (1 inference)
a → b, a ⊢ b: valid, a checked derivation of LJ (5 inferences)

deduxit reads the interpolant off a derivation without cuts by Maehara's method, and checks it before it prints it: it decides both halves again and compares the atoms. A sequent that is not valid has no interpolant:

$ deduxit interpolate 'a |- b'; echo "exit $?"
classical logic: not valid, a checked Kripke model refutes it:
  world 0 (the model's world): forces a
A sequent that is not valid has no interpolant.
exit 1

The exit status is 0 for a checked interpolant, 1 for a sequent that is not valid, 3 where a search stopped at a limit (by default after 2 s, --timeout) and 2 for an error.

JSON output

--format json writes the whole answer as one document at wire level 16. seq translate writes {"version", "deduxit", "translation", "target", "agreement", "sequent", "translated", "classical", "decided"}: both sequents, both outcomes with their derivations or countermodels, and agreement, which is valid, not_valid or unknown. interpolate writes {"version", "deduxit", "logic", "partition", "outcome", "interpolant"}: the positions of the first half, the sequent's outcome, and the interpolant's text with its first and second halves, each a sequent with its outcome.

In a program, deduxit::ordinary::negative::compare and deduxit::ordinary::interpolant::interpolate return the same answers, and the web bindings' ordinary_translate and ordinary_interpolate answer the same JSON.