Scroll nets
Pablo Donato · 2025
Read Scroll nets by Pablo Donato (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19689.txt.
Introduction
Pablo Donato brings in a new way to write logical proofs in this two thousand twenty-five paper on logic. Scroll nets stand for proofs in propositional logic. Their base construct, the scroll, is a topological notation for implication. Charles Sanders Peirce made it in the late nineteenth century for his diagrammatic existential graphs. Donato takes scroll nets from those graphs with the Curry-Howard methodology. Inference rules are taken in, inside judgments. That is how typed terms take in deduction rules.
The work centers on the intuitionistic implicative fragment. It starts from a natural diagrammatic representation of scroll nets. It then pulls their combinatorial essence into a pure graph-theoretic definition. A notion of detour backs a sketched elimination procedure like cut elimination in proof theory. The author also shows how to simulate normalization in the simply typed lambda calculus. That shows the frame's logical and computational expressivity.
Catalog record
| CREATOR | Pablo Donato |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-19689
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scroll nets Pablo Donato Abstract We introduce a new formalism for representing proofs in propositional logic called “scroll nets”. Its fundamental construct is the scroll, a topological notation for implication proposed by C. S. Peirce at the end of the 19th century as the basis for his diagrammatic system of existential graphs (EGs). Scroll nets are derived from EGs by following the Curry-Howard methodology of internalizing inference rules inside judgments, just as terms in type theory internalize natural deduction rules. We focus on the intuitionistic implicative fragment of EGs, starting from a natural diagrammatic representation of scroll nets, and then distilling their combinatorial essence into a purely graph-theoretic definition. We also identify a notion of detour, that we use to sketch a detour-elimination procedure akin to cut-elimination. We illustrate how to simulate normalization in the simply typed λ \lambda -calculus, demonstrating both the logical and computational expressivity of our framework. Charles University, [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003790.10003792¡/concept_id¿ ¡concept_desc¿Theory of computation Proof theory¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10011740¡/concept_id¿ ¡concept_desc¿Theory of computation Type theory¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10003798¡/concept_id¿ ¡concept_desc¿Theory of computation Equational logic and rewriting¡/concept_desc¿ ¡concept_significance¿100¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003753.10003759¡/concept_id¿ ¡concept_desc¿Theory of computation Interactive computation¡/concept_desc¿ ¡concept_significance¿100¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Proof theory ccs Theory of computation Type theory ccs Theory of computation Equational logic and rewriting ccs Theory of computation Interactive computation keywords deep inference, graphical calculi, existential graphs, Curry-Howard correspondence, simple type theory, cut-elimination † † runningauthor: Pablo Donato † † copyright: Pablo Donato † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Graphical proof theory Traditionally, proof theory has been established as a branch of symbolic logic: it embodies par excellence the Hilbertian ideal according to which any mathematical concept can be expressed as a finite sequence of symbols , with reasoning reduced to the sequential manipulation of these symbols . However, several recent developments tend to demonstrate that a finer analysis of the structure of formal proofs is possible with the help of graphical or diagrammatic representations: popular examples include Girard’s proof nets in linear logic [ 3 ] , string diagrams in categorical logic [ 12 ] , and Hughes’ combinatorial proofs [ 9 ] . The idea is to abstract from the arbitrary sequentiality suggested by a linguistic usage of symbols , by immersing statements and proofs in space to better understand their geometry. One aim is to find a solution to Hilbert’s 24th problem by devising a good notion of equality among proofs [ 26 ] . However, current research focuses almost exclusively on the structure of completed proofs, forgetting the sequential inference process that enabled their construction. This prevents in particular the application of these new methodologies to the design of interactive theorem provers ( ITPs ), which are fundamentally based on the incremental construction of partial proofs. Existential graphs To tackle this limitation, we investigate a graphical system mostly forgotten by contemporary proof theorists, probably because it predates the existence of proof theory itself: C. S. Peirce’s existential graphs [ 21 ] (“ EGs ” hereafter). It is based on a purely diagrammatic and topological representation of logical constants, inspired by a dialogical understanding of reasoning a century before the advent of game semantics [ 20 ] . Proving is then modelled as a dynamic process of constructing valid statements through rewriting of diagrams, using six elementary inference rules that perform insertions and deletions of graphs at a single specified location. Figure 3 illustrates how to derive modus ponens in EGs , starting from a graph of the statement a\land(a\Rightarrow b) and reducing it to b . We refer the reader to [ 2 , Sections 2–4] for a more detailed overview of the history of EGs . \captionsetup [subfigure]justification=centering {subfigure} [b]0.74 \vbox{\hbox{\includegraphics[width]{modusponens1.pdf}}}~~~\xrightarrow{{\color[rgb]{0,0.2969,0.3594}\text{\scriptsize$\mathsf{Deit}$}}}~~~\vbox{\hbox{\includegraphics[width]{modusponens2.pdf}}}~~~\xrightarrow{{\color[rgb]{0,0.2969,0.3594}\text{\scriptsize$\mathsf{Close}$}}}~~~\vbox{\hbox{\includegraphics[width]{modusponens3.pdf}}}~~~\xrightarrow{{\color[rgb]{0,0.2969,0.3594}\text{\scriptsize$\mathsf{Del}$}}}~~~\vbox{\hbox{\includegraphics[width]{modusponens4.pdf}}} {subfigure} [b]0.25 Figure 1: Dynamic proof trace Figure 2: Static proof object Figure 3: Modus ponens in scroll nets What is a proof? In order to contemplate the structure of (partial) proofs, one needs a way to represent them statically as bona fide proof objects . From our perspective, formalisms like Hilbert-style and Gentzen-style calculi conflate the final proof object with what we call the proof trace (usually called “derivation”), which is the history of inference steps that were undertaken to construct dynamically the proof object . On the other hand, graphical formalisms such as proof nets and combinatorial proofs forego the notion of inference rule altogether, and with it the whole proof trace . Although they are also graphical in nature, EGs somehow lay on the opposite end of the spectrum, together with string diagrams: they lack explicit syntax to capture the structure of proofs, leaving it implicit and mangled in the sequence of rewritings that represents the proof trace . In contrast, state-of-the-art ITPs such as Rocq [ 27 ] and Lean [ 15 ] do have distinct notions of proof trace and proof object : they are called respectively proof script and proof term . The full situation is summarized in Table 1 . Proof trace Proof object Hilbert calculi Derivation (sequence) Derivation (sequence) Gentzen calculi Derivation (tree) Derivation (tree) Rocq/Lean Proof script (= tactic tree ) Proof term (= natural deduction tree ) Proof nets — Formula tree + Axiom/Cut permutation String diagrams Equational rewriting ( sequence ) — Existential graphs Illative transformations ( sequence ) — Scroll nets Illative transformations ( sequence ) EG DAG + Argumentation forest Table 1: Comparing representations of proofs in various formalisms Scroll nets The aim of the current paper is to introduce a language of proofs on top of the existing language of statements in EGs , in order to represent proof objects in addition to proof traces . A notable feature of EGs is that they identify the language of statements with the language of judgments : scribing some graph on the sheet of assertion is, by definition, the same as asserting its truth 1 1 1 This identification is also found in the original notation of Gentzen for natural deduction, where nodes in derivation trees are formulas rather than sequents [ 4 ] . . Following the Curry-Howard methodology, our goal is then to internalize inference rules — Peirce called them illative transformations — inside the syntax of statements, just like terms in type theory can be seen as a way to internalize and record derivation trees (in natural deduction) inside judgments. The syntax we have arrived at is based on the simple observation that all illative transformations can be expressed in terms of pure locations : they consist in either inserting/deleting an arbitrary graph at a given location, duplicating an arbitrary graph from a source location, or deduplicating an arbitrary graph from a target location. This gives rise to a directed forest whose nodes are the “ subgraphs ” of some EG and whose edges encode exactly illative transformations . This data structure is surprisingly close to the proof nets of linear logic, and because it is based on