From decomposable to residual theories

Over the last decade, first-order constraints have been efficiently used in the artificial intelligence world to model many kinds of complex problems such as: scheduling, resource allocation, computer graphics and bio-informatics. Recently, a new property called decomposability has been introduced and many first-order theories have been proved to be decomposable: finite or infinite trees, rational and real numbers, linear dense order, etc. A decision procedure in the form of five rewriting rules has also been developed. This latter can decide if a first-order formula without free variables is true or not in any decomposable theory. Unfortunately, the definition of decomposable theories is too much complex: theoretical and definitively not intuitive. As a consequence, checking whether a given theory T is decomposable is almost impossible for a non expert in decomposability. We introduce in this paper residual theories: a new class of first-order theories whose definition is very intuitive, easy to check and much more adapted to the needs of the artificial intelligence community. We show that decomposable theories is a sub-class of residual theories and present, not only a decision procedure, but a full first-order constraint solver for residual theories. It transforms any first-order constraint φ (which can possibly contain free variables) into an equivalent formula ? which is either the formula true, or the formula false or a simple solved formula having at least one free variable and being equivalent neither to true nor to false. We show the efficiency of our solver by solving complex first-order constraints containing long nested alternations of quantifiers over different residual theories.     

Higher Intersection Theory on Algebraic Stacks: II

This is the second part of our work on the intersection theory of algebraic stacks. The main results here are the following. We provide an intersection pairing for all smooth Artin stacks (locally of finite type over a field) which we show reduces to the known intersection pairing on the Chow groups of smooth Deligne–Mumford stacks of finite type over a field as well as on the Chow groups of quotient stacks associated to actions of linear algebraic groups on smooth quasi-projective schemes modulo torsion. The former involves also showing the existence of Adams operations on the rational étale K-theory of all smooth Deligne–Mumford stacks of finite type over a field. In addition, we show that our definition of the higher Chow groups is intrinsic to the stack for all smooth stacks and also stacks of finite type over the given field. Next we establish the existence of Chern classes and Chern character for Artin stacks with values in our Chow groups and extend these to higher Chern classes and a higher Chern character for perfect complexes on an algebraic stack, taking values in cohomology theories of algebraic stacks that are defined with respect to complexes of sheaves on a big smooth site. As a by-product of our techniques we also provide an extension of higher intersection theory to all schemes locally of finite type over a field. As the higher cycle complex, by itself, is a bit difficult to handle, the stronger results like contravariance for arbitrary maps between smooth stacks and the intersection pairing for smooth stacks are established by comparison with motivic cohomology.     

Σ-definability of uncountable models of <Emphasis Type="Italic">c</Emphasis>-simple theories

We show that each c-simple theory with an additional discreteness condition has an uncountable model Σ-definable in ℍ$ \mathbb{H} $ \mathbb{H} ($ \mathbb{L} $ \mathbb{L} ), where $ \mathbb{L} $ \mathbb{L} is a dense linear order. From this we establish the same for all c-simple theories of finite signature that are submodel complete.     

Mutual definability does not imply definitional equivalence,a simple example

We give two theories, Th₁ and Th₂, which are explicitly definable over each other (i.e. the relation symbols of one theory are explicitly definable in the other, and vice versa), but are not definitionally equivalent. The languages of the two theories are disjoint. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Definability in the lattice of equational theories of semigroups

We study first-order definability in the latticeL of equational theories of semigroups. A large collection of individual theories and some interesting sets of theories are definable inL. As examples, ifT is either the equational theory of a finite semigroup or a finitely axiomatizable locally finite theory, then the set {T, T ^ϖ} is definable, whereT ^ϖ is the dual theory obtained by inverting the order of occurences of letters in the words. Moreover, the set of locally finite theories, the set of finitely axiomatizable theories, and the set of theories of finite semigroups are all definable. The research of both authors was supported by National Science Foundation Grant No. DMS-8302295     

Topological differential fields

We consider first-order theories of topological fields admitting a model-completion and their expansion to differential fields (requiring no interaction between the derivation and the other primitives of the language). We give a criterion under which the expansion still admits a model-completion which we axiomatize. It generalizes previous results due to M. Singer for ordered differential fields and of C. Michaux for valued differential fields. As a corollary, we show a transfer result for the NIP property. We also give a geometrical axiomatization of that model-completion. Then, for certain differential valued fields, we extend the positive answer of Hilbert’s seventeenth problem and we prove an Ax-Kochen-Ershov theorem. Similarly, we consider first-order theories of topological fields admitting a model-companion and their expansion to differential fields, and under a similar criterion as before, we show that the expansion still admits a model-companion. This last result can be compared with those of M. Tressl: on one hand we are only dealing with a single derivation whereas he is dealing with several, on the other hand we are not restricting ourselves to definable expansions of the ring language, taking advantage of our topological context. We apply our results to fields endowed with several valuations (respectively several orders).     

Free algebras over Bezout domains are Sylvester domains

Let λ be a finitary geometric theory and δ its classifying topos. We prove that δ is Boolean if and only if (1) every first-order formula in the language of λ is ?-provably equivalent to a geometric formula and (2) for any finite list of varibles, x, there are, up to ?-provable equivalence, only finitely many formulas, in the language of λ with free variables among x. We use this characterization to show that, when δ is Boolean, it is an atomic topos and can be viewed as a finite coproduct of topoi of continuous G-sets for topological groups G satisfying a certain finiteness condition.     

On Representing Concepts in Finite Models

We present a method of transferring Tarski's technique of classifying finite order concepts by means of truth‐definitions into finite mode theory. The other considered question is the problem of representability relations on words or natural numbers in finite models. We prove that relations representable in finite models are exactly those which are of degree ≤ o′. Finally, we consider theories of sufficiently large finite models. For a given theory T we define sl(T) as the set of all sentences true in almost all finite models for T. For theories of sufficiently large models our version of Tarski's technique becomes practically the same as the classica one. We investigate also degrees of undecidability for theories of sufficiently large finite models. We prove for some special theory ST that its degree is stronger than 0′ but still not more than Σ⁰₂.     

Bilinear spaces over a fixed field are simple unstable

We study the model theory of vector spaces with a bilinear form over a fixed field. For finite fields this can be, and has been, done in the classical framework of full first-order logic. For infinite fields we need different logical frameworks. First we take a category-theoretic approach, which requires very little set-up. We show that linear independence forms a simple unstable independence relation. With some more work we then show that we can also work in the framework of positive logic, which is much more powerful than the category-theoretic approach and much closer to the classical framework of full first-order logic. We fully characterise the existentially closed models of the arising positive theory. Using the independence relation from before we conclude that the theory is simple unstable, in the sense that dividing has local character but there are many distinct types. We also provide positive version of what is commonly known as the Ryll-Nardzewski theorem for ω-categorical theories in full first-order logic, from which we conclude that bilinear spaces over a countable field are ω-categorical.     

Algebraization of the Three‐valued BCK‐logic

In this paper a definition of n‐valued system in the context of the algebraizable logics is proposed. We define and study the variety V₃, showing that it is definitionally equivalent to the equivalent quasivariety semantics for the “Three‐valued BCK‐logic”. As a consequence we find an axiomatic definition of the above system.     

Definability in the structure of words with the inclusion relation

We develop a theory of (first-order) definability in the subword partial order in parallel with similar theories for the h-quasiorder of finite k-labeled forests and for the infix order. In particular, any element is definable (provided that the words of length 1 or 2 are taken as parameters), the first-order theory of the structure is atomic and computably isomorphic to the first-order arithmetic. We also characterize the automorphism group of the structure and show that every predicate invariant under the automorphisms of the structure is definable in the structure.     

Representation Dimension and Quasi-hereditary Algebras

We study Auslander's representation dimension of Artin algebras, which is by definition the minimal projective dimension of coherent functors on modules which are both generators and cogenerators. We show the following statements: (1) if an Artin algebra A is stably hereditary, then the representation dimension of A is at most 3. (2) If two Artin algebras are stably equivalent of Morita type, then they have the same representation dimension. Particularly, if two self-injective algebras are derived equivalent, then they have the same representation dimension. (3) Any incidence algebra of a finite partially ordered set over a field has finite representation dimension. Moreover, we use results on quasi-hereditary algebras to show that (4) the Auslander algebra of a Nakayama algebra has finite representation dimension.     

Equivalence in Finite-Variable Logics is Complete for Polynomial Time

of first-order logic whose formulas contain at most k variables (for some ). We show that for each , equivalence in the logic is complete for polynomial time. Moreover, we show that the same completeness result holds for the powerful extension of with counting quantifiers (for every ). The k-dimensional Weisfeiler–Lehman algorithm is a combinatorial approach to graph isomorphism that generalizes the naive color-refinement method (for ). Cai, Fürer and Immerman [6] proved that two finite graphs are equivalent in the logic if, and only if, they can be distinguished by the k-dimensional Weisfeiler-Lehman algorithm. Thus a corollary of our main result is that the question of whether two finite graphs can be distinguished by the k-dimensional Weisfeiler–Lehman algorithm is P-complete for each . Received: March 23, 1998     

Multi-fuzzy sets: An extension of fuzzy sets

In this paper we propose a method to construct more general fuzzy sets using ordinary fuzzy sets as building blocks. We introduce the concept of multi-fuzzy sets in terms of ordered sequences of membership functions. The family of operations T, S, M of multi-fuzzy sets are introduced by coordinate wise t-norms, s-norms and aggregation operations. We define the notion of coordinate wise conjugation of multifuzzy sets, a method for obtaining Atanassov’s intuitionistic fuzzy operations from multi-fuzzy sets. We show that various binary operations in Atanassov’s intuitionistic fuzzy sets are equivalent to some operations in multi-fuzzy sets like M operations, 2-conjugates of the T and S operations. It is concluded that multi-fuzzy set theory is an extension of Zadeh’s fuzzy set theory, Atanassov’s intuitionsitic fuzzy set theory and L-fuzzy set theory.     

On the Boolean algebras of definable sets in weakly o‐minimal theories

We consider the sets definable in the countable models of a weakly o‐minimal theory T of totally ordered structures. We investigate under which conditions their Boolean algebras are isomorphic (hence T is p‐ω‐categorical), in other words when each of these definable sets admits, if infinite, an infinite coinfinite definable subset. We show that this is true if and only if T has no infinite definable discrete (convex) subset. We examine the same problem among arbitrary theories of mere linear orders. Finally we prove that, within expansions of Boolean lattices, every weakly o‐minimal theory is p‐ω‐categorical. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Spreading-invariant sequences and processes on bounded index sets

We say that a random sequence is spreadable if all subsequences of equal length have the same distribution. For infinite sequences the notion is equivalent to exchangeability but for finite sequences it is more general. The present paper is devoted to a systematic study of finite spreadable sequences and of processes on [0, 1] with spreadable increments. In particular, we show how many basic results in the exchangeable case—notably the predictable sampling theorem, the Wald-type identities, and various martingale and weak convergence results—admit extensions to a spreadable setting. We also identify some additional conditions that ensure the exchangeability of a spreadable sequence or process. Received: 9 November 1999 / Revised version: 16 March 2000 / Published online: 18 September 2000     

Simple monadic theories and partition width

We study tree‐like decompositions of models of a theory and a related complexity measure called partition width. We prove a dichotomy concerning partition width and definable pairing functions: either the partition width of models is bounded, or the theory admits definable pairing functions. Our proof rests on structure results concerning indiscernible sequences and finitely satisfiable types for theories without definable pairing functions. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Sufficient conditions for effective translation of locally generic queries

This paper continues investigations into the database of queries of first-order language theory. It is known that for many decidable theories, the collapse result holds: each locally generic query is equivalent to some restricted query. But, until now, the problem of effective construction of this query remains almost unexplored. We use earlier results of the author on the construction of a method of effective obtaining this query. The method is rather general and applicable, for example, to the Presburger arithmetic and the real number theory.     

Higher Intersection Theory on Algebraic Stacks: I

In this paper and the sequel we establish a theory of Chow groups and higher Chow groups on algebraic stacks locally of finite type over a field and establish their basic properties. This includes algebraic stacks in the sense of Deligne–Mumford as well as Artin. An intrinsic difference between our approach and earlier approaches is that the higher Chow groups of Bloch enter into our theory early on and depends heavily on his fundamental work. Our theory may be more appropriately called the (Lichtenbaum) motivic homology and cohomology of algebraic stacks. One of the main themes of these papers is that such a motivic homology does provide a reasonable intersection theory for algebraic stacks (of finite type over a field), with several key properties holding integrally and extending to stacks locally of finite type. While several important properties of our higher Chow groups, like covariance for projective representable maps (that factor as the composition of a closed immersion into the projective space associated to a locally free coherent sheaf and the obvious projection), an intersection pairing and contravariant functoriality for all smooth algebraic stacks, are shown to hold integrally, our theory works best with rational coefficients.The main results of Part I are the following. The higher Chow groups are defined in general with respect to an atlas, but are shown to be independent of the choice of the atlas for smooth stacks if one uses finite coefficients with torsion prime to the characteristics or in general for Deligne–Mumford stacks. (Using some results on motivic cohomology, we extend this integrally to all smooth algebraic stacks in Part II.) Using cohomological descent, we extend Bloch's fundamental localization sequence for quasi-projective schemes to long exact localization sequences of the higher Chow groups modulo torsion for all Artin stacks: this is one of the main results of the paper. We show that these higher Chow groups modulo torsion are covariant for all proper representable maps between stacks of finite type while being contravariant for all representable flat maps and, in Part II, that they are independent of the choice of an atlas for all stacks of finite type over the given field k. The comparison with motivic cohomology, as is worked out in Part II, enables us to provide an explicit comparison of our theory for quotient stacks associated to actions of linear algebraic groups on quasi-projective schemes with the corresponding Totaro–Edidin–Graham equivariant intersection theory. As an application of our theory we compute the higher Chow groups of Deligne–Mumford stacks and show that they are isomorphic modulo torsion to the higher Chow groups of their coarse moduli spaces. As a by-product of our theory we also produce localization sequences in (integral) higher Chow groups for all schemes locally of finite type over a field: these higher Chow groups are defined as the Zariski hypercohomology with respect to the cycle complex.