We revisit evaluation of logical formulas that allow both uninterpreted relations, constrained to be finite, as well as interpreted vocabulary over an infinite domain: denoted in the past as embedded finite model theory. We extend the analysis of "collapse results": the ability to eliminate first-order quantifiers over the infinite domain in favor of quantification over the finite structure. We investigate several weakenings of collapse, one allowing higher-order quantification over the finite structure, another allowing expansion of the theory. We also provide results comparing collapse for unary signatures with general signatures, and new analyses of collapse for natural decidable theories.

A polynomial program is one in which all assignments are given by polynomial expressions and in which all branching is nondeterministic (as opposed to conditional). Given such a program, an algebraic invariant is one that is defined by polynomial equations over the program variables at each program location. Müller-Olm and Seidl have posed the question of whether one can compute the strongest algebraic invariant of a given polynomial program. In this article, we show that, while strongest algebraic invariants are not computable in general, they can be computed in the special case of affine programs, that is, programs with exclusively linear assignments. For the latter result, our main tool is an algebraic result of independent interest: Given a finite set of rational square matrices of the same dimension, we show how to compute the Zariski closure of the semigroup that they generate.

We exhibit an algorithm to compute the strongest polynomial (or algebraic) invariants that hold at each location of a given affine program (i.e., a program having only non-deterministic (as opposed to conditional) branching and all of whose assignments are given by affine expressions). Our main tool is an algebraic result of independent interest: given a finite set of rational square matrices of the same dimension, we show how to compute the Zariski closure of the semigroup that they generate.

Abstract We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the ‘geometric’ sorts which suffice to code all imaginaries in the corresponding algebraic setting.

Abstract We study the automorphism group of the algebraic closure of a substructureAof a pseudo-finite fieldF. We show that the behavior of this group, even whenAis large, depends essentially on the roots of unity inF. For almost all completions of the theory of pseudofinite fields, we show that overA, algebraic closure agrees with definable closure, as soon asAcontains the relative algebraic closure of the prime field.

Abstract We give several characterizations of weakly minimal abelian structures. In two special cases, dual in a sense to be made explicit below, we give precise structure theorems: 1. when the only finite 0-definable subgroup is {0}, or equivalently 0 is the only algebraic element (the co-strongly minimal case); 2. when the theory of the structure is strongly minimal. In the first case, we identify the abelian structure as a “near-subspace” A of a vector space V over a division ring D with its induced structure, with possibly some collection of distinguished subgroups of A of finite index in A and (up to acl(∅)) no further structure. In the second, the structure is that of V/A for a vector space and near-subspace as above, with the only further possible structure some collection of distinguished points. Here a near-subspace of V is a subgroup A such that for any nonzero d ∈ D. the index of A ∩ dA, in A is finite. We also show that any weakly minimal abelian structure is a reduct of a weakly minimal module.

Abstract We construct a strongly minimal set which is not a finite cover of one with DMP. We also show that for a strongly minimal theory T, generic automorphisms exist iff T has DMP, thus proving a conjecture of Kikyo and Pillay.

Abstract We use a new construction of an o-minimal structure, due to Lipshitz and Robinson, to answer a question of van den Dries regarding the relationship between arbitrary o-minimal expansions of real closed fields and structures over the real numbers. We write a first order sentence which is true in the Lipshitz-Robinson structure but fails in any possible interpretation over the field of real numbers.

Abstract We give some general criteria for the stable embeddedness of a definable set. We use these criteria to establish the stable embeddedness in algebraically closed valued fields of two definable sets: The set of balls of a given radius r < 1 contained in the valuation ring and the set of balls of a given multiplicative radius r < 1. We also show that in an algebraically closed valued field a 0-definable set is stably embedded if and only if its algebraic closure is stably embedded.

Abstract Orthogonality between two stably embedded definable sets is preserved under the addition of constants.

International audience

By a classifiable theory we shall mean a theory which is superstable, without the dimensional order property, which has prime models over pairs. In order to define what we mean by unique decomposition, we remind the reader of several definitions and results. We adopt the usual conventions of stability theory and work inside a large saturated model of a fixed classifiable theory T; for instance, if we write M ⊆ N for models of T, M and N we are thinking of these models as elementary submodels of this fixed saturated models; so, in particular, M is an elementary submodel of N. Although the results will not depend on it, we will assume that T is countable to ease notation. We do adopt one piece of notation which is not completely standard: if T is classifiable, M0 ⊆ Mi for i = 1, 2 are models of T and M1 is independent from M2 over M0 then we write M1 M2 for the prime model over M1 ∪ M2.

We note here, in answer to a question of Poizat, that the Morley and Lascar ranks need not coincide in differentially closed fields. We will approach this through the (perhaps) more fundamental issue of the variation of Morley rank in families. We will be interested here only in sets of finite Morley rank. Section 1 consists of some general lemmas relating the above issues. Section 2 points out a family of sets of finite Morley rank, whose Morley rank exhibits discontinuous upward jumps. To make the base of the family itself have finite Morley rank, we use a theorem of Buium.

We know from [H1], [H2] that in a stable theory, given a nontrivial locally modular regular type q, one can define a group with generic domination equivalent to q, and that the dependence relation on q can be analyzed in terms of this group. In a stable one-based theory, every regular type is locally modular; hence, this result holds for every nontrivial regular type. We show here that, in fact, in a stable one-based theory, a similar type of construction can be done without the assumption of regularity. More precisely, we show that for any type q, the nontrivial part of q can be analyzed by generics of groups and that any nontrivial relation can be described by affine relations (Theorem A). This construction is then used to answer a question about homogeneity in pairs of models which is still open in the case of arbitrary stable theories (Theorem C).

Abstract Finitely axiomatizable ℵ1categorical theories are locally modular.

Abstract Kueker's conjecture is proved for stable theories, for theories that interpret a linear ordering, and for theories with Skolem functions. The proof of the stable case involves certain results on coordinatization that are of independent interest.

Abstract A stable theory is finitely based if every set of indiscernibles is based on a finite subset. This is a common generalization of superstability and 1-basedness. We show that if such theories have more than one model they must have infinitely many, and prove some other conjectures.