A structure (M, $ ,...) is called quasi-o-minimal if in any structure elementarily equivalent to it the definable subsets are exactly the Boolean combinations of 0-definable subsets and intervals. We give a series of natural examples of quasi-o-minimal structures which are not o-minimal; one of them is the ordered group of integers. We develop a technique to investigate quasi-o-minimality and use it to study quasi-o-minimal ordered groups (possibly with extra structure). Main results: any quasi-o-minimal ordered group is abelian; any quasi-o-minimal (...) ordered ring is a real closed field, or has zero multiplication; every quasi-o-minimal divisible ordered group is o-minimal; every quasi-o-minimal archimedian densely ordered group is divisible. We show that a counterpart of quasi-o-minimality in stability theory is the notion of theory of U-rank 1. (shrink)

he model theory of groups of unitriangular matrices over rings is studied. An important tool in these studies is a new notion of a quasiunitriangular group. The models of the theory of all unitriangular groups are algebraically characterized; it turns out that all they are quasiunitriangular groups. It is proved that if R and S are domains or commutative associative rings then two quasiunitriangular groups over R and S are isomorphic only if R and S are isomorphic or antiisomorphic. This (...) algebraic result is new even for ordinary unitriangular groups. The groups elementarily equivalent to a single unitriangular group UTn are studied. If R is a skew field, they are of the form UTn, for some S ≡ R. In general, the situation is not so nice. Examples are constructed demonstrating that such a group need not be a unitriangular group over some ring; moreover, there are rings P and R such that UTn ≡ UTn, but UTn cannot be represented in the form UTn for S ≡ R. We also study the number of models in a power of the theory of a unitriangular group. In particular, we prove that, for any communicative associative ring R and any infinite power λ, I = I). We construct an associative ring such that I = 3 and I) = 2. We also study models of the theory of UTn in the case of categorical R. (shrink)

We consider relational databases organized over an ordered domain with some additional relations — a typical example is the ordered domain of rational numbers together with the operation of addition. In the focus of our study are the first-order queries that are invariant under order-preserving “permutations” — such queries are called order-generic. It has recently been discovered that for some domains order-generic FO queries fail to express more than pure order queries. For example, every order-generic FO query over rational numbers (...) with + can be rewritten without +. For some other domains, however, this is not the case.We provide very general conditions on the FO theory of the domain that ensure the collapse of order-generic extended FO queries to pure order queries over this domain: the Pseudo-finite Homogeneity Property and a stronger Isolation Property. We further distinguish one broad class of domains satisfying the Isolation Property, the so-called quasi-o-minimal domains. This class includes all the o-minimal domains, but also the ordered group of integer numbers and the ordered semigroup of natural numbers, and some other domains.An important difference of this paper from the recent series of related papers is that we generalize all the notions to the case of finitely representable database states — as opposed to finite states — and develop a general lifting technique that, essentially, allows us to extend any result of the kind we are interested in, from finite to finitely representable states. We show, however, that these results cannot be transfered to arbitrary infinite states. (shrink)

A totally ordered group G is called coset-minimal if every definable subset of G is a finite union of cosets of definable subgroups intersected with intervals with endpoints in G{±∞}. Continuing work in Belegradek et al. 1115) and Point and Wagner 261), we study coset-minimality, as well as two weak versions of the notion: eventual and ultimate coset-minimality. These groups are abelian; an eventually coset-minimal group, as a pure ordered group, is an ordered abelian group of finite regular rank. Any (...) pure ordered abelian group of finite regular rank is ultimately coset-minimal and has the exchange property; moreover, every definable function in such a group is piecewise linear. Pure coset-minimal and eventually coset-minimal groups are classified. In a discrete coset-minimal group every definable unary function is piece-wise linear 261), where coset-minimality of the theory of the group was required). A dense coset-minimal group has the exchange property ); moreover, any definable unary function is piecewise linear, except possibly for finitely many cosets of the smallest definable convex nonzero subgroup. Finally, we give some examples and open questions. (shrink)

We prove that any torsion-free, residually finite relatively free group of infinite rank is not \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\aleph_1}$$\end{document} -homogeneous. This generalizes Sklinos’ result that a free group of infinite rank is not \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\aleph_1}$$\end{document} -homogeneous, and, in particular, gives a new simple proof of that result.

A relation on a linearly ordered structure is called semi-bounded if it is definable in an expansion of the structure by bounded relations. We study ultimate behavior of semi-bounded relations in an ordered module M over an ordered commutative ring R such that M/rM is finite for all nonzero r $\epsilon$ R. We consider M as a structure in the language of ordered R-modules augmented by relation symbols for the submodules rM, and prove several quantifier elimination results for semi-bounded relations (...) and functions in M. We show that these quantifier elimination results essentially characterize the ordered modules M with finite indices of the submodules rM. It is proven that (1) any semi-bounded k-ary relation on M is equal, outside a finite union of k-strips, to a k-ary relation quantifier-free definable in M, (2) any semibounded function from $M^{k}$ to M is equal, outside a finite union of k-strips, to a piecewise linear function, and (3) any semi-bounded in M endomorphism of the additive group of M is of the form x $\mapsto \sigmax$ , for some $\mapsto \sigma$ from the field of fractions of R. (shrink)

For a quasi variety of algebras K, the Higman Theorem is said to be true if every recursively presented K-algebra is embeddable into a finitely presented K-algebra; the Generalized Higman Theorem is said to be true if any K-algebra which is recursively presented over its finitely generated subalgebra is embeddable into a K-algebra which is finitely presented over this subalgebra. We suggest certain general conditions on K under which the Higman Theorem implies the Generalized Higman Theorem; a finitely generated K-algebra (...) A is embeddable into every existentially closed K-algebra containing a finitely generated K-algebra B if and only if the word problem for A is Q-reducible to the word problem for B. The quasi varieties of groups, torsion-free groups, and semigroups satisfy these conditions. (shrink)

For any countable transitive complete theory T with infinite models and the finite model property, we construct a minimal structure M such that the theory of M is small if and only if T is small, and is λ-stable if and only if T is λ-stable. This gives a series of new examples of minimal structures.