This work is a tribute to the combinatorial nature of logical objects (formulas, sequents, proofs). In particular, we investigate the combinatorics of proof nets, that is pure geometrical objects, issued from the study of linear logic, intended to capture essential aspects of proofs in sequent calculus; in fact, proof nets can be obtained from proof structures (pure combinatorial nets of rules (or links)) by adding a constraint known as correctness criterion. In trying to establish the exact ratio between proof structures and proof nets in the multiplicative fragment of linear logic, we obtain an upper bound and a lower bound.

On the number of provable formulas

PIAZZA MARIO
;
PEDICINI MARCO;
2021

Abstract

This work is a tribute to the combinatorial nature of logical objects (formulas, sequents, proofs). In particular, we investigate the combinatorics of proof nets, that is pure geometrical objects, issued from the study of linear logic, intended to capture essential aspects of proofs in sequent calculus; in fact, proof nets can be obtained from proof structures (pure combinatorial nets of rules (or links)) by adding a constraint known as correctness criterion. In trying to establish the exact ratio between proof structures and proof nets in the multiplicative fragment of linear logic, we obtain an upper bound and a lower bound.
2021
Settore M-FIL/02 - Logica e Filosofia della Scienza
Fourth Pisa Colloquium in Logic, Language and Epistemology
Edizioni ETS
8846755197
File in questo prodotto:
File Dimensione Formato  
On the number of provable formulas.pdf

Accesso chiuso

Tipologia: Published version
Licenza: Non pubblico
Dimensione 405.85 kB
Formato Adobe PDF
405.85 kB Adobe PDF   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11384/109968
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact