C. J. Ash - What is Mathematical Logic?

What Is Mathematical Logic?

What Is Mathematical Logic?

J.N. Crossley

C.J. Ash

C.J. Brickhill

J.C. Stillwell

N.H. Williams

DOVER PUBLICATIONS, IC.

New York

Copyright 1972 by Oxford University Press.

All rights reserved under Pan American and International Copyright Conventions.

This Dover edition, first published in 1990, is an unabridged and unaltered republication of the work first published by the Oxford University Press in 1972. It is reprinted by special arrangement with Oxford University Press, Inc., 200 Madison Ave., New York, N.Y. 10016.

The authors: J.N. Crossley, Professor, Mathematics and Computer Science, C.J. Ash, Reader, Mathematics, J.C. Stillwell, Senior Lecturer, Mathematics, Monash University, Clayton, Victoria, Australia; N.H. Williams, Senior Lecturer, Mathematics, University of Queensland, St. Lucia, Brisbane, Queensland, Australia; C.J. Brickhill, President, Intelcom Data Systems Inc., New York, N.Y.

Library of Congress Cataloging-in-Publication Data

What is mathematical logic? / J.N. Crossley ... [et al.].

p. cm.

Includes bibliographical references (p. ) and index.

eISBN 13: 978-0-486-15152-6

1. Logic, Symbolic and mathematical. I. Crossley, John N. QA9.W47 1990

511.3dc20

90-3739

CIP

Manufactured in the United States by Courier Corporation

26404106

www.doverpublications.com

Preface

T HE lectures on which this book is based were conceived by Chris Brickhill and John Crossley. Our aim was to introduce the very important ideas in modern mathematical logic without the detailed mathematical work which is required of those with a professional interest in logic. The lectures were given at Monash University and the University of Melbourne in the autumn and winter of 1971. Their popularity induced us to produce this book which we hope will give some idea of the exciting aspects of mathematical logic to those who have no mathematical training.

We must add that we very much enjoyed giving these lectures and that the audience response exceeded all our expectations. We thank Associate Professor John McGechie of Monash University and Professor Douglas Gasking of the University of Melbourne who so ably supported us in this venture. We must also thank Dennis Robinson and Terry Boehm for their assistance to Chris Brickhill in the preparation of these notes. Finally we thank Anne-Marie Vandenberg who so masterfully dealt with the typing.

J. N. C ROSSLEY

Ayers Rock

August 1971

Introduction

M ATHEMATICAL logic is a living and lively subject. We hope that this will be conveyed by the somewhat unconventional style in which this book is written. Originally lectures were given by four of the authors but they have been so revamped that it seemed inappropriate to specify the authorship in detail.

It is our hope and belief that any reader who later undergoes a full course in logic would be able to fill out all our sketches into full proofs.

The chapters are in many ways independent, though items from , and we suggest that a reader who finds a chapter difficult should turn to another one and return to the first one later. In this way you may find the difficulties have been ameliorated.

Historical Survey

T HE different areas in logic emerged as a result of difficulties and new discoveries in a complicated history, so this first chapter is going to describe a flow chart (see p. 2). I shall skip rather briefly over the different areas, so do not be worried if you find a lot of strange terminologyit will be explained later on in the book. I am going to view the history as two different streams, both of which are very long: one is the history of formal deduction which goes back, of course, to Aristotle and Euclid and others of that era, and the other is the history of mathematical analysis which can be dated back to Archimedes in the same era. These two streams developed separately for a long timeuntil around 16001700, when we have Newton and Leibnitz and their invention of the calculus, which was ultimately to bring mathematics and logic together.

The two streams start to converge in the 19th century, let us say arbitrarily about 1850, when we have logicians such as Boole and Frege attempting to give a final and definitive form to what formal deduction actually was. Now Aristotle had made rather explicit rules of deduction, but he had stated them in natural language. Boole wanted to go further than this and he developed a purely symbolic system. This was extended by Frege, who arrived at the predicate calculus which turned out to be an adequate logical basis for all of todays mathematics. Perhaps I can dwell a little on this, since symbolism became so important from this point onwards. A little description of what symbolism can look like will help.

Purely logical connectives, such as and, or, not are given symbols such as &, V, ; need symbols (x, y, z and so on) for variables and also symbols P, Q, R for predicates (or properties or relations). Out of these we make formulae such as this: P(x) V Q(x), which is read as saying that x has property P or x has property Q, and this can be quantified by expressing for all x by x and there exists an x by x. Thus xP(x) says every x has property P.

Now any mathematical domain can be translated into this language with a suitable choice of predicate letters: arithmetic, for instance. We have numbers as the objects that the variables will denote, and we have various properties of numbers that we wish to express, such as being equal or the relationship between two numbers and a third one which is the sum of the other two; another one could be the product relationship. You can quickly convince yourself that all statements that we are accustomed to make in number theory about divisibility, prime numbers, and whether one number is the sum of another two can be made using these predicates. Frege gave rules for making deductions in this language and the whole conglomeration is called predicatecalculus.

Now meanwhile in analysis there was a long period, a couple of centuries, of controversy over the meaning of concepts that Newton introducedthe derivative and the integralbecause he talked about infinitesimals. A lot of people did not believe in these and thought they were contradictory, which they were. But nevertheless he got the right results and, to find out why he got the right results, clarification of the notions was made. Some of the people responsible for this were Bolzano, Dedekind, and Cantor. (This brings us down to about 1880.) These people realized that, to deal adequately with derivatives and integrals, infinite sets had to be considered, and considered very precisely. There was no way of avoiding infinite sets. This was the origin of set theory.

I think it is worth pointing out that Cantor had got into set theory from a problem in analysis. He was not trying to define natural numbers or any of the other things that people have used set theory for since. His original motivation was analysis of infinite sets of real numbers. And I think this is really the proper domain of set theory: to solve problems like that rather than problems of definition of primitive concepts. This