License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2018.37
URN: urn:nbn:de:0030-drops-97049
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9704/
Go to the corresponding LIPIcs Volume Portal

Terui, Kazushige

MacNeille Completion and Buchholz' Omega Rule for Parameter-Free Second Order Logics

pdf-format:
LIPIcs-CSL-2018-37.pdf (0.5 MB)

Abstract

Buchholz' Omega-rule is a way to give a syntactic, possibly ordinal-free proof of cut elimination for various subsystems of second order arithmetic. Our goal is to understand it from an algebraic point of view. Among many proofs of cut elimination for higher order logics, Maehara and Okada's algebraic proofs are of particular interest, since the essence of their arguments can be algebraically described as the (Dedekind-)MacNeille completion together with Girard's reducibility candidates. Interestingly, it turns out that the Omega-rule, formulated as a rule of logical inference, finds its algebraic foundation in the MacNeille completion.
In this paper, we consider a family of sequent calculi LIP = cup_{n >= -1} LIP_n for the parameter-free fragments of second order intuitionistic logic, that corresponds to the family ID_{<omega} = cup_{n <omega} ID_n of arithmetical theories of inductive definitions up to omega. In this setting, we observe a formal connection between the Omega-rule and the MacNeille completion, that leads to a way of interpreting second order quantifiers in a first order way in Heyting-valued semantics, called the Omega-interpretation. Based on this, we give a (partly) algebraic proof of cut elimination for LIP_n, in which quantification over reducibility candidates, that are genuinely second order, is replaced by the Omega-interpretation, that is essentially first order. As a consequence, our proof is locally formalizable in ID-theories.

BibTeX - Entry

@InProceedings{terui:LIPIcs:2018:9704,
  author =	{Kazushige Terui},
  title =	{{MacNeille Completion and Buchholz' Omega Rule for Parameter-Free Second Order Logics}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9704},
  URN =		{urn:nbn:de:0030-drops-97049},
  doi =		{10.4230/LIPIcs.CSL.2018.37},
  annote =	{Keywords: Algebraic cut elimination, Parameter-free second order logic, MacNeille completion, Omega-rule}
}

Keywords: Algebraic cut elimination, Parameter-free second order logic, MacNeille completion, Omega-rule
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI