We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like $\exists ^{ \ge 3/4} y$ which says that "for at least 3/4 of all y". These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are: 1. We deal with the quantifier $\exists ^{ \ge r} y$ , where y is a tuple (...) of variables. 2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope. 3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities pR for each predicate symbol R. 4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs). 5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers. 6. We allow each pR , as well as each r in the probability quantifier $(\exists ^{ \ge r} y)$ , to depend on the size of the universe. (shrink)

Dov Gabbay is a prolific logician just by himself. But beyond that, he is quite good at making other people investigate the many further things he cares about. As a result, King's College London has become a powerful attractor in our field worldwide. Thus, it is a great pleasure to be an organizer for one of its flagship events: the Augustus de Morgan Workshop of 2005. Benedikt Loewe and I proposed the topic of 'interactive logic' for this occasion, with an (...) emphasis on social software – the logical analysis and design of social procedures – and on games, arguably the formal interactive setting par excellence. This choice reflects current research interests in our logic community at ILLC Amsterdam and beyond. In this broad area of interfaces between logic, computer science, and game theory, this paper is my own attempt at playing Dov. I am, perhaps not telling, but at least asking other people to find out for me what I myself cannot. (shrink)

Game-theoretic solution concepts describe sets of strategy profiles that are optimal for all players in some plausible sense. Such sets are often found by recursive algorithms like iterated removal of strictly dominated strategies in strategic games, or backward induction in extensive games. Standard logical analyses of solution sets use assumptions about players in fixed epistemic models for a given game, such as mutual knowledge of rationality. In this paper, we propose a different perspective, analyzing solution algorithms as processes of learning (...) which change game models. Thus, strategic equilibrium gets linked to fixed-points of operations of repeated announcement of suitable epistemic statements. This dynamic stance provides a new look at the current interface of games, logic, and computation. (shrink)

The prospects and limitations of defining truth in a finite model in the same language whose truth one is considering are thoroughly examined. It is shown that in contradistinction to Tarski's undefinability theorem for arithmetic, it is in a definite sense possible in this case to define truth in the very language whose truth is in question.

Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and (...) extensions by so-called counting quantifiers.Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time or polynomial space can be characterized as collections of all classes of finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth. (shrink)

In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NC R , PAR R , EXP R and some others more.

We introduce frame-equivalence games tailored for reasoning about the size, modal depth, number of occurrences of symbols and number of different propositional variables of modal formulae defining a given frame property. Using these games, we prove lower bounds on the above measures for a number of well-known modal axioms; what is more, for some of the axioms, we show that they are optimal among the formulae defining the respective class of frames.

We consider infinitary logic with only two variable symbols, both with and without counting quantifiers, i.e. L2 L∞ω2 and C2 L∞ω2mεω. The main result is that finite relational structures admit canonization with respect to L2 and C2: there are polynomial time com putable functors mapping finite relational structures to unique representatives of their equivalence class with respect to indistinguishability in either of these logics. In fact we exhibit in verses to the natural invariants that characterize structures up to L2- or (...) C2-equivalence, respectively. As a corollary we obtain recursive presentations of the classes of all boolean queries that are closed with respect to L2- or C2-equivalence. (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)

The previously introduced algorithm \sqema\ computes first-order frame equivalents for modal formulae and also proves their canonicity. Here we extend \sqema\ with an additional rule based on a recursive version of Ackermann's lemma, which enables the algorithm to compute local frame equivalents of modal formulae in the extension of first-order logic with monadic least fixed-points \mffo. This computation operates by transforming input formulae into locally frame equivalent ones in the pure fragment of the hybrid mu-calculus. In particular, we prove that (...) the recursive extension of \sqema\ succeeds on the class of `recursive formulae'. We also show that a certain version of this algorithm guarantees the canonicity of the formulae on which it succeeds. (shrink)

We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given $\Delta _0$ -formula $\varphi (x)$ ; the parameter is the size of $\varphi $. This parameterization focusses attention on instances where n is large compared to the size of $\varphi $. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf {AC}^0$. From this we derive that certain natural upper bounds on the complexity of our parameterized (...) problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $I\Delta _0$ proves the MRDP theorem in a certain weak sense. (shrink)

We prove that modal definability with respect to the class of all structures with two commuting equivalence relations is an undecidable problem. The construction used in the proof shows that the same is true for the subclass of all finite structures. For that reason we prove that the first-order theories of these classes are undecidable and reduce the latter problem to the former.

We study those relational structures S with the property that each partition of S contains a block isomorphic to S. We show that the Fraïsse limits of parametric classes K. have property ; over a binary language, every countable structure in K satisfying along with a condition on 1-extensions must be isomorphic to this limit.

We say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M' over the same vocabulary if Φ is true on M but false on M'. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M'. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M'. We prove that every n-element structure M is identifiable by a (...) formula with quantifier rank less than (1- 1/2k)n+k²-k+4 and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than (1-1/2k²+2)n+k quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than n-√ n+k²+k quantifiers suffice to identify M and, as long as we keep the number of universal quantifiers bounded by a constant, at total n-O(√ n) quantifiers are necessary. (shrink)

Let $\mathscr {C}$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś–Tarski Theorem from classical model theory implies that $\mathscr {C}$ is definable in first-order logic by a sentence $\varphi $ if and only if $\mathscr {C}$ has a finite set of forbidden induced finite subgraphs. This result provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of forbidden (...) induced finite subgraphs. Furthermore, by the Completeness Theorem, we can compute from $\varphi $ the corresponding forbidden induced subgraphs. This machinery fails on finite graphs as shown by our results: –There is a class $\mathscr {C}$ of finite graphs that is definable in first-order logic and closed under induced subgraphs but has no finite set of forbidden induced subgraphs.–Even if we only consider classes $\mathscr {C}$ of finite graphs that can be characterized by a finite set of forbidden induced subgraphs, such a characterization cannot be computed from a first-order sentence $\varphi $ that defines $\mathscr {C}$ and the size of the characterization cannot be bounded by $f(|\varphi |)$ for any computable function f.Besides their importance in graph theory, the above results also significantly strengthen similar known theorems for arbitrary structures. (shrink)

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both (...) classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees. (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)

Satisfaction systems and reductions between them are presented as an appropriate context for analyzing the satisfiability and the validity problems. The notion of reduction is generalized in order to cope with the meet-combination of logics. Reductions between satisfaction systems induce reductions between the respective satisfiability problems and (under mild conditions) also between their validity problems. Sufficient conditions are provided for relating satisfiability problems to validity problems. Reflection results for decidability in the presence of reductions are established. The validity problem in (...) the meet-combination is proved to be decidable whenever the validity problem for the components are decidable. Several examples are discussed, namely, involving modal and intuitionistic logics, as well as the meet-combination of modal logic and intuitionistic logic. (shrink)

We present a number of, somewhat unusual, ways of describing what Craig’s interpolation theorem achieves, and use them to identify some open problems and further directions.

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...) when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory △ possesses a polynomial space computable model which is exponential space decidable and thus △ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity. (shrink)

We show that the existential preservation theorem fails for two-variable first-order logic FO2. It is known that for all k ≥ 3, FOk does not have an existential preservation theorem, so this settles the last open case, answering a question of Andreka, van Benthem, and Németi. In contrast, we prove that the homomorphism preservation theorem holds for FO2.

Being able to state the principles which lie deepest in the foundations of mathematics by sentences in three variables is crucially important for a satisfactory equational rendering of set theories along the lines proposed by Alfred Tarski and Steven Givant in their monograph of 1987. The main achievement of this paper is the proof that the 'kernel' set theory whose postulates are extensionality. (E), and single-element adjunction and removal. (W) and (L), cannot be axiomatized by means of three-variable sentences. This (...) highlights a sharp edge to be crossed in order to attain an 'algebraization' of Set Theory. Indeed, one easily shows that the theory which results from the said kernel by addition of the null set axiom, (N), is in its entirety expressible in three variables. (shrink)

Let φ be a monadic second order sentence about a finite structure from a class K which is closed under disjoint unions and has components. Compton has conjectured that if the number of n element structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilities ν(φ) (μ(φ) respectively) for φ always exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number (...) of single component K-structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates. (shrink)

Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these (...) forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view. It gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature. (shrink)

Minimal predicates P satisfying a given first-order description φ(P) occur widely in mathematical logic and computer science. We give an explicit first-order syntax for special first-order ‘PIA conditions’ φ(P) which guarantees unique existence of such minimal predicates. Our main technical result is a preservation theorem showing PIA-conditions to be expressively complete for all those first-order formulas that are preserved under a natural model-theoretic operation of ‘predicate intersection’. Next, we show how iterated predicate minimization on PIA-conditions yields a language MIN(FO) equal (...) in expressive power to LFP(FO), first-order logic closed under smallest fixed-points for monotone operations. As a concrete illustration of these notions, we show how our sort of predicate minimization extends the usual frame correspondence theory of modal logic, leading to a proper hierarchy of modal axioms: first-order-definable, first-order fixed-point definable, and beyond. (shrink)

Interpretability logic is a modal logic that can be used to describe relative interpretability between extensions of a given first-order arithmetical theory. Verbrugge semantics is a generalization of the basic semantics for interpretability logic. Bisimulation is the basic equivalence between models for modal logic. The Van Benthem Correspondence Theorem establishes modal logic as the bisimulation invariant fragment of first-order logic. In this paper we show that a special type of bisimulations, the so-called w-bisimulations, enable an analogue of the Van Benthem (...) Theorem for interpretability logic w.r.t. Verbrugge semantics. (shrink)