Category theory is a branch of abstract algebra with incredibly diverse applications. This text and reference book is aimed not only at mathematicians, but also researchers and students of computer science, logic, linguistics, cognitive science, philosophy, and any of the other fields in which the ideas are being applied. Containing clear definitions of the essential concepts, illuminated with numerous accessible examples, and providing full proofs of all important propositions and theorems, this book aims to make the basic ideas, theorems, and methods of category theory understandable to this broad readership.
Although assuming few mathematical pre-requisites, the standard of mathematical rigour is not compromised. The material covered includes the standard core of categories; functors; natural transformations; equivalence; limits and colimits; functor categories; representables; Yoneda's lemma; adjoints; monads. An extra topic of cartesian closed categories and the lambda-calculus is also provided - a must for computer scientists, logicians and linguists
This Second Edition contains numerous revisions to the original text, including expanding the exposition, revising and elaborating the proofs, providing additional diagrams, correcting typographical errors and, finally, adding an entirely new section on monoidal categories. Nearly a hundred new exercises have also been added, many with solutions, to make the book more useful as a course text and for self-study.

H. Hermes: Basic notions and applications of the theory of decidability.- D. Kurepa: On several continuum hypotheses.- A. Mostowski: Models of set theory.- A. Robinson: Problems and methods of model theory.- S. Sochor, B. Balcar: The general theory of semisets. Syntactic models of the set theory.

Logic is sometimes called the foundation of mathematics: the logician studies the kinds of reasoning used in the individual steps of a proof. Alonzo Church was a pioneer in the field of mathematical logic, whose contributions to number theory and the theories of algorithms and computability laid the theoretical foundations of computer science. His first Princeton book, "The Calculi of Lambda-Conversion" (1941), established an invaluable tool that computer scientists still use today.

Even beyond the accomplishment of that book, however, his second Princeton book, "Introduction to Mathematical Logic," defined its subject for a generation. Originally published in Princeton's Annals of Mathematics Studies series, this book was revised in 1956 and reprinted a third time, in 1996, in the Princeton Landmarks in Mathematics series. Although new results in mathematical logic have been developed and other textbooks have been published, it remains, sixty years later, a basic source for understanding formal logic.

Church was one of the principal founders of the Association for Symbolic Logic; he founded the "Journal of Symbolic Logic" in 1936 and remained an editor until 1979 At his death in 1995, Church was still regarded as the greatest mathematical logician in the world.

Dieses umfassende Lehrbuch wurde geschrieben fur Studenten und Dozenten der Mathematik und Informatik, und wegen der ausfuhrlichen Darstellung der Godelschen Unvollstandigkeitssatze auch fur Fachstudenten der Philosophischen Logik.
Fur diese Neuauflage wurde der Text sachlich und stilistisch vollstandig uberarbeitet, er enthalt verbesserte Beweise und Ubungen mit Losungshinweisen sowie eine historisch orientierte Einleitung. Das Buch kann ganz unabhangig von Vorlesungen aber auch zum Selbststudium genutzt werden.

"

Anna-Christin Soehling beschreibt die Erkenntnisgewinnung wahrend des Problemloeseprozesses durch Probieren und Aufdecken von Irrtumern. Dabei nutzt sie das Begriffsnetz aus Deduktion, Abduktion und Induktion nach Peirce (1903) und Meyer (2007). Mathematische Problemloeseprozesse zeichnen sich oft durch Probieren und irrtumbehaftete Herangehensweisen aus. Dennoch scheinen Schulerinnen und Schuler nicht nur durch reinen Zufall zu einer Loesung zu kommen. Neben der philosophisch-logischen Rekonstruktion ebensolcher Prozesse beschaftigt sich die Autorin mit der Frage nach dem Erlernen von Mathematik durch Problemloesen.

Im Jahr 1931 erschien im Monatsheft fur Mathematik und Physik ein Artikel mit dem geheimnisvoll klingenden Titel UEber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I. In dieser Arbeit hat Kurt Goedel zwei Unvollstandigkeitssatze bewiesen, die unseren Blick auf die Mathematik von Grund auf verandert haben. Goedels Satze manifestieren, dass zwischen dem Begriff der Wahrheit und dem Begriff der Beweisbarkeit eine Kluft besteht, die wir nicht uberwinden koennen. Die Mathematik fugt sich in kein formales Korsett. Seit ihrer Entdeckung sind die Unvollstandigkeitssatze in aller Munde und eine Flut an Buchern widmet sich ihrem fulminanten Inhalt. Doch kaum ein Werk behandelt die Goedel'sche Arbeit in ihrer ursprunglichen Form - und dies hat triftige Grunde: Seine komplexen, in akribischer Prazision beschriebenen Argumentationsketten, die vielen Definitionen und Satze und die heute weitgehend uberholte Notation machen Goedels historisches Meisterwerk zu einer schwer zu lesenden Arbeit. In diesem Buch wird Goedels Beweis aus dem Jahr 1931 detailliert aufgearbeitet. Alle Einzelschritte werden erlautert und anhand zahlreicher Beispiele verstandlich erklart. Doch dieses Buch ist mehr als eine kommentierte Fassung der historischen Arbeit. Die Beweise der Unvollstandigkeitssatze in vollem Umfang zu verstehen, bedingt, die Geschichte zu verstehen, und so versetzen zahlreiche Exkurse den Leser in die Zeit zu Beginn des zwanzigsten Jahrhunderts zuruck. Es ist die Zeit, in der die Mathematik die groesste Krise ihrer Geschichte durchlebte, die Typentheorie und die axiomatische Mengenlehre Gestalt annahmen und sich Hilberts formalistische Logik und Brouwers intuitionistische Mathematik mit offenem Visier gegenuber standen. Die 2. Auflage ist vollstandig durchgesehen. Stimme zur ersten Auflage: "...eine didaktisch sehr gut gemachte Darstellung." Prof. Dr. Matthias Homeister, FH Brandenburg

Proof and Disproof in Formal Logic is a lively and entertaining introduction to formal logic providing an excellent insight into how a simple logic works. Formal logic allows you to check a logical claim without considering what the claim means. This highly abstracted idea is an essential and practical part of computer science. The idea of a formal system-a collection of rules and axioms, which define a universe of logical proofs-is what gives us programming languages and modern-day programming. This book concentrates on using logic as a tool: making and using formal proofs and disproofs of particular logical claims. The logic it uses-natural deduction-is very small and very simple; working with it helps you see how large mathematical universes can be built on small foundations. The book is divided into four parts:
Part I "Basics" gives an introduction to formal logic with a short history of logic and explanations of some technical words.
Part II "Formal Syntactic Proof" show you how to do calculations in a formal system where you are guided by shapes and never need to think about meaning. Your experiments are aided by Jape, which can operate as both inquisitor and oracle.
Part III "Formal Semantic Disproof" shows you how to construct mathematical counterexamples to shoe that proof is impossible. Jape can check the counterexamples you build.
Part IV" Program Specification and Proof" describes how to apply your logical understanding to a real computer science problem, the accurate description and verification of programs. Jape helps, as far as arithmetic allows.
Aimed at undergraduates and graduates in computer science, logic, mathematics and philosophy, thetext includes reference to and exercises based on the computer software package Jape, an interactive teaching and research tool designed and hosted by the author that is freely available on the web.

Proof and Disproof in Formal Logic is a lively and entertaining introduction to formal logic providing an excellent insight into how a simple logic works. Formal logic allows you to check a logical claim without considering what the claim means. This highly abstracted idea is an essential
and practical part of computer science. The idea of a formal system-a collection of rules and axioms, which define a universe of logical proofs-is what gives us programming languages and modern-day programming. This book concentrates on using logic as a tool: making and using formal proofs and
disproofs of particular logical claims. The logic it uses-natural deduction-is very small and very simple; working with it helps you see how large mathematical universes can be built on small foundations. The book is divided into four parts:
Part I "Basics" gives an introduction to formal logic with a short history of logic and explanations of some technical words.
Part II "Formal Syntactic Proof" show you how to do calculations in a formal system where you are guided by shapes and never need to think about meaning. Your experiments are aided by Jape, which can operate as both inquisitor and oracle.
Part III "Formal Semantic Disproof" shows you how to construct mathematical counterexamples to shoe that proof is impossible. Jape can check the counterexamples you build.
Part IV" Program Specification and Proof" describes how to apply your logical understanding to a real computer science problem, the accurate description and verification of programs. Jape helps, as far as arithmetic allows.
Aimed at undergraduates and graduates in computer science, logic, mathematics and philosophy, thetext includes reference to and exercises based on the computer software package Jape, an interactive teaching and research tool designed and hosted by the author that is freely available on the
web.

The ability to reason and think in a logical manner forms the basis of learning for most mathematics, computer science, philosophy and logic students. Based on the author's teaching notes at the University of Maryland and aimed at a broad audience, this text covers the fundamental topics in classical logic in an extremely clear, thorough and accurate style that is accessible to all the above. Covering propositional logic, first-order logic, and second-order logic, as well as proof theory, computability theory, and model theory, the text also contains numerous carefully graded exercises and is ideal for a first or refresher course.

Carsten Roesnick legt seiner Arbeit die Frage nach der algorithmischen Komplexitat der approximativen Berechnung von Operatoren aus Geometrie, Topologie und Analysis zugrunde. Er betrachtet Operatoren wie Mengendurchschnitt, Projektion, Maximierung, Integration und Funktionsinversion. Der Begriff der Komplexitat ist hierbei im rigorosen Sinne von garantierten Laufzeitschranken und asymptotischen Optimalitatsbeweisen zu verstehen. Dazu fuhrt der Autor Kodierungen fur Mengen und Funktionen ein und untersucht sie hinsichtlich ihrer (Polynomialzeit-)AEquivalenz, um schliesslich in der Bestimmung parametrisierter Komplexitatsschranken fur obige Operatoren Verwendung zu finden.

Wie ist ein Ring definiert, wann kann man Grenzprozesse vertauschen, was sind lineare Ordnungen und wozu benoetigt man das Zornsche Lemma in der Linearen Algebra? Das Buch will seinen Lesern helfen, sich in der Fulle der grundlegenden mathematischen Definitionen zurecht zu finden und exemplarische mathematische Ergebnisse einordnen und ihre Eigenheiten verstehen zu koennen. Es behandelt hierzu je zwoelf Schlusselkonzepte der folgenden zwoelf Themengebiete der Mathematik: Grundlagen Zahlen Zahlentheorie Diskrete Mathematik Lineare Algebra Algebra Elementare Analysis Hoehere Analysis Topologie und Geometrie Numerik Stochastik Mengenlehre und Logik Ein besonderes Augenmerk liegt auf einer knappen und prazisen, dabei aber nicht zu formalen Darstellung. Dadurch erlauben die einzelnen Beitrage ein fokussiertes Nachlesen ebenso wie ein neugieriges Kennenlernen. Das Buch ist geschrieben fur Studierende der Mathematik ab dem ersten Semester und moechte ein treuer Begleiter und eine zuverlassige Orientierungshilfe fur das gesamte Studium sein. Die 2. Auflage ist vollstandig durchgesehen und um Literaturangaben erganzt.

Achim Mees untersucht Fragen zur Robustheit von Konfidenzbereichen und statistischen Tests, wobei der Fokus auf Konfidenzbereichen und Tests fur den Erwartungswert unabhangiger identisch verteilter Beobachtungsgroessen liegt. Neben der Zusammenfassung und Ausarbeitung bereits bestehender Ergebnisse werden zwei neue Resultate prasentiert. Zum einen wird die Nichtrobustheit des t-Tests und ahnlicher Tests fur absolut stetige unimodale Verteilungen auf einem beschrankten Intervall und zum anderen die Robustheit des t-Tests fur log-konkave Verteilungen auf der reellen Achse gezeigt. Ausserdem werden vier robuste Konfidenzintervalle fur Erwartungswerte miteinander verglichen.

Succinct representation and fast access to large amounts of data are challenges of our time. This unique book suggests general approaches of 'complexity of descriptions'. It deals with a variety of concrete topics and bridges between them, while opening new perspectives and providing promising avenues for the 'complexity puzzle'.

The theory of lattices, initiated by Dedekind in the past centu- ry, and revived in the thirties by Garrett Birkhoff, F. Klein-Barmen, ore, and von Neumann, is only in our time coming into its own. The fledgling theory was handicapped by a contingent historical circumstance. The peculiarities of mathematical personality of the founders made lattice theory less welcome to the mathematical public of the time than it otherwise might have been. Thus Dedekind was wi- dely thought in his time to be far too abstract for his own good, and some of his peers, notably Kronecker, did not hesitate to state their loud and clear disapproval. Later on, the tempers of Garrett Birkhoff and John von Neumann clashed with those of some of the "mainstream"' mathematicians of their time. Norman Levinson once related to me the following anecdote about von Neumann. Invited to deliver the weekly mathematics colloquium at Harvard sometime in the thirties, he chose the subject of his current interest, namely, continuous geometries. At the end of the lecture, as the public was streaming out, G. H. Hardy, who was at the time visiting Cambridge, was overheard whispering to G. D. Birkhoff (Gar- rett's father): "He is quite clearly a very brilliant man, but why does he waste his time on this stuff?" I myself, when still an assistant professor, was once stopped in the hall of M. I. T.

Gli Automi sono modelli matematici di macchine digitali di grande interesse sia dal punto di vista teorico che applicativo. La teoria degli Automi Finiti costituisce una delle parti fondamentali dell Informatica Teorica. Questo volume fornisce, per la prima volta, nel panorama didattico italiano una trattazione matematicamente rigorosa della teoria degli Automi Finiti e delle macchine sequenziali generalizzate nell ambito della teoria algebrica dei semigruppi. Il volume, la cui lettura presuppone solamente conoscenze elementari di algebra, si rivolge agli studenti sia dei corsi di laurea magistrale e specialistica che di master e di dottorato in Informatica, in Matematica, ed in Ingegneria. Il libro e anche uno strumento utilissimo per gli studiosi di Informatica e, in particolare, di Informatica Teorica, ai quali fornisce una trattazione completa e rigorosa della teoria algebrica degli Automi. Ogni capitolo ha una sezione di esercizi ed una di note bibliografiche. La risoluzione della maggior parte degli esercizi e riportata alla fine del volume.

Der Mathematiker David Hilbert entwickelte mit seiner Beweistheorie ein Programm zur Grundlegung der Mathematik. In der ersten deutschsprachigen Monographie zum Thema bietet der Autor neue Deutungen des Hilbertprogramms. Ausgehend von den historischen Quellen stellt er die Frage neu, ob Hilbert eine formalistische Philosophie der Mathematik voraussetzte. Er macht die Fulle der Ideen sichtbar, die Hilbert und seine Schuler formulierten, diskutiert anspruchsvolle philosophische Implikationen und raumt mit einer Reihe von Fehlinterpretationen auf."

Some of our earliest experiences of the conclusive force of an argument come from school mathematics: faced with a mathematical proof, we cannot deny the conclusion once the premises have been accepted. Behind such arguments lies a more general pattern of 'demonstrative arguments' that is studied in the science of logic. Logical reasoning is applied at all levels, from everyday life to advanced sciences, and a remarkable level of complexity is achieved in everyday logical reasoning, even if the principles behind it remain intuitive. Jan von Plato provides an accessible but rigorous introduction to an important aspect of contemporary logic: its deductive machinery. He shows that when the forms of logical reasoning are analysed, it turns out that a limited set of first principles can represent any logical argument. His book will be valuable for students of logic, mathematics and computer science.

herrschen. Bedeutsam ist auch die Abgrenzung der dritten Ebene, der Ebene der verselb- standigten Variablen und Zeiger. Der vergleichsweise geringe Umfang von Kap. 7 bedeutet einerseits, dass die Beschreibung sich auf Grundsatzliches beschrankt, dem sich viele aus der Literatur der Systemprogrammierung bekannte Einzelheiten unterordnen, beispiels- weise aus D. E. Knuth's, The Art of Computer Programming' oder G. Seegmullers, Ein- fuhrung in die Systemprogrammierung', andererseits aber auch, dass die Vervollstandi- gung der theoretischen Grundlagen noch aussteht. Zu den einzelnen Abschnitten dieses Buches gibt es einen Hintergrund unterschiedlich weit entwickelter mathematischer Theorien. Wichtige Grundbegriffe sind verbandstheore- tischer Natur. Die fundamentalen Arbeiten von D. Scott haben das eindrucksvoll bewie- sen. Bei den Rechenstrukturen des 3. Kapitels steht die moderne Theorie der universellen Algebra im Hintergrund, insbesondere Arbeiten von Birkhoff und Tarski sind hier von Be- deutung. Da wir kein mathematisches Lehrbuch vorlegen, mussen wir uns meistens mit Andeutungen und Hinweisen begnugen. Das Buch hat sich aus Vorlesungen und begleitenden UEbungen entwickelt, die in den letz- ten Jahren an der Technischen Universitat Munchen gehalten wurden. Es entstand in enger Wechselwirkung mit dem Projekt CIP ("Computer-aided Intuition-guided Programming") und dem Teilprojekt "Breitbandsprache und Programmtransformation" im Sonderfor- schungsbereich 49, Programmiertechnik, an der Technischen Universitat Munchen. Bei dem Versuch, fur ein einigermassen abgerundetes, geschlossenes Lehrgebaude der Programmie- rung die Fundamente zu legen, musste vieles fragmentarisch bleiben. In manchen Punkten war es notwendig, Positionen zu beziehen, die auf den ersten Blick unkonventionell erschei- nen moegen, um Erstarrungen zu loesen und einseitige Doktrinen zu korrigieren.

Gerhard Gentzen (1909-1945) ist der Begrunder der modernen mathematischen Beweistheorie. Die nachhaltige Bedeutung der von ihm entwickelten Methoden, Regeln und Strukturen zeigt sich heute in wichtigen Teilgebieten der Informatik, in der Verifikation von Programmen. Die Arbeiten Gentzens uber das naturliche Schliessen, der Sequenzenkalkul und die Ordinal-Beweistheorie beeindrucken noch heute durch ihre Einsicht und Eleganz. Der Autor dokumentiert in dieser ersten umfassenden Biografie Leben und Werk Gerhard Gentzens, seinen tragischen Lebensweg, Festnahme 1945 in Prag, Gefangenschaft und Tod. Die Bedingungen wissenschaftlicher Forschung, in diesem Fall der mathematischen Logik, im nationalsozialistischen Deutschland, den ideologischen Kampf um eine "Deutsche Logik" und deren Protagonisten ist ein weiterer Schwerpunkt des Buches. Zahlreiche, bislang unveroffentlichte Quellen, Fotos und Dokumente aus Korrespondenzen und Nachlass sowie der Abdruck dreier Vortrage von Gerhard Gentzen machen dieses Buch zu einer erstrangigen Informationsquelle uber diesen bedeutenden Mathematiker und seine Zeit. Der Band wird erganzt durch ein Essay von Jan von Plato uber Gentzens Beweistheorie und deren Entwicklung bis zur Gegenwart."

Nell'infanzia si pongono i classici interrogativi con tanti "perche?." Purtroppo poi, nel corso dell'educazione matematica, la curiosita diminuisce e spesso ci si accontenta di chiedere "come si fa?." Questo libro e dedicato ai perche della logica e teoria degli insiemi, dell'analisi matematica, della probabilita e statistica. Si completano cosi gli argomenti di matematica insegnati a scuola, dopo i precedenti testi di V. Villani sui perche dell'algebra e geometria. Il titolo contiene un messaggio. In logica si affronta il calcolo delle proposizioni, l'analisi matematica e nota anche col nome di calcolo, la probabilita e detta calcolo delle probabilita. In tutti e tre i casi si potrebbe focalizzare l'attenzione sulla parola calcolo. Ma questo e riduttivo: il calcolo e una componente importante, ma altrettanto importante e la comprensione critica di tutto cio che sta alla base dei calcoli. Il libro e rivolto a chi insegna matematica e a tutte le persone che hanno conservato una genuina curiosita scientifica."

This book contains twenty-one essays by leading authorities on aspects of contemporary logic, ranging from foundations of set theory to applications of logic in computing and in the theory of fields. In those parts of logic closest to computer science, the gap between foundations and applications is often small, as illustrated by three essays on the proof theory of non-classical logics. There are also chapters on the lambda calculus, on relating logic programs to inductive definitions, on Buechi and Presburger arithmetics, and on definability in Lindenbaum algebras. Aspects of constructive mathematics discussed are embeddings of Heyting algebras and proofs in mathematical anslysis. Set theory is well covered with six chapters discussing Cohen forcing, Baire category, determinancy, Nash-Williams theory, critical points (and the remarkable connection between them and properties of left distributive operations) and independent structures. The longest chapter in the book is a survey of 0-minimal structures, by Lou van den Dries; during the last ten years these structures have come to take a central place in applications of model theory to fields and function theory, and this chapter is the first broad survey of the area. Other chapters illustrate how to apply model theory to field theory, complex geometry and groups, and how to recover from its automorphism group. Finally, one chapter applies to the theory of toric varieties to solve problems about many-valued logics.