Heinz-Dieter Ebbinghaus

This textbook introduces first-order logic and its role in the foundations of mathematics by examining fundamental questions. What is a mathematical proof? How can mathematical proofs be justified? Are there limitations to provability? To what extent can machines carry out mathematical proofs? In answering these questions, this textbook explores the capabilities and limitations of algorithms and proof methods in mathematics and computer science. The chapters are carefully organized, featuring complete proofs and numerous examples throughout. Beginning with motivating examples, the book goes on to present the syntax and semantics of first-order logic. After providing a sequent calculus for this logic, a Henkin-type proof of the completeness theorem is given. These introductory chapters prepare the reader for the advanced topics that follow, such as Gödel's Incompleteness Theorems, Trakhtenbrot's undecidability theorem, Lindström's theorems on the maximality of first-order logic, and results linking logic with automata theory. This new edition features many modernizations, as well as two additional important results: The decidability of Presburger arithmetic, and the decidability of the weak monadic theory of the successor function. Mathematical Logic is ideal for students beginning their studies in logic and the foundations of mathematics. Although the primary audience for this textbook will be graduate students or advanced undergraduates in mathematics or computer science, in fact the book has few formal prerequisites. It demands of the reader only mathematical maturity and experience with basic abstract structures, such as those encountered in discrete mathematics or algebra.

Die Mengenlehre ist eine eigenständige mathematische Disziplin. Zugleich ist sie eine Grundlagendisziplin, die für alle mathematischen Gebiete ein begriffliches Gerüst bereithält. In dieser Universalität offenbart sich eine große Tragweite des Mengenbegriffs und seiner Axiomatisierung. Die vorliegende Einführung gibt daher nicht nur einen Einblick in die Theorie und belegt deren Bedeutung für die Mathematik, sie behandelt auch Methoden und Ergebnisse, die auf eine möglichst weitgehende Rechtfertigung der mengentheoretischen Axiomsysteme zielen. Geschichtliche und erkenntnistheoretische Betrachtungen runden das Bild ab. Das Buch setzt keine spezifischen mathematischen Kenntnisse voraus. Es richtet sich an alle, die an den Grundlagen der Mathematik interessiert und mit Gedankengängen mathematischer Prägung vertraut sind. Rund 200 Übungsaufgaben mit Lösungshinweisen bieten eine zusätzliche Hilfe, insbesondere dann, wenn man das Buch zur eigenständigen Erarbeitung des dargebotenen Stoffes nutzen möchte. Die Neuauflage ist vollständig durchgesehen und enthält jetzt eine systematische Behandlung der konstruktiblen Hierarchie, die Beweise der relativen Widerspruchsfreiheit des Auswahlaxioms und der Cantorschen Kontinuumshypothese erlaubt.

This textbook introduces first-order logic and its role in the foundations of mathematics by examining fundamental questions. What is a mathematical proof? How can mathematical proofs be justified? Are there limitations to provability? To what extent can machines carry out mathematical proofs? In answering these questions, this textbook explores the capabilities and limitations of algorithms and proof methods in mathematics and computer science. The chapters are carefully organized, featuring complete proofs and numerous examples throughout. Beginning with motivating examples, the book goes on to present the syntax and semantics of first-order logic. After providing a sequent calculus for this logic, a Henkin-type proof of the completeness theorem is given. These introductory chapters prepare the reader for the advanced topics that follow, such as Gödel's Incompleteness Theorems, Trakhtenbrot's undecidability theorem, Lindström's theorems on the maximality of first-order logic, and results linking logic with automata theory. This new edition features many modernizations, as well as two additional important results: The decidability of Presburger arithmetic, and the decidability of the weak monadic theory of the successor function. Mathematical Logic is ideal for students beginning their studies in logic and the foundations of mathematics. Although the primary audience for this textbook will be graduate students or advanced undergraduates in mathematics or computer science, in fact the book has few formal prerequisites. It demands of the reader only mathematical maturity and experience with basic abstract structures, such as those encountered in discrete mathematics or algebra.

Was ist ein mathematischer Beweis? Wie lassen sich Beweise rechtfertigen? Gibt es Grenzen der Beweisbarkeit? Ist die Mathematik widerspruchsfrei? Kann man das Auffinden mathematischer Beweise Computern übertragen? Erst im 20. Jahrhundert ist es der mathematischen Logik gelungen, weitreichende Antworten auf diese Fragen zu geben. Im vorliegenden Werk werden die Ergebnisse systematisch zusammengestellt; im Mittelpunkt steht dabei die Logik erster Stufe. Die Lektüre setzt – außer einer gewissen Vertrautheit mit der mathematischen Denkweise – keine spezifischen Kenntnisse voraus. Für die vorliegende 6. Auflage wurde der Text überarbeitet und durch die Darstellung zweier für Logik und Informatik wichtiger Entscheidbarkeitsresultate erweitert.

This biography sheds light on all facets of the life and the achievements of Ernst Zermelo (1871-1953). Zermelo is best-known for the statement of the axiom of choice and his axiomatization of set theory. However, he also worked in applied mathematics and mathematical physics. His dissertation, for example, promoted the calculus of variations, and he created the pivotal method in the theory of rating systems. The presentation of Zermelo's work explores motivations, aims, acceptance, and influence. Selected proofs and information gleaned from letters add to the analysis. The description of his personality owes much to conversations with his late wife Gertrud. This second edition provides additional information. The system of citations has been adapted to that of Zermelo's Collected Works in order to facilitate side-by-side reading and thus profit from the thorough commentaries written for the Collected Works by experts in the respective fields. All facts presented are documented by appropriate sources. The biography contains nearly 50 photos and facsimiles.

This biography sheds light on all facets of the life and the achievements of Ernst Zermelo (1871-1953). Zermelo is best-known for the statement of the axiom of choice and his axiomatization of set theory. However, he also worked in applied mathematics and mathematical physics. His dissertation, for example, promoted the calculus of variations, and he created the pivotal method in the theory of rating systems. The presentation of Zermelo's work explores motivations, aims, acceptance, and influence. Selected proofs and information gleaned from letters add to the analysis. The description of his personality owes much to conversations with his late wife Gertrud. This second edition provides additional information. The system of citations has been adapted to that of Zermelo's Collected Works in order to facilitate side-by-side reading and thus profit from the thorough commentaries written for the Collected Works by experts in the respective fields. All facts presented are documented by appropriate sources. The biography contains nearly 50 photos and facsimiles.

Ernst Zermelo (1871-1953) is best-known for the statement of the axiom of choice and his axiomatization of set theory. However, he also worked in applied mathematics and mathematical physics. His dissertation, for example, promoted the calculus of variations, and he created the pivotal method in the theory of rating systems. This biography attempts to shed light on all facets of Zermelo's life and achievements. Personal and scientific aspects are kept separate as far as coherence allows, in order to enable the reader to follow the one or the other of these threads. The description of his personality owes much to conversations with his late wife Gertrud. The presentation of his work explores motivations, aims, acceptance, and influence. Selected proofs and information gleaned from unpublished notes and letters add to the analysis. All facts presented are documented by appropriate sources. The biography contains more than 40 photos and facsimiles, most of them provided by Gertrud Zermelo and published here for the first time.

Finite model theory, the model theory of finite structures, has roots in clas­ sical model theory; however, its systematic development was strongly influ­ enced by research and questions of complexity theory and of database theory. Model theory or the theory of models, as it was first named by Tarski in 1954, may be considered as the part of the semantics of formalized languages that is concerned with the interplay between the syntactic structure of an axiom system on the one hand and (algebraic, settheoretic, . . . ) properties of its models on the other hand. As it turned out, first-order language (we mostly speak of first-order logic) became the most prominent language in this respect, the reason being that it obeys some fundamental principles such as the compactness theorem and the completeness theorem. These principles are valuable modeltheoretic tools and, at the same time, reflect the expressive weakness of first-order logic. This weakness is the breeding ground for the freedomwhich modeltheoretic methods rest upon. By compactness, any first-order axiom system either has only finite models of limited cardinality or has infinite models. The first case is trivial because finitely many finite structures can explicitly be described by a first-order sentence. As model theory usually considers all models of an axiom system, modeltheorists were thus led to the second case, that is, to infinite structures. In fact, classical model theory of first-order logic and its generalizations to stronger languages live in the realm of the infinite.

Die Schwierigkeit Mathematik zu lernen und zu lehren ist jedem bekannt, der einmal mit diesem Fach in Berührung gekommen ist. Begriffe wie "reelle oder komplexe Zahlen, Pi" sind zwar jedem geläufig, aber nur wenige wissen, was sich wirklich dahinter verbirgt. Die Autoren dieses Bandes geben jedem, der mehr wissen will als nur die Hülle der Begriffe, eine meisterhafte Einführung in die Magie der Mathematik und schlagen einzigartige Brücken für Studenten. Die Rezensenten der ersten beiden Auflagen überschlugen sich.

A book about numbers sounds rather dull. This one is not. Instead it is a lively story about one thread of mathematics-the concept of "number"­ told by eight authors and organized into a historical narrative that leads the reader from ancient Egypt to the late twentieth century. It is a story that begins with some of the simplest ideas of mathematics and ends with some of the most complex. It is a story that mathematicians, both amateur and professional, ought to know. Why write about numbers? Mathematicians have always found it diffi­ cult to develop broad perspective about their subject. While we each view our specialty as having roots in the past, and sometimes having connec­ tions to other specialties in the present, we seldom see the panorama of mathematical development over thousands of years. Numbers attempts to give that broad perspective, from hieroglyphs to K-theory, from Dedekind cuts to nonstandard analysis.