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)

The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity type t there is a generalized quantifier of type t which is not definable in the extension of first order logic by all generalized quantifiers of type smaller than t. This was proved for unary similarity types by Per Lindström [17] with (...) a counting argument. We extend his method to arbitrary similarity types. (shrink)

We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type .We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.

The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity typetthere is a generalized quantifier of typetwhich is not definable in the extension of first order logic by all generalized quantifiers of type smaller thant. This was proved for unary similarity types by Per Lindström [17] with a counting argument. We extend (...) his method to arbitrary similarity types. (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)

Many known tools for proving expressibility bounds for first-order logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of (...) the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree. (shrink)

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and the latter is (...) the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

We prove that if ℵα is uncountable and regular, then the Beth-closure of Lωω(Qα) is not a sublogic of L∞ω(Qn), where Qn is the class of all n-ary generalized quantifiers. In particular, B(Lωω(Qα)) is not a sublogic of any finitely generated logic; i.e., there does not exist a finite set Q of Lindstrom quantifiers such that B(Lωω(Qα)) ≤ Lωω(Q).

We prove that if $\aleph_\alpha$ is uncountable and regular, then the Beth-closure of $\mathscr{L}_{\omega\omega}(Q_\alpha)$ is not a sublogic of $\mathscr{L}_{\infty\omega}(\mathbf{Q}_n)$, where $\mathbf{Q}_n$ is the class of all $n$-ary generalized quantifiers. In particular, $B(\mathscr{L}_{\omega\omega}(Q_\alpha))$ is not a sublogic of any finitely generated logic; i.e., there does not exist a finite set $\mathbf{Q}$ of Lindstrom quantifiers such that $B(\mathscr{L}_{\omega\omega}(Q_\alpha)) \leq \mathscr{L}_{\omega\omega}(\mathbf{Q})$.

We give a sufficient condition for the inexpressibility of the k-th extended vectorization of a generalized quantifier $\sf Q$ in ${\rm FO}({\vec Q}_k)$ , the extension of first-order logic by all k-ary quantifiers. The condition is based on a model construction which, given two ${\rm FO}({\vec Q}_1)$ -equivalent models with certain additional structure, yields a pair of ${\rm FO}({\vec Q}_k)$ -equivalent models. We also consider some applications of this condition to quantifiers that correspond to graph properties, such as connectivity and (...) planarity. (shrink)

We analyze the expressive resources of \ logic that do not stem from Henkin quantification. When one restricts attention to regular \ sentences, this amounts to the study of the fragment of \ logic which is individuated by the game-theoretical property of action recall. We prove that the fragment of prenex AR sentences can express all existential second-order properties. We then show that the same can be achieved in the non-prenex fragment of AR, by using “signalling by disjunction” instead of (...) Henkin or signalling patterns. We also study irregular IF logic and analyze its correspondence to regular IF logic. By using new methods, we prove that the game-theoretical property of knowledge memory is a first-order syntactical constraint also for irregular sentences, and we identify another new first-order fragment. Finally we discover that irregular prefixes behave quite differently in finite and infinite models. In particular, we show that, over infinite structures, every irregular prefix is equivalent to a regular one; and we present an irregular prefix which is second order on finite models but collapses to a first-order prefix on infinite models. (shrink)

We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACENP and PTIMENP. For these classes, characterisations are known in terms of NP computable Lindström quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIMENP can be characterised in terms of Lindström quantifers , though it remains (...) open whether this can be done for LOGSPACENP. (shrink)

In this paper we prove that thek-ary fragment of transitive closure logic is not contained in the extension of the (k−1)-ary fragment of partial fixed point logic by all (2k−1)-ary generalized quantifiers. As a consequence, the arity hierarchies of all the familiar forms of fixed point logic are strict simultaneously with respect to the arity of the induction predicates and the arity of generalized quantifiers.Although it is known that our theorem cannot be extended to the sublogic deterministic transitive closure logic, (...) we show that an extension is possible when we close this logic under congruence. (shrink)

We provide a sound and complete proof system for an extension of Kleene’s ternary logic to predicates. The concept of theory is extended with, for each function symbol, a formula that specifies when the function is defined. The notion of “is defined” is extended to terms and formulas via a straightforward recursive algorithm. The “is defined” formulas are constructed so that they themselves are always defined. The completeness proof relies on the Henkin construction. For each formula, precisely one of the (...) formula, its negation, and the negation of its “is defined” formula is true on the constructed model. Many other ternary logics in the literature can be reduced to ours. Partial functions are ubiquitous in computer science and even in (in)equation solving at schools. Our work was motivated by an attempt to precisely explain, in terms of logic, typical informal methods of reasoning in such applications. (shrink)

This chapter explores how to understand the contributions of experience, especially with respect to the role of cognitive science, in developing and assessing metaphysical theories of reality. Further, it develops a methodological basis for the idea that, independently of work in experimental philosophy focused on explications of concepts, contemporary metaphysical theories with a role for experiential evidence can be fruitfully connected to empirical work in psychology, especially cognitive science. While there are different ways to flesh out the connection between cognitive (...) science and metaphysics, one way to understand the methodological issue concerns the evaluation of Moorean facts about the manifest. The chapter deals with Moorean facts about experience, in particular, with features of the manifest image that are drawn from ordinary experience. It also explores how temporal experience relates to the nature of time. (shrink)

How should we make choices when we know so little about our futures? L. A. Paul argues that we must view life decisions as choices to make discoveries about the nature of experience. Her account of transformative experience holds that part of the value of living authentically is to experience our lives and preferences in whatever ways they evolve.

In lieu of an abstract, here is a brief excerpt of the content:Reviewed by:WisCon 46Laurie Fuller, Jenna N. Hanchey, and E. OrnelasExistence as Resistance, WisCon 46, May 26–29, 2023, Madison, Wisconsin, United StatesIn a world that seems structured to kill most of its occupants, there is a utopian impulse in the act of existence itself. WisCon 46 represented a prefigurative utopian impulse through centering continued marginalized existence as resistance.1 Leah Lakshmi Piepzna-Samarasinha calls “prefigurative politics” the “fancy term for the idea (...) of imagining and building the world we want to see now,” particularly in terms of access needs.2 The structure as well as the content of the convention itself created a space in which to set the groundwork for utopia: the ways that we live and act to resist structures of oppression in order to prefigure a better world.Since WisCon’s founding in 1977, its intended audience has been fans, authors, and academics interested in the intersection between feminism and “science fiction, fantasy, and speculative literature of all sorts.”3 While neither feminism nor speculative fiction could be solely defined as utopian, both do explore utopian impulses that inspire change for the better. Therein lies the hope of Alessa Johns’s proposal that “the utopian imagination has been crucial for feminists.”4 Lisa Yaszek agrees: “for nearly 200 years writers have used speculative fiction consciously and collectively to dramatize the political issues most central to women living in a technocultural world and to create a sense of wonder about the interrelated possibilities of social and scientific change.”5 Envisioning a liberatory world is a feminist imperative, and speculative fiction offers a unique venue to do so. This imperative informed WisCon this year, as participants collectively worked to imagine and enact a better future for marginalized folks, in and beyond the space of the conference. [End Page 618]Enabling Existence through Con StructuresWisCon is unique in attuning its organizational structure to the creation of liberatory futures in the here and now. WisCon is strongly attentive to disability access of all kinds, COVID safety, antiracist/anti-oppression principles, and safety and anti-abuse support for all these areas. In the contemporary US context—where COVID-19 remains a major barrier to disabled people wishing to participate in conventions, where racist violence continues to threaten BIPOC (Black, Indigenous, and People of Color) life, where queer and trans folks are under exacerbated legal attacks—creating a convention space that protects and enables marginalized participation becomes a means of prefiguring utopian potential through embodied praxis. As mask, capacity, and vaccination mandates disappear (despite these ongoing pandemic times), and as bigotry of all forms continues relatively unabated, WisCon 46 remains steadfast in its commitment to safety. In short, the conference itself aims to become a utopian space.WisCon organizers are also keenly aware of the challenges that many different bodyminds might encounter in large group settings.6 Trained monitors oversee in-person and online programming in an effort to discourage harmful words and actions as well as ensure the fullest participation for those most impacted. Hence, disability justice lies at the center of the Con’s policies and practices. The event is made as accessible as possible through careful attention to venue selection, including the availability of gender-neutral bathrooms, scent-free spaces, and quiet rooms, as well as the use of color communication badges.This year’s event followed strict masking and testing protocols: individually packaged rapid COVID-19 tests were available without cost at registration, as were KN95 masks. The Con kept an anonymized record of self-reported positive COVID-19 tests, in case of possible exposure. This mutual responsibility reflects the kind of utopianism inherent to disability politics; that is, disability “allows for reformulation of in/dependence and community,” a way of rethinking how we share space and produce knowledge together.7The conference’s decidedly feminist approach “to creating a space for feminism and its consideration within the science fiction community” is applied at every level. The Con’s general organization and procedures are structured as nonhierarchically as possible. There is a board of directors as well as co-chairs, but these are rotating positions. This “commitment to feminism” is [End Page 619] reflected... (shrink)

I argue for a property mereology and for mereological bundle theory. I then apply this theory to the one over many problem (universals) and puzzles concerning persistence and material constitution.

The first ever interdisciplinary handbook in the field, this vital resource offers wide-ranging analysis of health research regulation. The chapters confront gaps between documented law and research in practice, and draw on legal, ethical and social theories about what counts as robust research regulation to make recommendations for future directions. The handbook provides an account and analysis of current regulatory tools - such as consent to participation in research and the anonymisation of data to protection participants' privacy - as well (...) as commentary on the roles of the actors and stakeholders who are involved in human health research and its regulation. Drawing on a range of international examples of research using patient data, tissue and other human materials, the collective contribution of the volume is to explore current challenges in delivering good medical research for the public good and to provide insights on how to design better regulatory approaches. This title is also available as Open Access on Cambridge Core. (shrink)

This book develops a grammatical method for our underlying presuppositions which can help us unravel the problem of evil. The problem essentially rests on a dualism between fact and meaning. 'Evil and Intelligibility' provides an examination of the grammar of being and of the intelligibility of the world, culminating in a philosophical grammar in which God, meaning, and evil can coexist.

This essay engages the work of Italian feminist philosopher Adriana Cavarero and her concept of the narratable self. Her relational humanism, rooted in our exposure to others, offers an ontology of uniqueness whose critique of abstraction, masculinism, and identity politics still resonates today where the meaning of a unique “you” is negotiated in embodied exchanges that may offer care or wounds. Cavarero develops an altruistic ethics that cultivates this humanism. I argue that her work should be extended to better capture (...) the political purchase of the narratable self that interacts dynamically and often ambiguously with the “we” of collective politics. Putting her work into conversation with the nineteenth‐century abolitionist and women's rights advocate Sojourner Truth, I suggest that Cavarero's work illuminates Truth as a philosopher of the narratable self. Moreover, Truth's work extends Cavarero's concerns with exposure that may do violence or offer care by making explicit the challenges of narration in the context of inequality, especially in terms of race and class. Exposure as an ontological and phenomenological condition then needs to take account of a broader publicity of textual, individual, and collective exposure to others to develop the critical, ethical, and political purchase it offers. (shrink)

This article represents an attempt to organize, critique, and extend research findings on gender differences in business ethics. The focus is on two dependent variables—ethical judgment and behavioral intent. Differences in findings between student and professional groups are noted and theoretical implications are discussed. The new research provided for this article contains two benchmark studies undertaken with identical stimuli and identical measures. These studies were followed by two additional studies, using the same measures but different stimuli, as a partial replication (...) and extension of the first two. Findings suggest that little difference exists between the genders on behavioral intent for professional groups and only minimal differences for the ethical judgment measures. Student results, however, produced more substantial differences for behavioral intention. (shrink)

Figuring prominently in their decisions regarding which theories to pursue are scientists' appeals to the promise or lack of promise of those theories. Yet philosophy of science has had little to say about how one is to assess theory promise. This essay identifies several indices that might be consulted to determine whether or not a theory is promising and worthy of pursuit. Various historical examples of appeals to such indices are introduced.