Logica Universalis 14 (2):209-242 (2020)

Jaime Ramos
Universidad Nacional de Colombia
The essential structure of proofs is proposed as the basis for a measure of complexity of formulas in FOL. The motivating idea was the recognition that distinct theorems can have the same derivation modulo some non essential details. Hence the difficulty in proving them is identical and so their complexity should be the same. We propose a notion of complexity of formulas capturing this property. With this purpose, we introduce the notions of schema calculus, schema derivation and description complexity of a schema formula. Based on these concepts we prove general robustness results that relate the complexity of introducing a logical constructor with the complexity of the component schema formulas as well as the complexity of a schema formula across different schema calculi.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/s11787-020-00251-4
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Translate to english
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,355
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

The Collected Papers of Gerhard Gentzen.Gerhard Gentzen - 1969 - Amsterdam: North-Holland Pub. Co..
On the Idea of a General Proof Theory.Dag Prawitz - 1974 - Synthese 27 (1-2):63 - 77.

View all 10 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Abstract Complexity Definition.Mariusz Stanowski - 2011 - Complicity: An International Journal of Complexity and Education (2).
The Depth of Resolution Proofs.Alasdair Urquhart - 2011 - Studia Logica 99 (1-3):349-364.
Is Complexity a Scientific Concept?Paul Taborsky - 2014 - Studies in History and Philosophy of Science Part A 47:51-59.
The Role of Quantifier Alternations in Cut Elimination.Philipp Gerhardy - 2005 - Notre Dame Journal of Formal Logic 46 (2):165-171.
Effective Complexity: In Which Sense is It Informative?Esteban Céspedes & Miguel Fuentes - 2020 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 51 (3):359-374.
The Kolmogorov Complexity of Random Reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.
Complexity.John Urry - 2006 - Theory, Culture and Society 23 (2-3):111-115.


Added to PP index

Total views
14 ( #735,225 of 2,519,622 )

Recent downloads (6 months)
2 ( #271,073 of 2,519,622 )

How can I increase my downloads?


My notes