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

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)

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.

The first complete English translation of a groundbreaking work. An ambitious account of the relation of mathematics to logic. Includes a foreword by Crispin Wright, translators' Introduction, and an appendix on Frege's logic by Roy T. Cook. The German philosopher and mathematician Gottlob Frege (1848-1925) was the father of analytic philosophy and to all intents and purposes the inventor of modern logic. Basic Laws of Arithmetic, originally published in German in two volumes (1893, 1903), is Freges magnum opus. It (...) was to be the pinnacle of Freges lifes work. It represents the final stage of his logicist project the idea that arithmetic and analysis are reducible to logic and contains his mature philosophy of mathematics and logic. The aim of Basic Laws of Arithmetic is to demonstrate the logical nature of mathematical theorems by providing gapless proofs in Frege's formal system using only basic laws of logic, logical inference, and explicit definitions. The work contains a philosophical foreword, an introduction to Frege's logic, a derivation of arithmetic from this logic, a critique of contemporary approaches to the real numbers, and the beginnings of a logicist treatment of real analysis. As is well-known, a letter received from Bertrand Russell shortly before the publication of the second volume made Frege realise that his basic law V, governing the identity of value-ranges, leads into inconsistency. Frege discusses a revision to basic law V written in response to Russells letter in an afterword to volume II. The continuing importance of Basic Laws of Arithmetic lies not only in its bearing on issues in the foundations of mathematics and logic but in its model of philosophical inquiry. Frege's ability to locate the essential questions, his integration of logical and philosophical analysis, and his rigorous approach to criticism and argument in general are vividly in evidence in this, his most ambitious work. Philip Ebert and Marcus Rossberg present the first full English translation of both volumes of Freges major work preserving the original formalism and pagination. The edition contains a foreword by Crispin Wright and an extensive appendix providing an introduction to Frege's formal system by Roy T. Cook. Readership: Scholars and advanced students in philosophy of logic, philosophy of mathematics, and early analytic philosophy. (shrink)

Dieser Band enthält die vier Arbeiten Freges: Begriffsschrift, eine der arithmetischen nachgebildeten Formelsprache, 1879; Anwendungen der Begriffsschrift, 1879; Über den Briefwechsel Leibnizens und Huggens mit Papin, 1881; Über den Zweck der Begriffsschrift, 1883; Über die wissenschaftliche Berechtigung einer Begriffsschrift, 1882. Frege's research work in the field of mathematical logic is of great importance for the present-day analytic philosophy. We actually owe to Frege a great amount of basical insight and exemplary research, which set up a new standard also in other (...) fields of knowledge. As the founder of mathematical logic he severely examindes the syllogisms on which arithmetic is built up. In doing so, Frege recognized that our colloquial language is inadequate to define logic structures. His notional language corresponded to the artaivicial logical language demandes by Leibniz. Frege's achievement in the field of logic were so important, that they radiated into the domain of philosophy and influenced the development of mathematical logic decisively. (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 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. 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)

Questo volume ripropone sei articoli fondamentali di Gottlob Frege nella versione italiana corredata dalla guida alla lettura di Carlo Lazzerini, che ha fatto di questa raccolta un’introduzione particolarmente felice alla logica moderna: un testo classico molto intenso viene proposto in modo tanto semplice da poter essere la porta di ingresso nella logica e nella filosofia della logica del Novecento anche per lettori che non ne hanno nessuna nozione e che ne iniziano da qui lo studio. Gli articoli di Frege, (...) composti in epoche diverse e caratterizzati da un’evoluzione verso una maggiore sistematicità, formano nel complesso un testo organico e seminale per lo sviluppo della logica matematica, della semantica e della filosofia del linguaggio del Novecento, come si constata anche ad una prima lettura, quando si tenga conto dell’influenza da un lato della geniale intuizione di Frege della distinzione nel significato dei nomi, dei concetti e delle proposizioni fra «senso» e «denotazione», e dall’altro della sua scoperta del valore funzionale del concetto. La lettura di Frege è un’occasione d’incontro tra cultura filosofica e scientifica. Se nell’antichità la logica (come, ad esempio, anche la fisica e la matematica) era intesa come disciplina filosofica, col volgere del tempo la logica è diventata sempre più una scienza autonoma, con un oggetto ben definito e finalità pratiche preminenti. Anzi, proprio la «logica matematica» promossa da Frege ha dato maggiore impulso a questo distacco, configurandosi sempre più come una tecnica precisa, un calcolo, come la forma elementare della matematica o come un ramo particolare della matematica stessa. Eppure, che gli scritti di Frege abbiano un valore filosofico, si avverte anche ad una lettura superficiale, nonostante l’impressione di tecnicismo che gli argomenti da lui preferiti possono dare. La ricerca matematica di Frege, il suo interesse per il problema dei «fondamenti» ed il suo inevitabile sconfinare di continuo nella logica, non sono mai promossi né da esigenze di applicazione, né di costruzione «all’in su» della scienza, ma sempre da un’esigenza di perfezionamento teoretico, verso il profondo. Dalla matematica ai fondamenti e dai fondamenti alla logica: se questo è l’itinerario della ricerca di Frege la sua qualità filosofica non è data dalla direzione dell’itinerario stesso, dal fatto che approda alla logica, ma dal modo della ricerca, che gli fa trascurare le possibilità costruttive della scienza (e da ciò viene la legittima diffidenza dei matematici suoi contemporanei), per tener dietro alle prospettive teoretiche che si aprono, una dopo l’altra, in direzioni del tutto imprevedibili. (shrink)

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, ...