002 Mathematical logic.pdf

(5043 KB) Pobierz
1198598068.038.png
H.-D. Ebbinghaus
J. Flum
W. Thomas
Mathematical Logic
Springer-Verlag
New York Berlin Heidelberg Tokyo
1198598068.039.png
H.-D. Ebbinghaus
J. Flum
Mathematisches Institut
Universitat Freiburg
Albertstrasse 23b
7800 Freiburg
Federal Republic of
Germany
W. Thomas
Lehrstuhl fiir Informatik 11
RWTH Aachen
Biichel 29-31
5100 Aachen
Federal Republic of
Germany
Editorial Board
P. R. Halmos
F. W. Gehring
Department of Mathematics
Department of Mathematics
Indiana University,
University of Michigan
Ann Arbor, MI 48109
Bloomington, IN 47405
U.S.A.
U.S.A.
Translated from Einjlihr~my
in die muthc~matischeLogik, published by Wissenschaftliche
Buchgesellschaft. Darmstadt. by Ann S. Ferebee, Kohlweg 12, D-6240 Konigstein 4,
Federal Republic of Germany.
-
AMS Subject Classification (1980): 03-01
Library of Congress Cataloging in Publication Data
Ebbinghaus, Heinz-Dieter, 1939
at he ma tical logic.
(Undergraduate texts in mathematics)
Translation of: Einfiihrung in die mathematische Logik,
Bibliography: p.
Includes index.
1. Logic, Symbolic and mathematical.
I. Flum, Jorg.
11. Thomas, Wolfgang.
111. Title.
IV. Series.
QA9.E2213
1984
511.3
83-20060
With 1 Illustration
@ 1984 by Springer-Verlag New York Inc.
All rights reserved. No part of this book may be translated or reproduced in any
form without written permission from Springer-Verlag, 175 Fifth Avenue,.New York,
New York 10010, U.S.A.
Typeset by Composition House Ltd., Salisbury, England.
Printed and bound by R. R. Donnelley & Sons, Harrisonburg, Virginia
Printed in the United States of America.
ISBN 0-387-90895-1 Springer-Verlag New York Berlin Heidelberg Tokyo
ISBN 3-540-90895-1 Springer-Verlag Berlin Heidelberg New York Tokyo
1198598068.040.png 1198598068.041.png 1198598068.001.png 1198598068.002.png 1198598068.003.png 1198598068.004.png 1198598068.005.png 1198598068.006.png 1198598068.007.png 1198598068.008.png 1198598068.009.png 1198598068.010.png 1198598068.011.png 1198598068.012.png 1198598068.013.png 1198598068.014.png 1198598068.015.png 1198598068.016.png 1198598068.017.png 1198598068.018.png 1198598068.019.png 1198598068.020.png
 
Preface
r
Some of the central questions of mathematical logic are: What is a
mathematical proof? How can proofs be justified? Are there limitations
to provability? To what extent can machines carry out mathematical
proofs?
Only in this century has there been success in obtaining substantial
and satisfactory answers, the most pleasing of which is given by Godel's
completeness theorem: It is possible to exhibit (in the framework of
first-order languages) a simple list of inference rules which suffices to
carry out all mathematical proofs. "Negative" results, however, appear
in Godel's incompleteness theorems. They show, for example, that it is
impossible to prove all true statements of arithmetic, and thus they reveal
principal limitations of the axiomatic method.
This book begins with an introduction to first-order logic and a proof of
Godel's completeness theorem. There follows a short digression into model
theory which shows that first-order languages have some deficiencies in
expressive power. For example, they do not allow the formulation of
an adequate axiom system for arithmetic or analysis. On the other hand,
this difficulty can be overcome-even in the framework of first-order
logic-by developing mathematics in set-theoretic terms. We explain the
prerequisites from set theory that are necessary for this purpose and then
treat the subtle relation between logic and set theory in a thorough manner.
Godel's incompleteness theorems are presented in connection with
several related results (such as Trahtenbrot's theorem) which all exemplify
the limitations of machine oriented proof methods. The notions of com-
putability theory that are relevant to this discussion are given in detail. The
concept of.computability is made precise by means of a simple programming
language.
1198598068.021.png 1198598068.022.png 1198598068.023.png 1198598068.024.png 1198598068.025.png 1198598068.026.png
The development of mathematics in the framework of first-order logic (as
indicated above) makes use of set-theoretic notions to an extent far beyond
that of mathematical practice. As an alternative one can consider logical
systems with more expressive power. We introduce sbme of these systems,
such as second-order and infinitary logics. In each of these cases we point
out deficiencies contrasting first-order logic. Finally, this empirical fact is
confirmed by Lindstrom's theorems, which show that there is no logical
system that extends first-order logic and at the same time shares all its
advantages.
The book does not require special mathematical knowledge; however, it
presupposes an acquaintance with mathematical reasoning as acquired, for
example, in the first year of a mathematics or computer science curriculum.
Exercises enable the reader to test and deepen his understanding of the text.
The references in the bibliography point out essays of historical importance,
further investigations, and related fields.
The original edition of the book appeared in 1978 under the title
" Einfiihrung in die mathematische Logik." Some sections have been revised
for the present translation; furthermore, some exercises have been added.
We thank Dr. J. Ward for his assistance in preparing the final English
text. Further thanks go to Springer-Verlag for their friendly cooperation.
Freiburg and Aachen
November 1983
1198598068.027.png 1198598068.028.png 1198598068.029.png 1198598068.030.png 1198598068.031.png 1198598068.032.png 1198598068.033.png 1198598068.034.png 1198598068.035.png 1198598068.036.png 1198598068.037.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin