First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite (...) model. Moreover, Mortimer showed that every satisfiable FO 2 -sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO 2 -sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO 2 is NEXPTIME-complete. (shrink)

We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L ′ are two logics and μ is an asymptotic measure on finite structures, then $\scr{L}\equiv _{\text{a.e.}}\scr{L}^{\prime}(\mu)$ means that there is a class C of finite structures with μ (C)=1 (...) and such that L and L ′ define the same queries on C. We carry out a systematic investigation of $\equiv _{\text{a.e.}}$ with respect to the uniform measure and analyze the $\equiv _{\text{a.e.}}$ -equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework. (shrink)

We carry out a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite model theory, such as least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show that the upper and lower bounds (...) established here cannot be made substantially tighter, unless outstanding conjectures in complexity theory are resolved at the same time. (shrink)

This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, and infinitary logics (...) to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful way to analyze the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the application of logic to computer science. (shrink)

In 1960, E. P. Wigner, a joint winner of the 1963 Nobel Prize for Physics, published a paper titled On the Unreasonable Effectiveness of Mathematics in the Natural Sciences [61]. This paper can be construed as an examination and affirmation of Galileo's tenet that “The book of nature is written in the language of mathematics”. To this effect, Wigner presented a large number of examples that demonstrate the effectiveness of mathematics in accurately describing physical phenomena. Wigner viewed these examples as (...) illustrations of what he called the empirical law of epistemology, which asserts that the mathematical formulation of the laws of nature is both appropriate and accurate, and that mathematics is actually the correct language for formulating the laws of nature. At the same time, Wigner pointed out that the reasons for the success of mathematics in the natural sciences are not completely understood; in fact, he went as far as asserting that “… the enormous usefulness of mathematics in the natural sciences is something bordering on the mysterious and there is no rational explanation for it.”. (shrink)

Caring for a child in a pediatric intensive care unit is emotionally and physically challenging and often leads to conflict. Skilled mediators may not always be available to aid in conflict resolution. Careproviders at all levels of training are responsible for managing difficult conversations with families and can often prevent escalation of conflict. Bioethics mediators have acknowledged the important contribution of mediation training in improving clinicians’ skills in conflict management. Familiarizing careproviders with basic mediation techniques is an important step towards (...) preventing escalation of conflict. While training in effective communication is crucial, a sense of fairness and justice that may only come with the introduction of a skilled, neutral third party is equally important. For intense conflict, we advocate for early recognition, comfort, and preparedness through training of clinicians in de-escalation and optimal communication, along with the use of more formally trained third-party mediators, as required. (shrink)

Taking as its starting point what is sometimes called 'the prison house of language' - the widespread feeling that language falls terribly short when it comes to articulating the rich and disparate contents of the human mental tapestry - this book sets out a radically new view of the interplay between language, literature and mind. Shifting the focus from the literary text itself to literature as a case of human agency, it reconsiders a wide range of interdisciplinary issues including the (...) move from world to mind, the existence or otherwise of a property of literariness or essence of art, the nature of literature as a unique output of human cognition and the possible distinctiveness of the mind that creates it. In constant dialogue with philosophy, linguistics and the cognitive sciences, this book offers an invaluable new treatment of literature and literary language, and sketches novel directions for literary study in the twenty-first century. (shrink)

Hume's Reception in Early America: Expanded Edition brings together the original American responses to one of Britain's greatest men of letters, David Hume. Now available as a single volume paperback, this new edition includes updated further readings suggestions and dozens of additional primary sources gathered together in a completely new concluding section. From complete pamphlets and booklets, to poems, reviews, and letters, to extracts from newspapers, religious magazines and literary and political journals, this book's contents come from a wide variety (...) of sources published in colonial America and the early United States between 1758 and 1850. As well as classics by Thomas Jefferson, John Adams and Alexander Hamilton, it contains scores of unknown and hard-to-locate items, many of which have not been reprinted since their original publication. These responses are divided into four parts covering Hume's Essays; his Philosophical Writings; his History of England; and his Character and Death. Each of those parts has a separate introductory essay, and every selection is introduced by a short headnote that sets the piece in its historical context and provides bibliographical references. Packed with new insights into Hume and American thought and culture, Hume's Reception in Early America reveals the relevance and impact of Hume on American political, philosophical, historical, religious, and aesthetic debates. (shrink)

This is a welcome reprint of a book that continues to grow in importance.

Editor James Fetzer presents an analytical and historical introduction and a comprehensive bibliography together with selections of many of Carl G. Hempel's most important studies to give students and scholars an ideal opportunity to appreciate the enduring contributions of one of the most influential philosophers of science of the 20th century.

This entirely new work guides the reader through the most basic systems of modal propositional logic up to systems of modal predicate with identity, dealing with both technical developments and discussing philosophical applications.

Includes bibliographical references and index.

Biological evolution is a complex blend of ever changing structural stability, variability and emergence of new phe- notypes, niches, ecosystems. We wish to argue that the evo- lution of life marks the end of a physics world view of law entailed dynamics. Our considerations depend upon dis- cussing the variability of the very ”contexts of life”: the in- teractions between organisms, biological niches and ecosys- tems. These are ever changing, intrinsically indeterminate and even unprestatable: we do not know ahead of (...) time the ”niches” which constitute the boundary conditions on selec- tion. More generally, by the mathematical unprestatability of the ”phase space”, no laws of mo- tion can be formulated for evolution. We call this radical emergence, from life to life. The purpose of this paper is the integration of variation and diversity in a sound concep- tual frame and situate unpredictability at a novel theoretical level, that of the very phase space. Our argument will be carried on in close comparisons with physics and the mathematical constructions of phase spaces in that discipline. The role of symmetries as invariant preserving transformations will allow us to under- stand the nature of physical phase spaces and to stress the differences required for a sound biological theoretizing. In this frame, we discuss the novel notion of ”enablement”. Life lives in a web of enablement and radical emergence. This will restrict causal analyses to differential cases. Mutations or other causal differ- ences will allow us to stress that ”non conservation princi- ples” are at the core of evolution, in contrast to physical dynamics, largely based on conservation principles as sym- metries. Critical transitions, the main locus of symmetry changes in physics, will be discussed, and lead to ”extended criticality” as a conceptual frame for a better understanding of the living state of matter. (shrink)