Logical structures and genus of proofs

Annals of Pure and Applied Logic 161 (2):139-149 (2010)
  Copy   BIBTEX

Abstract

Any arbitrarily complicated non-oriented graph, that is a graph of arbitrarily large genus, can be encoded in a cut-free proof. This unpublished result of Statman was shown in the early seventies. We provide a proof of it, and of a number of other related facts

Categories

Keywords

Reprint years

2009

DOI

10.1016/j.apal.2009.05.007

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,503

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Three logical theories.John Corcoran - 1969 - Philosophy of Science 36 (2):153-177.
Grammatical structures and logical deductions.Wojciech Buszkowski - 1995 - Logic and Logical Philosophy 3:47-86.
Aristotle's Use of Genos in Logic, Philosophy, and Science.Jeffrey Carr - 2007 - Peter Lang.
Logiki drzew derywacyjnych.Wojciech Krysztofiak - 2007 - Filozofia Nauki 2.
Combinatorics of first order structures and propositional proof systems.Jan Krajíček - 2004 - Archive for Mathematical Logic 43 (4):427-441.
A logical analysis of graphical consistency proofs.Atsushi Shimojima - 2002 - In L. Magnani, N. J. Nersessian & C. Pizzi (eds.), Logical and Computational Aspects of Model-Based Reasoning. Kluwer Academic Publishers. pp. 93--115.
New techniques and completeness results for preferential structures.Karl Schlechta - 2000 - Journal of Symbolic Logic 65 (2):719-746.
Probabilistic proofs and transferability.Kenny Easwaran - 2009 - Philosophia Mathematica 17 (3):341-362.
Kilka uwag o dowodzie w matematyce.Roman Murawski - 2013 - Filozofia Nauki 21 (1).
Quantified propositional logic and the number of lines of tree-like proofs.Alessandra Carbone - 2000 - Studia Logica 64 (3):315-321.
Systems of logical systems: Neuroscience and quantum logic. [REVIEW]Gin McCollum - 2002 - Foundations of Science 7 (1-2):49-72.

Analytics

Added to PP
2013-12-22

Downloads
28 (#564,813)

6 months
7 (#418,756)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

The undecidability of k-provability.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 53 (1):75-102.
Duplication of directed graphs and exponential blow up of proofs.A. Carbone - 1999 - Annals of Pure and Applied Logic 100 (1-3):1-67.
The undecidability of k-provability.Samuel Buss - 1991 - Annals of Pure and Applied Logic 53 (1):75-102.

Add more references