The concept of infinity is one of the most important, and at the same time, one of the most mysterious concepts of science. Already in antiquity many philosophers and mathematicians pondered over its contradictory nature. In mathematics, the contradictions connected with infinity intensified after the creation, at the end of the 19th century, of the theory of infinite sets and the subsequent discovery, soon after, of paradoxes in this theory. At the time, many scientists ignored the paradoxes and used set theory extensively in their work, while others subjected set-theoretic methods in mathematics to harsh criticism. The debate intensified when a group of French mathematicians, who wrote under the pseudonym of Nicolas Bourbaki, tried to erect the whole edifice of mathematics on the single notion of a set. Some mathematicians greeted this attempt enthusiastically while others regarded it as an unnecessary formalization, an attempt to tear mathematics away from life-giving practical applications that sustain it. These differences notwithstanding, Bourbaki has had a significant influence on the evolution of mathematics in the twentieth century. In this book we try to tell the reader how the idea of the infinite arose and developed in physics and in mathematics, how the theory of infinite sets was constructed, what paradoxes it has led to, what significant efforts have been made to eliminate the resulting contradictions, and what routes scientists are trying to find that would provide a way out of the many difficulties.

This is a collection of surveys and research papers on topics of interest in combinatorics, given at a conference in Matrahaza, Hungary. Originally published in journal form, it is here reissued as a book due to its special interest. It is dedicated to Paul Erdoes, who attended the conference and who is represented by two articles in the collection, including one, unfinished, which he was writing on the eve of his sudden death. Erdoes was one of the greatest mathematicians of his century and often the subject of anecdotes about his somewhat unusual lifestyle. A preface, written by friends and colleagues, gives a flavour of his life, including many such stories, and also describes the broad outline and importance of his work in combinatorics and other related fields. Here is a succinct introduction to important ideas in combinatorics for researchers and graduate students.

"Kind of crude, but it works, boy, it works " AZan NeweZZ to Herb Simon, Christmas 1955 In 1954 a computer program produced what appears to be the first computer generated mathematical proof: Written by M. Davis at the Institute of Advanced Studies, USA, it proved a number theoretic theorem in Presburger Arithmetic. Christmas 1955 heralded a computer program which generated the first proofs of some propositions of Principia Mathematica, developed by A. Newell, J. Shaw, and H. Simon at RAND Corporation, USA. In Sweden, H. Prawitz, D. Prawitz, and N. Voghera produced the first general program for the full first order predicate calculus to prove mathematical theorems; their computer proofs were obtained around 1957 and 1958, about the same time that H. Gelernter finished a computer program to prove simple high school geometry theorems. Since the field of computational logic (or automated theorem proving) is emerging from the ivory tower of academic research into real world applications, asserting also a definite place in many university curricula, we feel the time has corne to examine and evaluate its history. The article by Martin Davis in the first of this series of volumes traces the most influential ideas back to the 'prehistory' of early logical thought showing how these ideas influenced the underlying concepts of most early automatic theorem proving programs.

Coalgebraic logic is an important research topic in the areas of concurrency theory, semantics, transition systems and modal logics. It provides a general approach to modeling systems, allowing us to apply important results from coalgebras, universal algebra and category theory in novel ways. Stochastic systems provide important tools for systems modeling, and recent work shows that categorical reasoning may lead to new insights, previously not available in a purely probabilistic setting.

This book combines coalgebraic reasoning, stochastic systems and logics. It provides an insight into the principles of coalgebraic logic from a categorical point of view, and applies these systems to interpretations of stochastic coalgebraic logics, which include well-known modal logics and continuous time branching logics. The author introduces stochastic systems together with their probabilistic and categorical foundations and gives a comprehensive discussion of the Giry monad as the underlying categorical construction, presenting many new, hitherto unpublished results. He discusses modal logics, introduces their probabilistic interpretations, and then proceeds to an analysis of Kripke models for coalgebraic logics.

The book will be of interest to researchers in theoretical computer science, logic and category theory.

1. The ?rst edition of this book was published in 1977. The text has been well received and is still used, although it has been out of print for some time. In the intervening three decades, a lot of interesting things have happened to mathematical logic: (i) Model theory has shown that insights acquired in the study of formal languages could be used fruitfully in solving old problems of conventional mathematics. (ii) Mathematics has been and is moving with growing acceleration from the set-theoretic language of structures to the language and intuition of (higher) categories, leaving behind old concerns about in?nities: a new view of foundations is now emerging. (iii) Computer science, a no-nonsense child of the abstract computability theory, has been creatively dealing with old challenges and providing new ones, such as the P/NP problem. Planning additional chapters for this second edition, I have decided to focus onmodeltheory, the conspicuousabsenceofwhichinthe ?rsteditionwasnoted in several reviews, and the theory of computation, including its categorical and quantum aspects. The whole Part IV: Model Theory, is new. I am very grateful to Boris I. Zilber, who kindly agreed to write it. It may be read directly after Chapter II. The contents of the ?rst edition are basically reproduced here as Chapters I-VIII. Section IV.7, on the cardinality of the continuum, is completed by Section IV.7.3, discussing H. Woodin's discovery.

The theory of fuzzy sets has become known in Czechoslovakia in the early seventies. Since then, it was applied in various areas of science, engineering and economics where indeterminate concepts had to be handled. There has been a number of national semi- nars and conferences devoted to this topic. However, the International Symposium on Fuzzy Approach to Reasoning and Decision-Making, held in 1990, was the first really representative international meeting of this kind organized in Czechoslovakia. The symposium took place in the House of Scientists of the Czechoslovak Academy of Sciences in Bechyne from June 25 till 29, 1990. Its main organizer was Mining In- stitute of the Czechoslovak Academy of Sciences in Ostrava in cooperation and support of several other institutions and organizations. A crucial role in preparing of the Sym- posium was played by the working group for Fuzzy Sets and Systems which is active in the frame of the Society of Czechoslovak Mathematicians and Physicists. The organizing and program committee was headed by Dr. Vilem Novak from the Mining Institute in Ostrava. Its members (in alphabetical order) were Dr. Martin Cerny (Prague), Prof. Bla- hoslav Harman (Liptovsky Mikulas), Ema Hyklova (Prague), Prof. Zdenek Karpfsek (Brno), Jan Laub (Prague), Dr. Milan MareS - vice-chairman (Prague), Prof. Radko Mesiar (Bratislava), Dr. Jifi Nekola - vice-chairman (Prague), Daria Novakova (Os- trava), Dr. Jaroslav Ramfk (Ostrava), Prof. Dr. Beloslav Riecan (Bratislava), Dr. Jana TalaSova (Pi'erov) and Dr. Milos Vitek (Pardubice).

Combinatorial Algorithms on Words refers to the collection of manipulations of strings of symbols (words) - not necessarily from a finite alphabet - that exploit the combinatorial properties of the logical/physical input arrangement to achieve efficient computational performances. The model of computation may be any of the established serial paradigms (e.g. RAM's, Turing Machines), or one of the emerging parallel models (e.g. PRAM, WRAM, Systolic Arrays, CCC). This book focuses on some of the accomplishments of recent years in such disparate areas as pattern matching, data compression, free groups, coding theory, parallel and VLSI computation, and symbolic dynamics; these share a common flavor, yet ltave not been examined together in the past. In addition to being theoretically interest ing, these studies have had significant applications. It happens that these works have all too frequently been carried out in isolation, with contributions addressing similar issues scattered throughout a rather diverse body of literature. We felt that it would be advantageous to both current and future researchers to collect this work in a sin gle reference. It should be clear that the book's emphasis is on aspects of combinatorics and com plexity rather than logic, foundations, and decidability. In view of the large body of research and the degree of unity already achieved by studies in the theory of auto mata and formal languages, we have allocated very little space to them."

Michael Powell is one of the world's foremost figures in numerical analysis. This volume, first published in 1997, is derived from invited talks given at a meeting celebrating his 60th birthday and, reflecting Powell's own achievements, focuses on innovative work in optimisation and in approximation theory. The individual papers have been written by leading authorities in their subjects and are a mix of expository articles and surveys. They have all been reviewed and edited to form a coherent volume for this important discipline within mathematics, with highly relevant applications throughout science and engineering.

This book provides an integrated treatment of the theory of nonnegative matrices and some related classes of positive matrices, concentrating on connections with game theory, combinatorics, inequalities, optimization and mathematical economics. The authors have chosen the wide variety of applications, which include price fixing, scheduling, and the fair division problem, both for their elegant mathematical content and for their accessibility to students with minimal preparation. They present many new results in matrix theory for the first time in book form, while they present more standard topics in a novel fashion. The treatment is rigorous and almost all results are proved completely. These new results and applications will be of great interest to researchers in linear programming, statistics, and operations research. The minimal prerequisites also make the book accessible to first year graduate students.

Approximate reasoning is a key motivation in fuzzy sets and possibility theory. This volume provides a coherent view of this field, and its impact on database research and information retrieval. First, the semantic foundations of approximate reasoning are presented. Special emphasis is given to the representation of fuzzy rules and specialized types of approximate reasoning. Then syntactic aspects of approximate reasoning are surveyed and the algebraic underpinnings of fuzzy consequence relations are presented and explained. The second part of the book is devoted to inductive and neuro-fuzzy methods for learning fuzzy rules. It also contains new material on the application of possibility theory to data fusion. The last part of the book surveys the growing literature on fuzzy information systems. Each chapter contains extensive bibliographical material. Fuzzy Sets in Approximate Reasoning and Information Systems is a major source of information for research scholars and graduate students in computer science and artificial intelligence, interested in human information processing.

"Kind of Cl'Ude ~ but it UJorks~ boy~ it UJOrksl" Alan Ner. ueH to Herb Simon~ C1rl'istmas 1955 In 1954 a computer program produced what appears to be the first computer generated mathematical proof: Written by M. Davis at the Institute of Advanced Studies, USA, it proved a number theoretic theorem in Presburger Arithmetic. Christmas 1955 heralded a computer program which generated the first proofs of some propositions of Principia Mathematica, developed by A. Newell, J. Shaw, and H. Simon at RAND Corporation, USA. In Sweden, H. Prawitz, D. Prawitz, and N. Voghera produced the first general program for the full first order predicate calculus to prove mathematical theorems; their computer proofs were obtained around 1957 and 1958, about the same time that H. Gelernter finished a computer program to prove simple high school geometry theorems. Since the field of computational logic (or automated theorem proving) is emerging from the ivory tower of academic research into real world applications, asserting also a definite place in many university curricula, we feel the time has come to examine and evaluate its history. The article by Martin Davis in the first of this series of volumes traces the most influential ideas back to the 'prehistory' of early logical thought showing how these ideas influenced the underlying concepts of most early automatic theorem proving programs.

One high-level ability of the human brain is to understand what it has learned. This seems to be the crucial advantage in comparison to the brain activity of other primates. At present we are technologically almost ready to artificially reproduce human brain tissue, but we still do not fully understand the information processing and the related biological mechanisms underlying this ability. Thus an electronic clone of the human brain is still far from being realizable. At the same time, around twenty years after the revival of the connectionist paradigm, we are not yet satisfied with the typical subsymbolic attitude of devices like neural networks: we can make them learn to solve even difficult problems, but without a clear explanation of why a solution works. Indeed, to widely use these devices in a reliable and non elementary way we need formal and understandable expressions of the learnt functions. of being tested, manipulated and composed with These must be susceptible other similar expressions to build more structured functions as a solution of complex problems via the usual deductive methods of the Artificial Intelligence. Many effort have been steered in this directions in the last years, constructing artificial hybrid systems where a cooperation between the sub symbolic processing of the neural networks merges in various modes with symbolic algorithms. In parallel, neurobiology research keeps on supplying more and more detailed explanations of the low-level phenomena responsible for mental processes.

When solving real-life engineering problems, linguistic information is often encountered that is frequently hard to quantify using "classical" mathematical techniques. This linguistic information represents subjective knowledge. Through the assumptions made by the analyst when forming the mathematical model, the linguistic information is often ignored. On the other hand, a wide range of traffic and transportation engineering parameters are characterized by uncertainty, subjectivity, imprecision, and ambiguity. Human operators, dispatchers, drivers, and passengers use this subjective knowledge or linguistic information on a daily basis when making decisions. Decisions about route choice, mode of transportation, most suitable departure time, or dispatching trucks are made by drivers, passengers, or dispatchers. In each case the decision maker is a human. The environment in which a human expert (human controller) makes decisions is most often complex, making it difficult to formulate a suitable mathematical model. Thus, the development of fuzzy logic systems seems justified in such situations. In certain situations we accept linguistic information much more easily than numerical information. In the same vein, we are perfectly capable of accepting approximate numerical values and making decisions based on them. In a great number of cases we use approximate numerical values exclusively. It should be emphasized that the subjective estimates of different traffic parameters differs from dispatcher to dispatcher, driver to driver, and passenger to passenger.

Convexity of sets in linear spaces, and concavity and convexity of functions, lie at the root of beautiful theoretical results that are at the same time extremely useful in the analysis and solution of optimization problems, including problems of either single objective or multiple objectives. Not all of these results rely necessarily on convexity and concavity; some of the results can guarantee that each local optimum is also a global optimum, giving these methods broader application to a wider class of problems. Hence, the focus of the first part of the book is concerned with several types of generalized convex sets and generalized concave functions. In addition to their applicability to nonconvex optimization, these convex sets and generalized concave functions are used in the book's second part, where decision-making and optimization problems under uncertainty are investigated. Uncertainty in the problem data often cannot be avoided when dealing with practical problems. Errors occur in real-world data for a host of reasons. However, over the last thirty years, the fuzzy set approach has proved to be useful in these situations. It is this approach to optimization under uncertainty that is extensively used and studied in the second part of this book. Typically, the membership functions of fuzzy sets involved in such problems are neither concave nor convex. They are, however, often quasiconcave or concave in some generalized sense. This opens possibilities for application of results on generalized concavity to fuzzy optimization. Despite this obvious relation, applying the interface of these two areas has been limited to date. It is hoped that the combination of ideas and results from the field of generalized concavity on the one hand and fuzzy optimization on the other hand outlined and discussed in Generalized Concavity in Fuzzy Optimization and Decision Analysis will be of interest to both communities. Our aim is to broaden the classes of problems that the combination of these two areas can satisfactorily address and solve.

This monograph contains the results of our joint research over the last ten years on the logic of the fixed point operation. The intended au dience consists of graduate students and research scientists interested in mathematical treatments of semantics. We assume the reader has a good mathematical background, although we provide some prelimi nary facts in Chapter 1. Written both for graduate students and research scientists in theoret ical computer science and mathematics, the book provides a detailed investigation of the properties of the fixed point or iteration operation. Iteration plays a fundamental role in the theory of computation: for example, in the theory of automata, in formal language theory, in the study of formal power series, in the semantics of flowchart algorithms and programming languages, and in circular data type definitions. It is shown that in all structures that have been used as semantical models, the equational properties of the fixed point operation are cap tured by the axioms describing iteration theories. These structures include ordered algebras, partial functions, relations, finitary and in finitary regular languages, trees, synchronization trees, 2-categories, and others."

In the six years since the first edition of this book was published, the field of Structural Complexity has grown quite a bit. However, we are keeping this volume at the same basic level that it had in the first edition, and the only new result incorporated as an appendix is the closure under complementation of nondeterministic space classes, which in the previous edition was posed as an open problem. This result was already included in our Volume II, but we feel that due to the basic nature of the result, it belongs to this volume. There are of course other important results obtained during these last six years. However, as they belong to new areas opened in the field they are outside the scope of this fundamental volume. Other changes in this second edition are the update of some Bibliograph ical Remarks and references, correction of many mistakes and typos, and a renumbering of the definitions and results. Experience has shown us that this new numbering is a lot more friendly, and several readers have confirmed this opinion. For the sake of the reader of Volume II, where all references to Volume I follow the old numbering, we have included here a table indicating the new number corresponding to each of the old ones."

Substructural logics are by now one of the most prominent branches of the research field usually labelled as "nonclassical logics" - and perhaps of logic tout court. Over the last few decades a vast amount of research papers and even some books have been devoted to this subject. The aim of the present book is to give a comprehensive account of the "state of the art" of substructural logics, focusing both on their proof theory (especially on sequent calculi and their generalizations) and on their semantics (both algebraic and relational).
Readership: This textbook is designed for a wide readership: graduate students in either philosophy, mathematics, theoretical computer science or theoretical linguistics with no previous knowledge of the subject (except for a working knowledge of elementary logic) will be gradually introduced into the field starting from its basic foundations; specialists and researchers in the area will find an up-to-date survey of the most important current research topics and problems.

During the last three decades, interest has increased significantly in the representation and manipulation of imprecision and uncertainty. Perhaps the most important technique in this area concerns fuzzy logic or the logic of fuzziness initiated by L. A. Zadeh in 1965. Since then, fuzzy logic has been incorporated into many areas of fundamental science and into the applied sciences. More importantly, it has been successful in the areas of expert systems and fuzzy control. The main body of this book consists of so-called IF-THEN rules, on which experts express their knowledge with respect to a certain domain of expertise. Fuzzy IF-THEN Rules in Computational Intelligence: Theory and Applications brings together contributions from leading global specialists who work in the domain of representation and processing of IF-THEN rules. This work gives special attention to fuzzy IF-THEN rules as they are being applied in computational intelligence. Included are theoretical developments and applications related to IF-THEN problems of propositional calculus, fuzzy predicate calculus, implementations of the generalized Modus Ponens, approximate reasoning, data mining and data transformation, techniques for complexity reduction, fuzzy linguistic modeling, large-scale application of fuzzy control, intelligent robotic control, and numerous other systems and practical applications. This book is an essential resource for engineers, mathematicians, and computer scientists working in fuzzy sets, soft computing, and of course, computational intelligence.

The subject of the present book is sub differential calculus. The main source of this branch of functional analysis is the theory of extremal problems. For a start, we explicate the origin and statement of the principal problems of sub differential calculus. To this end, consider an abstract minimization problem formulated as follows: x E X, f(x) --+ inf. Here X is a vector space and f : X --+ iR is a numeric function taking possibly infinite values. In these circumstances, we are usually interested in the quantity inf f( x), the value of the problem, and in a solution or an optimum plan of the problem (i. e. , such an x that f(x) = inf f(X", if the latter exists. It is a rare occurrence to solve an arbitrary problem explicitly, i. e. to exhibit the value of the problem and one of its solutions. In this respect it becomes necessary to simplify the initial problem by reducing it to somewhat more manageable modifications formulated with the details of the structure of the objective function taken in due account. The conventional hypothesis presumed in attempts at theoretically approaching the reduction sought is as follows. Introducing an auxiliary function 1, one considers the next problem: x EX, f(x) -l(x) --+ inf. Furthermore, the new problem is assumed to be as complicated as the initial prob lem provided that 1 is a linear functional over X, i. e.

This IMA Volume in Mathematics and its Applications RANDOM SETS: THEORY AND APPLICATIONS is based on the proceedings of a very successful 1996 three-day Summer Program on "Application and Theory of Random Sets." We would like to thank the scientific organizers: John Goutsias (Johns Hopkins University), Ronald P.S. Mahler (Lockheed Martin), and Hung T. Nguyen (New Mexico State University) for their excellent work as organizers of the meeting and for editing the proceedings. We also take this opportunity to thank the Army Research Office (ARO), the Office ofNaval Research (0NR), and the Eagan, MinnesotaEngineering Center ofLockheed Martin Tactical Defense Systems, whose financial support made the summer program possible. Avner Friedman Robert Gulliver v PREFACE "Later generations will regard set theory as a disease from which one has recovered. " - Henri Poincare Random set theory was independently conceived by D.G. Kendall and G. Matheron in connection with stochastic geometry. It was however G.

This book has a rather strange history. It began in spring 1989, thirteen years after our Systems Science Department at SUNY-Binghamton was established, when I was asked by a group of students in our doctoral program to have a meeting with them. The spokesman of the group, Cliff Joslyn, opened our meeting by stating its purpose. I can closely paraphrase what he said: "We called this meeting to discuss with you, as Chairman of the Department, a fundamental problem with our systems science curriculum. In general, we consider it a good curriculum: we learn a lot of concepts, principles, and methodological tools, mathematical, computational, heu ristic, which are fundamental to understanding and dealing with systems. And, yet, we learn virtually nothing about systems science itself. What is systems science? What are its historical roots? What are its aims? Where does it stand and where is it likely to go? These are pressing questions to us. After all, aren't we supposed to carry the systems science flag after we graduate from this program? We feel that a broad introductory course to systems science is urgently needed in the curriculum. Do you agree with this assessment?" The answer was obvious and, yet, not easy to give: "I agree, of course, but I do not see how the situation could be alleviated in the foreseeable future.

1. Introduction . 1 2. Areas and Angles . . 6 3. Tessellations and Symmetry 14 4. The Postulate of Closest Approach 28 5. The Coexistence of Rotocenters 36 6. A Diophantine Equation and its Solutions 46 7. Enantiomorphy. . . . . . . . 57 8. Symmetry Elements in the Plane 77 9. Pentagonal Tessellations . 89 10. Hexagonal Tessellations 101 11. Dirichlet Domain 106 12. Points and Regions 116 13. A Look at Infinity . 122 14. An Irrational Number 128 15. The Notation of Calculus 137 16. Integrals and Logarithms 142 17. Growth Functions . . . 149 18. Sigmoids and the Seventh-year Trifurcation, a Metaphor 159 19. Dynamic Symmetry and Fibonacci Numbers 167 20. The Golden Triangle 179 21. Quasi Symmetry 193 Appendix I: Exercise in Glide Symmetry . 205 Appendix II: Construction of Logarithmic Spiral . 207 Bibliography . 210 Index . . . . . . . . . . . . . . . . . . . . 225 Concepts and Images is the result of twenty years of teaching at Harvard's Department of Visual and Environmental Studies in the Carpenter Center for the Visual Arts, a department devoted to turning out students articulate in images much as a language department teaches reading and expressing one self in words. It is a response to our students' requests for a "handout" and to l our colleagues' inquiries about the courses: Visual and Environmental Studies 175 (Introduction to Design Science), YES 176 (Synergetics, the Structure of Ordered Space), Studio Arts 125a (Design Science Workshop, Two-Dimension al), Studio Arts 125b (Design Science Workshop, Three-Dimensional),2 as well as my freshman seminars on Structure in Science and Art."

Fuzzy technology has emerged as one of the most exciting new concepts available. Fuzzy Logic and its Applications... covers a wide range of the theory and applications of fuzzy logic and related systems, including industrial applications of fuzzy technology, implementing human intelligence in machines and systems. There are four main themes: intelligent systems, engineering, mathematical foundations, and information sciences. Both academics and the technical community will learn how and why fuzzy logic is appreciated in the conceptual, design and manufacturing stages of intelligent systems, gaining an improved understanding of the basic science and the foundations of human reasoning.

Fundamentals of Fuzzy Sets covers the basic elements of fuzzy set theory. Its four-part organization provides easy referencing of recent as well as older results in the field. The first part discusses the historical emergence of fuzzy sets, and delves into fuzzy set connectives, and the representation and measurement of membership functions. The second part covers fuzzy relations, including orderings, similarity, and relational equations. The third part, devoted to uncertainty modelling, introduces possibility theory, contrasting and relating it with probabilities, and reviews information measures of specificity and fuzziness. The last part concerns fuzzy sets on the real line - computation with fuzzy intervals, metric topology of fuzzy numbers, and the calculus of fuzzy-valued functions. Each chapter is written by one or more recognized specialists and offers a tutorial introduction to the topics, together with an extensive bibliography.

This book appeared about ten years ago in Gennan. It started as notes for a course which I gave intermittently at the ETH over a number of years. Following repeated suggestions, this English translation was commissioned by Springer; they were most fortunate in finding translators whose mathemati cal stature, grasp of the language and unselfish dedication to the essentially thankless task of rendering the text comprehensible in a second language, both impresses and shames me. Therefore, my thanks go to Dr. Roberto Minio, now Darmstadt and Professor Charles Thomas, Cambridge. The task of preparing a La'JEX-version of the text was extremely daunting, owing to the complexity and diversity of the symbolisms inherent in the various parts of the book. Here, my warm thanks go to Barbara Aquilino of the Mathematics Department of the ETH, who spent tedious but exacting hours in front of her Olivetti. The present book is not primarily intended to teach logic and axiomat ics as such, nor is it a complete survey of what was once called "elementary mathematics from a higher standpoint." Rather, its goal is to awaken a certain critical attitude in the student and to help give this attitude some solid foun dation. Our mathematics students, having been drilled for years in high-school and college, and having studied the immense edifice of analysis, regrettably come away convinced that they understand the concepts of real numbers, Euclidean space, and algorithm."