Complete Theories with Finitely Many Countable Models. I

A syntactic characterization is furnished for the class of elementary complete theories with finitely many countable models, which is the analog of a known theorem by Ryll-Nardzewski on countably categorical theories, and is based on classifying the theories by Rudin-Keisler quasiorders and distribution functions of a number of models limit over types.     

Fuzzy Horn logic II

The paper studies closure properties of classes of fuzzy structures defined by fuzzy implicational theories, i.e. theories whose formulas are implications between fuzzy identities. We present generalizations of results from the bivalent case. Namely, we characterize model classes of general implicational theories, finitary implicational theories, and Horn theories by means of closedness under suitable algebraic constructions.     

Universal Horn classes and antivarieties of algebraic systems

We define and study universal Horn classes dual to varieties in both the syntactic and the semantic sense. Such classes, which we call antivarieties, appear naturally, e.g., in graph theory and in formal language theory. The basic results are the characterization theorem for antivarieties, the theorem on cores in axiomatizable color-families, and the decidability theorem for universal theories of families of interpretations of formal languages. Supported by RFFR grants Nos. 99-01-000485 and 96-01-00097, and also by DFG grant No. 436113/2670. Translated fromAlgebra i Logika, Vol. 39, No. 1, pp. 3–22, January–February, 2000.     

The Essentially Equational Theory of Horn Classes

It is well known that the model categories of universal Horn theories are locally presentable, hence essentially algebraic (see [2]). In the special case of quasivarieties a direct translation of the implicational syntax into the essentially equational one is known (see [1]). Here we present a similar translation for the general case, showing at the same time that many relationally presented Horn classes are in fact (equivalent to) quasivarieties.     

Towards a Ryll‐Nardzewski‐type theorem for weakly oligomorphic structures

A structure is called weakly oligomorphic if its endomorphism monoid has only finitely many invariant relations of every arity. The goal of this paper is to show that the notions of homomorphism‐homogeneity, and weak oligomorphy are not only completely analogous to the classical notions of homogeneity and oligomorphy, but are actually closely related. We first prove a Fraïssé‐type theorem for homomorphism‐homogeneous relational structures. We then show that the countable models of the theories of countable weakly oligomorphic structures are mutually homomorphism‐equivalent (we call first order theories with this property weakly ω‐categorical). Furthermore we show that every weakly oligomorphic homomorphism‐homogeneous structure contains (up to isomorphism) a unique homogeneous, homomorphism‐homogeneous core, to which it is homomorphism‐equivalent. As a consequence we obtain that every countable weakly oligomorphic structure is homomorphism‐equivalent to a finite or ω‐categorical structure. As a corollary we obtain a characterization of positive existential theories of weakly oligomorphic structures as the positive existential parts of ω‐categorical theories.     

On quasi‐varieties of multiple valued logic models

We extend the concept of quasi‐variety of first‐order models from classical logic to multiple valued logic (MVL) and study the relationship between quasi‐varieties and existence of initial models in MVL. We define a concept of ‘Horn sentence’ in MVL and based upon our study of quasi‐varieties of MVL models we derive the existence of initial models for MVL ‘Horn theories’. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Finding model-companions via the skeleton

We present an analysis on the existentially closed (e.c.) structures for some theoryT in a rather complete categorical setting. The central notion of the skeleton ofT is defined. We formulate conditions on the skeleton which limit the number of e.c. structures forT, thereby ensuring the existence of a model-companion ofT. A new (purely categorical) proof of the uniqueness of the atomic structure is given for theories having the joint-embedding-property (JEP).As an application it is shown that a finitely generated universal Horn class possesses a model-companion — a resuilt that was proved earlier by a different method.Presented by Stanley Burris.     

Complete theories with finitely many countable models. II

Previously, we obtained a syntactic characterization for the class of complete theories with finitely many pairwise non-isomorphic countable models [1]. The most essential part of that characterization extends to Ehrenfeucht theories (i.e., those having finitely many (but more than 1) pairwise non-isomorphic countable models). As the basic parameters defining a finite number of countable models, Rudin-Keisler quasiorders are treated as well as distribution functions defining the number of limit models for equivalence classes w.r.t. these quasiorders. Here, we argue to state that all possible parameters given in the characterization theorem in [1] are realizable. Also, we describe Rudin-Keisler quasiorders in arbitrary small theories. The construction of models of Ehrenfeucht theories with which we come up in the paper is based on using powerful digraphs which, along with powerful types in Ehrenfeucht theories, always locally exist in saturated models of these theories. Supported by RFBR grant Nos. 02-01-00258 and 05-01-00411. __________ Translated from Algebra i Logika, Vol. 45, No. 3, pp. 314–353, May–June, 2006.     

Fraïssé’s Construction from a Topos-Theoretic Perspective

We present a topos-theoretic interpretation of (a categorical generalization of) Fraïssé’s construction in Model Theory, with applications to homogeneous models and countably categorical theories.     

Categorical (binary) difference terms and protomodularity

In this paper we obtain an intrinsic syntactical characterization of protomodularity, via so-called categorical difference terms, similar to the one known in the case of varieties involving binary terms d satisfying d(x, x) = d(y, y). We also show that purely categorical modifications of the condition in the characterization give characterizations of Mal’tsev and additive categories, thus revealing a new conceptual link between these three classes of categories, and hence, also between the corresponding classes of varieties.     

On Holographic Structures

We introduce and study the class of holographic models which can be defined by copying of some of its finite parts by means of automorphisms. We prove this class to differ from the class of countably categorical models. Characterizations of the classes of holographic Boolean algebras, abelian groups, linear orderings, fields, and equivalences are given.

     

Axiomatisability and hardness for universal Horn classes of hypergraphs

We consider hypergraphs as symmetric relational structures. In this setting, we characterise finite axiomatisability for finitely generated universal Horn classes of loop-free hypergraphs. An Ehrenfeucht–Fraïssé game argument is employed to show that the results continue to hold when restricted to first order definability amongst finite structures. We are also able to show that every interval in the homomorphism order on hypergraphs contains a continuum of universal Horn classes and conclude the article by characterising the intractability of deciding membership in universal Horn classes generated by finite loop-free hypergraphs.     

Faith & falsity

A theory T is trustworthy iff, whenever a theory U is interpretable in T, then it is faithfully interpretable. In this paper we give a characterization of trustworthiness. We provide a simple proof of Friedman’s Theorem that finitely axiomatized, sequential, consistent theories are trustworthy. We provide an example of a theory whose schematic predicate logic is complete Π₂⁰.     

On model-theoretical properties in the sense of Peretyat’kin,o-minimality,and mutually interpretable theories

We prove that o-minimality is not a model-theoretical property in the sense of Peretyat’kin. We also prove that existence of a prime models need not be preserved under a passage between mutually interpretable theories.     

Equivalence for varieties in general and for $ {\cal BOOL} $ in particular

The varieties equivalent to a given variety are characterized in a purely categorical way. In fact they are described as the models of those Lawvere theories which are Morita equivalent to the Lawvere theory of which therefore are characterized first. Along this way the conceptual meanings of the n-th matrix power construction of a variety and McKenzie's σ-modification of classes of algebras [22] become transparent. Besides other applications not only the well known equivalences between the varieties of Post algebras of fixed orders m and the variety of Boolean algebras are obtained; moreover it can be shown that the varieties are the only varieties equivalent to . The results then are generalized to quasivarieties and more general classes of algebras. Received November 4, 1998; accepted in final form September 15, 1999.     

Automorphism groups of decidable models

It is proved that there exists no relationship between isomorphism types of the ordinary and recursive automorphism groups of recursive models and the property of being decidable for these models. Moreover, we show that all isomorphism types of recursive automorphism groups can be realized in a single (up to isomorphism) decidable countably categorical model. Taking account of the action of a group on the universe of the model makes it possible to distinguish between the classes of groups for decidable and all the recursive models.Translated fromAlgebra i Logika, Vol. 34, No. 4, pp. 437–447, July-August, 1995.     

Countably categorical theories

A series of countably categorical theories are constructed based on the Fra?sse method. In particular, an example of a decidable countably categorical theory in a finite signature is given for which no decidable model has an infinite computable set of order indiscernibles. Such a theory is used to refute Ershov’s conjecture on the representability of models of c-simple theories over linear orders.     

Models and quantifier elimination for quantified Horn formulas

In this paper, quantified Horn formulas (QHORN) are investigated. We prove that the behavior of the existential quantifiers depends only on the cases where at most one of the universally quantified variables is zero. Accordingly, we give a detailed characterization of QHORN satisfiability models which describe the set of satisfying truth assignments to the existential variables. We also consider quantified Horn formulas with free variables (QHORN^*) and show that they have monotone equivalence models.The main application of these findings is that any quantified Horn formula Φ of length |Φ| with free variables, |∀| universal quantifiers and an arbitrary number of existential quantifiers can be transformed into an equivalent quantified Horn formula of length O(|∀|·|Φ|) which contains only existential quantifiers.We also obtain a new algorithm for solving the satisfiability problem for quantified Horn formulas with or without free variables in time O(|∀|·|Φ|) by transforming the input formula into a satisfiability-equivalent propositional formula. Moreover, we show that QHORN satisfiability models can be found with the same complexity.