{"id":82,"date":"2024-04-24T07:01:34","date_gmt":"2024-04-24T07:01:34","guid":{"rendered":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/?p=82"},"modified":"2024-04-24T07:01:34","modified_gmt":"2024-04-24T07:01:34","slug":"discussing-nested-sequents-for-intuitionistic-logics","status":"publish","type":"post","link":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/2024\/04\/24\/discussing-nested-sequents-for-intuitionistic-logics\/","title":{"rendered":"Discussing \u201cNested Sequents for Intuitionistic Logics\u201d"},"content":{"rendered":"\n

(Link)<\/a><\/p>\n\n\n\n

Author:<\/strong> Melvin Fitting (City University of New York)<\/p>\n\n\n\n

Reference:<\/strong> M.\u00a0Fitting. Nested sequents for intuitionistic logics. Notre Dame Journal of Formal Logic, 55(1):41\u201361, 2014. https:\/\/doi.org\/10.1215\/00294527-2377869<\/p>\n\n\n\n

Why this paper?<\/strong> Cited by Syntactic Cut-Elimination for Intuitionistic Fuzzy Logic via Linear Nested Sequents<\/a> and Local Intuitionistic Modal Logics and Their Calculi<\/a><\/p>\n\n\n\n

About a year and a half ago I wrote about hypersequents<\/em><\/a>, a modification of the tried and trusted sequent calculus approach to structural proof theory. In that setting, instead of working with a single sequent (a set of premises alongside a set of possible conclusions) we work with a list of sequents. In this paper, we look at another such modification, called nested sequents<\/em> (sometimes, tree hypersequents<\/em>) in which the conclusions can contain both formulae and further nested sequents. The aim is the same: by defining communication rules between different sequents, we can give structural proof theory to logics that do not have a reasonable proof theory via conventional sequents.<\/p>\n\n\n\n

The concept of nested sequent has been rediscovered a few times, starting with work in the 90s by Ryo Kashima<\/a>. Fitting also showed, in a slightly earlier paper<\/a>, that these were essentially also a variation on an idea from the 70s called prefixed tableaux<\/em>. The paper we are reading today establishes nested sequent calculus and prefixed tableaux for intuitionistic logic, including a translation from tableaux to sequents (we are told that \u201cconversion in the other direction is also possible, but it is harder to describe and we omit it here\u201d). Of course, intuitionistic logic has had a conventional sequent calculus since the 30s, and Fitting does not even claim priority for nested sequents for intuitionistic logic \u2013 that goes to a group from my institution, Australian National University<\/a>. The goal here is to establish a clean and simple nested sequent calculus for intuitionistic logic which is amenable to extensions; modal logic is mentioned, and first-order quantifiers are investigated.<\/p>\n\n\n\n

It turns out that if we add first-order quantifiers to Fitting\u2019s calculus in a na\u00efve way we get, not standard intuitionistic first-order logic, but rather its \u2018constant domain\u2019 version. In this logic, the domain of quantification which our \u2200 and \u2203 connectives are interpreted over must be the same at each possible world. This property can be expressed in a single axiom, found by Grzegorczyk in the 60s. This system for constant domain logic is the main new contribution of the paper, as previous systems for this logic lacked appealing properties. We do also see how conventional intuitionistic first-order logic can also be handled, with some modest side conditions applied to the rules of the constant domain system.<\/p>\n","protected":false},"excerpt":{"rendered":"

About a year and a half ago I wrote about hypersequents, a modification of the tried and trusted sequent calculus approach to structural proof theory. In that setting, instead of working with a single sequent (a set of premises alongside a set of possible conclusions) we work with a list of sequents. In this paper, we look at another such modification, called nested sequents (sometimes, tree hypersequents) in which the conclusions can contain both formulae and further nested sequents. The aim is the same: by defining communication rules between different sequents, we can give structural proof theory to logics that do not have a reasonable proof theory via conventional sequents.<\/p>\n","protected":false},"author":10,"featured_media":83,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_share_on_mastodon":"0","_share_on_mastodon_status":"Catching up on my #blog writing with my second post in two days! I look at how a variation on the standard notion of sequent calculus led to new insights into structural #proofTheory for intuitionistic #logic. %permalink%"},"categories":[5],"tags":[97,95,19,94,92,96,93],"class_list":["post-82","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-summaries","tag-97","tag-city-university-of-new-york","tag-intuitionistic-logic","tag-melvin-fitting","tag-nested-sequent-calculus","tag-notre-dame-journal-of-formal-logic","tag-sequent-calculus"],"share_on_mastodon":{"url":"https:\/\/fediscience.org\/@RanaldClouston\/112324909173794890","error":""},"_links":{"self":[{"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/posts\/82","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/comments?post=82"}],"version-history":[{"count":1,"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/posts\/82\/revisions"}],"predecessor-version":[{"id":84,"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/posts\/82\/revisions\/84"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/media\/83"}],"wp:attachment":[{"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/media?parent=82"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/categories?post=82"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.fediscience.org\/the-updated-scholar\/wp-json\/wp\/v2\/tags?post=82"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}