**Allwein, G. Barker-Plummer, D. Barwise, Etchemendy, J., Liu, A....**

Our primary debt of gratitude goes to our three main collaborators on this project: Gerry Allwein,...

(Parte **1** de 6)

In collaboration with Gerard Allwein Dave Barker-Plummer Albert Liu

77SEVEN BRIDGES PRESS NEW YORK • LONDON

Library of Congress Cataloging-in-Publication Data Barwise, Jon.

Language, proof and logic / Jon Barwise and John Etchemendy ; in collaboration with Gerard Allwein, Dave Barker-Plummer, and Albert Liu.

p. cm. |

ISBN 1-889119-08-3 (pbk. : alk. paper)

I. Etchemendy, John, 1952- I. Allwein, Gerard, 1956- I. Barker-Plummer, Dave. IV. Liu, Albert, 1966- V. Title. IN PROCESS

9-41113 | |

CIP |

Copyright © 1999 CSLI Publications Center for the Study of Language and Information Leland Stanford Junior University

Acknowledgements

Our primary debt of gratitude goes to our three main collaborators on this project: Gerry Allwein, Dave Barker-Plummer, and Albert Liu. They have worked with us in designing the entire package, developing and implementing the software, and teaching from and reflning the text. Without their intelligence, dedication, and hard work, LPL would neither exist nor have most of its other good properties.

In addition to the flve of us, many people have contributed directly and indirectly to the creation of the package. First, over two dozen programmers have worked on predecessors of the software included with the package, both earlier versions of Tarski’s World and the program Hyperproof, some of whose code has been incorporated into Fitch. We want especially to mention Christopher Fuselier, Mark Greaves, Mike Lenz, Eric Ly, and Rick Wong, whose outstanding contributions to the earlier programs provided the foundation of the new software. Second, we thank several people who have helped with the development of the new software in essential ways: Rick Sanders, Rachel Farber, Jon Russell Barwise, Alex Lau, Brad Dolin, Thomas Robertson, Larry Lemmon, and Daniel Chai. Their contributions have improved the package in a host of ways.

Prerelease versions of LPL have been tested at several colleges and universities. In addition, other colleagues have provided excellent advice that we have tried to incorporate into the flnal package. We thank Selmer Bringsjord, Renssalaer Polytechnic Institute; Tom Burke, University of South Carolina; Robin Cooper, Gothenburg University; James Derden, Humboldt State University; Josh Dever, SUNY Albany; Avrom Faderman, University of Rochester; James Garson, University of Houston; Christopher Gauker, University of Cincinnati; Ted Hodgson, Montana State University; John Justice, Randolph- Macon Women’s College; Ralph Kennedy, Wake Forest University; Michael O’Rourke, University of Idaho; Greg Ray, University of Florida; Cindy Stern, California State University, Northridge; Richard Tieszen, San Jose State University; Saul Traiger, Occidental College; and Lyle Zynda, Indiana University at South Bend. We are particularly grateful to John Justice, Ralph Kennedy, and their students (as well as the students at Stanford and Indiana University), for their patience with early versions of the software and for their extensive comments and suggestions. We would also like to thank Stanford’s Center for the Study of Language vi / Acknowledgements and Information and Indiana University’s College of Arts and Sciences for their flnancial support of the project. Finally, we are grateful to our two publishers, Dikran Karagueuzian of CSLI Publications and Clay Glad of Seven Bridges Press, for their skill and enthusiasm about LPL, and to Lauri Kanerva for his dedication and skill in the preparation of the flnal manuscript.

Acknowledgements

Contents

Acknowledgements i

The special role of logic in rational inquiry | 1 |

Why learn an artiflcial language? | 2 |

Consequence and proof | 4 |

Instructions about homework exercises (essential!) | 5 |

To the instructor | 10 |

Web address | 15 |

Introduction 1

I Propositional Logic 17

1.1 Individual constants | 19 |

1.2 Predicate symbols | 20 |

1.3 Atomic sentences | 23 |

1.4 General flrst-order languages | 28 |

1.5 Function symbols (optional) | 31 |

1.6 The flrst-order language of set theory (optional) | 37 |

1.7 The flrst-order language of arithmetic (optional) | 38 |

1.8 Alternative notation (optional) | 40 |

1 Atomic Sentences 19

2.1 Valid and sound arguments | 41 |

2.2 Methods of proof | 46 |

2.3 Formal proofs | 54 |

2.4 Constructing proofs in Fitch | 58 |

2.5 Demonstrating nonconsequence | 63 |

2.6 Alternative notation (optional) | 6 |

2 The Logic of Atomic Sentences 41

3.1 Negation symbol: : | 68 |

3.2 Conjunction symbol: | 71 |

3.3 Disjunction symbol: | 74 |

3.4 Remarks about the game | 7 |

3 The Boolean Connectives 67 v

3.5 Ambiguity and parentheses | 79 |

3.6 Equivalent ways of saying things | 82 |

3.7 Translation | 84 |

3.8 Alternative notation (optional) | 89 |

vi / Contents

4.1 Tautologies and logical truth | 94 |

4.2 Logical and tautological equivalence | 106 |

4.3 Logical and tautological consequence | 110 |

4.4 Tautological consequence in Fitch | 114 |

4.5 Pushing negation around (optional) | 117 |

4.6 Conjunctive and disjunctive normal forms (optional) | 121 |

4 The Logic of Boolean Connectives 93

5.1 Valid inference steps | 128 |

5.2 Proof by cases | 131 |

5.3 Indirect proof: proof by contradiction | 136 |

5.4 Arguments with inconsistent premises (optional) | 140 |

5 Methods of Proof for Boolean Logic 127

6.1 Conjunction rules | 143 |

6.2 Disjunction rules | 148 |

6.3 Negation rules | 154 |

6.4 The proper use of subproofs | 163 |

6.5 Strategy and tactics | 167 |

6.6 Proofs without premises (optional) | 173 |

6 Formal Proofs and Boolean Logic 142

7.1 Material conditional symbol: ! | 178 |

7.2 Biconditional symbol: $ | 181 |

7.3 Conversational implicature | 187 |

7.4 Truth-functional completeness (optional) | 190 |

7.5 Alternative notation (optional) | 196 |

8.1 Informal methods of proof | 198 |

8.2 Formal rules of proof for ! and $ | 206 |

8.3 Soundness and completeness (optional) | 214 |

8.4 Valid arguments: some review exercises | 2 |

8 The Logic of Conditionals 198 Contents

Contents / vii

I Quantiflers 225

9.1 Variables and atomic wfis | 228 |

9.2 The quantifler symbols: 8; 9 | 230 |

9.3 Wfis and sentences | 231 |

9.4 Semantics for the quantiflers | 234 |

9.5 The four Aristotelian forms | 239 |

9.6 Translating complex noun phrases | 243 |

9.7 Quantiflers and function symbols (optional) | 251 |

9.8 Alternative notation (optional) | 255 |

9 Introduction to Quantiflcation 227

10.1 Tautologies and quantiflcation | 257 |

10.2 First-order validity and consequence | 266 |

10.3 First-order equivalence and DeMorgan’s laws | 275 |

10.4 Other quantifler equivalences (optional) | 280 |

10.5 The axiomatic method (optional) | 283 |

10 The Logic of Quantiflers 257

1.1 Multiple uses of a single quantifler | 289 |

1.2 Mixed quantiflers | 293 |

1.3 The step-by-step method of translation | 298 |

1.4 Paraphrasing English | 300 |

1.5 Ambiguity and context sensitivity | 304 |

1.6 Translations using function symbols (optional) | 308 |

1.7 Prenex form (optional) | 31 |

1.8 Some extra translation problems | 315 |

1 Multiple Quantiflers 289

12.1 Valid quantifler steps | 319 |

12.2 The method of existential instantiation | 322 |

12.3 The method of general conditional proof | 323 |

12.4 Proofs involving mixed quantiflers | 329 |

12.5 Axiomatizing shape (optional) | 338 |

12 Methods of Proof for Quantiflers 319

13.1 Universal quantifler rules | 342 |

13.2 Existential quantifler rules | 347 |

13.3 Strategy and tactics | 352 |

13.4 Soundness and completeness (optional) | 361 |

13 Formal Proofs and Quantiflers 342 Contents

13.5 Some review exercises (optional) | 361 |

viii / Contents

14.1 Numerical quantiflcation | 366 |

14.2 Proving numerical claims | 374 |

14.3 The, both, and neither | 379 |

14.4 Adding other determiners to fol | 383 |

14.5 The logic of generalized quantiflcation | 389 |

14.6 Other expressive limitations of flrst-order logic | 397 |

14 More about Quantiflcation (optional) 364

I Applications and Metatheory 403

15.1 Naive set theory | 406 |

15.2 Singletons, the empty set, subsets | 412 |

15.3 Intersection and union | 415 |

15.4 Sets of sets | 419 |

15.5 Modeling relations in set theory | 422 |

15.6 Functions | 427 |

15.7 The powerset of a set (optional) | 429 |

15.8 Russell’s Paradox (optional) | 432 |

15.9 Zermelo Frankel set theory zfc (optional) | 433 |

15 First-order Set Theory 405

16.1 Inductive deflnitions and inductive proofs | 443 |

16.2 Inductive deflnitions in set theory | 451 |

16.3 Induction on the natural numbers | 453 |

16.4 Axiomatizing the natural numbers (optional) | 456 |

16.5 Proving programs correct (optional) | 458 |

16 Mathematical Induction 442

17.1 Truth assignments and truth tables | 468 |

17.2 Completeness for propositional logic | 470 |

17.3 Horn sentences (optional) | 479 |

17.4 Resolution (optional) | 488 |

17 Advanced Topics in Propositional Logic 468

18.1 First-order structures | 495 |

18.2 Truth and satisfaction, revisited | 500 |

18.3 Soundness for fol | 509 |

18 Advanced Topics in FOL 495 Contents

18.4 The completeness of the shape axioms (optional) | 512 |

18.5 Skolemization (optional) | 514 |

18.6 Uniflcation of terms (optional) | 516 |

18.7 Resolution, revisited (optional) | 519 |

Contents / ix

19.1 The Completeness Theorem for fol | 527 |

19.2 Adding witnessing constants | 529 |

19.3 The Henkin theory | 531 |

19.4 The Elimination Theorem | 534 |

19.5 The Henkin Construction | 540 |

19.6 The Lowenheim-Skolem Theorem | 546 |

19.7 The Compactness Theorem | 548 |

19.8 The Godel Incompleteness Theorem | 552 |

19 Completeness and Incompleteness 526

Propositional rules | 557 |

First-order rules | 559 |

Inference Procedures (Con Rules) | 561 |

Summary of Formal Proof Rules 557

Glossary 562 General Index 573 Exercise Files Index 585

Contents

To Sol Feferman and Pat Suppes, teachers, colleagues, and friends.

Introduction

The special role of logic in rational inquiry

What do the flelds of astronomy, economics, flnance, law, mathematics, medicine, physics, and sociology have in common? Not much in the way of subject matter, that’s for sure. And not all that much in the way of methodology. What they do have in common, with each other and with many other flelds, is their dependence on a certain standard of rationality. In each of these flelds, it is assumed that the participants can difierentiate between rational argumentation based on assumed principles or evidence, and wild speculation or nonsequiturs, claims that in no way follow from the assumptions. In other words, these flelds all presuppose an underlying acceptance of basic principles of logic.

For that matter, all rational inquiry depends on logic, on the ability of logic and rational inquirypeople to reason correctly most of the time, and, when they fail to reason correctly, on the ability of others to point out the gaps in their reasoning. While people may not all agree on a whole lot, they do seem to be able to agree on what can legitimately be concluded from given information. Acceptance of these commonly held principles of rationality is what difierentiates rational inquiry from other forms of human activity.

Just what are the principles of rationality presupposed by these disciplines?

And what are the techniques by which we can distinguish correct or \valid" reasoning from incorrect or \invalid" reasoning? More basically, what is it that makes one claim \follow logically" from some given information, while some other claim does not?

Many answers to these questions have been explored. Some people have claimed that the laws of logic are simply a matter of convention. If this is so, logic and convention we could presumably decide to change the conventions, and so adopt difierent principles of logic, the way we can decide which side of the road we drive on. But there is an overwhelming intuition that the laws of logic are somehow more fundamental, less subject to repeal, than the laws of the land, or even the laws of physics. We can imagine a country in which a red tra–c light means go, and a world on which water °ows up hill. But we can’t even imagine a world in which there both are and are not nine planets. The importance of logic has been recognized since antiquity. After all, no

2 / Introduction science can be any more certain than its weakest link. If there is something arbitrary about logic, then the same must hold of all rational inquiry. Thus it becomes crucial to understand just what the laws of logic are, and evenlaws of logic more important, why they are laws of logic. These are the questions that one takes up when one studies logic itself. To study logic is to use the methods of rational inquiry on rationality itself.

Over the past century the study of logic has undergone rapid and important advances. Spurred on by logical problems in that most deductive of disciplines, mathematics, it developed into a discipline in its own right, with its own concepts, methods, techniques, and language. The Encyclopedia Brittanica lists logic as one of the seven main branches of knowledge. More recently, the study of logic has played a major role in the development of modern day computers and programming languages. Logic continues to play an important part in computer science; indeed, it has been said that computer science is just logic implemented in electrical engineering.

This book is intended to introduce you to some of the most importantgoals of the book concepts and tools of logic. Our goal is to provide detailed and systematic answers to the questions raised above. We want you to understand just how the laws of logic follow inevitably from the meanings of the expressions we use to make claims. Convention is crucial in giving meaning to a language, but once the meaning is established, the laws of logic follow inevitably.

More particularly, we have two main aims. The flrst is to help you learn a new language, the language of flrst-order logic. The second is to help you learn about the notion of logical consequence, and about how one goes about establishing whether some claim is or is not a logical consequence of other accepted claims. While there is much more to logic than we can even hint at in this book, or than any one person could learn in a lifetime, we can at least cover these most basic of issues.

Why learn an artiflcial language?

This language of flrst-order logic is very important. Like Latin, the language is not spoken, but unlike Latin, it is used every day by mathematicians, philosophers, computer scientists, linguists, and practitioners of artiflcial intelligence. Indeed, in some ways it is the universal language, the lingua franca, of the symbolic sciences. Although it is not so frequently used in other forms of rational inquiry, like medicine and flnance, it is also a valuable tool for understanding the principles of rationality underlying these disciplines as well.

The language goes by various names: the lower predicate calculus, the functional calculus, the language of flrst-order logic, and fol. The last ofFOL

Introduction

Why learn an artificial language? / 3 these is pronounced ef{oh{el, not fall, and is the name we will use.

Certain elements of fol go back to Aristotle, but the language as we know it today has emerged over the past hundred years. The names chie°y associated with its development are those of Gottlob Frege, Giuseppe Peano, and Charles Sanders Peirce. In the late nineteenth century, these three logicians independently came up with the most important elements of the language, known as the quantiflers. Since then, there has been a process of standardization and simpliflcation, resulting in the language in its present form. Even so, there remain certain dialects of fol, difiering mainly in the choice of the particular symbols used to express the basic notions of the language. We will use the dialect most common in mathematics, though we will also tell you about several other dialects along the way. Fol is used in difierent ways in difierent flelds. In mathematics, it is used in an informal way quite exten- logic and mathematics sively. The various connectives and quantiflers flnd their way into a great deal of mathematical discourse, both formal and informal, as in a classroom setting. Here you will often flnd elements of fol interspersed with English or the mathematician’s native language. If you’ve ever taken calculus you have probably seen such formulas as:

Here, the unusual, rotated letters are taken directly from the language fol.

In philosophy, fol and enrichments of it are used in two difierent ways. As logic and philosophy in mathematics, the notation of fol is used when absolute clarity, rigor, and lack of ambiguity are essential. But it is also used as a case study of making informal notions (like grammaticality, meaning, truth, and proof) precise and rigorous. The applications in linguistics stem from this use, since linguistics is concerned, in large part, with understanding some of these same informal notions.

In artiflcial intelligence, fol is also used in two ways. Some researchers logic and artiflcial intelligencetake advantage of the simple structure of fol sentences to use it as a way to encode knowledge to be stored and used by a computer. Thinking is modeled by manipulations involving sentences of fol. The other use is as a precise speciflcation language for stating axioms and proving results about artiflcial agents.

In computer science, fol has had an even more profound in°uence. The logic and computer sciencevery idea of an artiflcial language that is precise yet rich enough to program computers was inspired by this language. In addition, all extant programming languages borrow some notions from one or another dialect of fol. Finally, there are so-called logic programming languages, like Prolog, whose programs are sequences of sentences in a certain dialect of fol. We will discuss the

Why learn an artificial language?

4 / Introduction logical basis of Prolog a bit in Part I of this book.

Fol serves as the prototypical example of what is known as an artiflcialartiflcial languages language. These are languages that were designed for special purposes, and are contrasted with so-called natural languages, languages like English and Greek that people actually speak. The design of artiflcial languages within the symbolic sciences is an important activity, one that is based on the success of fol and its descendants.

Even if you are not going to pursue logic or any of the symbolic sciences, the study of fol can be of real beneflt. That is why it is so widely taught. For one thing, learning fol is an easy way to demystify a lot of formal work. It will also teach you a great deal about your own language, and the laws of logic it supports. First, fol, while very simple, incorporates in a clean way some of thelogic and ordinary language important features of human languages. This helps make these features much more transparent. Chief among these is the relationship between language and the world. But, second, as you learn to translate English sentences into fol you will also gain an appreciation of the great subtlety that resides in English, subtlety that cannot be captured in fol or similar languages, at least not yet. Finally, you will gain an awareness of the enormous ambiguity present in almost every English sentence, ambiguity which somehow does not prevent us from understanding each other in most situations.

Consequence and proof

Earlier, we asked what makes one claim follow from others: convention, or something else? Giving an answer to this question for fol takes up a significant part of this book. But a short answer can be given here. Modern logic teaches us that one claim is a logical consequence of another if there is no waylogical consequence the latter could be true without the former also being true.

This is the notion of logical consequence implicit in all rational inquiry.

All the rational disciplines presuppose that this notion makes sense, and that we can use it to extract consequences of what we know to be so, or what we think might be so. It is also used in disconflrming a theory. For if a particular claim is a logical consequence of a theory, and we discover that the claim is false, then we know the theory itself must be incorrect in some way or other. If our physical theory has as a consequence that the planetary orbits are circular when in fact they are elliptical, then there is something wrong with our physics. If our economic theory says that in°ation is a necessary consequence of low unemployment, but today’s low employment has not caused in°ation, then our economic theory needs reassessment. Rational inquiry, in our sense, is not limited to academic disciplines, and so

(Parte **1** de 6)