Hypersequent Explained

In mathematical logic, the hypersequent framework is an extension of the proof-theoretical framework of sequent calculi used in structural proof theory to provide analytic calculi for logics that are not captured in the sequent framework. A hypersequent is usually taken to be a finite multiset of ordinary sequents, written

\Gamma _{1} ⇒ \Delta _{1} \mid … \mid \Gamma _{n} ⇒ \Delta _{n} The sequents making up a hypersequent are called components. The added expressivity of the hypersequent framework is provided by rules manipulating different components, such as the communication rule for the intermediate logic LC (Gödel–Dummett logic) (\Gamma _{1} ⇒ \Delta _{1} \mid ... \mid \Gamma _{n} ⇒ \Delta _{n} \mid \Sigma ⇒ A \Omega _{1} ⇒ \Theta _{1} \mid ... \mid \Omega _{m} ⇒ \Theta _{m} \mid \Pi ⇒ B)/(\Gamma _{1} ⇒ \Delta _{1} \mid ... \mid \Gamma _{n} ⇒ \Delta _{n} \mid \Omega _{1} ⇒ \Theta _{1} \mid ... \mid \Omega _{m} ⇒ \Theta _{m} \mid \Sigma ⇒ B \mid \Pi ⇒ A) or the modal splitting rule for the modal logic S5:^[1] (\Gamma _{1} ⇒ \Delta _{1} \mid ... \mid \Gamma _{n} ⇒ \Delta _{n} \mid \Box \Sigma, \Theta ⇒ \Box \Pi, \Omega)/(\Gamma _{1} ⇒ \Delta _{1} \mid ... \mid \Gamma _{n} ⇒ \Delta _{n} \mid \Box \Sigma ⇒ \Box \Pi \mid \Theta ⇒ \Omega)

Hypersequent calculi have been used to treat modal logics, intermediate logics, and substructural logics. Hypersequents usually have a formula interpretation, i.e., are interpreted by a formula in the object language, nearly always as some kind of disjunction. The precise formula interpretation depends on the considered logic.

Formal definitions and propositional rules

Formally, a hypersequent is usually taken to be a finite multiset of ordinary sequents, written

\Gamma _{1} ⇒ \Delta _{1} \mid ... \mid \Gamma _{n} ⇒ \Delta _{n}

The sequents making up a hypersequent consist of pairs of multisets of formulae, and are called the components of the hypersequent. Variants defining hypersequents and sequents in terms of sets or lists instead of multisets are also considered, and depending on the considered logic the sequents can be classical or intuitionistic. The rules for the propositional connectives usually are adaptions of the corresponding standard sequent rules with an additional side hypersequent, also called hypersequent context. E.g., a common set of rules for the functionally complete set of connectives

\{\bot,\to\} for classical propositional logic is given by the following four rules:l{G \mid \Gamma, p ⇒ p,\Delta} l{G \mid \Gamma, \bot ⇒ \Delta} (l{G)/(\mid) \Gamma, B ⇒ \Delta l{G} \mid \Gamma ⇒ A, \Delta } { l{G}\mid \Gamma, A \to B ⇒ \Delta } (l{G)/(\mid) \Gamma,A ⇒ B, \Delta } { l{G} \mid \Gamma ⇒ A \to B, \Delta }

Due to the additional structure in the hypersequent setting, the structural rules are considered in their internal and external variants. The internal weakening and internal contraction rules are the adaptions of the corresponding sequent rules with an added hypersequent context:

(l{G)/(\mid) \Gamma ⇒ \Delta } { l{G}\mid \Gamma, \Sigma ⇒ \Delta, \Pi } (l{G)/(\mid) \Gamma, A, A ⇒ \Delta } { l{G} \mid \Gamma, A ⇒ \Delta } (l{G)/(\mid) \Gamma ⇒ A, A, \Delta } { l{G} \mid \Gamma ⇒ A, \Delta }

The external weakening and external contraction rules are the corresponding rules on the level of hypersequent components instead of formulae:

(l{G)/() }(l{G)/(\mid) \Gamma ⇒ \Delta \mid \Gamma ⇒ \Delta } { l{G} \mid \Gamma ⇒ \Delta }

Soundness of these rules is closely connected to the formula interpretation of the hypersequent structure, nearly always as some form of disjunction. The precise formula interpretation depends on the considered logic, see below for some examples.

Main examples

Modal logics

Hypersequents have been used to obtain analytic calculi for modal logics, for which analytic sequent calculi proved elusive. In the context of modal logics the standard formula interpretation of a hypersequent

\Gamma _{1} ⇒ \Delta _{1} \mid ... \mid \Gamma _{n} ⇒ \Delta _{n}

is the formula

\Box ( w edge \Gamma _{1} \to v ee \Delta _{1)} \lor ... \lor \Box( w edge\Gamma _{n} \to v ee\Delta _{n)}

Here if

\Gamma is the multiset A _{1,} ... , A _{n} we write \Box \Gamma for the result of prefixing every formula in \Gamma with \Box , i.e., the multiset \Box A _{1,} ... , \Box A _{n} . Note that the single components are interpreted using the standard formula interpretation for sequents, and the hypersequent bar \mid is interpreted as a disjunction of boxes. The prime example of a modal logic for which hypersequents provide an analytic calculus is the logic S5. In a standard hypersequent calculus for this logic the formula interpretation is as above, and the propositional and structural rules are the ones from the previous section. Additionally, the calculus contains the modal rules(l{G)/(\mid) \Box \Gamma ⇒ A } { l{G} \mid \Box \Gamma ⇒ \Box A } (l{G)/(\mid) \Gamma, A ⇒ \Delta } { l{G} \mid \Gamma, \Box A ⇒ \Delta } (l{G)/(\mid) \Box \Gamma, \Sigma ⇒ \Box \Delta, \Pi } { l{G} \mid \Box \Gamma ⇒ \Box\Delta \mid \Sigma ⇒ \Pi }

Admissibility of a suitably formulated version of the cut rule can be shown by a syntactic argument on the structure of derivations or by showing completeness of the calculus without the cut rule directly using the semantics of S5. In line with the importance of modal logic S5, a number of alternative calculi have been formulated.^{[2] [3] [4] [5] [6] [7]} Hypersequent calculi have also been proposed for many other modal logics.^{[8] [9]}

Intermediate logics

Hypersequent calculi based on intuitionistic or single-succedent sequents have been used successfully to capture a large class of intermediate logics, i.e., extensions of intuitionistic propositional logic. Since the hypersequents in this setting are based on single-succedent sequents, they have the following form:

\Gamma _{1} ⇒ A _{1} \mid ... \mid \Gamma _{n} ⇒ A _{n}

The standard formula interpretation for such an hypersequent is

( w edge\Gamma _{1} \to A _{1)} \lor ... \lor ( w edge\Gamma _{n} \to A _{n)}

Most hypersequent calculi for intermediate logics include the single-succedent versions of the propositional rules given above and a selection of the structural rules. The characteristics of a particular intermediate logic are mostly captured using a number of additional structural rules. E.g., the standard calculus for intermediate logic LC, sometimes also called Gödel–Dummett logic, contains additionally the so-called communication rule:

(\Gamma _{1} ⇒ \Delta _{1} \mid ... \mid \Gamma _{n} ⇒ \Delta _{n} \mid \Sigma ⇒ A \Omega _{1} ⇒ \Theta _{1} \mid ... \mid \Omega _{m} ⇒ \Theta _{m} \mid \Pi ⇒ B)/(\Gamma _{1} ⇒ \Delta _{1} \mid ... \mid \Gamma _{n} ⇒ \Delta _{n} \mid \Omega _{1} ⇒ \Theta _{1} \mid ... \mid \Omega _{m} ⇒ \Theta _{m} \mid \Sigma ⇒ B \mid \Pi ⇒ A)

Hypersequent calculi for many other intermediate logics have been introduced,^{[10] [11] [12]} and there are very general results about cut elimination in such calculi.^[13]

Substructural logics

As for intermediate logics, hypersequents have been used to obtain analytic calculi for many substructural logics and fuzzy logics.^[14]

History

The hypersequent structure seem to have appeared first in under the name of cortege, to obtain a calculus for the modal logic S5. It seems to have been developed independently in, also for treating modal logics, and in the influential, where calculi for modal, intermediate and substructural logics are considered, and the term hypersequent is introduced.

References

1. Book: Avron, Arnon. Arnon Avron. 1996. The method of hypersequents in the proof theory of propositional non-classical logics. Logic: From Foundations to Applications. 1–32. 978-0-19-853862-2.
2. Mints. Grigori. Grigori Mints. 1971. On some calculi of modal logic. Proc. Steklov Inst. Of Mathematics. 98. 97–122.
3. Pottinger. Garrell. 1983. Uniform, cut-free formulations of T, S4 and S5 (abstract). J. Symb. Log.. 48. 3. 900.
4. Poggiolesi. Francesca. 2008. A cut-free simple sequent calculus for modal logic S5. Rev. Symb. Log.. 1. 3–15. 10.1017/S1755020308080040. 37437016.
5. Restall. Greg. John R. Steel. Dag. Normann. Ludomir. Newelski. Costas. Dimitracopoulos. 2007. Proofnets for S5: Sequents and circuits for modal logic. Logic Colloquium 2005. Lecture Notes in Logic. 28. 151–172. 10.1017/CBO9780511546464.012. 11343/31712. 9780511546464. free.
6. Book: Kurokawa, Hidenori. 2014. New Frontiers in Artificial Intelligence. 8417. 51–68. 10.1007/978-3-319-10061-6_4. 978-3-319-10060-9. Hypersequent Calculi for Modal Logics Extending S4. Lecture Notes in Computer Science.
7. Book: 10.1109/LICS.2013.47. From Frame Properties to Hypersequent Rules in Modal Logics. 2013 28th Annual ACM–IEEE Symposium on Logic in Computer Science. 408–417. 2013. Lahav. Ori. 978-1-4799-0413-6. 221813.
8. Indrzejczak. Andrzej. 2015. Eliminability of cut in hypersequent calculi for some modal logics of linear frames. Information Processing Letters. 115. 2. 75–81. 10.1016/j.ipl.2014.07.002.
9. Lellmann. Björn. 2016. Hypersequent rules with restricted contexts for propositional modal logics. Theor. Comput. Sci.. 656. 76–105. 10.1016/j.tcs.2016.10.004. free.
10. Ciabattoni. Agata. Agata Ciabattoni . Ferrari. Mauro. 2001. Hypersequent calculi for some intermediate logics with bounded Kripke models. J. Log. Comput.. 11. 2. 283–294. 10.1093/logcom/11.2.283.
11. Ciabattoni. Agata. Agata Ciabattoni . Maffezioli. Paolo. Spendier. Lara. 2013. Galmiche. Didier. Larchey-Wendling. Dominique. Hypersequent and Labelled Calculi for Intermediate Logics. Tableaux 2013. 81–96.
12. Baaz. Matthias. Ciabattoni. Agata. Agata Ciabattoni . Fermüller. Christian G.. 2003. Hypersequent Calculi for Gödel Logics – A Survey. J. Log. Comput.. 13. 6. 835–861. 10.1093/logcom/13.6.835. 10.1.1.8.5319.
13. Book: 10.1109/LICS.2008.39. From Axioms to Analytic Rules in Nonclassical Logics. 2008 23rd Annual IEEE Symposium on Logic in Computer Science. 229–240. 2008. Ciabattoni. Agata. Agata Ciabattoni . Galatos. Nikolaos. Terui. Kazushige. 978-0-7695-3183-0. 10.1.1.405.8176. 7456109.
14. Book: Proof theory for fuzzy logics. Metcalfe. George. Olivetti. Nicola. Gabbay. Dov. Dov Gabbay. Springer, Berlin. 2008.