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     

Definability in the Substructure Ordering of Simple Graphs

For simple graphs, we investigate and seek to characterize the properties first-order definable by the induced subgraph relation. Let \({\mathcal{P}\mathcal{G}}\) denote the set of finite isomorphism types of simple graphs ordered by the induced subgraph relation. We prove this poset has only one non-identity automorphism co, and for each finite isomorphism type G, the set {G, G ^co } is definable. Furthermore, we show first-order definability in \({\mathcal{P}\mathcal{G}}\) captures, up to isomorphism, full second-order satisfiability among finite simple graphs. These results can be utilized to explore first-order definability in the closely associated lattice of universal classes. We show that for simple graphs, the lattice of universal classes has only one non-trivial automorphism, the set of finitely generated and finitely axiomatizable universal classes are separately definable, and each such universal subclass is definable up to the unique non-trivial automorphism.     

First-order decidability and definability of integers in infinite algebraic extensions of the rational numbers

We extend results of Videla and Fukuzaki to define algebraic integers in large classes of infinite algebraic extensions of Q and use these definitions for some of the fields to show the first-order undecidabilitv. We also obtain a structural sufficient condition for definability of the ring of integers over its field of fractions. In particular, we show that the following propositions hold: (1) For any rational prime q and any positive rational integer m. algebraic integers are definable in any Galois extension of Q where the degree of any finite subextension is not divisible by q^m. (2) Given a prime q, and an integer m > 0, algebraic integers are definable in a cyclotomic extension (and any of its subfields) generated by any set \(\{ {\zeta _{{p^l}}}|l \in {Z_{ > 0,}}P \ne q\) is any prime such that q^{m +1} ∧(p — 1)}. (3) The first-order theory of Any Abelina Extension of Q With Finitely Many Rational Primes is undecidable and rational integers are definable in these extensions.We also show that under a condition on the splitting of one rational Q generated elliptic curve over the field in question is enough to have a definition of Z and to show that the field is undecidable.     

On expansions and extensions of powerful digraphs

We study the problem of expanding and extending the structure of a stable powerful digraph to the structure of a stable Ehrenfeucht theory. We define the concepts of type unstability and type strict order property. We establish the presence of the type strict order property for every acyclic graph structure with an infinite chain. The simplest form of expansion of a powerful digraph to the structure of an Ehrenfeucht theory is the expansion with a 1-inessential ordered coloring and locally graph ?-definable many-placed relations, which enable us to mutually realize nonprincipal types; we prove that this expansion is incapable of keeping the structure in the class of stable structures, and moreover, by the type strict order property it generates the first-order definable strict order property. We define the concept of a locally countably categorical theory (LCC theory) and prove that given the list p ₁(x), ..., p _n (x) of all nonprincipal 1-types in an LCC theory, if all types r(x ₁, ..., x _m ) containing \(p_{i_1 } \) (x ₁) ∪ ... ∪ \(p_{i_m } \)(x _m ) are dominated by some type q then q is a powerful type.     

Powerful digraphs

We introduce the concept of a powerful digraph and establish that a powerful digraph structure is included into the saturated structure of each nonprincipal powerful type p possessing the global pairwise intersection property and the similarity property for the theories of graph structures of type p and some of its first-order definable restrictions (all powerful types in the available theories with finitely many (> 1) pairwise nonisomorphic countable models have this property). We describe the structures of the transitive closures of the saturated powerful digraphs that occur in the models of theories with nonprincipal powerful 1-types provided that the number of nonprincipal 1-types is finite. We prove that a powerful digraph structure, considered in a model of a simple theory, induces an infinite weight, which implies that the powerful digraphs do not occur in the structures of the available classes of the simple theories (like the supersimple or finitely based theories) that do not contain theories with finitely many (> 1) countable models.     

Elementary Properties of the Finite Ranks

This note investigates the class of finite initial segments of the cumulative hierarchy of pure sets. We show that this class is first-order definable over the class of finite directed graphs and that this class admits a first-order definable global linear order. We apply this last result to show that FO(<, BIT) = FO(BIT).     

Definability in Substructure Orderings,II: Finite Ordered Sets

Let \({{\uppercase {\mathcal{p}}}} \) be the ordered set of isomorphism types of finite ordered sets (posets), where the ordering is by embeddability. We study first-order definability in this ordered set. We prove among other things that for every finite poset P, the set \(\{p,p^{\partial}\}\) is definable, where p and \(p^{\partial}\) are the isomorphism types of P and its dual poset. We prove that the only non-identity automorphism of \({{\uppercase {\mathcal{p}}}}\) is the duality map. Then we apply these results to investigate definability in the closely related lattice of universal classes of posets. We prove that this lattice has only one non-identity automorphism, the duality map; that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice; and that for each member K of either of these two definable subsets, \(\{K,K^{\partial}\}\) is a definable subset of the lattice. Next, making fuller use of the techniques developed to establish these results, we go on to show that every isomorphism-invariant relation between finite posets that is definable in a certain strongly enriched second-order language \(\textup{\emph L}_2\) is, after factoring by isomorphism, first-order definable up to duality in the ordered set \({{\uppercase {\mathcal{p}}}}\). The language \(\textup{\emph L}_2\) has different types of quantifiable variables that range, respectively, over finite posets, their elements and order-relation, and over arbitrary subsets of posets, functions between two posets, subsets of products of finitely many posets (heteregenous relations), and can make reference to order relations between elements, the application of a function to an element, and the membership of a tuple of elements in a relation.     

Definability in substructure orderings, III: Finite distributive lattices

Let ${{\mathcal D}}$ be the ordered set of isomorphism types of finite distributive lattices, where the ordering is by embeddability. We study first-order definability in this ordered set. We prove among other things that for every finite distributive lattice D, the set {d, d ^opp} is definable, where d and d ^opp are the isomorphism types of D and its opposite (D turned upside down). We prove that the only non-identity automorphism of ${{\mathcal D}}$ is the opposite map. Then we apply these results to investigate definability in the closely related lattice of universal classes of distributive lattices. We prove that this lattice has only one non-identity automorphism, the opposite map; that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice; and that for each element K of the two subsets, {K, K ^opp} is a definable subset of the lattice.     

Abelian-by-central Galois groups of fields II: Definability of inertia/decomposition groups

This paper explores some first-order properties of commuting-liftable pairs in pro-? abelian-by-central Galois groups of fields. The main focus of the paper is to prove that minimized inertia and decomposition groups of many valuations are first-order definable using a predicate for the collection of commuting-liftable pairs. For higher-dimensional function fields over algebraically closed fields, we show that the minimized inertia and decomposition groups of quasi-divisorial valuations are uniformly first-order definable in this language.     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

Reducts of the random partial order

We determine, up to the equivalence of first-order interdefinability, all structures which are first-order definable in the random partial order. It turns out that there are precisely five such structures. We achieve this result by showing that there exist exactly five closed permutation groups which contain the automorphism group of the random partial order, and thus expose all symmetries of this structure.     

Topological dynamics and the complexity of strong types

We develop topological dynamics for the group of automorphisms of a monster model of any given theory. In particular, we find strong relationships between objects from topological dynamics (such as the generalized Bohr compactification introduced by Glasner) and various Galois groups of the theory in question, obtaining essentially new information about them, e.g., we present the closure of the identity in the Lascar Galois group of the theory as the quotient of a compact, Hausdorff group by a dense subgroup.We apply this to describe the complexity of bounded, invariant equivalence relations, obtaining comprehensive results, subsuming and extending the existing results and answering some open questions from earlier papers. We show that, in a countable theory, any such relation restricted to the set of realizations of a complete type over Ø is type-definable if and only if it is smooth. Then we show a counterpart of this result for theories in an arbitrary (not necessarily countable) language, obtaining also new information involving relative definability of the relation in question. As a final conclusion we get the following trichotomy. Let \(\mathfrak{C}\) be a monster model of a countable theory, p ∈ S(Ø), and E be a bounded, (invariant) Borel (or, more generally, analytic) equivalence relation on p(\(\mathfrak{C}\)). Then, exactly one of the following holds: (1) E is relatively definable (on p(\(\mathfrak{C}\))), smooth, and has finitely many classes, (2) E is not relatively definable, but it is type-definable, smooth, and has 2^?0 classes, (3) E is not type definable and not smooth, and has 2^?0 classes. All the results which we obtain for bounded, invariant equivalence relations carry over to the case of bounded index, invariant subgroups of definable groups.     

Directly Indecomposables in Semidegenerate Varieties of Connected po-Groupoids

We study varieties with a term-definable poset structure, po-groupoids. It is known that connected posets have the strict refinement property (SRP). In Sánchez Terraf and Vaggione (Trans Am Math Soc, in press) it is proved that semidegenerate varieties with the SRP have definable factor congruences and if the similarity type is finite, directly indecomposables are axiomatizable by a set of first-order sentences. We obtain such a set for semidegenerate varieties of connected po-groupoids and show its quantifier complexity is bounded in general. Supported by Conicet.     

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)     

Linear Groups Definable in o-Minimal Structures

We study subgroups G of GL(n, R) definable in o-minimal expansions M = (R, +, · ,…) of a real closed field R. We prove several results such as: (a) G can be defined using just the field structure on R together with, if necessary, power functions, or an exponential function definable in M. (b) If G has no infinite, normal, definable abelian subgroup, then G is semialgebraic. We also characterize the definably simple groups definable in o-minimal structures as those groups elementarily equivalent to simple Lie groups, and we give a proof of the Kneser–Tits conjecture for real closed fields.     

Models with second order properties IV. A general method and eliminating diamonds

We show how to build various models of first-order theories, which also have properties like: tree with only definable branches, atomic Boolean algebras or ordered fields with only definable automorphisms.For this we use a set-theoretic assertion, which may be interesting by itself on the existence of quite generic subsets of suitable partial orders of power λ⁺, which follows from ?_λ and even weaker hypotheses (e.g., λ=?₀, or λ strongly inaccessible). For a related assertion, which is equivalent to the morass see Shelah and Stanley [16].The various specific constructions serve also as examples of how to use this set-theoretic lemma. We apply the method to construct rigid ordered fields, rigid atomic Boolean algebras, trees with only definable branches; all in successors of regular cardinals under appropriate set- theoretic assumptions. So we are able to answer (under suitable set-theoretic assumptions) the following algebraic question.Saltzman's Question. Is there a rigid real closed field, which is not a subfield of the reals?     

Thom stratifications for functions definable in o-minimal structures on (R, +, ·)

We prove the existence of Thom stratifications for functions definable in any o-minimal structure on (R, +, ·).     

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.     

Definable groups of partial automorphisms

The motivation for this paper is to extend the known model-theoretic treatment of differential Galois theory to the case of linear difference equations (where the derivative is replaced by an automorphism). The model-theoretic difficulties in this case arise from the fact that the corresponding theory ACFA does not eliminate quantifiers. We therefore study groups of restricted automorphisms, preserving only part of the structure. We give conditions for such a group to be (infinitely) definable, and when these conditions are satisfied we describe the definition of the group and the action explicitly. We then examine the special case when the theory in question is obtained by enriching a stable theory with a generic automorphism. Finally, we interpret the results in the case of ACFA, and explain the connection of our construction with the algebraic theory of Picard–Vessiot extensions. The only model-theoretic background assumed is the notion of a definable set.      

Weakly o-minimal structures and real closed fields

A linearly ordered structure is weakly o-minimal if all of its definable sets in one variable are the union of finitely many convex sets in the structure. Weakly o-minimal structures were introduced by Dickmann, and they arise in several contexts. We here prove several fundamental results about weakly o-minimal structures. Foremost among these, we show that every weakly o-minimal ordered field is real closed. We also develop a substantial theory of definable sets in weakly o-minimal structures, patterned, as much as possible, after that for o-minimal structures.