Logical tomography [Elektronische Ressource] : exposing the structural constituents of logic / vorgelegt von Michael Arndt

Sujets

• Mathematics

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2008
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Logical Tomography
Exposing the Structural Constituents of Logic
Dissertation
der Fakult¨at fu¨r Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universit¨at Tu¨bingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Michael Arndt
aus Bisingen
Tu¨bingen 2008Tag der mu¨ndlichen Qualifikation: 13. Februar 2008
Dekan: Prof. Dr. Michael Diehl
1. Berichterstatter: Prof. Dr. Peter Schroeder-Heister
2. Berichterstatter: Prof. Dr. Reinhard KahleAcknowledgments
I am grateful to all the people who have supported and encouraged me in the effort of
writingthisdissertation. Besidesthemanyfellowstudentsandfriendswhohaveindirectly
contributed to its materialisation through suggestions, discussions and references, there
are several people who were essential to the effort.
My deepest gratitude is to my supervisor, Peter Schroeder-Heister, who granted me
the invaluable liberty to do conceptional work, and who I consider to be exemplary in
conducting conceptual investigations of a foundational nature on a solid formal basis.
It was him who made me aware of the structural origins of the sequent calculus, which
subsequently became the focus of the present investigation. I am very grateful to my co-
supervisor, Reinhard Kahle, for his initial suggestion for an area of research for a thesis.
The fact that he remained my co-supervisor even though I eventually departed from that
idea is something I hold in high regard. I fondly remember the intensive introduction to
the sequent calculus that I received under the tutorage of Jo¨rg Hudelmaier. His matter-
of-factly understanding of complexity issues regardingthe calculus andhis ability to make
extremely concise presentations thereof remain unrivalled to this day and have left a deep
impression. Without any doubt do I owe my investment into this subject matter to him.
I owe gratitude to Uwe Mo¨nnich and Arnim von Stechow for supporting me into
their graduateprogramme“Integriertes Linguistikstudium”. In connection with that pro-
gramme, Fritz Hamm brought me into contact with algorithmic semantics of natural lan-
guage, and provided a second forum for exchanges and research, which I have appreciated
greatly. This researchwas conducted in cordialcooperationwith my fellow student Ralph
Albrecht, in whom I came to value both his wide range of academic interests and his sin-
gular diligence. My fellow graduate student Katja Jasinskaja had a remarkable impact on
my ownmotivation due to her extraordinarycombinationof a jaunty attitude and natural
determination. The essential technical idea I employ draws from Yiannis Moschovakis’
work on algorithms, and I am much obliged to him for his kind instructions and his pa-
tient clarifications thereof. I am thankful to Eleni Kalyvianakifor discussing her teacher’s
ideas with me in great detail on several occasions.
The diploma theses of Tobias Heindel and Birgit Henningsen picked up ideas that
were related to my dissertation, thereby allowing me to focus on the essentials. The
softwaretoolsdevelopedbyRainerLuedecke,StefanElserandAnn-CarolinUng¨anzgreatly
facilitated the production of the illustrations of graphs that occur in this work.
I am grateful to Thomas Piecha for the many discussions that, in as far as they often
touched upon matters of physics, both went beyond the traditionalscope of logic and also
touched upon some of the historical aspects of this investigation. Special thanks go to
Inga Binder for lending me the eye of a social scientist and for supporting me through
many good conversations.
This dissertation is dedicated to the memory of Adolf Breimesser, my grandfather.Contents
1 Introduction 9
I The Elements of Structural Reasoning 15
2 Paul Hertz – Satzsysteme 17
2.1 The Conception of Structural Logic . . . . . . . . . . . . . . . 17
2.2 Noteworthy Particularities . . . . . . . . . . . . . . . . . . . . 22
3 Gerhard Gentzen – The Logistic Calculus 31
3.1 The Union of Formal and Structural Logic . . . . . . . . . . . 31
3.2 A Comparison with Hertz’ Logic . . . . . . . . . . . . . . . . . 37
4 The Calculus RK 43
4.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 From LK to RK . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3 From General Rules to Local Rules . . . . . . . . . . . . . . . 55
II The Explosion Calculus 65
5 The Explosion Procedure 67
5.1 Elementary Structural Sequents . . . . . . . . . . . . . . . . . 68
5.2 Initialisation of the Sequent . . . . . . . . . . . . . . . . . . . 72
5.3 Detachment of a Complex Formula . . . . . . . . . . . . . . . 73
5.4 Application of the Local Logical Rule . . . . . . . . . . . . . . 78
6 Properties of the Explosion Procedure 83
6.1 Explosion Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.2 An Extensive Example . . . . . . . . . . . . . . . . . . . . . . 91
6.3 Uniqueness of the Explosion Set . . . . . . . . . . . . . . . . . 94
6.4 Further Examples . . . . . . . . . . . . . . . . . . . . . . . . . 98
57 Structural Representation of Meaning 101
7.1 The Base Structure of a Sequent . . . . . . . . . . . . . . . . . 102
7.2 The Structure of Complex Formulae . . . . . . . . . . . . . . . 105
8 Explosion Sets and RK-Derivations 117
8.1 Revisiting RK-Derivations . . . . . . . . . . . . . . . . . . . . 118
8.2 Connexion Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.3 Connexion Trees . . . . . . . . . . . . . . . . . . . . . . . . . 132
9 Decision Procedures on Explosion Sets 143
9.1 Cut-Actions on Connexion Sets . . . . . . . . . . . . . . . . . 145
9.2 A Simple Refutation Procedure . . . . . . . . . . . . . . . . . 151
9.3 Remarks on a Decision Procedure . . . . . . . . . . . . . . . . 161
III Logical Tomography 165
10 Hypergraphs and Bipartite Graphs 167
10.1 Directed Hypergraphs and Hyperarcs . . . . . . . . . . . . . . 169
10.2 Partial and Total Traversals . . . . . . . . . . . . . . . . . . . 177
11 Explosion Sets as Hypergraphs 187
11.1 Interpreting Explosion Sets . . . . . . . . . . . . . . . . . . . . 187
11.2 Connexion Sets and Strands . . . . . . . . . . . . . . . . . . . 190
12 Decision Procedures on Hypergraphs 197
12.1 Bridging Actions on Strands . . . . . . . . . . . . . . . . . . . 197
12.2 Partial Cycles and Co-Identity Arcs . . . . . . . . . . . . . . . 204
13 The Growth Procedure 211
14 Discussion 225
Appendix 227
A On Formula Occurrences 229
6List of Figures
3.1 Logical inference schemes of LK . . . . . . . . . . . . . . . . . 35
3.2 Structural inference schemes of LK . . . . . . . . . . . . . . . 36
4.1 Structural rules of RK . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Logical rules of RK . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3 Local logical rules . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.1 Logical meta rules. . . . . . . . . . . . . . . . . . . . . . . . . 82
7.1 The ESS or ESSs representing the meaning of a connective . . 113
10.1 A directed hypergraph . . . . . . . . . . . . . . . . . . . . . . 171
10.2 2-seceding, 1-seceding and 1-conceding hyperarcs . . . . . . . 173
10.3 General, proper and elementary fusion arcs . . . . . . . . . . . 176
10.4 General, proper and elementary fission arcs . . . . . . . . . . . 177
10.5 A directed hypergraph containing a partial cycle . . . . . . . . 179
10.6 Two maximal strands of a directed hypergraph . . . . . . . . . 181
11.1 The relational interpretation of a→ a∨b . . . . . . . . . . . . 189
11.2 The relational interpretation of a,b→ a&b . . . . . . . . . . 190
11.3 The relational interpretation of a⊃b,b⊃c→a⊃c . . . . . . 192
11.4 The four maximal strands of a⊃b,b⊃c→a⊃c . . . . . . . 193
11.5 Exploring the four branches of Ξ . . . . . . . . . . . . . . . . 196
12.1 Different bridging actions on the same strand . . . . . . . . . 200
12.2 The results of the bridging actions on a&b→ a&b . . . . . . 203
12.3 Replacing labels by co-identity arcs . . . . . . . . . . . . . . . 207
13.1 Growing the tomograph for a&b,(a⊃c)&(b⊃d)→c&d. . 217
78Chapter 1
Introduction
The prominence of formal logic is justified by its many successes. These
successes are more often related to logical syntax providing a concise means
of communicating the content it is reasoned about and less often about the
process of reasoning itself. This is especially the case for first-order logic,
which is often employed as universal specification language. Applications of
logic in this sense very often extend the logical language in order to obtain
the descriptiveness, which is required to detail the subject matter at hand.
More often than otherwise, the logical formalism is used as specificational
shorthand only, the actual reasoning being performed outside of the formal
system. Bethatasitmay,asignificantsideeffectofsuchuseoflogicalsyntax
has been the emergence of the opinion that logic is about logical syntax, that
it is about expressing concrete content with the help of logical formalism.
Of course, such a conception is erroneous. Instead, logic is the study of
reasoning and of delivering sound argument. The focus lies specifically on
the structure of the argument and, ideally, the content of the argument can
be disregarded entirely. The Aristotelean syllogisms must be