We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not always (...) true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]. (shrink)

The often observed complexity gap between the expressiveness of a logical formalism and its exponentially harder expression complexity is proven for all logical formalisms which satisfy natural closure conditions. The expression complexity of the prefix classes of second-order logic can thus be located in the corresponding classes of the weak exponential hierarchies; further results about expression complexity in database theory, logic programming, nonmonotonic reasoning, first-order logic with Henkin quantifiers and default logic are concluded. The proof method illustrates the significance of (...) quantifier-free interpretations in descriptive complexity theory. (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)

We start with a simple proof of Leivant's normal form theorem for ∑11 formulas over finite successor structures. Then we use that normal form to prove the following:1. over all finite structures, every ∑21 formula is equivalent to a ∑21 formula whose first-order part is a Boolean combination of existential formulas, and2. over finite successor structures, the Kolaitis-Thakur hierarchy of minimization problems collapses completely and the Kolaitis-Thakur hierarchy of maximization problems collapses partially.The normal form theorem for ∑21 fails if ∑21 (...) is replaced with ∑11 or if infinite structures are allowed. (shrink)

It was conjectured by Halpern and Kapron (Annals of Pure and Applied Logic, vol. 69, 1994) that frame satisfiability of propositional modal formulas is incomparable in expressive power to both Σ 1 1 (Ackermann) and Σ 1 1 (Bernays-Schonfinkel). We prove this conjecture. Our results imply that Σ 1 1 (Ackermann) and Σ 1 1 (Bernays-Schonfinkel) are incomparable in expressive power, already on finite graphs. Moreover, we show that on ordered finite graphs, i.e., finite graphs with a successor, Σ 1 (...) 1 (Bernays-Schonfinkel) is strictly more expressive than Σ 1 1 (Ackermann). (shrink)

This chapter contains sections titled: The Dark Ages of Logic Kant and Whately Bernard Bolzano John Stuart Mill Boole, De Morgan, and Peirce Gottlob Frege The Austrian School Bertrand Russell.

George Berkeley (1685-1753) is the superstar of Irish Philosophy. He entered Trinity College, Dublin, in 1700 and became a fellow in 1707. In 1724 he resigned his Fellowship to become Dean of Derry, and in 1734 he was made Bishop of Cloyne. He settled in Oxford in 1752 and died the following year. The work of George Berkeley is marked by its diversity and range. His writings take in such topics as mathematics, psychology, politics, health, economics, deism and education, as (...) well as that with which he is most associated - philosophy. Whatever topic he dealt with, his grasp of the subject matter was always impressive and his criticisms of his contemporaries often acute. Among the most noteable of the British Empiricists, he took his starting point from Locke's new 'way of ideas', but he rejected abstract ideas and the possibility of real existence outside perception. It is for this doctrine that he is most known - that there is no such thing as matter, and that things are collections of ideas which can exist only in our minds and only for so long as they are perceived. This philosophy, summed up in his phrase 'to be is to be perceived', he termed 'immaterialism'. A.C. Fraser's collection includes a series of what were previously unpublished notes by Berkeley on all the main topics of his philosophy. This, the 1901 edition, was the first complete edition of his works. (shrink)

§ i. After deserting for a time the old Euclidean standards of rigour, mathematics is now returning to them, and even making efforts to go beyond them. ...

In arithmetic, if only because many of its methods and concepts originated in India, it has been the tradition to reason less strictly than in geometry, ...

Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens / von Dr. Gottlob Frege,...Date de l'edition originale : 1879Ce livre est la reproduction fidele d'une oeuvre publiee avant 1920 et fait partie d'une collection de livres reimprimes a la demande editee par Hachette Livre, dans le cadre d'un partenariat avec la Bibliotheque nationale de France, offrant l'opportunite d'acceder a des ouvrages anciens et souvent rares issus des fonds patrimoniaux de la BnF.Les oeuvres faisant partie de cette collection ont ete (...) numerisees par la BnF et sont presentes sur Gallica, sa bibliotheque numerique.En entreprenant de redonner vie a ces ouvrages au travers d'une collection de livres reimprimes a la demande, nous leur donnons la possibilite de rencontrer un public elargi et participons a la transmission de connaissances et de savoirs parfois difficilement accessibles.Nous avons cherche a concilier la reproduction fidele d'un livre ancien a partir de sa version numerisee avec le souci d'un confort de lecture optimal. Nous esperons que les ouvrages de cette nouvelle collection vous apporteront entiere satisfaction.Pour plus d'informations, rendez-vous sur www.hachettebnf.frhttp://gallica.bnf.fr/ark:/12148/bpt6k65658c. (shrink)

Die Grundlagen gehören zu den klassischen Texten der Sprachphilosophie, Logik und Mathematik. Frege stützt sein Programm einer Begründung von Arithmetik und Analysis auf reine Logik, indem er die natürlichen Zahlen als bestimmte Begriffsumfänge definiert. Die philosophische Fundierung des Fregeschen Ansatzes bilden erkenntnistheoretische und sprachphilosophische Analysen und Begriffserklärungen. Studienausgabe aufgrund der textkritisch herausgegebenen Jubiläumsausgabe (Centenarausgabe). Mit Einleitung, Anmerkungen, Literaturverzeichnis und Namenregister.

Die Grundlagen gehören zu den klassischen Texten der Sprachphilosophie, Logik und Mathematik. Frege stützt sein Programm einer Begründung von Arithmetik und Analysis auf reine Logik, indem er die natürlichen Zahlen als bestimmte Begriffsumfänge definiert. Die philosophische Fundierung des Fregeschen Ansatzes bilden erkenntnistheoretische und sprachphilosophische Analysen und Begriffserklärungen. Studienausgabe aufgrund der textkritisch herausgegebenen Jubiläumsausgabe (Centenarausgabe). Mit Einleitung, Anmerkungen, Literaturverzeichnis und Namenregister.

Equality1 gives rise to challenging questions which are not altogether easy to answer. Is it a relation? A relation between objects, or between names or signs of objects? In my Begriffsschrift I assumed the latter. The reasons which seem to favour this are the following: a = a and a = b are obviously statements of differing cognitive value; a = a holds a priori and, according to Kant, is to be labeled analytic, while statements of the form a = (...) b often contain very valuable extensions of our knowledge and cannot always be established a priori. The discovery that the rising sun is not new every morning, but always the same, was one of the most fertile astronomical discoveries. Even to-day the identification of a small planet or a comet is not always a matter of course. Now if we were to regard equality as a relation between that which the names ‘a’ and ‘b’ designate, it would seem that a = b could not differ from a = a (i.e. provided a = b is true). A relation would thereby be expressed of a thing to itself, and indeed one in which each thing stands to itself but to no other thing. What is intended to be said by a = b seems to be that the signs or names ‘a’ and ‘b’ designate the same thing, so that those signs themselves would be under discussion; a relation between them would be asserted. But this relation would hold between the names or signs only in so far as they named or designated something. It would be mediated by the connexion of each of the two signs with the same designated thing. But this is arbitrary. Nobody can be forbidden to use any arbitrarily producible event or object as a sign for something. In that case the sentence a = b would no longer refer to the subject matter, but only to its mode of designation; we would express no proper knowledge by its means. But in many cases this is just what we want to do. If the sign ‘a’ is distinguished from the sign ‘b’ only as object (here, by means of its shape), not as sign (i.e. not by the manner in which it designates something), the cognitive value of a = a becomes essentially equal to that of a = b, provided a = b is true.. (shrink)

This is the first single-volume edition and translation of Frege's philosophical writings to include his seminal papers as well as substantial selections from ...

This volume contains all of Frege's extant unpublished writings on philosophy and logic other than his correspondence, written at various stages of his career.

... as 'logicism') that the content expressed by true propositions of arithmetic and analysis is not something of an irreducibly mathematical character, ...