Bringing together over twenty years of research, this book gives a complete overview of independence-friendly logic. It emphasizes the game-theoretical approach to logic, according to which logical concepts such as truth and falsity are best understood via the notion of semantic games. The book pushes the paradigm of game-theoretical semantics further than the current literature by showing how mixed strategies and equilibria can be used to analyze independence-friendly formulas on finite models. The book is suitable for graduate students and advanced undergraduates who have taken a course on first-order logic. It contains a primer of the necessary background in game theory, numerous examples and full proofs.

A N Prior has a special place in the history of postwar philosophy for his highly original work at the intersection of logic and metaphysics. His logical innovations have found many applications in the areas of philosophical logic, mathematics, linguistics, and, increasingly, computer science. In addition, he made seminal contributions to debates in metaphysics, particularly on modality and the nature of time. This volume presents a selection of current research in the areas that were of most interest to Prior: temporal and tense logic, modal logic, proof theory, quantification and individuation, and the logic of agency. Both title and contents reflect Prior's view that logic is 'about the real world', and the orientation of the volume is towards the application of logic, in philosophy, computer science, and elsewhere. Following Prior, modal syntax is now widely applied to the formalization of a variety of subject matters, and tense logic has found numerous applications in computing, for example in natural language processing, logical deduction involving time-dependent data, program-verification, and VLSI. A special feature of the volume is the inclusion of three hitherto unpublished pieces by Prior on modal logic and the philosophy of time, along with a complete bibliography of Prior's published philosophical writings.

This textbook offers a detailed introduction to the methodology and applications of sequent calculi in propositional logic. Unlike other texts concerned with proof theory, emphasis is placed on illustrating how to use sequent calculi to prove a wide range of metatheoretical results. The presentation is elementary and self-contained, with all technical details both formally stated and also informally explained. Numerous proofs are worked through to demonstrate methods of proving important results, such as the cut-elimination theorem, completeness, decidability, and interpolation. Other proofs are presented with portions left as exercises for readers, allowing them to practice techniques of sequent calculus. After a brief introduction to classical propositional logic, the text explores three variants of sequent calculus and their features and applications. The remaining chapters then show how sequent calculi can be extended, modified, and applied to non-classical logics, including modal, intuitionistic, substructural, and many-valued logics. Sequents and Trees is suitable for graduate and advanced undergraduate students in logic taking courses on proof theory and its application to non-classical logics. It will also be of interest to researchers in computer science and philosophers.

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.

This long awaited book gives a thorough account of the mathematical foundations of Temporal Logic, one of the most important areas of logic in computer science. The book, which consists of fifteen chapters, moves on from giving a solid introduction in semantical and axiomatic approaches to temporal logic to covering the central topics of predicate temporal logic, meta-languages, general theories of axiomatization, many dimensional systems, propositional quantifiers, expressive power, Henkin dimension, temporalization of other logics, and decidability results. Much of the research presented here is frontline in the new results and in the unifying methodology. This is an indispensable reference work for both the pure logician and the theoretical computer scientist.

This open access book makes a case for extending logic beyond its traditional boundaries, to encompass not only statements but also also questions. The motivations for this extension are examined in detail. It is shown that important notions, including logical answerhood and dependency, emerge as facets of the fundamental notion of entailment once logic is extended to questions, and can therefore be treated with the logician's toolkit, including model-theoretic constructions and proof systems. After motivating the enterprise, the book describes how classical propositional and predicate logic can be made inquisitive-i.e., extended conservatively with questions-and what the resulting logics look like in terms of meta-theoretic properties and proof systems. Finally, the book discusses the tight connections between inquisitive logic and dependence logic.

In the last 60 years, the use of the notion of category has led to a remarkable unification and simplification of mathematics. Conceptual Mathematics introduces this tool for the learning, development, and use of mathematics, to beginning students and also to practising mathematical scientists. This book provides a skeleton key that makes explicit some concepts and procedures that are common to all branches of pure and applied mathematics. The treatment does not presuppose knowledge of specific fields, but rather develops, from basic definitions, such elementary categories as discrete dynamical systems and directed graphs; the fundamental ideas are then illuminated by examples in these categories. This second edition provides links with more advanced topics of possible study. In the new appendices and annotated bibliography the reader will find concise introductions to adjoint functors and geometrical structures, as well as sketches of relevant historical developments.

This book reports on cutting-edge concepts related to Bourbaki's notion of structures meres. It merges perspectives from logic, philosophy, linguistics and cognitive science, suggesting how they can be combined with Bourbaki's mathematical structuralism in order to solve foundational, ontological and epistemological problems using a novel category-theoretic approach. By offering a comprehensive account of Bourbaki's structuralism and answers to several important questions that have arisen in connection with it, the book provides readers with a unique source of information and inspiration for future research on this topic.

This book constitutes a self-contained and unified approach to automated reasoning in multiple-valued logics (MVL) developed by the author. Moreover, it contains a virtually complete account of other approaches to automated reasoning in MVL. This is the first overview of this subfield of automated reasoning ever given. Finally, a variety of applications of automated reasoning in MVL including several short case studies are listed. Automated reasoning in non-classical logics is an essential subtask of many AI applications. Applications of MVL in particular include, for instance, hardware and software verification, reasoning with incomplete or inconsistent knowledge, and natural language processing. Therefore, efficient theorem proving methods in MVL are essential. In the historical part of the book it is demonstrated why existing approaches are inadequate. In the original part a simple, but powerful, concept called 'sets-as-signs' is introduced in the context of semantic tableaux, and subsequently is applied to a variety of calculi including resolution and dissolution. It is shown that 'sets-as-signs' yields a many-valued extension of the well-known relationship between classical logic and integer programming. As a consequence, automated reasoning in infinitely-valued logics can be done uniformly and efficiently for the first time.

Structural proof theory is a branch of logic that studies the general structure and properties of logical and mathematical proofs. This book is both a concise introduction to the central results and methods of structural proof theory, and a work of research that will be of interest to specialists. The book is designed to be used by students of philosophy, mathematics and computer science. The book contains a wealth of results on proof-theoretical systems, including extensions of such systems from logic to mathematics, and on the connection between the two main forms of structural proof theory - natural deduction and sequent calculus. The authors emphasize the computational content of logical results. A special feature of the volume is a computerized system for developing proofs interactively, downloadable from the web and regularly updated.

Alfred Tarski, one of the greatest logicians of all time, is widely thought of as 'the man who defined truth'. His mathematical work on the concepts of truth and logical consequence are cornerstones of modern logic, influencing developments in philosophy, linguistics and computer science. Tarski was a charismatic teacher and zealous promoter of his view of logic as the foundation of all rational thought, a bon-vivant and a womanizer, who played the 'great man' to the hilt. Born in Warsaw in 1901 to Jewish parents, he changed his name and converted to Catholicism, but was never able to obtain a professorship in his home country. A fortuitous trip to the United States at the outbreak of war saved his life and turned his career around, even while it separated him from his family for years. By the war's end he was established as a professor of mathematics at the University of California, Berkeley. There Tarski built an empire in logic and methodology that attracted students and distinguished researchers from all over the world. From the cafes of Warsaw and Vienna to the mountains and deserts of California, this first full length biography places Tarski in the social, intellectual and historical context of his times and presents a frank, vivid picture of a personally and professionally passionate man, interlaced with an account of his major scientific achievements.

Packed with more than a hundred color illustrations and a wide variety of puzzles and brainteasers, Taking Sudoku Seriously uses this popular craze as the starting point for a fun-filled introduction to higher mathematics.
How many Sudoku solution squares are there? What shapes other than three-by-three blocks can serve as acceptable Sudoku regions? What is the fewest number of starting clues a sound Sudoku puzzle can have? Does solving Sudoku require mathematics? Jason Rosenhouse and Laura Taalman show that answering these questions opens the door to a wealth of interesting mathematics. Indeed, they show that Sudoku puzzles and their variants are a gateway into mathematical thinking generally. Among many topics, the authors look at the notion of a Latin square--an object of long-standing interest to mathematicians--of which Sudoku squares are a special case; discuss how one finds interesting Sudoku puzzles; explore the connections between Sudoku, graph theory, and polynomials; and consider Sudoku extremes, including puzzles with the maximal number of vacant regions, with the minimal number of starting clues, and numerous others. The book concludes with a gallery of novel Sudoku variations--just pure solving fun Most of the puzzles are original to this volume, and all solutions to the puzzles appear in the back of the book or in the text itself.
A math book and a puzzle book, Taking Sudoku Seriously will change the way readers look at Sudoku and mathematics, serving both as an introduction to mathematics for puzzle fans and as an exploration of the intricacies of Sudoku for mathematics buffs.

Topos theory provides an important setting and language for much of mathematical logic and set theory. It is well known that a typed language can be given for a topos to be regarded as a category of sets. This enables a fruitful interplay between category theory and set theory. However, one stumbling block to a logical approach to topos theory has been the treatment of geometric morphisms. This book presents a convenient and natural solution to this problem by developing the notion of a frame relative to an elementary topos. The authors show how this technique enables a logical approach to be taken to topics such as category theory relative to a topos and the relative Giraud theorem. The work is self-contained except that the authors presuppose a familiarity with basic category theory and topos theory. Logicians, set and category theorists, and computer scientist working in the field will find this work essential reading.

Als mehrbandiges Nachschlagewerk ist das Springer-Handbuch der Mathematik in erster Linie fur wissenschaftliche Bibliotheken, akademische Institutionen und Firmen sowie interessierte Individualkunden in Forschung und Lehregedacht. Es erganzt das einbandige themenumfassende Springer-Taschenbuch der Mathematik (ehemaliger Titel Teubner-Taschenbuch der Mathematik), das sich in seiner begrenzten Stoffauswahl besonders an Studierende richtet.Teil IV des Springer-Handbuchs enthalt die folgenden Zusatzkapitel zum Springer-Taschenbuch: Hohere Analysis, Lineare sowie Nichtlineare Funktionalanalysis und ihre Anwendungen, Dynamische Systeme, Nichtlineare partielle Differentialgleichungen, Mannigfaltigkeiten, Riemannsche Geometrie und allgemeine Relativitatstheorie, Liegruppen, Liealgebren und Elementarteilchen, Topologie, Krummung und Analysis.

Recent applications to biomolecular science and DNA computing have created a new audience for automata theory and formal languages. This is the only introductory book to cover such applications. It begins with a clear and readily understood exposition of the fundamentals that assumes only a background in discrete mathematics. The first five chapters give a gentle but rigorous coverage of basic ideas as well as topics not found in other texts at this level, including codes, retracts and semiretracts. Chapter 6 introduces combinatorics on words and uses it to describe a visually inspired approach to languages. The final chapter explains recently-developed language theory coming from developments in bioscience and DNA computing. With over 350 exercises (for which solutions are available), many examples and illustrations, this text will make an ideal contemporary introduction for students; others, new to the field, will welcome it for self-learning.

This book presents the latest research, conducted by leading philosophers and scientists from various fields, on the topic of top-down causation. The chapters combine to form a unique, interdisciplinary perspective, drawing upon George Ellis's extensive research and novel perspectives on topics including downwards causation, weak and strong emergence, mental causation, biological relativity, effective field theory and levels in nature. The collection also serves as a Festschrift in honour of George Ellis' 80th birthday. The extensive and interdisciplinary scope of this book makes it vital reading for anyone interested in the work of George Ellis and current research on the topics of causation and emergence.

Petri nets are a popular and powerful formal model for the analysis and modelling of concurrent systems, and a rich theory has developed around them. Petri nets are taught to undergraduates, and also used by industrial practitioners. This book focuses on a particular class of petri nets, free choice petri nets, which play a central role in the theory. The text is very clearly organised, with every notion carefully explained and every result proved. Clear exposition is given for place invariants, siphons, traps and many other important analysis techniques. The material is organised along the lines of a course book, and each chapter contains numerous exercises, making this book ideal for graduate students and research workers alike.

Als mehrbandiges Nachschlagewerk ist das Springer-Handbuch der Mathematik in erster Linie fur wissenschaftliche Bibliotheken, akademische Institutionen und Firmen sowie interessierte Individualkunden in Forschung und Lehregedacht. Es erganzt das einbandige themenumfassende Springer-Taschenbuch der Mathematik (ehemaliger Titel Teubner-Taschenbuch der Mathematik), das sich in seiner begrenzten Stoffauswahl besonders an Studierende richtet. Teil I des Springer-Handbuchs enthalt neben dem einfuhrenden Kapitel und dem Kapitel 1 des Springer-Taschenbuchs zusatzliches Material zur hoheren komplexen Funktionentheorie und zur allgemeinen Theorie der partiellen Differentialgleichungen.

Methods of dimensionality reduction provide a way to understand and visualize the structure of complex data sets. Traditional methods like principal component analysis and classical metric multidimensional scaling suffer from being based on linear models. Until recently, very few methods were able to reduce the data dimensionality in a nonlinear way. However, since the late nineties, many new methods have been developed and nonlinear dimensionality reduction, also called manifold learning, has become a hot topic. New advances that account for this rapid growth are, e.g. the use of graphs to represent the manifold topology, and the use of new metrics like the geodesic distance. In addition, new optimization schemes, based on kernel techniques and spectral decomposition, have lead to spectral embedding, which encompasses many of the

This introduction to first-order logic clearly works out the role of first-order logic in the foundations of mathematics, particularly the two basic questions of the range of the axiomatic method and of theorem-proving by machines. It covers several advanced topics not commonly treated in introductory texts, such as Fraisse's characterization of elementary equivalence, Lindstroem's theorem on the maximality of first-order logic, and the fundamentals of logic programming.

This volume presents the state of the art in the algebraic investigation into substructural logics. It features papers from the workshop AsubL (Algebra & Substructural Logics - Take 6). Held at the University of Cagliari, Italy, this event is part of the framework of the Horizon 2020 Project SYSMICS: SYntax meets Semantics: Methods, Interactions, and Connections in Substructural logics. Substructural logics are usually formulated as Gentzen systems that lack one or more structural rules. They have been intensively studied over the past two decades by logicians of various persuasions. These researchers include mathematicians, philosophers, linguists, and computer scientists. Substructural logics are applicable to the mathematical investigation of such processes as resource-conscious reasoning, approximate reasoning, type-theoretical grammar, and other focal notions in computer science. They also apply to epistemology, economics, and linguistics. The recourse to algebraic methods -- or, better, the fecund interplay of algebra and proof theory -- has proved useful in providing a unifying framework for these investigations. The AsubL series of conferences, in particular, has played an important role in these developments. This collection will appeal to students and researchers with an interest in substructural logics, abstract algebraic logic, residuated lattices, proof theory, universal algebra, and logical semantics.

Philosophical considerations, which are often ignored or treated casually, are given careful consideration in this introduction. Thomas Forster places the notion of inductively defined sets (recursive datatypes) at the center of his exposition resulting in an original analysis of well established topics. The presentation illustrates difficult points and includes many exercises. Little previous knowledge of logic is required and only a knowledge of standard undergraduate mathematics is assumed.

This volume presents articles from four outstanding researchers who work at the cusp of analysis and logic. The emphasis is on active research topics; many results are presented that have not been published before and open problems are formulated. Considerable effort has been made by the authors to make their articles accessible to mathematicians new to the area

This book reports on cutting-edge concepts related to Bourbaki's notion of structures meres. It merges perspectives from logic, philosophy, linguistics and cognitive science, suggesting how they can be combined with Bourbaki's mathematical structuralism in order to solve foundational, ontological and epistemological problems using a novel category-theoretic approach. By offering a comprehensive account of Bourbaki's structuralism and answers to several important questions that have arisen in connection with it, the book provides readers with a unique source of information and inspiration for future research on this topic.

What is the shortest possible route for a traveling salesman seeking to visit each city on a list exactly once and return to his city of origin? It sounds simple enough, yet the traveling salesman problem is one of the most intensely studied puzzles in applied mathematics--and it has defied solution to this day. In this book, William Cook takes readers on a mathematical excursion, picking up the salesman's trail in the 1800s when Irish mathematician W. R. Hamilton first defined the problem, and venturing to the furthest limits of today's state-of-the-art attempts to solve it. He also explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets.

"In Pursuit of the Traveling Salesman" travels to the very threshold of our understanding about the nature of complexity, and challenges you yourself to discover the solution to this captivating mathematical problem.