Logicism Renewed: Logical Foundations for

Logicism is the thesis that all mathematical concepts are definable as logical concepts. This book introduces intensional type theory based on rules of intensionality rather than rules of extensionality. ITT is used to provide a unified logical foundation for mathematics and computer science, yielding a much simpler foundation for recursion theory and the semantics of computer programs than that currently provided by category theory. The monograph unifies three contending theses on the nature of mathematics, namely logicism, formalism, and intuitionism. Paul Gilmore is professor emeritus in the Computer Science department at the University of British Columbia. His research interests include Logical Foundations of Mathematics and Computer Science, Applications of Logic in Computer Science, and Databases.

Preface

ix

Elementary Logic

1

(42)

Language and Logic

1

(1)

Types, Terms, and Formulas

2

(3)

Logical Connectives

5

(2)

Choice of connectives

6

(1)

Valuations

7

(4)

Domains, valuations, and models

9

(2)

The Lambda Abstraction Operator

11

(8)

Syntax for quantification

12

(1)

Semantics for abstraction terms

13

(2)

Free and bound variables

15

(1)

Substitutions and contractions

16

(3)

Syntax and Semantics for EL

19

(1)

Elementary Proof Theory

20

(12)

Semantic rules for EL

22

(1)

Derivation of a sequent

23

(1)

Terminology for and properties of derivations

24

(2)

Reusing derivations

26

(1)

An alternative proof theory

27

(1)

Derivations as binary trees of sequents

28

(3)

Other formulations of first order logic

31

(1)

Consistency of EL

32

(1)

Completeness of EL

33

(10)

A systematic search for a derivation

35

(2)

A descending chain defines a counter-example

37

(6)

Type Theory

43

(28)

The Type Theory TT

43

(3)

The terms of TT

44

(2)

Polymorphic Typing of TT

46

(9)

Typing strings of characters

46

(1)

Type expressions and their ranges

47

(1)

String assignments and unification

48

(3)

Polytyping TT

51

(4)

Lambda Contractions

55

(5)

The Proof Theory

60

(1)

Intensional and Extensional Identity

61

(5)

Extensional and intensional predicates

63

(2)

Identity and string identity

65

(1)

Semantics for TT

66

(5)

An extensional semantics for TT

66

(2)

An intensional semantics for TT

68

(3)

An Intensional Type Theory

71

(28)

The Terms of ITT

71

(5)

Motivation for secondary typing

71

(3)

Secondary typing

74

(1)

The normal form of a term of ITT

75

(1)

Polytyping ITT

76

(3)

A polytyping algorithm for ITT

76

(3)

An Intensional Semantics for ITT

79

(6)

Domains and valuations

79

(5)

Semantic basis for the proof theory

84

(1)

Sequents and counter-examples

84

(1)

Proof Theory for ITT

85

(3)

An essential restriction

86

(1)

Derivable rules for identity

86

(1)

Relationship between the identities

87

(1)

Properties of derivations

87

(1)

Completeness of ITT

88

(5)

A counter-example that is an intensional model

90

(3)

Denumerable models

93

(1)

SITT

93

(6)

Types and Terms of SITT

94

(1)

Lambda contractions

95

(1)

Semantics of SITT

96

(1)

Proof Theory for SITT

96

(1)

Russell's set

96

(3)

Recursions

99

(38)

Introduction

99

(2)

Least and Greatest Predicate Operators

101

(2)

Monotonic Recursion Generators

103

(3)

Properties of monotonic recursion generators

104

(2)

Zero, Successor, and Natural Numbers

106

(9)

A zero and successor

106

(1)

Nil and ordered pair

107

(2)

Projections of ordered pair

109

(1)

A recursion generator for the S-sequence

110

(1)

Understanding Gt(RN)

111

(4)

Continuous Recursion Generators

115

(1)

Positive Occurrences of a Variable

116

(6)

Subformula path

116

(1)

Positive and e-positive occurrences of variables

116

(2)

Monotonicity and continuity

118

(4)

Horn Sequents and Recursion Generators

122

(5)

Horn sequents

122

(1)

Simultaneous Horn sequents

123

(4)

Definition by Iteration

127

(4)

Defining Lt(RG) by iteration

128

(2)

Defining Gt(RG) by iteration

130

(1)

Potentially Infinite Predicates

131

(6)

Characters and strings

131

(1)

Lists

132

(1)

Universal quantification

133

(4)

Choice and Function Terms

137

(14)

Introduction

137

(3)

A functional notation from choice terms

138

(2)

Introducing Choice Terms

140

(3)

The Relation >ε on terms of ITTε

141

(2)

Proof Theory for ITTε

143

(2)

Consistency and Completeness

145

(3)

Completeness of ITTε

147

(1)

Function Terms

148

(1)

Partial Functions and Dependent Types

149

(2)

Intuitionist Logic

151

(20)

Intuitionist/Constructive Mathematics

151

(1)

A sequent calculus formulation ITTG of ITT

152

(2)

An intuitionist formulation HITTG of ITTG

154

(5)

Derivability in ITTG and HITTG

155

(4)

Semantic Tree Formulation HITT of HITTG

159

(8)

Properties of HITT derivations

162

(2)

Equivalence of HITT and HITTG

164

(3)

Semantics for HITT

167

(3)

Forests of semantic trees

167

(3)

Recursions in HITT

170

(1)

Logic and Mathematics

171

(14)

Introduction

171

(1)

Self-Applied Logic

172

(1)

Logic and Category Theory

173

(6)

Abelian semi-groups

173

(1)

Definitions

174

(1)

Typing

175

(1)

Derivation of (SG)

175

(4)

Set Theory and Logic

179

(4)

A set theory formalized in ITT

180

(1)

Cantor's diagonal argument in ITT

181

(2)

Why Is Mathematics Applicable?

183

(2)

Logic and Computer Science

185

(30)

Introduction

185

(4)

Definition, Derivation, and Computation

189

(2)

Semantics for Recursive Commands

191

(12)

Primitive Syntax

191

(1)

Expressions

192

(1)

Expression semantics

193

(3)

Command semantics

196

(5)

Example theorem

201

(2)

Recursive Domains

203

(10)

Primitive domains

204

(1)

Finite functions and domain constructors

204

(1)

Domain constructors

205

(5)

Solving domain equations: an example

210

(3)

Logical Support for Specification Languages

213

(2)

References

215

(10)

Index

225

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Logicism Renewed: Logical Foundations for Mathematics and Computer Science, Lecture Notes in Logic 23

Summary

Table of Contents

Supplemental Materials

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Logicism Renewed: Logical Foundations for Mathematics and Computer Science, Lecture Notes in Logic 23

Summary

Table of Contents

Supplemental Materials

Digital License