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)     

Some Boolean Algebras with Finitely Many Distinguished Ideals I

We consider the theory Th_prin of Boolean algebras with a principal ideal, the theory Th_max of Boolean algebras with a maximal ideal, the theory Th_ac of atomic Boolean algebras with an ideal where the supremum of the ideal exists, and the theory Th_sa of atomless Boolean algebras with an ideal where the supremum of the ideal exists. First, we find elementary invariants for Th_prin and Th_sa. If T is a theory in a first order language and α is a linear order with least element, then we let Sentalg(T) be the Lindenbaum-Tarski algebra with respect to T, and we let intalg(α) be the interval algebra of α. Using rank diagrams, we show that Sentalg(Th_prin) ? intalg(ω⁴), Sentalg(Th_max) ? intalg(ω³) ? Sentalg(Th_ac), and Sentalg(Th_sa) ? intalg(ω² + ω²). For Th_max and Th_ac we use Ershov's elementary invariants of these theories. We also show that the algebra of formulas of the theory Tx of Boolean algebras with finitely many ideals is atomic.     

Integral representations of unbounded operators by infinitely smooth kernels

In this paper, we prove that every unbounded linear operator satisfying the Korotkov-Weidmann characterization is unitarily equivalent to an integral operator in L ₂(R), with a bounded and infinitely smooth Carleman kernel. The established unitary equivalence is implemented by explicitly definable unitary operators.     

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     

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?     

Stationary logic of ordinals

The L(aa)-theory of ordinals—Th_aa(On)—is studied. It is shown that Th_aa(On) is primitive recursive. In a suitable language it is possible to eliminate quantifiers. L(aa)-equivalence invariants are given. Both the complete L(aa)-theories of ordinals and the complete extensions of Th_aa(On) are characterized. An ordering is L(aa)-inductive if every L(aa)-definable subset (with suitable parameters) has a least element. The models of Th_aa(On) are the L(aa)-inductive orderings. A variant of the back and forth method is introduced in order toprove primitive recursive decidability and elimination of quantifier results.     

Some Boolean algebras with finitely many distinguished ideals II

We describe the countably saturated models and prime models (up to isomorphism) of the theory Th_prin of Boolean algebras with a principal ideal, the theory Th_max of Boolean algebras with a maximal ideal, the theory Th_ac of atomic Boolean algebras with an ideal such that the supremum of the ideal exists, and the theory Th_sa of atomless Boolean algebras with an ideal such that the supremum of the ideal exists. We prove that there are infinitely many completions of the theory of Boolean algebras with a distinguished ideal that do not have a countably saturated model. Also, we give a sufficient condition for a model of the theory T_X of Boolean algebras with distinguished ideals to be elementarily equivalent to a countably saturated model of T_X.     

Definability of closure operations in the <Emphasis Type="Italic">h</Emphasis>-quasiorder of labeled forests

We prove that natural closure operations on quotient structures of the h-quasiorder of finite and (at most) countable k-labeled forests (k ≥ 3) are definable provided that minimal nonsmallest elements are allowed as parameters. This strengthens our previous result which holds that each element of the h-quasiorder of finite k-labeled forests is definable in the first-order language, and each element of the h-quasiorder of (at most) countable k-labeled forests is definable in the language L _ω1ω; in both cases k ≥ 3 and minimal nonsmallest elements are allowed as parameters. Similar results hold true for two other relevant structures: the h-quasiorder of finite (resp. countable) k-labeled trees and k-labeled trees with a fixed label on the root element.     

Stably Definable Classes of Theories

A question is studied as to which properties (classes) of elementary theories can be defined via generalized stability. We present a topological account of such classes. It is stated that some well-known classes of theories, such as strongly minimal, o-minimal, simple, etc., are stably definable, whereas, for instance, countably categorical, almost strongly minimal, ω-stable ones, are not. __________ Translated from Algebra i Logika, Vol. 44, No. 5, pp. 583–600, September–October, 2005. Supported by RFBR grant Nos. 02-01-00540 and 05-01-00411, and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1.     

Chain conditions in dependent groups

In this note we prove and disprove some chain conditions in type definable and definable groups in dependent, strongly dependent and strongly² dependent theories.     

Functorial implicit operations

Two forms of Keisler's characterization of functorial predicates are established for implicity definable infinitary operations. In particular, functorial and implicity definable ⇒ explicitly definable.     

Remarks on generic stability in independent theories

In NIP theories, generically stable Keisler measures can be characterized in several ways. We analyze these various forms of “generic stability” in arbitrary theories. Among other things, we show that the standard definition of generic stability for types coincides with the notion of a frequency interpretation measure. We also give combinatorial examples of types in NSOP theories that are finitely approximated but not generically stable, as well as ϕ-types in simple theories that are definable and finitely satisfiable in a small model, but not finitely approximated. Our proofs demonstrate interesting connections to classical results from Ramsey theory for finite graphs and hypergraphs.     

Definable Ramsey and definable Erdös ordinals

This paper studies the relation between definable Ramsey ordinals and constructible sets which have a certain set of indiscernibles. It is shown that an ordinal κ is Σ₁-Ramsey if and only if κ is ∑_ω-Ramsey. Similar results are obtained for definable Erdös ordinals.     

on the o-minimal LS-category

We introduce the o-minimal LS-category of definable sets in o-minimal expansions of ordered fields and we establish a relation with the semialgebraic and the classical one. We also study the o-minimal LS-category of definable groups. Along the way, we show that two definably connected definably compact definable groups G and H are definable homotopy equivalent if and only if L(G) and L(H) are homotopy equivalent, where L is the functor which associates to each definable group its corresponding Lie group via Pillay’s conjecture.     

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.     

Herbrandizing search problems in Bounded Arithmetic

We study search problems and reducibilities between them with known or potential relevance to bounded arithmetic theories. Our primary objective is to understand the sets of low complexity consequences (esp. Σ^b₁ or Σ^b₂) of theories Sⁱ₂ and Tⁱ₂ for a small i, ideally in a rather strong sense of characterization; or, at least, in the standard sense of axiomatization. We also strive for maximum combinatorial simplicity of the characterizations and axiomatizations, eventually sufficient to prove conjectured separation results. To this end two techniques based on the Herbrand's theorem are developed. They characterize/axiomatize Σ^b₁‐consequences of Σ^b₂‐definable search problems, while the method based on the more involved concept of characterization is easier and gives more transparent results. This method yields new proofs of Buss' witnessing theorem and of the relation between PLS and Σ^b₁(T¹₂), and also an axiomatization of Σ^b₁(T²₂). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Coherent Functors and Covariantly Finite Subcategories

Given a locally presentable additive category A, we study a class of covariantly finite subcategories which we call definable. A definable subcategory arises from a set of coherent functors F _i on A by taking all objects X in A such that F _i X=0 for all i. We give various characterizations of definable subcategories, demonstrating that all covariantly finite subcategories which arise in practice are of this form. This is based on a filtration of the category of all coherent functors on A.     

Definability of Geometric Properties in Algebraically Closed Fields

We prove that there exists no sentence F of the language of rings with an extra binary predicat I₂ satisfying the following property: for every definable set X ? ?², X is connected if and only if (?, X) ? F, where I₂ is interpreted by X. We conjecture that the same result holds for closed subset of ?². We prove some results motivated by this conjecture.