Abstract Answering a question of Junker and Ziegler, we construct a countable first order structure which is not ω-categorical, but does not have any proper nontrivial reducts, in either of two senses (model-theoretic, and group-theoretic). We also construct a strongly minimal set which is not ω-categorical but has no proper nontrivial reducts in the model-theoretic sense.

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.

A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction. Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from artificial intelligence, can be formulated with constraint languages that are rather well-behaved from a model-theoretic point of view. In particular, the automorphism group of these constraint languages tends to be large in the sense that the number of orbits of n -subsets of the automorphism group is bounded by some function in n . In this article we present a generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of n -subsets grows subexponentially in n , and prove that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes CSPs that cannot be solved by Datalog.

This paper contains a result on the reconstruction of certain homogeneous transitive ω-categorical structures from their automorphism group. The structures treated are relational. In the proof it is shown that their automorphism group contains a generic pair (in a slightly non-standard sense, coming from Baire category). Reconstruction results give conditions under which the abstract group structure of the automorphism group Aut( ) of an ω-categorical structure determines the topology on Aut( ), and hence determines up to bi-interpretability, by [1]; they can also give conditions under which the abstract group Aut( ) determines the permutation group ⟨Aut ( ), ⟩. so determines up to bi-definability. One such condition has been identified by M. Rubin in [12], and it is related to the definability, in Aut( ), of point stabilisers. If the condition holds, the structure is said to have a weak ∀∃ interpretation, and Aut( ) determines up to bi-interpretability or, in some cases, up to bi-definability. A better-known approach to reconstruction is via the ‘small index property’: an ω-categorical stucture has the small index property if any subgroup of Aut( ) of index less than is open. This guarantees that the abstract group structure of Aut( ) determines the topology, so if is ω-categorical with Aut( ) ≅ Aut( ) then and are bi-interpretable.

In this note, we consider models of the theories of valued algebraically closed fields and convexly valued real closed fields, their reducts to the pure field or ordered field language respectively, and expansions of these by predicates which are definable in the valued field. We show that, in terms of definability, there is no structure properly between the pure (ordered) field and the valued field. Our results are analogous to several other definability results for reducts of algebraically closed and real closed fields; see [9], [10], [11] and [12]. Throughout this paper, definable will mean definable with parameters. Theorem A. Let ℱ = (F, +, ×, V) be a valued, algebraically closed field, where V denotes the valuation ring. Let A be a subset ofFndefinable in ℱv. Then either A is definable in ℱ = (F, +, ×) or V is definable in . Theorem B. Let ℛv = (R, <, +, ×, V) be a convexly valued real closed field, where V denotes the valuation ring. Let Abe a subset ofRndefinable in ℛv. Then either A is definable in ℛ = (R, <, +, ×) or V is definable in . The proofs of Theorems A and B are quite similar. Both ℱv and ℛv admit quantifier elimination if we adjoin a definable binary predicate Div (interpreted by Div(x, y) if and only if v(x) ≤ v(y)). This is proved in [14] (extending [13]) in the algebraically closed case, and in [4] in the real closed case. We show by direct combinatorial arguments that if the valuation is not definable then the expanded structure is strongly minimal or o-minimal respectively. Then we call on known results about strongly minimal and o-minimal fields to show that the expansion is not proper.

In this paper we formulate a notion similar to o-minimality but appropriate for the p-adics. The paper is in a sense a sequel to [11] and [5]. In [11] a notion of minimality was formulated, as follows. Suppose that L, L+ are first-order languages and + is an L+-structure whose reduct to L is . Then + is said to be -minimal if, for every N+ elementarily equivalent to +, every parameterdefinable subset of its domain N+ is definable with parameters by a quantifier-free L-formula. Observe that if L has a single binary relation which in is interpreted by a total order on M, then we have just the notion of strong o-minimality, from [13]; and by a theorem from [6], strong o-minimality is equivalent to o-minimality. If L has no relations, functions, or constants (other than equality) then the notion is just strong minimality. In [11], -minimality is investigated for a number of structures . In particular, the C-relation of [1] was considered, in place of the total order in the definition of strong o-minimality. The C-relation is essentially the ternary relation which naturally holds on the maximal chains of a sufficiently nice tree; see [1], [11] or [5] for more detail, and for axioms. Much of the motivation came from the observation that a C-relation on a field F which is preserved by the affine group AGL(1,F) (consisting of permutations (a,b) : x ↦ ax + b, where a ∈ F \ {0} and b ∈ F) is the same as a non-trivial valuation: to get a C-relation from a valuation ν, put C(x;y,z) if and only if ν(y − x) < ν(y − z).

Abstract Let L be a finite relational language. The age of a structure over L is the set of isomorphism types of finite substructures of . We classify those ages for which there are less than 2ω countably infinite pairwise nonisomorphic L-structures of age .

Abstract It is shown lhat no infinite group is interpretable in any structure which is homogeneous in a finite relational language. Related questions are discussed for other ω-categorical structures.

For a structure let φ( ) be the number of nonisomorphic, countably infinite substructures of . The problem considered here, suggested by M. Pouzet, is that of characterizing those countable for which φ( ) ≤ ℵ0. In this paper we will deal exclusively with structures in a finite, binary relational language L. The characterization of those L-structures for which φ( ) ≤ ℵ0 (which turns out to be equivalent to ) is given in Theorem 3. It is the culmination of a three-step process. The first step, resulting in Theorem 1, shows that for a countable stable L-structure , φ( ) ≤ ℵ0 iff is cellular. (See Definition 0.1.) In the second step we consider linearly ordered sets = (A, ≤ ℵ0), and characterize in Theorem 2 the order types of those for which φ( ) ≤ ℵ0. Finally, in Theorem 3, we amalgamate Theorems 1 and 2 to get the classification of all countable L-structures for which φ( ) ≤ ℵ0.

Abstract 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.