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 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)

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)

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)

Feminist economics draws increasing attention from professional mainstream economists. In this paper, we discuss methodological issues, some theoretical developments – notably on the household – and issues of economic policy. We point to parallels between feminist economics and institutional economics, and argue that these relations might be strengthened to the benefit of both.

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)

Ethnicity and im/migrant classification systems and their constituent categories have a long history in the construction of public health knowledge on tuberculosis in the United Kingdom. This article critically examines the categories employed and the epidemiological discourses on TB, im/migrants, and ethnic minorities in health reporting between 1965 and 2015. We employ a Sociology of Knowledge Approach to Discourse Analysis to trace the continuities and changes in the categories used and in the discursive construction of im/migrants, ethnic minorities, and TB. (...) These continuities and disjunctures are analysed within their socio-historical context to demonstrate the historical contingency of epidemiological knowledge production. We outline two historical phases in knowledge construction. The first coincides with the period of decolonisation, which witnessed a change in discursive identity ascriptions from ‘immigrants’ to ‘ethnic groups’ in health reporting as the ‘other’. The second commenced after 1991, when the adoption of the census ethnicity categories as a standard in the collection of population statistics entrenched ethnicity categories in health reporting. We argue the health reporting discourse reveals that the ‘new’ public health exhibits continuities with the ‘old’ by targeting the immigrant ‘other’ through biosecuritisation practices. We contend that these categories originated within a postcolonial paradigm and that increasing immigration and new forms of mobility are creating the preconditions for new discourses on identity construction that have implications for the current collaborative TB strategy. (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)

In lieu of an abstract, here is a brief excerpt of the content:Capitalism in “Wealthy Hellas”? PETER W. ROSE Josiah ober has taken on the very ambitious task of analyzing a vast swath of ancient Greek history— precisely the periods—as his opening quotation from Byron (1) implies—most admired by those who have devoted any time to the study of Greek antiquity: Fair Greece! sad relic of departed worth! Immortal, though no more! Though fallen, great!1 At the same time, again as (...) suggested by the repetition of Byron’s lines (206, also mentioned on 293), Ober’s book falls within the large category of celebratory works about ancient Greece—like Werner Jaeger’s once popular three volumes of Paideia or, at the outset of the twentieth century, Alfred Zimmern ’s The Greek Commonwealth.2 It does not, on the other hand, fit in with a plethora of relatively recent, relatively short (as opposed to George Grote’s twelve volumes) histories of Greece aimed at the potentially lucrative textbook market for general more comprehensive overviews of Greek civilization.3 As such, the basis on which Ober celebrates ancient Greece merits close scrutiny. history and the overriding thesis ober’s conception of “history” here is heavily weighted towards the theoretical elaboration and justification of an Josiah Ober, The Rise and Fall of Classical Greece (Princeton University Press 2015), hardback, 415 pages. A truncated, arbitrarily reorganized version of this review appeared in New Left Review 103 (2017) 139–49. Thanks to Daniel Tompkins for full comments on an earlier version, and to Peter Green and Stephen Hodkinson for clarifications on specific points. arion 26.3 winter 2019 overriding thesis. Five initial chapters of a total of eleven are devoted to that task before five chronologically focused chapters, which offer a cursory romp through Greek history from ca. 1000 BCE to 334 BCE and some brief suggestions about the period down to the decisive takeover of Greece by Rome, usually dated to 31 BCE. The volume is capped by a final summary and overview chapter. Ober is admirably forthright about his agenda. Immediately in his preface he declares, “in states where citizens keep rulers in check, public authority protects individual rights and the rule of law pertains most of the time. These political conditions promote economic growth. The conjunction of democratic politics and a strong economy is, in practice, available only to affluent citizens of highly developed countries.... Democracy and growth define the normal, although not yet the usual, conditions of modernity” (xiii, my emphasis).4 This somewhat utopian conception of the present-day interface of democratic institutions and economic growth—posited as an unquestioned desideratum in sublime disregard of “ecology” in the literal sense5—underlies Ober’s whole project. While acknowledging the obvious negatives of ancient slavery,6 “denial of rights to women, and glorified war,” he argues “if we are interested in the conjunction of political and economic exceptionalism, we must start somewhere, and classical Greece was the society in which the wealth-and-democracy package first emerged in a form that can be studied in depth” (xv). Athenian democracy has been at the center of Ober’s impressive scholarly career at least since the publication of his study of fourth-century BCE Athenian rhetoric, Mass and Elite in Democratic Athens (Princeton 1989). “Athens” or “democracy” have featured in the titles of all his subsequent book publications7—not to mention the extraordinary output of more specialized essays in multiple venues. One overriding question about his latest book is whether the unique phenomenon of Athenian democracy is being unduly generalized to “Classical Greece.” 142 capitalism in “wealthy hellas”? The special focus of his interest here in ancient Greece, the “conjunction of political and economic exceptionalism,” is further clarified in his opening chapter which begins with the quotation from Byron cited above: “Byron’s vision of greatness was inspired by ancient Greek cultural and intellectual achievement: art and architecture, literature, visual and performance art, scientific and moral thought.... Hellas was great because of a cultural accomplishment that was supported by sustained economic growth. That growth was made possible by a distinctive approach to politics” (1–2). Greek cultural achievements, however, are bracketed (and in practical terms dismissed)8 in favor of the “wealth-anddemocracy... (shrink)

In proportion to their numbers the Semitic peoples have exercised a greater influence on the course of human history as a whole than any other of the large races of mankind. As far as our records carry us, it appears that the early spirit of exploration and adventure, as distinct from racial migration, had its origin with them. Even in Homeric times, the Phoenician trader or pirate was a familiar feature of the Mediterranean world. Greece, commonly regarded by us as (...) the home of true culture, admitted that she owed to Phoenicia her first introduction to the art of writing. Semitic establishments were spread over the whole of the ancient world, and the only state that ever seriously contested with Rome the sovereignty of the world was Carthage. Though not famed more for military prowess than other races, the Semitic branch of mankind in the seventh century of our era swept over northern Africa and western Asia, overflowing at two points into Europe itself. (shrink)

This work has been selected by scholars as being culturally important, and is part of the knowledge base of civilization as we know it. This work was reproduced from the original artifact, and remains as true to the original work as possible. Therefore, you will see the original copyright references, library stamps (as most of these works have been housed in our most important libraries around the world), and other notations in the work. This work is in the public domain (...) in the United States of America, and possibly other nations. Within the United States, you may freely copy and distribute this work, as no entity (individual or corporate) has a copyright on the body of the work. As a reproduction of a historical artifact, this work may contain missing or blurred pages, poor pictures, errant marks, etc. Scholars believe, and we concur, that this work is important enough to be preserved, reproduced, and made generally available to the public. We appreciate your support of the preservation process, and thank you for being an important part of keeping this knowledge alive and relevant. (shrink)