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

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9781568812762 | 1568812760
Cover: Nonspecific Binding
Copyright: 11/18/2005

Rent

(Recommended)

$38.12

Term

Due

Price

Semester

Dec 12

$40.13

Quarter

Aug 13

$38.12

Short Term

Jul 24

$36.11

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping bag.
Buy New

Usually Ships in 3-5 Business Days

$51.38
eBook

Available Instantly

Online: 180 Days

Downloadable: 180 Days

*To support the delivery of the digital material to you, a digital delivery fee of $3.99 will be charged on each digital item.

$41.58*

The original concept of logicism, as put forward by Bertrand Russell, the belief that all of mathematics can be deduced from a very small number of fundamental logical principles, is revisited in the light of advances in mathematical logic and the need for languages that can be understood by both humans and computers which require distinguishing between the intension and extension of predicates. Using Intensional Type Theory (ITT) the author provides a unified 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. Paul Gilmore is professor emeritus in the Computer Science department at the University of British Columbia.

PREFACE

CHAPTER 1. ELEMENTARY LOGIC

(42)

1.1. Language and Logic

(1)

1.2. Types, Terms, and Formulas

(3)

1.3. Logical Connectives

(2)

1.3.1. Choice of connectives

(1)

1.4. Valuations

(4)

1.4.1. Domains, valuations, and models

(2)

1.5. The Lambda Abstraction Operator

(8)

1.5.1. Syntax for quantification

(1)

1.5.2. Semantics for abstraction terms

(2)

1.5.3. Free and bound variables

(1)

1.5.4. Substitutions and contractions

(3)

1.6. Syntax and Semantics for EL

(1)

1.7. Elementary Proof Theory

(12)

1.7.1. Semantic rules for EL

(1)

1.7.2. Derivation of a sequent

(1)

1.7.3. Terminology for and properties of derivations

(2)

1.7.4. Reusing derivations

(1)

1.7.5. An alternative proof theory

(1)

1.7.6. Derivations as binary trees of sequents

(3)

1.7.7. Other formulations of first order logic

(1)

1.8. Consistency of EL

(1)

1.9. Completeness of EL

(10)

1.9.1. A systematic search for a derivation

(2)

1.9.2. A descending chain defines a counter-example

(6)

CHAPTER 2. TYPE THEORY

(28)

2.1. The Type Theory TT

(3)

2.1.1. The terms of TT

(2)

2.2. Polymorphic Typing of TT

(9)

2.2.1. Typing strings of characters

(1)

2.2.2. Type expressions and their ranges

(1)

2.2.3. String assignments and unification

(3)

2.2.4. Polytyping TT

(4)

2.3. Lambda Contractions

(5)

2.4. The Proof Theory

(1)

2.5. Intensional and Extensional Identity

(5)

2.5.1. Extensional and intensional predicates

(2)

2.5.2. Identity and string identity

(1)

2.6. Semantics for TT

(5)

2.6.1. An extensional semantics for TT

(2)

2.6.2. An intensional semantics for TT

(3)

CHAPTER 3. AN INTENSIONAL TYPE THEORY

(28)

3.1. The Terms of ITT

(5)

3.1.1. Motivation for secondary typing

(3)

3.1.2. Secondary typing

(1)

3.1.3. The normal form of a term of ITT

(1)

3.2. Polytyping ITT

(3)

3.2.1. A polytyping algorithm for ITT

(3)

3.3. An Intensional Semantics for ITT

(6)

3.3.1. Domains and valuations

(5)

3.3.2. Semantic basis for the proof theory

(1)

3.3.3. Sequents and counter-examples

(1)

3.4. Proof Theory for ITT

(3)

3.4.1. An essential restriction

(1)

3.4.2. Derivable rules for identity

(1)

3.4.3. Relationship between the identities

(1)

3.4.4. Properties of derivations

(1)

3.5. Completeness of ITT

(5)

3.5.1. A counter-example that is an intensional model

(3)

3.5.2. Denumerable models

(1)

3.6. SITT

(6)

3.6.1. Types and Terms of SITT

(1)

3.6.2. Lambda contractions

(1)

3.6.3. Semantics of SITT

(1)

3.6.4. Proof Theory for SITT

(1)

3.6.5. Russell's set

(3)

CHAPTER 4. RECURSIONS

(38)

4.1. Introduction

(2)

4.2. Least and Greatest Predicate Operators

101

(2)

4.3. Monotonic Recursion Generators

103

(3)

4.3.1. Properties of monotonic recursion generators

104

(2)

4.4. Zero, Successor, and Natural Numbers

106

(9)

4.4.1. A zero and successor

106

(1)

4.4.2. Nil and ordered pair

107

(2)

4.4.3. Projections of ordered pair

109

(1)

4.4.4. A recursion generator for the S-sequence

110

(1)

4.4.5. Understanding Gt(RN)

111

(4)

4.5. Continuous Recursion Generators

115

(1)

4.6. Positive Occurrences of a Variable

116

(6)

4.6.1. Subformula path

116

(1)

4.6.2. Positive and e-positive occurrences of variables

116

(2)

4.6.3. Monotonicity and continuity

118

(4)

4.7. Horn Sequents and Recursion Generators

122

(5)

4.7.1. Horn sequents

122

(1)

4.7.2. Simultaneous Horn sequents

123

(4)

4.8. Definition by Iteration

127

(4)

4.8.1. Defining Lt(RG) by iteration

128

(2)

4.8.2. Defining Gt(RG) by iteration

130

(1)

4.9. Potentially Infinite Predicates

131

(6)

4.9.1. Characters and strings

131

(1)

4.9.2. Lists

132

(1)

4.9.3. Universal quantification

133

(4)

CHAPTER 5. CHOICE AND FUNCTION TERMS

137

(14)

5.1. Introduction

137

(3)

5.1.1. A functional notation from choice terms

138

(2)

5.2. Introducing Choice Terms

140

(3)

5.2.1. The Relation >epsilon on terms of ITTepsilon

141

(2)

5.3. Proof Theory for ITTepsilon

143

(2)

5.4. Consistency and Completeness

145

(3)

5.4.1. Completeness of ITTepsilon

147

(1)

5.5. Function Terms

148

(1)

5.6. Partial Functions and Dependent Types

149

(2)

CHAPTER 6. INTUITIONIST LOGIC

151

(20)

6.1. Intuitionist/Constructive Mathematics

151

(1)

6.2. A sequent calculus formulation ITTG of ITT

152

(2)

6.3. An intuitionist formulation HITTG of ITTG

154

(5)

6.3.1. Derivability in ITTG and HITTG

155

(4)

6.4. Semantic Tree Formulation HITT of HITTG

159

(8)

6.4.1. Properties of HITT derivations

162

(2)

6.4.2. Equivalence of HITT and HITTG

164

(3)

6.5. Semantics for HITT

167

(3)

6.5.1. Forests of semantic trees

167

(3)

6.6. Recursions in HITT

170

(1)

CHAPTER 7. LOGIC AND MATHEMATICS

171

(14)

7.1. Introduction

171

(1)

7.2. Self-Applied Logic

172

(1)

7.3. Logic and Category Theory

173

(6)

7.3.1. Abelian semi-groups

173

(1)

7.3.2. Definitions

174

(1)

7.3.3. Typing

175

(1)

7.3.4. Derivation of (SG)

175

(4)

7.4. Set Theory and Logic

179

(4)

7.4.1. A set theory formalized in ITT

180

(1)

7.4.2. Cantor's diagonal argument in ITT

181

(2)

7.5. Why Is Mathematics Applicable?

183

(2)

CHAPTER 8. LOGIC AND COMPUTER SCIENCE

185

(30)

8.1. Introduction

185

(4)

8.2. Definition, Derivation, and Computation

189

(2)

8.3. Semantics for Recursive Commands

191

(12)

8.3.1. Primitive Syntax

191

(1)

8.3.2. Expressions

192

(1)

8.3.3. Expression semantics

193

(3)

8.3.4. Command semantics

196

(5)

8.3.5. Example theorem

201

(2)

8.4. Recursive Domains

203

(10)

8.4.1. Primitive domains

204

(1)

8.4.2. Finite functions and domain constructors

204

(1)

8.4.3. Domain constructors

205

(5)

8.4.4. Solving domain equations: an example

210

(3)

8.5. Logical Support for Specification Languages

213

(2)

REFERENCES

215

(10)

INDEX

225

Please wait while the item is added to your bag...

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