Bücher der Reihe Lecture Notes in Logic

Ordinal Definability and Recursion Theory is the third in a series of four books presenting the seminal papers from the Caltech-UCLA 'Cabal Seminar' with extensive unpublished material, new papers on related topics, and discussion of research developments since the publication of the original volumes.

Constraint Satisfaction Problems (CSPs) are natural computational problems that appear in many areas of theoretical computer science. Exploring which CSPs are solvable in polynomial time and which are NP-hard reveals a surprising link with central questions in universal algebra. This monograph presents a self-contained introduction to the universal-algebraic approach to complexity classification, treating both finite and infinite-domain CSPs. It includes the required background from logic and combinatorics, particularly model theory and Ramsey theory, and explains the recently discovered link between Ramsey theory and topological dynamics and its implications for CSPs. The book will be of interest to graduate students and researchers in theoretical computer science and to mathematicians in logic, combinatorics, and dynamics who wish to learn about the applications of their work in complexity theory.

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the first publication in the Lecture Notes in Logic series, Shoenfield gives a clear and focused introduction to recursion theory. The fundamental concept of recursion makes the idea of computability accessible to a mathematical analysis, thus forming one of the pillars on which modern computer science rests. This introduction is an ideal instrument for teaching and self-study that prepares the reader for the study of advanced monographs and the current literature on recursion theory.

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the fifth publication in the Lecture Notes in Logic series, the authors give an insightful introduction to the fascinating subject of the model theory of fields, concentrating on its connections to stability theory. In the first two chapters David Marker gives an overview of the model theory of algebraically closed, real closed and differential fields. In the third chapter Anand Pillay gives a proof that there are 2 non-isomorphic countable differential closed fields. Finally, Margit Messmer gives a survey of the model theory of separably closed fields of characteristic p > 0.

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the fourth publication in the Lecture Notes in Logic series, Miller develops the necessary features of the theory of descriptive sets in order to present a new proof of Louveau's separation theorem for analytic sets. While some background in mathematical logic and set theory is assumed, the material is based on a graduate course given by the author at the University of Wisconsin, Madison, and is thus accessible to students and researchers alike in these areas, as well as in mathematical analysis.

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the ninth publication in the Lecture Notes in Logic series, Martin Otto gives an introduction to finite model theory that indicates the main ideas and lines of inquiry that motivate research in this area. Particular attention is paid to bounded variable infinitary logics, with and without counting quantifiers, related fixed-point logics, and the corresponding fragments of Ptime. The relations with Ptime exhibit the fruitful exchange between ideas from logic and from complexity theory that is characteristic of finite model theory.

An advanced graduate course. Some knowledge of forcing is assumed, and some elementary Mathematical Logic, e.g. the Lowenheim-Skolem Theorem. A student with one semester of mathematical logic and 1 of set theory should be prepared to read these notes. The first half deals with the general area of Borel hierarchies. What are the possible lengths of a Borel hierarchy in a separable metric space? Lebesgue showed that in an uncountable complete separable metric space the Borel hierarchy has uncountably many distinct levels, but for incomplete spaces the answer is independent. The second half includes Harrington's Theorem - it is consistent to have sets on the second level of the projective hierarchy of arbitrary size less than the continuum and a proof and appl- ications of Louveau's Theorem on hyperprojective parameters.

This monograph is an exposition of the very general approach to the algebraization of sentential logics developed by the Barcelona logic group in the 1970s. It shows the results of this approach on a number of particular logics, and relates it to those developed by Blok, Czelakowski, Pigozzi and others.

Large cardinal hypotheses play a central role in modern set theory. This volume develops a method for constructing core models that have Woodin cardinals, a large cardinal hypothesis that is the focus of much current research. It is suitable for advanced graduate students and researchers in set theory.

This volume presents the conference proceedings of the 1995 Annual European Summer Meeting of the Association of Symbolic Logic. The papers here cover all topics of classical mathematical logic. There is also a tutorial on recent developments in theoretical computer science, and plenary lectures on the foundation and evolution of set theory.

This volume presents the proceedings of the 1996 European Summer Meeting of the Association for Symbolic Logic, held in San Sebastian, Spain. The main topics were model theory, proof theory, recursion and complexity theory, models of arithmetic, logic for artificial intelligence, formal semantics of natural language, and philosophy of contemporary logic.

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the third publication in the Lecture Notes in Logic series, Mitchell and Steel construct an inner model with a Woodin cardinal and develop its fine structure theory. This work builds upon the existing theory of a model of the form L[E], where E is a coherent sequence of extenders, and relies upon the fine structure theory of L[E] models with strong cardinals, and the theory of iteration trees and 'backgrounded' L[E] models with Woodin cardinals. This work is what results when fine structure meets iteration trees.

The proceedings of the Association for Symbolic Logic meeting held in Helsinki, Finland, in July 1990, containing eighteen papers written by leading researchers in logic. Between them they cover all fields of mathematical logic, including model theory, proof theory, recursion theory, and set theory.

The proceedings of the conference 'Logical Foundations of Mathematics, Computer Science, and Physics - Kurt Goedel's Legacy', held in Brno, Czech Republic, on the 90th anniversary of Goedel's birth. The papers in this volume cover the wide range of topics Goedel's work touched, and affirm its continuing importance.

This book is the first modern introduction to the logic of infinitary languages in forty years, and is aimed at graduate students and researchers in all areas of mathematical logic. Connections between infinitary model theory and other branches of mathematical logic, and applications to algebra and algebraic geometry are both comprehensively explored.

In this international cross-disciplinary collaboration, leading experts explore connections across their respective fields. The book offers an insight into the fundamental questions in quantum theory and logic, which will appeal to many researchers and graduate students including logicians, mathematicians, computer scientists, and physicists.

The Annual European Meeting of the Association for Symbolic Logic, generally known as the Logic Colloquium, is the most prestigious annual meeting in the field. Many of the papers presented there are invited surveys of developments, and the rest of the papers are chosen to complement the invited talks. This 2007 volume includes surveys, tutorials, and selected research papers from the 2005 meeting. Highlights include three papers on different aspects of connections between model theory and algebra; a survey of major advances in combinatorial set theory; a tutorial on proof theory and modal logic; and a description of Bernay's philosophy of mathematics.

This book, the first on the rapidly expanding topic of NIP theories, gives an accessible introduction to the subject for students and researchers in model theory and related areas such as combinatorics and algebraic geometry. It covers the basic notions while presenting a concise, elegant tour through the main results.

Large cardinal hypotheses play a central role in modern set theory. Here the author extends this theory so that it can produce core models satisfying "There is a Woodin cardinal", a large cardinal hypothesis which is the focus of much current research.

The Annual European Meeting of the Association for Symbolic Logic is among the most prestigious annual meetings in the field. Logic Colloquium 2007, with contributions from plenary speakers and selected special session speakers, contains both expository and research papers by some of the best logicians in the world.

The purpose of this monograph is to develop a very general approach to the algebra ization of sententiallogics, to show its results on a number of particular logics, and to relate it to other existing approaches, namely to those based on logical matrices and the equational consequence developed by Blok, Czelakowski, Pigozzi and others.

Papers examining aspects of Godel's work gathered from a symposium celebrating Goedel's centennial and papers from a 2004 ASL symposium.

This concise introduction to model theory begins with standard notions and takes the reader through to more advanced topics such as stability, simplicity and Hrushovski constructions. The authors introduce the classic results, as well as more recent developments in this vibrant area of mathematical logic. Concrete mathematical examples are included throughout to make the concepts easier to follow. The book also contains over 200 exercises, many with solutions, making the book a useful resource for graduate students as well as researchers.

Wadge Degrees and Projective Ordinals is the second of a series of four books presenting the seminal papers from the Caltech-UCLA 'Cabal Seminar' with extensive unpublished material, new papers on related topics and discussion of research developments since the publication of the original volumes.

The Annual European Meeting of the Association for Symbolic Logic is among the most prestigious annual meetings in the field. Logic Colloquium 2007, with contributions from plenary speakers and selected special session speakers, contains both expository and research papers by some of the best logicians in the world.

This book presents a unifying framework for using priority arguments to prove theorems in computability.

Papers examining aspects of Godel's work gathered from a symposium celebrating Goedel's centennial and papers from a 2004 ASL symposium.

Games, Scales, and Suslin Cardinals is the first of a series of four books presenting the seminal papers from the Caltech-UCLA 'Cabal Seminar' with extensive unpublished material, new papers on related topics, and discussion of research developments since the publication of the original volumes.

This book addresses a gap in the model-theoretic understanding of valued fields that had limited the interactions of model theory with geometry. It contains significant developments in both pure and applied model theory. Part I of the book is a study of stably dominated types. These form a subset of the type space of a theory that behaves in many ways like the space of types in a stable theory. This part begins with an introduction to the key ideas of stability theory for stably dominated types. Part II continues with an outline of some classical results in the model theory of valued fields and explores the application of stable domination to algebraically closed valued fields. The research presented here is made accessible to the general model theorist by the inclusion of the introductory sections of each part.

This book is an up-to-date introduction to simple theories and hyperimaginaries, with special attention to Lascar strong types and elimination of hyperimaginary problems. Assuming only knowledge of general model theory, the foundations of forking, stability and simplicity are presented in full detail. The treatment of the topics is as general as possible, working with stable formulas and types and assuming stability or simplicity of the theory only when necessary. The author offers an introduction to independence relations as well as a full account of canonical bases of types in stable and simple theories. In the last chapters the notions of internality and analyzability are discussed and used to provide a self-contained proof of elimination of hyperimaginaries in supersimple theories.