Postponement of $$\mathsf {raa}$$ and Glivenko’s Theorem, Revisited

Studia Logica - Tập 107 Số 1 - Trang 109-144 - 2019
Guerrieri, Giulio1, Naibo, Alberto2
1Dipartimento di Informatica – Scienza e Ingegneria (DISI), Alma Mater Studiorum–Università di Bologna, Bologna, Italy
2IHPST (UMR 8590), Université Paris 1 Panthéon–Sorbonne, CNRS, ENS, Paris, France

Tóm tắt

We study how to postpone the application of the reductio ad absurdum rule ( $$\mathsf {raa}$$ ) in classical natural deduction. This technique is connected with two normalization strategies for classical logic, due to Prawitz and Seldin, respectively. We introduce a variant of Seldin’s strategy for the postponement of $$\mathsf {raa}$$ , which induces a negative translation (a variant of Kuroda’s one) from classical to intuitionistic and minimal logic. Through this translation, Glivenko’s theorem from classical to intuitionistic and minimal logic is proven.

Tài liệu tham khảo

citation_journal_title=Higher-Order and Symbolic Computation; citation_title=A proof-theoretic foundation of abortive continuations; citation_author=ZM Ariola, H Herbelin, A Sabry; citation_volume=20; citation_issue=4; citation_publication_date=2007; citation_pages=403-429; citation_doi=10.1007/s10990-007-9007-z; citation_id=CR1 citation_journal_title=The Journal of Symbolic Logic; citation_title=Glivenko and Kuroda for simple type theory; citation_author=CE Brown, C Rizkallah; citation_volume=79; citation_issue=2; citation_publication_date=2014; citation_pages=485-495; citation_doi=10.1017/jsl.2013.10; citation_id=CR2 citation_journal_title=Reports on Mathematical Logic; citation_title=Subminimal logic and weak algebras; citation_author=R Ertola, M Sagastume; citation_volume=44; citation_publication_date=2009; citation_pages=153-166; citation_id=CR3 citation_journal_title=Archive for Mathematical Logic; citation_title=A short proof of glivenko theorems for intermediate predicate logics; citation_author=C Espíndola; citation_volume=52; citation_issue=7; citation_publication_date=2013; citation_pages=823-826; citation_doi=10.1007/s00153-013-0346-7; citation_id=CR4 citation_journal_title=Archive for Mathematical Logic; citation_title=Glivenko theorems and negative translations in substructural predicate logics; citation_author=H Farahani, H Ono; citation_volume=51; citation_issue=7; citation_publication_date=2012; citation_pages=695-707; citation_doi=10.1007/s00153-012-0293-8; citation_id=CR5 Ferreira, G., and P. Oliva, On the relation between various negative translations, in U. Berger, H. Diener, P. Schuster, and M. Seisenberger (eds.), Logic, Construction, Computation, vol. 3 of Ontos-Verlag Mathematical Logic Series. De Gruyter, 2012, pp. 227–258. citation_journal_title=Journal of Symbolic Logic; citation_title=Glivenko theorems for substructural logics over FL; citation_author=N Galatos, H Ono; citation_volume=71; citation_publication_date=2006; citation_pages=1353-1384; citation_doi=10.2178/jsl/1164060460; citation_id=CR7 citation_journal_title=Bulletins de la Classe des Sciences; citation_title=Sur quelques points de la logique de M. Brouwer; citation_author=V Glivenko; citation_volume=15; citation_issue=5; citation_publication_date=1929; citation_pages=183-188; citation_id=CR8 Guerrieri, G., and A. Naibo, Postponement of raa and Glivenko’s Theorem, Revisited (long version), ArXiv e-prints, http://arxiv.org/abs/1710.08854 , 2017. Kleene, S. C., Introduction to metamathematics, North-Holland, 1952. citation_journal_title=Nagoya Mathematical Journal; citation_title=Intuitionistische untersuchungen der formalistischen logik; citation_author=S Kuroda; citation_volume=2; citation_publication_date=1951; citation_pages=35-47; citation_doi=10.1017/S0027763000010023; citation_id=CR11 Murthy, C., Extracting Constructive Content From Classical Proofs, Ph.D. thesis, Cornell University, 1990. citation_journal_title=Journal of Logic and Computation; citation_title=Uniform provability in classical logic; citation_author=G Nadathur; citation_volume=8; citation_issue=2; citation_publication_date=1998; citation_pages=209-229; citation_doi=10.1093/logcom/8.2.209; citation_id=CR13 citation_journal_title=Annals of Pure and Applied Logic; citation_title=Glivenko theorems revisited; citation_author=H Ono; citation_volume=161; citation_issue=2; citation_publication_date=2009; citation_pages=246-250; citation_doi=10.1016/j.apal.2009.05.006; citation_id=CR14 Pereira, L. C., Translations and normalization procedures (abstract), in WoLLIC’2000—7th Workshop on Logic, Language, Information and Computation, pp. 21–24. www.cin.ufpe.br/~wollic/wollic2000/proceedings/anais.ps.gz , 2000. citation_title=On constructive fragments of classical logic; citation_inbook_title=Dag Prawitz on Proofs and Meaning; citation_publication_date=2015; citation_pages=281-292; citation_id=CR16; citation_author=LC Pereira; citation_author=EH Haeusler; citation_publisher=Springer von Plato, J., Elements of Logical Reasoning, Cambridge University Press, 2013. citation_journal_title=The Review of Symbolic Logic; citation_title=Normal derivability in classical natural deduction; citation_author=J Plato, A Siders; citation_volume=5; citation_publication_date=2012; citation_pages=205-211; citation_doi=10.1017/S1755020311000311; citation_id=CR18 citation_title=Natural Deduction: A proof-theoretical study; citation_publication_date=1965; citation_id=CR19; citation_author=D Prawitz; citation_publisher=Almqvist & Wiksell citation_journal_title=The Journal of Symbolic Logic; citation_title=On the proof theory of the intermediate logic MH; citation_author=JP Seldin; citation_volume=51; citation_issue=3; citation_publication_date=1986; citation_pages=626-647; citation_doi=10.2307/2274019; citation_id=CR20 citation_journal_title=Studia Logica; citation_title=Normalization and excluded middle. I; citation_author=JP Seldin; citation_volume=48; citation_issue=2; citation_publication_date=1989; citation_pages=193-217; citation_doi=10.1007/BF02770512; citation_id=CR21 citation_journal_title=The Journal of Symbolic Logic; citation_title=Normalization theorems for full first order classical natural deduction; citation_author=G Stålmarck; citation_volume=56; citation_issue=1; citation_publication_date=1991; citation_pages=129-149; citation_doi=10.2307/2274910; citation_id=CR22 Statman, R., Structural Complexity of Proofs, Ph.D. thesis, Stanford University, 1974. citation_title=Anti-Realism and Logic: Truth as eternal; citation_publication_date=1987; citation_id=CR24; citation_author=N Tennant; citation_publisher=Oxford University Press citation_journal_title=The Journal of Symbolic Logic; citation_title=On second order intuitionistic propositional logic without a universal quantifier; citation_author=K Zdanowski; citation_volume=74; citation_issue=1; citation_publication_date=2009; citation_pages=157-167; citation_doi=10.2178/jsl/1231082306; citation_id=CR25