Focused proof

According to the rules in the sequent calculus, formulas are canonically put into one of two classes called positive and negative e.g., in LK and LJ the formula ${\displaystyle \phi \lor \psi }$ is positive. The only freedom is over atoms are assigned a polarity freely. For negative formulas provability is invariant under the application of a right rule; and, dually, for a positive formulas provability is invariant under the application of a left rule. In either case one can safely apply rules in any order to hereditary sub-formulas of the same polarity.

In the case of a right rule applied to a positive formula, or a left rule applied to a negative formula, one may result in invalid sequents e.g., in LK and LJ there is no proof of the sequent ${\displaystyle B\lor A\implies A\lor B}$ beginning with a right rule. A calculus admits the focusing principle if when an original reduct was provable then the hereditary reducts of the same polarity are also provable. That is, one can commit to focusing on decomposing a formula and its sub-formulas of the same polarity without loss of completeness.

A sequent calculus is often shown to have the focusing property by working in a related calculus where polarity explicitly controls which rules apply. Proofs in such systems are in focused, unfocused, or neutral phases, where the first two are characterised by hereditary decomposition; and the latter by forcing a choice of focus. One of the most important operational behaviours a procedure can undergo is backtracking i.e., returning to an earlier stage in the computation where a choice was made. In focused systems for classical and Intuitionistic logic, the use of backtracking can be simulated by pseudo-contraction.

Let ${\displaystyle \uparrow }$ and ${\displaystyle \downarrow }$ denote change of polarity, the former making a formula negative, and the latter positive; and call a formula with an arrow neutral. Recall that ${\displaystyle \lor }$ is positive, and consider the neutral polarized sequent ${\displaystyle \downarrow \uparrow \phi \lor \psi \implies \uparrow \phi \lor \psi }$, which is interpreted as the actual sequent ${\displaystyle \phi \lor \psi \implies \phi \lor \psi }$. For neutral sequents such as this, the focused system forces on to make an explicit choice of which formula to focus on, denoted by ${\displaystyle \langle \,\rangle }$. To perform a proof-search the best thing is to chose the left formula, since ${\displaystyle \lor }$ is positive, indeed (as discussed above) in some cases there are no proofs where the focus is on the right formula. To overcome this, some focused calculi create a backtracking point such that focusing on the right yields ${\displaystyle \downarrow \uparrow \phi \lor \psi \implies \langle \phi \lor \psi \rangle ,\uparrow \phi \lor \psi }$, which is still as ${\displaystyle \phi \lor \psi \implies \phi \lor \psi }$. The second formula on the right can be removed only when the focused phase has finished, but if proof-search gets stuck before this happens the sequent may remove the focused component thereby returning to the choice e.g., ${\displaystyle \downarrow \uparrow B\lor A\implies \langle A\rangle ,\uparrow A\lor B}$ must be taken to ${\displaystyle \downarrow \uparrow B\lor A\implies \uparrow A\lor B}$ as no other reductive inference can be made. This is a pseudo-contraction since it has the syntactic form of a contraction on the right, but the actual formula doesn't exist i.e., in the interpretation of the proof in the focused system the sequent has only one formula on the right.