A Mathematical Introduction to Logic, 2nd Edition

A Mathematical Introduction to Logic

This Page Intentionally Left Blank

A Mathematical Introduction to Logic

Second Edition Herbert B. Enderton

University of California, Los Angeles

A Harcourt Science and Technology Company San Diego New York Boston

London Toronto Sydney Tokyo

Sponsoring Editor Production Editor Editorial Coordinator Marketing Manager Cover Design Copyeditor Composition Printer

Barbara Holland Julie Bolduc Karen Frost Marianne Rutter Judy Arisman, Arisman Design Kristin Landon Interactive Composition Corporation The Maple-Vail Book Manufacturing Group

This book is printed on acid-free paper.

Copyright c 2001, 1972 by HARCOURT/ACADEMIC PRESS

All rights reserved. No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher.

Requests for permission to make copies of any part of the work should be mailed to: Permissions Department, Harcourt, Inc., 6277 Sea Harbor Drive, Orlando, Florida 32887-6777.

Academic Press A Harcourt Science and Technology Company 525 B Street, Suite 1900, San Diego, California 92101-4495, USA

Academic Press Harcourt Place, 32 Jamestown Road, London NW1 7BY, UK

Harcourt /Academic Press A Harcourt Science and Technology Company 200 Wheeler Road, Burlington, Massachusetts 01803, USA

Library of Congress Catalog Card Number: 00-110670

International Standard Book Number: 0-12-238452-0

PRINTED IN THE UNITED STATES OF AMERICA 00 01 02 03 04 05 MB 9 8 7 6 5 4 3 2 1

for Eric and Bert

This Page Intentionally Left Blank

Contents

PREFACE

ix

INTRODUCTION

xi

CHAPTER ZERO Useful Facts about Sets

1

CHAPTER ONE Sentential Logic

11

1.0 Informal Remarks on Formal Languages

11

1.1 The Language of Sentential Logic

13

1.2 Truth Assignments

20

1.3 A Parsing Algorithm

29

1.4 Induction and Recursion

34

1.5 Sentential Connectives

45

1.6 Switching Circuits

54

1.7 Compactness and Effectiveness

59

CHAPTER TWO First-Order Logic

67

2.0 Preliminary Remarks

67

2.1 First-Order Languages

69

2.2 Truth and Models

80

2.3 A Parsing Algorithm

105

2.4 A Deductive Calculus

109

2.5 Soundness and Completeness Theorems

131

2.6 Models of Theories

147

2.7 Interpretations Between Theories

164

2.8 Nonstandard Analysis

173

CHAPTER THREE Undecidability

182

3.0 Number Theory

182

3.1 Natural Numbers with Successor

187

3.2 Other Reducts of Number Theory

193

3.3 A Subtheory of Number Theory

202

3.4 Arithmetization of Syntax

224

vii

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download