Mathematical Logic (eBook)

Foundations for Information Science

Wei Li (Autor)

eBook Download: PDF

2010 | 2010
XII, 273 Seiten
Springer Basel (Verlag)
978-3-7643-9977-1 (ISBN)

Infos

Mathematical logic is a branch of mathematics that takes axiom systems and mathematical proofs as its objects of study. This book shows how it can also provide a foundation for the development of information science and technology. The first five chapters systematically present the core topics of classical mathematical logic, including the syntax and models of first-order languages, formal inference systems, computability and representability, and Gödel's theorems. The last five chapters present extensions and developments of classical mathematical logic, particularly the concepts of version sequences of formal theories and their limits, the system of revision calculus, proschemes (formal descriptions of proof methods and strategies) and their properties, and the theory of inductive inference. All of these themes contribute to a formal theory of axiomatization and its application to the process of developing information technology and scientific theories. The book also describes the paradigm of three kinds of language environments for theories and it presents the basic properties required of a meta-language environment. Finally, the book brings these themes together by describing a workflow for scientific research in the information era in which formal methods, interactive software and human invention are all used to their advantage.

This book represents a valuable reference for graduate and undergraduate students and researchers in mathematics, information science and technology, and other relevant areas of natural sciences. Its first five chapters serve as an undergraduate text in mathematical logic and the last five chapters are addressed to graduate students in relevant disciplines.

Inhalt

Table of Contents 5
Preface 8
Chapter 1 Syntax of First-Order Languages 12
1.1 Symbols of first-order languages 15
1.2 Terms 17
1.3 Logical formulas 19
1.4 Free variables and substitutions 20
1.5 Gödel terms of formulas 24
1.6 Proof by structural induction 26
Chapter 2 Models of First-Order Languages 30
2.1 Domains and interpretations 33
2.2 Assignments and models 35
2.3 Semantics of terms 35
2.4 Semantics of logical connective symbols 36
2.5 Semantics of formulas 38
2.6 Satisfiability and validity 41
2.7 Valid formulas with 42
2.8 Hintikka set 44
2.9 Herbrand model 46
2.10 Herbrand model with variables 49
2.11 Substitution lemma 52
2.12 Theorem of isomorphism 53
Chapter 3 Formal Inference Systems 56
3.1 G inference system 60
3.2 Inference trees, proof trees and provable sequents 63
3.3 Soundness of the G inference system 68
3.4 Compactness and consistency 72
3.5 Completeness of the G inference system 74
3.6 Some commonly used inference rules 77
3.7 Proof theory and model theory 79
Chapter 4 Computability & Representability
4.1 Formal theory 83
4.2 Elementary arithmetic theory 85
4.3 P-kernel on N 87
4.4 Church-Turing thesis 91
4.5 Problem of representability 92
4.6 States of P-kernel 93
4.7 Operational calculus of P-kernel 95
4.8 Representations of statements 97
4.9 Representability theorem 106
Chapter 5 Gödel Theorems 108
5.1 Self-referential proposition 109
5.2 Decidable sets 111
5.3 Fixed point equation in . 115
5.4 Gödel’s incompleteness theorem 118
5.5 Gödel’s consistency theorem 120
5.6 Halting problem 123
Chapter 6 Sequences of Formal Theories 128
6.1 Two examples 129
6.2 Sequences of formal theories 133
6.3 Proschemes 136
6.4 Resolvent sequences 139
6.5 Default expansion sequences 141
6.6 Forcing sequences 144
6.7 Discussions on proschemes 147
Chapter 7 Revision Calculus 149
7.1 Necessary antecedents of formal consequences 150
7.2 New conjectures and new axioms 153
7.3 Refutation by facts and maximal contraction 154
7.4 R-calculus 156
7.5 Some examples 163
7.6 Special theory of relativity 165
7.7 Darwin’s theory of evolution 166
7.8 Reachability of R-calculus 170
7.9 Soundness and completeness of R-calculus 173
Chapter 8 Version Sequences 178
8.1 Versions and version sequences 180
8.2 The Proscheme OPEN 181
8.3 Convergence of the proscheme 185
8.4 Commutativity of the proscheme 187
8.5 Independence of the proscheme 189
8.6 Reliable proschemes 191
Chapter 9 Inductive Inference 195
9.1 Ground terms, basic sentences, and basic instances 198
9.2 Inductive inference system A 200
9.3 Inductive versions and inductive process 205
9.4 The Proscheme GUINA 205
9.5 Convergence of the proscheme GUINA 212
9.6 Commutativity of the proscheme GUINA 214
9.7 Independence of the proscheme GUINA 215
Chapter 10 Workflows for Scientific Discovery 217
10.1 Three language environments 217
10.2 Basic principles of the meta-language environment 221
1. Principle of environment 221
2. Principle of excluded middle 222
3. Principle of logical connectives 222
4. Church-Turing thesis 224
5. Principle of observability 224
6. Principle of Occam’s razor 224
10.3 Axiomatization 225
10.4 Formal methods 227
10.5 Workflow of scientific research 233
1. The Meta-language Environment L 234
2. The Domains 234
3. The Object Language 235
4. Formal Axiomatization 235
Appendix 1 Sets and Maps 237
Appendix 2 Substitution Lemma and Its Proof 240
Appendix 3 Proof of the Representability Theorem 244
A3.1 Representation of the while statement in . 244
A3.2 Representability of the P-procedure body 251
Bibliography 260
Index 263

Produkt-Details

• Erscheint lt. Verlag: 26.2.2010
• Reihe/Serie: Progress in Computer Science and Applied Logic
• Reihe/Serie: Progress in Computer Science and Applied Logic
• Zusatzinfo: XII, 273 p.
• Verlagsort: Basel
• Sprache: englisch
• Original-Titel: Mathematical Logic - Basic Principles and Formal Calculus, ISBN 978-7-03-020096-9
• Themenwelt: Geisteswissenschaften ► Philosophie ► Logik
• Themenwelt: Mathematik / Informatik ► Informatik
• Schlagworte: arithmetic • Calculus • first-order language • forcing • formal calculus • Gödel theorem • inference system • language environment • Lemma • Logic • Mathematical Logic • model Theory • Proof • Proof theory • revision calculus • version sequence
• ISBN-10: 3-7643-9977-5 / 3764399775
• ISBN-13: 978-3-7643-9977-1 / 9783764399771