In [2] A. Wroski proved that there is a strongly finite consequence C which is not finitely based i.e. for every consequence C + determined by a finite set of standard rules C C +. In this paper it will be proved that for every strongly finite consequence C there is a consequence C + determined by a finite set of structural rules such that C(Ø)=C +(Ø) and = (where , are consequences obtained by adding to (...) the rules of C, C + respectively the rule of substitution). Moreover it will be shown that under certain assumptions C=C +. (shrink)

We investigate properties of propositional modal logic over the classof finite structures. In particular, we show that certain knownpreservation theorems remain true over this class. We prove that aclass of finite models is defined by a first-order sentence and closedunder bisimulations if and only if it is definable by a modal formula.We also prove that a class of finite models defined by a modal formulais closed under extensions if and only if it is defined by a (...) -modal formula. (shrink)

In this paper we consider classes of finite structures where we have good control over the sizes of the definable sets. The motivating example is the class of finite fields: it was shown in [1] that for any formulain the language of rings, there are finitely many pairs (d,μ) ∈ω×Q>0so that in any finite fieldFand for any ā ∈Fmthe size |ø(Fn,ā)| is “approximately”μ|F|d. Essentially this is a generalisation of the classical Lang-Weil estimates from the category of (...) varieties to that of the first-order-definable sets. (shrink)

This chapter contains sections titled: Validity in the Finite Model Theory in the Finite? Definability and Complexity First‐Order Definability Second‐Order Definability Inductive Definability Infinitary Logics Random Graphs and 0–1 Laws.

We study the preservation of certain properties under products of classes of finite structures. In particular, we examine indivisibility, definable self-similarity, the amalgamation property, and the disjoint n-amalgamation property. We explore how each of these properties interacts with the lexicographic product, full product, and free superposition of classes of structures. Additionally, we consider the classes of theories which admit configurations indexed by these products. In particular, we show that, under mild assumptions, the products considered in this article (...) do not yield new classes of theories. (shrink)

Arithmetical definability has been extensively studied over the natural numbers. In this paper, we take up the study of arithmetical definability over finite structures, motivated by the correspondence between uniform AC0 and FO. We prove finite analogs of three classic results in arithmetical definability, namely that < and TIMES can first-order define PLUS, that < and DIVIDES can first-order define TIMES, and that < and COPRIME can first-order define TIMES. The first result sharpens the equivalence FO =FO (...) to FO = FO, answering a question raised by Barrington et al. about the Crane Beach Conjecture. Together with previous results on the Crane Beach Conjecture, our results imply that FO is strictly less expressive than FO = FO = FO. In more colorful language, one could say that, for parallel computation, multiplication is harder than addition. (shrink)

We discuss the possibility of applying the compactness theorem to the study of finite structures. Given a class of finite structures, it is important to determine whether it can be expressed by a particular category of sentences. We are interested in this type of problem, and use nonstandard method for showing the non‐expressibility of certain classes of finite graphs by an existential monadic second order sentence.

We introduce the concept of o-asymptotic classes of finite structures, melding ideas coming from 1-dimensional asymptotic classes and o-minimality. Along with several examples and non-examples of these classes, we present some classification theory results of their infinite ultraproducts: Every infinite ultraproduct of structures in an o-asymptotic class is superrosy of U^þ-rank 1, and NTP2 (in fact, inp-minimal).

We present a simple and completely model-theoretical proof of a strengthening of a theorem of Ajtai: The independence of the pigeonhole principle from IΔ0. With regard to strength, the theorem proved here corresponds to the complexity/proof-theoretical results of [10] and [14], but a different combinatorics is used. Techniques inspired by Razborov [11] replace those derived from Håstad [8]. This leads to a much shorter and very direct construction.

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)

We provide a canonical construction of conformal covers for finite hypergraphs and present two immediate applications to the finite model theory of relational structures. In the setting of relational structures, conformal covers serve to construct guarded bisimilar companion structures that avoid all incidental Gaifman cliques-thus serving as a partial analogue in finite model theory for the usually infinite guarded unravellings. In hypergraph theoretic terms, we show that every finite hypergraph admits a bisimilar cover (...) by a finite conformal hypergraph. In terms of relational structures, we show that every finite relational structure admits a guarded bisimilar cover by a finite structure whose Gaifman cliques are guarded. One of our applications answers an open question about a clique constrained strengthening of the extension property for partial automorphisms (EPPA) of Hrushovski, Herwig and Lascar. A second application provides an alternative proof of the finite model property (FMP) for the clique guarded fragment of first-order logic CGF, by reducing (finite) satisfiability in CGF to (finite) satisfiability in the guarded fragment, GF. (shrink)

First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: (...) iε I} is a family of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (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)

Model theory is concerned mainly, although not exclusively, with infinite structures. In recent years, finite structures have risen to greater prominence, both within the context of mainstream model theory, e.g., in work of Lachlan, Cherlin, Hrushovski, and others, and with the advent of finite model theory, which incorporates elements of classical model theory, combinatorics, and complexity theory. The purpose of this survey is to provide an overview of what might be called the model theory of (...) class='Hi'>finite structures. Some topics in finite model theory have strong connections to theoretical computer science, especially descriptive complexity theory. In fact, it has been suggested that finite model theory really is, or should be, logic for computer science. These connections with computer science will, however, not be treated here.It is well-known that many classical results of ‘infinite model theory’ fail over the class of finite structures, including the compactness and completeness theorems, as well as many preservation and interpolation theorems. The failure of compactness in the finite, in particular, means that the standard proofs of many theorems are no longer valid in this context. At present, there is no known example of a classical theorem that remains true over finite structures, yet must be proved by substantially different methods. It is generally concluded that first-order logic is ‘badly behaved’ over finite structures.From the perspective of expressive power, first-order logic also behaves badly: it is both too weak and too strong. Too weak because many natural properties, such as the size of a structure being even or a graph being connected, cannot be defined by a single sentence. Too strong, because every class of finite structures with a finite signature can be defined by an infinite set of sentences. Even worse, every finite structure is defined up to isomorphism by a single sentence. In fact, it is perhaps because of this last point more than anything else that model theorists have not been very interested in finite structures. Modern model theory is concerned largely with complete first-order theories, which are completely trivial here. (shrink)

There are properties of finite structures that are expressible with the use of Hilbert's ε-operator in a manner that does not depend on the actual interpretation for ε-terms, but not expressible in plain first-order. This observation strengthens a corresponding result of Gurevich, concerning the invariant use of an auxiliary ordering in first-order logic over finite structures. The present result also implies that certain non-deterministic choice constructs, which have been considered in database theory, properly enhance the expressive (...) power of first-order logic even as far as deterministic queries are concerned, thereby answering a question raised by Abiteboul and Vianu. (shrink)

We consider successor-invariant first-order logic (FO + succ)inv, consisting of sentences Φ involving an “auxiliary” binary relation S such that (.

In this paper, we continue the study of the Killing symmetries of an N-dimensional generalized Minkowski space, i.e., a space endowed with a metric tensor, whose coefficients do depend on a set of non-metrical coordinates. We discuss here the finite structure of the space–time rotations in such spaces, by confining ourselves to the four-dimensional case. In particular, the results obtained are specialized to the case of a “deformed” Minkowski space M_4, for which we derive the explicit general form of (...) the finite rotations and boosts in different parametric bases. (shrink)

Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.

Ajtai’s completeness theorem roughly states that a countable structure A coded in a model of arithmetic can be end-extended and expanded to a model of a given theory G if and only if a contradiction cannot be derived by a proof from G plus the diagram of A, provided that the proof is definable in A and contains only formulas of a standard length. The existence of such model extensions is closely related to questions in complexity theory. In this paper (...) we give a new proof of Ajtai’s theorem using basic techniques of model theory. (shrink)

We study model theory of actions of finite groups on substructures of a stable structure. We give an abstract description of existentially closed actions as above in terms of invariants and PAC structures. We show that if the corresponding PAC property is first order, then the theory of such actions has a model companion. Then, we analyze some particular theories of interest (mostly various theories of fields of positive characteristic) and show that in all the cases considered the (...) PAC property is first order. (shrink)

Inside a combinatory algebra, there are ‘internal’ versions of the finite type structure over ω, which form models of various systems of finite type arithmetic. This paper compares internal representations of the intensional and extensional functionals. If these classes coincide, the algebra is called ft-extensional. Some criteria for ft-extensionality are given and a number of well-known ca's are shown to be ft-extensional, regardless of the particular choice of representation for ω. In particular, DA, Pω, Tω, Hω and certain (...) D∞-models all share the property of ft-extensionality. It is also shown that ft-extensionality is by no means an intrinsic property of ca's i.e., that there exists a very concrete class of ca's—the class of reflexive coherence spaces—no member of which has this property. This leads to a comparison of ft-extensionality with the well-studied notions of extensionality and weak extensionality. Ft-extensionality turns out to be completely independent. (shrink)

A superstable homogeneous structure is said to be simple if every complete type over any set A has a free extension over any B ⊇ A. In this paper we give a characterization for this property in terms of U-rank. As a corollary we get that if the structure has finite U-rank, then it is simple.

The main result of this paper is a probabilistic construction of finite rigid structures. It yields a finitely axiomatizable class of finite rigid structures where no L ω ∞,ω formula with counting quantifiers defines a linear order.

Universality has been an important concept in computable structure theory. A class C of structures is universal if, informally, for any structure of any kind there is a structure in C with the same computability-theoretic properties as the given structure. Many classes such as graphs, groups, and fields are known to be universal. This paper is about the class of finitely generated groups. Because finitely generated structures are relatively simple, the class of finitely generated groups has no hope (...) of being universal. We show that finitely generated groups are as universal as possible, given that they are finitely generated: for every finitely generated structure, there is a finitely generated group which has the same computability-theoretic properties. The same is not true for finitely generated fields. We apply the results of this investigation to quasi Scott sentences, and also answer a question of Alvir, Knight, and McCoy. (shrink)

We generalize the result of non-finite axiomatizability of totally categorical first-order theories from elementary model theory to homogeneous model theory. In particular, we lift the theory of envelopes to homogeneous model theory and develope theory of imaginaries in the case of ω-stable homogeneous classes of finite U-rank.

We show that the structure R of recursively enumerable degrees is not a Σ₁-elementary substructure of Dn, where Dn (n > 1) is the structure of n-r.e. degrees in the Ershov hierarchy.

We show that any structure of finite Morley Rank having the definable multiplicity property has a rank and multiplicity preserving interpretation in a strongly minimal set. In particular, every totally categorical theory admits such an interpretation. We also show that a slightly weaker version of the DMP is necessary for a structure of finite rank to have a strongly minimal expansion. We conclude by constructing an almost strongly minimal set which does not have the DMP in any rank (...) preserving expansion, and ask whether this structure is interpretable in a strongly minimal set. (shrink)

A countably infinite relational structure M is called absolutely ubiquitous if the following holds: whenever N is a countably infinite structure, and M and N have the same isomorphism types of finite induced substructures, there is an isomorphism from M to N. Here a characterisation is given of absolutely ubiquitous structures over languages with finitely many relation symbols. A corresponding result is proved for uncountable structures.

A structure has a (finite-string) automatic presentation if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a decidable first-order theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.

We consider a universe of finite Morley rank and the following definable objects: a field math formula, a non-trivial action of a group math formula on a connected abelian group V, and a torus T of G such that math formula. We prove that every T-minimal subgroup of V has Morley rank math formula. Moreover V is a direct sum of math formula-minimal subgroups of the form math formula, where W is T-minimal and ζ is an element of G (...) of order 4 inverting T. (shrink)

Call a family F of subsets of a set E inductive if ∅ ∈ F and F is closed under unions with disjoint singletons, that is, if ∀X∈F ∀x∈E–X(X ∪ {x} ∈ F]. A Frege structure is a pair (E.