Postponement of $$\mathsf {raa}$$ and Glivenko’s Theorem, Revisited
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